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.

Filter by
Sorted by
Tagged with
8
votes
1answer
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 ...
8
votes
2answers
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 ...
8
votes
1answer
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 ...
8
votes
1answer
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, ...
8
votes
1answer
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 ...
8
votes
1answer
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 ...
8
votes
1answer
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, ...
8
votes
0answers
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 ...
7
votes
4answers
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 ...
7
votes
2answers
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 ...
7
votes
3answers
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? ...
7
votes
2answers
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 ...
7
votes
3answers
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 ...
7
votes
2answers
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$) ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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, ...
7
votes
2answers
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$?
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
1answer
4k 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 ($\left[...
7
votes
2answers
7k views

Homomorphic cryptosystems in RSA

Hopefully, Crypto can help me understand homomorphic cryptosystems. I'm designing a high score server for a game I made, and because of facets in the language I'm using, the player would be able to ...
7
votes
1answer
976 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) ...
7
votes
1answer
221 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 "...
7
votes
1answer
2k views

Algorithm to factorize $N$ given $N$, $e$, $d$

I have an RSA public key (public modulus $N$ and public exponent $e$), and the private exponent $d$ of matching private key. How can I compute $p$ and $q$, the primes factor of $N$ ?
7
votes
1answer
651 views

Does blinding work against side channel on RSA?

In the so called "blinding" technique for RSA, prior to decryption, the ciphertext is multiplied by random $r$ raised to the power of $e$; e.g., $C$ is replaced with $C\cdot r^e$; and then after ...
7
votes
2answers
898 views

Given enough RSA ciphertext, is it possible to determine which key was used?

Given enough RSA ciphertext, is it possible to determine which public key was used to generate the ciphertext? Presume an unknown public key that was used to generate RSA ciphertext, and we have ...
7
votes
3answers
2k views

What are some good references for the implementation weaknesses in RSA

I'm pretty sure I understand textbook RSA. Choose p and q, large primes, and compute n=pq. Choose e such that $gcd(\phi(n),e)=1.$ Publish n and e. Compute d such that $de=1$ (mod $\phi(n)$). To ...
7
votes
1answer
3k views

What happens if an RSA key pair has identical public and private exponents?

Rather, is it possible for big prime numbers? Classroom examples usually involve smaller primes, so for example if you are given a prime number pair $p = 3$, $q = 13$ you would get $n = 39$ and $e = ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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.
7
votes
4answers
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 ...
7
votes
1answer
3k views

Montgomery Ladder vs Double-and-Add

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. ...
7
votes
3answers
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, ...
7
votes
2answers
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. ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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$?
7
votes
1answer
411 views

Blinding twice in RSA

I understand that if you have a message $m$, you can blind it by selecting a random $r$ and then multiplying $r^e\times m \pmod{n}$ Someone else then signs it with $d$, raising to the power of $d$: $(...
7
votes
2answers
4k 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?
7
votes
2answers
995 views

RSA: revealing the modulus factorization by choosing a bad message

I started reading the book Cryptanalysis of RSA and its variants by M. Jason Hinek and I stumbled upon a phrase that intrigued me: plaintext messages that are relatively prime to the modulus (i.e....
7
votes
1answer
3k views

Is a private RSA key vulnerable to a chosen plaintext encrypted with that private key?

I grasp that having known plaintext encrypted with the public key doesn't provide a means of discovering the private key (that being the whole point...). But if one were in a situation where they ...
7
votes
1answer
717 views

In PKCS#1 V2.2, should MGF be based on the same hash function that RSA-OAEP-ENCRYPT uses?

In Section 7.1.1 of PKCS#1 v2.2 there are two options for RSAES-OAEP-Encrypt given: Hash MGF Appendix B.2.1 of the same document states that MGF1 is based on a hash function. Is MGF1 based on the ...
7
votes
1answer
1k views

Deletion in RSA Accumulator

I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the ...
7
votes
1answer
132 views

Can I switch out a private RSA Key, so that when decrypting a message, it is decrypted to a different message?

Here's a task I've been struggling with: Say I have an encrypted message $c$, and a desired plaintext $m$. How can I define a valid private RSA Key $(d,N)$, so that $c^d \bmod N = m$ Note that the ...
7
votes
2answers
2k views

How to forge a textbook RSA signature?

Let $pk=(N,e)$ (resp. $sk=(N,d)$) denote the public (resp. private) key in a plain RSA signature scheme. Define the function $\textbf{Int}: \{0,1\}^* \to \mathbb{Z}_N^*$ as follows: on input string $x=...

1
3 4
5
6 7
44