本文主要是介绍从零开始学RSA：已知dp,dq求解m和CopperSmith定理攻击，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
(11)已知dp,dq求解m
其中关系式如下:
dp=d%(p-1)
dq=d%(q-1)
解题脚本：
#!/usr/bin/python #coding:utf-8 import gmpy2 from Crypto.Util.number import long_to_bytes c = xxx p = xxx q = xxx dp = xxx dq = xxx InvQ=gmpy2.invert(q,p) mp=pow(c,dp,p) mq=pow(c,dq,q) m=(((mp-mq)*InvQ)%p)*q+mq print long_to_bytes(m) 这个题型实在没找到对应的题目，就先只记录一下这种方法吧，说不定以后会遇到。
(12)CopperSmith定理攻击
建议先跳过(12)先看后面的(13)(14)...，等时间充裕的时候再回来好好研究这部分。(12)这部分我写的不是很详细，建议看看后去网上找些其他相关的资料进行学习。
之前已经成功安装了sage，现在我们再来介绍一个工具包“RSA-and-LLL-attacks”，具体的功能在这个目录中的ppt和pdf有详细介绍。下载链接：
RSA-and-LLL-attacks
github.com/mimoo/RSA-and-LLL-attacks
# 01. Stereotyped messages Attack
适用情况：若e较小，并且已知m的高位，则可通过此方法求出完整的m。
什么叫m的高位呢，很简单，比如题目给你m=0x65c46754a7776c8b88867e000000000000000000 前面的部分就是高位，后面的0就是低位，0只是占位的作用并不是真正m的值。
题目: 13-2019强网杯copperstudy---level1
题目给出如下加密脚本参数：
n=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953L
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c451562c816e2303990834c94e580bf0cbd1L
((m>>72)<<72)=0x9e67d3a220a3dcf6fc4742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000L
要求出完整的m的值。
很明显e较小，并且已知了m的高位，我们通过CopperSmith算法的Stereotyped messages Attack获得完整的m。sage解题脚本(交互式输入):
使用在线网站https://sagecell.sagemath.org/
# -*- coding: utf-8 -*-from __future__ import print_functionimport timedebug = True# display matrix picture with 0 and Xdef 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'a += ' 'if BB[ii, ii] >= bound:a += '~'print(a)def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):"""Coppersmith revisited by Howgrave-Grahamfinds a solution if:* b|modulus, b >= modulus^beta , 0 < beta <= 1* |x| < XX"""## init#dd = pol.degree()nn = dd * mm + tt## checks#if not 0 < beta <= 1:raise ValueError("beta should belongs in (0, 1]")if not pol.is_monic():raise ArithmeticError("Polynomial must be monic.")## calculate bounds and display them#"""* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)* we know LLL will give us a short vector v such that:||v|| <= 2^((n - 1)/4) * det(L)^(1/n)* we will use that vector as a coefficient vector for our g(x)* so we want to satisfy:2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)(it's important to use N because we might not know b)"""if debug:# t optimized?print("\n# Optimized t?\n")print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")cond1 = RR(XX^(nn-1))print("* X^(n-1) = ", cond1)cond2 = pow(modulus, beta*mm)print("* N^(beta*m) = ", cond2)print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")# bound for Xprint("\n# X bound respected?\n")print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")print("* X =", XX)cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)print("* M =", cond2)print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")# solution possible?print("\n# Solutions possible?\n")detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)cond2 = RR(modulus^(beta*mm) / sqrt(nn))print("* N^(beta*m) / sqrt(n) = ", cond2)print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")# warning about Xprint("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")## Coppersmith revisited algo for univariate## change ring of pol and xpolZ = pol.change_ring(ZZ)x = polZ.parent().gen()# compute polynomialsgg = []for ii in range(mm):for jj in range(dd):gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)for ii in range(tt):gg.append((x * XX)**ii * polZ(x * XX)**mm)# construct lattice BBB = Matrix(ZZ, nn)for ii in range(nn):for jj in range(ii+1):BB[ii, jj] = gg[ii][jj]# display basis matrixif debug:matrix_overview(BB, modulus^mm)# LLLBB = BB.LLL()# transform shortest vector in polynomial new_pol = 0for ii in range(nn):new_pol += x**ii * BB[0, ii] / XX**ii# factor polynomialpotential_roots = new_pol.roots()print("potential roots:", potential_roots)# test rootsroots = []for root in potential_roots:if root[0].is_integer():result = polZ(ZZ(root[0]))if gcd(modulus, result) >= modulus^beta:roots.append(ZZ(root[0]))#return roots############################################# Test on Stereotyped Messages########################################## print("//")print("// TEST 1")print("")# RSA gen options (for the demo)length_N = 1024 # size of the modulusKbits = 200 # size of the roote = 3# RSA gen (for the demo)p = next_prime(2^int(round(length_N/2)))q = next_prime(p)N = p*qZmodN = Zmod(N);# Create problem (for the demo)K = ZZ.random_element(0, 2^Kbits)Kdigits = K.digits(2)M = [0]*Kbits + [1]*(length_N-Kbits);for i in range(len(Kdigits)):M[i] = Kdigits[i]M = ZZ(M, 2)C = ZmodN(M)^e# Problem to equation (default)P.<x> = PolynomialRing(ZmodN) #, implementation='NTL')pol = (2^length_N - 2^Kbits + x)^e - Cdd = pol.degree()# Tweak thosebeta = 1 # b = Nepsilon = beta / 7 # <= beta / 7mm = ceil(beta**2 / (dd * epsilon)) # optimized valuett = floor(dd * mm * ((1/beta) - 1)) # optimized valueXX = ceil(N**((beta**2/dd) - epsilon)) # optimized value# Coppersmithstart_time = time.time()roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)# outputprint("\n# Solutions")print("we want to find:",str(K))print("we found:", str(roots))print(("in: %s seconds " % (time.time() - start_time)))print("\n")############################################# Test on Factoring with High Bits Known##########################################print("//")print("// TEST 2")print("")# RSA genlength_N = 1024;p = next_prime(2^int(round(length_N/2)));q = next_prime( round(pi.n()*p) );N = p*q;# qbar is q + [hidden_size_random]hidden = 200;diff = ZZ.random_element(0, 2^hidden-1)qbar = q + diff;F.<x> = PolynomialRing(Zmod(N), implementation='NTL');pol = x - qbardd = pol.degree()# PLAY WITH THOSE:beta = 0.5 # we should have q >= N^betaepsilon = beta / 7 # <= beta/7mm = ceil(beta**2 / (dd * epsilon)) # optimizedtt = floor(dd * mm * ((1/beta) - 1)) # optimizedXX = ceil(N**((beta**2/dd) - epsilon)) # we should have |diff| < X# Coppersmithstart_time = time.time()roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)# outputprint("\n# Solutions")print("we want to find:", qbar - q)print("we found:", roots)print(("in: %s seconds " % (time.time() - start_time)))N=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953e=3m=0x9e67d3a220a3dcf6fc4742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000c=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c451562c816e2303990834c94e580bf0cbd1ZmodN=Zmod(N)P.<x> =PolynomialRing(ZmodN)f=(m+x)^e-cdd=f.degree()beta=1epsilon=beta/7mm=ceil(beta**2/(dd*epsilon))tt=floor(dd*mm*((1/beta)-1))XX=ceil(N**((beta**2/dd)-epsilon))roots=coppersmith_howgrave_univariate(f,N,beta,mm,tt,XX)print ("缺失的m部分是:"+hex(roots[0]))print ("完整的m是:自己手动把上面m中的0000000换为缺失的m部分值即可(16进制的).")potential roots: [(2075554696689911695150, 1)]缺失的m部分是:0x70841b8fe11fd1872e完整的m是:自己手动把上面m中的0000000换为缺失的m部分值即可(16进制的).Stereotyped messages Attack
github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%91%E6%9D%AFcopperstudy---level1/exp.sage
sage是基于python开发，所以python的语法几乎对它完全适用，但是sage自己还开发出了很多语法格式和数学公式，学习难度还是不低的，所以我把这些脚本都当做了工具，拿来直接用，自己写出来似乎能力还不够，因为不光要学语法，关键是这里面的数学算法知识。
使用方法：通过终端进入上面说的RSA-and-LLL-attacks工具包目录下，然后运行sage。
复制脚本内容到终端中然后回车回车运行(不知为何无法直接运行脚本，很是不解，可能是我的打开方式不对，你要是会的话，麻烦一定和我说一声，就当是带带我吧)
ps：感谢大佬@啦啦啦 提供的方法
sage下直接运行load("exp.sage")就可以解题运行，不用粘贴脚本内容了。
02. Partial Key Exposure Attack
适用情况：若e较小，已知d的低位，则可通过此方法求出完整的d。
Partial Key Exposure Attack中文名叫”部分私钥暴露攻击”。
题目: 13-2019强网杯copperstudy---level3
题目给出如下加密脚本参数：
n=0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c427bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x3d7e16fd8b0b1afdb4e12594c3d8590f1175800ef07bb275d7a8ad983d0d5d5fd5c6f81efa40f5d10c48bb200f805e679d633ee584748e5feef003e0921dea736ba91eef72f3d591d3a54cd59fd36f61140fdd3fb2e2c028b684e50cbeae4a1f386f6ab35359d46a29996c0f7d9a4a189f1096150496746f064c3cc41cf111b0L
d=invmod(e,(p-1)*(q-1))
d&((1<<512)-1)=0x17c4b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bL
要求出完整的d。
sage解题脚本:
Partial Key Exposure Attack
github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%91%E6%9D%AFcopperstudy---level3/exp.sage
脚本注释： d0代表已知的d的较低位，kbits是已知的d0的位数。
n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L pbits = 1024 kbits = 130 pbar = p_fake & (2^pbits-2^kbits) print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits) PR.<x> = PolynomialRing(Zmod(n)) f = x + pbar x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3 print hex(int(x0 + pbar)) sage: load("exp1.sage")upper 894 bits (of 1024 bits) is given0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a87321efe89ec89bdf3e4d9da9a45df22a787L03. Factoring with high bits known Attack
题目: 13-2019强网杯copperstudy---level2
题目给出如下加密脚本参数：
n=0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL
e=65537
m=random.getrandbits(512)
c=pow(m,e,n)=0x1922e7151c779d6bb554cba6a05858415e74739c36df0bcf169e49ef0e566a4353c51a306036970005f2321d1d104f91a673f40944e830619ed683d8f84eaf26e7a93c4abe1dbd7ca3babf3f4959def0e3d87f7818d54633a790fc74e9fed3c5b5456c21e3f425240f6217b0b14516cb59aa0ce74b83ca17d8cc4a0fbc829fb8L
((p>>128)<<128)=0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L
要求完整的p。
sage解题脚本:
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(必须为整形才可计算) = 0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c427bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL# d0=给出的部分d(必须为整形才可计算) = 0x17c4b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bLe = 3n = 57569201048993475052349187244752169754165154575782760003851777813767048953051839288528137121670999884309849815765999616346303792471518639080697166767644957046582385785721102370288806038187956032505761532789716009522131450217010629338000241936036185205038814391205848232364006349213836317806903032515194407739nbits = n.nbits()kbits = floor(nbits*0.5)print "kbits : ", kbitsd0 = 1244848677959253796774387650148978357579294769878147704641867595620534030329181934099194560059806799908134954814673426128260540575360296026444649631806619print "lower %d bits (of %d bits) is given" % (kbits, nbits)p = find_p(d0, kbits, e, n)print "found p: %d" % pq = n//p# print dprint "完整的d是:"+str(inverse_mod(e, (p-1)))Factoring with high bits known Attack
github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%
sage: load("exp2.sage")kbits : 511lower 511 bits (of 1023 bits) is givenfound p: 7086179599191994333603836952445140343587486096628720220842297473373568276314821730585498733360983965734902690794828276489674036310720194369289757363461559完整的d是:4724119732794662889069224634963426895724990731085813480561531648915712184209881153723665822240655977156601793863218850993116024207146796246193171575641039sage:这篇关于从零开始学RSA：已知dp,dq求解m和CopperSmith定理攻击的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
