モジュール詳細：RSA暗号

ヒル暗号2.0。

ある6文字の英単語が、ディスプレーの中央にある6つの数字に暗号化されている。この単語を送信すると、モジュールは解除される。

6つの数字の真上には、NとEのラベルが付けられた別の2つの数字がある。真下には、キーボードからの入力内容を最大6文字受け付ける点滅カーソルがある。緑の丸いボタンは入力内容を送信し、赤の丸いボタンは入力内容を削除する。

以下の手順に従い、復号された単語を取得する。

ステップ1：λ(N)の取得

最初にやることは、Nに掛け合わせられている2つの素数を取得することである。以下は、このモジュールで使用される素数の一覧である。

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

2つの素数を見つけたら、以下の式を用いてλ(N)を求める。

λ(N) = ((P1 - 1) * (P2 - 1)) / GCD(P1 - 1, P2 - 1)

GCDは「最大公約数」のことであり、以下の手順を使用して求めることができる。

1. 2つの数字のうち大きい方を取得し、小さい方の数字で割った余りを求める。
2. その後、割った数(除算の右側にある数)を先程の結果で割った余りを求める。
3. ステップ2を、結果が0になるまで行う。
4. 結果が0になる際の割った数が、2つの数字の最大公約数である。

例

N = 1643
P1 = 31
P2 = 53

GCDの計算
52 % 30 = 22
30 % 22 = 8
22 % 8 = 6
8 % 6 = 2
6 % 2 = 0
GCD(52, 30) = 2

λ(N) = (52 * 30) / 2 = 780

ステップ2：Dの取得

Dを求めるには、以下の手順で示される拡張ユークリッドの互除法を行う。

1. A, B, Q, R, T1, T2, T3からなる7つの変数を用意する。
2. Aをλ(N)とする。
3. BをEとする。
4. QをA / B(小数点以下切り捨て)とする。
5. RをA % Bとする。
6. T1を0とする。
7. T2を1とする。
8. T3をT1 - (T2 * Q)とする。
9. AをBとする。
10. BをRとする。
11. QをA / B(小数点以下切り捨て)とする。
12. RをA % Bとする。
13. T1をT2とする。
14. T2をT3とする。
15. T3をT1 - (T2 * Q)とする。
16. Rが0になるまで、ステップ9 ~ 15を繰り返す。
17. ステップ12で終わった場合、DをT3 % λ(N)とする。そうでなくステップ15で終わった場合、DをT2 % λ(N)とする。

すべてが正しく終われば、DとEの積をλ(N)で割った余りが1となるはずである。

例

λ(N) = 780
E = 347

A	B	Q	R	T1	T2	T3
780	347	2	86	0	1	-2
347	86	4	3	1	-2	9
86	3	28	2	-2	9	-254
3	2	1	1	9	-254	263
2	1	2	0	-254	263	-780

D = 263 % 780 = 263

ステップ3：数字の復号

6つの数字は読み順に読む。各数字(C)に対して、以下の演算を行い、Pを求める。

(C^D % N) - 1 = P

Pをアルファベット上の位置の数字とみなし、英字に変換する。

復号し各数字を英字に変換したら、復号された単語を取得できるはずである。

例

暗号化された数字：1622 1247 1012 283 2 1018
D = 263
N = 1643

(1622²⁶³ % 1643) - 1 = 13 -> M
(1247²⁶³ % 1643) - 1 = 9 -> I
(1012²⁶³ % 1643) - 1 = 18 -> R
(283²⁶³ % 1643) - 1 = 1 -> A
(2²⁶³ % 1643) - 1 = 7 -> G
(1018²⁶³ % 1643) - 1 = 5 -> E
復号された単語：MIRAGE