{"id":512,"date":"2020-12-24T22:42:48","date_gmt":"2020-12-24T14:42:48","guid":{"rendered":"http:\/\/eotstxtab.top\/?p=512"},"modified":"2021-06-21T19:14:39","modified_gmt":"2021-06-21T11:14:39","slug":"rsa%e9%9d%9e%e5%af%b9%e7%a7%b0%e5%8a%a0%e5%af%86%e7%ae%97%e6%b3%95demo","status":"publish","type":"post","link":"http:\/\/43.142.23.155\/?p=512","title":{"rendered":"RSA\u975e\u5bf9\u79f0\u52a0\u5bc6\u7b97\u6cd5demo"},"content":{"rendered":"\n

\u4e00\u3001\u57fa\u7840\u77e5\u8bc6\uff1a<\/p>\n\n\n\n

\u5bc6\u94a5\u751f\u6210<\/strong>\uff1a<\/p>\n\n\n\n

1<\/strong>\u3001\u968f\u673a\u9009\u62e9\u4e24\u4e2a\u4e0d\u76f8\u7b49\u7684\u8d28\u6570p\u548cq<\/strong><\/p>\n\n\n\n

\u6bd4\u5982\u6211\u4eec\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

2<\/strong>\u3001\u8ba1\u7b97p\u548cq\u7684\u4e58\u79efn<\/strong><\/p>\n\n\n\n

n = 61\u00d753 = 3233<\/p>\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

3<\/strong>\u3001\u8ba1\u7b97n\u7684\u6b27\u62c9\u51fd\u6570\u03c6(n)<\/strong><\/p>\n\n\n\n

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

\u6240\u4ee5\u03c6(3233)\u7b49\u4e8e60\u00d752\uff0c\u53733120\u3002<\/p>\n\n\n\n

4<\/strong>\u3001\u968f\u673a\u9009\u62e9\u6574\u6570e\uff0c\u6761\u4ef6\u662f1<e<\u03c6(n)\uff0c\u4e14e\u4e0e\u03c6(n)\u4e92\u8d28<\/strong><\/p>\n\n\n\n

\u6240\u4ee5\u6211\u4eec\u968f\u4fbf\u57281\u52303120\u4e4b\u95f4\u9009\u62e9\u4e8617\u3002\uff08\u5b9e\u9645\u5e38\u5e38\u9009\u62e965537\uff09<\/p>\n\n\n\n

5<\/strong>\u3001\u8ba1\u7b97e\u5bf9\u4e8e\u03c6(n)\u7684\u6a21\u53cd\u5143\u7d20d<\/strong><\/p>\n\n\n\n

\u6240\u8c13”\u6a21\u53cd\u5143\u7d20”\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

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

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

ed – 1 = k\u03c6(n) (k\u2208Z)<\/p>\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

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

\u5df2\u77e5 e=17, \u03c6(n)=3120\uff0c17x + 3120y = 1<\/p>\n\n\n\n

\u8fd9\u4e2a\u65b9\u7a0b\u53ef\u4ee5\u7528”\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5”\u6c42\u89e3\u3002\u7b97\u51fa\u4e00\u7ec4\u6574\u6570\u89e3\u4e3a<\/p>\n\n\n\n

(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

6<\/strong>\u3001\u5c06n\u548ce\u5c01\u88c5\u6210\u516c\u94a5\uff0cn\u548cd\u5c01\u88c5\u6210\u79c1\u94a5\u3002<\/strong><\/p>\n\n\n\n

n=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

7<\/strong>\u3001\u603b\u7ed3\u4e00\u4e0b<\/strong><\/p>\n\n\n\n

pq\u7684\u4f5c\u7528\u7528\u4e8e\u6c42n==pq\uff0c\u518d\u7528 (p-1)(q-1)\u6c42\u03c6(n)\uff0c\u5728\u03c6(n)\u8303\u56f4\u5185\u968f\u673a\u9009\u62e9\u5373\u4e3ae\uff0cd==e\u5bf9\u4e8e\u03c6(n)\u7684\u6a21\u53cd\u5143\u7d20<\/p>\n\n\n\n

\u4e8c\u3001python\u5b9e\u73b0<\/p>\n\n\n\n

\u751f\u6210\u5bc6\u94a5module\uff1a<\/p>\n\n\n\n

'''\u516c\u94a5\u79c1\u94a5\u751f\u6210\u6a21\u5757'''\n\n## by EotStxTaB\n## 20.11.20\n\nimport random\n\n# \u8f97\u8f6c\u76f8\u9664\u6cd5\u6c42\u6700\u5927\u516c\u56e0\u6570\ndef gcd(a, b):\n    if a > b: \n        a, b = b, a\n    while b != 0:\n        a, b = b, a%b\n    return a\n\n# \u5224\u65ad\u4e00\u4e2a\u6570\u662f\u5426\u4e3a\u7d20\u6570\ndef isPrime(n):\n    if n <= 1:\n        return False\n    for i in range(2, int(math.sqrt(n)) + 1):\n        if n % i == 0:\n            return False\n    return True\n\ndef fast_mod(b, n, m):\n    ret = 1\n    tmp = b\n    while n:\n        if n & 0x1:\n            ret = ret * tmp % m\n        tmp = tmp * tmp % m\n        n >>= 1\n    return ret\n\n# \u968f\u673a\u751f\u6210\u7d20\u6570\ndef random_prime(half_len):\n    while True:\n        n = random.randint(0, 1 << half_len)#\u6c422^half_len\u4e4b\u95f4\u7684\u5927\u6570\n        if n % 2 != 0:\n            found = True\n            # \u968f\u673a\u6027\u6d4b\u8bd5\n            for i in range(0, 5):   #\u5b89\u5168\u9608\u503c\u4e3a5\u7684\u65f6\u5019\u9519\u8bef\u7387\u5c0f\u4e8e\u5343\u5206\u4e4b\u4e00\n                if prime_test(n) == False:\n                    found = False\n                    break\n            if found == True:\n                return n\n\n# Miller-Rabin\u7d20\u6027\u68c0\u6d4b\u7b97\u6cd5\ndef prime_test(n):\n        q = n - 1\n        k = 0\n        # \u5bfb\u627ek,q \u662f\u5426\u6ee1\u8db32^k*q =n - 1\n        while q % 2 == 0:\n            k += 1\n            q = q \/\/ 2\n        a = random.randint(2, n - 2)\n        # \u5982\u679c a^q mod n= 1, n \u53ef\u80fd\u662f\u4e00\u4e2a\u7d20\u6570\n        if fast_mod(a, q, n) == 1:\n            return True\n        # \u5982\u679c\u5b58\u5728j\u6ee1\u8db3 a ^ ((2 ^ j) * q) mod n == n-1, n \u53ef\u80fd\u662f\u4e00\u4e2a\u7d20\u6570\n        for j in range(0, k):\n            if fast_mod(a, (2 ** j) * q, n) == n - 1:\n                return True\n        # n \u4e0d\u662f\u7d20\u6570\n        return False\n\ndef create_k(key_len): # key_len\u8981\u6bd4\u6d88\u606f\u957f\u5ea6\u5927\n    p = random_prime(key_len \/\/ 2)\n    q = random_prime(key_len \/\/ 2)\n    n  = p * q\n    phi_n = (p - 1)*(q - 1) # \u8ba1\u7b97n\u7684\u6b27\u62c9\u51fd\u6570\n    print(\"\u6b27\u62c9\u540e\u7684phi_N:\"+str(phi_n))\n    # \u4e8b\u5148\u8bbe\u5b9a\u597d\u516c\u94a5 E<phi\u4e14\u4e92\u7d20\n    E = 65537 \n    D = create_D(phi_n, E)\n    return (n,E,D)\n\n# \u8fed\u4ee3\u5b9e\u73b0\u6269\u5c55\u6b27\u51e0\u91cc\u5f97\u7b97\u6cd5\ndef ext_gcd(a, b):\n     if b == 0:\n        return 1, 0, a\n     else:\n        x, y, q = ext_gcd(b, a % b)\n        x, y = y, (x - (a \/\/ b) * y)\n        return x, y, q\n        \n# \u751f\u6210\u79c1\u94a5D\ndef create_D(phi_n, E):\n    (x, y, r) = ext_gcd(phi_n, E)\n    # y\u6709\u53ef\u80fd\u662f\u8d1f\u6570\n    if y < 0:\n        # return y % phi_n\n        return y + phi_n  \n    return y\n\n\n<\/code><\/pre>\n\n\n\n
\u52a0\u5bc6\u4e0e\u89e3\u5bc6\uff08\u53ef\u4ee5\u5206\u79bb\uff0c\u6211\u5c31\u662f\u968f\u4fbf\u6f14\u793a\u4e00\u4e0b\uff09<\/p>\n\n\n\n
'''\u52a0\u5bc6'''\n\n## by EotStxTaB\n## 20.11.20\n\nimport Create_Key as ck\nimport math\nimport random\n\nif __name__ == '__main__':\n    M = input(\"\u8f93\u5165\u660e\u6587M:\")\n    M_int = int(M)\n    mess_num_length = len(M)\n    (n, e, d) = ck.create_k(mess_num_length*15)\n    print (\"\u6b27\u62c9\u524d\u7684N:\"+str(n))\n    print (\"\u516c\u94a5E\u4e3a\uff1a\"+str(e))\n    print (\"\u79c1\u94a5D\u4e3a\uff1a\"+str(d))\n    cipher = ck.fast_mod(M_int,e,n) #\u751f\u6210\u5bc6\u6587C a^b%c=n\n    print (\"\u52a0\u5bc6\u540e\u7684\u5bc6\u6587cipher:\"+str(cipher))\n    print (\"-----------------------------------------------------------------\")\n    New_M = ck.fast_mod(cipher, d, n)\n    print (\"\u89e3\u5bc6\u540e\u7684\u660e\u6587:\"+str(New_M))\n    print (\"-----------------------------------------------------------------\")\n    print (\"\u8c22\u8c22\u670b\u53cb\u4eec\uff01\")\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u3001\u57fa\u7840\u77e5\u8bc6\uff1a \u5bc6\u94a5\u751f\u6210\uff1a 1\u3001\u968f\u673a\u9009\u62e9\u4e24\u4e2a\u4e0d\u76f8\u7b49\u7684\u8d28\u6570p\u548cq \u6bd4\u5982\u6211\u4eec\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 2\u3001\u8ba1\u7b97p\u548cq\u7684\u4e58\u79efn n = 61\u00d753 = 3233 n\u7684\u957f...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[11,24,21],"class_list":["post-512","post","type-post","status-publish","format-standard","hentry","category-7","tag-python","tag-rsa","tag-21"],"_links":{"self":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/512","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=512"}],"version-history":[{"count":1,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions"}],"predecessor-version":[{"id":572,"href":"http:\/\/43.142.23.155\/index.php?rest_route=\/wp\/v2\/posts\/512\/revisions\/572"}],"wp:attachment":[{"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=512"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=512"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/43.142.23.155\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=512"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}