How does one implement the RSA (Encryption/Decryption) Algorithm?
Hello,
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…
Tagged with: crypto • distinct primes • exponent • google • lt • mechanisms • modular arithmetic • odd number • rsa algorithm • two primes • wheel
Filed under: crypto and decrypt
Like this post? Subscribe to my RSS feed and get loads more!
1) How is this algorithm applied in real life?
RSA gets its security from factorization problem. Read the source below for more detail.
2) How does one generate two large primes?
Large odd number are chosen at random.
Factorization algorithms can be used (attempted at least) to
factor faster than brute forcing: Trial division, Pollard’s rho,
Pollard’s p-1, Quadratic sieve, elliptic curve factorization,
Random square factoring, Number field sieve, etc. to check whether the number is prime number or not.
3) How is the arithmetic carried out?
For a example of number sieve go here to website below:
http://www.daniweb.com/code/snippet305.html
Or read here to find out more:
http://en.wikipedia.org/wiki/Primality_test
http://en.wikipedia.org/wiki/Pollard%27s_p_-_1_algorithm
4) 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?
To find modular of a power is easier compared to finding the power first then finding the modular.
Example are from website below:
http://www.urch.com/forums/gmat-problem-solving/34778-remainder-high-power-ps.html
Or you can read about it below:
http://www.cat4mba.com/node/6127
http://en.wikipedia.org/wiki/Modular_arithmetic
http://babbage.sissa.it/PS_cache/cs/pdf/9903/9903001v1.pdf
e coprime to m, means that the largest number that can exactly divide both e and m (their greatest common divisor, or gcd) is 1. Euclid’s algorithm is used to find the gcd of two numbers, but the details are omitted here.
for two large prime,
(p-1)(q-1) is even number x even number = even number
So it can be said that e could not be 2.
m = (p – 1)(q – 1)
d = (1 + nm) / e
where d and n must be an integer.
See the below for good example:
http://pajhome.org.uk/crypt/rsa/rsa.html
this question is way to complex for all the idiots on yahoo answers.