This is the talk page for discussing improvements to the RSA (cryptosystem) article. This is not a forum for general discussion of the article's subject. 
Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL 
Archives: 1Autoarchiving period: 365 days 
This level5 vital article is rated Cclass on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:  

Todo list for RSA (cryptosystem):

This page has archives. Sections older than 365 days may be automatically archived by Lowercase sigmabot III when more than 10 sections are present. 
I think more information is needed about . 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)
Tuntable (talk) 00:46, 8 January 2024 (UTC)
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)
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
(The conditions " and " are the only two conditions cited in the article.) Well then is always a valid private key.
Indeed, we are searching for a
So if , then works! So when a public key is known, if the test is true, the message can be deciphered.
I believe this a well known fact since an easy example is given by the public key (and is always recommended to avoid). Indeed chose
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
However, we see that if , then
So, even the condition
is not very well stated because it may include which is forbidden by .
Therefore, I would propose the following conditions :
Does it make sense?
Clement justin (talk) 12:45, 24 June 2016 (UTC)
Currently the article reads "...calculate the totient lambda(n) = lcm((p1, q1)". But this is not the totient, the totient is (p1)(q1) which is at least twice lambda (because both p1, q1 are even). According to earlier comments it seems that earlier the page said "compute the totient phi (or lambda?) = (p1)(q1)". 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)
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)
I did put the anchor for this note, here: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#CryptoStrengthOfPQ
and here (old reverted edit cache): https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&diff=983454044&oldid=983447902#CryptoStrengthOfPQ
But my edit was been reverted: https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=983456104
I did discribed all, then put anchor, and add that link on SafePrimesdefinion page: https://en.wikipedia.org/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 (p1) and (q1), and leave only 2 as common factor of this,
to prevent an easy factorization of (n1), and make this so hard.
When p and q is a safe prime numbers, then p' = (p1)/2, q' = (p1)/2, where p' and q'  primes too, moreover this is a some SofiGermain prime numbers.
So, because of this, the numbers (p1) and (q1)  have only one common divisor (number 2).
Because each of this number can be factorized only as (p1) = 2*p'; (p1) = 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 SofiGermain 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 SofiGermain 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 commondivisors of (p1), and (q1),
problem, which was been described in previous version.
But, look at this:
p, q  primes;
n = p*q;
phi(n) = (p1)*(q1);
λ(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) = ((p1)*(q1))/gcd((p1),(q1)) = phi(n) / gcd((p1),(q1)) = phi(n)/gcd((p1),(q1)), because phi(n)  positive Natural Number;
Now, lets define some: g = gcd((p1),(q1));
λ(n) = phi(n)/g
g*λ(n) = phi(n);
g = phi(n)/λ(n);
Each x, which is coprime with n = p*q, is divisor for ( (n1) = (p*q1) = ( (p−1)*(q−1) + (p−1)+(q−1) ) ), for (p1), for (q1), 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'+(g1)*λ(n))  this is privkeys, cryptoequivalently, with privkey d.
This means, g = gcd((p1),(q1)) is a number of cryptoequivalently privkeys,
and when this number is growing, this is decreasing cryptostrength of RSAsystem.
The best case, when g = gcd((p1),(q1)) = 2, and in this case, p = 2*p'+1, q = 2*q'+1, where, gcd(p',q')=1,
and where p' and q' – primes (SophieGermen primes), and where p и q  Safe primes, because of this, by definition.
In this case, (p1) and (q1), have only one common factor (common divisor) = 2.
Discuss.
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 strongprimes, and algorithm to generate this  Gordon's Algorithm too.
213.231.62.76 (talk) 02:36, 15 October 2020 (UTC)
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 2prime RSA. The defense is to perform the publickey 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)
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 'multiprime 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 4096bit 'n' is the product of 2 2048bit primes or is the product of 4 1024bit 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 postquantum variant of multiprime RSA in https://cr.yp.to/papers/pqrsa20170419.pdf where 'n' is the product of an enormous number of 4096bit primes, but decryption/signing is accelerated using CRT calculation.
The advantage of multiprime RSA is that it has faster speed without reducing the bit length of 'n'. Because when there are 'k' equallength primes, there are 'k' exponentiations of numbers whose size is bits(n)/k. So the CRT calculation of signatures using an 8192bit 'n' can be done faster with CRT if there are 4 2048bit primes, than CRT when there are 2 4096bit 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 1bits. Care must be taken to avoid the LCM being significantly smaller than 'n', due to large factors shared between only 2 of the 3or4 'prime less 1's', and not reflected in the combined GCD.
For multiprime RSA, the CRT performed by OpenSSL involves creating an additional d(Prime) and Inverseofprime for each of the primes above the total of 2. Modifying the article's 2prime example to use the precalculated 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 coprime 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 precalculated:
d_p = d mod p1 = 436433 mod 60 = 53 (same as in 2prime example because p is same)
d_q = d mod q1 = 436433 mod 52 = 49 (same as in 2prime example because q is same)
d_r = d mod r1 = 436433 mod 58 = 41
d_s = d mod s1 = 436433 mod 82 = 29
10. While the inverse for 'q' is the same as in the 2prime calculation, the precalculated 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 2prime 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 * (1017)) mod 61 = 39
m_pq = (m_q + h_q * q) = 17 + 39 * 53 = 2084 (same variables as used in 2prime)
12. For the remaining steps, the calculations for the K'th prime are h_K = Kinv * (m_K  m_(pq...K1) ) mod Kth Prime, and m_(pq...K) is m_K + h_K * product_primes_previous_to_K
13. Next step extends the step 11 2prime calculation to use the CRT variables for the 3rd prime:
h_r = (rInv * (m_r  m_pq)) mod r = (54 * (462084)) 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 * (9137870)) 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)
RSA (cryptosystem)#Key generation What does this mean exactly?
Could this possibly be made clearer? InverseCosine (talk) 20:57, 27 March 2023 (UTC)
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)
https://www.researchgate.net/publication/374155658_High_temperature_QC_breaking_RSA2048 2601:205:8081:BC40:4071:2248:4EE5:1D8 (talk) 23:30, 4 August 2024 (UTC)