点击蓝字
关注我们
日期：2022-04-14
作者：jgk01
介绍：一道
RSA赛题的学习记录。
0x00 前言
最近过年回来好久没做题，最近找了一些国外的题目学习学习，这道题目看到有很多解法，研究一种之前没注意过的，记录一下。
0x01 题目分析
CTF赛事的RSA题目，我们先读一下题目代码来分析一些题目提供了那些信息。from Crypto.Util.number import getPrime, isPrimefrom hashlib import sha512import randomdef getSafePrime(bits):while True:p = getPrime(bits - 1)q = 2*p + 1if isPrime(q):return qdef make_inivitation():with open("flag.txt", "rb") as f:flag = f.read().strip()m = int.from_bytes(flag + sha512(flag).digest(), "big")p = getSafePrime(512)q = getSafePrime(512)n = p * qassert m < nb = random.randint(2, n-1)c = m*(m + b) % nreturn c, n, b# print("Dear Moe:")print(make_inivitation())# print("Dear Lulu:")print(make_inivitation())#c1, n1, b1 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)#c2, n2, b2 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)
题目给了两组c,n,b其他的暂时没有什么有用的信息了呢么下面我们开始分析解题思路。
0x02 解题思路
首先我们看题目给的加密式子 c = m*(m + b) % n 这样的话很明显我们可以写成：
m是flag并且附加了他的SHA512的哈希值，b是随机生成的水技术并且比n小，我们目前未知变量是m，而b和c和n都是已知的，只需要解这个m，但是这并不是等式方程组，而是同余式，但是我们可以发现这个式子非常像下面的公式：
Case of two moduli这种情况：
这时候我们有：
这个时候我们就可以得到:
并且互换下标我们可以知道不论i=1还是i=2都是成立的，这就是Case of two moduli的一般情况，再看到我们这个题目：
到这里就比较清晰了，我们可以发现：
此时我们可以移向构造函数：
所以我们就可以解出这个根来求我们的m。
0x02 解题脚本
下面是根据上面分析我们写出的解题脚本。
from Crypto.Util.number import long_to_bytesc1, n1, b1 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)c2, n2, b2 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)k1 = int(pow(n1, -1, n2))k2 = int(pow(n2, -1, n1)) //g,k1,k2=gmpy2.gcdextx = c1*k2*n2 + c2*k1*n1(n1,n2)P.<m> = PolynomialRing(Zmod(n1*n2))f = m^2 + m*(b1*k2*n2 + b2*k1*n1) - xflag = f.small_roots(X=2^(55*8 + 512), beta=0.5, epsilon=1/64)[0]print(long_to_bytes(flag)[:-64].decode())
这里说明一下这个R.<m> = PolynomialRing(Zmod(n1*n2))是什么意思：
R.<m> = PolynomialRing(Zmod(n1*n2))
0x03 总结
这个题目还有其他的解法，感兴趣的小伙伴们可以继续研究一下其他解法。
免责声明：本文仅供安全研究与讨论之用，严禁用于非法用途，违者后果自负。
宸极实验室隶属山东九州信泰信息科技股份有限公司，致力于网络安全对抗技术研究，是山东省发改委认定的“网络安全对抗关键技术山东省工程实验室”。团队成员专注于 Web 安全、移动安全、红蓝对抗等领域，善于利用黑客视角发现和解决网络安全问题。
团队自成立以来，圆满完成了多次国家级、省部级重要网络安全保障和攻防演习活动，并积极参加各类网络安全竞赛，屡获殊荣。
对信息安全感兴趣的小伙伴欢迎加入宸极实验室，关注公众号，回复『招聘』，获取联系方式。
原文始发于微信公众号（宸极实验室）：『CTF』Case of two moduli 解RSA题目思路
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论