Digd0g's Blog

Coppersmith定理

发表于 更新于 分类于 ，
本文字数： 1.2k 阅读时长 ≈ 4 分钟
       
-------------已经到底啦！-------------
 

*Coppersmith*
它的用途主要是找到多项式方程小值根,该求根算法本质上基于Lenstra，lenstra和lovasz给出的著名的LLL约化基算法

Coppersmith的结论不同于传统的格基约化在密码分析中的应用方法。第一，他的结论是在非线性的情况下考虑的，而传统的方法通常是线性的；第二，若将 Coppersmith 的攻击方法推广到多变元的情况，则该方法是启发式的。也就是说推广后的结论依赖于一个假设条件，但是该假设条件在实际应用中基本可以得到满足。

好了，目前为止我们已经知道Coppersmith算是RSA里面门槛蛮高的算法了，开始之前还是有很多要说的，当然光凭我的一篇拙论很难搞懂，建议搭配其他文章阅读。

Factoring with High Bits Known

首先先来了解一下RSA中的高位分解——当我们知道一个公钥中模数 N 的一个因子的较高位时，我们就有一定几率来分解 N。

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

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
hint1 = (p >> 128)<<128 
hint2 = p >> 128 
hint3 = p&(1 >> 128)-1
hint4 = p^((1<<900)-1)
print("p: %d\nq: %d"%(p,q))
print("")
print("hint1: %d\nhint2: %d\nhint4: %d\nhint3: %d"%(hint1,hint2,hint3,hint4))


p原本512bit但是(p >> 128)<<128时低128bit未知，这种情况我们称作p高位已知

为了更直观地对比，这里我把p和hint1截取了一下。可以看到p和p_high 的区别在于尾数不同，这就是所谓的高比特位相同但是低比特位由于二进制移位而发生了改变。

p和p_high都是154bits,高比特位有115bits，低比特位39bits.

hint2中p未知的二进制位数达到了 128

1
2
3
4
5
6
7
8
9
10
p = 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165 569022454807609001623119788467130139311

p_high = 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165 426184535223597456821873194001145790464 #hint1

hint2: 27452371801451037018511721067197827374680822064418745258798259123443933200806816038160568641586718215423031102731319

hint4: 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165569022454807609001623119788467130139311

hint3: 8452712498170643941637436558664265704301557216577944354047371344426782440907597751590676094202515006314790319892114049520559506760656753529663172024680615871725227215021223196330336218089891573548938467806048528656646134120401770655845327925464974622209497505896677834064

$$
在log(N)和\frac{1}{\epsilon}相关的时间复杂度内分解N需要满足以下条件
$$

已知p高位多少位才可以进行攻击

sage 里面的 small_roots 能实现上述的给出已知的p高位进行分解N的函数方法，利用LLL算法求解非线性低维度多项式方程小根的方法
$$
Coppersmith证明了在已知p和q部分比特的情况下，若q和p的未知部分的上界 X 和 Y 满足 XY <= N ^ {0.5} 则Ｎ的多项式可以被分解。
$$

$$
总而言之就是，存在一个e阶多项式f，在模n意义下，快速求出n^{1/e}以内的根\给定\beta(n的因数)求出模b下较小的根，其中b \geq n^{\beta}
$$
先上一道不知从哪扒来的例题看一下吧

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
import gmpy2 
import random 
from Crypto.Util.number import getPrime 
from Crypto.PublicKey import RSA 
def generate_public_key(): 
	part1 = 754000048691689305453579906499719865997162108647179376656384000000000000001232324121 		part1bits = part1.bit_length() 
    lastbits = 512 - part1.bit_length() 
    part1 = part1 << lastbits 
    part2 = random.randrange(1, 2**lastbits) 
    p = part1 + part2 
    while not gmpy2.is_prime(p): 
        p = part1 + random.randrange(1, 2**lastbits) 
    q = getPrime(512) 
    n = p * q 
    print p 
    print q 
    e = 0x10001 
    key = RSA.construct((long(n), long(e))) 
    key = key.exportKey() 
    with open('public.pem', 'w') as f: 
        f.write(key) 
def encrypt(): 
    flag = open('./flag.txt').read().strip('n') 
    flag = flag.encode('hex') 
    flag = int(flag, 16) 
    with open('./public.pem') as f: 
        key = RSA.importKey(f) 
        enc = gmpy2.powmod(flag, key.e, key.n) 
    with open('flag.enc', 'w') as f: 
        f.write(hex(enc)[2:]) 
generate_public_key() 
encrypt()

#n=0x639386F4941D1511D89A9D19DC4731188D3F4D2D04623FB26F5A85BB3A54747BCBADCDBD8E4A75747DB4072A90F62DCA08F11AC276D7588042BEFA504DCD87CD3B0810F1CB28168A53F9196CDAF9FD1D12DCD4C375EB68B67A8EFCCEC605C57C736943170FEF177175F696A0F6123B993E56FFBF1B62435F728A0BAC018D0113 
#e=0x10001


我们已知的part1的比特位为279位，距离我们的条件还差9位左右，我们还需要爆破 9 位左右的数据。
由于 9 位左右的bit需要至少 3 位十六进制(3*4 > 9) 

1
2
kbits = pbits - p4.nbits() 
roots = f.small_roots(X=2^kbits, beta=0.4)
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
from sage.all import * 
import binascii 
n = 0x639386F4941D1511D89A9D19DC4731188D3F4D2D04623FB26F5A85BB3A54747BCBADCDBD8E4A75747DB4072A90F62DCA08F11AC276D7588042BEFA504DCD87CD3B0810F1CB28168A53F9196CDAF9FD1D12DCD4C375EB68B67A8EFCCEC605C57C736943170FEF177175F696A0F6123B993E56FFBF1B62435F728A0BAC018D0113 
cipher = 0x56c5afbc956157241f2d4ea90fd24ad58d788ca1fa2fddb9084197cfc526386d223f88be38ec2e1820c419cb3dad133c158d4b004ae0943b790f0719b40e58007ba730346943884ddc36467e876ca7a3afb0e5a10127d18e3080edc18f9fbe590457352dca398b61eff93eec745c0e49de20bba1dd77df6de86052ffff41247d 
e2 = 0x10001 
pbits = 512 
for i in range(0,4095): 
    p4 = 0x635c3782d43a73d70465979599f65622c7b4242a2d623459337100000000004973c619000 
    p4 = p4 + int(hex(i),16) 
    kbits = pbits - p4.nbits() #未知需要爆破的比特位数 
    p4 = p4 << kbits 
    PR.<x> = PolynomialRing(Zmod(n)) #生成一个以x为符号的一元多项式环
    f = x + p4 #定义求解的函数
    roots = f.small_roots(X=2^kbits, beta=0.4) #进行爆破  多项式小值根求解及因子分解 X：表示求解根的上界beta即是前面提到的 β ，当p,q二进制位数相同时一般只能取 0.4；
    #print roots 
    if roots: #爆破成功，求根 
        p = p4+int(roots[0]) 
        assert n % p == 0 
        q = n//int(p) 
        phin = (p-1)*(q-1) 
        d = inverse_mod(e2,phin) 
        flag = pow(cipher,d,n) 
        flag = hex(int(flag))[2:-1] 
        print binascii.unhexlify(flag)

$$
回到初始，hint1中(p >> 128)<<128 给出了p的高384位，需要我们推理出未知的低128位.记原p为p_{high}+x \
求解方程p=0(mod \quad sth \quad divides \quad n)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#已知 p 高位，求低位
def phase(high_p, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    p = high_p + x
    roots = p.small_roots(X = 2^128, beta = 0.1)[0]
    
    P = int(p(roots))
    Q = n // P
    
    assert n == P*Q
    
    d = inverse_mod(65537, (P-1)*(Q-1))
    print(hex(power_mod(c, d, n)))
    
n = 65941249956454045900925748110344885155578849459761886289551541848033080705473468411505136530336561460230704780102762179334949928987017294170942951738408512582341934721650026103527287094659147263380069441023677649037769806095851547697740578588236302465290071838541989837695241059034636247243505104997008048433
c = 627824086157119245056478875800598959553774250161670787506083253960788230737588761787385686125828765665617567887904228030839535317987589608761534500003128247164233774794784231518212804270056404565710426613938264302998015421153393879729263551292024543756422702956470022959537221269172084619081368498693930550456153543628170306324206266216348386707008661128717431426237486511309767286175518238620230507201952867261283880986868752676549613958785288914989429224582849218395471672295410036858881836363364885164276983237312235831591858044908369376855484127614933545955544787160352042318378588039587911741028067576722790778
p_high = 97522826022187678545924975588711975512906538181361325096919121233043973599759518562689050415761485716705615149641768982838255403594331293651224395590747133152128042950062103156564440155088882592644046069208405360324372057140890317518802130081198060093576841538008960560391380395697098964411821716664506908672

phase(p_high, n, c)

参考：

https://ctf-wiki.org/crypto/asymmetric/rsa/rsa_coppersmith_attack/

https://github.com/mimoo/RSA-and-LLL-attacks

https://www.jianshu.com/p/d8d2ce53041b

https://blog.csdn.net/qq_51999772/article/details/123620932