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.
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?
3
votes
3answers
4k views
RSA encryption with private key and decryption with a public key
Does the encryption with a private key and decryption with a public key works in RSA? Is it done when we use RSA for sender authentication ?
Thanks.
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?
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 ...
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.
...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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, ...
2
votes
4answers
846 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
...
2
votes
1answer
408 views
Is RSA of a random nonce with no padding safe?
Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a ...
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. ...
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 ...
1
vote
2answers
175 views
One-way function and factoring
I am confused about the hardness of the one-way function behind cryptography -- if someone could factor the large number produced back into two primes quickly then the one-way function would be ...
10
votes
8answers
847 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 ...
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, ...
4
votes
1answer
224 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 private key d.
I can calculate phi(N) = 40, but my lecturer then says to use the extended Euclidean algorithm to compute d. ...
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
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 ...
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
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) ...
4
votes
2answers
335 views
RSA and prime difference
It is known that the two prime factors $p$ and $q$ of an RSA modulus $n$ should not be too close to each other, otherwise an attacker may factor the modulus. In other words, $\Delta = \left| p - q ...
4
votes
1answer
113 views
In RSA, rationale for prime $p$ with $p-1$ having prime factor $u$ with $u-1$ having large prime factor?
In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors ...
4
votes
0answers
78 views
RSA security assumptions - does breaking the DLP also break RSA? [duplicate]
Possible Duplicate:
Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?
I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, ...
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 ...
2
votes
1answer
246 views
Is a known plaintext, ciphertext, and public-key a viable attack on RSA?
Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key.
Alice and Bob each have their public- and private-key pairs ...
2
votes
1answer
97 views
RSA Without Padding?
I've been looking at the weakness with plain/textbook RSA, where the same message is encrypted and sent to multiple destinations. In this case, it is possible to recover the message.
Given that an ...
2
votes
1answer
267 views
What is the harm if I publish an encrypted RSA private key publicly?
What is the harm if I publish an encrypted RSA private key publicly? Or in this case, what is the harm if I publish many thousands or millions of them?
Assuming that the private key is encrypted ...
1
vote
1answer
131 views
using Post-quantum asymmetric ciphers instead of RSA
We can't trust RSA to encrypt our Emails so what is best post-quantum cryptography system as alternative for RSA which provide good security and don't be breakable? because McEliece cryptosystem looks ...
1
vote
2answers
117 views
RSA keys finding when messages are known
I have this situation, where, in a game, people send messages to each other (game moves etc...) These messages need to be encrypted, and should only be readable by the destination person. I am using ...
1
vote
0answers
76 views
Two untrusted party want to exchange data: how to ensure each one gets the data it needs? [duplicate]
Possible Duplicate:
Two untrusted party want to exchange data: how to insure each one gets the data it needs?
I am trying to come up with what could maybe be a novel algorithm for an ...
0
votes
1answer
45 views
chaining rsa with ecies
In an answer to a previous question it was suggested that one way to protect your asymmetrically encrypted AES-256 keys, from say a solution to prime factorization, would be to chain asymmetric ...
0
votes
2answers
85 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 ...
0
votes
1answer
218 views
What is the correct value for “certainty” in RSA key pair generation?
I'm creating an RSA key pair in Bouncy Castle and need to specify an int value for certainty. This Stack Overflow answer says it is a relative test for how prime the values are.
There is another ...
-1
votes
1answer
82 views
What length should the padding be when encrypting or signing with RSA?
Does it matter what length the padding is? If so - what length should it be?
(Another point: Should it be random?)
