2020纵横杯 comon-Extending Wiener attack

Posted on Edited on In Word count in article: 4.2k Reading time ≈ 4 mins.

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

e1 =  28720970875923431651096339432854172528258265954461865674640550905460254396153781189674547341687577425387833579798322688436040388359600753225864838008717449960738481507237546818409576080342018413998438508242156786918906491731633276138883100372823397583184685654971806498370497526719232024164841910708290088581
e2 =  131021266002802786854388653080729140273443902141665778170604465113620346076511262124829371838724811039714548987535108721308165699613894661841484523537507024099679248417817366537529114819815251239300463529072042548335699747397368129995809673969216724195536938971493436488732311727298655252602350061303755611563
N =  159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781117564072817251103154968492955749973403646311198170703330345340987100788144707482536112028286039187104750378366564167383729662815980782817121382587188922253
flag = b"flag{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}"
f1 = bytes_to_long(flag[:21])
f2 = bytes_to_long(flag[21:])
c1 = pow(f1, e1, N)
c2 = pow(f2, e2, N)

print("e1 = ", e1)
print("e2 = ", e2)
print("N = ", N)
print("c1 = ", c1)
print("c2 = ", c2)

分析

这个题一看还以为是简单的Common Attack, 只有同一个明文, 不同的才能用Common Attack 这里显然两个密文对应的不是同一个明文…
这种题估计都有什么攻击方法, 后来找wp看了, 果然是有一种攻击方法的, 把paper(Extending Wiener’s Attack in the Presence of Many Decrypting Exponents)详细的学了一遍, 才明白具体该怎么解,

这个攻击方法适用于特别大, 并且有多个的时候(显然还有大到可以直接winner)
大概思路是造一个格子求出参数让问题转变成winner要解决的问题(连分数的分解), 但是这里是为1的所以不需要连分数可以直接求出phi

构造格子的方法paper里有, 阅读笔记里也有这里就不多说, 直接造!

这里
LLL()规约出基后求phi即可

exp

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
from Crypto.Util.number import long_to_bytes
e1 =  28720970875923431651096339432854172528258265954461865674640550905460254396153781189674547341687577425387833579798322688436040388359600753225864838008717449960738481507237546818409576080342018413998438508242156786918906491731633276138883100372823397583184685654971806498370497526719232024164841910708290088581
e2 =  131021266002802786854388653080729140273443902141665778170604465113620346076511262124829371838724811039714548987535108721308165699613894661841484523537507024099679248417817366537529114819815251239300463529072042548335699747397368129995809673969216724195536938971493436488732311727298655252602350061303755611563
N =  159077408219654697980513139040067154659570696914750036579069691821723381989448459903137588324720148582015228465959976312274055844998506120677137485805781117564072817251103154968492955749973403646311198170703330345340987100788144707482536112028286039187104750378366564167383729662815980782817121382587188922253
c1 =  89410578059910615243542114610890994179298819076294899300341196922537672226283347286177838507350481980653301675042566354947161446918391494634173771489921535378415952543761341962187827617956463740415683816828323475428328607025791449389552492799278886876413138326117622825124519567340298133646090783889193450681
c2 =  106022564245731443282859231814772725680579944691962958987527668508496192529331599682371642691880849071915084510118117099828154554231286326729922119326305261125960484865171940233343041874124811917291652357776045940511178855947892557181650249473057939642726565131933445072147505756108121271288834439942107732015
for epsilon in range(100):
    M1 = int(N^(0.5))
    M2 = int(N^(1+5/14 - (epsilon*0.01)))
    #epsilon是没办法确定的, 小小的爆破一下
    v1 = vector([N,-M1*N,0,N^2])
    v2 = vector([0,M1*e1,-M2*e1,-e1*N])
    v3 = vector([0,0,M2*e2,-e2*N])
    v4 = vector([0,0,0,e1*e2])

    L = Matrix([v1,v2,v3,v4])
    B = L.LLL()[0]
    B = L.solve_left(B)

    phi = floor(e1 * B[1]//B[0])
	# 这边phi会前后差1或者差2
    for j in range(-2,3):
        try:
            d1 = inverse_mod(e1,phi+j)
            d2 = inverse_mod(e2,phi+j)
            flag = long_to_bytes(pow(c1,d1,N)) + long_to_bytes(pow(c2,d2,N))
            if b'{' in flag and b'}' in flag:
                print(i,flag)
        except:
            pass

后记

看完了理论自己代码实现的时候还是会有不少问题的..

这里有一个Matrix.solve_left和Matrix.solve_right的区别, 也没怎么搞懂, 主要是不知道这两个到底什么时候用什么, 只能先每次都试试这两个了.