RSA

#Program to break RSA Encrytion (192 bits)
#For UNL CSE 235
import fractions
import binascii

def moddingFunction(base, exp, modulus):
    exp = bin(exp)
    exp = exp[2:]
    length = len(exp)
    result = 1
    i = 1
    while i <= length:
        if (exp[length - i] == "1"):
            result = result * base % modulus
        i+=1
        base = base * base % modulus
    return result

def findAscii(binary):
    num = int(binary, 2)
    s = chr(num)
    return s

def parseBinary(binaryString):
    length = len(str(binaryString))
    string = str(binaryString)
    i = 0
    s = ""
    while i < length:
        s+=findAscii(string[i:i+8])
        i+=8
    return s

def euclidianAlg(a, b):
    a0 = a
    b0 = b
    t0 = 0
    t = 1
    s0 = 1
    s = 0
    q = a0 / b0
    r = a0 - q * b0
    while r > 0:
        temp = t0 - q * t
        t0 = t
        t = temp
        temp = s0 - q * s
        s0 = s
        s = temp
        a0 = b0
        b0 = r
        q = a0 / b0
        r = a0 - q * b0
        if r > 0:
            gcd = r

    return s

n = int("71b01d67076bae7f77834fc8de6f7fd5d82c83118debce5b", 16)
a = int("11ce93d4ad2d558e9e96d8a2155593bd8cd9f8c054bf15", 16)

p = 44923681168431411353414651281
q = 62052358958489486690048694059
totient = (p - 1) * (q - 1)

#find ainv

ainv = euclidianAlg(a, totient)
#find b
b = ainv % totient

#decrypt is y^b mod n y is the line in hex
#build string at the same time
s = ""
file = open('cipher.txt', 'r')
for line in file:
    num = int(line, 16)
    num = moddingFunction(num, b, n)
    test = pow(num, b, n)
    num = bin(num)
    num = num[2:]
    while (len(num) < 96):
        num = "0" + num
    s+=parseBinary(num)

print s