{"id":4231,"date":"2024-07-03T14:24:53","date_gmt":"2024-07-03T06:24:53","guid":{"rendered":"https:\/\/www.aqwu.net\/wp\/?p=4231"},"modified":"2024-07-03T23:01:44","modified_gmt":"2024-07-03T15:01:44","slug":"rsa-%e7%a7%81%e9%92%a5%e9%87%8c%e9%9d%a2%e7%9a%84exponent1%e5%92%8cexponent2","status":"publish","type":"post","link":"https:\/\/www.aqwu.net\/wp\/?p=4231","title":{"rendered":"RSA \u79c1\u94a5\u91cc\u9762\u7684exponent1\u548cexponent2"},"content":{"rendered":"\n<p>\u5f53\u4f60\u4f7f\u7528 openssl \u547d\u4ee4\u89e3\u6790\u4e00\u4e2a\u79c1\u94a5\u7684\u65f6\u5019\uff0c\u4f1a\u51fa\u73b0 exponent1\u548c exponent2\uff0c\u6bd4\u5982\u5982\u4e0b\u7684\u4f8b\u5b50\uff0c\u53bb\u6389\u4e86\u90e8\u5206\u4fe1\u606f\uff1a<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:sh decode:true \">openssl rsa -in private.key -text -noout\nPrivate-Key: (2048 bit)\nmodulus:\n    00:f7:c0:63:6c:27:5e:f3:ab:b6:2e:6a:ee:a6:0c:\n    ......\n    f9:b1\npublicExponent: 65537 (0x10001)\nprivateExponent:\n    00:f1:73:1f:f2:01:94:ba:29:38:8d:98:4d:28:aa:\n    ......\n    a4:19\nprime1:\n    00:fe:e8:5d:62:81:4e:59:dd:53:22:dc:4e:94:36:\n    ......\n    16:66:ea:82:f0:84:b5:f8:f3\nprime2:\n    00:f8:d0:2c:59:4b:8f:20:77:4e:e0:11:34:c2:d6:\n    ......\n    44:99:2d:ff:2e:aa:b3:6b:cb\nexponent1:\n    4e:ab:63:f6:bc:b5:73:a2:8c:bf:db:82:1c:d7:db:\n    ......\n    7e:c1:ad:7b:91:59:9f:e5\nexponent2:\n    00:a9:3b:ee:ee:4d:96:6c:5e:ba:27:6d:8c:95:79:\n    ......\n    ea:4f:c6:19:6b:84:6f:c5:41\ncoefficient:\n    20:52:6a:76:51:aa:60:2c:1f:36:c7:ef:0e:f3:ef:\n    ......\n    02:a9:73:81:39:f0:d9:9e\n<\/pre><\/div>\n\n\n\n<p>\u5728RSA\u7b97\u6cd5\u4e2d\uff0c<code>exponent1<\/code>\u548c<code>exponent2<\/code>\u662f\u4e3a\u4e86\u63d0\u9ad8\u89e3\u5bc6\u548c\u7b7e\u540d\u901f\u5ea6\u800c\u5f15\u5165\u7684\u4f18\u5316\u53c2\u6570\u3002RSA\u5bc6\u94a5\u5bf9\u7531\u516c\u94a5\u548c\u79c1\u94a5\u7ec4\u6210\uff0c\u5176\u4e2d\u79c1\u94a5\u5305\u542b\u4e00\u4e9b\u989d\u5916\u7684\u4fe1\u606f\u4ee5\u52a0\u901f\u64cd\u4f5c, <code>coefficient<\/code>\u901a\u5e38\u6307\u7684\u662f<code>iqmp<\/code>\uff0c\u5373<code>q<\/code>\u7684\u6a21\u9006\u5728\u6a21<code>p<\/code>\u610f\u4e49\u4e0b\u7684\u503c\u3002<code>iqmp<\/code> \u662f<code>inverse of q mod p<\/code>\u7684\u7f29\u5199\u3002<\/p>\n\n\n\n<p>\u5177\u4f53\u6765\u8bf4\uff0c<code>exponent1<\/code>\u548c<code>exponent2,<code>coefficient<\/code><\/code> \u662f\u57fa\u4e8e\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08Chinese Remainder Theorem, CRT\uff09\u7684\u4f18\u5316\u7ed3\u679c\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u4f18\u5316<\/strong><\/h3>\n\n\n\n<p>\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u4f18\u5316\u662fRSA\u7684\u4e00\u79cd\u5e38\u7528\u4f18\u5316\u6280\u672f\uff0c\u7528\u6765\u52a0\u901fRSA\u7684\u89e3\u5bc6\u548c\u7b7e\u540d\u64cd\u4f5c\u3002\u4f7f\u7528CRT\u4f18\u5316\u53ef\u4ee5\u4f7f\u8fd9\u4e9b\u64cd\u4f5c\u7684\u901f\u5ea6\u63d0\u9ad8\u7ea6\u56db\u500d\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>\u79c1\u94a5\u7ed3\u6784<\/strong><\/h3>\n\n\n\n<p>\u4e00\u4e2a\u6807\u51c6\u7684RSA\u79c1\u94a5\uff0c\u9664\u4e86\u5305\u542b\u516c\u94a5\u548c\u79c1\u94a5\u7684\u57fa\u672c\u4fe1\u606f\u5916\uff0c\u8fd8\u5305\u542b\u4ee5\u4e0b\u51e0\u4e2a\u53c2\u6570\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>n<\/code>: \u6a21\u6570\uff08public modulus\uff09<\/li>\n\n\n\n<li><code>e<\/code>: \u516c\u94a5\u6307\u6570\uff08public exponent\uff09<\/li>\n\n\n\n<li><code>d<\/code>: \u79c1\u94a5\u6307\u6570\uff08private exponent\uff09<\/li>\n\n\n\n<li><code>p<\/code>: \u5927\u7d20\u65701<\/li>\n\n\n\n<li><code>q<\/code>: \u5927\u7d20\u65702<\/li>\n\n\n\n<li><code>dmp1<\/code>\uff08\u6216<code>exponent1<\/code>\uff09: <code>d mod (p-1)<\/code><\/li>\n\n\n\n<li><code>dmq1<\/code>\uff08\u6216<code>exponent2<\/code>\uff09: <code>d mod (q-1)<\/code><\/li>\n\n\n\n<li><code>iqmp<\/code>: <code>q<\/code>\u7684\u6a21\u9006\uff0c\u5373 <code>q^(-1) mod p<\/code><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong><code>exponent1<\/code>\u548c<code>exponent2<\/code><\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>exponent1<\/code>\uff08\u6216<code>dmp1<\/code>\uff09\u662f <code>d mod (p-1)<\/code>\uff0c\u5176\u4e2d <code>p<\/code> \u662fRSA\u7684\u4e00\u4e2a\u5927\u7d20\u6570\u3002<\/li>\n\n\n\n<li><code>exponent2<\/code>\uff08\u6216<code>dmq1<\/code>\uff09\u662f <code>d mod (q-1)<\/code>\uff0c\u5176\u4e2d <code>q<\/code> \u662fRSA\u7684\u53e6\u4e00\u4e2a\u5927\u7d20\u6570\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u8fd9\u4e9b\u53c2\u6570\u7684\u5f15\u5165\u662f\u4e3a\u4e86\u5229\u7528\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u52a0\u901f\u89e3\u5bc6\u548c\u7b7e\u540d\u64cd\u4f5c\u3002\u5177\u4f53\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>1. \u8ba1\u7b97\u4e2d\u95f4\u7ed3\u679c\uff1a<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u4f7f\u7528 <code>exponent1<\/code> \u548c <code>p<\/code> \u8ba1\u7b97\u4e2d\u95f4\u7ed3\u679c <code>m1<\/code>\uff1a<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \">m1 = c^exponent1 mod p\n<\/pre><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u4f7f\u7528 <code>exponent2<\/code> \u548c <code>q<\/code> \u8ba1\u7b97\u4e2d\u95f4\u7ed3\u679c <code>m2<\/code>\uff1a<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \">m2 = c^exponent2 mod q\n<\/pre><\/div>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>2. \u5408\u5e76\u4e2d\u95f4\u7ed3\u679c\uff1a<\/strong><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u4f7f\u7528 <code>iqmp<\/code> \u6765\u5408\u5e76 <code>m1<\/code> \u548c <code>m2<\/code>\uff0c\u5f97\u5230\u6700\u7ec8\u7ed3\u679c <code>m<\/code>\uff1a<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \">h = (iqmp * (m1 - m2)) mod p\nm = m2 + h * q\n<\/pre><\/div>\n\n\n\n<p>\u901a\u8fc7\u8fd9\u4e9b\u6b65\u9aa4\uff0c\u89e3\u5bc6\u548c\u7b7e\u540d\u64cd\u4f5c\u90fd\u53ef\u4ee5\u663e\u8457\u52a0\u901f\uff0c\u56e0\u4e3a\u6307\u6570\u8fd0\u7b97\u7684\u6a21\u6570\u4ece <code>n<\/code>\uff08\u5927\u7d20\u6570\u7684\u4e58\u79ef\uff09\u51cf\u5c11\u5230\u4e86 <code>p<\/code> \u548c <code>q<\/code>\uff08\u4e24\u4e2a\u8f83\u5c0f\u7684\u7d20\u6570\uff09\uff0c\u8fd9\u4f7f\u5f97\u8ba1\u7b97\u66f4\u52a0\u9ad8\u6548\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7ed3\u8bba<\/h3>\n\n\n\n<p><code>exponent1<\/code> \u548c <code>exponent2<\/code> \u662f\u57fa\u4e8e\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u4f18\u5316RSA\u89e3\u5bc6\u548c\u7b7e\u540d\u64cd\u4f5c\u7684\u53c2\u6570\uff0c\u5b83\u4eec\u4f7f\u8fd9\u4e9b\u64cd\u4f5c\u7684\u901f\u5ea6\u663e\u8457\u63d0\u9ad8\u3002\u56e0\u6b64\uff0c\u5728RSA\u79c1\u94a5\u4e2d\u5305\u542b\u8fd9\u4e9b\u53c2\u6570\u662f\u4e3a\u4e86\u589e\u5f3a\u6027\u80fd\uff0c\u5e76\u4e14\u8fd9\u662f\u6807\u51c6\u7684RSA\u5b9e\u73b0\u4e2d\u7684\u5e38\u89c1\u505a\u6cd5\u3002<\/p>\n\n\n\n<p>\u7528Python\u4ee3\u7801\u6765\u9a8c\u8bc1RSA\u89e3\u5bc6\u8fc7\u7a0b\uff0c\u7279\u522b\u662f\u4f7f\u7528\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08CRT\uff09\u4f18\u5316\u7684\u90e8\u5206\uff1a<\/p>\n\n\n\n<p>\u9700\u8981\u5148\u5b89\u88c5 pycryptodome<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:sh decode:true \" >pip install pycryptodome<\/pre><\/div>\n\n\n\n<p>\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:python decode:true \" >from Crypto.Util.number import inverse, long_to_bytes\n\n# RSA\u53c2\u6570\np = 61\nq = 53\nn = p * q\ne = 7\nphi = (p - 1) * (q - 1)\nd = inverse(e, phi)\n\n# \u9884\u8ba1\u7b97CRT\u53c2\u6570\ndmp1 = d % (p - 1)\ndmq1 = d % (q - 1)\niqmp = inverse(q, p)\n\n# \u52a0\u5bc6\u6d88\u606f\nm = 65\nc = pow(m, e, n)\nprint(f'\u52a0\u5bc6\u540e\u7684\u6d88\u606f (c): {c}')\n\n# \u4f7f\u7528\u6807\u51c6\u65b9\u6cd5\u89e3\u5bc6\nm1_standard = pow(c, d, n)\nprint(f'\u4f7f\u7528\u6807\u51c6\u65b9\u6cd5\u89e3\u5bc6\u540e\u7684\u6d88\u606f: {m1_standard}')\n\n# \u4f7f\u7528CRT\u65b9\u6cd5\u89e3\u5bc6\nm1 = pow(c, dmp1, p)\nm2 = pow(c, dmq1, q)\nh = (m1 - m2) * iqmp % p\nm_crt = m2 + h * q\n\nprint(f'\u4f7f\u7528CRT\u65b9\u6cd5\u89e3\u5bc6\u540e\u7684\u6d88\u606f: {m_crt}')\n<\/pre><\/div>\n\n\n\n<p>\u8fd0\u884c\u8fd9\u4e2a\u4ee3\u7801\uff0c\u6211\u4eec\u53ef\u4ee5\u9a8c\u8bc1\u89e3\u5bc6\u8fc7\u7a0b\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u4ee3\u7801\u89e3\u91ca<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u53c2\u6570\u8bbe\u7f6e<\/strong>\uff1a\n<ul class=\"wp-block-list\">\n<li>p \u548c q \u662f\u4e24\u4e2a\u5927\u7d20\u6570<\/li>\n\n\n\n<li>n = p\u00d7q \u662f\u6a21\u6570<\/li>\n\n\n\n<li>e = 3 \u662f\u516c\u94a5\u6307\u6570<\/li>\n\n\n\n<li>\u03d5 = (p\u22121)\u00d7(q\u22121) \u662f\u6b27\u62c9\u51fd\u6570<\/li>\n\n\n\n<li>d  \u662f\u79c1\u94a5\u6307\u6570\uff0c\u6ee1\u8db3 d\u00d7e \u2261 1 mod\u2009\u03d5<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u9884\u8ba1\u7b97CRT\u53c2\u6570<\/strong>\uff1a\n<ul class=\"wp-block-list\">\n<li><code>dmp1<\/code> \u662f d mod (p\u22121)<\/li>\n\n\n\n<li><code>dmq1<\/code> \u662f d mod (q\u22121)<\/li>\n\n\n\n<li><code>iqmp<\/code> \u662f q<sup>\u22121<\/sup> mod p\uff0c\u5373 <code>coefficient<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u52a0\u5bc6\u6d88\u606f<\/strong>\uff1a\n<ul class=\"wp-block-list\">\n<li>\u5bf9\u6d88\u606f m = 65 \u8fdb\u884c\u52a0\u5bc6\uff0c\u8ba1\u7b97 c = m<sup>e<\/sup> mod n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>\u89e3\u5bc6\u6d88\u606f<\/strong>\uff1a\n<ul class=\"wp-block-list\">\n<li>\u4f7f\u7528\u6807\u51c6\u65b9\u6cd5\u89e3\u5bc6\uff1a\u8ba1\u7b97 m1<sub>standard<\/sub> = c<sup>d<\/sup> mod\u2009\u2009n<\/li>\n\n\n\n<li>\u4f7f\u7528CRT\u65b9\u6cd5\u89e3\u5bc6\uff1a\u8ba1\u7b97 m1 = c<sup>dmp1<\/sup>mod\u2009\u2009p \u548c m2 = c<sup>dmq1<\/sup> mod\u2009\u2009q\uff0c\u7136\u540e\u5408\u5e76\u7ed3\u679c<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>\u901a\u8fc7\u8fd9\u4e2a\u793a\u4f8b\uff0c\u6211\u4eec\u53ef\u4ee5\u6e05\u695a\u5730\u770b\u5230\uff0c<code>coefficient<\/code>\uff08\u5373<code>iqmp<\/code>\uff09\u5728CRT\u4f18\u5316\u4e2d\u7684\u4f5c\u7528\uff0c\u4ee5\u53ca\u5982\u4f55\u6b63\u786e\u4f7f\u7528\u5b83\u6765\u52a0\u901fRSA\u89e3\u5bc6\u8fc7\u7a0b\u3002<\/p>\n\n\n\n<p>\u8fd0\u884c\u4e0a\u8ff0\u4ee3\u7801\u540e\uff0c\u4f60\u5e94\u8be5\u770b\u5230\u8f93\u51fa\uff1a<\/p>\n\n\n\n<div class=\"wp-block-urvanov-syntax-highlighter-code-block\"><pre class=\"lang:sh decode:true \" >\u52a0\u5bc6\u540e\u7684\u6d88\u606f (c): 1317\n\u4f7f\u7528\u6807\u51c6\u65b9\u6cd5\u89e3\u5bc6\u540e\u7684\u6d88\u606f: 65\n\u4f7f\u7528CRT\u65b9\u6cd5\u89e3\u5bc6\u540e\u7684\u6d88\u606f: 65\n<\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5f53\u4f60\u4f7f\u7528 openssl \u547d\u4ee4\u89e3\u6790\u4e00\u4e2a\u79c1\u94a5\u7684\u65f6\u5019\uff0c\u4f1a\u51fa\u73b0 exponent1\u548c exponent2\uff0c\u6bd4\u5982\u5982\u4e0b\u7684 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"set","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[59],"tags":[511,512,390],"class_list":["post-4231","post","type-post","status-publish","format-standard","hentry","category-linux","tag-exponent1","tag-exponet2","tag-rsa"],"views":1920,"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4231","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4231"}],"version-history":[{"count":11,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4231\/revisions"}],"predecessor-version":[{"id":4244,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/4231\/revisions\/4244"}],"wp:attachment":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4231"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4231"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}