#Good and bad verification function for 2048-bit RSA signatures


#The arguments to both functions are

#m -- a string
#e -- verification exponent
#N --modulus
#s --the signature as an integer < N

import hashlib
import re

#a utility for converting a long integer N to a 512-character hex string
def hexx(num):
    u=hex(num)
    #strip leading 0x and trailing L
    if u[:2]=='0x':
        u=u[2:]
    if u[-1]=='L':
        u=u[:-1]
    le = len(u)
    return '0'*(512-le)+u

def goodVerify(m,e,N,s):
    h=hashlib.sha1(m).hexdigest()
    k=pow(s,e,N)
    u=hexx(k)
    test = '0001'+'f'*436 +'003021300906052b0e03021a05000414'+h
    return u==test

#badVerify  uses regular expression matching to verify that
#the hex representation of the signature
#begins 0001 followed by a bunch of f's, followed
#by the test pattern containing the SHA-1 hash of the message.
#This leaves the possibility that the hash is not at the right-
#hand end of the signature
def badVerify(m,e,N,s):
    h=hashlib.sha1(m).hexdigest()
    k=pow(s,e,N)
    u=hexx(k)
    test='003021300906052b0e03021a05000414'+h
    loc=u.find(test)
    m = re.match('0001f*'+test,u)
    if m:
        return True
    return False

#This creates the padded RSA signature on m, using the
#private key d.  You won't actually use this in the assignment,
#but it might be helpful in putting together your fake signature.
def sign(m,d,N):
    h=hashlib.sha1(m).hexdigest()
    padded='0001'+'f'*436 +'003021300906052b0e03021a05000414'+h
    print padded
    return pow(long(padded,16),d,N)