gistfile1.txt

import random

def isPrime(n):
    #print 'is ',n,' prime?'
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        #print 'no'
        return False
    # 2 is the only even prime number
    if n == 2:
        #print 'yes'
        return True
    # all other even numbers are not primes
    if not n & 1:
        #print 'no'
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            #print 'no'
            return False
    #print 'yes'
    return True

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def multiplicative_inverse(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def gcd(a, b):
    while b != 0:
        #print 'is ',a,' a gcd of ',b
        t = b
        b = a%b
        a = t
    return a
def genPrime():
    print 'Generating prime number'
    buff=random.randrange(1, 500000)
    while 1:
        if(isPrime(buff)): return buff
        buff+=1#random.randrange(1, 500000)
def modexp ( g, u, p ):
   """computes s = (g ^ u) mod p
      args are base, exponent, modulus
      (see Bruce Schneier's book, _Applied Cryptography_ p. 244)"""
   s = 1
   while u != 0:
      if u & 1:
         s = (s * g)%p
      u >>= 1
      g = (g * g)%p;
   return s
def main():
    print 'Create primes'
    p=genPrime()
    q=genPrime()
    print 'Create sub primes'
    print 'p is ',p
    print 'q is ',q
    n=p*q
    m=(p-1)*(q-1)
    print 'n is ',n
    print 'm is ',m
    e=random.randrange(1, 100);
    while(gcd(m,e)!=1):
        e+=1
    d=0
    d = multiplicative_inverse(e, m)
    print 'Private key ',n,' and ',e
    print 'Public key ',n,' and ',d

    P = 123
    E = modexp( P, e, n )
    print 'Ciphertext ', E
    Pd = modexp( E, d, n )
    print 'Plaintext ', Pd

    thing = multiplicative_inverse(e, n)
    print 'Inverse of e base n ', thing
    hack = modexp( E, thing, n )
    print 'Hacked Plaintext ', hack

main()