Franklin-Reiter攻击

(Updated: )

Franklin-Reiter攻击

群友发了个题目看，顺便复习一下相关的攻击方式

该攻击方法要求当前明文m1和m2要存在线性关系，形如 m1 = a * m2 + b 并且给出了c1,c2,形如

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

那么在知道部分条件的情况下就可以解决这个攻击

原理

Franklin-Reiter攻击

板子（e较小的情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#sage
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)

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#2023 SICTF#Round2-签到题来咯！
from secret import flag
from  Crypto.Util.number import *

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
e = getPrime(10)
n = p*q
c1 = pow(114*m+2333,e,n)
c2 = pow(514*m+4555,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
'''
n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931
'''

在本题中，我们把c1和c2的式子合并一下就可以得到一个m1和m2的线性关系的式子，所以采取关联信息攻击

在这里e不知道，爆破一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#sage
from Crypto.Util.number import *
import binascii
n = 18993579800590288733556762316465854395650778003397512624355925069287661487515652428099677335464809283955351330659278915073219733930542167360381688856732762552737791137784222098296804826261681852699742456526979985201331982720936091963830799430264680941164508709453794113576607749669278887105809727027129736803614327631979056934906547015919204770702496676692691248702461766117271815398943842909579917102217310779431999448597899109808086655029624478062317317442297276087073653945439820988375066353157221370129064423613949039895822016206336117081475698987326594199181180346821431242733826487765566154350269651592993856883
c1 = 3089900890429368903963127778258893993015616003863275300568951378177309984878857933740319974151823410060583527905656182419531008417050246901514691111335764182779077027419410717272164998075313101695833565450587029584857433998627248705518025411896438130004108810308599666206694770859843696952378804678690327442746359836105117371144846629293505396610982407985241783168161504309420302314102538231774470927864959064261347913286659384383565379900391857812482728653358741387072374314243068833590379370244368317200796927931678203916569721211768082289529948017340699194622234734381555103898784827642197721866114583358940604520
c2 = 6062491672599671503583327431533992487890060173533816222838721749216161789662841049274959778509684968479022417053571624473283543736981267659104310293237792925201009775193492423025040929132360886500863823523629213703533794348606076463773478200331006341206053010168741302440409050344170767489936681627020501853981450212305108039373119567034948781143698613084550376070802084805644270376620484786155554275798939105737707005991882264123315436368611647275530607811665999620394422672764116158492214128572456571553281799359243174598812137554860109807481900330449364878168308833006964726761878461761560543284533578701661413931
E=[]

def franklinReiter(n,e,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = (114*X+2333)^e - c1
    f2 = (514*X+4555)^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)

 
for i in range(2^9,2^10):
    if isPrime(i):
        E.append(i)
        
for e in E:
    m=franklinReiter(n,e,c1,c2)
    flag = long_to_bytes(int(m))
    if b'SICTF' in flag:
        print(flag)
        break
#b'SICTF{hhh!!franklin_reiter_is_easy}'

变种1（e较大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
flag=b'***********************'
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
s = getPrime(512)
n = p*q
e = 65537
N = r*s
c=pow(m,e,N)
hint=pow(2*n-m,e,N)
print("c=",c)
print("hint=",hint)
print("n=",n)
print("N=",N)

#c= 43423259937720066480242410526037389734571893127158233205737545043602193683218952791597974839200703121553143890730144526413655108545977821189710879408898644701513344608064565504835818250834830946068290342466474835847253410119959543697202410717599632660251368457331495123509744140359426727527159405849222042904
#hint= 89537408314628349360681080619200657586241472538131163588783156955363783938404653920858723523923816459939025368445559319678708590708447372760960717580102364538146808058244182943711216634553435802209993315675850991445302288452001520355914988818746892371521355287514190070845238469510131978354461286857156484121
#n= 96057998051371812919914259081675081604252517298501757815284793426110918357966765942391148507280051300098320736867050151134371603055535299365601258161010775195220785961631344762299227895001117209392625701969565546911778685726924433390650031008333418731518891577294501764604134694827909301545655417944252385457
#N= 95181714079493329531165311913904927118650797513377627413903416782105479156418795803026947805144779310353978629552614854588095189968968837714554428210176704918400033966916106360194840969634589344847367250484955828002283022190696454537908315916133149984631966651777998417569331796811800254259365688365260226819

改了一下变量的命名，但实际上还是线性关联攻击

1
2
c=pow(m,e,N)
hint=pow(2*n-m,e,N)

所以实际上我们需要构造的多项式即

1
2
f = x^e - c1
g = (2*n1 - x)^e - c2

但是这里的e非常大，常规的关联攻击要打很久才能出

这里套一个half-gcd的板子

多项式 gcd 的正确姿势：Half-GCD 算法 - whx1003 - 博客园

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#sage
from Crypto.Util.number 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 = 96057998051371812919914259081675081604252517298501757815284793426110918357966765942391148507280051300098320736867050151134371603055535299365601258161010775195220785961631344762299227895001117209392625701969565546911778685726924433390650031008333418731518891577294501764604134694827909301545655417944252385457
n2 = 95181714079493329531165311913904927118650797513377627413903416782105479156418795803026947805144779310353978629552614854588095189968968837714554428210176704918400033966916106360194840969634589344847367250484955828002283022190696454537908315916133149984631966651777998417569331796811800254259365688365260226819
c1 = 43423259937720066480242410526037389734571893127158233205737545043602193683218952791597974839200703121553143890730144526413655108545977821189710879408898644701513344608064565504835818250834830946068290342466474835847253410119959543697202410717599632660251368457331495123509744140359426727527159405849222042904
c2 = 89537408314628349360681080619200657586241472538131163588783156955363783938404653920858723523923816459939025368445559319678708590708447372760960717580102364538146808058244182943711216634553435802209993315675850991445302288452001520355914988818746892371521355287514190070845238469510131978354461286857156484121

R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (2*n1 - x)^e - c2

res = GCD(f,g)
print(long_to_bytes(int(-res.monic().coefficients()[0])))
#'flag{a7d2ffde-7161-474a-ba21-6533620d2d58}'

变种2 ci = (aim + bi)e (mod  ni)

后续再补充罢了