江苏龙网

  1. 首页 > 人文 > >

浪子归家|密码学学习笔记之Coppersmith’s Method （三）( 四 )

对于这一关 ， 由于我们知道m是512bit的 ， 而用于加密的e=3 ， 因此三个c即为m^3 在不同模下的剩余 。 由于m^3为512 * 3=1536bit ， 而可以知道的是三个模n的bit长度分别为1021 ， 1023 ， 1024 。所以利用中国剩余定理【具体原理可以看俺这一篇文章】我们是可以还原长度为1536bit的m^3的 ， 最后我们再开个三次根就好得到m了 。
【浪子归家|密码学学习笔记之Coppersmith’s Method （三）】exp
from gmpy2 import *def CRT(mi, ai):assert (reduce(gcd,mi)==1)assert (isinstance(mi, list) and isinstance(ai, list))M = reduce(lambda x, y: x * y, mi)ai_ti_Mi = [a * (M / m) * invert(M / m, m) for (m, a) in zip(mi, ai)]return reduce(lambda x, y: x + y, ai_ti_Mi) % Mprint iroot(CRT([n1,n2,n3],[c1,c2,c3]),3)
浪子归家|密码学学习笔记之Coppersmith’s Method （三）exp来自食兔人的博客——CTF中的RSA基本套路
Cs = []Ns =[]A=[1, 1, 2]B= [0, 1, 2]e= 3# solvecnt = ePR. = PolynomialRing(ZZ)x = PR.gen()Fs = []for i in range(cnt):f =(A[i]*x + B[i])**e - Cs[i]ff = f.change_ring(Zmod(Ns[i]))ff = ff.monic()f = ff.change_ring(ZZ)Fs.append(f)F = crt(Fs, Ns)M = reduce( lambda x, y: x * y, Ns )FF = F.change_ring(Zmod(M))m = FF.small_roots()print("m: ",m)第五关：Related Message Attack已知n,e=3 ， m对应的密文c1 ， (m+1)对应的密文c2
[+]Generating challenge 5[+]n=0xf2e5339236455e2bc1b1bd12e45b9341a3b223ddb02dec11c880fa4aa8835df9e463e4c446292cd5a2fe19b10017856654b6d6c3f3a94a95807712329f7dae2e1e6506094d5d2f9c8a05c35cbf3366330996db9bff930fe566016d5e850e232057d419292ce30df9c135d56ef1bb72c38838d4b127aa577ceb4aba94d4e0d55L[+]e=3[+]m=random.getrandbits(512)[+]c=pow(m,e,n)=0x7175f2614b8d1a27b43f7c3873b3422658af28291ddc88b15f97f499e00cd4c5c4fd980f062376a61e5dd4c15d52d73262d3c066f1e8f46a04af6fead7c3960d2768a0d214bbc3e05d2f6e56aee158071574e55753624a19e094590fc3f9918a2065cd5ff7693e0d34517bc0072e6c9e444e66c4ece88d657f99e44bee48924L[+]x=pow(m+1,e,n)=0xd5f4af36b5391bd731cfa4313466024ab1bc3b455024a5d8b218faba0e956252f01c4d01bd36765035c33d73e5af7f178aeb2606edf86814d74082c64828fa4c1666b69d05fab69dd1ef47b243356290fdb74e001f54edec70681cf52319c73bce9acda4803a9e97597ca21d60072c2d2b516f161bec1f6a91baa2e24c7655bL[-]long_to_bytes(m).encode('hex')=同第四关一样 ， 这一题也有多解 ， 一种是像一叶飘零师傅这篇文章所述 ， 直接硬化公式
exp
import gmpydef getM2(a,b,c1,c2,n):a3 = pow(a,3,n)b3 = pow(b,3,n)first = c1-a3*c2+2*b3first = first % nsecond = 3*b*(a3*c2-b3)second = second % nthird = second*gmpy.invert(first,n)third = third % nfourth = (third+b)*gmpy.invert(a,n)return fourth % na = 1b = -1c1 =c2 =n =m = a*getM2(a,b,c1,c2,n) + bprint hex(m)
浪子归家|密码学学习笔记之Coppersmith’s Method （三）exp
def franklinReiter(n,e,b,c1,c2):R. = Zmod(n)[]f1 = X^e - c1f2 = (X + b)^e - c2m_ = GCD(f1,f2).coefficients()[0] # 返回的是首一多项式 ， coefficients()返回多项式各项式的系数 ， 项式次数递增 ， 所以第0项是常数return Integer(n - m_) # 由于tmp其实是 -m % n,所以这里给他转换回去 。 def GCD(a, b):if(b == 0):return a.monic()# 返回首一多项式 ， 即多项式最高次的项式系数为1else:return GCD(b, a % b)e = n = b = c1 = c2 = M = franklinReiter(n,e,b,c1,c2)print(M)


推荐阅读


上一篇：Sofm|Sofm明牌了？说到SN能赢的原因：大家都习惯了吧？那个方面

下一篇：袖手天下看苍生|看到村口的大树这副模样，村民吓得腿软，大雨过后