""" Class defintion for the Franklin Reiter related message attack 

    Much of the code in this file is derived from the writeup
    located at: ahack.ru/write-ups/ructf-quals-14.htm
"""
sage_present = True
try:
    from sage.all_cmdline import *
except ImportError:
    sage_present = False

from RSAExploits.exploits.exploit import Exploit


class Franklin_Reiter(Exploit):
    """ Class providing a run interface to Franklin Reiter's attack """

    def run(self, rsadata_list, info_dict = None):
        """ Recovers plaintext message using Franklin-Reiter's attack

            This attack should work as long as the provided parameters
            are correct. However, if the public exponent e is not small,
            it may run for a long time.
    
            Args:
                rsadata_list: A list of RSA_Data objects on which to attempt the
                              boneh durfee exploit
                info_dict: Specifies the relationship between the two plaintext
                           messages as a polynomial under the key "Franklin_Reiter"

            Side Effects: 
                If a message is recovered, the corresponding field in the
                RSA_Data objects will be set

            Return: 
                True if the attack completes
        """
        
        global sage_present
        success = False
        
        if not sage_present:
            print "Franklin Reiter: Sage required, skipping exploit"
            return success

        if len(rsadata_list) != 2:
            print "Franklin Reiter: Exactly 2 RSA_Data objects must be provided"
            return success
        
        if info_dict == None or "Franklin_Reiter" not in info_dict:
            print "Franklin Reiter: Polynomial relationship between messages required"
            return success
        
        print ("Franklin Reiter: Running Attack...")
        success = True  
        n = rsadata_list[0].get_n()
        e = rsadata_list[0].get_e()
        c1 = rsadata_list[0].get_c()
        c2 = rsadata_list[1].get_c()
        poly = info_dict["Franklin_Reiter"]
        msg = Franklin_Reiter.franklin_reiter(n, e, c1, c2, poly)
        rsadata_list[0].set_m(msg)
        rsadata_list[1].set_m(msg)
        print ("Franklin Reiter: Message recovered")
        return success

    @staticmethod
    def franklin_reiter(n, e, c1, c2, poly):
        """ Recover the plaintext message using franklin-reiter attack """
        x = PolynomialRing(ZZ.quo(n*ZZ), 'x').gen()
        poly1 = poly**e - c1
        poly2 = x**e-c2
        coefs = Franklin_Reiter.poly_gcd(poly1, poly2)
        msg = int(-pow(coefs[1], -1, n) * coefs[0])
        return msg

    @staticmethod
    def poly_gcd(poly1, poly2):
        """ Compute the gcd of two polynomials """
        a = poly1
        b = poly2
        i = 0

        while True:
            r = a % b
            if r == 0:
                c = rp.coeffs()
                return c
            rp = r
            a, b = b, r
            i += 1
