Algorithm - Python - 現代の暗号 - RSA暗号を解読してみよう(復号化) - フェルマーの小定理、互いに素、剰余

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

学習環境

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

1. $\begin{array}{l} (7, 11) = 1 \\ 7^{11 - 1} \equiv 1 (m o d 7) \\ 7^{10} \equiv 1 (m o d 7) \\ 7^{100} \\ \equiv {(7^{10})}^{10} \\ \equiv 1^{10} \\ \equiv 1 \\ (m o d 7) \end{array}$
  よって求める余りは1。
2. $\begin{array}{l} (5, 23) = 1 \\ 5^{23 - 1} \equiv 1 (m o d 23) \\ 5^{22} \equiv 1 (m o d 23) \\ 5^{100} \\ \equiv {(5^{22})}^{4} \cdot 5^{12} \\ \equiv 5^{12} \\ \equiv {(5^{2})}^{6} \\ (m o d 23) \\ 5^{2} \\ \equiv 25 \\ \equiv 2 \\ (m o d 23) \\ {(5^{2})}^{6} \\ \equiv 2^{6} \\ \equiv 64 \\ \equiv 64 - 23 \cdot 2 \\ \equiv 18 \\ (m o d 23) \end{array}$
  よっと求める余りは18。

#!/usr/bin/env python3 from unittest import TestCase, main class MyTest(TestCase): def setUp(self): pass def tearDown(self): pass def test(self): spam = [7 ** 10 % 11, 5 ** 100 % 23] egg = [1, 18] for s, t in zip(spam, egg): self.assertEqual(s, t) if __name__ == '__main__': main()

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

Kamimura's blog

2019年9月3日火曜日

Algorithm - Python - 現代の暗号 - RSA暗号を解読してみよう(復号化) - フェルマーの小定理、互いに素、剰余

0 コメント:

コメントを投稿