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

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

学習環境

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

数字化。
$3218$
暗号化。
$\begin{array}{l} (m o d 2279) \\ 321 8^{2} \equiv 2027 \\ 321 8^{4} \equiv 1971 \\ 321 8^{8} \equiv 1425 \\ 321 8^{16} \equiv 36 \\ 321 8^{32} \equiv 1296 \\ 321 8^{64} \equiv 2272 \\ 321 8^{128} \equiv 49 \\ 321 8^{256} \equiv 122 \\ 321 8^{512} \equiv 1210 \\ 321 8^{1024} \equiv 982 \\ 321 8^{1241} \\ \equiv 321 8^{1024 + 128 + 64 + 16 + 8 + 1} \\ \equiv 982 \cdot 49 \cdot 2272 \cdot 36 \cdot 1425 \cdot 3218 \\ \equiv 48118 \cdot 81792 \cdot 1425 \cdot 939 \\ \equiv 259 \cdot 2027 \cdot 1338075 \\ \equiv 524993 \cdot 302 \\ \equiv 823 \cdot 302 \\ \equiv 248545 \\ \equiv 135 \end{array}$
よって、暗号は 135。
秘密鍵は
$(1241, 2279)$
復号化。
$\begin{array}{l} (m o d 2279) \\ 13 5^{557} \equiv X \\ 321 8^{2184} \equiv 1 \\ 13 5^{557} \\ \equiv {(321 8^{1241})}^{557} \\ \equiv 321 8^{691237} \\ \equiv 321 8^{2184 \cdot 316 + 1093} \\ \equiv {(321 8^{2184})}^{316} \cdot 321 8^{1093} \\ \equiv 321 8^{1093} \\ \equiv 321 8^{1024 + 64 + 4 + 1} \\ \equiv 982 \cdot 2272 \cdot 1971 \cdot 3218 \\ \equiv 2231104 \cdot 1971 \cdot 939 \\ \equiv 2242 \cdot 1850769 \\ \equiv 2242 \cdot 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
$

Kamimura's blog

ほしい物リスト

2019年9月9日月曜日

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

0 コメント:

コメントを投稿