"""-- dsa_sig_verification.py --
	Finds the DSA signature in 'dsa_signatures.txt' that 
	matches 'student_id'. Verification is carried out as described
	on pg. 264 of Johannes Buschmann's 'Introduction to Cryptography'
	text.

	AUTHORS:
		- Ivan Guerra (2016-04-23)
"""
import hashlib

class DSAPublicKey:
    """Plain data structure used to store the DSA public key."""
    def __init__(self, p, q, g, A):
        self.p = Integer(p)
        self.q = Integer(q)
        self.g = Integer(g)
        self.A = Integer(A)
    def __str__(self):
        ret_str = 'p = %d\n\nq = %d\n\ng = %d\n\nA = %d' % (self.p, self.q, self.g, self.A)
        return ret_str

class DSAStudentRecord:
    """Plain data structure used to store the DSA signatures parsed from 'dsa_signatures.txt'."""
    def __init__(self, index, r, s):
        self.index = index
        self.r = Integer(r)
        self.s = Integer(s)
    def __str__(self):
        ret_str = '%s\nindex = %d\n\nr = %d\n\ns = %d\n%s' % (80*'#', self.index, self.r, self.s, 80*'#')
        return ret_str

def compute_r(student_id, public_key, sig):
    """Compute r as shown in (12.13)."""
    R = GF(public_key.q)
    Q = GF(public_key.p)

    s_inv = (R(sig.s))^-1
    id_hash = Integer(int(hashlib.sha1(student_id).hexdigest(), 16))
    pow1 = R(s_inv * id_hash)
    pow2 = R(s_inv * sig.r)

    return R(Q(Q(public_key.g)^pow1 * Q(public_key.A)^pow2))

def get_id_signature(student_id, public_key, signatures):
    """Return the DSA signature in dsa_signatures.txt that corresponds to student_id."""
    for sig in signatures:
        if is_valid_signature(student_id, public_key, sig):
            return sig
    return None

def is_valid_signature(student_id, public_key, sig):
    """Verify the parameter signature, sig, corresponds to the DSA signature for student_id."""
    if not ((1 <= sig.r <= (public_key.q - 1)) and (1 <= sig.s <= (public_key.q - 1))):
        return False
    else:
        calculated_r = compute_r(student_id, public_key, sig)
        if (calculated_r == sig.r):
            return True
    return False

def parse_signatures(input_file):
    """Parse the DSA signatures in dsa_signatures.txt
    	Keyword arguments:
	input_file -- The path to the file containing DSA signatures.

	Return:
	Returns a list of DSAStudentRecord objects representing the signatures
	parsed from input_file.
    """
    signatures = []
    metadata = []
    file_handle = open(input_file, 'r')
    
    for line in file_handle:
        metadata = []
        for word in line.split():
            if word.isdigit():
                metadata.append(int(word))
        if len(metadata):
            signatures.append(DSAStudentRecord(metadata[0], metadata[1], metadata[2]))
    file_handle.close()
    return signatures
    
public_key = DSAPublicKey(7664992313008918236977211412910130800399425670702503643551476623493679890787062063547882061505697814057305052929801040264761076662492447105317357252788527, 2873825735738573859476020492596948649629496249717, 1457872567205293335814477132071849632453552864031138793244094012032641669938107233950162457826864071004561487382195476003583744649291185127122168774450172, 6513383146781514625030778825327897847455818159601805238207187913006663193547364532795538975416643743234045402412772195238742384241082145913862477173428524)

student_id = '112860972'
signature_file = 'dsa_signatures.txt'
signatures = parse_signatures(signature_file)
id_signature = get_id_signature(student_id, public_key, signatures)

print('The following DSA signature matches the ID ' + student_id + ':')
print(id_signature)
