# Tagged Questions

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.

21k 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 ...
24k 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 ...
2k 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). ...
11k 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?
2k 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 ...
4k 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 ...
16k 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 (encrypted) message. How can I do this?
7k 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: ...
9k views

### Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

I've studied that the Bleichenbacher's CCA attack on PKCS#1 v1.5. is a base to many versions of attacks in the area. I'm trying to understand that attack, but every explanation I saw starts with the ...
8k 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 ...
10k 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 ...
2k 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 ...
41k 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?
13k 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 ...
3k 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 ...
1k 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 ...
9k 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. ...
3k views

### Using the same RSA keypair to sign and encrypt

The RSA signature operation is basically the same as encrypting with the private key. In particular, both operations use the same kind of keys. Is it safe to use the same RSA keypair both for ...
2k views

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 \... 2answers 828 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 ... 2answers 288 views ### Factors of RSA modulus In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any ... 3answers 7k 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 ... 3answers 3k views ### Is sharing the modulus for multiple RSA key pairs secure? In the public-key system RSA scheme, each user holds beyond a public modulus$m$a public exponent,$e$, and a private exponent,$d$. Suppose that Bob's private exponent is learned by other users. ... 0answers 697 views ### Who first published the interest of more than two prime factors in RSA? Multi-prime RSA is now a well known technique (described here): 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 ... 0answers 471 views ### Security of RSA for paranoids with padding? RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ... 4answers 4k 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 ... 4answers 17k 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 ... 1answer 1k 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 ... 2answers 380 views ### Small Prime Difference in RSA In RSA, the$p$and$q$should be randomly generated, and they are the same size. The difference between$p$and$q$should not be small. Suppose that$u=|p-q|<20$and$p \times q =...
Is it true that breaking a 1024-bit RSA key is as difficult as breaking a 128 bit symmetric key (e.g. AES)? I know that breaking a RSA key is equivalent to factoring the modulus $N$. To factor it, you ...