Franklin-Reiter_相关信息攻击

Franklin-Reiter相关消息攻击

已知pow(x,e,n)和pow(ax+b,e,n)

可以通过形如下列式子求解

from sage.all import *

def franklinReiter(n,e,c1,c2,a,b):
    PR=PolynomialRing(Zmod(n),'X') 
    X=PR.gen()
    f1 = X**e - c1 #
    f2 = (X*a+ b)**e - c2 #
    # coefficient 0 = -m, which is what we wanted!
    return Integer(n-(compositeModulusGCD(f1,f2)).coefficients()[0]) # 系数
def compositeModulusGCD(a, b):
    if(b == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

最好将x的已知位给到最大，比如pow(x<<30,e,n)与pow(a*(x<<30),e,n)这里会有三十的已知位

如果直接把x<<30求解，可能会有较大误差可以试着更改

f1 = (X*2**30)**e - c1 f2 = ((X*2**30)*a)**e - c2

注意sage中<<并不是左移而是增大多少次方