A few helper functions
There are several functions required to perform RSA. The most interesting is bezout(a,b)
which solves for integer and given positive integers and so that
Computing or can take a long time if exponentiation without thinking. The following uses about multiplication and mod operations instead of the many of these operations if m ** d % n
were used.
The following plot indictes the time difference between using fast_exp and not for relatively small exponents. The blue is the running time of regular exponentiation in nanoseconds.
The next two helper functions convert a text message to an integer and vice versa.
Two more helper functions, isPrime does the obvious test, it optimizes a bit by testing only odd possible factors for primes and only up to the square root of n. The function Primes does a complete prime factorization of n. It is really the running time of these and similar functions that make RSA secure. If you try the isPrime on p or q below in the "Real World" parameters section, then don't plan on seeing the process terminate. To test primality on truely large numbers probabilistic primality tests are used. It is also useful to know about how likely you are to find a prime, the Prime Number Theorem basically provides that if an odd number is chosen at random that is around n bits, then the probability that that number is prime is approximately . so if we choose a random odd number, , that is around 516 bits, then . After 53 random attempts the probability for finding a prime is already over 50%.
Real World RSA parameters
Here would be some "real world" prime pairs. The primes p and q are 516 bits making n 1024 bits as required for RSA, but our codes run too slow on these.
Generate Primes
These function generate primes to use for RSA. You can choose the size of the primes to look for. Do not try a size like 1024 bits as required for real RSA applications!
The RSA algorithm
Here is the actual RSA. The first function uses the gen_prime_pair together with a seed for the random number generator (the "pass phrase" -- really just noise.) The encoding function simply takes the message, converts it to an integer, , which must be and then computes . This is the cypher text. The decoding function, then computes which is again and then reconstructs the text from its numeric representation.
Generate public, private key pair.
There are things to watch out for. Suppose I wish to code "Hello", this is five 8 bit (1 byte) characters, or 40 bits. For n to have 40 bits we need p and q to have around 20 bits so when running the key_gen, we need to use bits = 20.
Encode the plain text message "Hello".
Decode the original message.
Breaking RSA
The following simulates a brute force break of a 32 bit RSA encryption. The primes are chosen to be 16 bit, so the search space has size .
Brute force factor and comput the private key, then decrypt.