{"id":1157,"date":"2025-11-07T16:09:33","date_gmt":"2025-11-07T08:09:33","guid":{"rendered":"https:\/\/www.youvii.site\/?p=1157"},"modified":"2025-11-07T16:09:33","modified_gmt":"2025-11-07T08:09:33","slug":"buuctf-cryptorsa","status":"publish","type":"post","link":"https:\/\/www.youvii.site\/index.php\/archives\/buuctf-cryptorsa","title":{"rendered":"BUUCTF-Crypto\uff1aRSA"},"content":{"rendered":"<h1>RSA<\/h1>\n<p>\u5728\u4e00\u6b21RSA\u5bc6\u94a5\u5bf9\u751f\u6210\u4e2d\uff0c\u5047\u8bbep=473398607161\uff0cq=4511491\uff0ce=17<br \/>\n\u6c42\u89e3\u51fad\u4f5c\u4e3aflga\u63d0\u4ea4<\/p>\n<p>\u6c42\u89e3\u8fc7\u7a0b\uff1a<\/p>\n<p>\u9996\u5148\u8ba1\u7b97n\u548c\u03d5(n)<\/p>\n<p>n=p*q  \u03d5(n)=(p-1)(q-1)<\/p>\n<p>d\u662fe\u5173\u4e8e\u6a21\u03d5(n)\u7684\u4e58\u6cd5\u9006\u5143\uff0c\u5373d\u22c5e\u22611 (mod \u03d5(n))<\/p>\n<p>\u6839\u636e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u6c42\u89e3d<\/p>\n<pre class=\"prettyprint linenums\" ><code class=\"language-python\"># \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a\u7528\u6765\u8ba1\u7b97 a \u548c b \u7684\u6700\u5927\u516c\u7ea6\u6570\uff0c\u540c\u65f6\u8fd4\u56de\u8d1d\u7956\u7cfb\u6570 x \u548c y\n# \u4f7f\u5f97 a * x + b * y = gcd(a, b)\ndef extended_gcd(a, b):\n    # \u57fa\u672c\u60c5\u51b5\uff0c\u5982\u679c b == 0\uff0c\u5219 gcd(a, b) = a, x = 1, y = 0\n    if b == 0:\n        return a, 1, 0\n    # \u9012\u5f52\u8c03\u7528\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff0c\u83b7\u53d6 gcd(a, b) \u548c\u8d1d\u7956\u7cfb\u6570 x, y\n    gcd, x1, y1 = extended_gcd(b, a % b)\n    # \u66f4\u65b0\u8d1d\u7956\u7cfb\u6570 x \u548c y\uff0c\u8fd4\u56de\u65b0\u7684\u7cfb\u6570\n    x = y1\n    y = x1 - (a \/\/ b) * y1\n    return gcd, x, y\n\n# \u6c42\u89e3\u6a21\u9006\u5143\uff1a\u5373\u6c42\u89e3 x \u4f7f\u5f97 a * x \u2261 1 (mod m)\ndef mod_inverse(a, m):\n    # \u8c03\u7528\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff0c\u83b7\u53d6 gcd(a, m), x, y\n    gcd, x, y = extended_gcd(a, m)\n\n    # \u5982\u679c a \u548c m \u4e0d\u662f\u4e92\u8d28\u7684\uff0c\u8bf4\u660e\u6ca1\u6709\u6a21\u9006\u5143\n    if gcd != 1:\n        raise ValueError(f\"{a} \u548c {m} \u6ca1\u6709\u4e92\u8d28\uff0c\u65e0\u6cd5\u6c42\u6a21\u9006\u5143\")\n    else:\n        # \u8fd4\u56de x \u7684\u6a21 m \u7ed3\u679c\uff0c\u5373\u4e3a a \u5173\u4e8e\u6a21 m \u7684\u9006\u5143\n        return x % m\n\n# \u4e3b\u51fd\u6570\uff1a\u6839\u636e\u7ed9\u5b9a\u7684 p, q \u548c e \u8ba1\u7b97 RSA \u79c1\u94a5 d\ndef rsa_private_key(p, q, e):\n    # \u8ba1\u7b97 RSA \u7684 n \u548c \u03c6(n)\n    n = p * q  # \u516c\u94a5\u7684\u6a21\u6570 n = p * q\n    phi_n = (p - 1) * (q - 1)  # \u6b27\u62c9\u51fd\u6570 \u03c6(n) = (p-1)(q-1)\n\n    # \u8ba1\u7b97 d = e^(-1) mod \u03c6(n)\uff0c\u5373 e \u7684\u6a21\u9006\u5143\n    d = mod_inverse(e, phi_n)\n\n    # \u8fd4\u56de\u8ba1\u7b97\u5f97\u5230\u7684\u79c1\u94a5 d\n    return d\n\n# \u7ed9\u5b9a\u7684 RSA \u53c2\u6570\np = 473398607161\nq = 4511491\ne = 17\n\n# \u8c03\u7528 rsa_private_key \u51fd\u6570\u8ba1\u7b97\u79c1\u94a5 d\nd = rsa_private_key(p, q, e)\n\n# \u8f93\u51fa\u8ba1\u7b97\u5f97\u5230\u7684\u79c1\u94a5 d\nprint(f\"\u79c1\u94a5 d \u7684\u503c\u4e3a: {d}\")<\/code><\/pre>\n<p><img loading="lazy" decoding="async" decoding=\"async\"  src=\"https:\/\/www.youvii.site\/wp-content\/themes\/lolimeow-lolimeowV13.13\/assets\/images\/loading.gif\" data-src=\"https:\/\/cdn.picui.cn\/vip\/2025\/11\/07\/690da78d4b5b6.png\" class=\"lazy\" loading=\"lazy\" alt=\"image-20251104135834640\" \/><\/p>\n<p>\u5f97\u5230flag{125631357777427553}<\/p>\n","protected":false},"excerpt":{"rendered":"<p>RSA \u5728\u4e00\u6b21RSA\u5bc6\u94a5\u5bf9\u751f\u6210\u4e2d\uff0c\u5047\u8bbep=473398607161\uff0cq=4511491\uff0ce=17 \u6c42\u89e3\u51fad\u4f5c\u4e3aflga\u63d0\u4ea4 \u6c42\u89e3\u8fc7\u7a0b\uff1a \u9996\u5148\u8ba1\u7b97n\u548c\u03d5(n) n=p*q \u03d5(n)=(p-1)(q-1) d\u662fe\u5173\u4e8e\u6a21\u03d5(n)\u7684\u4e58\u6cd5\u9006\u5143\uff0c\u5373d\u22c5e\u22611 (mod \u03d5(n)) \u6839\u636e\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\u6c42\u89e3d # \u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\uff1a\u7528\u6765\u8ba1\u7b97 a \u548c b \u7684\u6700\u5927\u516c\u7ea6\u6570\uff0c\u540c\u65f6\u8fd4\u56de\u8d1d\u7956\u7cfb\u6570 x \u548c y # \u4f7f\u5f97 a  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[126,114,113],"tags":[44,56,112],"class_list":["post-1157","post","type-post","status-publish","format-standard","hentry","category-buuctf","category-crypto","category-ctf","tag-44","tag-ctf","tag-crypto"],"_links":{"self":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/posts\/1157","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/comments?post=1157"}],"version-history":[{"count":0,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/posts\/1157\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/media?parent=1157"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/categories?post=1157"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/tags?post=1157"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}