Franklin-Reiter相关信息攻击

前言

参考:这篇文章

装好sage：下载链接

Franklin-Reiter介绍

该攻击方法在于两个明文m1,m2，这两个明文利用同一个e和m，并且m2和m1间具有线性关系,例如：

m2 = a*m1 + b

• 并且给出了c1,c2

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

知道c1,c2,a,b,n，那么m1是可解的

原理

• 因此最后的解的形式其实是X-M的形式的，利用sage库中的Q.coefficients()[0]

Q.coefficients() —— 提取多项式Q中的系数，并且是升序排列
举个栗子：
f = x^3 + 2x^2 -3x + 4
f.coefficients()
返回列表[4,-3,2,1]

f = x^3 + 2x^2 + 4
f.coefficients()
返回列表[4,2,1] # 0省略

板子

题目

from secret import flag
from Crypto.Util.number import *

m1 = bytes_to_long(flag)
N = getPrime(512)*getPrime(512)
e = 17

c1 = pow(m1, e, N)

a = getRandomNBitInteger(512)
b = getRandomNBitInteger(512)
m2 = a * m1 + b
c2 = pow(m2, e, N)

print(N, a, b, c1, c2, sep="\n")

EXP

import libnum
n = ...
c1 = ...
c2 = ...
a = ...
b = ...
def franklinReiter(n,e,c1,c2,a,b):
    R.<X> = Zmod(n)[]
    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]) # 系数

  # 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 == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

m=franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))

题目

NSSCTF

flag1=b'******'

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
m1 = bytes_to_long(flag1)
a = getPrime(128)
b = getPrime(128)
m2 = a*m1 + b

hint1 = a**2 + a*b 
hint2 = b**2 + b*a

c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

print(f'n = {n}')
print(f'hint1 = {hint1}')
print(f'hint2 = {hint2}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

'''
n = 96294984374753089080583610747240203389088051930341615602841335596072081913930052484580770899610689065293206976889303327507604080242460321817406117877072425663471808350427893332726383611142246218026112051129578226014713958882307096859175042839198895428723757405196020266267824586199807170149650434306779718677   
hint1 = 111128465335502483574544230236618721723785067258103368528600651970108082026274
hint2 = 149777690555091648253749138438840244052377948686936166203166372618778229891842
c1 = 19258639302759286032385037035129183959148363633353536085988651266927081471573889078520697158985164250184287591219408939982288951952002632371950165308028756191357634396067109728491154241759098403135297660541258808223827178690693818047525955978891748361038516201626720292976210372367169577574791733786601438737  
c2 = 94728391095098686718854324913205273277837107275197779266203956111447917954217642996612375426900185362566372715775684730383657923112702380810451305560067414494793397392647318953106387697001580454130672044011060132072400728672015125332880303053556556640562753160804196189095016248121783366388642672259225712092  
'''

• 注意给出了hint1,hint2,二元二次方程组，可以用z3解出a,b

from z3 import *

hint1 = ...
hint2 = ...
s = Solver()

a,b = Ints('a b')
s.add(a**2 + a*b == hint1)
s.add(b**2 + a*b == hint2)
if s.check() == sat:
    m = s.model()
    print(m[a], m[b])
# a= 217562055747111316427029035559575901669 
# b= 293227681709108659093110186239101833877

• 然后直接套板子即可，但是对于sage来说libnum是外部库，要到sageShell下载，但是直接用

sage -python -m pip install libnum-i https://pypi.tuna.tsinghua.edu.cn/simple

会报错，要加上

--trusted-host pypi.tuna.tsinghua.edu.cn

exp

n = 96294984374753089080583610747240203389088051930341615602841335596072081913930052484580770899610689065293206976889303327507604080242460321817406117877072425663471808350427893332726383611142246218026112051129578226014713958882307096859175042839198895428723757405196020266267824586199807170149650434306779718677   
hint1 = 111128465335502483574544230236618721723785067258103368528600651970108082026274
hint2 = 149777690555091648253749138438840244052377948686936166203166372618778229891842
c1 = 19258639302759286032385037035129183959148363633353536085988651266927081471573889078520697158985164250184287591219408939982288951952002632371950165308028756191357634396067109728491154241759098403135297660541258808223827178690693818047525955978891748361038516201626720292976210372367169577574791733786601438737  
c2 = 94728391095098686718854324913205273277837107275197779266203956111447917954217642996612375426900185362566372715775684730383657923112702380810451305560067414494793397392647318953106387697001580454130672044011060132072400728672015125332880303053556556640562753160804196189095016248121783366388642672259225712092 
e=3

import libnum
import gmpy2
import random
def franklinReiter(n,e,c1,c2,a,b):
    R.<X> = Zmod(n)[]
    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]) # 系数

  # 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 == 0):
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

total = 0x18046866aad5439317601b1de20ad687a

a=217562055747111316427029035559575901669 
b=293227681709108659093110186239101833877
m=franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))
# b'ZcxKh0OHA4nmSOnyeKsfh44P8FukJ6VMmQlXsAAAAASUVORK5CYII='