{"id":464,"date":"2024-01-11T20:22:58","date_gmt":"2024-01-11T12:22:58","guid":{"rendered":"https:\/\/blog.taiyang.space\/?p=464"},"modified":"2024-01-09T20:24:52","modified_gmt":"2024-01-09T12:24:52","slug":"buuctf-crypto-rsa1","status":"publish","type":"post","link":"https:\/\/blog.taiyang.space\/?p=464","title":{"rendered":"BUUCTF-Crypto-RSA1"},"content":{"rendered":"

<\/p>\n

1. \u9898\u76ee\u63cf\u8ff0<\/h2>\n

\u9898\u76ee\u8fde\u63a5\uff1a\u6233\u6211\ud83d\udc8b<\/a><\/p>\n

\u62ff\u5230\u9898\u76ee\u770b\u5230\uff1a<\/p>\n

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 \nq = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 \ndp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 \ndq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 \nc = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852\n<\/code><\/pre>\n
\u4e00\u773c\u9274\u5b9a\u4e3a dp\u3001dq \u6cc4\u9732<\/p>\n
2. \u89e3\u9898\u8fc7\u7a0b<\/h2>\n
RSA-CRT<\/h3>\n
\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406<\/p>\n
\u76ee\u7684\uff1a\u964d\u4f4e\u6307\u6570\u52a0\u5feb RSA \u7b97\u6cd5\u7684\u89e3\u5bc6\u8fc7\u7a0b<\/p>\n
\u9700\u8981\u8ba1\u7b97\u989d\u5916\u7684 dp\u3001dq\u3001qlnv<\/p>\n
\u52a0\u5bc6\uff1a<\/p>\n
\n
<\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/use><\/g><\/g><\/g><\/svg><\/mjx-container><\/div>\n<\/div>\n
\u89e3\u5bc6\uff1a<\/p>\n
\n
<\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/use><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/use><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/use><\/g><\/g><\/g><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/use><\/g><\/g><\/g><\/g><\/g><\/svg><\/text><\/use><\/use><\/use><\/g><\/g><\/g><\/text><\/use><\/use><\/use><\/g><\/g><\/g><\/text><\/use><\/use><\/use><\/g><\/g><\/g><\/text><\/use><\/use><\/use><\/g><\/g><\/g><\/g><\/svg><\/g><\/g><\/g><\/g><\/svg><\/mjx-container><\/div>\n<\/div>\n
\u76f4\u63a5\u4e0a\u4ee3\u7801\uff1a<\/p>\n
import libnum\n\np = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229\nq = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469\ndp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929\ndq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041\nc = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852\n\n\ndef extended_gcd(a, b):\n    if b == 0:\n        return a, 1, 0\n    else:\n        gcd, x, y = extended_gcd(b, a % b)\n        return gcd, y, x - (a \/\/ b) * y\n\n\ndef find_modular_inverse(q, p):\n    gcd, x, _ = extended_gcd(q, p)\n    if gcd == 1:\n        return x % p\n    else:\n        raise ValueError("The modular inverse does not exist.")\n\n\nqlnv = find_modular_inverse(q, p)\nm1 = pow(c, dp, p)\nm2 = pow(c, dq, q)\nh = qlnv * (m1 - m2) % p\nm = m2 + h * q\n# m = 11630208090204506176302961171539022042721137807911818876637821759101\n\n# \u89e3\u5bc6\u51fa\u6765\u7684 m \u662f\u5341\u8fdb\u5236\u6570\uff0c\u8981\u8f6c\u6362\u4e3a\u5b57\u7b26\nprint(libnum.n2s(m))\n# \u83b7\u5f97flag\uff1anoxCTF{W31c0m3_70_Ch1n470wn}\n<\/code><\/pre>\n
3. \u6240\u9700\u5de5\u5177<\/h2>\n
\u65e0<\/p>\n
4. \u5199\u5728\u6700\u540e<\/h2>\n
\u672c\u6587\u5b8c<\/p>\n
\u656c\u7231\u4e0e\u660e\u5929\ud83c\udf39<\/p>\n
<\/body>
\n<\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
1. \u9898\u76ee\u63cf\u8ff0 \u9898\u76ee\u8fde\u63a5\uff1a\u6233\u6211\ud83d\udc8b \u62ff\u5230\u9898\u76ee\u770b\u5230\uff1a p = 86376337672570085670996534 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[167,166,165],"class_list":["post-464","post","type-post","status-publish","format-standard","hentry","category-crypto","tag-crypto","tag-ctf","tag-165"],"yoast_head":"\nBUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/blog.taiyang.space\/?p=464\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"BUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0\" \/>\n<meta property=\"og:description\" content=\"1. \u9898\u76ee\u63cf\u8ff0 \u9898\u76ee\u8fde\u63a5\uff1a\u6233\u6211\ud83d\udc8b \u62ff\u5230\u9898\u76ee\u770b\u5230\uff1a p = 86376337672570085670996534 […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/blog.taiyang.space\/?p=464\" \/>\n<meta property=\"og:site_name\" content=\"#\u762b\u7537\u65e5\u8bb0\" \/>\n<meta property=\"article:published_time\" content=\"2024-01-11T12:22:58+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-01-09T12:24:52+00:00\" \/>\n<meta name=\"author\" content=\"taiyang\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"taiyang\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/blog.taiyang.space\/?p=464#article\",\"isPartOf\":{\"@id\":\"https:\/\/blog.taiyang.space\/?p=464\"},\"author\":{\"name\":\"taiyang\",\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c\"},\"headline\":\"BUUCTF-Crypto-RSA1\",\"datePublished\":\"2024-01-11T12:22:58+00:00\",\"dateModified\":\"2024-01-09T12:24:52+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/blog.taiyang.space\/?p=464\"},\"wordCount\":8,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c\"},\"keywords\":[\"Crypto\",\"CTF\",\"\u7f51\u5b89\"],\"articleSection\":[\"Crypto\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/blog.taiyang.space\/?p=464#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/blog.taiyang.space\/?p=464\",\"url\":\"https:\/\/blog.taiyang.space\/?p=464\",\"name\":\"BUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0\",\"isPartOf\":{\"@id\":\"https:\/\/blog.taiyang.space\/#website\"},\"datePublished\":\"2024-01-11T12:22:58+00:00\",\"dateModified\":\"2024-01-09T12:24:52+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/blog.taiyang.space\/?p=464#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/blog.taiyang.space\/?p=464\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/blog.taiyang.space\/?p=464#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\/\/blog.taiyang.space\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"BUUCTF-Crypto-RSA1\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/blog.taiyang.space\/#website\",\"url\":\"https:\/\/blog.taiyang.space\/\",\"name\":\"#\u762b\u7537\u65e5\u8bb0\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/blog.taiyang.space\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"zh-Hans\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c\",\"name\":\"taiyang\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/blog.taiyang.space\/wp-content\/uploads\/2022\/10\/touxiang.jpg\",\"contentUrl\":\"https:\/\/blog.taiyang.space\/wp-content\/uploads\/2022\/10\/touxiang.jpg\",\"width\":612,\"height\":640,\"caption\":\"taiyang\"},\"logo\":{\"@id\":\"https:\/\/blog.taiyang.space\/#\/schema\/person\/image\/\"},\"sameAs\":[\"https:\/\/blog.taiyang.space\"],\"url\":\"https:\/\/blog.taiyang.space\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"BUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/blog.taiyang.space\/?p=464","og_locale":"zh_CN","og_type":"article","og_title":"BUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0","og_description":"1. \u9898\u76ee\u63cf\u8ff0 \u9898\u76ee\u8fde\u63a5\uff1a\u6233\u6211\ud83d\udc8b \u62ff\u5230\u9898\u76ee\u770b\u5230\uff1a p = 86376337672570085670996534 […]","og_url":"https:\/\/blog.taiyang.space\/?p=464","og_site_name":"#\u762b\u7537\u65e5\u8bb0","article_published_time":"2024-01-11T12:22:58+00:00","article_modified_time":"2024-01-09T12:24:52+00:00","author":"taiyang","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"taiyang","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"1 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/blog.taiyang.space\/?p=464#article","isPartOf":{"@id":"https:\/\/blog.taiyang.space\/?p=464"},"author":{"name":"taiyang","@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c"},"headline":"BUUCTF-Crypto-RSA1","datePublished":"2024-01-11T12:22:58+00:00","dateModified":"2024-01-09T12:24:52+00:00","mainEntityOfPage":{"@id":"https:\/\/blog.taiyang.space\/?p=464"},"wordCount":8,"commentCount":0,"publisher":{"@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c"},"keywords":["Crypto","CTF","\u7f51\u5b89"],"articleSection":["Crypto"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/blog.taiyang.space\/?p=464#respond"]}]},{"@type":"WebPage","@id":"https:\/\/blog.taiyang.space\/?p=464","url":"https:\/\/blog.taiyang.space\/?p=464","name":"BUUCTF-Crypto-RSA1 - #\u762b\u7537\u65e5\u8bb0","isPartOf":{"@id":"https:\/\/blog.taiyang.space\/#website"},"datePublished":"2024-01-11T12:22:58+00:00","dateModified":"2024-01-09T12:24:52+00:00","breadcrumb":{"@id":"https:\/\/blog.taiyang.space\/?p=464#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/blog.taiyang.space\/?p=464"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/blog.taiyang.space\/?p=464#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/blog.taiyang.space\/"},{"@type":"ListItem","position":2,"name":"BUUCTF-Crypto-RSA1"}]},{"@type":"WebSite","@id":"https:\/\/blog.taiyang.space\/#website","url":"https:\/\/blog.taiyang.space\/","name":"#\u762b\u7537\u65e5\u8bb0","description":"","publisher":{"@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/blog.taiyang.space\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"zh-Hans"},{"@type":["Person","Organization"],"@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/5e3b9567310d4c4a328573992325178c","name":"taiyang","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/image\/","url":"https:\/\/blog.taiyang.space\/wp-content\/uploads\/2022\/10\/touxiang.jpg","contentUrl":"https:\/\/blog.taiyang.space\/wp-content\/uploads\/2022\/10\/touxiang.jpg","width":612,"height":640,"caption":"taiyang"},"logo":{"@id":"https:\/\/blog.taiyang.space\/#\/schema\/person\/image\/"},"sameAs":["https:\/\/blog.taiyang.space"],"url":"https:\/\/blog.taiyang.space\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/posts\/464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=464"}],"version-history":[{"count":1,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/posts\/464\/revisions"}],"predecessor-version":[{"id":465,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=\/wp\/v2\/posts\/464\/revisions\/465"}],"wp:attachment":[{"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.taiyang.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}