Talk:RSA

From Wikipedia, the free encyclopedia

Archived discussion from 27th December 2001 – 31st August 2004: Talk:RSA/archive1

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

It is intended that this article be included in WikiReader Cryptography, a WikiReader on the topic of cryptography. Help and comments for improving this article would be especially welcome. A tool for coordinating the editing and review of these articles is the daily article box.

To-do list for RSA:	edit · history · watch · refresh
A rigorous and correct treatment of padding is essential for this article to avoid being misleading. In the paragraph "Security", I think the figure 1999 must be reviewed.

[edit] 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)

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.

[edit] 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)

[edit] 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)

[edit] 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)

[edit] Earlier Work

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)

[edit] a question

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)

[edit] 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)

[edit] What does this mean ?

I think more information is needed about $φ(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)

[edit] 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)

[edit] 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)

[edit] Please define your acronyms

If you don't mind.

[edit] 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.

[edit] 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 $e d = 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)

[edit] "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."

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

[edit] From message to integer, how?

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

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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.

[edit] 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)

Retrieved from "http://en.wikipedia.org../../../r/s/a/Talk%7ERSA_6dda.html"

Categories: To do | To do, priority undefined