# -*- coding: utf-8 -*-
"""
-------------------------------------------------
   File Name :      short_pad_attack
   Description :
   Author :         x3nny
   date :           2021/7/23
-------------------------------------------------
   Change Activity:
                    2021/7/23: Init
-------------------------------------------------
"""


# This file was *autogenerated* from the file /Users/x3nny/tools/pypackages/xenny/xenny/ctf/crypto/modern/asymmetric/rsa/copper_smith/short_pad_attack.sage
from sage.all_cmdline import *   # import sage library

_sage_const_0 = Integer(0); _sage_const_1 = Integer(1); _sage_const_30 = Integer(30); _sage_const_2 = Integer(2); _sage_const_0p5 = RealNumber('0.5'); _sage_const_25 = Integer(25)
__author__ = 'x3nny'


# 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
    """
    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)
    if diff:
        return diff[_sage_const_0 ]
    return None

def another_get_diff(e, n, c1, c2):
    PRxy = PolynomialRing(Zmod(n), names=('x', 'y',)); (x, y,) = PRxy._first_ngens(2)
    PRx = PolynomialRing(Zmod(n), names=('xn',)); (xn,) = PRx._first_ngens(1)
    PRZZ = PolynomialRing(Zmod(n), names=('xz', 'yz',)); (xz, yz,) = PRZZ._first_ngens(2)

    g1 = x ** e - c1
    g2 = (x + y) ** e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.bit_length() // (_sage_const_2  * e * e)
    diff = h.small_roots(X=_sage_const_2 **kbits, beta=_sage_const_0p5 )[_sage_const_0 ]  # find root < 2^kbits with factor >= n^0.5
    return diff

def getdiff(e, n, c1, c2, eps):
    diff = CoppersmithShortPadAttack(e, n, c1, c2, eps)
    if diff:
        return diff
    return another_get_diff(e, n, c1, c2)

def attack(e, n, c1, c2, r=None, eps=_sage_const_1 /_sage_const_25 ):
    if r is None:
        r = getdiff(e, n, c1, c2, eps)
    m = franklinReiter(n,e,r,c1,c2)
    return m

