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
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 ...
Antonio Sanso's user avatar
3 votes
1 answer
11k views

Cube-Root attack - RSA with low exponent

I have this RSA public key ...
ping0Fdeath's user avatar
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. $$ ...
almodawan's user avatar
  • 151
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 ...
Chirayu Chiripal's user avatar
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 ...
Siyanew's user avatar
  • 121
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 ...
user81147's user avatar
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 ...
user6039980's user avatar
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 ...
user1136342's user avatar
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 ...
Ted's user avatar
  • 201
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 ...
javic's user avatar
  • 293
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 ...
yydl's user avatar
  • 699
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 ...
PlanetUnknown's user avatar
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, ...
kodlu's user avatar
  • 22.4k
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 ...
user avatar
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 ...
adi's user avatar
  • 175
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 ...
Maarten Bodewes's user avatar
  • 92.6k
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 ...
forest's user avatar
  • 15.2k
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 ...
mbigras's user avatar
  • 241
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, ...
Myria's user avatar
  • 2,575
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 ...
wlad's user avatar
  • 1,239
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 ...
Naka Wai's user avatar
  • 163
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 ...
jrgray's user avatar
  • 123
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 \...
chelsea's user avatar
  • 404
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 ...
sukhvir's user avatar
  • 245
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 ...
user1812844's user avatar
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 ...
sg777's user avatar
  • 367
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 ...
SEJPM's user avatar
  • 45.9k
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.
Davis's user avatar
  • 93
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$ (...
AseN's user avatar
  • 193
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 ...
meta_warrior's user avatar
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 ...
satya's user avatar
  • 1,404
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 ...
fgrieu's user avatar
  • 141k
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?
Meltem Coroz's user avatar
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 ...
user2934766's user avatar
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 ...
zywu's user avatar
  • 79
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 ...
Ashwin's user avatar
  • 303
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 ...
EscalatedQuickly's user avatar
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 ...
SEJPM's user avatar
  • 45.9k
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 ...
Karel Bílek's user avatar
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 =...
Idonknow's user avatar
  • 491
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 ...
Idonknow's user avatar
  • 491
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 ...
Boaz Shahar's user avatar
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 ...
hhel uilop's user avatar
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 ...
daniel's user avatar
  • 381
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 ...
joifsi's user avatar
  • 151
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$, ...
Gretty's user avatar
  • 239
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 ...
Glushiator's user avatar
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 ...
Piotr Dobrogost's user avatar
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)$?
Leo Jiang's user avatar
  • 201
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$ ...
user avatar

1 2
3
4 5
11