{"id":2016,"date":"2024-01-23T23:06:39","date_gmt":"2024-01-23T15:06:39","guid":{"rendered":"https:\/\/www.aqwu.net\/wp\/?p=2016"},"modified":"2024-01-23T23:41:22","modified_gmt":"2024-01-23T15:41:22","slug":"rsa%e7%ae%97%e6%b3%95%e5%8e%9f%e7%90%86%ef%bc%88%e4%ba%8c%ef%bc%89","status":"publish","type":"post","link":"https:\/\/www.aqwu.net\/wp\/?p=2016","title":{"rendered":"RSA\u7b97\u6cd5\u539f\u7406\uff08\u4e8c\uff09"},"content":{"rendered":"\n

\u4e0a\u4e00\u6b21\uff0c\u6211\u4ecb\u7ecd\u4e86\u4e00\u4e9bRSA\u7b97\u6cd5\u539f\u7406\uff08\u4e00\uff09<\/a>\u3002<\/p>\n\n\n\n

\u6709\u4e86\u8fd9\u4e9b\u77e5\u8bc6\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u770b\u61c2RSA\u7b97\u6cd5<\/a>\u3002\u8fd9\u662f\u76ee\u524d\u5730\u7403\u4e0a\u6700\u91cd\u8981\u7684\u52a0\u5bc6\u7b97\u6cd5\u3002<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

\u516d\u3001\u5bc6\u94a5\u751f\u6210\u7684\u6b65\u9aa4<\/strong><\/p>\n\n\n\n

\u6211\u4eec\u901a\u8fc7\u4e00\u4e2a\u4f8b\u5b50\uff0c\u6765\u7406\u89e3RSA\u7b97\u6cd5\u3002\u5047\u8bbe\u7231\u4e3d\u4e1d<\/a>\u8981\u4e0e\u9c8d\u52c3\u8fdb\u884c\u52a0\u5bc6\u901a\u4fe1\uff0c\u5979\u8be5\u600e\u4e48\u751f\u6210\u516c\u94a5\u548c\u79c1\u94a5\u5462\uff1f<\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n

\u7b2c\u4e00\u6b65\uff0c\u968f\u673a\u9009\u62e9\u4e24\u4e2a\u4e0d\u76f8\u7b49\u7684\u8d28\u6570p\u548cq\u3002<\/strong><\/p>\n\n\n\n

\u7231\u4e3d\u4e1d\u9009\u62e9\u4e8661\u548c53\u3002\uff08\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u8fd9\u4e24\u4e2a\u8d28\u6570\u8d8a\u5927\uff0c\u5c31\u8d8a\u96be\u7834\u89e3\u3002\uff09<\/p>\n\n\n\n

\u7b2c\u4e8c\u6b65\uff0c\u8ba1\u7b97p\u548cq\u7684\u4e58\u79efn\u3002<\/strong><\/p>\n\n\n\n

\u7231\u4e3d\u4e1d\u5c31\u628a61\u548c53\u76f8\u4e58\u3002<\/p>\n\n\n\n

\n

n = 61\u00d753 = 3233<\/p>\n<\/blockquote>\n\n\n\n

n\u7684\u957f\u5ea6\u5c31\u662f\u5bc6\u94a5\u957f\u5ea6\u30023233\u5199\u6210\u4e8c\u8fdb\u5236\u662f110010100001\uff0c\u4e00\u5171\u670912\u4f4d\uff0c\u6240\u4ee5\u8fd9\u4e2a\u5bc6\u94a5\u5c31\u662f12\u4f4d\u3002\u5b9e\u9645\u5e94\u7528\u4e2d\uff0cRSA\u5bc6\u94a5\u4e00\u822c\u662f1024\u4f4d\uff0c\u91cd\u8981\u573a\u5408\u5219\u4e3a2048\u4f4d\u3002<\/p>\n\n\n\n

\u7b2c\u4e09\u6b65\uff0c\u8ba1\u7b97n\u7684\u6b27\u62c9\u51fd\u6570\u03c6(n)\u3002<\/strong><\/p>\n\n\n\n

\u6839\u636e\u516c\u5f0f\uff1a<\/p>\n\n\n\n

\n

\u03c6(n) = (p-1)(q-1)<\/p>\n<\/blockquote>\n\n\n\n

\u7231\u4e3d\u4e1d\u7b97\u51fa\u03c6(3233)\u7b49\u4e8e60\u00d752\uff0c\u53733120\u3002<\/p>\n\n\n\n

\u7b2c\u56db\u6b65\uff0c\u968f\u673a\u9009\u62e9\u4e00\u4e2a\u6574\u6570e\uff0c\u6761\u4ef6\u662f1< e < \u03c6(n)\uff0c\u4e14e\u4e0e\u03c6(n) \u4e92\u8d28\u3002<\/strong><\/p>\n\n\n\n

\u7231\u4e3d\u4e1d\u5c31\u57281\u52303120\u4e4b\u95f4\uff0c\u968f\u673a\u9009\u62e9\u4e8617\u3002\uff08\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u5e38\u5e38\u9009\u62e965537\u3002\uff09<\/p>\n\n\n\n

\u7b2c\u4e94\u6b65\uff0c\u8ba1\u7b97e\u5bf9\u4e8e\u03c6(n)\u7684\u6a21\u53cd\u5143\u7d20d\u3002<\/strong><\/p>\n\n\n\n

\u6240\u8c13“\u6a21\u53cd\u5143\u7d20”<\/a>\u5c31\u662f\u6307\u6709\u4e00\u4e2a\u6574\u6570d\uff0c\u53ef\u4ee5\u4f7f\u5f97ed\u88ab\u03c6(n)\u9664\u7684\u4f59\u6570\u4e3a1\u3002<\/p>\n\n\n\n

\n

ed \u2261 1 (mod \u03c6(n))<\/p>\n<\/blockquote>\n\n\n\n

\u8fd9\u4e2a\u5f0f\u5b50\u7b49\u4ef7\u4e8e<\/p>\n\n\n\n

\n

ed – 1 = k\u03c6(n)<\/p>\n<\/blockquote>\n\n\n\n

\u4e8e\u662f\uff0c\u627e\u5230\u6a21\u53cd\u5143\u7d20d\uff0c\u5b9e\u8d28\u4e0a\u5c31\u662f\u5bf9\u4e0b\u9762\u8fd9\u4e2a\u4e8c\u5143\u4e00\u6b21\u65b9\u7a0b\u6c42\u89e3\u3002<\/p>\n\n\n\n

\n

ex + \u03c6(n)y = 1<\/p>\n<\/blockquote>\n\n\n\n

\u5df2\u77e5 e=17, \u03c6(n)=3120\uff0c<\/p>\n\n\n\n

\n

17x + 3120y = 1<\/p>\n<\/blockquote>\n\n\n\n

\u8fd9\u4e2a\u65b9\u7a0b\u53ef\u4ee5\u7528“\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5”<\/a>\u6c42\u89e3\uff0c\u6b64\u5904\u7701\u7565\u5177\u4f53\u8fc7\u7a0b\u3002\u603b\u4e4b\uff0c\u7231\u4e3d\u4e1d\u7b97\u51fa\u4e00\u7ec4\u6574\u6570\u89e3\u4e3a (x,y)=(2753,-15)\uff0c\u5373 d=2753\u3002<\/p>\n\n\n\n

\u81f3\u6b64\u6240\u6709\u8ba1\u7b97\u5b8c\u6210\u3002<\/p>\n\n\n\n

\u7b2c\u516d\u6b65\uff0c\u5c06n\u548ce\u5c01\u88c5\u6210\u516c\u94a5\uff0cn\u548cd\u5c01\u88c5\u6210\u79c1\u94a5\u3002<\/strong><\/p>\n\n\n\n

\u5728\u7231\u4e3d\u4e1d\u7684\u4f8b\u5b50\u4e2d\uff0cn=3233\uff0ce=17\uff0cd=2753\uff0c\u6240\u4ee5\u516c\u94a5\u5c31\u662f (3233,17)\uff0c\u79c1\u94a5\u5c31\u662f\uff083233, 2753\uff09\u3002<\/p>\n\n\n\n

\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u516c\u94a5\u548c\u79c1\u94a5\u7684\u6570\u636e\u90fd\u91c7\u7528ASN.1<\/a>\u683c\u5f0f\u8868\u8fbe\uff08\u5b9e\u4f8b<\/a>\uff09\u3002<\/p>\n\n\n\n

\u4e03\u3001RSA\u7b97\u6cd5\u7684\u53ef\u9760\u6027<\/strong><\/p>\n\n\n\n

\u56de\u987e\u4e0a\u9762\u7684\u5bc6\u94a5\u751f\u6210\u6b65\u9aa4\uff0c\u4e00\u5171\u51fa\u73b0\u516d\u4e2a\u6570\u5b57\uff1a<\/p>\n\n\n\n

\n

p
q
n
\u03c6(n)
e
d<\/p>\n<\/blockquote>\n\n\n\n

\u8fd9\u516d\u4e2a\u6570\u5b57\u4e4b\u4e2d\uff0c\u516c\u94a5\u7528\u5230\u4e86\u4e24\u4e2a\uff08n\u548ce\uff09\uff0c\u5176\u4f59\u56db\u4e2a\u6570\u5b57\u90fd\u662f\u4e0d\u516c\u5f00\u7684\u3002\u5176\u4e2d\u6700\u5173\u952e\u7684\u662fd\uff0c\u56e0\u4e3an\u548cd\u7ec4\u6210\u4e86\u79c1\u94a5\uff0c\u4e00\u65e6d\u6cc4\u6f0f\uff0c\u5c31\u7b49\u4e8e\u79c1\u94a5\u6cc4\u6f0f\u3002<\/p>\n\n\n\n

\u90a3\u4e48\uff0c\u6709\u65e0\u53ef\u80fd\u5728\u5df2\u77e5n\u548ce\u7684\u60c5\u51b5\u4e0b\uff0c\u63a8\u5bfc\u51fad\uff1f<\/strong><\/p>\n\n\n\n

\n

\uff081\uff09ed\u22611 (mod \u03c6(n))\u3002\u53ea\u6709\u77e5\u9053e\u548c\u03c6(n)\uff0c\u624d\u80fd\u7b97\u51fad\u3002<\/p>\n\n\n\n

\uff082\uff09\u03c6(n)=(p-1)(q-1)\u3002\u53ea\u6709\u77e5\u9053p\u548cq\uff0c\u624d\u80fd\u7b97\u51fa\u03c6(n)\u3002<\/p>\n\n\n\n

\uff083\uff09n=pq\u3002\u53ea\u6709\u5c06n\u56e0\u6570\u5206\u89e3\uff0c\u624d\u80fd\u7b97\u51fap\u548cq\u3002<\/p>\n<\/blockquote>\n\n\n\n

\u7ed3\u8bba\uff1a\u5982\u679cn\u53ef\u4ee5\u88ab\u56e0\u6570\u5206\u89e3\uff0cd\u5c31\u53ef\u4ee5\u7b97\u51fa\uff0c\u4e5f\u5c31\u610f\u5473\u7740\u79c1\u94a5\u88ab\u7834\u89e3\u3002<\/strong><\/p>\n\n\n\n

\u53ef\u662f\uff0c\u5927\u6574\u6570\u7684\u56e0\u6570\u5206\u89e3\uff0c\u662f\u4e00\u4ef6\u975e\u5e38\u56f0\u96be\u7684\u4e8b\u60c5\u3002\u76ee\u524d\uff0c\u9664\u4e86\u66b4\u529b\u7834\u89e3\uff0c\u8fd8\u6ca1\u6709\u53d1\u73b0\u522b\u7684\u6709\u6548\u65b9\u6cd5\u3002\u7ef4\u57fa\u767e\u79d1\u8fd9\u6837\u5199\u9053\uff1a<\/p>\n\n\n\n

\n

“\u5bf9\u6781\u5927\u6574\u6570\u505a\u56e0\u6570\u5206\u89e3\u7684\u96be\u5ea6\u51b3\u5b9a\u4e86RSA\u7b97\u6cd5\u7684\u53ef\u9760\u6027\u3002\u6362\u8a00\u4e4b\uff0c\u5bf9\u4e00\u6781\u5927\u6574\u6570\u505a\u56e0\u6570\u5206\u89e3\u6108\u56f0\u96be\uff0cRSA\u7b97\u6cd5\u6108\u53ef\u9760\u3002<\/p>\n\n\n\n

\u5047\u5982\u6709\u4eba\u627e\u5230\u4e00\u79cd\u5feb\u901f\u56e0\u6570\u5206\u89e3\u7684\u7b97\u6cd5\uff0c\u90a3\u4e48RSA\u7684\u53ef\u9760\u6027\u5c31\u4f1a\u6781\u5ea6\u4e0b\u964d\u3002\u4f46\u627e\u5230\u8fd9\u6837\u7684\u7b97\u6cd5\u7684\u53ef\u80fd\u6027\u662f\u975e\u5e38\u5c0f\u7684\u3002\u4eca\u5929\u53ea\u6709\u77ed\u7684RSA\u5bc6\u94a5\u624d\u53ef\u80fd\u88ab\u66b4\u529b\u7834\u89e3\u3002\u52302008\u5e74\u4e3a\u6b62\uff0c\u4e16\u754c\u4e0a\u8fd8\u6ca1\u6709\u4efb\u4f55\u53ef\u9760\u7684\u653b\u51fbRSA\u7b97\u6cd5\u7684\u65b9\u5f0f\u3002<\/p>\n\n\n\n

\u53ea\u8981\u5bc6\u94a5\u957f\u5ea6\u8db3\u591f\u957f\uff0c\u7528RSA\u52a0\u5bc6\u7684\u4fe1\u606f\u5b9e\u9645\u4e0a\u662f\u4e0d\u80fd\u88ab\u89e3\u7834\u7684\u3002”<\/p>\n<\/blockquote>\n\n\n\n

\u4e3e\u4f8b\u6765\u8bf4\uff0c\u4f60\u53ef\u4ee5\u5bf93233\u8fdb\u884c\u56e0\u6570\u5206\u89e3\uff0861\u00d753\uff09\uff0c\u4f46\u662f\u4f60\u6ca1\u6cd5\u5bf9\u4e0b\u9762\u8fd9\u4e2a\u6574\u6570\u8fdb\u884c\u56e0\u6570\u5206\u89e3\u3002<\/p>\n\n\n\n

\n

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413<\/p>\n<\/blockquote>\n\n\n\n

\u5b83\u7b49\u4e8e\u8fd9\u6837\u4e24\u4e2a\u8d28\u6570\u7684\u4e58\u79ef\uff1a<\/p>\n\n\n\n

\n

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
\u3000\u3000\u00d7
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917<\/p>\n<\/blockquote>\n\n\n\n

\u4e8b\u5b9e\u4e0a\uff0c\u8fd9\u5927\u6982\u662f\u4eba\u7c7b\u5df2\u7ecf\u5206\u89e3\u7684\u6700\u5927\u6574\u6570\uff08232\u4e2a\u5341\u8fdb\u5236\u4f4d\uff0c768\u4e2a\u4e8c\u8fdb\u5236\u4f4d\uff09\u3002\u6bd4\u5b83\u66f4\u5927\u7684\u56e0\u6570\u5206\u89e3\uff0c\u8fd8\u6ca1\u6709\u88ab\u62a5\u9053\u8fc7\uff0c\u56e0\u6b64\u76ee\u524d\u88ab\u7834\u89e3\u7684\u6700\u957fRSA\u5bc6\u94a5\u5c31\u662f768\u4f4d\u3002<\/p>\n\n\n\n

\u516b\u3001\u52a0\u5bc6\u548c\u89e3\u5bc6<\/strong><\/p>\n\n\n\n

\u6709\u4e86\u516c\u94a5\u548c\u5bc6\u94a5\uff0c\u5c31\u80fd\u8fdb\u884c\u52a0\u5bc6\u548c\u89e3\u5bc6\u4e86\u3002<\/p>\n\n\n\n

\uff081\uff09\u52a0\u5bc6\u8981\u7528\u516c\u94a5 (n,e)<\/strong><\/p>\n\n\n\n

\u5047\u8bbe\u9c8d\u52c3\u8981\u5411\u7231\u4e3d\u4e1d\u53d1\u9001\u52a0\u5bc6\u4fe1\u606fm\uff0c\u4ed6\u5c31\u8981\u7528\u7231\u4e3d\u4e1d\u7684\u516c\u94a5 (n,e) \u5bf9m\u8fdb\u884c\u52a0\u5bc6\u3002\u8fd9\u91cc\u9700\u8981\u6ce8\u610f\uff0cm\u5fc5\u987b\u662f\u6574\u6570\uff08\u5b57\u7b26\u4e32\u53ef\u4ee5\u53d6ascii\u503c\u6216unicode\u503c\uff09\uff0c\u4e14m\u5fc5\u987b\u5c0f\u4e8en\u3002<\/p>\n\n\n\n

\u6240\u8c13”\u52a0\u5bc6”\uff0c\u5c31\u662f\u7b97\u51fa\u4e0b\u5f0f\u7684c\uff1a<\/p>\n\n\n\n

\n

me<\/sup>\u00a0\u2261 c (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u7231\u4e3d\u4e1d\u7684\u516c\u94a5\u662f (3233, 17)\uff0c\u9c8d\u52c3\u7684m\u5047\u8bbe\u662f65\uff0c\u90a3\u4e48\u53ef\u4ee5\u7b97\u51fa\u4e0b\u9762\u7684\u7b49\u5f0f\uff1a<\/p>\n\n\n\n

\n

6517<\/sup>\u00a0\u2261 2790 (mod 3233)<\/p>\n<\/blockquote>\n\n\n\n

\u4e8e\u662f\uff0cc\u7b49\u4e8e2790\uff0c\u9c8d\u52c3\u5c31\u628a2790\u53d1\u7ed9\u4e86\u7231\u4e3d\u4e1d\u3002<\/p>\n\n\n\n

\uff082\uff09\u89e3\u5bc6\u8981\u7528\u79c1\u94a5(n,d)<\/strong><\/p>\n\n\n\n

\u7231\u4e3d\u4e1d\u62ff\u5230\u9c8d\u52c3\u53d1\u6765\u76842790\u4ee5\u540e\uff0c\u5c31\u7528\u81ea\u5df1\u7684\u79c1\u94a5(3233, 2753) \u8fdb\u884c\u89e3\u5bc6\u3002\u53ef\u4ee5\u8bc1\u660e\uff0c\u4e0b\u9762\u7684\u7b49\u5f0f\u4e00\u5b9a\u6210\u7acb\uff1a<\/p>\n\n\n\n

\n

cd<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u4e5f\u5c31\u662f\u8bf4\uff0cc\u7684d\u6b21\u65b9\u9664\u4ee5n\u7684\u4f59\u6570\u4e3am\u3002\u73b0\u5728\uff0cc\u7b49\u4e8e2790\uff0c\u79c1\u94a5\u662f(3233, 2753)\uff0c\u90a3\u4e48\uff0c\u7231\u4e3d\u4e1d\u7b97\u51fa<\/p>\n\n\n\n

\n

27902753<\/sup>\u00a0\u2261 65 (mod 3233)<\/p>\n<\/blockquote>\n\n\n\n

\u56e0\u6b64\uff0c\u7231\u4e3d\u4e1d\u77e5\u9053\u4e86\u9c8d\u52c3\u52a0\u5bc6\u524d\u7684\u539f\u6587\u5c31\u662f65\u3002<\/p>\n\n\n\n

\u81f3\u6b64\uff0c”\u52a0\u5bc6–\u89e3\u5bc6”\u7684\u6574\u4e2a\u8fc7\u7a0b\u5168\u90e8\u5b8c\u6210\u3002<\/p>\n\n\n\n

\u6211\u4eec\u53ef\u4ee5\u770b\u5230\uff0c\u5982\u679c\u4e0d\u77e5\u9053d\uff0c\u5c31\u6ca1\u6709\u529e\u6cd5\u4ecec\u6c42\u51fam\u3002\u800c\u524d\u9762\u5df2\u7ecf\u8bf4\u8fc7\uff0c\u8981\u77e5\u9053d\u5c31\u5fc5\u987b\u5206\u89e3n\uff0c\u8fd9\u662f\u6781\u96be\u505a\u5230\u7684\uff0c\u6240\u4ee5RSA\u7b97\u6cd5\u4fdd\u8bc1\u4e86\u901a\u4fe1\u5b89\u5168\u3002<\/p>\n\n\n\n

\u4f60\u53ef\u80fd\u4f1a\u95ee\uff0c\u516c\u94a5(n,e) \u53ea\u80fd\u52a0\u5bc6\u5c0f\u4e8en\u7684\u6574\u6570m\uff0c\u90a3\u4e48\u5982\u679c\u8981\u52a0\u5bc6\u5927\u4e8en\u7684\u6574\u6570\uff0c\u8be5\u600e\u4e48\u529e\uff1f\u6709\u4e24\u79cd\u89e3\u51b3\u65b9\u6cd5\uff1a\u4e00\u79cd\u662f\u628a\u957f\u4fe1\u606f\u5206\u5272\u6210\u82e5\u5e72\u6bb5\u77ed\u6d88\u606f\uff0c\u6bcf\u6bb5\u5206\u522b\u52a0\u5bc6\uff1b\u53e6\u4e00\u79cd\u662f\u5148\u9009\u62e9\u4e00\u79cd”\u5bf9\u79f0\u6027\u52a0\u5bc6\u7b97\u6cd5”\uff08\u6bd4\u5982DES<\/a>\uff09\uff0c\u7528\u8fd9\u79cd\u7b97\u6cd5\u7684\u5bc6\u94a5\u52a0\u5bc6\u4fe1\u606f\uff0c\u518d\u7528RSA\u516c\u94a5\u52a0\u5bc6DES\u5bc6\u94a5\u3002<\/p>\n\n\n\n

\u4e5d\u3001\u79c1\u94a5\u89e3\u5bc6\u7684\u8bc1\u660e<\/strong><\/p>\n\n\n\n

\u6700\u540e\uff0c\u6211\u4eec\u6765\u8bc1\u660e\uff0c\u4e3a\u4ec0\u4e48\u7528\u79c1\u94a5\u89e3\u5bc6\uff0c\u4e00\u5b9a\u53ef\u4ee5\u6b63\u786e\u5730\u5f97\u5230m\u3002\u4e5f\u5c31\u662f\u8bc1\u660e\u4e0b\u9762\u8fd9\u4e2a\u5f0f\u5b50\uff1a<\/p>\n\n\n\n

\n

cd<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u56e0\u4e3a\uff0c\u6839\u636e\u52a0\u5bc6\u89c4\u5219<\/p>\n\n\n\n

\n

\uff4de<\/sup>\u00a0\u2261 c (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u4e8e\u662f\uff0cc\u53ef\u4ee5\u5199\u6210\u4e0b\u9762\u7684\u5f62\u5f0f\uff1a<\/p>\n\n\n\n

\n

c = me<\/sup>\u00a0– kn<\/p>\n<\/blockquote>\n\n\n\n

\u5c06c\u4ee3\u5165\u8981\u6211\u4eec\u8981\u8bc1\u660e\u7684\u90a3\u4e2a\u89e3\u5bc6\u89c4\u5219\uff1a<\/p>\n\n\n\n

\n

(me<\/sup>\u00a0– kn)d<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u5b83\u7b49\u540c\u4e8e\u6c42\u8bc1<\/p>\n\n\n\n

\n

med<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u7531\u4e8e<\/p>\n\n\n\n

\n

ed \u2261 1 (mod \u03c6(n))<\/p>\n<\/blockquote>\n\n\n\n

\u6240\u4ee5<\/p>\n\n\n\n

\n

ed = h\u03c6(n)+1<\/p>\n<\/blockquote>\n\n\n\n

\u5c06ed\u4ee3\u5165\uff1a<\/p>\n\n\n\n

\n

mh\u03c6(n)+1<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u63a5\u4e0b\u6765\uff0c\u5206\u6210\u4e24\u79cd\u60c5\u51b5\u8bc1\u660e\u4e0a\u9762\u8fd9\u4e2a\u5f0f\u5b50\u3002<\/p>\n\n\n\n

\uff081\uff09m\u4e0en\u4e92\u8d28\u3002<\/strong><\/p>\n\n\n\n

\u6839\u636e\u6b27\u62c9\u5b9a\u7406\uff0c\u6b64\u65f6<\/p>\n\n\n\n

\n

m\u03c6(n)<\/sup>\u00a0\u2261 1 (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u5f97\u5230<\/p>\n\n\n\n

\n

(m\u03c6(n)<\/sup>)h<\/sup>\u00a0\u00d7 m \u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u539f\u5f0f\u5f97\u5230\u8bc1\u660e\u3002<\/p>\n\n\n\n

\uff082\uff09m\u4e0en\u4e0d\u662f\u4e92\u8d28\u5173\u7cfb\u3002<\/strong><\/p>\n\n\n\n

\u6b64\u65f6\uff0c\u7531\u4e8en\u7b49\u4e8e\u8d28\u6570p\u548cq\u7684\u4e58\u79ef\uff0c\u6240\u4ee5m\u5fc5\u7136\u7b49\u4e8ekp\u6216kq\u3002<\/p>\n\n\n\n

\u4ee5 m = kp\u4e3a\u4f8b\uff0c\u8003\u8651\u5230\u8fd9\u65f6k\u4e0eq\u5fc5\u7136\u4e92\u8d28\uff0c\u5219\u6839\u636e\u6b27\u62c9\u5b9a\u7406\uff0c\u4e0b\u9762\u7684\u5f0f\u5b50\u6210\u7acb\uff1a<\/p>\n\n\n\n

\n

(kp)q-1<\/sup>\u00a0\u2261 1 (mod q)<\/p>\n<\/blockquote>\n\n\n\n

\u8fdb\u4e00\u6b65\u5f97\u5230<\/p>\n\n\n\n

\n

[(kp)q-1<\/sup>]h(p-1)<\/sup>\u00a0\u00d7 kp \u2261 kp (mod q)<\/p>\n<\/blockquote>\n\n\n\n

\u5373<\/p>\n\n\n\n

\n

(kp)ed<\/sup>\u00a0\u2261 kp (mod q)<\/p>\n<\/blockquote>\n\n\n\n

\u5c06\u5b83\u6539\u5199\u6210\u4e0b\u9762\u7684\u7b49\u5f0f<\/p>\n\n\n\n

\n

(kp)ed<\/sup>\u00a0= tq + kp<\/p>\n<\/blockquote>\n\n\n\n

\u8fd9\u65f6t\u5fc5\u7136\u80fd\u88abp\u6574\u9664\uff0c\u5373 t=t’p<\/p>\n\n\n\n

\n

(kp)ed<\/sup>\u00a0= t’pq + kp<\/p>\n<\/blockquote>\n\n\n\n

\u56e0\u4e3a m=kp\uff0cn=pq\uff0c\u6240\u4ee5<\/p>\n\n\n\n

\n

med<\/sup>\u00a0\u2261 m (mod n)<\/p>\n<\/blockquote>\n\n\n\n

\u539f\u5f0f\u5f97\u5230\u8bc1\u660e\u3002<\/p>\n\n\n\n

\uff08\u5b8c\uff09<\/p>\n\n\n\n

\u53c2\u8003\u8fde\u63a5\uff1aRSA\u7b97\u6cd5\u539f\u7406\uff08\u4e00\uff09<\/a><\/p>\n\n\n\n

\u539f\u6587\u8fde\u63a5\uff1ahttps:\/\/www.ruanyifeng.com\/blog\/2013\/07\/rsa_algorithm_part_two.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

\u4e0a\u4e00\u6b21\uff0c\u6211\u4ecb\u7ecd\u4e86\u4e00\u4e9bRSA\u7b97\u6cd5\u539f\u7406\uff08\u4e00\uff09\u3002 \u6709\u4e86\u8fd9\u4e9b\u77e5\u8bc6\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u770b\u61c2RSA\u7b97\u6cd5\u3002\u8fd9\u662f\u76ee\u524d\u5730\u7403\u4e0a\u6700\u91cd\u8981\u7684\u52a0\u5bc6 […]<\/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":[43],"tags":[242,60,314,390],"class_list":["post-2016","post","type-post","status-publish","format-standard","hentry","category-infoarticle","tag-chatgpt","tag-linux","tag-openai-api","tag-rsa"],"views":1746,"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/2016","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=2016"}],"version-history":[{"count":8,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/2016\/revisions"}],"predecessor-version":[{"id":2033,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=\/wp\/v2\/posts\/2016\/revisions\/2033"}],"wp:attachment":[{"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2016"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2016"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aqwu.net\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2016"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}