Skip to content

Decrypting RSA encryption

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

Decrypting RSA encryption

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
DecryptingRSAencryption.js
DecryptingRSAencryption.js
 
 
DecryptingRSAencryption.py
DecryptingRSAencryption.py
 
 
README.md
README.md
 
 

README.md

🔐 問題概要

RSA暗号では、以下のようにして送信者が暗号化したデータ（数値）を、受信者が復号（解読）します：

📘 入力：

p, q, e, E

例：

p = 23917
q = 23929
e = 8731
E = 109861231

🧩 処理ステップと図解

① n と φ(n) の計算

数式：

n = p × q
φ(n) = (p - 1) × (q - 1)

例：

n = 23917 × 23929 = 572068093
φ(n) = (23917 - 1) × (23929 - 1) = 23916 × 23928 = 572020248

図解：

+-------------------+
|  RSA モジュロ空間 |
+-------------------+
   p = 23917
   q = 23929
 ┌────────────────────┐
 │    n = p × q       │ → 572068093
 └────────────────────┘
 ┌────────────────────┐
 │ φ(n) = (p-1)(q-1)   │ → 572020248
 └────────────────────┘

② 拡張ユークリッドで d = e⁻¹ mod φ(n) を求める

数式：

d ≡ e⁻¹ mod φ(n)

e の逆元を求めるために、拡張ユークリッドの互除法（Extended Euclidean Algorithm）を使います。

図解：

+---------------------------------------+
| 拡張ユークリッド互除法               |
+---------------------------------------+
| e = 8731, φ(n) = 572020248           |
| 目的：8731 × d ≡ 1 mod 572020248     |
| 結果：d = 428126443                  |
+---------------------------------------+

※ d を求めるには以下のように「a×x + b×y = gcd(a,b)」の形にし、x を mod m で正に直します。

③ 復号処理：M ≡ E^d mod n を求める

ここがRSAの心臓部です！

数式：

M ≡ E^d mod n

これを高速に行うために「繰り返し二乗法（Binary Exponentiation）」を使います。

図解：

       E = 109861231
             |
             v
+--------------------------+
| 繰り返し二乗法で         |
| M = E^d mod n を計算     |
| d = 428126443            |
| n = 572068093            |
+--------------------------+

結果：
M = 75  ← ASCIIコード

④ ASCII変換

M = 75 → 'K'

図解：

+------------------+
| ASCII 変換       |
+------------------+
| M = 75 → 'K'     |
+------------------+

🧪 全体の流れまとめ（チャート）

graph TD;
  A[入力: p, q, e, E] --> B[n = p × q]
  B --> C[φ(n) = (p-1)(q-1)]
  C --> D[d = e⁻¹ mod φ(n)]
  D --> E[M = E^d mod n]
  E --> F[文字 = ASCII(M)]
Loading

✅ 結果

出力：K

🔚 まとめ

ステップ 内容 実行時間・効率
n, φ(n) 乗算のみ O(1)
d計算 拡張ユークリッド O(log φ(n))
復号 繰り返し二乗法 O(log d)
ASCII変換 Number → String O(1)