Algorithm - Python - 現代の暗号 - RSA暗号を作ってみよう(暗号化) - 合同式 - 復号化(解読)、1次合同方程式の解

中学数学からはじめる暗号入門
~現代の暗号はどのようにして作られたのか~
楽天ブックス 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) (関根 章道(著)、技術評論社)の後編(現代の暗号)、第6章(RSA暗号を作ってみよう(暗号化) - 合同式)のやってみよう④の解答を求めてみる。

4. 
   
   1. 
      
      $\begin{array}{l}-1\\ 13-1=12\\ 26-1=25\\ 39-1=38\\ 52-1=51\\ 65-1=64\\ 78-1=77\\ x\equiv 6\left(mod11\right)\\ 13x\equiv 78\equiv 1\left(mod11\right)\end{array}$

      ここから

      $\begin{array}{l}-1\\ 64-1=63\\ 128-1=127\\ 192-1=191\\ 256-1=255\\ x\equiv 4\left(mod17\right)\\ 64x\equiv 256\equiv 1\left(mod17\right)\end{array}$

コード

Python 3

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


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

    def tearDown(self):
        pass

    def test(self):
        n = symbols('n', integer=True)
        ts = [(13, 11), (64, 1)]
        nums = [6, 4]
        for (a, m), num in zip(ts, nums):
            x = num + m * n
            self.assertEqual((a * x - 1) % m, 0)


if __name__ == '__main__':
    main()

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

$ ./sample4.py
.
----------------------------------------------------------------------
Ran 1 test in 0.011s

OK
$