Archive for January, 2013

RSA Algorithm

16/01/2013

I have put together some short articles with sample code, all based on mathematical algorithms in Python.

Series One

1: A. M. Legendre, exponentiation by successive squaring.
2: Heron of Alexandria, square roots
3: Peano arithmetic
4: Zeller’s congruence
5: Factorial
6: Fibonacci numbers
7: Euclid’s GCD & prime factors
8: Eratosthenes’ Sieve and the Miller-Rabin algorithm
9: Pascal’s triangle
10: Tau using Gregory and Euler’s equations

Series Two

1. Newton’s method for nth roots.
2. Primes revisited
a) faster Miller-Rabin
b) Lucas-Lehmer number
3. A Little Number Theory
a) Ramanujan’s Highly Composite Numbers
b) Ramanujan and Hardy – roundness
c) Pythagoras – perfect numbers
d) Pythagoras – friendly numbers
4. Pi
a) Euler’s method for calculating Pi
b) Cesaro / Monte Carlo method
5. The RSA algorithm

The .zip file is here.

As a little taster, here is the code of my RSA algorithm program. You can copy and paste it and have a play and download the .zip file to read my notes in the pdf file.

# rsa.py - demo of the RSA algorithm

def main():
    n = e = d = 0
    while 1:
        print("""
    1. Set Public Key
    2. Encode
    3. Decode
    0. Quit
    Your choice? """, end = "")
        choice = int(input())
        if not choice:
            return
        if choice == 1:
            n, e, d = set_keys()
        if choice == 2:
            if not n:
                n = int(input("Public Key: "))
                e = int(input("e: "))
            encode(n, e)
        if choice == 3:
            if not d:
                n, e, d = set_keys()
            decode(d, n)

def set_keys():
    """This fuction asks for 2 primes.
    It sets a public key and an encoding number, 'e'."""
    p = int(input("p: "))
    q = int(input("q: "))
    n = p * q
    m = (p - 1) * (q - 1)
    e = get_e(m)
    print("N = ", n, "\ne = ", e)
    d = get_d(e, m)
    while d < 0:
         d += m
     return [n, e, d]

     def encode(n, e):
     """This function asks for a number and encodes it using 'n' and 'e'."""
     while 1:
         c = int(input("Number to encode: "))
         if not c:
             return
         print(pow(c, e, n))

 def decode(d, n):
     """This function asks for a number and decodes it using 'd' and 'n'."""
     while 1:
         c = int(input("Number to decode: "))
         if not c:
             return
         else:
             print(pow(c, d, n))
     
  def even(x):
     """True if x is even."""
     return x % 2 == 0

  def get_e(m):
     """Finds an e coprime with m."""
     e = 2
     while gcd(e, m) != 1:
         e += 1
     return e

 def gcd(a,b):
     """Euclid's Algorithm: Takes two integers and returns gcd."""
     while b > 0:
        a, b = b, a % b
    return a

def get_d(e, m):
    """Takes encoding number, 'e' and the value for 'm' (p-1) * (q-1).
    Returns a decoding number."""
    x = lasty = 0
    lastx = y = 1
    while m != 0:
        q = e // m
        e, m = m, e % m
        x, lastx = lastx - q*x, x
        y, lasty = lasty - q*y, y
    return lastx

if __name__ == "__main__":
    main()

You can download a .zip file with the other short articles and programs here.

Enjoy!