文章目录
  1. 题目信息
  2. 分析
  3. 解题

题目信息

这个密码系统的开发者在开发过程中使用率很高，也可以说是非常高。 也许他的想法是错的，这个密码系统是非常容易攻破的。

分析

RSA的d很小，但是N有3个因子，使用wiener攻击没破解出来，想用boneh_durfee攻击却发现没法列方程，看了writeup才了解到wiener攻击的变种，论文链接在此；总的来说，记$\{h_{i}/k_{i}\}$是$e/N$的连分数收敛列，常规的wiener攻击中$d=k_{i}$，而在wiener攻击的变种中，$d=s\cdot k_{i}+t\cdot k_{i-1} , s,t \in Z$，一般来说，$d$越大，$s,t$的取值范围也越大。

解题

解题的Python脚本如下：

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
from gmpy2 import is_square,sqrt
from Crypto.Util.number import *
from pwn import pwnlib
from pwnlib.util.iters import mbruteforce

class Wiener(object):
    def __init__(self,N,e,mode):
        self.N=N
        self.e=e
        self.mode=mode
        return

    def next_frac(self):
        hi_1,hi_2=1,0
        ki_1,ki_2=0,1
        a,b=self.e,self.N
        r=1
        while r:
            p,r=divmod(a,b)
            hi=p*hi_1+hi_2
            ki=p*ki_1+ki_2
            hi_1,hi_2=hi,hi_1
            ki_1,ki_2=ki,ki_1
            a,b=b,r
            yield (hi,ki)

    def two(self):
        N,e=self.N,self.e
        for frac in self.next_frac():
            hi,ki=frac
            if hi==0:
                continue
            # f=t^2-(N-(ki*e-1)/hi+1)*t+N ==> delta=[N-(ki*e-1)/hi+1]^2-4*N
            t1=(ki*e-1)%hi
            if not t1:
                t1=N-(ki*e-1)//hi+1
                delta=pow(t1,2)-4*N
                if is_square(delta):
                    t2=int(sqrt(delta))
                    if not (t1-t2)%2:
                        P=(t1-t2)//2
                        Q=(t1+t2)//2
                        return P,Q
        return

    def multi(self,rate):
        N,e=self.N,self.e
        pt=getRandomRange(2,N-1)
        ct=pow(pt,e,N)
        ki_1,ki_2=0,1
        for frac in self.next_frac():
            hi,ki=frac
            ki_1,ki_2=ki,ki_1
            if hi==0:
                continue
            check=lambda rs: pow(ct,int(rs[:rate],2)*ki_1+int(rs[rate:],2)*ki_2,N)==pt
            rs=mbruteforce(check,'01',2*rate,method='fixed')
            if rs:
                return int(rs[:rate],2)*ki_1+int(rs[rate:],2)*ki_2
        return

    def attack(self):
        if self.mode:
            #when there is no solution, maybe you could take greater action, via increase rate.
            return self.multi(4)
        else:
            return self.two()

def solve():
    pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
    n,e,a,g=pubkey
    wiener=Wiener(n,e,1)
    d=wiener.attack()
    c1,c2=(1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)
    k=pow(c1,d,n)
    K=pow(g,k,a)
    return long_to_bytes(c2*inverse(K,a)%a)

if __name__=='__main__':
    print solve()

程序运行结果如下：
1
2
3
4
5
6
$ python solve.py 
[-] MBruteforcing: No matches found
......
[-] MBruteforcing: No matches found
[+] MBruteforcing: Found key: "01110110"
ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}