Talk:RSA (cryptosystem)

What is greatest common denominator?

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 USING MODULI

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?

It's an unfortunate mathematical convention that "mod" applies to everything to the left of it. You could think of it as a very low precedence operator, or like a parenthetical remark, as in "four is equal to eight (if we reduce them both modulo two)". Lunkwill 20:46, 24 November 2005 (UTC)

Even so, if they mean the same thing (which I think Lunkwill is saying), wouldn't it be clearer to write it as suggested? At least the original questioner and I both did not know this "unfortunate fact," and avoiding the confusion in the first place seems preferable to explaining it afterwards. Jackrepenning (talk) 21:47, 14 January 2008 (UTC)

No, it is much better to follow the accepted notation.   Maybe we could add a sentence describing in words what the symbols say to make it more clear, but the RSA page doesn't need to be explaining modular arithmetic. Astgtciv (talk) 11:40, 16 January 2008 (EST) —Preceding unsigned comment added by 143.215.153.95 (talk)

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)

No, this is clearly wrong and only adds to the confusion. One simply has to distinguish between congruence relations (see modular arithmetic) and the modulo operation, which have similar but not equal notation. Congruence relations use an equivalence symbol, e.g. $27\equiv 17{\pmod {10}}$ (Note, the three strokes in $\equiv$). This notation means that both sides reduced modulo 10 are the same (or more precise that the difference is a multiple of 10). The meaning of the '=' sign is never changed and $a=b\mod c$ always denotes a modulo operation that only involves the arguments b and c. Hence, it is wrong to write $7=2\mod 5$ and as the OP notes it would be equally wrong to write $d*e=1\mod (phi)$. But fortunately the RSA article does use correct notation. 85.2.20.48 (talk) 08:19, 16 August 2008 (UTC)

Destroying P and Q

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)

To Featured Article standard?

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)

The most important thing would be a proper treatment of padding and security for encryption and signing - without them, it's positively misleading. ciphergoth 19:54, 2004 Nov 30 (UTC)

Proof

Should we be including a proof of RSA in this section? Revived 22:31, 28 Dec 2004 (UTC)

What do you mean by a "proof of RSA"? Do you mean a proof that decryption "works"? If so, no; TBH I'd rather move away from presenting the idea of a "decryption exponent" at all, in favour of directly using the Chinese Remainder Theorem to do decryption. This would be easier to understand, closer to what is really done in practice, and gets rid of the misleading idea that the public and secret key operations are somehow 'symmetric' when for all practical purposes they aren't. Hopefully it would discourage people from saying misleading things like "signing is encryption with the private key".

If on the other hand you mean a proof that RSA is secure, there is no such proof. — ciphergoth 12:15, 2004 Dec 29 (UTC)

Earlier Work

Pohlig and Hellman

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.

Can we cite a source showing that Rivest, Shamir and Adleman were influenced by (or are believed to have been influenced by) Pohlig and Hellman's work? (RSA was published as an MIT tech report in April 1977, before Pohlig-Hellman's pub in Jan 1978).— Matt Crypto 18:44, 14 Mar 2005 (UTC)

At the NSA

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 p and q be?

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)

p and q should be approximately the same size which means they should be half the size of the modulus you want. Common RSA modulus sizes are 1024 bit, 2048 bit and 4096 bit. So for a 1024 bit modulus you would be looking at 512 bit p and q, for a 2048 bit modulus you would be looking at 1024 bit p and q and for a 4096 bit modulus you would be looking at a 2048 bit p ang q.

768 bit moduluses are known to be feasible to factor (see RSA numbers). AIUI noone has publically demonstrated factoring a 1024 bit modulus yet but they are generally regarded as "at risk" and should not be used for new keys. 2048 bit seems to be the default for new keys at the moment at least in GPG. 4096 bit is typically used by users looking for a larger margin of safety.

A comment on variables

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)

Yeah, I'd prefer the message to be written as m. — Matt Crypto 08:09, 16 August 2005 (UTC)

I second this, and made the change throughout the article. M is now the un-padded plaintext, and m is the padded value to be encrypted. Hope I didn't miss any... Dachshund 17:18, 16 August 2005 (UTC)

What does this mean ?

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

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

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

This is totally confusing.

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

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

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

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

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

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

Question for a reader

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)

Technically, no, since m^ed is only claimed to be congruent, not equal, to m (modulo p and q). But it does seem nonintuitive that RSA would still work for m>p and m>q. Note that taking m^ed mod p and q is a setup for using the Chinese Remainder Theorem to then find the value m for which m^ed is also congruent to m modulo pq. To be honest though, the CRT never seemed especially intuitive to me, so I prefer to think in terms of the generalization of Fermat's Little Theorem which states that m^phi(n) is congruent to m modulo n (for all m relatively prime to n). That way is easier to understand and code, since you just take m^ed(mod n), but using the CRT is faster for computers because it allows the modular exponentiation to happen on the smaller values p and q. Lunkwill 10:54, 1 December 2005 (UTC)

Is RSA based on the discrete logarithm problem?

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)

Please define your acronyms

If you don't mind.

Rivest Shamir Adleman

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)

I'm not sure what you mean. Rivest, Shamir and Adleman are already mentioned: the fourth sentence of the article reads, "The algorithm was described in 1977 by Ron Rivest, Adi Shamir and Len Adleman at MIT; the letters RSA are the initials of their surnames." Their publication is also referenced in the "References" section. — Matt Crypto 18:05, 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.

RSA is not an acronym, it doesn't "stand" for anything - it's just a name derived from the surnames of its creators. Dcoetzee 00:32, 28 January 2010 (UTC)

You just described an acronym.

 "acronym –noun

1. a word formed from the initial letters or groups of letters of words in a set phrase or series of words." Unimaginative Username (talk) 02:50, 22 March 2010 (UTC)

Fermat's little theorem

The article says:

Now, since ed ≡ 1 (mod p-1) and ed ≡ 1 (mod q-1), Fermat's little theorem yields

$m^{ed}\equiv m{\pmod {p}}$

and

$m^{ed}\equiv m{\pmod {q}}$

How does one use Fermat's little theorem to do this? The theorem states that for all integers a and all primes p, $a^{p}\equiv a{\pmod {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 $ed=k(p-1)+1=k'(q-1)+1$, 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)

You started well. Remember that Fermat's little theorem states that m^(p-1)≡1 (mod p), since p is prime. Thus we also have m^k(p-1)≡1^k≡1 (mod p) and thus m^ed≡m^k(p-1)+1≡1^k m≡m (mod p). 129.199.97.157 16:26, 10 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)

No. This is incorrect. Maybe you wanted to say that ed ≡ 1 (mod p-1) implies e.g. m^ed≡m (mod p) since p is prime. 85.2.73.11 15:31, 31 March 2007 (UTC)

"Still" and "Electronic Commerce"

The article says: "RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys."

1. To me the word "still" gives the impression that newer and better algorithms are taking over, but the electronic commerce is still using RSA, because they are a little behind or because they dont need anything better.

1. Yup. AES-256 is the current state of the art, approved by the US Govt for Top Secret material. Plenty of web sites (not just commerce, but e-mail, etc.) have implemented it. Want to have some fun? Visit your various banks, credit card companies, etc., double-click the padlock icon in the browser, and view the encryption protocol used. You'll find that a free webmail service (Yahoo) uses AES-256 (although for sending login credentials only), while a number of *banks* -- who need security the most -- are still using RSA-128. Can't be bothered? Unimaginative Username (talk) 05:32, 10 March 2011 (UTC)

AES-256 is not a public key system; RSA is. They serve different purposes and are not directly comparable.--agr (talk) 12:13, 10 March 2011 (UTC)

My bad. I had RC4-128 on the brain, probably because it bugs me how many "secure" sites still use it instead of AES, *after* agreeing on symmetric keys by using RSA. Thanks for the catch. Unimaginative Username (talk) 05:23, 20 March 2011 (UTC)

1. And what is the electronic commerce protocols? I guess they are talking about https, but this is aimed at every kind of internet use, not only electronic commerce! Velle 12:29, 20 August 2006 (UTC)

1. Yup, again. HTTPS is used for many other kinds of secure connections, not just for online shopping. Unimaginative Username (talk) 05:32, 10 March 2011 (UTC)

AIUI eliptic curve cryptography is considered "better" in that it is belived to be deliver eqivilent security with much smaller keys. Plugwash (talk) 14:07, 27 September 2013 (UTC)

From message to integer, how?

1. When encrypting a message, how is it turned into a number? I guess the message will be divided into blocks, and every block is mapped into a number by some reversible function. Is it?
2. Does the term padding count for the "mapping" Im looking for. I thought the term padding was used for turning a bit string into a longer one, in a reversible way, and not for mapping between messages and numbers.
3. And if im right, about a message being divided into blocks, what is the block size? I guess this is implementation specific, but I cant find any implementations on wikipedia describing this.
4. Will the mapping from message to integer sometimes result in small numbers like 15, or is this easily broken and therefor avoided?

Velle 12:54, 20 August 2006 (UTC)

Remember that text is just an array of bytes which are represented as characters based on their binary value. You can say exactly the same thing for numbers - the 16-bit integer 9656 is represented in an array of bytes as 0x25 0xb8 (I'm ignoring the usual least-significant byte first integer-encoding policy for this example). So, we could technically say that the string 'hello' converts to 0x68 0x65 0x6c 0x6c 0x6f, or 448378203247 in integer format. This isn't the exact method in RSA, but it's the basis on which the "convert text to a number" principle is based. Burningmace 13:10, 27 January 2009 (UTC) —Preceding unsigned comment added by Burningmace (talk • contribs)

Key size

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)

The key size is the length in bits of the modulus pq. Standardised sizes are 2^9 through 2^14 bits (512, 1024, 2048, 4096, 8192, 16384) but in reality any arbitrary number of bits can be used. Try using 'openssl rsagen -out private_key.pem <key_length>' with different values of key length - the lowest supported is 32 bits and the highest is 2147483646. Obviously generating such inordinately sized key is going to take a few million years on your average supercomputer. Burningmace 12:58, 27 January 2009 (UTC) —Preceding unsigned comment added by Burningmace (talk • contribs)

e<phi(n) is not necessary

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)

Notation

We should clearly distinguish between modular reduction and congruence relations. I.e. $c=m^{e}{\bmod {n}}\,$ denotes a modular reduction. Here mod is a function. The result of $m^{e}{\bmod {n}}\,$ is an integer in the range $0..n-1$. On the other hand $m^{ed}\equiv m{\pmod {n}}$ 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=m^e(mod n). 212.254.78.1 10:09, 15 October 2006 (UTC)

Norbert Wiener

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)

Michael J. Wiener "Cryptanalysis of Short RSA Secret Exponents", IEEE Transactions on Information Theory, vol. 36, no. 3, 1990, pp. 553-558. Also presented at Eurocrypt ’89, Houthalen, Belgium, April 1989.

Rendering glitch?

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

Strange. I see it too; in fact I see it in every block enclosed by <math> tags. Like "p=61- and q=53-". It is present in the page's source (the HTML source, not the pre-HTML source in the wiki). I guess it's a (new) bug with Mediawiki's math rendering... it wasn't there earlier, AFAIR. I don't see it in the bigger blocks that have been rendered as images (but obviously).

To clarify: when I set my "math" options (in "my preferences", available at the top right to logged in users) to "MathML if possible", I see these extra "-"s everywhere (as above). When I set it to "Always render PNG" or to "Leave it as TeX", I see it nowhere (obviously). When I set it to anyting else, I see it in only the place User:IvanAndreevich mentioned above. --Shreevatsa 07:59, 28 October 2006 (UTC)

Unusable messages

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)

Yes, it is. --thematrixeatsyou 10:10, 28 August 2007 (UTC)

Non-article question about RSA

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)

I don't think you're supposed to pick a predetermined value of e, but rather choose it after you have your modulus. If you insist on doing it this way, then you'll have to reject values for P and Q that are congruent to 1 mod e. Ntsimp 20:27, 1 March 2007 (UTC)

Many implementations (e.g. OpenSSL, Java JCE, Microsoft Capi etc.) let the user fix the public exponent e and simply generate P and Q such that P-1 and Q-1 are relatively prime to e. Similarly the digital signature standard (FIPS PUB 186-3) selects e first and then generates P and Q. We might even consider to change the RSA article accordingly. 85.2.66.205 01:02, 2 March 2007 (UTC)

Defacement

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))

All better. Goodnightmush 02:42, 6 March 2007 (UTC)

RSA without padding

I'm removing the following paragraph:

If a padding method is not used, then $m\,<\min(p,q)\,$ is better. if a value $m\,>\min(p,q)\,$ is used, then for some combinations of $e\,$ and $\phi (n)\,$ you will get $m=c\,$ for some values of $m\,$. In the working example below, this happens for m=477 and 560 and others. Usually, this is no problem since $p,q$ is larger than any $m\,$ value.

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:

When $m$ is between $\min(p,q)$ and $n$, then for some combinations of $e$ and $\phi (n)$ you will get $m=c$ for some values of $m$. In the working example above, this happens for the given $e,d$ and $m=477$ or $m=560$ among others. This can confuse beginners trying to understand the basic algorithm. It can be avoided using padding.

First, the coincidence $m=c=m^{e}(modn)$ has nothing to do with the size of $m$. In particular it can happen for $m<\min(p,q)$. An example is $n=73*97;e=17$ and $m=22$ or $m=27$. Cases where $m=c$ become rare with large $n$. There are only $(\gcd(e-1,p-1)+1)(\gcd(e-1,q-1)+1)$ such messages. Paddings schemes do not prevent these unlikely cases. $m=c$ can happen even with padding, but that is just very unlikely. 85.2.41.56 12:14, 14 April 2007 (UTC)

RSA implementation of educational purposes

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)

How to choose the two prime numbers P and Q?

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.

The article already contains a link to probabilistic primality tests, which includes the most commonly used algorithms for RSA key generation. 85.2.125.143 11:56, 10 June 2007 (UTC)

Communists attack America's wallet via RSA-breaking

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)

Why don't we think logically and blame the people who put the back door in their product and secured it with weak encryption? --Ray andrew 17:57, 24 June 2007 (UTC)

RSA for general encryption

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)

Something I should note that with a small key I made (pq = 8633, e = 83 ), from 2 to 8632 inclusively, there were 7 values which encoded to themselves, and 216 which decoced with the public key. Also, if you have an encoded byte, you can re-encode it 39 times and you will return to the original value. My advice: only use RSA for fun. Like sending a message to me with that key I supplied ;D --thematrixeatsyou 10:08, 28 August 2007 (UTC)

This is known as a cycling attack. Such attacks are long known, have been well analyzed. They are unlikely to succeed. 24.228.51.109 21:06, 28 August 2007 (UTC)

Easy Decryption???

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)

The main reason why this does not work are the padding schemes. These padding schemes generally randomize the message. E.g. to encrypt a message M the popular PKCS #1 v1.5 standard first generates a new message of the form m = 00 01 PS 00 M, where PS is a randomly chosen padding string of 8 or more bytes. Then m is converted into a single large integer which is encrypted with RSA. Hence if an attacker tries to find out whether a message M was sent by encrypting M he would also have to guess the random padding string PS correctly. More reasons for using message padding are described in the section on padding schemes. 85.2.46.162 (talk) 12:20, 26 December 2007 (UTC)

RSA messages are not encrypted character-by-character - it's typically used to encrypt secret keys as a single complete message. Your scheme would at best work for single-character messages, and the padding schemes still defeat it. Dcoetzee 18:58, 27 December 2007 (UTC)

Create a database of all known primes

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)

When creating a new RSA key one does not use published primes. Rather one finds two random primes, e.g. by first generating random numbers of the approriate size and testing them for primality. These primes are kept secret. Thus a list of published primes does not help to break RSA keys. The prime number theorem gives us an approximation on the number of primes smaller than a given bound. This theorem tells us that there are far too many primes for typical RSA key sizes to be listed all in a database. E.g. the number of 512 bit primes is larger than 10¹⁵¹. Trying to factor an integer by dividing it by potential factors is known as trial division. Because of the size of the RSA keys this method is infeasible. Much better integer factorisation methods exist. 85.2.6.86 (talk) 06:24, 19 March 2008 (UTC)

Can you post a simple algorithim (say written in java) that can genegerate 2048 bit random primes? it would take too long for instantly generating random primes for online transaction 75.87.86.76 (talk) 08:14, 19 March 2008 (UTC)

In java the method java.math.BigInteger.probablePrime generates primes reasonably fast. 85.2.69.178 (talk) 06:16, 20 March 2008 (UTC)

Yes, the Miller-Rabin algorithm can test a random 2048-bit number for primality quickly, and a random 2048-bit number has a roughly 1 in 1420 chance of being prime. More importantly, this is actually how cryptography systems work in practice. Dcoetzee 03:25, 22 June 2008 (UTC)

Function changes?

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) 

Yup. Correct is to use \varphi not \phi. 85.2.104.180 (talk) 19:55, 21 May 2008 (UTC)

RSA on T-shirts

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)

I've restored the section as even though the use of RSA-in-Perl was something of a MacGuffin, the three-line RSA script and the T-shirts it was printed on did play a major role in the debate as a protest of the government's treatment of Zimmerman et al. It could just as easily have been Bruce Schneier's Solitaire/Pontifex algorithm or some other strong encrypt, but it happened to be RSA, and therefore the section is highly relevant as a description of a watershed event in the ongoing debate over online civil rights. It's like having a history of the Civil War without talking about John Brown, Nat Turner or Harriet Tubman -- they may not have had anything directly to do with the war, but their lives and actions as opponents of slavery are a critical part of the context of the history of the Southern secession and the ensuing war. Haikupoet (talk) 18:44, 8 July 2008 (UTC)

What do you think of making more general comments about the legal restrictions placed on RSA? RSA as an internet meme could be the PGP incident or something. We could add a few things about Bernstein and Zimmermann, if applicable. My hope is a more professional look. Skippydo (talk) 20:37, 8 July 2008 (UTC)

Rephrase it however you wish; just make sure the coverage remains, as it's a fairly important thing. I will point out, however, that though deadly serious, the RSA-in-Perl protest does in fact qualify as an Internet meme by the currently accepted definition. RSA and the ITAR controversy would be another good phrasing. Haikupoet (talk) 02:11, 9 July 2008 (UTC)

Ok, let's try to be at least somewhat serious and do some simple fact checking. Much of the section just simply contradicts common sense and hence should either be removed or referenced. The first sentence reads like the U.S. government was more interested to restrict the export of Perl snippets than the export of fully implemented cryptographic schemes such as PGP. Why would the gouvernment want to do that? Can you give a reference? The next sentence claims that the government treated cryptography as munitions. All I can find is that cryptography was treated as export restricted technology with primarily military use and hence the same restrictions as for munition would apply. Just because the two things were treated the same does not mean the government claimed cryptography is munition. Next, the section implies that people in black t-shirts were responsible for easing the U.S. export restriction. This is in contradiction with the article export of cryptography, which claims more bluntly that American companies claimed the export restrictions would hurt their business. Given these two potential explanations, I really find it difficult that it was the t-shirts that made an impact unless of course you can give a reliable reference. 85.0.101.98 (talk) 05:41, 9 August 2008 (UTC)

Are d and e interchangeable?

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)

Yes. Or to put it differently, whereas the current steps say to choose e and then compute d, you are free to choose d and then compute e instead. Dcoetzee 22:54, 21 August 2008 (UTC)

No. Public and secret exponents are not exchangeable. Encryption and decryption still works when d and e are exchanged. However, doing so may allow an attacker to break the key. This is because the conditions that d and e must satisfy are different. e can be small but not d. E.g., e=65537 is very common. On the other hand it must not be possible to guess d or compute d from information how it was selected. In particular, d must not be small, because of the attack by Wiener. There are other attacks that can break if d is chosen in a specific way. Standards such as PKCS #1 or FIPS PUB 186-3 specifically require that e is chosen first and d is computed from e, p and q. In fact appendix B.3.1 in FIPS PUB 186-3 requires that e is at least 160 bits shorter than the public modulus. This requirement was included into the standard so that it is possible to protect against a user exchanging d and e by accident. 85.2.92.41 (talk) 07:39, 23 August 2008 (UTC)

I came here looking for this specific information and I'm grateful for your clear and concise explanation. However, shouldn't this text be in the main article rather than hidden in the discussions? Mandolamus (talk) 09:47, 19 April 2011 (UTC)

Perhaps you're right, this could go in the article, but it should be worded carefully. As far as the core algorithm and its underlying mathematics are concerned, d and e are completely interchangeable, as are p and q for that matter. However, in practice you do need to keep track of which is the public exponent and which is the private one because, as mentioned above, there are implications to the resulting strength of security. --Skysmurf (talk) 13:47, 19 April 2011 (UTC)

Real standards specify lambda(n), not phi(n)

Real standards for RSA, such as PKCS #1 or IEEE P1363, specify that $ed\equiv 1{\pmod {\lambda (n)}}$, where $\lambda (n)=\mathrm {lcm} (p-1,q-1)$. Note that $\lambda (n)=\phi (n)/\gcd(p-1,q-1)$, 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 $\mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z}$. Therefore $x^{k}\equiv x{\pmod {n}}$ if and only if $x^{k}\equiv x{\pmod {p}}$ and $x^{k}\equiv x{\pmod {q}}$. Fermat's Little Theorem tells us that the latter happens if and only if $k\equiv 1{\pmod {p-1}}$ and $k\equiv 1{\pmod {q-1}}$. Hence $k-1$ must be a multiple of both $p-1$ and $q-1$, i.e., a multiple of $\lambda (n)=\mathrm {lcm} (p-1,q-1)$ 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)

encryption preconditions wrong

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)

Keep in mind that the security of the protocol requires that factoring is difficult. If you discover a message that shares a nontrivial factor with n, you have factored n. Since we are assuming factoring is infeasible (for the security of the algorithm), we are assuming that finding such a message is infeasible. Removing the check makes the algorithm more efficient.

In summery, we are left to chose between a faster algorithm, or a check for something that is infeasible. Also note that using the heuristic infeasible=impossible, the choice is obvious.

I would suggest we note that for the algorithm to work, m must be relatively prime to n but in practice, this issue does not arise. Skippydo (talk) 17:10, 18 February 2009 (UTC)

agreed

141.24.45.251 (talk) 18:09, 18 February 2009 (UTC)

Correctness of RSA requires that $m^{ed}{\bmod {n}}=m$ and this holds for all $0\leq m<n$. At some point this article contained a proof of correctness that included the m that were not relatively prime to n, but that proof got replaced by the current one, which is simpler but does not cover all values for m. Still, RSA does correctly work for all m and as Skippydo notices those special cases happen with extremely small probability anyway. Standards don't include any requirements that gcd(n,m) must be checked. Nor is this done in any implementation of RSA that I'm aware of. 92.106.74.178 (talk) 19:15, 18 February 2009 (UTC)

"private key" != "secret key"

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)

You are of course right, using two terms that refer to the same thing is confusing. Though, authors sometimes use the the terms "public key" and "secret key" for the two keys in a key pair of a public key cryptosystem, for example when they also use symbols such as ${\rm {PK}}_{A},{\rm {SK}}_{A}$ to refer to the two keys. 62.203.40.35 (talk) 21:41, 14 March 2009 (UTC)

I don't see the problem. Please give an example where the meaning of private key is distinct from secret key. What is secret-key cryptography? Skippydo (talk) 21:59, 14 March 2009 (UTC)

The problem was that the article used both "secret key" and "private key" at the same time. They mean the same thing in public key crypto, but it is still less confusing just to use one of the terms consistently in the article. 62.203.40.35 (talk) 22:28, 14 March 2009 (UTC)

Question on example

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

Yup, it should be 855. Thanks 62.203.4.103 (talk) 17:05, 18 May 2009 (UTC)

What happened to the Proof? !!

(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)

The proof using Fermats little theorem and the Chinese remainder theorem was removed in Dezember 2008. Comparing the two versions, I'd agree that the old proof based on Fermat is clearer than the current proof that is based on Eulers theorem. Eulers theorem doesn't cover the cases where the message is not relatively prime to the modulus. Hence it is not a complete proof 83.78.70.161 (talk) 01:01, 11 December 2009 (UTC)

I have added an intuative proof, largely based on http://www.di-mgt.com.au/rsa_theory.pdf. No need for Totient functions. I have left the original for the mathematically minded, although there is a gap about why phi(pq) = (p-1)(q-1). I realize that there are many mathematician on wikipedia who delite in articles that only they can understand. But this was written for the rest of us. Tuntable (talk) 06:29, 27 January 2010 (UTC)

I also added a note about why the obvious attack of finding a different decrypter

$ef\equiv 1{\pmod {n-1}}$

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)

The problem with your "explanation" is that it simply is not correct. If n is not prime then this does not imply that $a^{n-1}\not \equiv 1{\pmod {n}}$. [Charmicael numbers] (e.g. n=561) are counter examples. Just because you call a section "intuitive" does not mean you can invent stuff on the spot. Those numbers are rare enough not to be a threat to RSA. There is no need to disprove attacks that are nobody is seriously suggesting. If we write a section about attacks that don't work, then we should include stuff that has been proposed and analyzed. For example "cycling attacks" come to my mind. On a separate note, there is a simple proof that computing d from e and n is as difficult as factoring. However, no such proof is mentioned in the section "Security" as you claim. Thus, please either cite a reference or give a proof. Don't just remove the call for citation. 62.203.85.79 (talk) 06:59, 29 January 2010 (UTC)

I still prefer the former proof in the section "Decryption", which was removed in December 2008 to the current proof in the section "Intuitive Derivation". The former proof was somewhat better organized and better formalized (i.e. it used whole sentences rather than thought snippets). I'll try to clean up the current proof a little, but I wouldn't mind if it gets replaced again with the old version. 62.203.85.79 (talk) 07:24, 29 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)

section on patents needs fact checking

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)

• Never mind, it turned out that the term of patent was 17 years at the time. --Ixfd64 (talk) 03:29, 25 November 2009 (UTC)

Verification

• Choosing e having a short addition chain results in more efficient encryption.
• In practice, e is usually 216+1.

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)

I've cleaned it up a bit. Hopefully, you'll find it acceptable. Skippydo (talk) 18:04, 23 February 2010 (UTC)

1024-bit broken

http://techie-buzz.com/tech-news/1024-bit-rsa-cracked.html --149.4.115.3 (talk) 22:51, 8 March 2010 (UTC)

The title of this article is misleading. 1024-bit RSA wasn't cracked. The researchers just claim to have successfully implemented a fault based attack. They changed the valtage of the server doing RSA so long until it started making errors, then manage to derived the RSA private key from the faulty results. Since the concept of this attack is already known, it is unclear what exactly is the contribution. Hence as usual newpaper articles are a weak source. Having access to the conference paper would be much more helpful. 92.107.157.23 (talk) 07:52, 9 March 2010 (UTC)

Link to the paper http://www.eecs.umich.edu/~valeria/research/publications/DATE10RSA.pdf —Preceding unsigned comment added by 84.209.15.52 (talk) 07:41, 10 March 2010 (UTC)

Equivalence to factoring

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)

ASCII Error

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?

The ASCII code of 'A' is 65 (or 41 in hexadecimal notation). But this is irrelevant here. RSA is not used to encrypt single characters and in fact it is generally not even used to encrypt text. Rather one encrypts for example a AES key, which is then used to encrypt the text. Hence the "worked example" is contrieved an may even mislead readers to apply RSA incorrectly. 85.2.166.21 (talk) 17:58, 13 September 2010 (UTC)

Only the private key holder can know the value of P and Q separately - please make this clear for didactic purposes.

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)

Right now, the wikipedia article follows the notation used in the original paper by Rivest, Shamir and Adleman. I.e. they used (n,e) as the public key and (n,d) as the private key. (n,e) is sufficient to encrypt and (n,d) is sufficient to decrypt. There is no need to use the factors of n. For didactic purposes the primary question should be, how hard it is to invert RSA. The fact that finding (n,d) is equivalent to factoring n is then only a consequence of exploring one way to break RSA, but it is not the primary question. Therefore, I think, it is quite adequate how the wikipedia article presents basic RSA.85.3.176.55 (talk) 21:24, 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)

What makes you think the private key should store original values of P and Q (instead of N which is P*Q)? Did you read this in some college cryptography textbook, or other source? If so, what is your source? If you have a source for this idea, please state it in your post here. 76.104.145.19 (talk) 08:04, 4 January 2014 (UTC)

When are primes created in browser?

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)

Or is it so, that server sends its public key to client, and client encrypts symmetric key with that, so client's browser does not need to create primes?--Teveten (talk) 15:11, 5 October 2010 (UTC)

The details depend on the cipher suite but AIUI there are generally two approaches, the first is for the client to generate the secret key and encrypt it with the server's public key (which it can obtain from the certificate). This is simple but has the significant disadvantage that anyone who can steal the server's key can passively decrypt the session and they can do so retroactively.

The other approach is to use some key agreement algorithm like diffe-hellmen to agree the secret key and use RSA merely to verify that you are agreeing a key with the correct server.

As you say generating a new RSA key for every session isn't really practical.

See the perfect forward secrecy article for more. 151.229.191.223 (talk) 01:50, 22 June 2014 (UTC)

Concise proof using Euler's Theorem

In the end of the proof there is stated:

The last congruence directly follows from Euler's theorem when m is relatively prime to n.

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)

Disambiguation

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)

As there have been no objections, I have removed it. Feezo (send a signal | watch the sky) 08:31, 22 May 2011 (UTC)

I object - RSA is an extremely common acronym for Republic of South Africa in the RSA. For example South African stamps have RSA on them as the name of the country. — Preceding unsigned comment added by 78.147.7.7 (talk) 01:29, 9 June 2011 (UTC)

Possibly breakable by NSA?

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)

bradass87 doesn't seem to know the difference between DES and tripleDES, otherwise he wouldn't claim that both can be brute forced in minutes. bradass87 doesn't seems to understand that a successful fault-based attack does not mean 1024-bit keys are broken, and generally his claims are not reputable. For a recent estimate how much it would take to break a 2048-bit RSA keys, see for example the paper http://eprint.iacr.org/2011/254.pdf which was written by the real experts using real arguments and comes to the conclusion that 2048-bit RSA keys are way out of reach. 83.79.23.51 (talk) 19:21, 26 July 2011 (UTC)

...The same key should never be used for both encryption and signing. ...

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)

There is a design principle saying that generally the same key (for any cryptographic algorithm not just RSA) should not be used for multiple encryption modes. NIST has this explicitely in one of its standards (though I can't find a reference at the moment). One reason for not using a cryptographic key for multiple encryption modes is that the analysis of encryption modes are done under the assumption that the key is only used for one particular encryption mode. I.e., RSA-OAEP does have a nice security reduction. But the proofs can no longer be applied, if the same key is also used for some signature scheme (or even another encryption mode). Hence using an RSA key for both encryption and signature means that you have to give up much of the scientific progress on RSA an go back to a situation, where your only argument for security is the lack of known attacks.

Of course, the text in the article may need some clarification and better citation. Generally for recommendations like this one, we should not rely on a web page and rather refer to a concrete cryptographic standard or a reviewed paper. 85.3.68.148 (talk) 08:26, 31 July 2011 (UTC)

First for Key Exchange

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)

Page Move

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)

I would suggest renaming this article RSA algorithm instead of the current RSA (algorithm). Per WP:NAME, a natural disambiguation is preferred over parenthetical terms.--agr (talk) 22:09, 21 February 2012 (UTC)

Faulty Key Generation additions

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)

md5

what is md5 in padding — Preceding unsigned comment added by 220.225.106.177 (talk) 08:13, 6 March 2012 (UTC)

A paradox!

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)

We can find d from n and e but not easily. Finding φ(n) is equivalent to factoring n, which is difficult, in general. Skippydo (talk) 15:21, 14 July 2012 (UTC)

Smallest Keys

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)

Missing text?

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)

should be better now. --MarioS (talk) 11:11, 26 September 2012 (UTC)

Valid range for m

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)

You are presumably referring to my revert of your edit, which you should mention so that editors generally know what you are referring to. I infer that you are concerned that the encryption might not be secure with these values (as well as with n – 1, as you pointed out in your edit summary). These cases could be treated as a weak encryption, but not out of the valid range of the algorithm, since it functions correctly for all values (including these). However, the literature generally makes no mention of an exclusion such as you are motivating, and the primary requirement is that the literature be used as reference.

However, these values are in fact not weak from a security perspective, counterintuitive as this may seem. For an attacker to exploit these values, she must implement a comparison algorithm on the ciphertext. Since the attacker can derive any number of plaintext–ciphertext pairs given only the public key, limited only by her computational and storage capacity, any message value is exactly as weak as the ones that you have chosen to classify as "invalid", because such a comparison algorithm would work equally well for any other value in the attacker's database. — Quondum 14:49, 25 July 2013 (UTC)

polynomial-time method for factoring large integers may have been discovered

Primary link to article:

http://deepthought.newsvine.com/_news/2013/08/15/20030719-has-rsa-encryption-been-broken-need-a-second-opinion-on-this-math

Yet to be confirmed...but looks good. — Preceding unsigned comment added by 80.47.125.210 (talk) 05:35, 15 August 2013 (UTC)

Please don't waste your time on this. Wolfram Alpha automatically determines and displays the prime factorization of relatively small numbers. — Quondum 02:17, 16 August 2013 (UTC)

Removed HE-RSA

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.

Message equaling ciphertext

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 $m^{e-1}{\text{ (mod }}p{\text{)}}=1$ or $m^{e-1}{\text{ (mod }}q{\text{)}}=1$ 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)

Indeed it is; I was being sloppy and did not think through the detail closely enough. However, the inclusion of this point seems to me to be spurious; in particular, it does not have cryptographic significance and I strongly doubt whether you'll find any notable source mentioning it. If whole books on the subject do not mention it, there is little case for including it in WP. You don't find mention of approximately one c=m pair expected for every use of AES (or any other block cipher) for any give key, which is a far higher probability than for the typical RSA operation. Even if it were to be included, it is in an inappropriate section. Try to add quality, not oddments. —Quondum 01:59, 29 November 2013 (UTC)

What about when the Totient of n is 1 or 2 ?

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)

The security of RSA is based on the difficulty to factor n = pq. This implies that none of p, q and |p-q| is small. In practice, the random prime generator is designed to produce p and q in some predefined range. For example, for a n with 600 digits, one choose p with, say, 200 digits and q with 400 digits. Thus small primes like 2 and 3 are never generated. D.Lazard (talk) 09:42, 4 January 2014 (UTC)

Any unusual conditions when RSA does not work?

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)

That one is in the article: Choose two distinct prime numbers p and q. Digital Brains (talk) 10:10, 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)

If you give an example of all the numbers where your decryption goes wrong, someone might be able to pinpoint where it goes wrong. Please do give all of p, q, d, e, m, and c. And if I just now forgot an important one, include that one as well ;). Digital Brains (talk) 10:18, 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)

• Choose an integer e such that 1 < e < φ(n), so e can not be as large as the modulo which is larger than φ(n)
• He first turns M into an integer m, such that 0 ≤ m < n, so your example m = 79 is not valid. In fact, 79 ≡ 2 (mod 77), so your message is 2, and it decrypts fine.

Since everything is done either modulo φ(n) or modulo n, numbers in general can't be bigger than that because they'll get "truncated". Digital Brains (talk) 11:12, 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)

key generation

"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)

what if m=p or m=q?

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)

this is answered in the section titled "Proof using Fermat's little theorem" Jackzhp (talk) 22:30, 23 June 2014 (UTC)

open a file

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)

Attacks against plain RSA citations

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)

ElGamal is better

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)

Prime numbers

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)

Key Generation Section is not in line with the orignal paper by Rivest Shamir and Adleman

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)

Sure, this could be mentioned in a comment somewhere. However, more important is to describe RSA as it is used today and how it is standardized and implemented. For example the PKCS #1 standard chooses e first, then computes d. This allows to choose a small e. Most RSA keys used today use e=65537. Setting e to a small value is not possible if d is chosen first. 176.127.147.245 (talk) 07:05, 8 March 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)

d and e in example are mislabeled and misused

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)

I was already typing a comment, but I see you have corrected yourself. My gut feeling is that the reason that a properly chosen constant e has small Hamming weight and length is a much more important reason than a bit of computation at key generation time. Because a good e pays off every time you encrypt or check a signature, rather than just at key generation time. To get more on topic of the article page, the current version seems fine: it mentions that the original paper did it differently, but we do it like this now. I did only scan through the article, I didn't mull over it endlessly like some people apparently did :) Digital Brains (talk) 18:31, 11 April 2016 (UTC)

Mnemonic for the equations

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)

Yes, that is exactly the sort of mnemonics we need to show that computer science is a mature science and not some plaything for pubescent boys... Sigh... Digital Brains (talk) 18:36, 11 April 2016 (UTC)

Ransomware edit

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)

Assessment comment

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)

Should quantum computers be mentioned more?

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)

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

Hello,

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

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

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

Indeed, we are searching for a

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

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

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

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

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

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

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

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

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

So, even the condition

• $e<\phi (n)$

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

Therefore, I would propose the following conditions :

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

Does it make sense?

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

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

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

Proof for totient function

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)

Hmmmm - why we don't choose the public exponent e as function of the message m?

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)

Phrasing in pararagraph from History section misleading?

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)

Totient or LCM !?

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

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

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

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

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

Safe Primes, in RSA Key Generation

I did put the anchor for this note, here: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#CryptoStrengthOfPQ

and here (old reverted edit cache): https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&diff=983454044&oldid=983447902#CryptoStrengthOfPQ

But my edit was been reverted: https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=983456104

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

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

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

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

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

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

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

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

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

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

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

problem, which was been described in previous version.

But, look at this:

p, q - primes;

n = p*q;

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

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

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

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

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

λ(n) = phi(n)/g

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

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

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

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

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

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

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

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

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

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

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

Discuss.

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

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

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

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

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

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

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

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

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

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

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

Bellcore vs CRT

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

Multi-Prime RSA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

RSA(cryptosystem)

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

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