#!/usr/local/bin/python

import curses.ascii
import time
import hashlib
import getpass
import hmac
import random
import sys

#text formatting strings
bold = "\033[1m"
blue = "\033[34m"
red = "\033[31m"
default = "\033[0m"
inverted = "\033[7m"

def egcd(a,b):
    """
    egcd(a,b) for a,b>0 returns g,x,y where g=gcd(a,b) and xa+yb=g
    """
    
    if b==0: return a,1,0
    if a==0: return b,0,1

    if a<b:
        q,r=divmod(b,a)
        g,x,y=egcd(a,r)
        return g,x-y*q,y
    else:
        q,r=divmod(a,b)
        g,x,y=egcd(r,b)
        return g,x,y-x*q

def powermod(a,k,m):
    # computes a^k mod m
    ret,aa,kk = 1,a,k
    # ret*aa**kk with smaller and smaller kk
    while kk>0:
        if kk%2==0:
            kk >>= 1
            aa = (aa*aa)%m
        else:
            kk = kk-1
            ret = ret*aa % m
    return ret


def invmod(a,m):
    # finds multiplicative inverse of a mod m, assuming gcd(a,m)=1
    g,u,v=egcd(a,m)
    return u%m


def miller_rabin(n,tests=4):
    # tests if number n is prime, 0 means composite, 1 means probably prime
    if n<2: return 0
    if n==2: return 1
    if n%2==0: return 0
    d=n-1
    s=0
    while d%2==0:
        s=s+1
        d >>= 1    #d = d *2
    # now n-1=d*2**s with d odd
    for i in range(tests):
        a=random.randrange(1,n)
        b=powermod(a,d,n)
        if b!=1:
            j=0
            res=0
            while j<s and b!=n-1:
                b=(b*b)%n
                j=j+1
            if j==s:
                return 0
    return 1

def encloop(mod, k, inv, hp):
    #prompt for encode, decode, or exit
    c="\0"
    while c!="E" and c!="e" and c!="D" and c!="d" and c != "X" and c != "x":
        c = raw_input(bold+"[e]ncode, [d]ecode, or e[x]it: "+default+blue)
        sys.stdout.write(default)
    if c == "X" or c == "x":
        exit()
    encode = 0
    if c == "E" or c == "e":
        encode = 1
    
    if encode:
        #encoding: get message to encode
        message = raw_input(bold+"message: "+default+blue)
        sys.stdout.write(default)
        nm = [0]               #numerical representation of message
        index = 0              #which entry in nm are we working on
        count = 0              #how many characters added to nm so far
        for i in message:
            if count == 0:
                #add random bits to begining of number for extra security
                nm[index] |= random.getrandbits(7*9) << (7*26)
                count = 10
            #add numerical representation of character i to nm
            nm[index] |= (ord(i) % 128) << (7*(35 - count))
            count = count + 1
            if count > 35:
                #this nm full, go to next one
                index = index + 1
                nm.append(0)
                count = 0

        #print encoded output
        print "\n"+red
        for i in range(len(nm)):
            print powermod(nm[i], k, mod),

            #puts comma if not last time
            if i != len(nm)-1:
                print ",",

        print "\n"+default
    else:
        #get array of encypted numbers in list form
        rsa = eval("[%s]" % raw_input(bold+"message: "+default+blue))
        sys.stdout.write(default)
        for i in rsa:
            #decode current number using inv
            nm = powermod(i, inv, mod)
            count = 0
            out = ""
            while nm != 0:
                #get character from decoded number
                pc = chr((nm >> (7*(25-count)))%128)
                #make sure character is real text
                if curses.ascii.isspace(pc) or curses.ascii.isgraph(pc):
                    #append decoded caracter to output string
                    out = out + pc
                count = count + 1
                if count > 25:
                    #all data read from number
                    break
            print red+out+default

            
#begining of program
print inverted+"RSA implemented by Cobb"+default

kps = ""
while kps != "k" and kps != "K" and kps != "p" and kps != "P":
    kps = raw_input(bold+"[k]ey or [p]assword? "+default+blue)
    sys.stdout.write(default)


haspass = 0
if kps == "p" or kps == "P":
    haspass = 1

p = 0
q = 0
k = 0
inv = 0
m = 0
if haspass:
    #seed random number generator with password
    m = hashlib.md5(getpass.getpass(bold+"Password: "+default))
    random.seed(m.hexdigest())
    #
    power = random.randint(75, 175)
    while 1:
        p = random.randint(1 << power, 1 << (power + 3))|1
        if miller_rabin(p, 10):
            break
    while 1:
        q = random.randint(1 << (253-power), 1 << (256 - power))|1
        if miller_rabin(q, 10):
            break
    while 1:
        k = random.randint(1 << 25, 1 << 225)|1
        if egcd((p-1)*(q-1), k)[0] == 1:
            break
    print bold+"m = "+default+red, p*q, default
    print bold+"k = "+default+red, k, default
    inv = invmod(k, (p-1)*(q-1))
else:
    m = input(bold+"m: "+default+blue)
    sys.stdout.write(default)
    k = input(bold+"k: "+default+blue)
    sys.stdout.write(default)

t = "%f" % time.time()
random.seed(hmac.new("%f" % random.random(), t).digest())

if haspass:
    while 1:
        encloop(p*q, k, inv, 1)
else:
    while 1:
        encloop(m, k, k, 0)