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

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

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

Factoring with High Bits Known

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

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

p = 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165 569022454807609001623119788467130139311
p_high = 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165 426184535223597456821873194001145790464 #hint1
hint2: 27452371801451037018511721067197827374680822064418745258798259123443933200806816038160568641586718215423031102731319
hint4: 9341558054191386215066345451630726417358808959728962858150369368064732931483299449258725330485809722318563623217165569022454807609001623119788467130139311
hint3: 8452712498170643941637436558664265704301557216577944354047371344426782440907597751590676094202515006314790319892114049520559506760656753529663172024680615871725227215021223196330336218089891573548938467806048528656646134120401770655845327925464974622209497505896677834064

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

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

sage 里面的 small_roots 能实现上述的给出已知的 p 高位进行分解 N 的函数方法,利用 LLL 算法求解非线性低维度多项式方程小根的方法

Coppersmith证明了在已知pq部分比特的情况下,若qp的未知部分的上界XY满足XY<=N0.5则N的多项式可以被分解。Coppersmith证明了在已知p和q部分比特的情况下,若q和p的未知部分的上界 X 和 Y 满足 XY <= N ^ {0.5} 则N的多项式可以被分解。

总而言之就是,存在一个e阶多项式f,在模n意义下,快速求出n1/e以内的根给定β(n的因数)求出模b下较小的根,其中bnβ总而言之就是,存在一个e阶多项式f,在模n意义下,快速求出n^{1/e}以内的根\\给定\beta(n的因数)求出模b下较小的根,其中b \geq n^{\beta}

先上一道不知从哪扒来的例题看一下吧

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)

kbits = pbits - p4.nbits() 
 roots = f.small_roots(X=2^kbits, beta=0.4)
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.记原pphigh+x求解方程p=0(modsthdividesn)回到初始,hint1中(p >> 128)<<128 给出了p的高384位,需要我们推理出未知的低128位.记原p为p_{high}+x \\ 求解方程p=0(mod \quad sth \quad divides \quad n)

#已知 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

更新于

请我喝[茶]~( ̄▽ ̄)~*

1sme 微信支付

微信支付