I am trying to learn more about the RSA Algorithm. I have researched several pages on Google and have a fairly clear idea of what the algorithm entails — I don’t exactly understand *why* it works, but I believe I understand a good amount as to how one would encrypt/decrypt a message. My question, is how is this algorithm applied in real life? I mean, how does one generate two large primes? SInce there is no known algorithm for factoring the product of two primes it seems that there would also be no known algorithm for generating numbers that are prime? Also, is the arithmetic carried out? Raising a message to a power of significant size isn’t going to work well with a 32 or even 64bit processor. I assume some type of addon library is used to accomodate the larger numbers? How are these implemented? Finally, I understand that these mechanisms already exist and re-inventing the wheel is often dangerous in terms of crypto, but I just want to do it as a learning exercise.
My understanding of RSA algo:

1) Choose 2 large distinct primes p and q
2) Calculate modulus as N = p*q
3) Calculate totient as (p-1)(q-1)
4) Choose e such that 1 < e < (p-1)(q-1) and e is coprime with (p-1)(q-1). [Does this mean e could ever be 2? It seems an odd number would be required for e?]
5) Find d such that ed = 1 mod (p-1)(q-1)
[Is there only 1 d that works or does it matter which solution I choose?? What is an efficient way to calculate this??]

6) c = m^e mod N where m = msg expressed as number … whats an efficient way to raise m to such a large exponent? I realize modular arithmetic bounds this somewhat, but still the calculation could/should be much larger than 32 or 64bit values…
McDonger: Thanks for your response. I guess I’m looking for more detailed information as to how it gets split up and calculated. The symmetric encryption (the key passed via the PKE) isn’t so much of an interest to me.

Thanks.

Tagged with: • • • • • • • • • • • • •

Filed under: crypto and decrypt

Like this post? Subscribe to my RSS feed and get loads more!