オンデマンドで受講する場合は、本題に入る前に必ず連絡の動画を見てください。

動画の解説を参照

今回と次回は暗号について解説します。暗号にかかわる用語は以下の通りです。 暗号には大きく分けて以下の2つがあります。 共通鍵暗号ではあらかじめ鍵を共有するか、通信路を通して鍵を送らなければならないので、第三者に盗み取られる危険があります。
公開鍵暗号の2つの鍵は無関係ではありませんが、暗号化の鍵から復号の鍵を得るのは非常に困難です。
ここでは現在使われている代表的な公開鍵暗号、RSA暗号について紹介します。
(ちなみに「RSA」は開発者3人の名前の頭文字です)

動画の解説を参照

RSA暗号では、暗号化と復号のときにそれぞれ2つの数値を使います (\(e\) はencode, \(d\) はdecodeの頭文字です)。 鍵は以下の手順で受信側が作ります。
こうしてできた鍵のうち \(e\) と \(n\) を、通信路を通して送信側に送ります。

---

例

1. \(p\) と \(q\) を決める
   \(p=13\), \(q=19\) とする
   (本来は非常に大きい値にしますが、説明を簡単にするためここでは小さい値にします)
   
   
2. \(n\) を求める
\(n=pq=247\)


3. \(L\) を求める
\(L=lcm(18, 12)\)\(=36\)
(「\(lcm\)」は最小公倍数のことです)


4. \(E\) をつくる
\(L=36\) を素因数分解すると \(2^2\times3^2\) となります。
つまり、\(L\) と互いに素な数は「2でも3でも割り切れない数」です。
\(2\)～\(L-1\)、つまり2～35の範囲の数を書きだして2か3で割り切れるものを消して、残ったものが \(E\) です。

\(E\) = {5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35}

		2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18	19
20	21	22	23	24	25	26	27	28	29
30	31	32	33	34	35



5. \(e\) を決める
ここでは \(e=23\) とします (無作為なので 23 であることに特に意味はありません)。


6. \(d\) を求める
順番に調べていくと
• \(5\) → \((23\times5-1)/36=3.1...\) (割り切れない)
• \(7\) → \((23\times7-1)/36=4.4...\) (割り切れない)
• \(11\) → \((23\times11-1)/36=7\) (割り切れる)
なので、\(d=11\) になります。


7. 送信者に \(e\) と \(n\) の値を渡す
通信路を通して \(e=23\) と \(n=247\) を送る

---

\(e\) と \(d\) の対称性
6番目のステップでは \(e\times d-1\) が \(L\) で割り切れるかどうかを調べるので、\(e\) と \(d\) を逆にしてもこの条件は成り立ちます。
つまり、\(e=23\) に対して \(d=11\) なら \(e=11\) なら \(d=23\) になるということです。
同様にすれば、\(E\) に含まれる要素すべてについてペアを求められます。
上記の例だとこうなります。

\(e\)	5	7	11	13	17	19	23	25	29	31	35
\(d\)	29	31	23	25	17	19	11	13	5	7	35

---

※ 6番目のステップで \(e\) から \(d\) を求めているので、\(e\) を通信路に通すのは危険なように見えますが、このステップには \(L\) の値も必要なので、これを通信路に通さなければ安全です。
(原理的には \(n\) を因数分解すれば求められますが、実際は \(n\) は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能です)。

※ 準備 : 学籍番号を入れて「入力」をクリック (タップ) してください。
学籍番号 入力

\(p\), \(q\) として \(E\) を求めてください。
課題1解説

課題1の \(p\), \(q\) で \(e\) の場合の \(d\) を求めてください。
課題2解説

動画の解説を参照

ここからは、前節で作った鍵を使って具体的に暗号化・復号する方法について解説します。

---

暗号化・復号の前にあらかじめ決めておくこと
RSA暗号では、数値としては \(0\)～\(n-1\) を扱えます。
前節の例では \(n=247\) なので最大値は 246 です。
\(2^7=128\lt 246 \lt2^8=256\) なので、符号を7bitずつに区切れば扱える範囲に収まります。
この区切る桁数を \(m\) とします。
(実際のRSA暗号では \(m\) は非常に大きく、300～1000bit程度です)

暗号化 (送信側が行う)

1. 符号を \(m\) 桁ずつ区切る (これをPとします)
2. Pを2進数の値として読み、10進数の値に変換する (これをQとします)
3. Qを \(e\) 乗して \(n\) で割った余りを求める (これをRとします)
4. Rを \(m+1\) bitの2進数に変換し、符号とする (これをFとします)

復号 (受信側が行う)

1. 符号を \(m+1\) 桁ずつ区切る (これをF'とします)
2. F'を2進数の値として読み、10進数の値に変換する (これをR'とします)
3. R'を \(d\) 乗して \(n\) で割った余りを求める (これをQ'とします)
4. Q' を \(m+1\) bitの2進数に変換し、符号とする (これをP'とします)

---

例 (上で挙げた \(n=247,e=23,d=11,m=7\) のケース)

暗号化

1. 符号を \(m\) 桁ずつ区切る
たとえば P = 0010010


2. Pを2進数の値として読み、10進数の値に変換する
\((0010010)_2=(18)_{10}\) → Q = 18


3. Qを \(e\) 乗して \(n\) で割った余りを求める
Q^e = 18²³ =
で、それを247で割った余り → R = 151


4. Rを \(m+1\) bitの2進数に変換し、符号とする
\((151)_{10}=(10010111)_2\) → F = 10010111

復号

1. 符号を \(m+1\) 桁ずつ区切る
F' = 10010111


2. F'を2進数の値として読み、10進数の値に変換する
\((10010111)_2=(151)_{10}\) → R' = 151


3. R'を \(d\) 乗して \(n\) で割った余りを求める
R'^d = 151¹¹ =
で、それを247で割った余り → Q' = 18


4. Q' を \(m\) bitの2進数に変換し、符号とする
\((18)_{10}=(0010010)_2\) → P' = 0010010 (もとの符号が得られる)

---

実際の暗号化・復号はプログラムで行いますが、この際に「＊を＊乗して＊で割った余り」をまともに求めることはありません。
上の例に出てきた \(18^{23}\), \(151^{11}\) は10進数で29桁、24桁という巨大な数になり、まともに求めようとすると int や long で扱える範囲を遥かに超えてしまいます (ちなみに、この数は配列を使って疑似的に巨大な数を扱えるようにして計算しました)。

必要なのは余りだけなのでこの値自体は必要ありません。
「18の2乗」を 247 で割り切れる部分「247A」と余り「B」に分けるとこう書けます。 これに18をかければ18の3乗になります。 「247×18A」は247で割り切れます。
つまり、「18の3乗」のかわりに「18B」を 247 で割っても余りは同じです。
このようにしてひとつ 18 をかけるたびに余りを求めていけば、上の例のように巨大な数を扱わなくても最終的な余りは求められます。

課題2の \(e\), \(n\) で P = を暗号化してください。
※ \(n\) の値にあわせ、\(m\) の桁数にしてあります。
課題3解説

課題3で求めたFが通信路で変化しなかった前提で復号してください。
課題4解説

課題解答