Questions tagged [rsa]

an asymmetric (e.g. public-key) cryptosystem, based on modular exponentiation with big exponents and modulus. RSA can be used both for signature and encryption.

Filter by
Sorted by
Tagged with
3
votes
1answer
2k views

Why do we need in RSA the modulus to be product of 2 primes?

I think I roughly understand how the RSA alorithm is working. However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$. I vaguely know it ...
3
votes
0answers
161 views

IND-CCA1 RSA padding?

I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property. I'm restricted to RSA (any padding; for hardware ...
3
votes
2answers
3k views

Can RSA (theoretically) be used as a block cipher?

Assume AES gets a devastating attack making it unusable. Is it possible to use RSA in a secure way that can encrypt data in bulk? I can't see how RSA (assuming OAEP padding) can be used in normal ...
43
votes
2answers
63k views

Signatures: RSA compared to ECDSA

I'm signing very small messages using RSA, and the signature and public key are added to every message, which requires a lot of space compared to the actual content. I'm considering switching to ...
31
votes
2answers
38k views

What's the fundamental difference between Diffie-Hellman and RSA?

What is the difference in the purpose of DH and RSA? Aren't they both public-key encryption?
39
votes
1answer
4k views

What is “Fast Prime”?

In this note, the manufacturer of a RSA key generation gizmo vulnerable to the new ROCA attack (see second section) explains that it is common practice to employ acceleration algorithms in order to ...
28
votes
4answers
11k views

Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the ...
17
votes
1answer
22k views

Low Public Exponent Attack for RSA

I'm having trouble understanding the algorithm for finding the original message $m$, when there is a small public exponent. Here is the example I'm trying to follow (you can also read it in the 'Low ...
4
votes
1answer
7k views

What is a trapdoor permutation?

Can anyone explain to me what a trapdoor one-way permutation is? Is RSA a trapdoor one-way permutation? Context: I was reading about ring signatures. On page 560, it describes steps to implementing ...
13
votes
2answers
5k views

Can two different pairs of RSA key have the same modulus?

Can $n=pq$ be part of two different pairs of RSA keys? If such keys exist, say $(e_1,n)$ and $(e_2,n)$, how are they related? What will be the security concerns for the two users?
6
votes
2answers
16k views

What is the meaning of “trapdoor” in cryptography?

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions: What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
32
votes
1answer
11k views

Why do all SSH-RSA Keys begin with “AAAAB3NzaC1yc”?

My Friend and I have been generating a few ssh2-rsa keys and noticed that all the public keys began with "AAAAB3NzaC1yc". The similarity extended to "AAAAB3NzaC1yc2EAAAABIwAAAQEA" between two keys I ...
12
votes
6answers
30k views

How do ciphers change plaintext into numeric digits for computing?

For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption. If our message is "hello world", then what number do we have to ...
10
votes
1answer
451 views

Collision resistance of hash function built on modular exponentiation

Consider the following hash function family for hashing integers: $Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$. $H_{(n,y)}(x) = y^x \...
10
votes
1answer
1k views

Safe primes in RSA

It's my understanding that there's no longer a requisite of safe primes for $q$ and $p$ when choosing a RSA modulus. How is it that this does not change the hardness of factoring $N$?
15
votes
5answers
3k views

Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

I have just learned about using PGP/GPG for email encryption and one thing bugs me: How is it possible that a message encrypted with somebody's public key can be decrypted only with that person's ...
11
votes
4answers
7k views

Is it possible to get an RSA encryption key by comparing the unencrypted and encrypted file?

Exactly what the title says. If I have a RSA encrypted file, and the exact same file but decrypted, can I tell the key that was used from that information?
10
votes
1answer
260 views

IND-CPA secure RSA padding with a partial homomorphic property

A while ago, I asked for an IND-CCA1 secure padding for RSA that still allows for the multiplicative homomorphic property of RSA and got no answers (yet). Now I've seen fgrieu's answer about standard ...
7
votes
2answers
2k views

What's the difference between rsa_pss_pss_* and rsa_pss_rsae_* schemes?

I'm trying to understand the difference between rsa_pss_pss_ and rsa_pss_rsae_. The picture shows the extension of TLS1.3's ...
5
votes
2answers
2k views

Why is Diffie Hellman used alongside public keys?

I just read this post here: Why do we need asymmetric algorithms for key exchange? that asserts that in public key cryptography when asymmetric keys are used to secure communications, for parties to ...
4
votes
4answers
7k views

Is 512-bit RSA still safe for signature generation?

The standard CSP on Windows XP only supports RSA up to 512-bit, which means that it's the maximum key size I can use for authenticity verification of updates. The public key is embedded in the updater,...
3
votes
1answer
7k views

How much safer is RSA-OAEP compared to RSA with PKCS#1 v1.5 padding?

Is there a way to calculate how much safer RSA-OAEP is compared to RSA with PKCS#1 v1.5 compliant padding? Or is there a good rule of thumb?
8
votes
2answers
3k views

Why is the complexity of RSA-1024 80 bit and not 86 bit?

Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit? Here is the complexity for the GNFS (pulled from the linked Wikipedia article): $$\exp\left( \left(\sqrt[3]{\frac{64}{...
6
votes
1answer
402 views

Can RSA-PSS signing be made deterministic without loss of security?

Is it possible to make RSA-PSS signing deterministic without loss of security? Specifically, I would use Blake2b of the key and message to generate the salt.
5
votes
2answers
3k views

Calculate the RSA private exponent from the CRT parameters

I am trying to make the RSA structure of Openssl manually, knowing the public key ($n$, $e$) and the CRT parameters $p$, $q$, $d_P$, $d_Q$, and $u = q^{-1} \mod p$. That is, I want to get the $d$ ...
4
votes
1answer
3k views

RSA key pair generation using PRNG with same seed

I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static ...
4
votes
4answers
1k views

Why $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ for RSA crypto?

For RSA cryptography, we know that the modulo $n$ is a product of two big prime numbers(say $p$ and $q$). However, in some documents I see an extension of $p=2p'+1$ and $q=2q'+1$ with $q'$ and $p'$ ...
3
votes
2answers
2k views

Encryption with private key?

we normally always encrypt by public key and decrypt with private key. If i encrypt with private key, then its still secure as normal PKI ? i mean known-plain-text will not take private key on the ...
3
votes
1answer
1k views

Why is RSA usually limited to messages up to 1 block [duplicate]

I'm wondering why RSA encryption usually is only used for messages that fit into one block. For larger messages hybrid encryption in combination with symmetric ciphers like AES seem to be the solution ...
2
votes
2answers
3k views

Could Riemann hypothesis solve certainly RSA?

I don't have the background for dealing with Riemann hypothesis but is well known that covers the prime distribution below a specified number. In order to solve the RSA problem you have to factor the ...
9
votes
4answers
706 views

Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?

Alice is going to use some existing RSA scheme (employing industry-standard signature or/and encryption with proper padding), which she can't change, or influence beyond her choice of key. In this ...
7
votes
1answer
745 views

Exposing RSA private-key data… bad?

We know that exposing $p$, or $q$ or $\phi(n)$ results in trivial attacks on RSA since they allow us to factor $n$ and to compute the private exponent $d$. In OpenSSL (and most RSA implementations) ...
6
votes
1answer
1k views

Modular exponentiation on calculator for textbook RSA

How do you encrypt $51$ with public key $(n,e) = (91,23)$ I understand that $c = 51^{23} \bmod 91$. How can I calculate the result on a calculator?
6
votes
4answers
3k views

How do institutions like banks do RSA with big primes?

When encrypting with RSA it is often infeasible to decrypt by just doing c^d mod n, because for example when using the primes $(p,q)=(12553,1233)$, which are small ...
5
votes
1answer
884 views

In the RSA DES challenges, how did the contestants know they had found the right key considering they weren't given any plaintext?

If the contestants were given both the plaintext and ciphertext, it's straightforward. Just bruteforce all 56-bit keys until you find one that maps the given plaintext to the given ciphertext. But ...
5
votes
2answers
1k views

Generation of strong primes

It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes $p$ where $(p-1)$ has a very large prime factor. Is there any information regarding the ...
5
votes
1answer
1k views

Why is it claimed that ElGamal is worse than RSA?

I have some notes that claim that ElGamal is worse than RSA in the sense that ElGamal is length-increasing. Do anybody know what this means and why is a bad property? Edit: For completeness I show ...
5
votes
2answers
5k views

What does an RSA signature look like?

I am using OpenSSL libs to generate signatures. Internally, I learn that a signature is a hash of the message with some padding added to it. I am trying to understand the structure of a signature. If ...
5
votes
1answer
109 views

Random Masking of Padded RSA Ciphertext through homomorphism

I had asked a question related to this before: Oblivious Decryption: Decrypting with a private key, without knowing the message @rikhavshah has an answer, which I would like to discuss the security ...
5
votes
1answer
5k views

Common modulus attack on RSA when the 2 public exponents differ by a single bit

This is an exam question an i have no idea how to recover the message m. John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and ...
4
votes
2answers
2k views

Is there a way to systematically calculate the public exponent $e$ in RSA?

I'm learning RSA in one of my classes and we were given a problem: $p = 5$, $q = 11$ I have done the following steps: $n = 5 \cdot 11 = 55$ $\phi = (5-1)\cdot(11-1) = 40$ I know that to find ...
4
votes
2answers
849 views

How common are weak RSA keys?

There exist certain attacks that can be used against RSA keys whose prime factors are of specific forms, such as one by Coppersmith. How common are these RSA keys? If you generate primes randomly, ...
4
votes
4answers
510 views

Where does the $\varphi(n)$ part of RSA come from?

$e d \equiv 1 \pmod{\varphi(n)}$ Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?
3
votes
1answer
2k views

Finding public exponent e

I'm trying to create an algorithm to find the public exponent e given a plain (non-CRT) private key that doesn't include the public exponent, i.e. I've only got $n$ and $d$. A question has already ...
3
votes
2answers
1k views

risk of attacker decrypting RSA ciphertext without public or private key

As I describe in my previous question I am trying to decide if it's worth it for me to use the Offline Private Key Protocol in creating some long term private archives, instead of just going with a ...
2
votes
2answers
3k views

Why RSA uses {d,n} as private key instead of {e,n}?

While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d ...
42
votes
6answers
3k views

How to check that you got the right key when brute forcing an encryption?

How do you know when you have the right key when brute-forcing? Let's say that they test the right key. They then have to check that the decrypted text makes sense. To do so, they can test whether ...
5
votes
1answer
194 views

Is there a standard padding/format for RSA Blind Signatures?

I'm working on a RSA blinded signature scheme. RSA Blind signatures are discussed in Chaum's original paper and other places like wikipedia. The descriptions of RSA blind signatures are straight ...
5
votes
4answers
7k views

Is it safer to encrypt twice with RSA?

I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
5
votes
2answers
522 views

Timing attacks against RSA, DH and AES

I have been reading about “Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension” by Wing H. Wong. I was wondering if this attack is feasible while signing with RSA and, if yes, ...