Technology — 06 January 2014

by

Walker Rowe

(Note:  This post has nothing to do with literature or South America.  Our editor studied mathematics in college and continues with that, because David Foster Wallace did.)

Here I give an example of how to create a public and private key and encrypt and decrypt a message using the RSA encryption algorithm.   I am writing this, because I have found no example on the Internet that is complete, meaning nothing you can understand from beginning to end.  Examples on the internet give the theory and walk the user most of the way through an example, but the user gets stuck trying to calculate the private key.  They say things like, “This can be done very easily and quickly with the Extended Euclidean Algorithm.” and then leave out the details.

Here we use a Python program to calculate the Extended Euclidean Algorithm.  I am not going to explain how to do that by hand here.  You can find that on YouTube here.

So, let’s go.  We base our example of the description of the RSA algorithm given here on Wikipedia.    We will take this example and show you how to solve it from beginning to end.

First, pick two prime numbers:

p=11

q=13

Calculate n=p*q=11*13=143

Calculate Φ(n)=(11-1)(13-12)=120

Find an e such that 1 < e < Φ(n) and gcd(e,Φ(n))=1.  We pick e=7.  That is our public key. Check that gcd(7,120)=1.

Now is the hard part, finding the private key.  We need to find d such d * e mod Φ (n) = 1.   That is where we need the Extended Euclid Algorithm.  We copied the Python code to do that from here.

Now calculate the public key like this:

modinv(7,120)=103=d

Let’s try to encrypt and decrypt something.

let m=8 be our message.

To encrypt m solve:

m^e mod n=c=(8**7)%143=57

To decrypt c solve:

 c^d mod n=m=(57**103)%143=8=m

Done.

Here is the Python code:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

def egcd(a, b):

    x,y, u,v = 0,1, 1,0

    while a != 0:

       q, r = b//a, b%a

       m, n = x-u*q, y-v*q

       b,a, x,y, u,v = a,r, u,v, m,n

    return b, x, y

 

def modinv(a, m):

    g, x, y = egcd(a, m)

    if g != 1:

       return None  # modular inverse does not exist

    else:

       return x % m

Related Reading

Diffie-Hellman

Share

About Author

(2) Readers Comments

  1. RSA is dying. Advances in math and computing have made larger and large primes necessary. Something like 3000 digits is now recommended. The new way is elliptic curve, where instead of having to factor the product of two giant primes, you have to find the base log and exponent of one large prime raised to the power of another, which is more difficult. Certicom owns all the patents, I believe.

    David Wallace was a brilliant writer, but a terrible mathematician, by the way.

  2. Great text but as the first time I saw phi of a number, this really confused me for a while:
    “Calculate Φ(n)=(11-1)(13-12)=120”

    Calculation typos can really confuse newbies.

Leave a Reply

Your email address will not be published. Required fields are marked *


× four = 4