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

34
votes
5answers
6k 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 ...
10
votes
2answers
5k 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?
31
votes
3answers
9k 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?
24
votes
2answers
932 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 ...
11
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?
15
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 ...
2
votes
2answers
277 views

Which attacks are possible against raw/textbook RSA?

The PKCS#1 standard defines multiple padding schemes for signature generation/verification (EMSA-PSS and EMSA-PKCS1-v1_5), and encryption/decryption (EME-OAEP and the less safe EME-PKCS1-v1_5). ...
8
votes
3answers
17k 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?
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 ...
64
votes
3answers
40k 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 ...
30
votes
10answers
5k 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 ...
5
votes
1answer
5k 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 ...
11
votes
1answer
2k 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: ...
4
votes
1answer
257 views

how to use common modulus attack?

I am struck with the following problem: Let Alice, Bob, Chris and Eve communicate over a public network. They encrypt all messages they send using RSA system. Bob and Chris have the RSA modulus ...
1
vote
4answers
676 views

RSA with composite numbers

It has been said that RSA uses a modulus product of two prime numbers for security reasons. But does RSA even work correctly if we allow composite integers instead? I think that the answer is "NO". ...
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 ...
7
votes
3answers
892 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 ...
7
votes
3answers
1k 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 ...
1
vote
2answers
219 views

Attacks against El Gamal private key

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know. What are some efficient and strong algorithms ...
28
votes
4answers
18k 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 ...
10
votes
3answers
4k 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 ...
12
votes
2answers
5k 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 ...
5
votes
2answers
5k views

How much computing resource is required to brute-force RSA?

It's been over 30 years since Rivest, Shamir and Adleman first publicly described their algorithm for public-key cryptography; and the intelligence community is thought to have known about it for ...
6
votes
4answers
2k 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?
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
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. ...
10
votes
1answer
6k 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 ...
9
votes
3answers
2k 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 ...
8
votes
2answers
431 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
1answer
1k 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 ...
6
votes
1answer
2k 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 ...
7
votes
3answers
2k views

Why hash or salt when signing?

I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV. Why is that needed?
5
votes
1answer
2k 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 ...
5
votes
4answers
7k 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 ...
4
votes
1answer
291 views

Is knowing the private key of RSA equivalent to the factorization of $N$?

Given the RSA modulus $N$ the fastest method to factor it is of sub-exponent order. But, now if I know the private key $d$ of RSA, does that mean I can factor $N$ efficiently?. It intuitively seems ...
3
votes
2answers
242 views

Is RSA encryption of a cryptographic hash with a private key the same as signature generation?

It is often said that RSA encryption with a private key is the same as signing (signature generation). Will RSA encryption with a private key over a cryptographic hash give the same result as ...
3
votes
1answer
2k views

RSA cracking: The same message is sent to two different people problem

Suppose we have two people: Smith and Jones. Smith public key is e=9, n=179 and Jones public key is e=13, n=179. Bob sends to ...
2
votes
1answer
379 views

Attack of an RSA signature scheme using PKCS#1 v1.5 encryption padding

My best interpretation of this question is that Java's crypto API has been subverted to perform RSA signature using PKCS#1 v1.5 encryption padding. Assume the signature $S$ of a message $M$ is ...
-3
votes
1answer
147 views

Currently i am doing decryption for RSA encoding and i face some problem with it [closed]

I am very new to cryptography so I don’t know much about it. I have been given a very large $N$ value and $E$ value to decrypt a ciphertext which was created using a AES 128 key and a IV by using RSA ...
26
votes
3answers
3k 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. ...
10
votes
2answers
9k 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
2answers
5k views

How does a chosen plaintext attack on RSA work?

How can one run a chosen plaintext attack on RSA? If I can send some plaintexts and get the ciphertexts, how can I find a relation between them which helps me to crack another ciphertext?
9
votes
0answers
355 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 ...
8
votes
1answer
8k 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 ...
2
votes
2answers
3k views

What makes RSA secure by using prime numbers?

I am just learning about the RSA algorithm. Looking at the first two steps: Choose two distinct prime numbers $p$ and $q$. Compute $n = pq$. I have some probably stupid questions: Why do $p$ ...
2
votes
1answer
877 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 ...
5
votes
2answers
1k views

RSA blind signatures in practice

Hi I have a problem with moving my blind signature implementation from educational (textbook RSA) to more practical (padded RSA) side. David Chaums paper gives a following figure: $r$ - blinding ...
4
votes
2answers
276 views

State of the art RSA key generation

I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis. Beside the key lenght I know there are some weakness in the choice of prime ...
4
votes
4answers
419 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)$?
4
votes
2answers
1k views

Are there any standards of multi-prime RSA key generation?

FIPS 186-3 specifies a method to generate DSA parameters. Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?