RSA\u52a0\u5bc6\u7b97\u6cd5<\/strong>\u662f\u4e00\u79cd\u975e\u5bf9\u79f0\u52a0\u5bc6\u7b97\u6cd5<\/strong>\uff0c\u4e8e1977\u5e74\u7531\u7f57\u7eb3\u5fb7\u00b7\u674e\u7ef4\u65af\u7279\uff08Ron Rivest\uff09\u3001\u963f\u8fea\u00b7\u8428\u83ab\u5c14\uff08Adi Shamir\uff09\u3001\u4f26\u7eb3\u5fb7\u00b7\u963f\u5fb7\u66fc\uff08Leonard Adleman\uff09\u4e00\u8d77\u63d0\u51fa\u3002<\/p>\n RSA\u4f18\u52bf<\/strong> \u52a0\u5bc6\u7531 \u516c\u94a5 \u79c1\u94a5 \u660e\u6587 \u5bc6\u6587 <\/strong>\u56db\u4e2a\u90e8\u5206\u7ec4\u6210<\/p>\n \u8d28\u6570\u4e0e\u4e92\u8d28\u6570<\/strong> \u53d6\u6a21\u8fd0\u7b97<\/strong> \u540c\u4f59\u5b9a\u7406<\/strong> \uff082\uff09a\u2261b(mod m)\u7b49\u4ef7\u4e8ea\u4e0eb\u5206\u522b\u7528m\u53bb\u9664\uff0c\u4f59\u6570\u76f8\u540c<\/p>\n \u6b27\u62c9\u51fd\u6570<\/strong> \u6b27\u62c9\u5b9a\u7406\u4e0e\u6a21\u53cd\u5143\u7d20<\/strong> RSA\u5bc6\u94a5\u4e00\u822c\u4e3a1024\u4f4d<\/p>\n \u7531p,q,dp,dq,c\u6c42\u660e\u6587\u7684\u7b97\u6cd5<\/p>\n \u6a21\u8fd0\u7b97\u7684\u57fa\u672c\u89c4\u5219<\/p>\n \uff081\uff09 \uff0812\uff09\u300b\u82e5a\u2261b(%p)\uff0c\u2200C\uff0c\u6709\uff08a\u00d7c\uff09\u2261\uff08b\u00d7c\uff09\uff08%p\uff09<\/strong> RSA\u5df2\u77e5p,q,dp,dq,c<\/strong> \uff081\uff09 \u5229\u7528\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\u53ef\u5f97\uff1a $$ \u73b0\u5728\u53ea\u8981\u6c42m1\u548cm2\u4e86<\/p>\n RSA\u52a0\u5bc6\u7b97\u6cd5 RSA\u52a0\u5bc6\u7b97\u6cd5\u662f\u4e00\u79cd\u975e\u5bf9\u79f0\u52a0\u5bc6\u7b97\u6cd5\uff0c\u4e8e1977\u5e74\u7531\u7f57\u7eb3\u5fb7\u00b7\u674e\u7ef4\u65af\u7279\uff08Ron Rivest\uff09\u3001\u963f\u8fea\u00b7\u8428\u83ab\u5c14\uff08Adi Shamir\uff09\u3001\u4f26\u7eb3\u5fb7\u00b7\u963f\u5fb7\u66fc\uff08Leonard Adleman\uff09\u4e00\u8d77\u63d0\u51fa\u3002 RSA\u4f18\u52bf \u5bf9\u6781\u5927\u6574\u6570\u505a\u56e0\u5f0f\u5206\u89e3\u5230\u96be\u5ea6\u51b3\u5b9a\u4e86RSA\u7b97\u6cd5\u7684\u53ef\u9760\u6027\uff0c\u5bf9\u4e00\u6781\u5927\u6574\u6570\u505a\u56e0\u5f0f\u5206\u89e3\u8d8a\u56f0\u96be\uff0cRSA\u7b97\u6cd5\u8d8a\u53ef\u9760 \u52a0\u5bc6\u7531 \u516c\u94a5 \u79c1\u94a5 \u660e\u6587 \u5bc6\u6587 \u56db\u4e2a\u90e8\u5206\u7ec4\u6210 \u8d28\u6570\u4e0e\u4e92\u8d28\u6570 \u4e00\u4e2a\u5927\u4e8e1\u5230\u81ea\u7136\u6570\uff0c\u9664 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[114,113,36,2],"tags":[44],"class_list":["post-1163","post","type-post","status-publish","format-standard","hentry","category-crypto","category-ctf","category-cryptography","category-network_sec","tag-44"],"_links":{"self":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/posts\/1163","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=1163"}],"version-history":[{"count":0,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/posts\/1163\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/media?parent=1163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/categories?post=1163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.youvii.site\/index.php\/wp-json\/wp\/v2\/tags?post=1163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\u5bf9\u6781\u5927\u6574\u6570\u505a\u56e0\u5f0f\u5206\u89e3\u5230\u96be\u5ea6\u51b3\u5b9a\u4e86RSA\u7b97\u6cd5\u7684\u53ef\u9760\u6027\uff0c\u5bf9\u4e00\u6781\u5927\u6574\u6570\u505a\u56e0\u5f0f\u5206\u89e3\u8d8a\u56f0\u96be\uff0cRSA\u7b97\u6cd5\u8d8a\u53ef\u9760<\/p>\n
\n\u4e00\u4e2a\u5927\u4e8e1\u5230\u81ea\u7136\u6570\uff0c\u9664\u4e861\u548c\u5b83\u672c\u8eab\u5916\uff0c\u4e0d\u80fd\u88ab\u5176\u4ed6\u81ea\u7136\u6570\u6574\u9664\uff08\u96640\u4ee5\u5916\uff09\u7684\u6570\u79f0\u4e3a\u8d28\u6570\uff08\u7d20\u6570\uff09\uff1b\u5426\u5219\u79f0\u4e3a\u5408\u6570\u3002
\n\u4f8b\u5982 15=3\u00d75\uff0c\u6240\u4ee515\u4e0d\u662f\u7d20\u6570
\n13\u9664\u4e86\u7b49\u4e8e13\u00d71\u4ee5\u5916\uff0c\u4e0d\u80fd\u8868\u793a\u4e3a\u5176\u4ed6\u4efb\u4f55\u4e24\u4e2a\u6574\u6570\u7684\u4e58\u79ef\uff0c\u6240\u4ee513\u662f\u4e00\u4e2a\u7d20\u6570
\n1\u4e0d\u662f\u8d28\u6570\uff0c\u4e5f\u4e0d\u662f\u5408\u6570
\n\u516c\u7ea6\u6570\u53ea\u67091\u7684\u4e24\u4e2a\u6570\uff0c\u53eb\u505a\u4e92\u8d28\u6570<\/p>\n
\n\u53d6\u6a21\u4e5f\u5c31\u662f\u6c42\u4f59\u6570
\n\u4f8b\u5982 10mod3=1\uff0810%3=1\uff09\u300126mod6=2\u300128mod2=0
\n\u5176\u4e2d 10mod 3 =1 \u4e3a 10 – (3\u00d7n)=1\uff0c3n<10<\/p>\n
\n\u201c\u2261\u201d\u662f\u6570\u8bba\u4e2d\u8868\u793a\u540c\u4f59\u7684\u7b26\u53f7\uff0c\u540c\u4f59\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a
\n\u7ed9\u5b9a\u4e00\u4e2a\u6b63\u6574\u6570m\uff0c\u5982\u679c\u4e24\u4e2a\u6574\u6570a\u548cb\u6ee1\u8db3 a – b \u80fd\u88abm\u6574\u9664 \uff1a(a -b)mod m = 0\uff0c\u90a3\u4e48\u5c31\u79f0\u6574\u6570a\u4e0eb\u5bf9\u6a21m\u540c\u4f59\uff0c\u8bb0\u4f5ca\u2261b\uff08mod m\uff09\uff0c\u540c\u65f6\u53ef\u6210\u7acba mod m =b
\n\u540c\u4f59\u4e0e\u6a21\u8fd0\u7b97\u662f\u4e0d\u540c\u7684\uff1a
\n\uff081\uff09\u82e5a\u22610(mod m)\uff0c\u5219m|a\uff1b<\/p>\n
\n\u4efb\u610f\u7ed9\u5b9a\u6b63\u6574\u6570n\uff0c\u8ba1\u7b97\u5728\u5c0f\u4e8e\u7b49\u4e8en\u7684\u6b63\u6574\u6570\u4e4b\u4e2d\uff0c\u6709\u591a\u5c11\u4e2a\u4e0en\u6784\u6210\u4e92\u8d28\u5173\u7cfb\uff1f
\n\u8ba1\u7b97\u8fd9\u4e2a\u503c\u7684\u65b9\u6cd5\u5c31\u53eb\u6b27\u62c9\u51fd\u6570\uff0c\u4ee5\u03c6(n)<\/strong>\u8868\u793a
\n\u4f8b\u5982\u57281\u52308\u4e2d\uff0c\u4e0e8\u5f62\u6210\u4e92\u8d28\u5173\u7cfb\u7684\u662f1\u30013\u30015\u30017\u6240\u4ee5\u03c6(n)=4
\n\u5728RSA\u7b97\u6cd5\u4e2d\uff0c\u6b27\u62c9\u51fd\u6570\u5bf9\u4ee5\u4e0b\u5b9a\u7406\u6210\u7acb:
\n\uff081\uff09\u5982\u679cn\u53ef\u4ee5\u5206\u89e3\u4e3a\u4e24\u4e2a\u4e92\u8d28\u7684\u6574\u6570\u4e4b\u79ef\uff0c\u5373n=p\u00d7q\uff0c\u5219\u6709\uff1a\u03c6(n)=\u03c6(pq)=\u03c6(p)\u03c6(q)\uff1b
\n\uff082\uff09\u5f53p\u4e3a\u8d28\u6570\uff0c\u03c6(p)=p-1\uff0c\u6240\u4ee5\u6709\u03c6(n)=(p-1)(q-1)<\/p>\n
\n\u6b27\u62c9\u51fd\u6570\u7684\u7528\u5904\u5728\u4e8e\u6b27\u62c9\u5b9a\u7406<\/strong>\uff1a\u5982\u679c\u4e24\u4e2a\u6b63\u6574\u6570a\u548cn\u4e92\u8d28\uff0c\u5219n\u7684\u6b27\u62c9\u51fd\u6570\u03c6(n)\u53ef\u4ee5\u8ba9\u4e0b\u9762\u7684\u7b49\u5f0f\u6210\u7acb\uff1b
\n$$
\na^{\u03c6(n)}\u22611(mod n)
\n$$
\n\u4e5f\u5c31\u662f\u8bf4\uff0ca\u7684\u03c6(n)\u6b21\u65b9\u88abn\u9664\u7684\u4f59\u6570\u4e3a1
\n\u6a21\u53cd\u5143\u7d20\u7684\u63a8\u5bfc\u8fc7\u7a0b\u5982\u4e0b\uff1a
\n\u6839\u636e\u6b27\u62c9\u5b9a\u7406\uff0c\u6709\uff1a
\n$$
\na^{\u03c6(n)}=a\u00d7a^{(\u03c6(n-)-1)}=1(mod n)
\n$$
\n\u4ee4b=a^(\u03c6(n)-1)=1(mod n)\u5f97
\nab=1(modn)
\nb\u5c31\u662fa\u7684\u6a21\u53cd\u5143\u7d20\uff0c\u6240\u4ee5\u5982\u679c\u4e24\u4e2a\u6b63\u6574\u6570a\u548cn\u4e92\u8d28\uff0c\u90a3\u4e48\u4e00\u5b9a\u53ef\u4ee5\u627e\u5230\u6574\u6570b\u4f7f\u5f97ab-1\u88abn\u6574\u9664\uff0c\u6216\u8005\u8bf4ab\u88abn\u9664\u7684\u4f59\u6570\u662f1\uff0c\u6240\u4ee5\u6c42\u79c1\u94a5d\u7684\u516c\u5f0f\uff1a
\n$$
\nde\u22611mod[(p-1)(q-1)]
\n$$
\n\u5176\u4e2d{\u03c6(n)=(p-1)(q-1),\u03c6(n)\u4e0ee\u4e92\u8d28\uff0ck\u4e3a\u6b63\u6574\u6570}
\n\u53ef\u5316\u4e3a\uff1a
\n$$
\nd=(k<\/em>\u03c6(n)+1)\/e
\n$$<\/p>\n\u63a8\u5bfc\u516c\u5f0f\uff1ad*e=1mod \u03c6(n)\n\u53ef\u5f97\uff1a(d*e-1)\/\u03c6(n)=k;\n\u5373\uff1ad =(k*\u03c6(n)+1)\/e<\/code><\/pre>\nimport gmpy2\nI =gmpy2.invert(q,p)\nmp = pow(c,dp,p)\nmq = pow(c,dq,q) #\u6c42\u51a5\u53d6\u6a21\u8fd0\u7b97\n\nm = (((mp-mq)*I)%p)*q+mq #\u6c42\u660e\u6587\u516c\u5f0f\n\nprint(hex(m)) #\u8f6c\u4e3a\u5341\u516d\u8fdb\u5236<\/code><\/pre>\n
\n$$
\n( a + b ) mod p = ( a mod p + b mod p ) mod p
\n$$
\n\uff082\uff09
\n$$
\n( a – b ) mod p = (a mod p – b mod p ) mod p
\n$$
\n\uff083\uff09
\n$$
\n(a b ) mod p = (a mod p <\/em> b mod p ) modp
\n$$
\n\uff084\uff09
\n$$
\na ^b mod p = ( (a mod p ) ^ b ) mod p
\n$$
\n\u7ed3\u5408\u5f8b<\/strong>
\n\uff085\uff09
\n$$
\n((a+b)modp +c ) mod p = (a + (b + c)mod p) mod p
\n$$
\n\uff086\uff09
\n$$
\n((ab)mod p <\/em>c) mod p = (a(b<\/em>c)modp)modp
\n$$
\n\u4ea4\u6362\u5f8b<\/strong>
\n\uff087\uff09
\n$$
\n(a+b)modp=(b+a)modp
\n$$
\n\uff088\uff09
\n$$
\n(ab)modp=(b<\/em>a)modp
\n$$
\n\u5206\u914d\u5f8b<\/strong>
\n\uff089\uff09
\n$$
\n(a+b)modp=(amodp+bmodp)mod p
\n$$
\n\uff0810\uff09
\n$$
\n((a+b)modpc)modp=((a<\/em>c)modp+(b*c)modp)modp
\n$$
\n\uff0811\uff09\u300b\u82e5a\u2261b(%p)\uff0c\u5bf9\u4efb\u610f\u7684C\uff0c\u90fd\u6709\uff08a+c\uff09\u2261\uff08b+c\uff09\uff08%p\uff09<\/strong><\/p>\n
\n\uff0813\uff09\u300b\u82e5a\u2261b(%p)\uff0c\u2200C\uff0c\u6709c\u2261d\uff08%p\uff09\uff0c\u5219(a+c)\u2261(b+d)(%p),(a-c)\u2261(b-d)(%p),<\/strong>
\n(a\u00d7c)\u2261(b\u00d7d)(%p)<\/strong><\/p>\n
\n\u516c\u5f0f\uff1a<\/p>\n
\n$$
\nm_1=C^{dp}modp
\n$$
\n\uff082\uff09
\n$$
\nm_2=C^{dq}mod q
\n$$
\n\uff083\uff09\u6c42\u660e\u6587
\n$$
\nm=(((m_1-m_2)I)modp)<\/em>q+m
\n$$
\nI\u4e3a\u4e58\u6cd5\u9006\u5143<\/p>\n\u5df2\u77e5\u6761\u4ef6\uff1a\nc \u2261 m^e mod n #\u52a0\u5bc6\nm \u2261 c^d mod n #\u89e3\u5bc6\n\u03c6(n) = (p-1)(q-1) #\u6b27\u62c9\u5b9a\u7406\nd\u00b7e \u2261 1 mod \u03c6(n) #\u6b27\u62c9\u5b9a\u7406\u4e0e\u6a21\u53cd\u5143\u7d20\ndp \u2261 d mod (p-1)\ndq \u2261 d mod (q-1)<\/code><\/pre>\n
\n$$
\nm_1 \u2261 c^d mod p
\n$$<\/p>\n
\nm_2 \u2261 c^d mod q
\n$$<\/p>\n\u8bc1\u660e\u8fc7\u7a0b\n\u7531 \nm \u2261 c^d mod n\n\u53ef\u5f97\nm = c^d + k*n\n\u2235 n = p*q\n\u2234 m = c^d + k*p*q\n\u4e0a\u8ff0\u5f0f\u5b50\u540c\u65f6\u53d6\u4f59q\u548cp\u5206\u522b\u5f97\u5230\nm_1=c^d mod p #m_1 \u4e2d _1\u8868\u793a\u4e0b\u6807 \u5373\u533a\u5206m1\u548cm2\nm_2=c^d mod q\n> c^d = kp+m\n\u4ee3\u5165m_2 = c^d mod q\u5f97\nm_2 \u2261(kp+m_1)mod q\n\u7b49\u5f0f\u4e24\u8fb9\u540c\u65f6\u51cf\u53bbm \u5f97\u5230\n(m_2 - m_1)\u2261 kp mod q\n\u53c8\u56e0\u4e3agcd(p,q)=1 \u6c42p\u90fd\u9006\u5143\n(m_2 - m_1)*p^{-1}\u2261 k mod q #{-1}\u8868\u793a\u6307\u6570\n>k \u2261(m_2 - m_1)*p{-1} mod q\n\u2234k \u2261 (m_2 - m_1)*p{-1}mod q && c^d = kp +m_1\n>c^d = ((m_2 - m_1)*p^{-1}mod q)*p + m_1\n\u4ee3\u5165m\u2261c^d mod n\n\u2234m\u2261(((m_2 - m_1)*p^{-1}mod q)*p + m_1)mod n<\/code><\/pre>\n\u56e0\nd \u2261 dp mod (p-1)\nd \u2261 dq mod (q-1)\n\u5206\u522b\u4ee3\u5165m_1,m_2\nm_1 \u2261 c^{dp mod(p-1)} mod p > m_1 \u2261 c^{dp} mod p #1\nm_2 \u2261 c^{dq mod(q-1)} mod q > m_2 \u2261 c^{dq} mod q #2\n\u8d39\u9a6c\u63a8\u5bfcgcd(a,b)#\u6c42\u6700\u5927\u516c\u7ea6\u6570\uff0c\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\n\u5047\u5982p\u662f\u8d28\u6570\uff0c\u4e14gcd(k,p)=1,\u5219k^(p-1)\u22611 mod p\n\u5982\u679c\u6709\u7b49\u5f0fd = dp +k*(p-1)\n\u4ee3\u5165m_1 \u2261 c^d mod p\n\u5f97 m_1 \u2261 c^{dp+k*(p-q)} mod p > m_1 \u2261 c^{dp}\u00b7c^{k*(p-1)} mod p\n\u7531\u8d39\u9a6c\u5c0f\u5b9a\u7406\nc^{k*(p-1)} mod p = (c^{p-1}mod p)^k = 1^k = 1\nm_1 \u2261 c^{dp} mod p\n\u540c\u7406 m_2 \u2261 c^{dq} mod q<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"