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.
545
questions
3
votes
1
answer
2k
views
May and Coron's algorithm for factoring knowing RSA private key
According to this and this paper from Alexander May is possible to factor given the knowledge of the RSA private key.
This is possible via Coppersmith and LLL reduction.
Now I am trying to implement ...
3
votes
1
answer
11k
views
Cube-Root attack - RSA with low exponent
I have this RSA public key
...
3
votes
1
answer
18k
views
How do I derive the time complexity of encryption and decryption based on modular arithmetic?
I want to calculate the time complexity of two encryption and decryption algorithms.
The first one (RSA-like) has the encryption
$$ C := M^e \bmod N $$
and decryption
$$ M_P := C^d \bmod N. $$
...
3
votes
3
answers
5k
views
Why RSA uses {d,n} as private key instead of {e,n}?
While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d ...
2
votes
1
answer
704
views
Crack RSA with $e$ and $d$?
Is it possible to decipher a ciphertext, in RSA with small primes (two 128-bit factors) when we only have ciphertext $c$, private exponent $d$ and public exponent $e=65537$ to crack it? I try hard on ...
1
vote
1
answer
3k
views
How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?
Here is some information we got :
We know the value of $n$, with size $1043$.
We know the value of $p$ (size $20$) and $q$ (size $1023$) as the factors.
$e = 65537.$
$\varphi(n)$ = $(q-1)(p-1)$
When I ...
0
votes
1
answer
2k
views
RSA encryption/decryption process is not working correctly
I'm trying to apply the RSA cryptosystem to encrypt a byte M=72, using predefined modulus n, public key exponent ...
25
votes
1
answer
47k
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 ...
20
votes
6
answers
53k
views
How do ciphers change plaintext into numeric digits for computing?
For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$ and for decryption.
If our message is "hello world", then what number do we have to ...
19
votes
5
answers
4k
views
RSA leak bits to factor N
Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q.
Then, you would like to actually let me factor N, except you should tell me as few bits of ...
18
votes
4
answers
12k
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 ...
18
votes
4
answers
23k
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 ...
18
votes
3
answers
5k
views
Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?
There is a claim by Chinese researchers making the rounds (Schneier's blog here) that RSA can be broken by Quantum Computers. The paper is on arXiv.
Wading through the discussion in Schneier's blog, ...
17
votes
4
answers
3k
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 ...
17
votes
3
answers
13k
views
After Google's collision attack, is RSA-SHA1 signature still safe?
Google succeeded to get a collision in SHA-1 last year in an attack called shattered. Does this fact make certificates based RSA-SHA1 Signature risky for creating fraud certificates?
If RSA-SHA1 ...
15
votes
2
answers
3k
views
Given enough RSA signature values, is it possible to determine the public key value?
Given enough RSA signature values, is it possible to determine which public key is required to verify the values?
Could there be enough information to establish which key is required? Is there ...
15
votes
2
answers
2k
views
Why is pqRSA in the NIST PQC submissions?
In the NIST post-quantum cryptography workshop, the round one submissions included pqRSA. If memory serves, this is an implementation of RSA using the product of a very large number of 4096-bit primes ...
13
votes
3
answers
13k
views
Anatomy of an RSA private key
I'm learning about OpenSSL and public key infrastructure and am curious about the structure of an RSA key and how it's related to its corresponding public key.
I can generate a private RSA key with ...
12
votes
2
answers
5k
views
Is it possible to recover an RSA modulus from its signatures?
Let's say that you have some small number of RSA signatures of known data: you know some pairs $(m_k, c_k)$ such that ${c_k}^e \equiv m_k \pmod n$. If you know $e$, because probably it's one of $\{3, ...
12
votes
1
answer
1k
views
If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA?
As far as I know, IND-CPA is used to protect against frequency analysis. But if RSA is only used to encrypt symmetric keys, what's wrong with using only textbook RSA because random keys are very ...
12
votes
2
answers
3k
views
uniqueness of the RSA public modulus
What is the probability that two separate RSA public moduli are the same? For example, consider a 2048-bit modulus. The number seems to be huge, but the choice for prime factors p and q is much more ...
12
votes
3
answers
4k
views
Is RSA padding needed for single recipient, one-time, unique random message?
I want a way to encrypt files using this process: https://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 ...
11
votes
1
answer
1k
views
Collision resistance of hash function built on modular exponentiation
Consider the following hash function family for hashing integers:
$Gen(1^k)$: generate 2 $k$-bit primes p,q. Let $n = pq$. Choose random $y \rightarrow QR_n$ and output $n,y$.
$H_{(n,y)}(x) = y^x \...
11
votes
1
answer
11k
views
Can an RSA private key have several public keys?
Ok, so my cryptography lecturer in University posed this question at the end of the RSA key generation lecture as a brain teaser.
I have been thinking about this and I think I have come up with a way ...
10
votes
1
answer
11k
views
What is a trapdoor permutation?
Can anyone explain to me what a trapdoor one-way permutation is? Is RSA a trapdoor one-way permutation?
Context: I was reading about ring signatures. On page 560, it describes steps to implementing ...
10
votes
2
answers
20k
views
What is the difference between RSASSA-PSS signing and RSA-PSS signing?
I read the RFC 8017 and understood the pkcsv1.5 and pss padding techniques. I understood that in RSASSA-PSS signing scheme the signature will be appended at the end of M.
In some websites I read both ...
10
votes
1
answer
612
views
IND-CPA secure RSA padding with a partial homomorphic property
A while ago, I asked for an IND-CCA1 secure padding for RSA that still allows for the multiplicative homomorphic property of RSA and got no answers (yet).
Now I've seen fgrieu's answer about standard ...
9
votes
2
answers
3k
views
How does PKCS 1.5 solve the insecureness of Textbook RSA?
As we know, Textbook RSA is not enough safe to use because of the following issues;
Guessable plaintext problem
Small $e$ issue
I want to know how PKCS 1.5 solved these problems.
9
votes
1
answer
2k
views
Is it possible to have multiple RSA private keys?
I just did some math:
Pick $p$ and $q$ distinct primes;
Calculate $N=p\cdot q$;
Calculate Euler`s totient => $\phi=(p-1)\cdot(q-1)$;
Pick an $e$ (public key), coprime with $\phi$;
Calculate $d$ (...
9
votes
1
answer
1k
views
Adi Shamir's secret database of all primes
I was going through these presentation slides (PDF) on Crypto 2013.
It summarizes the paper, Factoring RSA keys from certified smart cards: Coppersmith in the wild.
In the last slide, it was ...
9
votes
2
answers
6k
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 ...
9
votes
1
answer
617
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
1
answer
17k
views
How much safer is RSA-OAEP compared to RSA with PKCS#1 v1.5 padding?
Is there a way to calculate how much safer RSA-OAEP is compared to RSA with PKCS#1 v1.5 compliant padding? Or is there a good rule of thumb?
7
votes
2
answers
6k
views
Is RSA key size the size of private key exponent?
I have implemented a key pair generation scheme for RSA algorithm. I have taken the length of private key exponent as RSA key size, but then I've got to know that RSA key size is the size of the ...
7
votes
1
answer
5k
views
Using same modulus for RSA
I know that there exist some attack when using same modulus.
Can two different pairs of RSA key have the same modulus?
RSA cracking: The same message is sent to two different people problem
But ...
6
votes
2
answers
3k
views
Difficulty of breaking RSA for a given key size
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 ...
6
votes
4
answers
12k
views
Is it safer to encrypt twice with RSA?
I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the ...
6
votes
0
answers
348
views
IND-CCA1 RSA padding?
I've found a way to complete a task which I'd solve with passwords or by sending keys over the wire (otherwise) by using RSA's homomorphic property.
I'm restricted to RSA (any padding; for hardware ...
6
votes
1
answer
5k
views
Why do we need in RSA the modulus to be product of 2 primes?
I think I roughly understand how the RSA alorithm is working.
However, I don't understand why we need the $N$, which we use as a modulus, to be $pq$ for some large primes $p, q$.
I vaguely know it ...
6
votes
2
answers
4k
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 =...
6
votes
1
answer
4k
views
File format of an $2048$ bits RSA public key
From here, there are $14$ bytes specifying the file format of the key. I am still quite confused about the format bytes. For example, the following public key
30 82 01 0a 02 82 01 01 00 8e a3 d1 c7 9c ...
5
votes
2
answers
2k
views
Generation of strong primes
It seems that this is pretty difficult to find large (above 1024 bits) strong primes, or at least such primes $p$ where $(p-1)$ has a very large prime factor. Is there any information regarding the ...
5
votes
2
answers
5k
views
Computing p and q from private key
We are given n (public modulus) where n=pq and e (encryption exponent). Then I was able to crack the private key d, using Wieners attack. So now, I have (n,e,d). My question is, is there a way to ...
5
votes
2
answers
11k
views
What will happen if I use RSA encryption for plaintext larger than RSA bit size?
I have often read that using RSA for encrypting bigger size plaintext is not good solution.
What I understand is that using RSA encrytion is best for small plaintext and most effective if it is ...
5
votes
2
answers
960
views
Inclusion and Exclusion proofs in RSA accumulators
I am reading about RSA accumulators from this video and few other sources. I had a confusion whether the complete set is needed to construct a proof of inclusion/exclusion in an RSA accumulator or is ...
5
votes
3
answers
6k
views
Proof for exponentiation in modular arithmetic
If $e$ is a natural number, then this is true:
$$m^e \bmod\ n = (m\bmod\ n)^e\bmod\ n$$
This is often used when encrypting, especially with RSA, since one can avoid directly calculating $m^e$, ...
5
votes
1
answer
4k
views
RSA public key recovery from signatures
Is it possible (how) to recover public (512 bit long) RSA key from multiple signatures having corresponding plain texts. Padding is not randomized.
I need it to verify any future message comming from ...
5
votes
2
answers
530
views
Usability of padding scheme in blinded RSA signature?
In Wikipedia's article on Blind signature, in the section Dangers of blind signing which describes RSA blinding attack one reads the following
This attack works because in this blind signature ...
5
votes
4
answers
608
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
3
answers
1k
views
RSA: Construct private / public key for given cipher and plain text message
let's say we are given a classical RSA encryption scheme, though we would like to "reverse" the task:
Given two messages $c, m$ choose $p, q, e$ such that $p, q$ are prime and $c ^ d \equiv m\pmod N$ ...