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.
21
votes
4answers
6k 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 ...
20
votes
3answers
3k 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?
19
votes
10answers
2k 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 ...
19
votes
4answers
5k 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 ...
17
votes
2answers
820 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. ...
16
votes
3answers
1k 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 ...
13
votes
4answers
545 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 ...
10
votes
8answers
846 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 ...
9
votes
4answers
1k 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.
8
votes
5answers
419 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 ...
8
votes
2answers
755 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?
8
votes
4answers
637 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 ...
8
votes
3answers
2k 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 ...
8
votes
2answers
466 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$ ...
8
votes
3answers
372 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 ...
8
votes
3answers
240 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 ...
8
votes
2answers
548 views
Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC) ?
Related to this question.
Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts be distinguished from random noise? Justify why, why ...
7
votes
7answers
3k 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.
...
7
votes
1answer
314 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 ...
7
votes
2answers
591 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 ...
7
votes
1answer
1k views
Why has the RSA factoring challenge been withdrawn?
Wikipedia states that RSA challenge has been withdrawn.
Does it mean that an efficient factoring algorithm is "just around the corner"?
or are there some other reasons?
If the challenge was still ...
7
votes
0answers
131 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 ...
6
votes
3answers
1k views
Why RSA encryption key is based on modulo(phi(n)) rather than modulo n
While calculating RSA encryption key we take modulo(phi(n)) rather that modulo(n). I couldn't understand why its so?
6
votes
2answers
1k 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?
6
votes
2answers
268 views
What is the key strength reduction encrypting only 160 bits of data using RSA1024 for signatures
I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, ...
6
votes
2answers
997 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 ...
6
votes
3answers
430 views
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.
RSA labs makes a similar statement:
The discrete logarithm problem bears the same ...
6
votes
2answers
150 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 ...
6
votes
4answers
402 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 ...
6
votes
2answers
535 views
How much can we compress RSA public keys?
I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a ...
6
votes
1answer
1k views
How do other, non-RSA algorithms, compare to the PKCS #1 standard?
Arguably the PKCS suite of standards have a profit-oriented bias as they are promoted by RSA and promote their algorithms over others in the form of RFCs and other means.
I'm considering the ...
6
votes
3answers
354 views
Security equivalence proofs for breaking RSA
It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.
In otherwords, ...
5
votes
3answers
427 views
Is RSA padding needed for single recipient, one-time, unique random message?
I want a way to encrypt files using this process: http://crypto.stackexchange.com/a/15 . That is: generate a random password, use that to AES-encrypt a file, and use an RSA public key to encrypt the ...
5
votes
3answers
584 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 ...
5
votes
1answer
297 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) ...
5
votes
1answer
113 views
Including a “purpose” designation in a digital signature
A signature of some data can mean many different things, such as: This is a message I sent, this is a certificate I validated,... So I was surprised that common signing schemes don't include a ...
5
votes
1answer
348 views
Would RSA-encrypting a private key for itself constitute a vulnerability?
I'm planning to encrypt some individual files for storage, using the GnuPG implementation of RSA. If I happened to encrypt the private key corresponding to the public key used for encrypting -- either ...
5
votes
2answers
723 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 ...
5
votes
1answer
813 views
Chinese Remainder Theorem and RSA
Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption ...
5
votes
1answer
630 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:
...
5
votes
1answer
674 views
RSA-PSS salt size
One of the inputs of RSA-PSS signing and verification is the salt size. According to PKCS#1, you must know the salt size before the verfication is carried out. However, this makes interoperability ...
5
votes
1answer
271 views
Are there any MGF1 and OS2IP functions available in C?
I need MGF1 and OS2IP functions, as defined in the PKCS #1 v2.1: RSA Cryptography Standard.
Is there anything available in OpenSSL, or any other open C library?
5
votes
1answer
102 views
Proof that padded RSA is CPA-secure
I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA:
${\bf Key Generation:}$ same as Textbook RSA (given security parameter ...
5
votes
1answer
116 views
In textbook RSA with low public exponent, how big does a random message needs to be?
Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod ...
5
votes
2answers
2k 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?
5
votes
1answer
356 views
RSA-OAEP Input Parameters
When creating padding for RSA using OAEP, a message is prepared as follows:
Hash(Input Parameter) || Zeros || 1 || Message
My question is, what should the Input ...
4
votes
4answers
412 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?
4
votes
3answers
207 views
Initialize a PRNG with a password
Let's assume that we have a secure PRNG. Is it "safe" to initialize it with password, or seed based on a password like SHA256(password).
If yes, is it "safe" to generate as RSA or DSA key from it? If ...
4
votes
2answers
295 views
Does RSA padding have to be unpredictable if the payload is?
I'm trying to understand the precise requirements on padding when using RSA for encryption.
Suppose Alice uses RSA to encrypt a payload $M$ that cannot be guessed (say, a random nonce): Alice send ...
4
votes
2answers
2k views
Cracking plain RSA without private key
I was wondering whether plain RSA encryption can be cracked given:
The public key
A plaintext of a known cipher text(s).
In other words the decrypted message from an encrypted one (but without ...
