第三屆強網杯之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)=

第一關，告訴了我們和的大部分比特位(最後72比特未知)；根據CopperSmith定理，的時候，如果明文的三分之二的比特位是已知的，那麼我們可以恢復出後面三分之一比特位，這個題目裡面的是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)=

第二關，也告訴了我們，不過這次沒有了，而是的大部分比特位(最後128位未知)；這也是CopperSmith定理的另一種典型情況：已知模數的其中一個素數的高比特位，我們可以求出。

這一關用的還是那個腳本，適用於第二個測試。雖然還是沒有看懂方程怎麼回事，不過還是，改自己需要的參數，運行就出來了（我運行出來是的低比特位的負數/捂臉）。

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)=

第三關，也告訴了我們，還有解密祕鑰的低512比特位。我剛才開始以為這題目就只有三個關卡，所以第三個應該是 Boneh and Durfee 攻擊，結果看了半天也不對勁。後來在另外一個博客上找到了，這個應該是關於部分密鑰泄露的攻擊的一個定理，當然也是基於CopperSmith定理的：

設為RSA私鑰，其中長度為位.。給定的 $lceil frac{d}{4} ceil$ 最小有效位，可以在的線性時間算出。

這定理大概就是說我們知道一部分的的低比特位，我們可以求出。具體的分析也不是很懂，不過那篇博客寫到了一點：

之後， $mid D?dmid leq frac{(p+q)}{e} leq frac{3ksqrt{N}}{e} < 3sqrt{N}$ 因此，是的很好的近似值。該界表明，對於大多數，中一半的最高有效位與相同。由於只有個可能的值，因此可以構造一個大小的小集合，使得集合中的一個元素等於的一半最高有效位的。的情況特別有趣，在這種情況下，可以知道，系統完全泄漏了的一半最高有效位。

這個就很清楚了，題目也完全符合我們的要求，這樣我們就可以很快的求出了私鑰的高512位，結合已知的低512位即可解出消息。

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)=

第四關給出了三對公鑰，其中他們的都是相同的，等於，並且給出了消息分別使用三個公鑰加密後的密文。這個要是放以前就直接中國剩餘定理(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)=

第五關，給出了和消息的密文以及的密文。一看很小，我還傻乎乎的自己看，其實這也是CopperSmith定理的一個應用，叫做，Franklin-Reiter相關消息攻擊。

令，為RSA公鑰。設對於的線性多項式滿足。然後，給定，可以在的平方時間內計算出。

其實，原理似乎很簡單，奈何對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)=

第六關，只給出了，題目中有提示，我以為提示是不大的意思，於是我就先去試了試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

https://crypto.stackovernet.com/cn/q/7012

https://paper.seebug.org/727/

第三屆強網杯之copperstudy