Q57.py

import random, hashlib, hmac, binascii, math
from Crypto.Cipher import AES


def encryptAndMac(K, message):
    key = integerToAscii(K).zfill(16)
    encryption_suite = AES.new(key[0:16], AES.MODE_CBC, 'YELLOW SUBMARINE')
    padLength = 16 * int(math.ceil(float(len(message)) / 16))
    cipher_text = encryption_suite.encrypt(message.zfill(padLength))
    return [cipher_text, hmac.new(key, message, hashlib.sha1).digest()]

def decrypt(K, encrypt):
    key = integerToAscii(K).zfill(16)
    decryption_suite = AES.new(key[0:16], AES.MODE_CBC, 'YELLOW SUBMARINE')
    plain_text = decryption_suite.decrypt(encrypt)
    return plain_text

def bob(g, p, message):
    K = pow(g, b, p)
    return encryptAndMac(K, message)

def asciiToInteger(ascii):
    return int(binascii.hexlify(ascii), 16);

def integerToAscii(integer):
    hexString = format(integer, 'x')
    length = len(hexString)
    hexString = hexString.zfill(length+length%2)
    return binascii.unhexlify(hexString);

p = 7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771
g = 4565356397095740655436854503483826832136106141639563487732438195343690437606117828318042418238184896212352329118608100083187535033402010599512641674644143
q = 236234353446506858198510045061214171961

""" prove this to yourself by verifying g^x mod p = g^(x + k*q) mod p
x = random.randint(1, 0xffffffff)
k = random.randint(1, 0xffffffff)
#  g^x mod p 
print pow(g, x, p)
#  g^(x + k*q) mod p
print pow(g, (x + k*q), p)
# for any x and k. """

j = 30477252323177606811760882179058908038824640750610513771646768011063128035873508507547741559514324673960576895059570

count = 0

def prime_sieve(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

def trial_division(n, lowerThan):
    """Return a list of the prime factors for a natural number."""
    if n < 2:
        return []
    prime_factors = []
    for p in prime_sieve(lowerThan):
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1:
        prime_factors.append(n)
    return set(prime_factors)

factorsJ = trial_division(j, pow(2, 16))


""" Bob generates his secret key mod q """
global b
b = random.getrandbits(128) % q

message = 'crazy flamboyant for the rap enjoyment';

X = []
R = []

for r in factorsJ:
    if r > pow(2, 16) or r == 2:
        continue
    h = 1
    while (h == 1):
        h = pow(random.randint(1, p), ((p-1)/r), p)

    """ Eve Sends Bob h as her public key  """
    (tag, cypherText) = bob(h, p, message)

    for testR in range(r, r * 2):
        testk = pow(h, testR, p)
        (testTag, cypherText) = encryptAndMac(testk, message)
        if hmac.compare_digest(testTag, tag):
            X.append(testR % r)
            R.append(r)
            break


def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

bobsSecretKey = chinese_remainder(R, X)
a = random.getrandbits(128) % q
A = pow(g, a, p)
(cypherText, tag) = bob(A, p, message)
K = pow(A, bobsSecretKey, p)
print decrypt(K, cypherText)