Algorithm - Python - 現代の暗号 - 最終問題 - オイラー関数の性質、オイラーの定理、暗号化、復号化、公開鍵、秘密鍵、素数の積、合同式

中学数学からはじめる暗号入門
~現代の暗号はどのようにして作られたのか~
楽天ブックス Yahoo!

学習環境

• Surface、Surface ペン(端末)
• Windows 10 Pro (OS)
• Nebo(Windows アプリ)
• iPad Pro 10.5 + Apple Pencil
• MyScript Nebo - MyScript(iPad アプリ(iOS))
• 参考書籍
  • Pythonからはじめる数学入門 (楽天ブックス Yahoo!)
  • JavaScriptリファレンス 第6版 (楽天ブックス Yahoo!)
  • インタラクティブ・データビジュアライゼーション (楽天ブックス Yahoo!)

中学数学からはじめる暗号入門 ~現代の暗号はどのようにして作られたのか~ (知りたい!サイエンス 141) (関根 章道(著)、技術評論社)の後編(現代の暗号)、第8章(最終問題)の最後の暗号を解いてみよう - Part 7 (RSA暗号)の解答を求めてみる。

7. 
   

   数字化。

   $3218$

   暗号化。

   $\begin{array}{l}\left(mod2279\right)\\ 3218^2\equiv 2027\\ 3218^4\equiv 1971\\ 3218^8\equiv 1425\\ 3218^{16}\equiv 36\\ 3218^{32}\equiv 1296\\ 3218^{64}\equiv 2272\\ 3218^{128}\equiv 49\\ 3218^{256}\equiv 122\\ 3218^{512}\equiv 1210\\ 3218^{1024}\equiv 982\\ 3218^{1241}\\ \equiv 3218^{1024+128+64+16+8+1}\\ \equiv 982·49·2272·36·1425·3218\\ \equiv 48118·81792·1425·939\\ \equiv 259·2027·1338075\\ \equiv 524993·302\\ \equiv 823·302\\ \equiv 248545\\ \equiv 135\end{array}$

   よって、 暗号は 135。

   秘密鍵は

   $\left(1241,2279\right)$

   復号化。

   $\begin{array}{l}\left(mod2279\right)\\ 135^{557}\equiv X\\ 3218^{2184}\equiv 1\\ 135^{557}\\ \equiv {\left(3218^{1241}\right)}^{557}\\ \equiv 3218^{691237}\\ \equiv 3218^{2184·316+1093}\\ \equiv {\left(3218^{2184}\right)}^{316}·3218^{1093}\\ \equiv 3218^{1093}\\ \equiv 3218^{1024+64+4+1}\\ \equiv 982·2272·1971·3218\\ \equiv 2231104·1971·939\\ \equiv 2242·1850769\\ \equiv 2242·221\\ \equiv 495482\\ \equiv 939\\ \equiv 3218\end{array}$

コード

Python 3

#!/usr/bin/env python3
from unittest import TestCase, main
from sympy import gcd


class MyTest(TestCase):
    def setUp(self):
        pass

    def tearDown(self):
        pass

    def test(self):
        num = 3218
        e, n = 1241, 2279
        d = 557
        encoded = num ** e % n
        decoded = encoded ** d % n + n
        self.assertEqual(encoded, 135)
        self.assertEqual(decoded, num)


if __name__ == '__main__':
    main()

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal、Jupyter(IPython))

$ ./sample2.py
.
----------------------------------------------------------------------
Ran 1 test in 0.000s

OK
$