Talk:RSA (cryptosystem)

What does this mean ?

I think more information is needed about $\phi (n)=(p-1)(q-1)$. What does this mean ? Take the 2 primes, decrease them by 1,multiply them with each other, but then ? Save the result in empty set number 'n' ? How can a empty set contain something ? --Garo 21:52, 17 August 2005 (UTC)

That's a phi, not an empty set. In this case, it is simply a new function which we have defined over the domain of all integers n which are the product of two large primes. It is, in effect, a convenient notation for (p-1)(q-1). Aerion//talk 23:20, 17 August 2005 (UTC)

Small correction: phi(n) is the Euler totient function and it is defined over all integers. It is the number of integers less than n which are coprime to n. Should I mention this in the article where phi(n) first appears? Birge 06:26, 18 August 2005 (UTC)

This is totally confusing.

Why does λ(n) = (p − 1) * (q − 1) not work? The article says it has to be lcm. Is that true?

And why introduce these obscure totient and lambda functions. They do nothing to clarify the article.

The purpose of maths articles seems to be to show the cleverness of mathematicians. And to be impenetrable to anyone else.

This article should be intelligible to anyone with advanced high school maths. Modulo arithmetic, calculus, but not totients!

Tuntable (talk) 00:46, 8 January 2024 (UTC)

I'm not sure I understand what you're asking. The article does not say that (p-1)*(q-1) "does not work". It says just the opposite: In the original RSA paper, the Euler totient function φ(n) = (p − 1)(q − 1) is used instead of λ(n) for calculating the private exponent d. Since φ(n) is always divisible by λ(n), the algorithm works as well. The totient functions are hard to avoid when explaining the algorithm, and I think the explanation would be harder to follow if we tried to do so, but you are of course welcome to propose wording that you think would be clearer. CodeTalker (talk) 02:40, 8 January 2024 (UTC)

Supplementary condition: $e^{2}\neq 1{\text{ mod }}\phi (n)$

Hello,

I was reading this article on the RSA algorithm and something seemed to be a problem to me in the key generation. Indeed, what happens if we chose

• $e\wedge \phi (n)=1$
• $e<\phi (n)$
• but $e^{2}=1{\text{ mod }}\phi (n)?$

(The conditions "$e\wedge \phi (n)=1$ and $e<\phi (n)$" are the only two conditions cited in the article.) Well then $d=e$ is always a valid private key.

Indeed, we are searching for a

• $d\wedge \phi (n)=1$
• $ed=1{\text{ mod }}\phi (n)$

So if $e^{2}=1{\text{ mod }}\phi (n)$, then $d=e$ works! So when a public key is known, if the test $e^{2}=1{\text{ mod }}\phi (n)$ is true, the message can be deciphered.

I believe this a well known fact since an easy example is given by the public key $(e,n)=(3,15)$ (and $e=3$ is always recommended to avoid). Indeed chose

• $p=3,q=5$
• $n=15$
• $\phi (n)=(3-1)(5-1)=8$
• $e=3$ so $e=3{\text{ mod }}8$
• yet $e^{2}=9=1{\text{ mod }}8$

So (3,15) is not a valid public key, yet it satisfies the conditions stated in the Wikipedia article.

So what are the correct conditions ? First, we need to ask that

• $e\wedge \phi (n)=1$
• $e<\phi (n)$
• but also $e^{2}\neq 1{\text{ mod }}\phi (n)$

However, we see that if $e=\phi (n)-1$, then

• $e=-1{\text{ mod }}\phi (n)$
• so $e^{2}=1{\text{ mod }}\phi (n)$

So, even the condition

• $e<\phi (n)$

is not very well stated because it may include $e=\phi (n)-1$ which is forbidden by $e^{2}\neq 1{\text{ mod }}\phi (n)$.

Therefore, I would propose the following conditions :

• $e\wedge \phi (n)=1$
• $e<\phi (n)-1$
• $e^{2}\neq 1{\text{ mod }}\phi (n).$

Does it make sense?

Clement justin (talk) 12:45, 24 June 2016 (UTC)

This restriction is usually enabled without being specified, due to NIST requiring that 'e' not be larger than 2^256, and the totient is generally not that small except for poorly chosen primes. Since the totient is not provided with the public key, a way for you to verify that my 'e' does not violate these conditions is to encrypt a message twice then check whether the double-encryption returns to the original value. Which you can check by altering the page's example to use e=781 or e=779 or e=1+780*anything. In both cases, e and d (each mod lambda) are identical, and double-encryption results in the original message.

Note that, when OpenSSL currently checks an RSA certificate, they have 2 kinds of restrictions for the maximum 'e' depending on the bit length, and they do not check if e2 mod totient = 1. If the bit length of 'n' is 3072 or shorter, it just verifies that 'e' is less than 'n', and for longer 'n' it restricts 'e' to be no longer than 2^64. So indeed OpenSSL does not currently detect, especially in 2048-bit or 3072-bit keys, whether 'e' is any of the many values which would meet your conditions. Silversplash (talk) 20:18, 25 January 2023 (UTC)

Totient or LCM !?

Currently the article reads "...calculate the totient lambda(n) = lcm((p-1, q-1)". But this is not the totient, the totient is (p-1)(q-1) which is at least twice lambda (because both p-1, q-1 are even). According to earlier comments it seems that earlier the page said "compute the totient phi (or lambda?) = (p-1)(q-1)". Now it's not obvious that the two choices will yield the same result (not even clear what result means... maybe: modular inverse?). Do they? If so, that's worth a remark, to the least. If not, what should be used? — MFH:Talk 21:16, 22 May 2018 (UTC)

Why isn't the Euler's totient in the article

I have seen numerous high profile websites and books using the Euler's totient but it is not used on Wikipedia. I was building an RSA code on your program only to realise there is a faster and more efficient way of coding it only that it wasn't include on the article. A subtle mention would at least be appreciated. Cyclone26 (talk) 23:06, 9 April 2019 (UTC)

Euler's totient is discussed in Key generation, including noting why Carmichael's totient is used in that section instead. I doubt using Euler's totient is more efficient. If we assume that Hamming weight of d is the deciding efficiency factor for private key operations, and that its Hamming weight is mostly decided by its length, then Carmichael's is more efficient: the small price you pay during key generation vastly pays off during all subsequent private key operations. I'm just not really sure that my assumptions are valid. By the way, I'm also assuming you're not using the Chinese Remainder Theorem for private key operations, as discussed in the section. Digital Brains (talk) 10:14, 10 April 2019 (UTC)

Okay, actually, if you're worried about efficiency and are thus using the Chinese Remainder Theorem anyway, it's possible you might just as well use Euler since the CRT will take care of reducing it further. That does assume you have control over both the generation code and the private key operation code; if your key might also be used by different private key operation code, it could still be worthwhile to reduce the length of d for those implementations (by using Carmichael's rather than Euler's). Digital Brains (talk) 10:19, 10 April 2019 (UTC)

Safe Primes, in RSA Key Generation

I did put the anchor for this note, here: http://en.wiki.x.io/wiki/RSA_(cryptosystem)#CryptoStrengthOfPQ

and here (old reverted edit cache): http://en.wiki.x.io/w/index.php?title=RSA_(cryptosystem)&diff=983454044&oldid=983447902#CryptoStrengthOfPQ

But my edit was been reverted: http://en.wiki.x.io/w/index.php?title=RSA_(cryptosystem)&oldid=983456104

I did discribed all, then put anchor, and add that link on Safe-Primes-definion page: http://en.wiki.x.io/w/index.php?title=Safe_and_Sophie_Germain_primes&diff=983441331&oldid=983436407

The main thing, described there - exclude the common factors (common difisors) for the numbers (p-1) and (q-1), and leave only 2 as common factor of this,

to prevent an easy factorization of (n-1), and make this so hard.

When p and q is a safe prime numbers, then p' = (p-1)/2, q' = (p-1)/2, where p' and q' - primes too, moreover this is a some Sofi-Germain prime numbers.

So, because of this, the numbers (p-1) and (q-1) - have only one common divisor (number 2).

Because each of this number can be factorized only as (p-1) = 2*p'; (p-1) = 2*q',

and only 2 is a common factor (result of factorization, difisor), while p' and q' is a different prime numbers, and this is not a common divisors.

Yes, this p' and q' is Sofi-Germain primes, but this is not used in key generation,

and used the safe primes - p, and q, and this is a Safe prime numbers, not Sofi-Germain primes.

I did discribed this all there, and I do not know what need to add more,

to explain the resolution of that problem, with common-divisors of (p-1), and (q-1),

problem, which was been described in previous version.

But, look at this:

p, q - primes;

n = p*q;

phi(n) = (p-1)*(q-1);

λ(n) = lcm((p−1),(q−1)); where λ is Carmichael's totient function.

The lcm may be calculated through the Euclidean algorithm, since lcm(a,b) = |ab|/gcd(a,b), gcd - greatest common divisor.

λ(n) = |((p-1)*(q-1))|/gcd((p-1),(q-1)) = |phi(n)| / gcd((p-1),(q-1)) = phi(n)/gcd((p-1),(q-1)), because phi(n) - positive Natural Number;

Now, lets define some: g = gcd((p-1),(q-1));

λ(n) = phi(n)/g

g*λ(n) = phi(n);

g = phi(n)/λ(n);

Each x, which is co-prime with n = p*q, is divisor for ( (n-1) = (p*q-1) = ( (p−1)*(q−1) + (p−1)+(q−1) ) ), for (p-1), for (q-1), and for a λ(n).

So, to calculate d, can be used formula ( d*e === 1 ( mod λ(n) ) ), instead of ( d' * e === 1 ( mod phi(n) ) ).

Since g = phi(n)/λ(n), ( d*e === 1 ( mod phi(n) ) ) -> ( d*e === 1 ( mod λ(n) ) ) too, so d = d' mod λ(n), and (d !== d' mod phi(n));

After this all, we can see, that (d, d'+1*λ(n), d'+2*λ(n), ..., d'+(g-1)*λ(n)) - this is privkeys, cryptoequivalently, with privkey d.

This means, g = gcd((p-1),(q-1)) is a number of cryptoequivalently privkeys,

and when this number is growing, this is decreasing crypto-strength of RSA-system.

The best case, when g = gcd((p-1),(q-1)) = 2, and in this case, p = 2*p'+1, q = 2*q'+1, where, gcd(p',q')=1,

and where p' and q' – primes (Sophie-Germen primes), and where p и q - Safe primes, because of this, by definition.

In this case, (p-1) and (q-1), have only one common factor (common divisor) = 2.

Discuss.

I have moved this thread to its right place, namely the bottom of the page.

It is not the role of Wikipedia editors to decide whether what you wrote is correct or not. But it is our role to verify whether your assertions are supported by reliable sources. For this purpose, you have to provide such reliable sources. This has not been done. On the contrary, the reference 20 of Safe and Sophie Germain primes asserts that, with the modern factorization algorithms, choosing safe primes does not increase the security. So, there is no need to insist on the choice of the primes more than that is already in the article. D.Lazard (talk) 14:01, 14 October 2020 (UTC)

I don't know what "reliable sources" you want, for the obvious things. Perhaps this old book will "convince" you:

https://studfile.net/preview/5367570/page:7/

Paragraph 8.4, keywords: "Очевидно, в наилучшем возможном случае..." - there is Safe Primes.

After this, was been described the usage of strong-primes, and algorithm to generate this - Gordon's Algorithm too.

213.231.62.76 (talk) 02:36, 15 October 2020 (UTC)

The reference describes choosing 'p' by requiring a large factor for each of the 3 related numbers (p-1) and (p+1) and for (p-1)/2. The FIPS method for choosing RSA primes has been updated to recommend a method which achieves the first 2 of 3 qualities, though not the 3rd.

Your link says "In general, p and q should not differ from typical representatives of random prime numbers", but by allowing only safe primes as the p q primes, that would significantly slow down key generation, and thins the pool of primes that could be chosen. Also, this means that p and q are no longer 'typical'. Among large primes, the remainder from p-mod-12 can be any of the 4 alternatives 1 5 7 11, but safe primes can only have remainder 11, so this requirement would discard 3/4th of all primes. By having this same requirement for both p and q, instead of n-mod-144 being any of 10 possible results, it would now have only result=121.

As an idea for how much the safe prime requirement would slow down key generation, take as an example the RSA-4096 search for a 2048-bit 'p'. Among b-bit numbers, the density of primes trends toward 1 per (b * log(2)), or 1 per 1420 numbers at 2048 bits. But the density of Sophie Germain primes among b-1 bit numbers would be approximately 1 per ((b-1) * log(2))^2 / (twin prime constant), or 1 per 1.52 million numbers, which is around 1070 times more rare. Each time the 'Gordon method' reaches a candidate that's prime, there would be a tiny chance that (p-1)/2 is also prime, and the Gordon method isn't a shortcut for that. Silversplash (talk) 00:08, 13 April 2023 (UTC)

edit: should have said (2*twin prime constant) Silversplash (talk) 17:32, 13 April 2023 (UTC)

Bellcore vs CRT

I know the article does not intend to be a definitive list of all attacks. But since the article mentions the CRT shortcut for signing/decryption, and has a whole section of attacks against unpadded RSA messages, there should probably be a mention of the Bellcore attack, where someone gets you to sign the same message twice, where one of them is a valid signature but the other is defective due to an error in 1 of the CRT exponentiations, it allows someone to discover 1 of the prime factors, which completely solves 2-prime RSA. The defense is to perform the public-key operation using 'e' against the signature to ensure that the result matches the original message being signed. Deterministic padding is just as vulnerable as no padding, but methods like OAEP should prevent the same 'message' input being seen twice. Silversplash (talk) 06:56, 26 January 2023 (UTC)

Multi-Prime RSA

Perhaps there can be a section for RSA using more than 2 primes, as it can be hard to find info about it.

While the most common usage of RSA has the modulus 'n' being the product of 2 primes, it is possible for it to work as 'multi-prime RSA' where 'n' is the product of 3 or more primes.

Current factoring algorithms depend on the size of 'n', but if the prime factors are large enough, they aren't able to detect whether a 4096-bit 'n' is the product of 2 2048-bit primes or is the product of 4 1024-bit primes. To limit how small the primes can be, OpenSSL limits the number of primes based on the size of 'n', with a default maximum of 5 primes.

Daniel J Bernstein describes an extreme post-quantum variant of multi-prime RSA in https://cr.yp.to/papers/pqrsa-20170419.pdf where 'n' is the product of an enormous number of 4096-bit primes, but decryption/signing is accelerated using CRT calculation.

The advantage of multi-prime RSA is that it has faster speed without reducing the bit length of 'n'. Because when there are 'k' equal-length primes, there are 'k' exponentiations of numbers whose size is bits(n)/k. So the CRT calculation of signatures using an 8192-bit 'n' can be done faster with CRT if there are 4 2048-bit primes, than CRT when there are 2 4096-bit primes.

The math for RSA which does not use the CRT shortcut is the same, except that the calculations for 'phi' and 'lambda' involve multiplying more than two 'prime less 1' numbers together, and with more than 2 primes it's no longer true that the LCM is always the product of primes divided by the GCD. Also, it's no longer possible to ensure that 'n' has the correct bit length by forcing the top 2 bits of all primes to be 1-bits. Care must be taken to avoid the LCM being significantly smaller than 'n', due to large factors shared between only 2 of the 3-or-4 'prime less 1's', and not reflected in the combined GCD.

For multi-prime RSA, the CRT performed by OpenSSL involves creating an additional d(Prime) and Inverse-of-prime for each of the primes above the total of 2. Modifying the article's 2-prime example to use the pre-calculated OpenSSL variables is as follows.

1. Choose distinct primes p=61 q=53 r=59 s=83 (same p and q, extra r and s)
2. Compute 'n' = product of all primes, n = 61 x 53 x 59 x 83 = 15832001
3. totient(n) = lcm(60,52,58,82) = 927420
4. e = 17, and is validated as co-prime to totient, due to gcd(17,927420) = 1
5. d = inverse of 17 mod 927420 = 436433, as 436433 * 17 mod 927420 = 1
6. public key is e=17 and n=15832001, and encryption is c(m) = m^e mod n = m^17 mod 15832001
7. If the plaintext is smaller than p*q, then the CRT variables for the 3rd and 4th prime have no effect, so this example changes from m=65 to m=12345678.
8. The encryption is c=12345678^17 mod 15832001 = ciphertext c=8765942
9. The shortcut CRT variables are pre-calculated:
d_p = d mod p-1 = 436433 mod 60 = 53 (same as in 2-prime example because p is same)
d_q = d mod q-1 = 436433 mod 52 = 49 (same as in 2-prime example because q is same)
d_r = d mod r-1 = 436433 mod 58 = 41
d_s = d mod s-1 = 436433 mod 82 = 29
10. While the inverse for 'q' is the same as in the 2-prime calculation, the pre-calculated inverses for the primes beyond the 2nd prime are calculated differently, where the value is instead the inverse of the product of the previous primes, mod 'that prime':
qInv = 1/q mod p = 53 ^-1 mod 61 = 38 (same as in 2-prime example)
rInv = 1/(p*q) mod r = (61*53) ^-1 mod 59 = 54
sInv = 1/(p*q*r) mod s = (61*53*59)^-1 mod 83 = 32
11. The partial messages here are labeled using the prime letter(s) instead of numbered as m1 and m2, but otherwise the 1st step is an identical method to the entire calculation when there are 2 primes:

m_p = c ^ d_p mod p = 8765942^53 mod 61 = 10
m_q = c ^ d_q mod q = 8765942^49 mod 53 = 17
m_r = c ^ d_r mod r = 8765942^41 mod 59 = 46
m_s = c ^ d_s mod s = 8765942^29 mod 83 = 9

h_q = (qInv * (m_p - m_q)) mod p = (38 * (10-17)) mod 61 = 39
m_pq = (m_q + h_q * q) = 17 + 39 * 53 = 2084 (same variables as used in 2-prime)

12. For the remaining steps, the calculations for the K'th prime are h_K = Kinv * (m_K - m_(pq...K-1) ) mod Kth Prime, and m_(pq...K) is m_K + h_K * product_primes_previous_to_K
13. Next step extends the step 11 2-prime calculation to use the CRT variables for the 3rd prime:
h_r = (rInv * (m_r - m_pq)) mod r = (54 * (46-2084)) mod 59 = 42
m_pqr = (m_pq + h_r * p*q) = (2084 + 42 * 61*53) = 137870
14. Next step extends the step#13 calculation to use the CRT variables for the 4th prime:
h_s = (sInv * (m_s - m_pqr)) mod s = (32 * (9-137870)) mod 83 = 64
m_pqrs = (m_pqr + h_s * p*q*r) = (137870 + 64 * 61*53*59) = 12345678
Silversplash (talk) 06:57, 26 January 2023 (UTC)

"...similar in magnitude, but differ in length."

RSA (cryptosystem)#Key generation What does this mean exactly?

Could this possibly be made clearer? InverseCosine (talk) 20:57, 27 March 2023 (UTC)

Good catch. I have decrypted it. D.Lazard (talk) 08:37, 28 March 2023 (UTC)

@D.Lazard Thanks! This seems like a more understandable rendering now. InverseCosine (talk) 09:09, 28 March 2023 (UTC)

RSA(cryptosystem)

Hi over there, thank you for this excellent contribution, I read it in all language I do understand, German, Spanish, French, all these version are amongst them and in respect to your super contribution different, the contributions in the other languages are matematically erroneous, what a shame, the basics for this algoritm developed Leonhard Euler in round about 1880 in German, but the worst pages about RSA Lobito060454 (talk) 12:11, 4 April 2023 (UTC)

Can you say what mathematical bugs you found? 62.202.182.94 (talk) 13:38, 3 August 2023 (UTC)

proof numeric

https://www.researchgate.net/publication/374155658_High_temperature_QC_breaking_RSA-2048 2601:205:8081:BC40:4071:2248:4EE5:1D8 (talk) 23:30, 4 August 2024 (UTC)