# RSA Implementation
# Eliot Ball

import random
import math
import time

def RsaEnc(key, ptext):
    return ModPow(StrToNum(str(ptext)), key[1], key[0])

def RsaDec(key, ctext):
    return NumToStr(ModPow(ctext, key[1], key[0]))

def PublicKey(primes):
    e = 65537
    while (primes[0] - 1) * (primes[1] - 1) % e == 0 or CheckPrimeF(e) == False:
        e += 2
    return [primes[0] * primes[1], e]

def PrivateKey(primes):
    e = 65537
    while (primes[0] - 1) * (primes[1] - 1) % e == 0 or CheckPrimeF(e) == False:
        e += 2
    i = 0
    d = 0
    while d == 0:
        i = i + 1
        if (i * (primes[0] - 1) * (primes[1] - 1) + 1) % e == 0:
            d = (i * (primes[0] - 1) * (primes[1] - 1) + 1) / e
    return [primes[0] * primes[1], d]

def StrToNum(text):
    result = 0
    for i in range(len(text)):
        result += ord(text[i]) * 256**i
    return result

def NumToStr(num):
    result = ""
    while num > 0:
        result += chr(num % 256)
        num = (num - (num % 256)) / 256
    return result

def GetKeys():
    primes = GetPrimes()
    private = PrivateKey(primes)
    return [private, PublicKey(primes)]

def GetPrimes():
    return [GetPrime(), GetPrime()]

def GetPrime():
    n = int(10**(100 - 1) * (time.clock() % 1.0) * 10)
    n = n + n % 2 + 1
    while CheckPrimeF(n) == False:
        n += 2
    return n
    
def CheckPrimeF(n):
    for i in xrange(100000):
        a = random.randint(1, n - 1)
        if ModPow(a, n-1, n) != 1:
            return False
    return True

def ModPow(a, b, m):
    result = 1
    while b > 0:
        if (b & 1) == 1:
           result = (result * a) % m
        b = b >> 1
        a = (a**2) % m
    return result