
# This file was *autogenerated* from the file franklin.sage
from sage.all_cmdline import *   # import sage library

_sage_const_3 = Integer(3); _sage_const_2 = Integer(2); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_11 = Integer(11); _sage_const_8 = Integer(8); _sage_const_512 = Integer(512); _sage_const_8192 = Integer(8192); _sage_const_16 = Integer(16); _sage_const_30 = Integer(30); _sage_const_400 = Integer(400); _sage_const_25 = Integer(25)
from sage.all import *
# https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage
# Franklin-Reiter attack against RSA.
# If two messages differ only by a known fixed difference between the two messages
# and are RSA encrypted under the same RSA modulus N
# then it is possible to recover both of them.

# Inputs are modulus, known difference, ciphertext 1, ciphertext2.
# Ciphertext 1 corresponds to smaller of the two plaintexts. (The one without the fixed difference added to it)
def franklinReiter(n,e,r,c1,c2):
    R = Zmod(n)['X']; (X,) = R._first_ngens(1)
    f1 = X**e - c1
    f2 = (X + r)**e - c2
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[_sage_const_0 ])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == _sage_const_0 ):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=_sage_const_1 /_sage_const_30 ):
    """
    Coppersmith's Shortpad attack!
    Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack
    """
    import binascii
    P = PolynomialRing(ZZ, names=('x', 'y',)); (x, y,) = P._first_ngens(2)
    ZmodN = Zmod(n)
    g1 = x**e - C1
    g2 = (x+y)**e - C2
    res = g1.resultant(g2)
    P = PolynomialRing(ZmodN, names=('y',)); (y,) = P._first_ngens(1)
    # Convert Multivariate Polynomial Ring to Univariate Polynomial Ring
    rres = _sage_const_0 
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y**(res.exponents()[i][_sage_const_1 ]))

    diff = rres.small_roots(epsilon=eps)
    recoveredM1 = franklinReiter(n,e,diff[_sage_const_0 ],C1,C2)
    print(recoveredM1)
    print("Message is the following hex, but potentially missing some zeroes in the binary from the right end")
    print(hex(recoveredM1))
    print("Message is one of:")
    for i in range(_sage_const_8 ):
        msg = hex(Integer(recoveredM1*pow(_sage_const_2 ,i)))
        if(len(msg)%_sage_const_2  == _sage_const_1 ):
            msg = '0' + msg
        if(msg[:_sage_const_2 ]=='0x'):
            msg = msg[:_sage_const_2 ]
        print(binascii.unhexlify(msg))

def testCoppersmithShortPadAttack(eps=_sage_const_1 /_sage_const_25 ):
    from Crypto.PublicKey import RSA
    import random
    import math
    import binascii
    M = "flag{This_Msg_Is_2_1337}"
    M = int(binascii.hexlify(M),_sage_const_16 )
    e = _sage_const_3 
    nBitSize =  _sage_const_8192 
    key = RSA.generate(nBitSize)
    #Give a bit of room, otherwhise the epsilon has to be tiny, and small roots will take forever
    m = int(math.floor(nBitSize/(e*e))) - _sage_const_400 
    assert (m < nBitSize - len(bin(M)[_sage_const_2 :]))
    r1 = random.randint(_sage_const_1 ,pow(_sage_const_2 ,m))
    r2 = random.randint(r1,pow(_sage_const_2 ,m))
    M1 = pow(_sage_const_2 ,m)*M + r1
    M2 = pow(_sage_const_2 ,m)*M + r2
    C1 = Integer(pow(M1,e,key.n))
    C2 = Integer(pow(M2,e,key.n))
    CoppersmithShortPadAttack(e,key.n,C1,C2,eps)

def testFranklinReiter():
    p = random_prime(_sage_const_2 **_sage_const_512 )
    q = random_prime(_sage_const_2 **_sage_const_512 )
    n = p * q # 1024-bit modulus
    e = _sage_const_11 

    m = randint(_sage_const_0 , n) # some message we want to recover
    r = randint(_sage_const_0 , n) # random padding

    c1 = pow(m + _sage_const_0 , e, n)
    c2 = pow(m + r, e, n)
    print(m)
    recoveredM = franklinReiter(n,e,r,c1,c2)
    print(recoveredM)
    assert recoveredM==m
    print("They are equal!")
    return True

if __name__=="__main__":
    testFranklinReiter()



# This file was *autogenerated* from the file franklin.sage
from sage.all_cmdline import *   # import sage library

_sage_const_3 = Integer(3); _sage_const_2 = Integer(2); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_11 = Integer(11); _sage_const_8 = Integer(8); _sage_const_512 = Integer(512); _sage_const_8192 = Integer(8192); _sage_const_16 = Integer(16); _sage_const_30 = Integer(30); _sage_const_400 = Integer(400); _sage_const_25 = Integer(25)
from sage.all import *
# https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage
# Franklin-Reiter attack against RSA.
# If two messages differ only by a known fixed difference between the two messages
# and are RSA encrypted under the same RSA modulus N
# then it is possible to recover both of them.

# Inputs are modulus, known difference, ciphertext 1, ciphertext2.
# Ciphertext 1 corresponds to smaller of the two plaintexts. (The one without the fixed difference added to it)
def franklinReiter(n,e,r,c1,c2):
    R = Zmod(n)['X']; (X,) = R._first_ngens(1)
    f1 = X**e - c1
    f2 = (X + r)**e - c2
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[_sage_const_0 ])

  # GCD is not implemented for rings over composite modulus in Sage
  # so we do our own implementation. Its the exact same as standard GCD, but with
  # the polynomials monic representation
def compositeModulusGCD(a, b):
    if(b == _sage_const_0 ):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def CoppersmithShortPadAttack(e,n,C1,C2,eps=_sage_const_1 /_sage_const_30 ):
    """
    Coppersmith's Shortpad attack!
    Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack
    """
    import binascii
    P = PolynomialRing(ZZ, names=('x', 'y',)); (x, y,) = P._first_ngens(2)
    ZmodN = Zmod(n)
    g1 = x**e - C1
    g2 = (x+y)**e - C2
    res = g1.resultant(g2)
    P = PolynomialRing(ZmodN, names=('y',)); (y,) = P._first_ngens(1)
    # Convert Multivariate Polynomial Ring to Univariate Polynomial Ring
    rres = _sage_const_0 
    for i in range(len(res.coefficients())):
        rres += res.coefficients()[i]*(y**(res.exponents()[i][_sage_const_1 ]))

    diff = rres.small_roots(epsilon=eps)
    recoveredM1 = franklinReiter(n,e,diff[_sage_const_0 ],C1,C2)
    print(recoveredM1)
    print("Message is the following hex, but potentially missing some zeroes in the binary from the right end")
    print(hex(recoveredM1))
    print("Message is one of:")
    for i in range(_sage_const_8 ):
        msg = hex(Integer(recoveredM1*pow(_sage_const_2 ,i)))
        if(len(msg)%_sage_const_2  == _sage_const_1 ):
            msg = '0' + msg
        if(msg[:_sage_const_2 ]=='0x'):
            msg = msg[:_sage_const_2 ]
        print(binascii.unhexlify(msg))

def testCoppersmithShortPadAttack(eps=_sage_const_1 /_sage_const_25 ):
    from Crypto.PublicKey import RSA
    import random
    import math
    import binascii
    M = "flag{This_Msg_Is_2_1337}"
    M = int(binascii.hexlify(M),_sage_const_16 )
    e = _sage_const_3 
    nBitSize =  _sage_const_8192 
    key = RSA.generate(nBitSize)
    #Give a bit of room, otherwhise the epsilon has to be tiny, and small roots will take forever
    m = int(math.floor(nBitSize/(e*e))) - _sage_const_400 
    assert (m < nBitSize - len(bin(M)[_sage_const_2 :]))
    r1 = random.randint(_sage_const_1 ,pow(_sage_const_2 ,m))
    r2 = random.randint(r1,pow(_sage_const_2 ,m))
    M1 = pow(_sage_const_2 ,m)*M + r1
    M2 = pow(_sage_const_2 ,m)*M + r2
    C1 = Integer(pow(M1,e,key.n))
    C2 = Integer(pow(M2,e,key.n))
    CoppersmithShortPadAttack(e,key.n,C1,C2,eps)

def testFranklinReiter():
    p = random_prime(_sage_const_2 **_sage_const_512 )
    q = random_prime(_sage_const_2 **_sage_const_512 )
    n = p * q # 1024-bit modulus
    e = _sage_const_11 

    m = randint(_sage_const_0 , n) # some message we want to recover
    r = randint(_sage_const_0 , n) # random padding

    c1 = pow(m + _sage_const_0 , e, n)
    c2 = pow(m + r, e, n)
    print(m)
    recoveredM = franklinReiter(n,e,r,c1,c2)
    print(recoveredM)
    assert recoveredM==m
    print("They are equal!")
    return True

if __name__=="__main__":
    testFranklinReiter()


# This file was *autogenerated* from the file franklin.sage # import sage library # https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage # Franklin-Reiter attack against RSA. # If two messages differ only by a known fixed difference between the two messages # and are RSA encrypted under the same RSA modulus N # then it is possible to recover both of them. # Inputs are modulus, known difference, ciphertext 1, ciphertext2. # Ciphertext 1 corresponds to smaller of the two plaintexts. (The one without the fixed difference added to it) # coefficient 0 = -m, which is what we wanted! # GCD is not implemented for rings over composite modulus in Sage # so we do our own implementation. Its the exact same as standard GCD, but with # the polynomials monic representation Coppersmith's Shortpad attack!     Figured out from: https://en.wikipedia.org/wiki/Coppersmith's_attack#Coppersmith.E2.80.99s_short-pad_attack # Convert Multivariate Polynomial Ring to Univariate Polynomial Ring #Give a bit of room, otherwhise the epsilon has to be tiny, and small roots will take forever # 1024-bit modulus # some message we want to recover # random padding