How does one implement the RSA (Encryption/Decryption) Algorithm?

Question

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.

Answer 1

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

Answer 2

MD5 and MD6 aren't even encryption schemes - they're cryptographic hashes. This means you can't go the other way. Of all of the algorithms, RSA is probably one of the easiest to implement. It's equivalent to first-year university algebra, and there are dozens of existing implementations available on the Internet. It's also essentially uncrackable for anyone without the computing resources of the NSA (they can probably do it in a few seconds). In general, the harder a type of encryption is to break, the harder the math behind it working (though the math behind breaking these schemes is usually way harder than making it work), and the harder it will be to understand well enough to code. RSA, difficult though it may seem, is actually really easy as far as algorithms go, and surprisingly difficult to crack.

Answer 3

this question is way to complex for all the idiots on yahoo answers.