格密码笔记一

  • Lattice based crypto基于一类新的难题——关于格（lattice）密码学
  • 相比较于其他公钥密码学体系的优势：
    • 加解密更快
    • 可抵抗量子攻击1

1:量子攻击是什么?如何抵抗攻击？ - 知乎 (zhihu.com)

一、“格”

“格”，是一种与向量空间类似的数学空间。

实数空间 R 上的向量空间 V，是一些向量的集合；其中两个向量可以相加、向量可以和一个实数相乘，运算保持封闭。

也就是说，向量空间支持向量加法和标量乘法。而 lattice 与向量空间的区别，就是将标量乘法中的乘数，从实数改为整数。

格可以视为向量的集合，也可以视为点的集合。lattice 上的点排列非常整齐。

二、引例

  • 一个公钥密码学方案

首先，Alice 选择一个大整数 q 作为公共参数。然后选择两个比较小的整数 f,g

满足$f<\sqrt{\frac{q}{2}},\sqrt{\frac{q}{4}}<g<\sqrt{\frac{q}{2}},gcd(f,qg)=1$

亦即 f 的长度大约小于$\frac{q}{2}$ 的一半，g 的长度大约在 $\frac{q}{4}$的一半到 $\frac{q}{2}$的一半之间。从而 f,g 远远小于 q，为 $O(\sqrt{q})$ 。然后要求 f 与 q、g 都互质。

接下来，Alice 计算$h≡f^{−1}g(mod\ q)$

注意到尽管 f 很小，其逆元仍然会很大，于是 h 是 $O(q)$ 。

Alice 的公钥是 h，私钥是 ⟨f,g⟩。

接下来考虑 Bob 如何给 Alice 发送消息。

首先，Bob 有一个小于$\sqrt{\frac{q}{4}}$的明文 m，然后他随机选择整数$ r<\sqrt{\frac{q}{2}}$， 计算$e≡rh+m(mod\ q)$，将 e 作为密文发送给 Alice。

然后 Alice 解密：

先计算$a≡fe(mod\ q)$，然后计算$b≡f^{−1}a(mod\ g)$，其中 f 的逆元也是在模 g 群中的。

我们断言这里求出来的 b，就等于 m.

首先，有 a 满足$a≡fe≡rg+fm(mod\ q)$

我们注意到$ rg+fm<\sqrt{\frac{q}{2}}\sqrt{\frac{q}{2}}+\sqrt{\frac{q}{2}}\sqrt{\frac{q}{4}}<q$，从而知道 a 就是$ rg+fm$ 的真实值，即$a=rg+fm$

接下来，将 a 模 g，分离出$ fm(mod\ g)$，然后乘以 f 的逆元得到 $m(mod\ g)$。而 m 是小于 g 的，所以这个 m 是真实值。

由此，从上面的过程可以看出，最大的跨越在于得到 $rg+fm$ 的真实值。正因为有了 $rg+fm$ 的确切值，才可以模掉 g，从而分开 rg，得到 fm。

加解密代码：

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
import random
from numpy import sqrt, gcd
from gmpy2 import invert

class SimpleScheme():
    
    def __init__(self):
        while True:
            self.q = random.randint(1<<128, (1<<129) - 1)
            self.f = random.randint(1, sqrt(self.q / 2))
            self.g = random.randint(sqrt(self.q / 4), sqrt(self.q / 2))

            if gcd(self.f, self.q * self.g) == 1:
                break
        
        self.h = invert(self.f, self.q) * self.g % self.q
        
        print(f'pk = (q, h) = ({self.q}, {self.h})')
        print(f'sk = (f, g) = ({self.f}, {self.g})')
    
    def enc(self, m):
        assert m < sqrt(self.q/4)
        
        r = random.randint(1, sqrt(self.q / 2))
        e = (r * self.h + m) % self.q
        
        print(f'rg+mf = {r*self.g + m*self.f}')
        
        print(f'e = {r * self.h % self.q} + {m} = {e}')
        
        return int(e)

    def dec(self, e):
        a = self.f * e % self.q
        
        print(f'a = {a}')
        
        b = invert(self.f, self.g) * a % self.g
        
        print(f'b = {b}')

worker = SimpleScheme()
c = worker.enc(114514)
worker.dec(c)

# pk = (q, h) = (514230918051282920692602780404498492433, 115647624614577988455515336107635422730)
# sk = (f, g) = (2405709868378346209, 15028670797073718546)
# rg+mf = 13054637933699032665165943687110631912
# e = 259719708311083043320270690207664511027 + 114514 = 259719708311083043320270690207664625541
# a = 13054637933699032665165943687110631912
# b = 114514

那么敌手Eve如何攻击这个密码体系？

仅仅已知公钥 (q,h)，她并不能找到真正的 (f,g)。但她可以找到一组 (F,G)，如果 (F,G) 在解密时表现与 (f,g) 相同，那么 Eve 就可以完成解密工作。

也就是说，她需要找到 F,G 满足$Fh≡G(mod\ q),F=O(\sqrt{q}),G=O(\sqrt{q})$，那么真正的 (f,g) 就是合法的 (F,G)。

那么，为什么这样的 (F,G) 可以用于解密？

首先，我们有$Fe≡F⋅(rh+m)≡rG+Fm(mod\ q)$，注意到这求出了$rG+Fm$的真实值。继续按照原先的解密算法来操作，模掉 G 获得$Fm(modG)$，乘以 F 的逆元，即可恢复出 m。

也就是说，Eve 只需要找到合法的 (F,G)，就可以攻破这个密码体系。将 $Fh≡G(mod\ R) $改写为等价形式$ Fh=G+qR$，那么 Eve 的任务就是找到足够小的 F,G，使得$F(1,h)−R(0,q)=(F,G)$。这个式子等价于$ (1,h),(0,q) $这两个向量以 F,R 为系数进行线性组合。如果我们能找到合适的 F,R，使得线性组合出来的向量足够短，那么我们就找到了合法的 (F,G) 来攻击密码体系。

上面的问题可以概括为：有两个已知的向量，需要找出一套线性组合系数（必须是整数），来生成一个足够短的向量。

Eve 的任务是：已知 $v1=(1,h)$ 和$ v2=(0,q)$，长度均为 $O(q)$，要寻找它们的线性组合$ w=a1v1+a2v2$，长度为$O(q)$。 要求系数 a1,a2 均为整数。

从 lattice 的角度看，Eve 是在一个 lattice $L$ 中寻找一个很短的向量：$L=\left{a1v1+a2v2:a1,a2∈Z\right}$

在二维的 lattice 里面找最短向量，是有高效算法的（Gauss 的工作）。由此Eve 攻破了这个密码体系。

三、Coppersmith

Coppersmith 可以用于求多项式的小根，经常用于 RSA 攻击中“已知某些二进制位，求剩余位”这一类问题。

Coppersmith解决了这么一个问题：今有一个 e 阶的多项式 f, 那么：

  • 在模 n 意义下，快速求出 $n^{1/e}$ 以内的根
  • 给定 β，快速求出模某个 b 意义下较小的根，其中 $b≥n^β$，是 n 的因数。

一般采用 Sage 实现的 small_roots 方法。

Sage文档

Wikipedia

参考资料：Twenty Years of Attacks on the RSA Cryptosystem

题型一 : hash爆破

1
2
3
4
[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=246bfcbe8c7b0be0a3ee28840a276272ba4416cb650affd846e9f7f2db2820a9
[+]skr[0:5].encode('hex')=c2183d3580
[-]skr.encode('hex')=

▲ 第一阶段。需要找出符合条件的 skr

给出了 skr 的前 5 位，需要找到正确的 skr 使得其 sha256 为给定值。显然直接爆破后三位就行。

1
2
3
4
5
6
7
8
9
10
11
12
def phase1(pre, target):
    pre = codecs.decode(pre.encode(), 'hex')
    for x in itertools.product(range(256), repeat=3):
        skr = pre + b''.join([t.to_bytes(1, 'big') for t in x])
        if hashlib.sha256(skr).hexdigest() == target:
            print(f'find {skr}')
            return codecs.encode(skr, 'hex').decode()

phase1('c2183d3580', '246bfcbe8c7b0be0a3ee28840a276272ba4416cb650affd846e9f7f2db2820a9')

# find b'\xc2\x18=5\x80\x14Q9'
# 'c2183d3580145139'

题型二 : 已知明文高位，求低位

1
2
3
4
5
6
7
8
9
10
11
[+]n=13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517

[+]((m>>72)<<72)=2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

[-]long_to_bytes(m).encode('hex')=

这里给出了 m 的高440位，我们只需要推断剩余的低 72 位。记真实的 m 为$highM+x$，则$m^3−c=(highM+x)^3−c=0$，这个方程的根很小，可以直接求解。

1
2
3
4
5
6
7
8
9
10
11
12
def phase2(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    M = m((m^3 - c).small_roots()[0])
    print(hex(int(M))[2:])

n = 13112061820685643239663831166928327119579425830632458568801544406506769461279590962772340249183569437559394200635526183698604582385769381159563710823689417274479549627596095398621182995891454516953722025068926293512505383125227579169778946631369961753587856344582257683672313230378603324005337788913902434023431887061454368566100747618582590270385918204656156089053519709536001906964008635708510672550219546894006091483520355436091053866312718431318498783637712773878423777467316605865516248176248780637132615807886272029843770186833425792049108187487338237850806203728217374848799250419859646871057096297020670904211
c = 15987554724003100295326076036413163634398600947695096857803937998969441763014731720375196104010794555868069024393647966040593258267888463732184495020709457560043050577198988363754703741636088089472488971050324654162166657678376557110492703712286306868843728466224887550827162442026262163340935333721705267432790268517
high_m = 2519188594271759205757864486097605540135407501571078627238849443561219057751843170540261842677239681908736

phase2(high_m, n, c)
# 464c41477b325e3872736137353839363933666336383963373763356635323632643635343237323432377d

题型三: 已知 p 高位，求低位

1
2
3
4
5
6
7
8
9
10
11
[+]n=12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219

[+]e=65537

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778

[+]((p>>128)<<128)=97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

[-]long_to_bytes(m).encode('hex')=

Coppersmith 可以解决多项式在模 n 的某个因数下的根。我们设$p=pHigh+x$，然后拿去求解方程$p=0(mod\ sth\ divides\ n)$，得到 p 之后即可推出私钥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def phase3(high_p, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = high_p + x
    x0 = p.small_roots(X = 2^128, beta = 0.1)[0]
    
    P = int(p(x0))
    Q = n // P
    
    assert n == P*Q
    
    d = inverse_mod(65537, (P-1)*(Q-1))
    print(hex(power_mod(c, d, n)))
    
n = 12784625729032789592766625203074018101354917751492952685083808825504221816847310910447532133616954262271205877651255598995305639194329607493047941212754523879402744065076183778452640602625242851184095546100200565113016690161053808950384458996881574266573992526357954507491397978278604102524731393059303476350167738237822647246425836482533150025923051544431330502522043833872580483142594571802189321599016725741260254170793393777293145010525686561904427613648184843619301241414264343057368192416551134404100386155751297424616254697041043851852081071306219462991969849123668248321130382231769250865190227630009181759219
c = 627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778
high_p = 97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

phase3(high_p, n, c)

题型四: 已知 d 低位，求 p, q

1
2
3
4
5
6
7
8
9
10
11
[+]n=92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183

[+]e=3

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530

[+]d&((1<<512)-1)=787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955

[-]long_to_bytes(m).encode('hex')=

既然已知 d 的低位，也就是已知 d 在模 $2^{512}$ 意义下的值，又有 e=3

我们考虑等式

$ed≡1(mod\ (p−1)(q−1))$

$3d=1+k⋅(p−1)(q−1)\ where\ k<3$

两边对 $2^{512}$ 取模，有

$3⋅dLow≡1+k⋅(n−p−q+1)\ (mod\ 2^{512})$

以 $\frac{n}{p}$ 代替 q，使上面的方程成为单变量的：

$3⋅dLow⋅p≡p+k⋅(np−p^2−n+p)\ (mod\ 2^{512})$

这个方程是模意义下的一元二次方程，是可解的。解出来之后得到了 p 的低位，通过与 题型三类似的方式可以得到 p,q.

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
def getFullP(low_p, n):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = x*2^512 + low_p
    root = (p-n).monic().small_roots(X = 2^128, beta = 0.4)
    if root:
        return p(root[0])
    return None
    
def phase4(low_d, n, c):
    maybe_p = []
    for k in range(1, 4):
        p = var('p')
        p0 = solve_mod([3*p*low_d  == p + k*(n*p - p^2 - n + p)], 2^512)
        maybe_p += [int(x[0]) for x in p0]
    print(maybe_p)
    
    for x in maybe_p:
        P = getFullP(x, n)
        if P: break
    
    P = int(P)
    Q = n // P
    
    assert P*Q == n
    
    d = inverse_mod(3, (P-1)*(Q-1))
    print(hex(power_mod(c, d, n))[2:])
    


n = 92896523979616431783569762645945918751162321185159790302085768095763248357146198882641160678623069857011832929179987623492267852304178894461486295864091871341339490870689110279720283415976342208476126414933914026436666789270209690168581379143120688241413470569887426810705898518783625903350928784794371176183
c = 56164378185049402404287763972280630295410174183649054805947329504892979921131852321281317326306506444145699012788547718091371389698969718830761120076359634262880912417797038049510647237337251037070369278596191506725812511682495575589039521646062521091457438869068866365907962691742604895495670783101319608530
low_d = 787673996295376297668171075170955852109814939442242049800811601753001897317556022653997651874897208487913321031340711138331360350633965420642045383644955

phase4(low_d, n, c)
# 464c41477b325e3872736135616230383637343566366563373435363139613862363566653465633536307d

题型五: 广播攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
[+]e=3
[+]m=random.getrandbits(512)

[+]n1=78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
[+]c1=pow(m,e,n1)=23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860

[+]n2=98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
[+]c2=pow(m,e,n2)=72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676

[+]n3=91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
[+]c3=pow(m,e,n3)=22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616

[-]long_to_bytes(m).encode('hex')=

相同的消息用三个不同的公钥加密，且 e=3，直接通过中国剩余定理得到 $e^3 $的确切值，开根号即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def phase5(n1, c1, n2, c2, n3, c3):
    r = CRT([c1, c2, c3], [n1, n2, n3])
    m = int(r)^(1/3)
    print(hex(m)[2:])
    
n1 = 78642188663937191491235684351005990853149481644703243255021321296087539054265733392095095639539412823093600710316645130404423641473150336492175402885270861906530337207734106926328737198871118125840680572148601743121884788919989184318198417654263598170932154428514561079675550090698019678767738203477097731989
c1 = 23419685303892339080979695469481275906709035609088426118328601771163101123641599051556995351678670765521269546319724616458499631461037359417701720430452076029312714313804716888119910334476982840024696320503747736428099717113471541651211596481005191146454458591558743268791485623924245960696651150688621664860
n2 = 98174485544103863705821086588292917749386955237408645745685476234349659452606822650329076955303471252833860010724515777826660887118742978051231030080666542833950748806944312437614585352818344599399156268450521239843157288915059003487783576003027303399985723834248634230998110618288843582573006048070816520647
c2 = 72080679612442543693944655041130370753964497034378634203383617624269927191363529233872659451561571441107920350406295389613006330637565645758727103723546610079332161151567096389071050158035757745766399510575237344950873632114050632573903701015749830874081198250578516967517980592506626547273178363503100507676
n3 = 91638855323231795590642755267985988356764327384001022396221901964430032527111968159623063760057482761918901490239790230176524505469897183382928646349163030620342744192731246392941227433195249399795012672172947919435254998997253131826888070173526892674308708289629739522194864912899817994807268945141349669311
c3 = 22149989692509889061584875630258740744292355239822482581889060656197919681655781672277545701325284646570773490123892626601106871432216449814891757715588851851459306683123591338089745675044763551335899599807235257516935037356212345033087798267959242561085752109746935300735969972249665700075907145744305255616

phase5(n1,c1,n2,c2,n3,c3)
# 464c41477b325e3872736138633566336366663462633039353334396665633635666332323633653837387d

题型六: Franklin-Reiter 相关消息攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[+]n= 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061


[+]e=3


[+]m=random.getrandbits(512)


[+]c=pow(m,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308


[+]x=pow(m+1,e,n)=112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175


[-]long_to_bytes(m).encode('hex')=

注意到 m 是下面方程组的解：

于是 (x−m) 是这两个多项式的公因式。把两个多项式求 gcd，即可得到 m.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = 113604829563460357756722229849309932731534576966155520277171862442445354404910882358287832757024693652075211204635679309777620586814014894544893424988818766425089667672311645586528776360047956843961901352792631908859388801090108188344342619580661377758180391734771694803991493164412644148805229529911069578061
c1 = 112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021533447981943498594790549326550460216939216988828130624120379925895123186121819609415184887470233938291227816332249857236198616538782622327476603338806349004620909717360739157545735826670038169284252348037995399308
c2 = 112992730284209629010217336632593897028023711212853788739137950706145189880318698604512926758021552486915464025361447529153776277710423467951041523831865232164370127602772602643378592695459331174613894578701940837730590029577336924367384969935652616989527416027725713616493815764725131271563545176286794438175
e = 3

# c1 = m^e
# c2 = (m+1)^e

R.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+1)^e - c2

def myGcd(x, y):
    if y == 0:
        return x.monic()
    return myGcd(y, x%y)

v = myGcd(g2, g1)
M = n - v.coefficients()[0]

assert g1(M) == 0
print(hex(M))
# 0x464c41477b325e3872736133393863663864663763323636363162623763623635623262396661653235657d

题型七: Boneh Durfee 攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L

[+]d=random.getrandbits(1024*0.270)

[+]e=invmod(d,phin)

[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL

[+]m=random.getrandbits(512)

[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL

[-]long_to_bytes(m).encode('hex')=

知道 e，另外 $≤n^{0.27}$， 查阅资料知使用 Boneh and Durfee attack。 现成脚本：(https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage)

Python3 版本：

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
import time

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print (a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print ("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        print ("We do not have det < bound. Solutions might not be found.")
        print ("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print ("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
        print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print ("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print ("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print ("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        print ("no independant vectors could be found. This should very rarely happen...")
        return 0, 0
    
    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        print ("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27
    # the public exponent
    e = 0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bb

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = 0.280 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(1/2))    # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print ("=== checking values ===")
        print ("* delta:", delta)
        print ("* delta < 0.292", delta < 0.292)
        print ("* size of e:", int(log(e)/log(2)))
        print ("* size of N:", int(log(N)/log(2)))
        print ("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print ("=== running algorithm ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
        print ("=== solution found ===")
        if False:
            print ("x:", solx)
            print ("y:", soly)

        d = int(pol(solx, soly) / e)
        print ("private key found:", d)
    else:
        print ("=== no solution was found ===")

    if debug:
        print("=== %s seconds ===" % (time.time() - start_time))

if __name__ == "__main__":
    example()

　　最终拿到 flag: flag{b12a39f1-b96b-4a46-8bc7-7c3871242b9c}

参考：