Franklin-Reiter相关消息攻击

使用条件

m1和m2两个明文存在线性关系如 M₁ ≡ F(M₂) (mod n)，其中F表示类似于ax+b的线性关系，且都在相同的e和n下加密

解密原理

首先,我们知道C₁ ≡ M₁^e(mod n)，并且M₁ ≡ F(M₂)(mod n)，那么我们可以知道M₂是F(x)^e ≡ C₁(mod n)的一个根。同样的M₂是x^e - C₂在模n意义下的一个根。所以说x - M₂同时整除以上两个多项式。因此我们可以求得以上两个多项式的最大公因子，如果最大公因子恰好是线性的话，那么我们就求得了M₂。需要注意的是当 e=3 的情况下，最大公因子一定是线性的。

例题

m1=a*m2+b，c1=pow(m1,e,n)，c2=pow(m2,e,n)

from sage.all import *
from Crypto.Util.number import long_to_bytes
n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720
e=17
def franklinReiter(n,e,c1,c2,a,b):
    x = PolynomialRing(Zmod(n),'x').gen()
    g1 = (x)**e - c1
    g2 = (a*x+b)**e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 
    return -gcd(g1, g2)[0]
'''
使用辗转相除法求多项式的最大公因子
在代数中，一个多项式的首项系数通常被称为该多项式的引导系数（leading coefficient），而将多项式变成首项系数为1的形式被称为将多项式化为首一形式（monic form）
调用函数g1.monic()将g1转换为首一多项式（monic polynomial），并返回该多项式。
使用g.monic()[0]，则会返回g(x)除以引导系数后得到的多项式的常数项
比如：g.monic() = x + 32412345
那么：g.monic()[0] = 32412345
'''
m=franklinReiter(n,e,c1,c2,a,b)
print(long_to_bytes(int(m)))
# flag{a593591a-3749-cc52-0c27-e897fac2c967}

---

c1 = pow(2m+3,17,n) c2 = pow(4m+11,17,n)

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from functools import reduce
from secret import flag, x, y

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

assert(reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x]))
assert(reduce(lambda x,y:x&y,[(j-15)*j+44==0 for j in y]))

print(pow(reduce(lambda x,y:x*m+y,x),17,n))
print(pow(reduce(lambda x,y:x*m+y,y),17,n))

# n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
# c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
# c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450

题目分析

assert(reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x]))

1. [(i-5)*i+6==0 for i in x] 使用列表推导式判断等式是否成立，若成立，返回True，否则False,故列表中最终得到的是[True,True]，
2. 由此可以反推出x = [2,3] (解方程得到)，显然也可以知道下一串中y = [4,11]
3. reduce函数是应用lambda表达式对列表([True,True])中的每一个元素依次进行异或操作
4. PS：“lambda x,y:x&y”中的‘x’与“[(i-5)*i+6==0 for i in x]”中的‘x’并不是同一个

所以能够得到

x = [2,3]
y = [4,11]

看reduce函数，举个例子

x = [1, 2, 3, 4]
result = reduce(lambda x, y: x * y, x)
print(result)

1. 初始时，reduce 函数将列表中的第一个元素 1 作为初始的累积结果 x。
2. 然后，对于列表中的每个元素 y，都将当前的累积结果 x 和该元素 y 传递给匿名函数 lambda x, y: x * y 进行积累操作。
3. 第一次迭代中，x 是 1，y 是 2，所以累积结果是 1 * 2 = 2。
4. 第二次迭代中，x 是 2（上一次的累积结果），y 是 3（列表中的下一个元素），所以累积结果是 2 * 3 = 6。
5. 第三次迭代中，x 是 6，y 是 4，所以累积结果是 6 * 4 = 24。

所以题目中

reduce(lambda x,y:x*m+y,x) = 2*m+3
reduce(lambda x,y:x*m+y,y) = 4*m+11

最终得到

c1 = pow(2*m+3,17,n)
c2 = pow(4*m+11,17,n)

解题代码

n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450
e = 17
def franklinReiter(n,e,c1,c2):
    x = PolynomialRing(Zmod(n),'x').gen()
    g1 = (2*x+3)**e - c1
    g2 = (4*x+11)**e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,c1,c2)
print(long_to_bytes(int(m)))
# flag{r54__r3l473d_m355463_4774ck_4l50_c4ll3d_fr4nkl1n_r3173r_4774ck~}

---

d,e未知，但是中间量存在线性关系

from Crypto.Util.number import *
from sympy import nextprime
import gmpy2
import random

def encode (p1,p2,e):
    not_hint = (p1 + 1) * (p2 + 1)
    S = gmpy2.invert(e, not_hint)
    not_p = S%(p1+1)
    return not_p

flag = b'Neepu{********************}'
flag = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = nextprime(random.randint(1,1000))
d = gmpy2.invert(e, (p-1)*(q-1))
c = pow(flag, e, n)
print(c)
print(n)

m = encode(p, q, e)
c1 = pow(m, 7, n)
c2 = pow(m+e, 7, n)
print(c1)
print(c2)

c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
c1 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
c2 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119

这里的加密关系

c1 = pow(m, 7, n)
c2 = pow(m+e, 7, n)

其中有两个未知数，可以把e直接爆破出来（原文便用到了短填充攻击(Coppersmith’s short-pad attack)的代码，暂时没研究明白）

def attack(c1, c2, n, e):
    x = PolynomialRing(Zmod(n),'x').gen()  # 初始化多项式环，模n的多项式环PR
    g1 = (x)**7 - c1  # 计算g1，即x的7次方减去c1
    g2 = (x+e)**7 - c2  # 计算g2，即(x+e)的7次方减去c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2  # 使用欧几里得算法计算最大公因式
        return g1.monic()  # 返回最大公因式的首项系数为1的最简形式

    return -gcd(g1, g2)[0]  # 返回最大公因式的最简形式的首项系数的负值

c1 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
c2 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543

for e in range(1, 1000):#直接爆破e
    m = attack(c1, c2, n, e)  # 调用attack函数解密密文
    try:
        if pow(m, 7, n) == c1:  # 判断解密是否成功
            print((e, m))  # 打印解密成功的结果
    except:
        pass
#结果：(71, 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859)
#e = 71
#m = 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859

求出m了，根据题目的加密方式 m = s % (p+1) = d % (p+1)，类似于dp泄露

import gmpy2
from Crypto.Util.number import *
e = 71
# m = 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859
c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
# dp = m ,类似的dp
dp = 129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859
for i in range(1,65535):
    p = (dp*e-1)//i-1
    if n%p == 0:
        q = n//p
        d = gmpy2.invert(e, (p - 1) * (q - 1))
        flag = pow(c,d,n)
        print(long_to_bytes(flag))
        break
# Neepu{Have-a-g00d-day12138}

e 比较大的时候的half-gcd算法

from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

这道题比较特殊，e很大，用上面的脚本跑大概要1个小时，这里引入另一种解法,half gcd算法
（这个half gcd算法也没看明白,以后看明白再写一篇）
参考:多项式 gcd 的正确姿势：Half-GCD 算法

常规算法

from Crypto.Util.number import *

e = 65537
n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

def attack(c1, c2):
    PR.<x>=PolynomialRing(Zmod(n2))
    g1 = x^e - c1
    g2 = (n1-x)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
            if(g2.degree() % 100 == 0):
                print(g2.degree())
        return g1.monic()
    return -gcd(g1, g2)[0]

m1 = attack(c1, c2)
flag = long_to_bytes(int(m1))
print(flag)

half gcd算法

from Crypto.Util.number import long_to_bytes
from sage.all import *
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x**m)
    b_top, b_bot = b.quo_rem(x**m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x**(m // 2))
    e_top, e_bot = e.quo_rem(x**(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

x = PolynomialRing(Zmod(n2),'x').gen()
f = x**e - c1
g = (n1 - x)**e - c2

res = GCD(f,g)
print(long_to_bytes(int(-res.monic().coefficients()[0])))

gcd的结果是 ax - b，我们要得到的是x - m，用monic()将ax - b化为首一多项式即x系数位1，如此得到x - m，然后用coefficients()[0]提取到-m，最后再添个符号得到flag。

参考文章Franklin-Reiter相关消息攻击