第三届强网杯之copperstudy
最早是在看ctf比赛里面的RSA类题目的总结的时候有看到关于CopperSmith定理的介绍，不过当时那篇总结并没有提供可参考的例题，第一次看到了相关的题目是在第二届强网杯的一道叫做next_rsa的题目里面，当时其中一关涉及到了CopperSmith定理。今年的强网杯又出现了一道关于CopperSmith定理的题目，这次这个题目题如其名，是一次学习CopperSmith定理的机会。
开始之前
这个题目总共6个关卡，一开始我以为只是github上的那个算法实现的一次使用，所以应该只有3个关卡，然而是我太菜了。
stage 1
[+]Generating challenge 1
[+]n=0x7e2611bb35a5aa8fcf89459b02f7c5071197fffc7d65dd974aaef6fa01351b376e8e1b34316d8da3f62d1a202bcc23a8995949b65e5b93a33d9407381fae42ff1f1ee6ab2fae9ec119cad9823bd953c4eb63ca786cd9e05a6c9975f380bfe5c7519f189176e021a01f182aa75dba2bebf43065b237e0d3a6df94bfaf61fb3911L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x73e2ec0f8549edf4183fed73b336ae41451755d78f4dfdc7b490d58760048dbc360b435ddc0ab9e83197028358786343b62c7a9b9495bc078a71a77f782d8ceb2de0e08b3ebaf31eed3e03e7cb9bf0dd8dfe48ed9c26ed222f9a7aae4b255224159270f21ed2031febaedade9449e749f6d996e669a97d3a2b17665ca20c9a12L
[+]((m>>72)<<72)=0xd305b50c5909c49f3698544c7f550bd948d5b639e74d066505c2518421be3bc9077e30a61197b61c88718cfe9e6c75fa70a38633ce5125000000000000000000L
[-]long_to_bytes(m).encode('hex')=
第一关，告诉了我们 \(n,e,c\) 和 \(m\) 的大部分比特位(最后72比特未知)；根据CopperSmith定理， \(e=3\) 的时候，如果明文的三分之二的比特位是已知的，那么我们可以恢复出后面三分之一比特位，这个题目里面的 \(m\) 是512位，所以显然是满足条件的。
那么我们就可以直接使用上面那个github库里面的coppersmith.sage脚本了（这个是sagemath的运行脚本，如果本地没有Sagemath的运行环境或者觉得这东西太大了的话，可以使用sage提供的在线服务）。
Sage 是一个免费的、开源的数学软件系统，采用GPL协议。它整合了许多开源Python包，采用Python语言编写，但也支持其他语言。它的目标是创造一个可变的开源软件以替代Magma、Maple、Mathematica和Matlab。Sage不仅是一个软件，也是一个编程环境，提供命令行模式、笔记本模式，可以编写编译型程序和解释型程序。目前Sage支持Linux、Mac OS X、BSD、Solaris平台。—— 百度百科
不过脚本里面的求解函数参数太多，太菜了并没有看懂。不过还好下面的测试用例都写好了，这一关适用于这个脚本的第一个测试，改了几个参数就能求解出来，第一关真是差点就让我学了好多的sage的数学语法。
stage 2
[+]Generating challenge 2
[+]n=0x4ac21d5a9c7ce7b9e19dfc9551725b5fcf39b365b6ba1235c28e3e5d1566791bed5dbeeccb5a698ffd680ed487ea3b27620a49b3ada155b67f569b6b8333afbd08ed3fc9142f6ed407e24f7777859d24aff5455a894900a700b710b31a9967e906f528e4472a8218fe8e9e1287481b99add78220f0390c4a0e5518e5bbb71559L
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x19ce8c6e86b39116c35a4e3059d65f9872c26e08455e14c7b3f76917093acd0080a20b0035b0770819e2d37f75eca7f2cf8421a6313d607c3d033a651f111c686f82dbb9932943836d338ad177494deae01e97bd1855c313b3ae88fdfbc2196ddf1b48f1091f91023a2b986d1e7f2c0f166e4a1cbaa412a37470a87df386212L
[+]((p>>128)<<128)=0xd37ce3c9a11ae5c3cb567d2c783ad793162e4794edb8d370fc2bb63b0ee32d02262f92fb4d5233fbedde6da45aa810da00000000000000000000000000000000L
[-]long_to_bytes(m).encode('hex')=
第二关，也告诉了我们 \(n,e,c\) ，不过这次没有 \(m\) 了，而是 \(p\) 的大部分比特位(最后128位未知)；这也是CopperSmith定理的另一种典型情况：已知模数 \(n\) 的其中一个素数 \(p\) 的高比特位，我们可以求出 \(p\) 。
这一关用的还是那个脚本，适用于第二个测试。虽然还是没有看懂方程怎么回事，不过还是，改自己需要的参数，运行就出来了（我运行出来是 \(p\) 的低比特位的负数/捂脸） 。
stage 3
[+]Generating challenge 3
[+]n=0x2653fa7e16c89a7af9339c3c8e7310fcb1f20948481ffa23d1e49a44869caa256fb8d656318f44eec1257e92375f9518eea9b6748374b172ccafd26e110af667dce4d0c10dc15a82b645482d0f1b3cd7f516c4b55f0d17cd8eae141ca6e92b95fbb8adcff101af3b6aacb5778ecc5c45e887b81d4a7d5c4a02bcbf52e61ecdcbL
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x11cb789529b6ff51e821901c27bf277f9a79613baab967de66cc00b8aa893b7eb078f4a385ce4dc6f456fe103e4dfe0082828df983ea9192719dcb8c21960a807c63762f1767d2780cc12ea3222638a2363841366406f42fa020226803c28552b7afc50b0f573513d82f05b50052818eec0f785c5fe8ca3c7ce70bfc51728cf7L
[+]d=invmod(e,(p-1)*(q-1))
[+]d&((1<<512)-1)=0xd9e274d30589d1d00958e889e019e5d598d197cb306a9f67fcb26959b2c8bdd519c3f4d4aea85d01d5162de408cef05b4c9fc094676ef23d55dc8b8735fcfdbL
[-]long_to_bytes(m).encode('hex')=
第三关，也告诉了我们 \(n, e, c\) ，还有解密秘钥 \(d\) 的低512比特位。我刚才开始以为这题目就只有三个关卡，所以第三个应该是 Boneh and Durfee 攻击，结果看了半天也不对劲。后来在另外一个博客上找到了，这个应该是关于部分密钥泄露的攻击的一个定理，当然也是基于CopperSmith定理的：
设 \(⟨N,d⟩\) 为RSA私钥，其中 \(N\) 长度为 \(n\) 位.。给定 \(d\) 的 \(\lceil \frac{d}{4} \rceil\) 最小有效位，可以在 \(e \log _2 e\) 的线性时间算出 \(d\) 。
这定理大概就是说我们知道一部分的 \(d\) 的低比特位，我们可以求出 \(d\) 。具体的分析也不是很懂，不过那篇博客写到了一点：
\(D=\lfloor (kN+1)/e \rfloor \) 之后， \(\mid D−d\mid \leq \frac{(p+q)}{e} \leq \frac{3k\sqrt{N}}{e} < 3\sqrt{N} \) 因此， \(D\) 是 \(d\) 的很好的近似值。该界表明，对于大多数 \(d，\) \(D\) 中一半的最高有效位与 \(d\) 相同。由于 \(k\) 只有 \(e\) 个可能的值，因此可以构造一个大小 \(e\) 的小集合，使得集合中的一个元素等于 \(d\) 的一半最高有效位的。 \(e=3\) 的情况特别有趣，在这种情况下，可以知道 \(k=2\) ，系统完全泄漏了 \(d\) 的一半最高有效位。
这个就很清楚了，题目也完全符合我们的要求，这样我们就可以很快的求出了私钥 \(d\) 的高512位，结合已知的低512位即可解出消息 \(m\) 。
stage 4
[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=0x681b467e0fd16c1b551f3c9d5b64d7b0e3ae23e4c8f93f867066972100912296bc6a26e1e10ace246613d0b372f29e77edec08adc9785b7bf16e261bfde22eb7976aa3649216dd30f557420f8ff9fcef17341de1b121b2d1078e3713a9a7800a63cc24e815c741f0d8c44c69eb153b3b6792995c92e3accac1b8ffd53fe596dL
[+]c1=pow(m,e,n1)=0x2f9a6a3442e62d33ddf5e6bb8154613268749f397bc5eefadf359d94649d3c021f00b772d4d57650179517487d60e38b87af6a84e5b08bdce94a0ca3365ab4f4ccd06f2d840998b21539a6681406eb1278b13cd52235693c95fd569f76c5b0c7c8dd2f415e4ce8224b854b6092e211c2e9b5bc0136c497f87e4de20e4eb262cL
[+]n2=0x5174e7d2c56f1b110413edf286c8adf5020de8ae6c982907350bba38a33af076f88bac3374047941cb02dc40821e09b187092784bedee4bd2c609e48795f4467c4372dd54d7e470a79a291cd35a1e20c6db9a13f7e4b389735aaa17c5ca62a8c02370e880add05408851b41a34ebbe5cbda92bc85936eb51b93f112f4da1b27dL
[+]c2=pow(m,e,n2)=0x420399bd8f56613471c3ccc52ac3cfa5abb54cd52a20126c4333b4824c549d24726a72bca5f6823628dd199053856024f491079bcd652cecf0e450d24671f25549782d07578684fdbdc280fa2a683a1f856375b7920f813e4a5eaeb47e3bce2b45d14613a4aae9f8f855d237889dc67d5f00e2b6ba81950112ff918544c8af7eL
[+]n3=0x507cf73f0c3a2bb903ba1444472374abbbc77091b3e0e467cb85f3c6ff84a33ec90ed8540fce9a481a7c6db7a40129e2dc0d62854f0895f1bddb86282c1f0e89c6b5fdf11b148cb879931788a693d481db3ca95567be96df79c8144d6dc60bcf7cb25da1f2b05d8f7598b743e2ae4a63a76fbfacb936e5c87a6cb9526ccb304fL
[+]c3=pow(m,e,n3)=0x47fb9f451f54e077ed05dbdced8875eedc9ffc7e4679a42b01f2e0a0d1b98fc17144efb6b7e2f81168d30c590af87e9ada00a511bcf523667442c56f234970f87e21018335440a4c6fc453240ec2fadab6c596e5db7b331901996dacfc09bbc7824958b0726d07fad39fb0ba6697aa1c1acd88be0fc88f90fa117fff98b52debL
[-]long_to_bytes(m).encode('hex')=
第四关给出了三对公钥，其中他们的 \(e\) 都是相同的，等于 \(3\) ，并且给出了消息 \(m\) 分别使用三个公钥加密后的密文 \(c\) 。这个要是放以前就直接中国剩余定理(CRT)直接去求解了，不过这次我才知道了原来这个攻击也是CopperSmith定理的一个应用。
直接使用中国剩余定理求解就可以了，这篇总结里面的CRT实现不错，可以借鉴。
stage 5
[+]Generating challenge 5
[+]n=0x96e6b5c21e3cb3ce7fd18b13bd8d71bd9a3ad2a1d6c4dc3c9efd1b2c7806f7d53a7434cc888df8e97560f77855132b8381c92d189eecd43f9070a6f08dd95d0e94ebf752d33b8bc4a622ddf7176f98a5a5b6bc0346eb7fd74afbf0f3a8586ee9cc787bbe1783e2ab0d7f2e0ee09f24f4fc49967400d617c3dd09451f19cff3bdL
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x635c0c375c0d757dd157503155620868faef93de5b540a13e8fd1cda26a07bc906a9d32c7dc6fc4903c62877cbdf75696e7fd3407b4e5e20b56e1891bd36352a0438837a6278d5f2a60d11348d60c5d2faf0ddc3e3da7c83a3f2659607b9065397734ec40dd58c3c10758ab035189ae1a0ec60f369cfa92891f31858734bf1ccL
[+]x=pow(m+1,e,n)=0x3bf6ae0ae69edc5343e6e38090596ff75cbc272aa512ae1c9963b2eb364ea5dfd9d44745dbc21355ad5c35785e84ac69c66e95dcc72f0c5439196442a1aa95d9bf41cfdec96fd8720eb28b71f052437c448a8a3eddaebd98e4dff4180e2d1c0200dece1dbc2064a73359f035c10f3c305a649b7dbeebd2f0d73aa60dc01b899aL
[-]long_to_bytes(m).encode('hex')=
第五关，给出了 \(n, e\) 和消息 \(m\) 的密文 \(c\) 以及 \(m+1\) 的密文 \(x\) 。一看 \(e=3\) 很小，我还傻乎乎的自己看，其实这也是CopperSmith定理的一个应用，叫做，Franklin-Reiter相关消息攻击。
令 \(e=3\) ，\(⟨N,e⟩\)为RSA公钥。设 \(M_1 \neq M_2 \in Z_N^*\) 对于 \(b \neq 0\) 的线性多项式 \(f=ax+b \in Z_N[x]\) 满足 \(M_1=f(M_2) mod N\) 。然后，给定 \(⟨N,e,C_1,C_2,f⟩\) ，可以在 \(\logN\) 的平方时间内计算出 \(M_1,M_2\) 。
其实，原理似乎很简单，奈何对sage并不熟悉，找了好久，才找到别人的实现，发现这个并不复杂。
stage 6
[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=
第六关，只给出了 \(n, e, c\) ，题目中有提示 \(d\) ，我以为提示是 \(d\) 不大的意思，于是我就先去试了试wiener-attack，没有解出来，但是其实显然这是CopperStudy啊！所以其实最后一个才是Boneh Durfee攻击。
github上的实现可以用，也是修改参数即可。
最后终于出现了flag。
总的来说这次的copperstudy是一个对比CopperSmith定理出题比较全面的应用，或许数学原理不是特别理解，但是攻击的实现大部分都已经有了。
具体的数学原理这篇博客讲的比较清楚。
参考链接
https://github.com/mimoo/RSA-and-LLL-attacks
https://www.anquanke.com/post/id/84632
https://xz.aliyun.com/t/2446#toc-9
https://xz.aliyun.com/t/2731#toc-21