包含四个赛题的题解。
GeneratePrime
题目描述:
1 | 尝试分解一下素数吧 |
题目:
1 | from Crypto.Util.number import getPrime, isPrime, bytes_to_long |
题目是根据ImaginaryCTF 2023的sus题目改的,具体推导可以见我这一篇文章:
Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)
在sus一题与本题中,q分别为:
而这其实并没有多大区别,因为他们分别满足如下因式分解:
所以推导过程可以说是完全一样的,参考上面那篇文章即可,而这个题目本身我觉得是非常有意思的,所以我强烈推荐弄明白原理。
exp:
1 | from Crypto.Util.number import * |
FindPrime
题目描述:
1 | 利用你的所学知识看看这个素数有啥能分解的吧 |
题目:
1 | from Crypto.Util.number import * |
output.txt:
1 | 833477371577037248671393488796841448323259324097064076319628420817885469255000583369058481944985769427996156459681454706589776988919309994624061437098895355604275125815197436256702258179251584180213654099283298392635474661213568306075241588048132336078444076126820420463425993589637558750777268224105474567279804292533669526701194763687939785229766307504441712413449981891561774806156665751819904294472651269669748332928431198159353146128591296262185405972439546 |
这个题目就没太多可说的了,第一部分AGCD,第二部分AMM或者有限域开根后CRT组合就好。
exp:
1 | from Crypto.Util.number import * |
MathFactor1
题目描述:
1 | 简单利用你的知识观察即可 |
题目:
1 | from Crypto.Util.number import * |
题目要求分解RSA的公钥n,为此给了我们一个额外信息:
但是这个额外信息并不是完整的,而只给了我们低300位。利用这个信息推导的过程如下,首先同乘p^17:
那么在模2^300的意义下就有:
那么解这个模方程就能解出可能的p的低300位,然后copper高位恢复p就有n的分解。
exp:
1 | from Crypto.Util.number import * |
MathFactor
题目描述:
1 | 尝试利用你学过的知识来解决吧 |
题目:
1 | from random import randint |
output.txt太长了,需要的师傅可以找我要。
回到题目,题目分为两部分,第一部分基于一个奇怪的get_Prime_leak函数生成了两个大素数p、q;第二部分将flag放在指数上,然后做一个有掩码的加密。这也就是说,第一部分应该是让我们获得素数p,从而能够求解第二部分的离散对数问题。
但是其实第二部分是N1CTF的e2D1p一题,在这个题目中是可以直接用第二部分恢复p的,详细推导可以见:
Crypto趣题-Lattice | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)
我也是直接从第二部分尝试入手的。但实际实施会发现,这个题目中flag有183比特,但是e2D1p中仅有159比特,而就是这样一个flag的比特长度差异,导致我们需要的左核中规约出的短向量长度依然很大,没有办法在有限时间内进行幂乘运算(不太明白我在说什么的师傅可以先去看看e2D1p我的题解)。具体来说,e2D1p中规约出的短向量数量级是下面这样:
1 | (-28, -58, -136, -183, 73, 41, -45, -37, -75, 129, 89, -14, 23, 31, -31, 6, 46, -79, 15, 53, 82, 16, -10, 6, -8, 102, 114, -58, 7, 90, 51, 62, 21, -49, -140, 209, 21, 90, 17, -27, 60, -123, -64, -65, 72, -159, -124, 72, -88, 101, -64, -11, -139, 169, -18, -93, -49, -66, 27, -2, 111, -68, -87, 41, -103, 2, -176, 61, -41, 93, -92, -60, -64, 38, -40, 156, 79, 141, 103, -12, 25, 1, 158, -18, -36, 8, 63, 164, 15, -101, -160, 64, -66, 23, 105, -70, 71, -38, 41, 37, 2, -85, 72, -107, -41, -77, -117, 77, -250, -55, 13, -148, -34, -36, -119, -44, -117, 98, -101, 23, 154, 32, -11, -17, -52, -29, 81, 182, 26, 45, 162, -29, 71, 114, 44, -21, 11, -37, 6, -119, 19, -22, -76, -41, -41, 17, 146, 73, -82, 41, -52, -91, 130, -25, -6, 24, -2, -39, 16, -76, -59, 15, 64, -118, 40, -155, 141, -32, 143, -67, 78, -43, -58, 18, 131, 55, -34, -24, 27, -20, 128, -172, -3, -3, 38, 14, 189, 128, 158, -164, 107, -53, 70, -67, -32, 4, 18, 36, -81, -117) |
但是本题规约出的是下面这样:
1 | (615531, 820840, 1843883, -988269, 1428114, 1582152, 1858592, 416398, 1347348, -1249922, 493164, -13983, 1130024, 1207762, -83772, -1709002, -3710981, 1039779, -3519123, 907341, -2290927, 1126688, -1249423, -628301, 1916755, 521537, 73886, -186219, -219367, -1906389, 1594946, -120368, 166749, -1244087, 134738, -538176, -668121, -1056203, -559497, -34191, 2611364, 4432570, -1553761, -2032445, -1084508, 10039, -3117250, 1811906, -2528854, -1267546, 723272, 209526, 518286, -131043, -2547708, -1392536, -3286900, 1086367, 559683, -3090238, 3206757, 697813, 2242044, -371728, -957366, 3591511, 3179698, -879907, -3571962, -69278, -2108676, -244744, -808858, -628418, 992696, -1803330, -803533, -1487603, 1611449, -2704640, -2402337, -210044, 3150751, -32136, -255605, 1362843, -218480, 1148073, -1481245, 1778748, 3009486, -2402629, -2055140, -233379, 475049, 190266, -2005899, -196650, 770396, 979739, 3141171, -491714, -146091, -128110, -1281062, 260650, -380974, -39241, -1018453, 47184, 597919, 2378194, -105102, -56783, 1635534, -2230566, -684866, 649656, -909431, 412454, -2314462, -173275, -516860, 6333941, -968605, -398729, -754797, 352076, 1182197, -539564, -152936, 384461, 143728, -2349008, -1065335, -2770792, 2956471, -720375, 874597, -1971207, -2306567, -2043739, -3030757, 3705855, 3554038, -188858, -880846, -1461827, 776425, -1640892, -2061636, 1561268, 447146, 1784411, 800767, 590142, 1506176, -885787, 186370, -3483445, 3071150, -1020290, -1274281, -756202, -1208553, 616290, 432768, 2234865, 3184408, -1384911, 1993714, 1300044, -2446183, 1265363, -542953, 142733, 1177658, 1691082, 578373, -798776, 2288770, 355350, 2204661, 536178, 1373409, 1436493, -254000, -704253, 2164140, -3300946, -376660, 459460, -1819436, 2012068, -846015, 1651051, 1783145, 2637474, -1493120, -3108069) |
所以直接从第二部分恢复p的尝试就宣告破产了,因此还是要从第一部分入手。
然后看第一部分素数p的产生过程,其实可以发现他的产生过程其实是一个线性的迭代,因此都可以写成矩阵形式。具体来说,第一次迭代为:
第二次迭代就是:
其实就可以发现规律了,不妨令:
那么其实n次迭代后得到的xn,yn其实就是:
而根据数量级或者测试可以知道,要生成512bit的素数,题目一共会进行18次迭代,所以最后得到的p其实是:
那么问题就在于如何由刚才的矩阵表示形式推出p的值,我们简单观察一下前几次累乘矩阵得到的结果:
有没有发现什么,我们可以把这个结果矩阵写成如下形式:
而如果再进行一次迭代,累乘矩阵的符号又会变成如下形式:
因此,18次迭代后,累乘矩阵的符号表示为:
所以有:
所以p就等于:
而接下来就是最重要的一点就是注意到:
而累乘矩阵的行列式又等于每个矩阵的行列式乘积,所以就有:
这个时候你应该明白了,这其实说的就是A’’^2 + 39041B’’^2是由若干个如下的小因子组成的:
这其实还说明了一个信息,就是p的表达式的末尾的或运算其实只能写成:
否则p一定不是一个素数,因为如果不加1,前面这一部分肯定是一个合数。
那么题目就很显然了:p-1是一个光滑数,并且他的所有可能的因子就只有一个39041以及:
所以我们把所有这样的因子乘起来,就可能可以覆盖所有p-1和q-1的因子,也就是说我们就拥有了kphi,然后就可以用kphi分解n了,而之所以说是可能可以覆盖所有p-1和q-1的因子,是因为只乘一遍的话,若有因子重复可能会覆盖不到。但是这种情况可以想到概率非常低,因为其实素数p和q的生成过程是从200x200种组合中随机抽取了18+18个,所以这36种组合均不相同的概率是很大的。
得到n的分解后,其实第二部分已经没有难度了,因为p-1是光滑数所以可以直接选一组求dlp后与message异或得到flag,而并不需要像N1CTF那道题目一样逐比特恢复。
1 | from Crypto.Util.number import * |