Coppersmith's Attack

使用SageMath尝试Coppersmith’s Attack

Sage的small_root方法

N = 10001
K = Zmod(10001)
P.<x> = PolynomialRing(K)
f = x^3 + 10*x^2 + 5000*x - 222
print f.small_roots()
[4]

http://sage-doc.sis.uta.fi/reference/polynomial_rings/sage/rings/polynomial/polynomial_modn_dense_ntl.html#sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots

p的高位或低位已知时

Sage的small_root方法b >= N^β可以找到以N的除数b为模的解。在此,模数为N的解就是β = 1这种情况。 考虑到公钥n是RSA中相同位数的p和q的乘积,可以通过设置β = x度数来求b = p or q模解,满足n ^ x < p,暂设x=0.3

已知p的高位是n的位数的1/4,即p的位数的约1/2时,将其余位设置为0, 设为pbar

此时f(x) = x + pbar = 0 (mod b),可以通过求出满足的f(x)的值x0,即p = x0 + pbar

p = 0x00f23799c031b942026e420769b74d22fa2114428189139c43c366c6ab8367c6b3d6f821449aafb2058b0e6ed964fa0ad45fb306f96376e80823a72b58101919e50acad3b5e6d079e7ff9218ed6df6edbef536742714ce88b2e717f45af53ef0d04c89faf01c80b28e764973aba27726c85c0236e8756a865c03577722bac5e391
q = 0x00c9d24330fa4945cfe1e5d6912d6bde0231035a1cc8d8ae67d949347b895f8d579bce2adaf37c568957b17a6564dbf80d36d81e4622ab30e02132b0155aefbd3912a27c625a9b7b05bc72217039f5aa88c20cbf9871c3228e9d80d9106f94b11c1f50c40c96862b5cd6b6f781883dd2eff80a059d3ca027af6a03edeb34a7390f
n = p*q

beta = 0.5
epsilon = beta^2/7

pbits = p.nbits()
kbits = floor(n.nbits()*(beta^2-epsilon))
pbar = p & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar

print p
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]  # find root < 2^kbits with factor >= n^0.3
print x0 + pbar

运行结果:upper 586 bits (of 1024 bits) is given

betaX参数的作用是缩小范围,限制了n ^ 0.3 < px0 < 2 ^ kbits

即使知道了低位而不是高位,也可以通过使用多项式来恢复p的值。

当秘密密钥d的低位已知时

若e较小,对于秘密密钥d,如果已知低位,大约是n位的1/4,则可以恢复d的值。称为部分密钥暴露攻击。

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
    e = 3
    d = 0x7f4dbb449cc8aa9a0cb73c2fc7b1372da924d7b46c8a710c93e9281c010faaabfd8bec59ef47f5702648925cccc284099d138b33ad65a8a54db425a3c1f5b0b4f5cac22273b13cc617aed340d98ec1af4ed5206be011097c459726e72b7459192f35e1a8768567ea46883d30e7aaabc1fa2d8baa62cfcde93915a4a809bc3e9547bb07e1ecca16e51078312e89f0561e31b55db8b0ea5bc87a6ca7464a3d7c28a68c60e2ba88fe6a7d2b300d723e549910a987da89fc0a1c0de197a3d62c501b1f0e819891b1c32a0d6c233f2a285df87bb9e5c6c72d983ff3e706696bba639f573f9c3646968f02f3a615a438e20bb7c38d53621079f2899547a95350f3abeb

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

运行结果:lower 585 bits (of 2048 bits) is given

当知道明文m的高位或低位时

若e较小,当已知明文m的高位为n位数的(1-1 / e)时,其余位设置为0,设为 mbar。当对应的密文为c时,f(x) = (mbar + x)^e - c (mod n)可以通过获得以下公式的解来获得满足此要求的f(x)的值,即m。这b = n是因为是这种情况β = 1

n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
e = 3

m = randrange(n)
c = pow(m, e, n)

beta = 1
epsilon = beta^2/7

nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
mbar = m & (2^nbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c

print m
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print mbar + x0

运行结果:upper 1658 bits (of 2048 bits) is given

这个例子中 e=3,公式kbits = floor(nbits*x)其中x最大不超过0.25 至少要已知1536个字符

例题

广外rsa2

已知n,p的高位576位,要求出完整的p

from sage.all import *
n = 0xeb4f8c45336c229371fd73a252b24dd3bf8b3cdc1bb1864f140fd63c88d47c44ba228bebe223fe53c7eaf88678b780821a6660b2726506216554990a5dda178ee04a47c7f1974fc8f8268d081bbb2be7e7353ccf36fecfce5f5f82722d064928f2d60844373c52b4d1db9dc41f7f16807c5b4356c4d2290811e25c51ef1227aa6e893d37dd8743e391fa638d77d0c55e4fb331576602128333d4be95f06523521e7511b39fc20111c88f2635b67e3531684d58ea6574179b5e63a862d073241f5ff91c97a45aa3d8e3287d8161a97728d2e19d72669f39f9e6ad10677bb563bdef30d0dcfa719c2f1836bd02b73d21dbecc11717b54c45d415d3f423ce6dfd8dL
p2 =0xfb2151c701f7667b53822fe625b95edee00c3a947b234eca47903ef62fb128d813a9c1acb328f3f7181d24ce31814cd1a69ac4b61b269e2b0eb7fbaabe9633d33a36d0715b4cd386L

e = 0x10001
pbits = 1024

kbits = 448
p2 = p2 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p2
roots = f.small_roots(X=2^kbits, beta=0.4)

if roots:        
    p = p2+int(roots[0]) 
    print "n: ", n   
    print "p: ", p
    print "q: ", n/p

如果已知位数不足576位,可以爆破所缺位的二进制,达到576位了再用算法恢复完整的p

高校运维

题目给了enc,n,e

from flag import FLAG
from Crypto.Util.number import *
import os
import gmpy2

p = getPrime(2048)
q = gmpy2.next_prime(bytes_to_long(os.urandom(32)*8))
n = p*q
e = 65537

m = bytes_to_long(FLAG)
enc = pow(m,e,n)

with open("enc","wb") as f:
    f.write(str(enc)+"\n")
    f.write(str(n)+"\n")

爆破减去 next_prime的产生的偏移,os.urandom(32)得到的32字节是mod p方程的小根

已知bytes_to_long(os.urandom(32)*8)会是bytes_to_long(('\x00'*31+'\x01')*8)的倍数,设t = bytes_to_long(('\x00'*31+'\x01')*8)

通过小根求出来的r和i=1452,得到p=(r*t+1452),monic表示首一

n=120807710153113702551615579080626349972702435654213602643278178850601270671946229285821528380336690426317604059622034599839001416930715968066016772516322170847232613450387418879151680919583407733398280475244970196660246303755390654445483988806163997943960045202300170321033632884706732013873256539789027552900587666422370948750842536533923935656875965991272731558533581897633592458155859972323709278905289729445241014357315813048740496355157322217479024997808766708783034169626351658483634985294355975778256304622956911622334081421352132051371869608818591717661111189285407351900021893457439899221542567630909004930602528901255429064258255953091799356807896508016798627878778491866567622281528441807056062152648122769596905617532839645811871242955534491003544450002957748265702306031022676181061669831693628120952508570252446308607118097142440911574131249381253267168309302968966178203572103064042325655007707720847432033652545364390235670894288288369956445797446648862192044259720010703057599068467348014822871417162946598110099990800849922664801383108437169282005803013729663209291895365964487113632471631243676196750054390014101920098216264290734689252677221687512705895162185620154778448467145374612676883160397044672382343419867
t=bytes_to_long(('\x00'*31+'\x01')*8)
K = Zmod(n)
P.<x> = PolynomialRing(K)
for i in range(1452,1453):
    f= x * t +i
    r =f.monic().small_roots(beta=0.45)
    if r:
        print i,r
        p = r * t + i
        print p

sage运行得到

1452 [25097212148084861298779072266686287643405205222520917844564707998487462593163]

求出p,q,得到flag

参考链接

http://inaz2.hatenablog.com/entries/2016/01/20

https://www.jianshu.com/p/e407be39a22b
https://github.com/mimoo/RSA-and-LLL-attacks
https://code.felinae98.cn/ctf/crypto/rsa%E5%A4%A7%E7%A4%BC%E5%8C%85%EF%BC%88%E4%BA%8C%EF%BC%89coppersmith-%E7%9B%B8%E5%85%B3/

https://xz.aliyun.com/t/6813


文章作者: hh
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 hh !
 上一篇
Thinkphp < 6.0.2 session id未作过滤 Thinkphp < 6.0.2 session id未作过滤
漏洞版本环境2020年1月13号,Thinkphp 6.0.2发布,在详情页指出修复了一处Session安全隐患。 ➜ htdocs composer create-project topthink/think tp 将 composer
2020-01-23
下一篇 
d3ctf writeup d3ctf writeup
easyweb(二次注入)看一下控制器,就user.php和file.php ci框架+smarty模版,猜测可能是模版注入 查找一下smarty的display()函数,在user.php的index里的display参数可控 //use
2019-11-24
  目录