# Questions tagged [rsa]

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 with proper paddings.

2,175 questions
Filter by
Sorted by
Tagged with
2k views

### What does “a 15360-bit RSA key is the equivalent to a 256-bit symmetric key” mean?

NIST key management guidelines suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys. If a 15360-bit RSA key is the equivalent to a 256-bit symmetric key, does that mean ...
2k views

### How to better generate large primes: sieving and then random picking or random picking and then checking?

I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q). I know of two methods to achieve this, one based on a prime number ...
440 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 ...
204 views

### Can we break RSA with an optical Fourier Transform?

We all known that RSA can be compromised using quantum Shor's algorithm. The horsepower underlying this algorithm is the Fourier transform. However, we can use alternatives to perform this function, ...
1k 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 ...
4k 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 ...
429 views

### Can RSA be securely used for “blind decryption”?

Assume we have the following setup: A client with trusted storage and computing capabilities (e.g. a smartcard) A server with trusted computing and short-term storage capabilities (e.g. RAM + CPU, ...
322 views

### Bleichenbacher RSA1024 signature forgery, closed-form solution

Hal Finney's writeup (Bleichenbacher's RSA signature forgery based on implementation error) shows a formula for RSA3072. I tried to replicate the attack for RSA1024 and failed, since the first term of ...
3k views

### Why canāt the public key exponent in RSA be negative?

I am looking at why certain public keys in RSA can't be used, such as: 2 and all other even numbers (since $\gcd(\phi,e)$ must equal 1) 1 (since the cipher text would equal the message) 0 (since the ...
5k views

### If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit primes? [duplicate]

"Largest Known Prime Number Discovered; Has 17,425,170 Digits" http://www.sciencedaily.com/releases/2013/02/130213225424.htm If we can find prime numbers larger than 17 milion digits, why can't we ...
1k 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 an RSA or DSA key from it? ...
2k views

### How to efficiently generate a random safe prime of given length?

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 ...
15k views

### Deciphering the RSA encrypted message from three different public keys

I have three different 1024-bit public keys with common exponent $e$ but different moduli. A message $m$ is encrypted (without padding) using the three keys, which results in three different encrypted ...
19k views

### Finding Private key in RSA with public key, cipher text and plain text

Is there a known 'non-brute force' method of determining a private key in an RSA system when all other parameters are know? I found the values of a ciphertext ($C$), its corresponding plaintext ($P$) ...
900 views

### RSA: Letting $p$ and $q$ have different bit-size

I am aware that there are concerns if $p$ and $q$ are close i.e. $\Delta=|p-q|$ can't be too small. But I would like to know if there are any known attacks for cases where $p$ and $q$ take on ...
782 views

### Is unusual (non power-of-two) RSA key size more secure?

On this blog https://blog.josefsson.org/2014/06/23/offline-gnupg-master-key-and-subkeys-on-yubikey-neo-smartcard/ there is a following sentence Generate master key Below I will use a 3744 bit ...
5k views

### ECDH or RSA more secure for symmetric key wrapping?

Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key. In this case, the size of the message is ...
8k views

### Hybrid encryption with RSA and AES versus spliting into multiple RSA messages?

I've done research about this subject, but I can't find the answer I'm looking for. The problem is that the string I want to send doesn't fit into the RSA key that the client have, and during ...
705 views

### Anonymous trust/reputation system

Suppose there are 3 persons, Alice, Bob and Peter. They are identified by their pseudonyms (public RSA keys). Alice has a key Alice, Bob has ...
4k views

### RSA: If n=35, show that e will equal d

Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$ always equals the decryption exponent $d$? What I have so far: $n = 35$ Therefore $p = 5$ and $q = 7$ or vice versa, ...
480 views

### Calculating RSA Public Modulus from Private Exponent and Public Exponent

If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?
1k views

### How does the ROCA attack work?

I have been trying to understand the ROCA attack described here as the "First Attack" and I cannot follow the explaination. I have been trying to generate a 512-bits key and crack it. As far as I can ...
411 views

### RSA exhibits symmetrical properties ā is it possible to form a cryptanalytic attack?

This question is broken into two sections really: Symmetry in RSA I have been analyzing raw RSA and I have noticed some interesting symmetrical properties of the algorithm. Assume that $M$ is a ...
4k views

4k views

### Why not use OAEP for signatures?

There seems to be a distinct lack of implementations of RSA signatures using OAEP to pad the digest. Other than the old, funky, padding schemes, it's PSS all the way. PSS seems to have the whiff of ...
710 views

### Timing attack on RSA as used by CryptoLocker?

So far I have researched timing attacks on RSA, We all know the ransomware named CryptoLocker uses RSA 2048 bit encryption. Now, is it possible to break the encryption using a timing attack. I have ...
3k views

### How do I solve this RSA instance for m?

How we can solve this equation and get the value of M? $$8 = M^{13} \mod 33$$ not a computer program, but a mathematical operation.
18k views

### What is the typical block size in RSA?

If the input text is divided into a fixed block size for encryption and decryption, what could be the typical block size for RSA algorithm for different size of input like 8 MB, 16 MB, 126 MB and 256 ...
3k views

I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm. I think that firstly, Monty would be slightly faster than DoubleAndAdd. ...
804 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, ...
908 views

### RSA Timing Attack on “Extra” Montgomery Reduction

In "A practical implementation of the timing attack", the authors take advantage of a timing difference that stems from "extra reductions" that occur when multiplying numbers in the Montgomery form. ...
861 views

### RSA reconstructing private key knowing MSBs

PREMISE: This question is purely theoretical because usually an attacker will not know private exponent d and can't compare it with obtained MSB bytes. Suppose an RSA 1024 bit signature. An attacker ...
5k views

### CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11

What is the exact difference between the CKM_RSA_PKCS and CKM_RSA_X_509 mechanisms in the PKCS#11 v2.20 specification (Please ...
4k views

### Help Finding D from Dq and Dp

Let $$d_p = d~\mathrm{mod}~(pā1)$$ and $$d_q = d~\mathrm{mod}~(qā1).$$ Given $d_p$, $d_q$, $p$ and $q$, how can I reconstruct $d$?