{"id":783,"date":"2021-10-26T00:47:21","date_gmt":"2021-10-25T16:47:21","guid":{"rendered":"http:\/\/eotstxtab.top\/?p=783"},"modified":"2021-10-26T00:52:56","modified_gmt":"2021-10-25T16:52:56","slug":"rsa%e5%92%8crabin%e7%9a%84%e5%9f%ba%e6%9c%ac%e5%8e%9f%e7%90%86","status":"publish","type":"post","link":"http:\/\/43.142.23.155\/?p=783","title":{"rendered":"RSA\u548cRabin\u7684\u57fa\u672c\u539f\u7406"},"content":{"rendered":"\n<p class=\"has-large-font-size wp-block-paragraph\">\u4e00\u3001RSA<\/p>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">1\u3001\u5bc6\u94a5\u751f\u6210<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u751f\u6210\u4e24\u4e2a\u4fdd\u5bc6\u7684\u5927\u7d20\u6570p, q<\/li><li>n = pq; <\/li><li>n\u7684\u6b27\u62c9\u51fd\u6570\u03c6(n) = ( p &#8211; 1 )( q &#8211; 1 );<\/li><li>\u53d6\u4e00\u4e2a\u6570\u4f5c\u4e3a\u516c\u94a5e\uff0c\u76f4\u63a5\u53d6(1, \u03c6(n) )\u4e4b\u95f4\u7684\u4e00\u4e2a\u6574\u6570\uff0c\u800c\u4e14gcd( e , \u03c6(n) )=1\uff1b<\/li><li>\u6211\u4eec\u7531\u516c\u94a5e\u548c\u6b27\u62c9\u51fd\u6570\u503c\u6c42\u51fa\u79c1\u94a5d:   d * e = 1 (mod \u03c6(n) )<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">ed\u4e4b\u95f4\u7684\u5173\u7cfb\uff1a\u4e8c\u8005\u4e3a\u6b27\u62c9\u51fd\u6570\u4e0b\u7684\u4e58\u6cd5\u9006\u5143\uff0ce\u548c\u6b27\u62c9\u51fd\u6570\u4e4b\u6240\u4ee5\u4e92\u7d20\u662f\u4e3a\u4e86\u4fdd\u8bc1\u9006\u5143\u5b58\u5728\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e58\u6cd5\u9006\u5143\u7684\u6027\u8d28\u5728\u4e8e\uff1a<\/p>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">2\u3001\u52a0\u89e3\u5bc6\u7b97\u6cd5<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6ce8\u610f\u4e00\u4e0b\u660e\u6587\u9884\u5904\u7406\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5c06\u94ed\u6587\u6bd4\u7279\u4e32\u5206\u7ec4\uff0c\u6bcf\u4e00\u7ec4\u5341\u8fdb\u5236\u6570\u5c0f\u4e8en\uff0c\u6240\u4ee5length\uff08\u5206\u7ec4\uff09&lt;= log2(n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u52a0\u5bc6\uff1a\u8bb0\u5206\u7ec4\u4e3am\uff0c\u5219\u5bc6\u6587c = m^d (mod n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u89e3\u5bc6\uff1am&#8217; = c^e (mod n)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n\n\n\n<p class=\"has-large-font-size wp-block-paragraph\">\u4e8c\u3001Rabin\u5bc6\u7801\u673a\u5236<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">rabin\u5b8f\u89c2\u4e0a\u548cRSA\u7684\u533a\u522b\u5728\u4e8e\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">1\uff09RSA\u7684\u653b\u51fb\u7834\u89e3\u5728\u4e8e\u96be\u5ea6\u7b49\u540c\u6216\u4e0d\u8d85\u8fc7\u5927\u6574\u6570\u5206\u89e3\u56f0\u96be\u95ee\u9898\uff0c\u4f46\u662fRabin\u662f\u548c\u5927\u6574\u6570\u7834\u89e3\u76f4\u63a5\u7b49\u4ef7\u7684\uff0c\u6240\u4ee5\u4e00\u5b9a\u662f\u4e00\u6837\u56f0\u96be\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2\uff09\u540c\u65f6Rabin\u4e5f\u4e0d\u662f\u5355\u9879\u9677\u95e8\uff0c\u6240\u4ee5\u540c\u4e00\u5bc6\u6587\u53ef\u80fd\u6709\u597d\u51e0\u4e2a\u660e\u6587\u5bf9\u5e94\u3002<\/p>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">1\u3001\u5bc6\u7801\u751f\u6210<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>e = 2\uff08\u5176\u5b9e\u5c31\u662f\u7b97\u6cd5\u7684\u4e00\u90e8\u5206\uff0c\u4e5f\u53ef\u4ee5\u4e0d\u770b\u6210\u5bc6\u94a5\uff09<\/li><li>\u4e5f\u53d6\u4e24\u4e2a\u5927\u7d20\u6570p, q\uff0c\u4f46\u662f\u8981\u6ee1\u8db3p=q=3 (mod 4)\u3002<\/li><li>n = pq\uff0c\u5e76\u76f4\u63a5\u516c\u5f00\uff08p\uff0cq\u4fdd\u5bc6\uff09<\/li><li>\u6240\u4ee5n\u662f\u516c\u94a5\uff0cp,q\u4e3a\u79c1\u94a5<\/li><\/ul>\n\n\n\n<p class=\"has-medium-font-size wp-block-paragraph\">2\u3001\u52a0\u89e3\u5bc6<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u52a0\u5bc6\uff1ac = m^2 ( mod n )<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u89e3\u5bc6\uff1a\u6c42\u56db\u4e2a\u65b9\u7a0b\u7ec4\uff0c\u5f97\u5230\u56db\u4e2a\u4e0d\u540c\u7684\u89e3\uff0cm\u4e2d\u4f9d\u9760\u7279\u5b9a\u4fe1\u606f\u4f7f\u63a5\u6536\u65b9\u6709\u6548\u7684\u786e\u5b9a\u660e\u6587\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4e00\u3001RSA 1\u3001\u5bc6\u94a5\u751f\u6210 \u751f\u6210\u4e24\u4e2a\u4fdd\u5bc6\u7684\u5927\u7d20\u6570p, q n = pq; n\u7684\u6b27\u62c9\u51fd\u6570\u03c6(n) = ( p &#8211; 1 )( q &#8211; 1 ); \u53d6\u4e00\u4e2a\u6570\u4f5c\u4e3a\u516c\u94a5e\uff0c\u76f4\u63a5\u53d6(1, \u03c6(&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,39],"tags":[24,41,21],"class_list":["post-783","post","type-post","status-publish","format-standard","hentry","category-7","category-39","tag-rsa","tag-41","tag-21"],"_links":{"self":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/783","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=783"}],"version-history":[{"count":4,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/783\/revisions"}],"predecessor-version":[{"id":787,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/783\/revisions\/787"}],"wp:attachment":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=783"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}