More questions about RSA cryptography?

Question

First of all, I have been trying to wrap my mind around why this algorithm works for several years -- with each website and book I read, more understanding is often gained. I feel like I am so close to connecting all the dots, but there is still a disconnect. I can work the RSA algorithm out by hand with artificially small numbers and see that it works, but I'm trying to understand *why* it works. I appreciate anyone who takes the time to share their insight (hopefully in simple terms with an example).

Here is what I understand:
1. Choose two distinct prime numbers, P and Q
2. Calculate the modulus as N = P * Q
3. Calculate the Euler Totient as phi(P,Q)=(P-1)(Q-1). PKCS#1 directs using the lambda(P,Q)=lcm(P-1,Q-1) where lcm denotes least common multiple, instead of the Euler Totient, but I have recently learned these values have the same multiplicative order (e.g. phi(P,Q) = k*lambda(P,Q) for some value k) so it doesn't really matter which one is used. For this description I will use lambda.

4. Choose a value for the encryption exponent, e, such that gcd( lambda(P,Q), e) = 1 (co-prime) and 1 < e < lambda(P,Q)

5. Calculate the decryption exponent d, such that e * d = 1 mod lambda(P,Q)

6. To encrypt a message m to ciphertext c, perform c = m^e mod N
7. To decrypt a message c to plain text m, perform m = c^d mod N

Up to this point I am fine with everything. I have tried many examples and it always works. Now I am trying to convince myself WHY this works.

Someone recently explained it like this:

m = c^d = (m^e)^d = m^(ed) mod N
That makes sense to me.

From part 5, above, we have that ed = 1 mod lambda(PQ), so we can re-write the above eq as:
m^(ed) = m^(1 + k*lambda[P,Q]) mod N
which simplifies to:

(m^1)*(m^lambda[P,Q])^k mod N
which means m^lambda[P,Q] mod N must evaluate to 1....and it does!
But WHY?
Why does m^lambda[P,Q] mod N always evaluate to 1? I'm not a math major so I usually get lost in the proofs or technical descriptions :(

Similarly, what guarantees that m^e mod N is a one-to-one function (e.g. that each value of m will map to a distinct value?) I suspect it has something to do with using prime numbers in the first place...but I haven't connected the dots.

Thanks to anyone that takes the time to enlighten me!

Josh

Answer 1

This document takes you through it nice and slowly. http://www.di-mgt.com.au/rsa_theory.pdf



It starts off by listing all the results about prime numbers, congruences, modulo arithemetic, etc that you need to undeertand the proof. Work your way through those results step by step. If you get stuck, look for websites about number theory to help you get over any problems..



Probably one thing you are missing is "Fermat's little theorem". You will find a proof of that on many number theory web sites. The proof is quite straightforward, the basic idea is that if you are doing arithmetic modulo N, there are only N different possible answers (i.e. the numbers 0 through N-1), so if you repeat the same calculation enough times, two of the answers will have to be the same because you have used up all the different numbers.



This idea is sometimes called the "pigeonhole principle". If you have N pigeonholes and N+1 pigeons, then there must be at least one pigeonhole with two pigeons in it. The basic idea is simple, but the consequences of it can be not-so-simple.



Good luck!

Answer 2

Hi :



here a website



http://en.wikipedia.org/wiki/RSA



http://www.muppetlabs.com/~breadbox/txt/rsa.html



http://www.bing.com/search?q=RSA+cryptography&src=IE-SearchBox



but way it works there are two code keys a public one and a private one



the computer use prime numbers in the the Encryption and Decryption of the above website will help you to better understand it .





the reason why they use prime number is because they are very difficult to break down or factor or find especially when the are in the hundred of digit long



I do know that the inventor of it offered a 100 prize to anyone who could break it and he post the message online and before you go trying it someone all ready beat you to it about three years later someone crack it but it took hundreds of computers and two years of blood sweat and tears to get it



I hope this helps



Ps :

to quote Edgar Allen Poe: there is not a code that can not be devised by the human mind that another human mind can not crack or break.





and to quote another famous codebreaker :



A code does not need to be unbreakable but it does need to be unbreakable, long enough for the information on it to be totally useless to the enemy , for a example: I sent a message in code to my army to attack you at dawn the next day and your code boys couldn't break it until next week . Quess what ? what good was it ?



also read the book "The Codebreakers" by David Kahn - a very good book on the history and uses of codebreaking

Answer 3

that is thoroughly available, and it really works o.ok.. the significant wide-spread public-key cipher, RSA, has an uncomplicated starting up, to boot the reality that the implementations and the arithmetic on the back of them are a lot more effective complicated. In RSA, you in basic terms take a block of plaintext, and deal with it as one significant, particularly huge volume. then you actually improve it to an particularly extreme ability (one with one thousand's of digits), divide it by using ability of a though more effective volume (the modulus), and then take something by using creating use of reality the ciphertext. The exponent used is the encryption key. To decrypt, you in basic terms repeat the operation, yet with a diverse exponent that represents the decryption key. as lengthy by using creating use of reality the modulus, encryption exponent, and decryption exponent have a diverse mathematical relationship to at least one yet another, it really works thoroughly. something it particularly is encrypted with between the keys would properly be decrypted (in basic terms) by using ability of the diverse key. Breaking RSA demands factoring numbers with one thousand's or one thousand's of digits, or taking discrete logarithms of similar numbers. actual now, no individual is familiar with the thanks to attempt this with any overall performance, so RSA is considered look after with a sufficient key length (limitless thousand bits). there are various diverse public-key algorithms. the options were wide-spread for type of 50 years, to boot the reality that they did not substitute into wide-spread outdoors of secret authorities circles till the 1990s or thereabouts.