{"id":389,"date":"2013-05-16T19:07:00","date_gmt":"2013-05-16T11:07:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=389"},"modified":"2025-11-04T01:40:40","modified_gmt":"2025-11-03T17:40:40","slug":"%e9%9d%9e%e5%b0%8d%e7%a8%b1%e5%bc%8f%e5%8a%a0%e5%af%86rsa","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/389","title":{"rendered":"\u975e\u5c0d\u7a31\u5f0f\u52a0\u5bc6RSA"},"content":{"rendered":"\n

RSA(rivest-shamir-adleman)<\/strong>
\u5340\u6bb5\u52a0\u5bc6\u6cd5,\u7528\u6307\u6578\u904b\u7b97
\u4f7f\u7528fractorization(\u56e0\u6578\u5206\u89e3)\u539f\u7406
publickey\u53ef\u4ee5\u662f\u4efb\u4f55\u9577\u5ea6,\u5178\u578b\u7528\u6cd5\u662f512bit,\u6700\u9ad8\u652f\u63f44096bit
\u53ef\u81ea\u5df1\u6c7a\u5b9a\u52a0\u5bc6\u8a0a\u606f\u5340\u584a\u9577\u5ea6,\u4f46\u6700\u597d\u4e0d\u8981\u8d85\u904ekey\u7684\u9577\u5ea6
\u9808\u5148\u7522\u751fkey pair,\u4e5f\u5c31\u662fpublickey\u53caprivatekey
\u653b\u64ca\u65b9\u6cd5\uff1a\u66b4\u529b\u6cd5,\u6578\u5b78\u653b\u64ca\u6cd5,\u8a08\u6642\u653b\u64ca\u6cd5<\/p>\n\n\n\n

\u7522\u751fkey\u6b65\u9a5f<\/strong>
1\u627e2\u500b\u5927\u8cea\u6578p\u53caq
ps:\u5c0f\u65bc100\u7684\u8cea\u6578\u67092,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
2\u8a08\u7b97N=p*q\u53caM=euler(N)
3\u7522\u751fpublic key(e,N),e\u9700\u6eff\u8db3gcd(e,M)=1
4\u7522\u751fprivate key(d,N),d\u9700\u6eff\u8db3(e*d)mod M=1
ex:
1
\u8a2dp=3,q=5 ,pq\u4e92\u70ba\u8cea\u6578
2
N=pq=3*5=15
M=euler(15)=(p-1)(q-1)=(3-1)(5-1)=8
3
gcd(e,8)=1
e\u53ef\u4ee5\u70ba1,3,5,7\u4efb\u4e00\u6578,\u5047\u8a2de=3
(3,15)\u70bapublic key
4
(3*d)mod 8=1
d\u53ef\u4ee5\u70ba3,11,…,\u4f463\u548ce\u76f8\u540c,\u6240\u4ee5\u907811\u7576d
(11,15)\u70baprivate key
ex:
N=35=p*q=7*5
M=24=eular(35)=(7-1)(5-1)
gcd(e,24)=1,e=1,5,7,11,13,17,19,23,we select e=5 ,so public key=(5,35)
(5*d)%24=1,select d=29 ,so private key=(29,35)<\/p>\n\n\n\n

\u52a0\u89e3\u5bc6\u6b65\u9a5f<\/strong>
\u8a2dpublic key=(e,N),private key=(d,N),\u660e\u6587\u70baP,\u5bc6\u6587\u70baC
\u52a0\u5bc6\u65b9\u5f0f:\u7528\u516c\u9470\u52a0\u5bc6
C=encrypt(P,(e,N))=(P^e)mod N
\u89e3\u5bc6\u65b9\u5f0f:\u7528\u79c1\u9470\u89e3\u5bc6
P=decrypt(C,(d,N))=(C^d)mod N
ex:
\u8a2dpublic key=(3,15),private key=(11,15),P=7
\u52a0\u5bc6\u65b9\u5f0f:(7^3)mod15=343mod15=13
\u7522\u751f”\u5bc6\u658713″
\u89e3\u5bc6\u65b9\u5f0f:(13^11)mod15=(169*169*…*13)mod15=(4*4*4*4*4*13)mod15=(4*13)mod15=7
\u7522\u751f”\u660e\u65877″
ex:
\u8a2dpublic key=(5,35),private key=(29,35),P=10
encryption
C=(10,(5,35))=(10^5)mod35=5
decryption
P=(5,(29,35))=(5^29)mod35=(125*125*..5*5)mod35=(20*20*…5*5)mod35=(20*5*5)mod35=10<\/p>\n\n\n\n

\u6578\u4f4d\u7c3d\u7ae0\u6b65\u9a5f<\/strong>
\u8a2dpublic key=(e,N),private key=(d,N),\u8a2d\u606f\u70baM,\u7c3d\u7ae0\u70baS
\u7c3d\u7ae0\u7522\u751f\u65b9\u5f0f:\u7528\u79c1\u9470\u7522\u751f\u7c3d\u7ae0
1 S=signature(M,(d,N))=(M^d)mod N
2 \u5c07S\u548cM\u653e\u5728\u4e00\u8d77
\u7c3d\u7ae0\u9a57\u8b49\u65b9\u5f0f:\u7528\u516c\u9470\u9a57\u8b49\u7c3d\u7ae0
1 M=verify(S,(e,N))=(S^e)mod N
2 \u82e5\u539f\u4f86\u7684M\u548c\u9a57\u8b49\u51fa\u4f86\u7684M\u76f8\u540c,\u8868\u793a\u78ba\u5b9a\u8a0a\u606fM\u70ba\u79c1\u9470\u64c1\u6709\u8005\u6240\u7c3d\u7f72<\/p>\n\n\n\n

ps:
\u5c24\u62c9\u51fd\u6578<\/strong>
euler(n)
\u5c0f\u65bcn\u7684\u6574\u6578\u4e2d\u8207n\u4e92\u8cea\u7684\u6574\u6578\u500b\u6578
ex:
1
euler(15)=(3-1)(5-1)=8
\u8b49\u660e:\u8a08\u7b97\u5c0f\u65bc15\u7684\u6574\u6578\u820715\u4e92\u8cea\u7684\u6574\u6578,\u7b97\u6cd5\u5982\u4e0b
gcd(15,1)=1
gcd(15,2)=1
gcd(15,4)=1
gcd(15,7)=1
gcd(15,8)=1
gcd(15,11)=1
gcd(15,13)=1
gcd(15,14)=1
\u56e0\u6b64\u5c0f\u65bc15\u7684\u6574\u6578\u4e2d\u820715\u4e92\u8cea\u7684\u6574\u6578\u70ba1,2,4,7,8,11,13,14,\u51718\u500b
2
euler(6)=(3-1)(2-1)=2
\u5c0f\u65bc6\u7684\u6574\u6578\u4e2d\u82076\u4e92\u8cea\u7684\u6574\u6578\u70ba1,5<\/p>\n\n\n\n

ps:
\u5efa\u8b70RSA\u7684\u91d1\u9470\u9577\u5ea6\u81f3\u5c11\u89811024bit\u4ee5\u4e0a
A. Lenstra(1994)\u53ef\u6210\u529f\u5730\u89e3\u51faRSA 129bit<\/p>\n\n\n\n

ps:
\u5e38\u898bRSA\u653b\u64ca:
chosen-ciphertext
common modulus attack<\/p>\n","protected":false},"excerpt":{"rendered":"

RSA(rivest-shamir-adleman)\u5340\u6bb5\u52a0\u5bc6 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[375],"tags":[],"class_list":["post-389","post","type-post","status-publish","format-standard","hentry","category-cryptographic-fundamentals"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/389","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=389"}],"version-history":[{"count":1,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/389\/revisions"}],"predecessor-version":[{"id":2852,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/389\/revisions\/2852"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=389"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=389"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}