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 |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||||||||
|
|
no archives yet ( create) |
![]() | This article links to one or more target anchors that no longer exist.
Please help fix the broken anchors. You can remove this template after fixing the problems. |
Reporting errors |
Is is the same as greatest common divisor? gcd(n,m)? — Preceding unsigned comment added by 156.17.236.67 ( talk) 14:07, 6 January 2012 (UTC)
Equations involving mod operations seem to be written in the wrong order. On this account I was not able to understand the simple operation even though it should have been easy. The first example is as follows:
d*e = 1 mod( phi )
Surely you mean:
d*e mod( phi ) = 1
Don't you? Or am I missing something?
1 mod( anything ) = 1 doesn't it?
Well, that is an unfortunate convention. I am glad that you explained that. To clarify, I guess that you are saying that: (II) x=y mod(a) is the same thing as: (I) x%a = y%a ... if I may steal that modulus symbol from C. But in your notation, how do you write (II) y = x%a , where y is the unknown???? What I mean is that in equation (I), if x = 8 and a = 5, then y has to be a member of {3,8,13,18,.........}. But in equation (II), there is only one solution for y, 3. right?
If all you care about is finding out if two numbers are at the same point in a cycle given that a cycle has a certain length, that makes sense, you are qualifying in which way they are equivalent.
But there is no way of asking, using that notation, what is the most basic way to represent that point in that cycle of that given length. Or is there?
This doesn't have much to do with the subject of this page. But Lunkwill seems to know a little about this. So I just thought I would ask.
Response from Anonomous -> Keep in mind that the reasoning behind the convention is that you are doing arithmetic in a finite field, i.e. you only have a subset of the integer numbers to work with (a FINITE field of integer numbers) designated as Z sub N (where N is the number of integer elements, ex. Z sub 7 is Z sub inf. mod 7 thus => [0,6] inclusive). Therefore, anytime any particular operation is done, if the resultant number is "outside" the field, it is mod'ed down to get back into the field (this is rather a harsh explanation, but is an easy way to see it at first). So for instance, saying x [is congruent to] y (mod a) can be directly viewed as x = y + k * a for some value of k (y is a multiple of k * a which equals x). Keep in mind that a congruence and an equality are two different things. For ex, say that you have something silly like 11 [is congruent to] 1 (mod 10), this makes sense since 11 = 1 + [1] * 10, 11 is outside of the finite field of Z sub 10. The calculator notation is in fact mod(11, 10) (for TI-89) or 11 % 10 (for C/C++/Java/etc.), but that is just by notation of an operator (from a comp. sci. point of view), not modular arithmetic (from a mathematical point of view). Keep in mind that the reason for doing modulus in the first place, again, is for staying inside of the field. A really good example of this is modular exponentiation, where we have, say, some number a raised to some ridiculously large power b (which RSA does with its e and d components) but while doing it mod some normal value of n (ex. say something rhetorically stupid as 2^1234567890 (mod 3)). Would you really compute this by doing a^b and then mod'ing by n? No, you would overflow 64-bit integers within a few iterations of pow(). All you need to do is take it one step at a time maintaining the field (in fact if you do it the intelligent way you can do it in O(log n) if you use successive squaring). So, I think what you're missing is, why is the notation not like one would do it on a calculator? Because, simply, having a (mod n) at the far right hand side (and only once) isn't an operation per-sey, it is literally meaning working with integers of a finite field, which is a convenient way to work with moduluar arithmetic, (mod n). Hope this helps.
the question is answered, but I'll add that confusion seems to come from computer types who see mod(phi) as an operator changing the value of 1, but you'd be closer to the truth if you see it as an operator changing the meaning of the '=' —Preceding unsigned comment added by 131.172.99.15 ( talk) 08:10, 14 August 2008 (UTC)
Will people please stop saying that good implementations destroy P and Q. In fact, good implementations keep P and Q, and never calculate D at all; they use the Chinese Remainder Theorem to speed up private key operations, and calculate a separate D for P and Q. Furthermore, it has long been known that P and Q are easily determined given N, E, and D. So there is no point to this misleading advice. ciphergoth 19:54, 2004 Nov 30 (UTC)
Would anyone be interested in working this article up to "Featured Article" standard? What would it need? I guess some sort of diagram or illustration is usually asked for, and references. — Matt 17:45, 30 Nov 2004 (UTC)
Should we be including a proof of RSA in this section? Revived 22:31, 28 Dec 2004 (UTC)
The history section of the article gives the impression that Rivest, Shamir and Adleman invented the algorithm out of thin air although very similar work had actually been published shortly before by others. For example: Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance, IEEE TRANSACTIONS ON INFORMATION THEORY (Jan. 1978) (article submitted on June 17, 1976). Unfortunately I don't have easy access to this article - I've only found it referenced on http://www.cyberlaw.com/rsa.html.
The recently declassified A History of U.S. Communications Security (Volumes I and II); the David G. Boak Lectures, National Security Agency, 1973 (declassified December 2008) mentions in volume 2 an algorithm that is not fully described but is clearly similar to RSA. The document implies that it's only useful for encryption, not signature, though. A closer reading might indicate how much the NSA knew about PKC when RSA's work was published. Volume 2 seems to date from 1981. 209.221.140.12 ( talk) 11:15, 29 December 2008 (UTC) In view of the close links between GCHQ and NSA, it would be surprising if NSA did not know about Clifford Cocks's work long before its public disclosure. 109.158.245.62 ( talk) 23:09, 2 April 2012 (UTC)
how large shoude be p and q? can you give me some real public key?
For an l-bit modulus n=pq, the lengths of p and q would need to add up to about l. So 512-bit p and q would give you an n around 1024 bits long. I generated a real key just for you and created a sub-article about it under the "working example" part of the main article. Lunkwill 4 July 2005 23:15 (UTC)
Every article I've ever seen on RSA uses n as a public modulus. Why the heck are we using n to be the message integer here? That's really confusing, especially since N is the modulus. Should we fix this, or am I wrong about the conventional variables? Birge 02:19, 16 August 2005 (UTC)
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)
A Wikipedia reader has asked the following question at the Wikipedia Help Desk.
Where m is the plaintext in this case m=123.Shouldn't m be less than or equal to the least of (p-1) or ( q-1) which would be 52 or less for both m^(e d) congruent m(mod p) and m^(e d) congruent m(mod q) to be correct.
I have posted it here so that we can provide an answer. Capitalistroadster 09:53, 1 December 2005 (UTC)
I have just removed a claim that RSA is based on the discrete logarithm problem. Here are some additional clarifications. RSA is based on the integer factorisation problem, that is RSA can be reduced to integer factorisation. This means that RSA can be broken if the integer factorisation problem is easy, but does not mean that every attack on RSA leads to a fast factorisation algorithm. It is indeed possible to prove that integer factorisation can be reduced to computing discrete logarithms modulo composite integers. I.e. if there exists a fast algorithm for computing discrete logarithm modulo pq, then this algorithm can be used to find p and q fast. If there exists a fast algorithm for computing discrete logarithms modulo primes, then this algorithm cannot be used to break RSA.
That said, it should be clear that claiming RSA is based on the discrete logarithm problem, is certainly a confusing claim, even though it is correct in the sense described above. Since additionaly solving discrete logarithms does not provide an alternative way to break RSA, I have removed the claim that RSA is based on DL. 24.228.93.22 20:52, 17 March 2006 (UTC)
If you don't mind.
for Ron Rivest, Adi Shamir, and Leonard Adleman.
I'm sure they'd appreciate a proper citation for their work, as you might. —The preceding unsigned comment was added by CyberSongs ( talk • contribs) 16:03, 26 June 2006 (UTC)
Ah, so, you get top billing over the creators? Doesn't seem fair, an offshoot, no doubt, of the failure in Wikipedia and most of the world these days to define their acronyms.
The article says:
How does one use Fermat's little theorem to do this? The theorem states that for all integers a and all primes p, . Only p and q are primes here, so one would assume that the theorem is to apply to the last two equations, but how? The first congruences state that there exist integer k and k' such that , but how does this help? The rest of the explanation is very clear, but this part could surely be made more obvious. 82.103.198.180 14:43, 9 July 2006 (UTC)
Since ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q-1) then ed ≡ p (mod p) and ed ≡ q (mod q) which can be substituted in Fermat's little theorem as above. 86.9.165.154 12:23, 31 March 2007 (UTC)
The article says: "RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys."
Velle 12:54, 20 August 2006 (UTC)
What is the size of RSA keys? I saw somewhere that they are multiples of 1024, with 1024 about to be broken and 2048 expected to be broken in 2030. But I guess they could be any size?
And what is the key size? The size of p,q,m or some combination?
Velle 13:01, 20 August 2006 (UTC)
It is not necessary to choose e<phi(n). RSA works as long as the public exponent e is just relatively prime to (p-1)(q-1). In fact, Cocks description of RSA used a fixed public exponent e=n. Also some protocols may require that the sender can verify that e is chosen relatively prime to phi(n). Such a verification is easy if e is a prime larger than n. 67.84.116.166 17:12, 10 September 2006 (UTC)
We should clearly distinguish between modular reduction and congruence relations. I.e. denotes a modular reduction. Here mod is a function. The result of is an integer in the range . On the other hand denotes an congruence relation, which only states that the difference between the left and right side of the relation is divisible by n. In particular we should not mix the two notations and not write things like c=me(mod n). 212.254.78.1 10:09, 15 October 2006 (UTC)
From article: " Norbert Wiener showed in 1990 that if p is between q and 2q (which is quite typical) and d < n1/4/3, then d can be computed efficiently from n and e."
According to the Norbert Wiener article he died in 1964 so it seems that someone has mistaken him with someone else. Anybody know who actually made this discovery? -- Evild00d 10:39, 26 October 2006 (UTC)
In the example section, I see this
φ(n) = (61 − 1)(53 − 1) = 3120-
What the hell is the "-" at the end? I checked, it's not there in the code. I am not familiar with entering math into wikipedia yet, but that definitely looks like some sort of a script glitching out. User:IvanAndreevich 27 October 2006
The article mentions that if the message is 0 or 1 the encrypted message will be the same, but if i remember correctly, if m = n - 1, the encrypted message will also be the same (unless the public exponent is an even nuber, which it is not). Is this correct, and is it worth mentioning? 213.214.198.224 15:09, 13 January 2007 (UTC)
I'm trying to do a rough implementation of RSA in C++, and have encountered a stumbling block, which could be a programming error, but I think is a more fundamental misunderstanding on my part of the encryption scheme. For simplicity, I'm using 17 as the public exponent (e). The problem arises when I end up with prime numbers P and Q whose totient (phi) is a whole number multiple of e. Under these circumstances, my decrypted message ends up with the same value as my encrypted method (.e.g, message = 17 , encrypted to 46, and decrypted to 46 as well). I guess technically, e and phi aren't coprime because in addition to 1, they share e as a common factor. So I guess that's where the problem lies, but is there a way to make sure I don't end up with P and Q that will yield such a result? I've tried this with both phi = (p-1)(q-1), as well as lambda = lcm(p-1, q-1), but neither is helpful. Also, this doesn't happen if I restrict P and Q to values under 103. As soon as I let them go to 103 or above, I start seeing this behavior pop up. Any clarification here, or on my talk page, or by email (bmearns#coe.neu.edu) would be appreciated). B. Mearns *, KSC 19:50, 1 March 2007 (UTC)
well, it looks like some sort of anti-semitic statement has been put up in place of the rsa entry... backup? —The preceding unsigned comment was added by 68.159.120.49 ( talk) 02:41, 6 March 2007 (UTC).( 68.159.120.49 02:41, 6 March 2007 (UTC))
I'm removing the following paragraph:
First, RSA without padding is in most cases insecure and should be avoided. The advice given here to use short messages only when using RSA without padding makes the situation even worse. The paper "Why Textbook ElGamal and RSA Encryption are Insecure" by D. Boneh, A. Joux, and P. Nguyen presented at AsiaCrypt '00 analyzes this situation. One attack presented there is only feasible when short messages are encrypted without padding. 85.2.31.101 12:59, 10 April 2007 (UTC)
I'm also removing this paragraph:
First, the coincidence has nothing to do with the size of . In particular it can happen for . An example is and or . Cases where become rare with large . There are only such messages. Paddings schemes do not prevent these unlikely cases. can happen even with padding, but that is just very unlikely. 85.2.41.56 12:14, 14 April 2007 (UTC)
Is there a need for oversimplified implementations that show how to implement textbook RSA (i.e. no padding) using standard libraries? I think it is not, because it (i.e. writing an insecure implementation) is simple enough to be done by most people. Moreover, there is a danger that promoting such implementations will lead to insecure use, when people start extending such tiny implementations and use them instead of the preinstalled standard libraries. However, if readers still look for educational implementations we might want to find one that does a good job commenting the code. [1] might be a start, although I'm sure there are better pages. 85.2.56.39 07:58, 18 April 2007 (UTC)
Can any one explain me how a key generator choose the two prime number P and Q? It seems to me that choosing 512bit long prime number is not easy without certain algorithm.
Russkie company Elcomsoft blackmails Intuit via breaking the RSA-512 Quicken factory support backdoor keycode. This is the same company which blackmailed Adobe Acrobat a few years ago but FBI nabbed the boss, who had to be released due to liberal whining instead of supermax.
Link: http://www.theregister.co.uk/2007/06/23/quicken_password_backdoor/
Me thinks NSA and Homeland Security should act against the crypto-communists before it is too late for the free world! 81.0.68.145 16:41, 24 June 2007 (UTC)
RSA can be used for general encryption. Do I need to find references stating such or is it obvious? Someone reverted my edit stating so. Its expensive computationally, but done for short messages. Daniel.Cardenas 17:50, 28 June 2007 (UTC)
Why can't you just encrypt all possible plaintext characters once and compare the encrypted characters with other ciphertexts? Wouldn't you instantly be able to decrypt all messages given the public key? There must be something I am missing in the article... —Preceding unsigned comment added by 141.154.34.78 ( talk) 04:28, 26 December 2007 (UTC)
Yes, there are infinitely many primes but only finite number of primes are known. Why can't some govt (say US govt) create a database of all known primes and then figure out p and q by dividing n with all the numbers in the database? Don't say there are infinitely many primes because only finite number of primes are known, and it's possible to create a database of all known primes. 75.87.86.76 ( talk) 22:04, 18 March 2008 (UTC)
In the list describing the RSA algorithm, I believe there is a mistake with the function used to describe totient. It changes from a \phi to a φ for some reason, but they could be different functions as I am not sure of the steps, so I didn't change it.
RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way:
1. Choose two distinct large random prime numbers p and q 2. Compute n = pq\, * n\, is used as the modulus for both the public and private keys 3. Compute the totient: \phi(n) = (p-1)(q-1) \,. 4. Choose an integer e such that 1 < e < φ(n), and e\, and φ(n) share no factors other than 1 (i.e. e and φ(n) are coprime) * e is released as the public key exponent 5. Compute d to satisfy the congruence relation d e \equiv 1\pmod{\phi(n)}; i.e. de = 1 + kφ(n) for some integer k. * d is kept as the private key exponent —Preceding unsigned comment added by Michael miceli ( talk • contribs) 19:34, 21 May 2008 (UTC)
I've removed a section about violating US export restrictions by printing some small code snippets on T-shirts because it is not relavant. What was relevant to the discussion about export control is for example the case Bernstein v. United States or the criminal investigation against Phil Zimmermann for publishing PGP. These cases did have an impact on cryptography. The T-shirts did not. 85.1.98.86 ( talk) 20:46, 1 July 2008 (UTC)
Is there a reason why d is the private key and e is the public key? Can you release d and keep e secret and achieve the same results? —Preceding unsigned comment added by 68.62.2.221 ( talk) 21:56, 21 August 2008 (UTC)
Real standards for RSA, such as PKCS #1 or IEEE P1363, specify that , where . Note that , so the difference is at least a factor of 2.
To see that this is both necessary and sufficient, observe that the Chinese Remainder Theorem describes an isomorphism of rings . Therefore if and only if and . Fermat's Little Theorem tells us that the latter happens if and only if and . Hence must be a multiple of both and , i.e., a multiple of by definition of lcm.
None of this makes any difference for practical implementations, since they use the Chinese Remainder Theorem directly for private-key operations and the public exponent is chosen to be small.
-- 80.177.3.76 ( talk) 19:34, 10 October 2008 (UTC)
Hi,
I've had just added the correct preconditions for decryption to work.
History:
# 18:03, 16 February 2009 Skippydo (Talk | contribs) (28,437 bytes) (undo: with overwelmingly high probability, M is relatively prime to p and q.) # 13:37, 16 February 2009 141.24.45.251 (Talk) (28,473 bytes) (→Encryption: vgl. page 318 in ISBN 3-540-42061-4 or slide 19 in chapter 4 of networt security analysis of prof. schäfer at tu-ilmenau or look at the prerequisites of the euler theorem) (undo)
The wikitext says, that the Message M is put into a number m < n.
The assumption is that (M**phi(n) mod n = 1), which does not hold for n=15, M=3.
The correct precondition - as they are also mentioned in scientific literature - is that m is relativly prime to n and m < n.
Removing this precondition - as skippydo did - renders the the algorithm wrong. Who wants an encrpytion algorithm that *probably* can decrpyt ones important messages - but not always though they are correct.
I could agree that with m < n m is likely to be relativly prime to n - but not always the case.
Please give a proof that (m < n) implies (m relatively prime to n) before removing the preconditions from the wikitext!
141.24.45.251 ( talk) 13:35, 18 February 2009 (UTC)
This article uses the phrase secret key as a synonym of private key. This could cause confusion with secret-key cryptography, which is not the topic of this article. It would be best to use private key exclusively. DaveBeal ( talk) 15:59, 14 March 2009 (UTC)
I can't reproduce the example of encryption / decryption using python or scientific calc.
I get:
123^17 mod 3233 = 855 and not 2193 Indeed 855^2753 mod 3233 = 123 so it gives back message m=123 whereas 2193^2753=1254 which is not expected m
Am i missing something? 82.66.65.79 ( talk) 14:34, 18 May 2009 (UTC) Chris
(Ie that decryption works.) There was a good explanation here, involving Fermats little theorum. I went to look for it and it has disappeared. The one liner does not cut it. Who deleted it, and why! (There seems to be a general theme that maths on wikipedia shoul be impenetrable.) Tuntable ( talk) 00:02, 20 November 2009 (UTC)
I also added a note about why the obvious attack of finding a different decrypter
would not work. This was not obvious to me initially. It also helps give a good understanding of the algorithm, and is short. Remember, this is the intuitive seciton. Tuntable ( talk) 10:53, 27 January 2010 (UTC)
Small detail: the "concise proof" uses k, while the "intuitive proof" uses h. These are the same variable. So perhaps h could be changed to k in the "intuitive proof" for notational consistency. 69.139.234.238 ( talk) 10:11, 25 November 2010 (UTC)
The article says that the patent was to expire in September 2003, and that RSA released the algorithm into public domain in September 2000. United States patent law states that the term of patent is 20 years, which corroborates this information. However, most other sources I've found state that the patent lasted only until 2000.
Does anyone know which is the correct case? -- Ixfd64 ( talk) 03:17, 25 November 2009 (UTC)
Both of these statements are bold to not have a reference. I added citation needed, but doing some small googling the second statement seems like it should be "e is usually 2^16 - 1" not + 1 website Michael miceli ( talk) 21:21, 22 February 2010 (UTC)
http://techie-buzz.com/tech-news/1024-bit-rsa-cracked.html -- 149.4.115.3 ( talk) 22:51, 8 March 2010 (UTC)
There is a EUROCRYPT 2009 paper (Aggarwal and Maurer, Breaking RSA Generically is Equivalent to Factoring) showing that breaking RSA generically (i.e., using only ring operations to work on the numbers involved) is equivalent to factoring. I believe that this is significantly stronger than all previous security proofs of RSA. Might be worthwhile adding to the discussion in the hardness section. —Preceding unsigned comment added by 128.178.42.58 ( talk) 14:52, 18 March 2010 (UTC)
In the worked example, it says 'A' is represented in ASCII as 65. As far as I know, 'A' in ASCII is 41 while 65 is 'e.' Am I missing something?
In the RSA article I attempted to change the private key example. The private key should consist of (P,Q,D) not (PQ,D). Yes we can definitely compute P and Q if we know D however for didactic purposes in this article its important for people to be able to understand that from the public key only we CAN NOT compute P and Q separately which is the foundation of the algorithm based on the integer factorization problem. Integer factorization states that semiprimes, in this case PQ are computationally infeasible to factor.
Anytime in the article that the private key is shown it should be listed as (P,Q and D) not (PQ,D).
http://en.wikipedia.org/wiki/Integer_factorization —Preceding unsigned comment added by Mikeatcmu ( talk • contribs) 17:12, 17 September 2010 (UTC)
Yes I see how P and Q do not have to be represented separately in the explanation of the private key. P and Q separately are only needed to generate d. Thanks for the explanation. —Preceding unsigned comment added by 128.237.243.213 ( talk) 00:19, 22 September 2010 (UTC)
When are the primes created in web browser? I would assume it takes several minutes for a web browser to find two e.g. 1024 primes? When are they created?-- Teveten ( talk) 12:10, 3 October 2010 (UTC)
In the end of the proof there is stated:
So it's no complete proof because RSA works for all numbers and not only for those that are relatively prime to n. -- Jobu0101 ( talk) 09:39, 15 March 2011 (UTC)
Is RSA such a common search term for South Africa that it really needs its own disambiguation message? Feezo (send a signal | watch the sky) 21:55, 20 May 2011 (UTC)
http://www.cablegatesearch.net/manning-logs-diff.php Ctrl F for (7:35:37 AM) bradass87: other person knows a lot about phones... how to tap cellular phones (its his job, after all) — Preceding unsigned comment added by 90.204.167.76 ( talk) 17:50, 26 July 2011 (UTC)
In that source, there were mentioned that only if raw encrypted data is signed, there is a weakness. This is rather unlikely and does not includes case when signed data is encrypted, so it seems that the same key CAN be used safely for signing and encryption, as long as not blindly signing random raw data. - Yyy ( talk) 11:29, 30 July 2011 (UTC)
Diffie-Hellman was first, based on WP dates in that article and this one, as well as CISSP references. (These aren't authoritative as they all cite answers from the same, single, dictatorial source, which is ISC2. They are ubiquitous).
Also removed reference to being consider adequate since all algorithms used for their intended purpose are also deemed adequate -- which is how they end up getting used in the first place. However, most banking encryption isn't this sophisticated -- which was the real reason I removed it. See "Security Engineering" by Ross Anderson.
Kernel.package ( talk) 18:57, 10 November 2011 (UTC)
This page has been moved from RSA to RSA algorithm based on an assertion that "the RSA - acronym should redirect to the most notable denotations of the acronym (which is in this case an organisation Royal Society of Arts and not the algorithm. The page view statistics indicate that Royal Society of Arts got about 4,500 hits in October 2011 and RSA (as far as the page view stats for October are concerned the old name would appear to be required) got 63,914. Accordingly, without going through all of the other uses of the acronym, this assertion would not appear to be well grounded in fact and the RSA algorithm would appear to meet WP:PRIMARYTOPIC. Moreover, no discussion took place on the talk page. I believe that the original page name might usefully be restored.
FrankFlanagan ( talk) 23:45, 10 November 2011 (UTC) 23:56, 10 November 2011 (UTC)
Recent additions to the Faulty Key Generation section about Lenstra's discovery of faulty keys are premature and read like an essay. There have been additional developments that change the story significantly -- see Nadia Heninger's post https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs and my http://diceware.blogspot.com. In particular the duplicate keys seems to come from weak entropy generation in some black-box appliances, perhaps when they are first setup. The keys with one shared prime seem to be caused by an interesting programming glitch:
seed_random_number_generator (entropy-pool) P=generate_random_prime () add_entropy_to_pool (whatever) Q=generate_random_prime () public_key=P*Q
The add_entropy statement seems harmless enough, but if the initial entropy pool is weak, it can result in two users with the same P and different Q's, which is fatal to RSA via GCD algorithm. The simple solution is to remove the add_entropy statement. The apparent weak entropy revealed by duplicate keys from some appliances implies a bigger problem. If the detailed nature of the weak entropy can be characterized, perhaps by reverse engineering one of the boxes, then an attacker can generate a large numbers of keys using the same limited entropy states and compare them against public key registries or intercepted internet traffic, with a high likelihood of many successful matches. Generating high quality random numbers is essential to all public key systems, not just RSA. For example, an attacker who discovers weak entropy being used could look for two DSA signatures that employ the same nonce and thereby find the DSA secret key, much like the PlayStation attack. -- agr ( talk) 19:45, 17 February 2012 (UTC)
what is md5 in padding — Preceding unsigned comment added by 220.225.106.177 ( talk) 08:13, 6 March 2012 (UTC)
Hi We said that there mustn't be any way to find the private key by public key. public key is(n, e) private key is(n, d) and d=φ(n)/e can't we easily find the d from n and e ?! Qualux ( talk) 16:57, 13 July 2012 (UTC)
Is it possible that 22,3 and 22,7 are the smallest keys you can get with RSA without having the same key for both encryption and decryption ? — Preceding unsigned comment added by 2001:6F8:14DC:2:1E65:9DFF:FE26:33C3 ( talk) 07:26, 28 August 2012 (UTC)
I don't see how small RSA keys are useful, but I'll bite: 22,3 and 14,5 look a little smaller? -- DavidCary ( talk) 17:10, 13 February 2014 (UTC)
I can't make sense of "so, d*e= 1 mod φ(n)". It seems like some text got deleted or moved. — Preceding unsigned comment added by 213.114.153.157 ( talk) 16:24, 25 September 2012 (UTC)
how can this be a valid range "0 ≤ m < n " when 0^x = 0 and 1^x = 1 ? — Preceding unsigned comment added by 129.12.46.20 ( talk) 12:57, 25 July 2013 (UTC)
Primary link to article:
Yet to be confirmed...but looks good. — Preceding unsigned comment added by 80.47.125.210 ( talk) 05:35, 15 August 2013 (UTC)
The article is about RSA not its derivatives. If I were an author to HE-RSA's paper I would be ashamed of such inappropriate inclusion.
A couple years ago I added the sentence "Note that at least nine values of m will yield a ciphertext c equal to m, but this is very unlikely to occur in practice", with a footnote saying, "Namely, the values of m which are equal to -1, 0, or 1 modulo p while also equal to -1, 0, or 1 modulo q. There will be more values of m having c=m if p-1 or q-1 has other divisors in common with e-1 besides 2 because this gives more values of m such that or respectively." In December 2012, user:Quondum removed this with the comment "Removal of false statement. There is a bijection between ciphertexts and plaintexts in RSA."
But of course, what I wrote is true. It's quite easy to see that the message 0 will give ciphertext 0 and 1 will give 1. This has nothing to do with whether there exists a bijection between m and c. So I'm putting my sentence back in. Eric Kvaalen ( talk) 08:15, 28 November 2013 (UTC)
If for example p=2 and q=2 (both valid prime numbers) then the totient is (p-1)*(q-1) = (2-1)*(2-1) = 1. Also, if p=2 and q=3 the totient will be 2. Since in the next step the value e must be a random integer greater than 1 but less than the totient, how is that specific condition to be resolved? 2 and 3 are both valid prime numbers, so it is possible (but highly unlikely) that both p and q will be 2, or that one will be 2 and the other will be 3 when the random prime number generator is creating the values for p and q. How is the algorithm to proceed then? Does it have to go back and regenerate values p and q? 76.104.145.19 ( talk) 07:43, 4 January 2014 (UTC)
I wrote a simple VB6 (Visual Basic 6) program to test RSA. For simplicity I used 1-byte random prime numbers for P and Q, which produced 2-byte numbers for the totient, the modulo, and the keys E and D. I'm not sure what the conditions are yet, but I've found that even when E and D are multiplicative inverses as calculated by finding a value of D that makes (D * E) mod totient = 1, D is NOT necessarily able to decrypt a number that had been encrypted with E (it usually does, but sometimes it doesn't). I made sure all the values were calculated according to the Wikipedia article. Totient = (P-1)*(Q-1). Modulo = P*Q. E is a random value greater than 1 and less than the totient, and who's GCD is equal to 1. Everything has been calculated to Wikipedia's specs. Yet, I'm not always able to decrypt a number that has been encrypted. It fails about 1 time out of 15 times. Sometimes more, sometimes less. The only thing I can think of is that the Wikipedia article is not complete in listing special conditions in which RSA actually fails, and an encrypted number is unable to be decrypted. E and the totient is all I should need to encrypt a number, and D along with the totient is all I should need to decrypt it. I've double checked my program, and can't find any bugs in the code. So I assume something may be missing or inaccurate in the Wikipedia article.
Ok I think I found the problem. It happens when P=Q.
76.104.145.19 (
talk)
09:58, 4 January 2014 (UTC)
I just found the problem still occurs, even when the two random prime numbers are different from each other. I thought I solved it, but that was apparently only one of the conditions that triggered this problem. I'm finding that sometimes encrypted numbers are still not decryptable. And I can't find the cause. None of the numbers are equal to each other. Is it possible that certain mathematical relationships between some of the numbers that are extremely unlikely to occur in 1024bit numbers (but are fatal to the RSA algorithm if they do occur) are highly likely when working with small numbers? Is there something I'm missing, or is there a mistake in the article somewhere? 76.104.145.19 ( talk) 10:14, 4 January 2014 (UTC)
It seems that when E is equal to the modulo this also happens. The result is that the encrypted value is 0. And there's no way to decrypt the value of 0 it seems. And also it seems if for any reason the input number encrypts to the value of 1, then it also is not decryptable. So basically if it encrypts to 0 or 1 then it gets "stuck" at 0 or 1, and can't be decrypted. Of course that makes sense because 0 to the power of anything is 0, and 1 to the power of anything is 1. How an encrypted value could end up being 0 or 1, I don't know. Theoretically that shouldn't happen if everything else in the algorithm is correct. But that's not the only times it has failed. Here's one that makes no sense at all.
P=7
Q=11
Totient=60
Modulo=77
E=37
D=13
input number = 79
encrypted number = 51
result of decrypting encrypted number = 2
Something is VERY wrong here. Any idea what's happening? 76.104.145.19 ( talk) 10:53, 4 January 2014 (UTC)
I finally got it working. Thanks for all the help you guys provided. 76.104.145.19 ( talk) 02:34, 5 January 2014 (UTC)
"Using λ instead of φ(n) allows more choices for d " ? this is not the contrary? λ is smaller than φ(n). In fact with the mod. we have the same computing...if you talk about lcm it's important maybe to compare the key generation by Euler and by Carmichael. For example with Euler way, computation is faster than with Carmichael way. With Carmichael in reseach it s more clear because the Interval is smaller and more clear, we don't have repetitions. -- Mbachkat ( talk) 23:02, 14 May 2014 (UTC)
The Euler theorem says m and n=p*q should be coprime, but in practice, m might be p or qo. What will happen in that case? Jackzhp ( talk) 22:17, 23 June 2014 (UTC)
I am unable to open my picture files. How can I fix this? — Preceding unsigned comment added by Njblondie ( talk • contribs) 22:26, 28 December 2014 (UTC)
The last two attacks (although correct) are uncited. Dues should be given to the people who first noticed and published these attacks in relation to RSA. Informalmunch ( talk) 12:11, 18 February 2015 (UTC)
Rivest, Shamir and Adleman note[2] that Miller has shown that – assuming the Extended Riemann Hypothesis – finding d from n and e is as hard as factoring n into p and q (up to a polynomial time difference).[19]
It means using n = pq and (p-1)(q-1) instead of p and p-1 in ElGamal would be at least as secure as RSA. 109.90.224.162 ( talk) 15:28, 10 October 2015 (UTC)
From article Choose two distinct prime numbers, such as
p = 61 and q = 53
7 times 9 = 61 it is not an example of a prime number
—Actually, 7*9=63. 61 is a prime number. 217.99.252.222 ( talk) 06:00, 26 December 2015 (UTC)
The article references E and N as the public key components, and d as the private key component.
HOWEVER according to the Key Generation paragraph E is chosen as co-prime toφ(n), and d is computed according to the congruence relation of
d ≡ e^-1 (mod φ(n)).
This is not in line with the source "A method for obtaining digital signatures and public-key cryptosystems" by Rivest Shamir and Adleman where section VII describes how to "[...] choose a number d which is relatively prime to φ(n) [...]" and further to "[...] compute e from d and φ(n)[..]"
As a result, both the Key Generation, Example and Code subparagraphs of the Operation section need to be corrected. — Preceding unsigned comment added by FLHeilmann ( talk • contribs) 13:01, 8 February 2016 (UTC)
Fair point, I'll fix the code listing as well sicne I also made changes to that. — Preceding unsigned comment added by FLHeilmann ( talk • contribs) 14:15, 9 March 2016 (UTC)
I'm not sure enough of the correction to make it, but 'd' and 'e' in the example are not being used consistently. The talk page says 'e' can/should be small, and 'd' large, yet the example has 'e'=2753 and 'd'=17. Similarly, it talks about calculating 'e', then immediately says "Let d = 2753". Someone needs to sort this out. — Preceding unsigned comment added by 76.28.205.57 ( talk) 05:47, 22 February 2016 (UTC) Hi! I made an account to correct this. e and d were being mixed up during the Key generation part of the article. I'm going to go through and fix the rest- yes, e should be small, d should be large, and you calculate d from e. look at the sources pls if you don't believe me. — Preceding unsigned comment added by Laudiacay ( talk • contribs) 03:37, 23 February 2016 (UTC)
I was the one who made the changes by swapping d and e. Please check the original RSA paper. While I agree that the example values are not in line with the text, e and d are now swapped again. You need to CHOOSE d AS COPRIME and COMPUTE E As per Rivest and Adleman Paper Section VII-C,VII-D. See my previous talk topic for details.
— Preceding unsigned comment added by FLHeilmann ( talk • contribs) 12:34, 4 March 2016 (UTC)
Uhh..... I don't think that's correct. You choose the co-prime, but that's e, the encryption exponent. e is usually chosen as 65537. You choose a small, constant e for standardization purposes (and security- some formerly common e's are VERY vulnerable (like 3 for example)). d is supposed to be secret- with a small e inversed on your enormous modulo, d will be large and hard to brute-force, which is the entire trapdoor function in a nutshell... d chosen as coprime and e computed simply does not make sense, if d is the secret and e is the public. Please do re-read the paper, it agrees with me. 17:58, 11 April 2016 (UTC) — Preceding unsigned comment added by Laudiacay ( talk • contribs)
FLHeilmann, the current version of the article is correct for encryption. Didn't check signing, but the code, worked examples, key generation/decryption, and basic Alice/Bob examples are all correct. Please don't change the math any further, it's correct now. Laudiacay ( talk) 18:02, 11 April 2016 (UTC)
Note: It appears in the original paper that they did reverse it, but soon after they realized that just picking a giant coprime d is stupidly computationally expensive. The equivalent, picking an e and then calculating d, is waaaay faster to get a big, secure d for current keysizes. So, yes, the original paper does agree with you, but NO secure or fast implementations of key generation today do. Laudiacay ( talk) 18:21, 11 April 2016 (UTC)
If anyone needs to remember the equations used to encrypt/decrypt RSA for a test or something, use the mnemonic SEMEN (c = m^e mod n) MCDONALDS (m = c^d mod n) — Preceding unsigned comment added by 137.63.71.51 ( talk) 21:23, 29 February 2016 (UTC)
IP 66.196.50.51( contributions, talk) put the following text in the article which then got removed by Cluebot:
This page is being linked to by Ransonware to further their argument as to why I need to pay them money to decrypt my files. Maybe a disclaimer here would help, for anyone that might click on the link to read.
I'm putting it here on the talk page which is the proper place for such discussion, without further substantial comment on the subject. Digital Brains ( talk) 14:16, 22 April 2016 (UTC)
The comment(s) below were originally left at Talk:RSA (cryptosystem)/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
I think it is a virus 108.89.134.155 ( talk) 16:33, 18 June 2015 (UTC) |
Last edited at 12:40, 23 June 2015 (UTC). Substituted at 03:46, 30 April 2016 (UTC)
This page contains just a few lines that mention how quantum computers could theoretically crack this algorithm eventually. Should this be expanded, or left to be covered by other articles? — Preceding unsigned comment added by Gluons12 ( talk • contribs) 19:16, 7 May 2016 (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)
I think that most people tend to get lost on the link between the totient function and Chinese remainder theorem, so I decided to put it here.
we have:
(M^(p-1))^(q-1) = aq +1 (Fermat's Little Theorem) a is any integer
The above can be re-ordered and for p we can state as:
(M^(q-1))^(p-1) = bp +1 --b is any integer.
So M^((p-1)(q-1)) -1 is divisible by both p and q
Hence we can conclude that: M^((p-1)(q-1)) -1 = m pq (that is there is some integer m for which LHS is mpq)
Hence the property that M^(totient(pq))= 1 mod pq 07:03, 26 August 2016 (UTC)
— Preceding unsigned comment added by Alokdube ( talk • contribs) 07:00, 26 August 2016 (UTC)
We may choose as the smallest prime greater or equal h(m) with some numerical hash function h of the message m.
84.118.82.226 ( talk) 10:04, 9 February 2018 (UTC)
The following is a paragraph directly from the current (see signature) English language entry:
Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described an equivalent system in an internal document in 1973.[7] However, given the relatively expensive computers needed to implement it at the time, RSA was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification.
Maybe I'm just being a stickler but I would suggest that the second-to-last sentence be reworded somewhat as it seems to imply that GCHQ also called Clifford Cocks' system RSA, which would be preposterous.
I suggest instead: However, given the relatively expensive computers needed to implement it at the time, Cocks' RSA-like system was considered to be mostly a curiosity and - as far as is publicly known - was never deployed.
I know it's not much of a change and normally I'd just edit it and let it be instead of starting a talk section to (hopefully) gather other ideas but since I have a sneaking suspicion either I'm the only person who would notice this incongruity or, possibly, it's not incongruous at all and I'm just being a pedant.
So, if anyone has anything to say about it I'd appreciate feedback on the proposed change. If I don't hear any objections, I intend to make the edit on or after 26 May, 2018 (That's Pacific Standard time zone).
DacodaNelson ( talk) 20:52, 19 May 2018 (UTC) DacodaNelson ( talk) 20:52, 19 May 2018 (UTC)
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)
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: /info/en/?search=RSA_(cryptosystem)#CryptoStrengthOfPQ
and here (old reverted edit cache): https://en.wikipedia.org/?title=RSA_(cryptosystem)&diff=983454044&oldid=983447902#CryptoStrengthOfPQ
But my edit was been reverted: https://en.wikipedia.org/?title=RSA_(cryptosystem)&oldid=983456104
I did discribed all, then put anchor, and add that link on Safe-Primes-definion page:
https://en.wikipedia.org/?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 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)
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)
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)
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)
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 |
![]() | This ![]() It is of interest to the following WikiProjects: | |||||||||||||||||||||||
|
|
no archives yet ( create) |
![]() | This article links to one or more target anchors that no longer exist.
Please help fix the broken anchors. You can remove this template after fixing the problems. |
Reporting errors |
Is is the same as greatest common divisor? gcd(n,m)? — Preceding unsigned comment added by 156.17.236.67 ( talk) 14:07, 6 January 2012 (UTC)
Equations involving mod operations seem to be written in the wrong order. On this account I was not able to understand the simple operation even though it should have been easy. The first example is as follows:
d*e = 1 mod( phi )
Surely you mean:
d*e mod( phi ) = 1
Don't you? Or am I missing something?
1 mod( anything ) = 1 doesn't it?
Well, that is an unfortunate convention. I am glad that you explained that. To clarify, I guess that you are saying that: (II) x=y mod(a) is the same thing as: (I) x%a = y%a ... if I may steal that modulus symbol from C. But in your notation, how do you write (II) y = x%a , where y is the unknown???? What I mean is that in equation (I), if x = 8 and a = 5, then y has to be a member of {3,8,13,18,.........}. But in equation (II), there is only one solution for y, 3. right?
If all you care about is finding out if two numbers are at the same point in a cycle given that a cycle has a certain length, that makes sense, you are qualifying in which way they are equivalent.
But there is no way of asking, using that notation, what is the most basic way to represent that point in that cycle of that given length. Or is there?
This doesn't have much to do with the subject of this page. But Lunkwill seems to know a little about this. So I just thought I would ask.
Response from Anonomous -> Keep in mind that the reasoning behind the convention is that you are doing arithmetic in a finite field, i.e. you only have a subset of the integer numbers to work with (a FINITE field of integer numbers) designated as Z sub N (where N is the number of integer elements, ex. Z sub 7 is Z sub inf. mod 7 thus => [0,6] inclusive). Therefore, anytime any particular operation is done, if the resultant number is "outside" the field, it is mod'ed down to get back into the field (this is rather a harsh explanation, but is an easy way to see it at first). So for instance, saying x [is congruent to] y (mod a) can be directly viewed as x = y + k * a for some value of k (y is a multiple of k * a which equals x). Keep in mind that a congruence and an equality are two different things. For ex, say that you have something silly like 11 [is congruent to] 1 (mod 10), this makes sense since 11 = 1 + [1] * 10, 11 is outside of the finite field of Z sub 10. The calculator notation is in fact mod(11, 10) (for TI-89) or 11 % 10 (for C/C++/Java/etc.), but that is just by notation of an operator (from a comp. sci. point of view), not modular arithmetic (from a mathematical point of view). Keep in mind that the reason for doing modulus in the first place, again, is for staying inside of the field. A really good example of this is modular exponentiation, where we have, say, some number a raised to some ridiculously large power b (which RSA does with its e and d components) but while doing it mod some normal value of n (ex. say something rhetorically stupid as 2^1234567890 (mod 3)). Would you really compute this by doing a^b and then mod'ing by n? No, you would overflow 64-bit integers within a few iterations of pow(). All you need to do is take it one step at a time maintaining the field (in fact if you do it the intelligent way you can do it in O(log n) if you use successive squaring). So, I think what you're missing is, why is the notation not like one would do it on a calculator? Because, simply, having a (mod n) at the far right hand side (and only once) isn't an operation per-sey, it is literally meaning working with integers of a finite field, which is a convenient way to work with moduluar arithmetic, (mod n). Hope this helps.
the question is answered, but I'll add that confusion seems to come from computer types who see mod(phi) as an operator changing the value of 1, but you'd be closer to the truth if you see it as an operator changing the meaning of the '=' —Preceding unsigned comment added by 131.172.99.15 ( talk) 08:10, 14 August 2008 (UTC)
Will people please stop saying that good implementations destroy P and Q. In fact, good implementations keep P and Q, and never calculate D at all; they use the Chinese Remainder Theorem to speed up private key operations, and calculate a separate D for P and Q. Furthermore, it has long been known that P and Q are easily determined given N, E, and D. So there is no point to this misleading advice. ciphergoth 19:54, 2004 Nov 30 (UTC)
Would anyone be interested in working this article up to "Featured Article" standard? What would it need? I guess some sort of diagram or illustration is usually asked for, and references. — Matt 17:45, 30 Nov 2004 (UTC)
Should we be including a proof of RSA in this section? Revived 22:31, 28 Dec 2004 (UTC)
The history section of the article gives the impression that Rivest, Shamir and Adleman invented the algorithm out of thin air although very similar work had actually been published shortly before by others. For example: Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance, IEEE TRANSACTIONS ON INFORMATION THEORY (Jan. 1978) (article submitted on June 17, 1976). Unfortunately I don't have easy access to this article - I've only found it referenced on http://www.cyberlaw.com/rsa.html.
The recently declassified A History of U.S. Communications Security (Volumes I and II); the David G. Boak Lectures, National Security Agency, 1973 (declassified December 2008) mentions in volume 2 an algorithm that is not fully described but is clearly similar to RSA. The document implies that it's only useful for encryption, not signature, though. A closer reading might indicate how much the NSA knew about PKC when RSA's work was published. Volume 2 seems to date from 1981. 209.221.140.12 ( talk) 11:15, 29 December 2008 (UTC) In view of the close links between GCHQ and NSA, it would be surprising if NSA did not know about Clifford Cocks's work long before its public disclosure. 109.158.245.62 ( talk) 23:09, 2 April 2012 (UTC)
how large shoude be p and q? can you give me some real public key?
For an l-bit modulus n=pq, the lengths of p and q would need to add up to about l. So 512-bit p and q would give you an n around 1024 bits long. I generated a real key just for you and created a sub-article about it under the "working example" part of the main article. Lunkwill 4 July 2005 23:15 (UTC)
Every article I've ever seen on RSA uses n as a public modulus. Why the heck are we using n to be the message integer here? That's really confusing, especially since N is the modulus. Should we fix this, or am I wrong about the conventional variables? Birge 02:19, 16 August 2005 (UTC)
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)
A Wikipedia reader has asked the following question at the Wikipedia Help Desk.
Where m is the plaintext in this case m=123.Shouldn't m be less than or equal to the least of (p-1) or ( q-1) which would be 52 or less for both m^(e d) congruent m(mod p) and m^(e d) congruent m(mod q) to be correct.
I have posted it here so that we can provide an answer. Capitalistroadster 09:53, 1 December 2005 (UTC)
I have just removed a claim that RSA is based on the discrete logarithm problem. Here are some additional clarifications. RSA is based on the integer factorisation problem, that is RSA can be reduced to integer factorisation. This means that RSA can be broken if the integer factorisation problem is easy, but does not mean that every attack on RSA leads to a fast factorisation algorithm. It is indeed possible to prove that integer factorisation can be reduced to computing discrete logarithms modulo composite integers. I.e. if there exists a fast algorithm for computing discrete logarithm modulo pq, then this algorithm can be used to find p and q fast. If there exists a fast algorithm for computing discrete logarithms modulo primes, then this algorithm cannot be used to break RSA.
That said, it should be clear that claiming RSA is based on the discrete logarithm problem, is certainly a confusing claim, even though it is correct in the sense described above. Since additionaly solving discrete logarithms does not provide an alternative way to break RSA, I have removed the claim that RSA is based on DL. 24.228.93.22 20:52, 17 March 2006 (UTC)
If you don't mind.
for Ron Rivest, Adi Shamir, and Leonard Adleman.
I'm sure they'd appreciate a proper citation for their work, as you might. —The preceding unsigned comment was added by CyberSongs ( talk • contribs) 16:03, 26 June 2006 (UTC)
Ah, so, you get top billing over the creators? Doesn't seem fair, an offshoot, no doubt, of the failure in Wikipedia and most of the world these days to define their acronyms.
The article says:
How does one use Fermat's little theorem to do this? The theorem states that for all integers a and all primes p, . Only p and q are primes here, so one would assume that the theorem is to apply to the last two equations, but how? The first congruences state that there exist integer k and k' such that , but how does this help? The rest of the explanation is very clear, but this part could surely be made more obvious. 82.103.198.180 14:43, 9 July 2006 (UTC)
Since ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q-1) then ed ≡ p (mod p) and ed ≡ q (mod q) which can be substituted in Fermat's little theorem as above. 86.9.165.154 12:23, 31 March 2007 (UTC)
The article says: "RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys."
Velle 12:54, 20 August 2006 (UTC)
What is the size of RSA keys? I saw somewhere that they are multiples of 1024, with 1024 about to be broken and 2048 expected to be broken in 2030. But I guess they could be any size?
And what is the key size? The size of p,q,m or some combination?
Velle 13:01, 20 August 2006 (UTC)
It is not necessary to choose e<phi(n). RSA works as long as the public exponent e is just relatively prime to (p-1)(q-1). In fact, Cocks description of RSA used a fixed public exponent e=n. Also some protocols may require that the sender can verify that e is chosen relatively prime to phi(n). Such a verification is easy if e is a prime larger than n. 67.84.116.166 17:12, 10 September 2006 (UTC)
We should clearly distinguish between modular reduction and congruence relations. I.e. denotes a modular reduction. Here mod is a function. The result of is an integer in the range . On the other hand denotes an congruence relation, which only states that the difference between the left and right side of the relation is divisible by n. In particular we should not mix the two notations and not write things like c=me(mod n). 212.254.78.1 10:09, 15 October 2006 (UTC)
From article: " Norbert Wiener showed in 1990 that if p is between q and 2q (which is quite typical) and d < n1/4/3, then d can be computed efficiently from n and e."
According to the Norbert Wiener article he died in 1964 so it seems that someone has mistaken him with someone else. Anybody know who actually made this discovery? -- Evild00d 10:39, 26 October 2006 (UTC)
In the example section, I see this
φ(n) = (61 − 1)(53 − 1) = 3120-
What the hell is the "-" at the end? I checked, it's not there in the code. I am not familiar with entering math into wikipedia yet, but that definitely looks like some sort of a script glitching out. User:IvanAndreevich 27 October 2006
The article mentions that if the message is 0 or 1 the encrypted message will be the same, but if i remember correctly, if m = n - 1, the encrypted message will also be the same (unless the public exponent is an even nuber, which it is not). Is this correct, and is it worth mentioning? 213.214.198.224 15:09, 13 January 2007 (UTC)
I'm trying to do a rough implementation of RSA in C++, and have encountered a stumbling block, which could be a programming error, but I think is a more fundamental misunderstanding on my part of the encryption scheme. For simplicity, I'm using 17 as the public exponent (e). The problem arises when I end up with prime numbers P and Q whose totient (phi) is a whole number multiple of e. Under these circumstances, my decrypted message ends up with the same value as my encrypted method (.e.g, message = 17 , encrypted to 46, and decrypted to 46 as well). I guess technically, e and phi aren't coprime because in addition to 1, they share e as a common factor. So I guess that's where the problem lies, but is there a way to make sure I don't end up with P and Q that will yield such a result? I've tried this with both phi = (p-1)(q-1), as well as lambda = lcm(p-1, q-1), but neither is helpful. Also, this doesn't happen if I restrict P and Q to values under 103. As soon as I let them go to 103 or above, I start seeing this behavior pop up. Any clarification here, or on my talk page, or by email (bmearns#coe.neu.edu) would be appreciated). B. Mearns *, KSC 19:50, 1 March 2007 (UTC)
well, it looks like some sort of anti-semitic statement has been put up in place of the rsa entry... backup? —The preceding unsigned comment was added by 68.159.120.49 ( talk) 02:41, 6 March 2007 (UTC).( 68.159.120.49 02:41, 6 March 2007 (UTC))
I'm removing the following paragraph:
First, RSA without padding is in most cases insecure and should be avoided. The advice given here to use short messages only when using RSA without padding makes the situation even worse. The paper "Why Textbook ElGamal and RSA Encryption are Insecure" by D. Boneh, A. Joux, and P. Nguyen presented at AsiaCrypt '00 analyzes this situation. One attack presented there is only feasible when short messages are encrypted without padding. 85.2.31.101 12:59, 10 April 2007 (UTC)
I'm also removing this paragraph:
First, the coincidence has nothing to do with the size of . In particular it can happen for . An example is and or . Cases where become rare with large . There are only such messages. Paddings schemes do not prevent these unlikely cases. can happen even with padding, but that is just very unlikely. 85.2.41.56 12:14, 14 April 2007 (UTC)
Is there a need for oversimplified implementations that show how to implement textbook RSA (i.e. no padding) using standard libraries? I think it is not, because it (i.e. writing an insecure implementation) is simple enough to be done by most people. Moreover, there is a danger that promoting such implementations will lead to insecure use, when people start extending such tiny implementations and use them instead of the preinstalled standard libraries. However, if readers still look for educational implementations we might want to find one that does a good job commenting the code. [1] might be a start, although I'm sure there are better pages. 85.2.56.39 07:58, 18 April 2007 (UTC)
Can any one explain me how a key generator choose the two prime number P and Q? It seems to me that choosing 512bit long prime number is not easy without certain algorithm.
Russkie company Elcomsoft blackmails Intuit via breaking the RSA-512 Quicken factory support backdoor keycode. This is the same company which blackmailed Adobe Acrobat a few years ago but FBI nabbed the boss, who had to be released due to liberal whining instead of supermax.
Link: http://www.theregister.co.uk/2007/06/23/quicken_password_backdoor/
Me thinks NSA and Homeland Security should act against the crypto-communists before it is too late for the free world! 81.0.68.145 16:41, 24 June 2007 (UTC)
RSA can be used for general encryption. Do I need to find references stating such or is it obvious? Someone reverted my edit stating so. Its expensive computationally, but done for short messages. Daniel.Cardenas 17:50, 28 June 2007 (UTC)
Why can't you just encrypt all possible plaintext characters once and compare the encrypted characters with other ciphertexts? Wouldn't you instantly be able to decrypt all messages given the public key? There must be something I am missing in the article... —Preceding unsigned comment added by 141.154.34.78 ( talk) 04:28, 26 December 2007 (UTC)
Yes, there are infinitely many primes but only finite number of primes are known. Why can't some govt (say US govt) create a database of all known primes and then figure out p and q by dividing n with all the numbers in the database? Don't say there are infinitely many primes because only finite number of primes are known, and it's possible to create a database of all known primes. 75.87.86.76 ( talk) 22:04, 18 March 2008 (UTC)
In the list describing the RSA algorithm, I believe there is a mistake with the function used to describe totient. It changes from a \phi to a φ for some reason, but they could be different functions as I am not sure of the steps, so I didn't change it.
RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way:
1. Choose two distinct large random prime numbers p and q 2. Compute n = pq\, * n\, is used as the modulus for both the public and private keys 3. Compute the totient: \phi(n) = (p-1)(q-1) \,. 4. Choose an integer e such that 1 < e < φ(n), and e\, and φ(n) share no factors other than 1 (i.e. e and φ(n) are coprime) * e is released as the public key exponent 5. Compute d to satisfy the congruence relation d e \equiv 1\pmod{\phi(n)}; i.e. de = 1 + kφ(n) for some integer k. * d is kept as the private key exponent —Preceding unsigned comment added by Michael miceli ( talk • contribs) 19:34, 21 May 2008 (UTC)
I've removed a section about violating US export restrictions by printing some small code snippets on T-shirts because it is not relavant. What was relevant to the discussion about export control is for example the case Bernstein v. United States or the criminal investigation against Phil Zimmermann for publishing PGP. These cases did have an impact on cryptography. The T-shirts did not. 85.1.98.86 ( talk) 20:46, 1 July 2008 (UTC)
Is there a reason why d is the private key and e is the public key? Can you release d and keep e secret and achieve the same results? —Preceding unsigned comment added by 68.62.2.221 ( talk) 21:56, 21 August 2008 (UTC)
Real standards for RSA, such as PKCS #1 or IEEE P1363, specify that , where . Note that , so the difference is at least a factor of 2.
To see that this is both necessary and sufficient, observe that the Chinese Remainder Theorem describes an isomorphism of rings . Therefore if and only if and . Fermat's Little Theorem tells us that the latter happens if and only if and . Hence must be a multiple of both and , i.e., a multiple of by definition of lcm.
None of this makes any difference for practical implementations, since they use the Chinese Remainder Theorem directly for private-key operations and the public exponent is chosen to be small.
-- 80.177.3.76 ( talk) 19:34, 10 October 2008 (UTC)
Hi,
I've had just added the correct preconditions for decryption to work.
History:
# 18:03, 16 February 2009 Skippydo (Talk | contribs) (28,437 bytes) (undo: with overwelmingly high probability, M is relatively prime to p and q.) # 13:37, 16 February 2009 141.24.45.251 (Talk) (28,473 bytes) (→Encryption: vgl. page 318 in ISBN 3-540-42061-4 or slide 19 in chapter 4 of networt security analysis of prof. schäfer at tu-ilmenau or look at the prerequisites of the euler theorem) (undo)
The wikitext says, that the Message M is put into a number m < n.
The assumption is that (M**phi(n) mod n = 1), which does not hold for n=15, M=3.
The correct precondition - as they are also mentioned in scientific literature - is that m is relativly prime to n and m < n.
Removing this precondition - as skippydo did - renders the the algorithm wrong. Who wants an encrpytion algorithm that *probably* can decrpyt ones important messages - but not always though they are correct.
I could agree that with m < n m is likely to be relativly prime to n - but not always the case.
Please give a proof that (m < n) implies (m relatively prime to n) before removing the preconditions from the wikitext!
141.24.45.251 ( talk) 13:35, 18 February 2009 (UTC)
This article uses the phrase secret key as a synonym of private key. This could cause confusion with secret-key cryptography, which is not the topic of this article. It would be best to use private key exclusively. DaveBeal ( talk) 15:59, 14 March 2009 (UTC)
I can't reproduce the example of encryption / decryption using python or scientific calc.
I get:
123^17 mod 3233 = 855 and not 2193 Indeed 855^2753 mod 3233 = 123 so it gives back message m=123 whereas 2193^2753=1254 which is not expected m
Am i missing something? 82.66.65.79 ( talk) 14:34, 18 May 2009 (UTC) Chris
(Ie that decryption works.) There was a good explanation here, involving Fermats little theorum. I went to look for it and it has disappeared. The one liner does not cut it. Who deleted it, and why! (There seems to be a general theme that maths on wikipedia shoul be impenetrable.) Tuntable ( talk) 00:02, 20 November 2009 (UTC)
I also added a note about why the obvious attack of finding a different decrypter
would not work. This was not obvious to me initially. It also helps give a good understanding of the algorithm, and is short. Remember, this is the intuitive seciton. Tuntable ( talk) 10:53, 27 January 2010 (UTC)
Small detail: the "concise proof" uses k, while the "intuitive proof" uses h. These are the same variable. So perhaps h could be changed to k in the "intuitive proof" for notational consistency. 69.139.234.238 ( talk) 10:11, 25 November 2010 (UTC)
The article says that the patent was to expire in September 2003, and that RSA released the algorithm into public domain in September 2000. United States patent law states that the term of patent is 20 years, which corroborates this information. However, most other sources I've found state that the patent lasted only until 2000.
Does anyone know which is the correct case? -- Ixfd64 ( talk) 03:17, 25 November 2009 (UTC)
Both of these statements are bold to not have a reference. I added citation needed, but doing some small googling the second statement seems like it should be "e is usually 2^16 - 1" not + 1 website Michael miceli ( talk) 21:21, 22 February 2010 (UTC)
http://techie-buzz.com/tech-news/1024-bit-rsa-cracked.html -- 149.4.115.3 ( talk) 22:51, 8 March 2010 (UTC)
There is a EUROCRYPT 2009 paper (Aggarwal and Maurer, Breaking RSA Generically is Equivalent to Factoring) showing that breaking RSA generically (i.e., using only ring operations to work on the numbers involved) is equivalent to factoring. I believe that this is significantly stronger than all previous security proofs of RSA. Might be worthwhile adding to the discussion in the hardness section. —Preceding unsigned comment added by 128.178.42.58 ( talk) 14:52, 18 March 2010 (UTC)
In the worked example, it says 'A' is represented in ASCII as 65. As far as I know, 'A' in ASCII is 41 while 65 is 'e.' Am I missing something?
In the RSA article I attempted to change the private key example. The private key should consist of (P,Q,D) not (PQ,D). Yes we can definitely compute P and Q if we know D however for didactic purposes in this article its important for people to be able to understand that from the public key only we CAN NOT compute P and Q separately which is the foundation of the algorithm based on the integer factorization problem. Integer factorization states that semiprimes, in this case PQ are computationally infeasible to factor.
Anytime in the article that the private key is shown it should be listed as (P,Q and D) not (PQ,D).
http://en.wikipedia.org/wiki/Integer_factorization —Preceding unsigned comment added by Mikeatcmu ( talk • contribs) 17:12, 17 September 2010 (UTC)
Yes I see how P and Q do not have to be represented separately in the explanation of the private key. P and Q separately are only needed to generate d. Thanks for the explanation. —Preceding unsigned comment added by 128.237.243.213 ( talk) 00:19, 22 September 2010 (UTC)
When are the primes created in web browser? I would assume it takes several minutes for a web browser to find two e.g. 1024 primes? When are they created?-- Teveten ( talk) 12:10, 3 October 2010 (UTC)
In the end of the proof there is stated:
So it's no complete proof because RSA works for all numbers and not only for those that are relatively prime to n. -- Jobu0101 ( talk) 09:39, 15 March 2011 (UTC)
Is RSA such a common search term for South Africa that it really needs its own disambiguation message? Feezo (send a signal | watch the sky) 21:55, 20 May 2011 (UTC)
http://www.cablegatesearch.net/manning-logs-diff.php Ctrl F for (7:35:37 AM) bradass87: other person knows a lot about phones... how to tap cellular phones (its his job, after all) — Preceding unsigned comment added by 90.204.167.76 ( talk) 17:50, 26 July 2011 (UTC)
In that source, there were mentioned that only if raw encrypted data is signed, there is a weakness. This is rather unlikely and does not includes case when signed data is encrypted, so it seems that the same key CAN be used safely for signing and encryption, as long as not blindly signing random raw data. - Yyy ( talk) 11:29, 30 July 2011 (UTC)
Diffie-Hellman was first, based on WP dates in that article and this one, as well as CISSP references. (These aren't authoritative as they all cite answers from the same, single, dictatorial source, which is ISC2. They are ubiquitous).
Also removed reference to being consider adequate since all algorithms used for their intended purpose are also deemed adequate -- which is how they end up getting used in the first place. However, most banking encryption isn't this sophisticated -- which was the real reason I removed it. See "Security Engineering" by Ross Anderson.
Kernel.package ( talk) 18:57, 10 November 2011 (UTC)
This page has been moved from RSA to RSA algorithm based on an assertion that "the RSA - acronym should redirect to the most notable denotations of the acronym (which is in this case an organisation Royal Society of Arts and not the algorithm. The page view statistics indicate that Royal Society of Arts got about 4,500 hits in October 2011 and RSA (as far as the page view stats for October are concerned the old name would appear to be required) got 63,914. Accordingly, without going through all of the other uses of the acronym, this assertion would not appear to be well grounded in fact and the RSA algorithm would appear to meet WP:PRIMARYTOPIC. Moreover, no discussion took place on the talk page. I believe that the original page name might usefully be restored.
FrankFlanagan ( talk) 23:45, 10 November 2011 (UTC) 23:56, 10 November 2011 (UTC)
Recent additions to the Faulty Key Generation section about Lenstra's discovery of faulty keys are premature and read like an essay. There have been additional developments that change the story significantly -- see Nadia Heninger's post https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs and my http://diceware.blogspot.com. In particular the duplicate keys seems to come from weak entropy generation in some black-box appliances, perhaps when they are first setup. The keys with one shared prime seem to be caused by an interesting programming glitch:
seed_random_number_generator (entropy-pool) P=generate_random_prime () add_entropy_to_pool (whatever) Q=generate_random_prime () public_key=P*Q
The add_entropy statement seems harmless enough, but if the initial entropy pool is weak, it can result in two users with the same P and different Q's, which is fatal to RSA via GCD algorithm. The simple solution is to remove the add_entropy statement. The apparent weak entropy revealed by duplicate keys from some appliances implies a bigger problem. If the detailed nature of the weak entropy can be characterized, perhaps by reverse engineering one of the boxes, then an attacker can generate a large numbers of keys using the same limited entropy states and compare them against public key registries or intercepted internet traffic, with a high likelihood of many successful matches. Generating high quality random numbers is essential to all public key systems, not just RSA. For example, an attacker who discovers weak entropy being used could look for two DSA signatures that employ the same nonce and thereby find the DSA secret key, much like the PlayStation attack. -- agr ( talk) 19:45, 17 February 2012 (UTC)
what is md5 in padding — Preceding unsigned comment added by 220.225.106.177 ( talk) 08:13, 6 March 2012 (UTC)
Hi We said that there mustn't be any way to find the private key by public key. public key is(n, e) private key is(n, d) and d=φ(n)/e can't we easily find the d from n and e ?! Qualux ( talk) 16:57, 13 July 2012 (UTC)
Is it possible that 22,3 and 22,7 are the smallest keys you can get with RSA without having the same key for both encryption and decryption ? — Preceding unsigned comment added by 2001:6F8:14DC:2:1E65:9DFF:FE26:33C3 ( talk) 07:26, 28 August 2012 (UTC)
I don't see how small RSA keys are useful, but I'll bite: 22,3 and 14,5 look a little smaller? -- DavidCary ( talk) 17:10, 13 February 2014 (UTC)
I can't make sense of "so, d*e= 1 mod φ(n)". It seems like some text got deleted or moved. — Preceding unsigned comment added by 213.114.153.157 ( talk) 16:24, 25 September 2012 (UTC)
how can this be a valid range "0 ≤ m < n " when 0^x = 0 and 1^x = 1 ? — Preceding unsigned comment added by 129.12.46.20 ( talk) 12:57, 25 July 2013 (UTC)
Primary link to article:
Yet to be confirmed...but looks good. — Preceding unsigned comment added by 80.47.125.210 ( talk) 05:35, 15 August 2013 (UTC)
The article is about RSA not its derivatives. If I were an author to HE-RSA's paper I would be ashamed of such inappropriate inclusion.
A couple years ago I added the sentence "Note that at least nine values of m will yield a ciphertext c equal to m, but this is very unlikely to occur in practice", with a footnote saying, "Namely, the values of m which are equal to -1, 0, or 1 modulo p while also equal to -1, 0, or 1 modulo q. There will be more values of m having c=m if p-1 or q-1 has other divisors in common with e-1 besides 2 because this gives more values of m such that or respectively." In December 2012, user:Quondum removed this with the comment "Removal of false statement. There is a bijection between ciphertexts and plaintexts in RSA."
But of course, what I wrote is true. It's quite easy to see that the message 0 will give ciphertext 0 and 1 will give 1. This has nothing to do with whether there exists a bijection between m and c. So I'm putting my sentence back in. Eric Kvaalen ( talk) 08:15, 28 November 2013 (UTC)
If for example p=2 and q=2 (both valid prime numbers) then the totient is (p-1)*(q-1) = (2-1)*(2-1) = 1. Also, if p=2 and q=3 the totient will be 2. Since in the next step the value e must be a random integer greater than 1 but less than the totient, how is that specific condition to be resolved? 2 and 3 are both valid prime numbers, so it is possible (but highly unlikely) that both p and q will be 2, or that one will be 2 and the other will be 3 when the random prime number generator is creating the values for p and q. How is the algorithm to proceed then? Does it have to go back and regenerate values p and q? 76.104.145.19 ( talk) 07:43, 4 January 2014 (UTC)
I wrote a simple VB6 (Visual Basic 6) program to test RSA. For simplicity I used 1-byte random prime numbers for P and Q, which produced 2-byte numbers for the totient, the modulo, and the keys E and D. I'm not sure what the conditions are yet, but I've found that even when E and D are multiplicative inverses as calculated by finding a value of D that makes (D * E) mod totient = 1, D is NOT necessarily able to decrypt a number that had been encrypted with E (it usually does, but sometimes it doesn't). I made sure all the values were calculated according to the Wikipedia article. Totient = (P-1)*(Q-1). Modulo = P*Q. E is a random value greater than 1 and less than the totient, and who's GCD is equal to 1. Everything has been calculated to Wikipedia's specs. Yet, I'm not always able to decrypt a number that has been encrypted. It fails about 1 time out of 15 times. Sometimes more, sometimes less. The only thing I can think of is that the Wikipedia article is not complete in listing special conditions in which RSA actually fails, and an encrypted number is unable to be decrypted. E and the totient is all I should need to encrypt a number, and D along with the totient is all I should need to decrypt it. I've double checked my program, and can't find any bugs in the code. So I assume something may be missing or inaccurate in the Wikipedia article.
Ok I think I found the problem. It happens when P=Q.
76.104.145.19 (
talk)
09:58, 4 January 2014 (UTC)
I just found the problem still occurs, even when the two random prime numbers are different from each other. I thought I solved it, but that was apparently only one of the conditions that triggered this problem. I'm finding that sometimes encrypted numbers are still not decryptable. And I can't find the cause. None of the numbers are equal to each other. Is it possible that certain mathematical relationships between some of the numbers that are extremely unlikely to occur in 1024bit numbers (but are fatal to the RSA algorithm if they do occur) are highly likely when working with small numbers? Is there something I'm missing, or is there a mistake in the article somewhere? 76.104.145.19 ( talk) 10:14, 4 January 2014 (UTC)
It seems that when E is equal to the modulo this also happens. The result is that the encrypted value is 0. And there's no way to decrypt the value of 0 it seems. And also it seems if for any reason the input number encrypts to the value of 1, then it also is not decryptable. So basically if it encrypts to 0 or 1 then it gets "stuck" at 0 or 1, and can't be decrypted. Of course that makes sense because 0 to the power of anything is 0, and 1 to the power of anything is 1. How an encrypted value could end up being 0 or 1, I don't know. Theoretically that shouldn't happen if everything else in the algorithm is correct. But that's not the only times it has failed. Here's one that makes no sense at all.
P=7
Q=11
Totient=60
Modulo=77
E=37
D=13
input number = 79
encrypted number = 51
result of decrypting encrypted number = 2
Something is VERY wrong here. Any idea what's happening? 76.104.145.19 ( talk) 10:53, 4 January 2014 (UTC)
I finally got it working. Thanks for all the help you guys provided. 76.104.145.19 ( talk) 02:34, 5 January 2014 (UTC)
"Using λ instead of φ(n) allows more choices for d " ? this is not the contrary? λ is smaller than φ(n). In fact with the mod. we have the same computing...if you talk about lcm it's important maybe to compare the key generation by Euler and by Carmichael. For example with Euler way, computation is faster than with Carmichael way. With Carmichael in reseach it s more clear because the Interval is smaller and more clear, we don't have repetitions. -- Mbachkat ( talk) 23:02, 14 May 2014 (UTC)
The Euler theorem says m and n=p*q should be coprime, but in practice, m might be p or qo. What will happen in that case? Jackzhp ( talk) 22:17, 23 June 2014 (UTC)
I am unable to open my picture files. How can I fix this? — Preceding unsigned comment added by Njblondie ( talk • contribs) 22:26, 28 December 2014 (UTC)
The last two attacks (although correct) are uncited. Dues should be given to the people who first noticed and published these attacks in relation to RSA. Informalmunch ( talk) 12:11, 18 February 2015 (UTC)
Rivest, Shamir and Adleman note[2] that Miller has shown that – assuming the Extended Riemann Hypothesis – finding d from n and e is as hard as factoring n into p and q (up to a polynomial time difference).[19]
It means using n = pq and (p-1)(q-1) instead of p and p-1 in ElGamal would be at least as secure as RSA. 109.90.224.162 ( talk) 15:28, 10 October 2015 (UTC)
From article Choose two distinct prime numbers, such as
p = 61 and q = 53
7 times 9 = 61 it is not an example of a prime number
—Actually, 7*9=63. 61 is a prime number. 217.99.252.222 ( talk) 06:00, 26 December 2015 (UTC)
The article references E and N as the public key components, and d as the private key component.
HOWEVER according to the Key Generation paragraph E is chosen as co-prime toφ(n), and d is computed according to the congruence relation of
d ≡ e^-1 (mod φ(n)).
This is not in line with the source "A method for obtaining digital signatures and public-key cryptosystems" by Rivest Shamir and Adleman where section VII describes how to "[...] choose a number d which is relatively prime to φ(n) [...]" and further to "[...] compute e from d and φ(n)[..]"
As a result, both the Key Generation, Example and Code subparagraphs of the Operation section need to be corrected. — Preceding unsigned comment added by FLHeilmann ( talk • contribs) 13:01, 8 February 2016 (UTC)
Fair point, I'll fix the code listing as well sicne I also made changes to that. — Preceding unsigned comment added by FLHeilmann ( talk • contribs) 14:15, 9 March 2016 (UTC)
I'm not sure enough of the correction to make it, but 'd' and 'e' in the example are not being used consistently. The talk page says 'e' can/should be small, and 'd' large, yet the example has 'e'=2753 and 'd'=17. Similarly, it talks about calculating 'e', then immediately says "Let d = 2753". Someone needs to sort this out. — Preceding unsigned comment added by 76.28.205.57 ( talk) 05:47, 22 February 2016 (UTC) Hi! I made an account to correct this. e and d were being mixed up during the Key generation part of the article. I'm going to go through and fix the rest- yes, e should be small, d should be large, and you calculate d from e. look at the sources pls if you don't believe me. — Preceding unsigned comment added by Laudiacay ( talk • contribs) 03:37, 23 February 2016 (UTC)
I was the one who made the changes by swapping d and e. Please check the original RSA paper. While I agree that the example values are not in line with the text, e and d are now swapped again. You need to CHOOSE d AS COPRIME and COMPUTE E As per Rivest and Adleman Paper Section VII-C,VII-D. See my previous talk topic for details.
— Preceding unsigned comment added by FLHeilmann ( talk • contribs) 12:34, 4 March 2016 (UTC)
Uhh..... I don't think that's correct. You choose the co-prime, but that's e, the encryption exponent. e is usually chosen as 65537. You choose a small, constant e for standardization purposes (and security- some formerly common e's are VERY vulnerable (like 3 for example)). d is supposed to be secret- with a small e inversed on your enormous modulo, d will be large and hard to brute-force, which is the entire trapdoor function in a nutshell... d chosen as coprime and e computed simply does not make sense, if d is the secret and e is the public. Please do re-read the paper, it agrees with me. 17:58, 11 April 2016 (UTC) — Preceding unsigned comment added by Laudiacay ( talk • contribs)
FLHeilmann, the current version of the article is correct for encryption. Didn't check signing, but the code, worked examples, key generation/decryption, and basic Alice/Bob examples are all correct. Please don't change the math any further, it's correct now. Laudiacay ( talk) 18:02, 11 April 2016 (UTC)
Note: It appears in the original paper that they did reverse it, but soon after they realized that just picking a giant coprime d is stupidly computationally expensive. The equivalent, picking an e and then calculating d, is waaaay faster to get a big, secure d for current keysizes. So, yes, the original paper does agree with you, but NO secure or fast implementations of key generation today do. Laudiacay ( talk) 18:21, 11 April 2016 (UTC)
If anyone needs to remember the equations used to encrypt/decrypt RSA for a test or something, use the mnemonic SEMEN (c = m^e mod n) MCDONALDS (m = c^d mod n) — Preceding unsigned comment added by 137.63.71.51 ( talk) 21:23, 29 February 2016 (UTC)
IP 66.196.50.51( contributions, talk) put the following text in the article which then got removed by Cluebot:
This page is being linked to by Ransonware to further their argument as to why I need to pay them money to decrypt my files. Maybe a disclaimer here would help, for anyone that might click on the link to read.
I'm putting it here on the talk page which is the proper place for such discussion, without further substantial comment on the subject. Digital Brains ( talk) 14:16, 22 April 2016 (UTC)
The comment(s) below were originally left at Talk:RSA (cryptosystem)/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
I think it is a virus 108.89.134.155 ( talk) 16:33, 18 June 2015 (UTC) |
Last edited at 12:40, 23 June 2015 (UTC). Substituted at 03:46, 30 April 2016 (UTC)
This page contains just a few lines that mention how quantum computers could theoretically crack this algorithm eventually. Should this be expanded, or left to be covered by other articles? — Preceding unsigned comment added by Gluons12 ( talk • contribs) 19:16, 7 May 2016 (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)
I think that most people tend to get lost on the link between the totient function and Chinese remainder theorem, so I decided to put it here.
we have:
(M^(p-1))^(q-1) = aq +1 (Fermat's Little Theorem) a is any integer
The above can be re-ordered and for p we can state as:
(M^(q-1))^(p-1) = bp +1 --b is any integer.
So M^((p-1)(q-1)) -1 is divisible by both p and q
Hence we can conclude that: M^((p-1)(q-1)) -1 = m pq (that is there is some integer m for which LHS is mpq)
Hence the property that M^(totient(pq))= 1 mod pq 07:03, 26 August 2016 (UTC)
— Preceding unsigned comment added by Alokdube ( talk • contribs) 07:00, 26 August 2016 (UTC)
We may choose as the smallest prime greater or equal h(m) with some numerical hash function h of the message m.
84.118.82.226 ( talk) 10:04, 9 February 2018 (UTC)
The following is a paragraph directly from the current (see signature) English language entry:
Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described an equivalent system in an internal document in 1973.[7] However, given the relatively expensive computers needed to implement it at the time, RSA was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification.
Maybe I'm just being a stickler but I would suggest that the second-to-last sentence be reworded somewhat as it seems to imply that GCHQ also called Clifford Cocks' system RSA, which would be preposterous.
I suggest instead: However, given the relatively expensive computers needed to implement it at the time, Cocks' RSA-like system was considered to be mostly a curiosity and - as far as is publicly known - was never deployed.
I know it's not much of a change and normally I'd just edit it and let it be instead of starting a talk section to (hopefully) gather other ideas but since I have a sneaking suspicion either I'm the only person who would notice this incongruity or, possibly, it's not incongruous at all and I'm just being a pedant.
So, if anyone has anything to say about it I'd appreciate feedback on the proposed change. If I don't hear any objections, I intend to make the edit on or after 26 May, 2018 (That's Pacific Standard time zone).
DacodaNelson ( talk) 20:52, 19 May 2018 (UTC) DacodaNelson ( talk) 20:52, 19 May 2018 (UTC)
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)
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: /info/en/?search=RSA_(cryptosystem)#CryptoStrengthOfPQ
and here (old reverted edit cache): https://en.wikipedia.org/?title=RSA_(cryptosystem)&diff=983454044&oldid=983447902#CryptoStrengthOfPQ
But my edit was been reverted: https://en.wikipedia.org/?title=RSA_(cryptosystem)&oldid=983456104
I did discribed all, then put anchor, and add that link on Safe-Primes-definion page:
https://en.wikipedia.org/?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 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)
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)
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)
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)