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.

learn more… | top users | synonyms

72
votes
3answers
47k views

Why is elliptic curve cryptography not widely used, compared to RSA?

I recently ran across elliptic curve crypto-systems: An Introduction to the Theory of Elliptic Curves (Brown University) Elliptic Curve Cryptography (Wikipedia) Performance analysis of identity ...
40
votes
5answers
13k views

How big an RSA key is considered secure today?

I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
36
votes
3answers
12k views

How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

RSA is not designed to be used on long blocks of plaintext like a block cipher, but I need to use it to send a large message. How can I do this?
33
votes
4answers
24k views

How can I generate large prime numbers for RSA?

What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption? I'm aware that I can find any number of articles on the Internet that explain how ...
30
votes
9answers
6k views

Now that quantum computers have been out for a while, has RSA been cracked?

D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum ...
27
votes
4answers
4k views

How are primes generated for RSA?

As I understand it, the RSA algorithm is based on finding two large primes (p and q) and multiplying them. The security aspect is based on the fact that it's difficult to factor it back into p and q. ...
24
votes
2answers
1k views

What security authorities and standards reject $e=3$ in RSA, when, and with what rationale?

In RSA, some security authorities and/or standards allow the public exponent $e=3$, others require or recommend $e>2^{16}$ (or perhaps some other minimum). I gathered the following: PKCS#1 allows ...
16
votes
5answers
1k views

Is it feasible to build an index of prime factors?

Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
16
votes
6answers
6k views

Is Diffie-Hellman mathematically the same as RSA?

Is the Diffie-Hellman key exchange the same as RSA? Diffie Hellman allows key exchange on a observed wire – but so can RSA. Alice and Bob want to exchange a key – Big brother is watching everything. ...
16
votes
5answers
2k views

Does RSA work for any message M?

I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but ...
16
votes
1answer
14k views

How does RSA signature verification work?

I understand how the RSA algorithm works for encryption and decryption purposes but I don't get how signing is done. Here's what I (think) I know and is common practice: If I have a message that I ...
15
votes
4answers
1k views

Is Wiener's attack on RSA extendable to larger keys with low hamming weight?

Using small private exponents with RSA improves performance. However, it has been shown (Wiener, 1990) that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the ...
15
votes
2answers
7k views

Impacts of not using RSA exponent of 65537

This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower? What are the ...
15
votes
1answer
4k views

Security strength of RSA in relation with the modulus size

NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits: ...
14
votes
8answers
3k views

RSA with small exponents?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse ...
13
votes
3answers
26k views

RSA encryption with private key and decryption with a public key

When using the RSA cryptosystem, does it still work if you instead encrypt with the private key and decrypt with the public key? What about in the case of using RSA for sender authentication?
13
votes
2answers
7k views

Definition of Textbook RSA

What is the definition of Textbook RSA? What are some of the properties of textbook RSA? How does it differ from other RSAs?
13
votes
2answers
13k 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 ...
13
votes
2answers
14k 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?
13
votes
1answer
3k 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 ...
12
votes
4answers
2k views

Why RSA encryption key is based on modulo $\varphi(n)$ rather than modulo $n$

While calculating RSA encryption key we take modulo $\varphi(n)$ rather that modulo $n$. I couldn't understand why its so?
12
votes
1answer
315 views

RSA with probable primes

I am a bit of a newbie to RSA encryption, so please be patient. I understand that for a 4096 bit RSA, the numbers p and q should be prime. And to have the best security, the p and q should both be ...
12
votes
1answer
10k views

Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

When given $p = 5, q = 11, N = 55$ and $e = 17$, I'm trying to compute the RSA private key $d$. I can calculate $\varphi(N) = 40$, but my lecturer then says to use the extended Euclidean algorithm to ...
11
votes
2answers
2k 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?
11
votes
2answers
4k views

Are there practical upper limits of RSA key lengths?

Suppose one wanted to use RSA encryption for the sole purpose of sending key bits for use in symmetric crypto systems, a dedicated key exchange system so to speak. And say you didn't think that the ...
11
votes
3answers
1k views

Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?

Related to "Is it possible to derive the encryption method from encrypted text?". Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts ...
10
votes
3answers
5k views

What is the relation between RSA & Fermat's little theorem?

I came across this while refreshing my cryptography brain cells. From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
10
votes
2answers
819 views

Why RSA can't handle numbers above 76?

I'm going to encrypt the characters Zhu, and decrypt them using RSA. I'm using the public key $\{e, n\}$ and private key $\{d, n\}$. The values of $e$, $d$ and $p$ ...
10
votes
1answer
2k views

How many RSA keys before a collision?

I was wondering how many possible private/public keys exist? If a million people – for whatever reason – would try to generate 5 keys each in the same minute (on the same date and time) is there a ...
10
votes
4answers
1k 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 has always bugged me: How is it possible that a message encrypted with somebody's public key can be decrypted only with that ...
10
votes
3answers
333 views

Is it possible to create an asymmetric cryptosystem where the private keys are not easily verifiable as such?

Plaintext that consists of an RSA key is easily recognizable as such, because it satisfies certain mathematical properties, in particular (See the answer for Why can an encrypted private key be brute ...
10
votes
2answers
12k views

When to use RSA and when ElGamal asymmetric encryption

If i am not wrong in cryptography there are 2 basic cryptographic schemes for public key cryptography. RSA encryption whose security is based on the infeasibility of solving the factoring of big ...
10
votes
3answers
3k views

Is it possible to validate a Public Key in RSA?

If I have a 1024-bit number, and someone is telling me that it is in fact a valid RSA public key, is there any way I can quickly validate that it is indeed so (without cracking RSA)? (I suppose I am ...
10
votes
2answers
10k views

Difference between “Signature Algorithm” and “Signature Hash Algorithm” in X.509

What's the difference between the "Signature Algorithm" and the "Signature Hash Algorithm" found in an X.509 certificate? Why does it need a "Signature Hash Algorithm"? Edit: I'm creating the ...
10
votes
1answer
1k views

Bleichenbacher 1998 “Million message attack” on RSA

I have been reading Bleichenbacher's 1998 paper on a forged message attack on RSA. The paper assumes access to an Oracle that takes a ciphertext $c$ and will check the decrypted text for valid PKCS #1 ...
10
votes
0answers
500 views

Who first published the interest of more than two prime factors in RSA?

Multi-prime RSA is now a well known technique: it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed boost in ...
9
votes
1answer
3k 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 ...
9
votes
4answers
3k views

Encrypting small values with RSA private key

I'm looking for best practices when it comes to encrypting small (< 128 bytes) amounts of data with the RSA private key. Signing it would make the resulting payload too large.
9
votes
3answers
5k views

Why hash the message before signing it with RSA?

The diagram below illustrates the process of digitally signing a message with RSA: As diagram shows, the message is first hashed, and the signature is then computed on the hash, rather than on the ...
9
votes
4answers
10k views

Why is padding used for RSA encryption given that it is not a block cipher?

In AES we use some padded bytes at end of message to fit 128/256 byte blocks. But as RSA is not a block cipher why is padding used? Can the message size be any byte length (is the encrypting agent ...
9
votes
3answers
573 views

Can we ensure the security of a crypto-algorithm and -implementaton against acoustic cryptanalysis?

Like people always say: “Attacks only get worse…” — which is why I'm asking early. I have been reading the paper “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis” published December 18, ...
9
votes
3answers
517 views

Is it reasonable to assure that p-1 and q-1 aren't smooth?

I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question: How complicated is it to check whether $p-1$ is ...
9
votes
1answer
2k views

Why does the PKCS1 RSA private key structure contain more than just exponent and modulus?

The ASN.1 spec for the PKCS1 RSA private key format is as follows: ...
9
votes
1answer
746 views

What changed in PKCS#1 v2.2, and why?

PKCS#1 is one of the most used (de-facto) standard for real-world use of RSA. That's for good reasons: PKCS#1 is well thought, versatile, understandable, has been relatively stable for over two ...
8
votes
4answers
3k views

Why is it important that phi(n) is kept a secret, in RSA?

Why is it important that $\phi(n)$ is kept a secret, in RSA?
8
votes
4answers
1k views

Why are RSA key sizes almost always a power of two?

I know that other bit sizes are possible, e.g. this HTTPS server seems to have a 9000 bit key https://www.ssllabs.com/ssltest/analyze.html?d=qqq.gg, but it's very rare that one sees a key not of size ...
8
votes
2answers
738 views

Can RSA encryption produce collisions?

In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.) My question is, can $m^e$ be ...
8
votes
2answers
809 views

Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus?

In standard RSA, the modulus $n=p_1 p_2$ is a product of two primes $p_1,p_2$ of the same size. Suppose we construct the modulus as a product of multiple primes $p_1,\dots,p_k$, i.e., $n=p_1 p_2 ...
8
votes
5answers
509 views

RSA leak bits to factor N

Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q. Then, you would like to actually let me factor N, except you should tell me as few bits of ...
8
votes
2answers
4k views

What are advantages of using a HMAC over RSA with SHA-1 hashes?

I am currently studying for an exam and this was a previous question: Give one advantage of using HMACs over using RSA to sign SHA-1 hashes. My thoughts are that it has something to do with the ...