Talk:RSA

From Wikipedia, the free encyclopedia

This is the talk page for discussing improvements to the RSA article.
Please sign and date your posts by typing four tildes (`~~~~`). Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Ask questions, get answers. This is not a forum for general discussion about the article's subject.	Be polite Assume good faith No personal attacks Be welcoming	Article policies No original research Neutral point of view Verifiability
Archives: 1

This article has been reviewed by the Version 1.0 Editorial Team.

This article does not currently meet the quality requirements for the Version 0.7 offline release. It is not currently being considered for later releases, as outlined in the notes left here. Please help improve this article if you can, and renominate after improvements have been made.

Additional information:
B	This article has been rated as B-Class on the assessment scale.
Mid	This article has been rated as Mid-Importance on the assessment scale.
	The following comments have been left for this page: I have failed this article for Wikipedia 0.7 because I have rated it as a B-class article of mid importance. To be included in Wikipedia 0.7 I recommend that this article gets at least 1 useful illustration and be promoted to GA status so that it may be included. Funpika 21:56, 5 June 2007 (UTC) (edit)

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on 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. It should be reviewed whether a 256 bit key can be factored in hours on a personal computer. I can factor them in minutes on my (somewhat old) machine.

Archives
1

1 EQUATIONS USING MODULI
2 Destroying P and Q
3 To Featured Article standard?
4 Proof
5 Earlier Work
6 a question
7 A comment on variables
8 What does this mean ?
9 Question for a reader
10 Is RSA based on the discrete logarithm problem?
11 Please define your acronyms
12 Rivest Shamir Adleman
13 Fermat's little theorem
14 "Still" and "Electronic Commerce"
15 From message to integer, how?
16 Key size
17 e<phi(n) is not necessary
18 Notation
19 Norbert Wiener
20 Rendering glitch?
21 Unusable messages
22 Non-article question about RSA
23 defacement
24 RSA without padding
25 RSA implementation of educational purposes
26 How to choose the two prime numbers P and Q?
27 Communists attack America's wallet via RSA-breaking
28 RSA for general encryption
29 Easy Decryption???
30 Create a database of all known primes
31 Function changes?
32 Decrypting Messages

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

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.

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

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)

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

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

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

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

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

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

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 (m o d n)$ 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)

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

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

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

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

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

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

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

[edit] Decrypting Messages

Is it possible at all to encrypt a message by knowing the mod and the public key? Or do you have to know the private key in order to encrypt it. I'm sorry if it's already been answered in the article, but I didn't understand it entirely. —Preceding unsigned comment added by 58.175.171.238 (talk) 07:54, 23 May 2008 (UTC)

With the public key, anyone can encrypt. Only the holder of the private key can decrypt.Skippydo (talk) 21:28, 23 May 2008 (UTC)

I have a program that has the mod and the public key. I have another program that only has the private key. I DO NOT know the private key. Is it possible to use the first to encrypt the message "ABCDEF" and achieve the same result with the second application? SO if (for example) App. 1 generates "AABB" using the public key, would App. 2 also generate "AABB"? Or would it be completely different? 58.175.171.238 (talk) 05:53, 24 May 2008 (UTC)

Let us say, your public key is e and your modulus is N. Each bit string (such as AABB) is assigned some integer, let's call it x. You compute x^e modulo N and sent it as the encrypted message. Only the holder of the private key can determine x. Using x, one can determine the actual message.

If the private key is called d, we have some theory that says for all integers x, (x^e)^d=x.

To turn some text AABB into an integer, we can just take the bit representation of the message as it appears in memory and call that our integer.

Hope this helps!Skippydo (talk) 02:48, 26 May 2008 (UTC)

So will the string encrypted using the private key be the same as the string encrypted using the public key? Or not? What I am trying to do is encrypt a string using a public key (I do not know the private key) and have it be the same as the string encrypted using the private key, and I do know the modulus. (On a side note, does an encrypted string necessarily have to be the same length as the unencrypted string?)58.175.171.238 (talk) 08:06, 26 May 2008 (UTC)

The public key can be generated using the private key. So, yes, they do generated the same encrypted message. However, only the private key can be used to decrypt.

The encrypted string needs to be at least as long as the original, due to some results from information theory. It is assumed that the message is some integer less than N (the modulus), so usually we restrict ourselves to messages of at most log N bits (or split up a long message into chunks). The encrypted messages has at most log N bits. Skippydo (talk) —Preceding comment was added at 18:53, 26 May 2008 (UTC)

Ok Thanks! So the encrypted string must be at least as long as the decrypted string, but does it neccesarily have to be the same length? And will shorter keys produce shorter encrypted strings? So if I encrypt "A" with the private key "ABC", will the result be longer if I use the private key "ABCD"?58.175.171.238 (talk) 06:36, 27 May 2008 (UTC)

In this case, it is the same length. The value of N determines the length of the encrypted/original messages. As a matter of trivia, the public key in RSA is usually always taken to be 3. This seems strange, but changing the modulus allows us to maintain security. The private key one chooses does not effect the length of the encrypted messages, only the modulus N.

I misspoke eariler when I told you the public key can be obtained from the private key. In RSA the public key is e, the private key d. To obtain them, we require the prime factors of N=pq. We do not need p and q to decrypt; we only need d to decrypt. But to get d in the first place, we need to factor N. Sorry if this caused any confusion. Skippydo (talk) 16:56, 27 May 2008 (UTC)

I already have the public key and the modulus, so what I truly want to know is:

1. Which key affects the length of the outcome.

2. If you can encrypt a message using the public key (Which in this case is EF) and receive the same outcome with the private key (which I do not know).

Thanks!210.84.28.66 (talk) 21:21, 27 May 2008 (UTC)