Cryptography - HW3.2 (sign.py)

from oracle import *
from helper import *

# xgcd(a,b) and modinv(a,b) taken from https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm


def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0


def modinv(a, b):
    """return x such that (x * a) % b == 1"""
    g, x, _ = xgcd(a, b)
    if g != 1:
        raise Exception('gcd(a, b) != 1')
    return x % b


def sign(challenge, N):
    ''' Step 0 : Initialize Conecction '''
    Oracle_Connect()

    ''' Step 1 : convert original message to integers'''
    m = ascii_to_int(challenge)

    ''' Step 2 : HACKING!!! '''
    # divide msg into two parts
    m1 = 7
    m2 = m / m1
    # inverse of sign(1) over N
    inverse_1 = modinv(Sign(1), N)
    # evaluate new sign
    r = (Sign(m1) * Sign(m2) * inverse_1) % N

    ''' Step 3 : Check if sign is correcy'''
    if Verify(m, r):
        print 'Sign Verified!'
        print r
    else:
        print 'Sign Verification Failed'

    ''' Step 4: Disconect from server '''
    Oracle_Disconnect()


def main():
    challenge = 'Crypto is hard --- even schemes that look complex can be broken'
    N = 119077393994976313358209514872004186781083638474007212865571534799455802984783764695504518716476645854434703350542987348935664430222174597252144205891641172082602942313168180100366024600206994820541840725743590501646516068078269875871068596540116450747659687492528762004294694507524718065820838211568885027869
    sign(challenge, N)


if __name__ == '__main__':
    main()