第14回 公開鍵暗号

初めに必ず連絡事項を確認してください。

暗号の種類

解説動画

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

RSA暗号 - 鍵の決定

概要

解説動画

RSA暗号では、暗号化と復号のときにそれぞれ2つの数値を使う。そのうちの1つ \(n\) は共通で、\(e\) はencode, \(d\) はdecodeの頭文字。
暗号化の鍵 : \(e\) と \(n\)
復号の鍵 : \(d\) と \(n\)

鍵の準備 (受信者が行う)
  1. 大きな素数 \(p\) と \(q\) を決める
  2. \(p\) と \(q\) の積 \(n\) と、\(p-1\) と \(q-1\) の最小公倍数 \(L\) を求める
  3. \(L\) と互いに素 (2以上で1以外の共通の約数を持たない) な、\(L\) より小さい正の整数 \(e\) を決める
  4. \(de=kL+1\) (\(k\) は整数) を満たす、\(L\) より小さい正の整数 \(d\) を求める
  5. 送信者 に \(e\) と \(n\) の値を渡す
  1. \(p\) と \(q\) を決める
  2. \(p=19\), \(q=13\) とする
    (本来は非常に大きい値にするが、説明を簡単にするためここでは小さい値にする)

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

  5. \(e\) を決める
  6. \(L=36\) を素因数分解すると \(2^2\times3^2\) となる。1以外の共通の約数を持たないということは、要するに「2でも3でも割り切れない」ということ。2~35の範囲の数を書きだして2か3で割り切れるものを消していけば、5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 が残る。\(e\) はこの中のどれでもよいが、ここでは \(e=23\) とする。
    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

  7. \(d\) を求める
  8. 満たすべき関係式 \(de=kL+1\) を変形すると
    \((de-1)/L=k\)
    となる。これは \(d\) と \(e\) に対して対称な形なので、\(d\) も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
    この例の条件 \(L=36\), \(e=23\) では
    \((23d-1)/36=k\)
    となるので、候補の値それぞれについてこの左辺の値を計算し、それが整数になるどうかを調べればその \(d\) が対応するものかどうかがわかる。 順番に調べていくと
    • \(d\) が \(5\) → \((23\times5-1)/36=3.1...\) (整数でないのでこれは違う)
    • \(d\) が \(7\) → \((23\times7-1)/36=4.4...\) (整数でないのでこれは違う)
    • \(d\) が \(11\) → \((23\times11-1)/36=7\)
    なので、\(e=23\) に対応する \(d\) は \(11\) であることがわかる。

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

ここでは \(e=23\) に対して \(d\) が 11 になることを求めたが、逆に \(e=11\) にするとそれに対応する \(d\) は 23 になる。
同様に割り切れるものを書き出すと
\((5\times29-1)/36=4\)
\((7\times31-1)/36=6\)
\((11\times23-1)/36=7\)
\((13\times25-1)/36=9\)
\((17\times17-1)/36=8\)
\((19\times19-1)/36=10\)
\((35\times35-1)/36=34\)

のようになる。よって、\(p=19\), \(q=13\) の場合のすべての \(e\) と \(d\) の対応は表1のようになる。
(\(e\) の候補は11個あるが、対称性を考えればほぼ半分の手間で全部のペアが求められる)

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

※ 表からわかるように、\(e=d\) になることもある(このケースでは3通り)。実際の暗号化ではそういう組み合わせは使用されない。
※ 1番目と3番目のステップでは値を勝手に決める。2番目と4番目のステップで決まる値は一通りだけ。
※ 3番目のステップでの「互いに素」の意味に注意。この場合は2, 3で割り切れないだけで、素数ということではない (候補のうち25, 35は素数ではない)
※ 4番目のステップで \(e\) から \(d\) を求めているので、\(e\) を通信路に通すのは危険なように見えるが、このステップには \(L\) の値も必要なので、これを通信路に通さなければ安全 (原理的には \(n\) を因数分解すれば求められるが、実際は \(n\) は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能)。

課題1

課題1ヒント

\(p=17\), \(q=13\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。 導出過程も書き、表1のような形にまとめること。

※ まずは \(n\) と \(L\) を求める。
※ 次に太枠の説明の3番目のステップのように \(e\) の候補をリストアップする (全部で15個ある)。
※ \(e\) の候補それぞれに対応する \(d\) を求める (\(d\) も \(e\) の候補の中のどれかになる)。

RSA暗号 - 暗号化と復号

解説動画

暗号化・復号の前にあらかじめ決めておくこと
暗号化 (送信者が行う)
  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. 変換した値を \(e\) 乗して \(n\) で割った余りを求める
  3. 得られた値を \(m\) ビットの符号とする

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

  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. たとえば「0001101」だったときは \((0001101)_2=(13)_{10}\) が得られる

  3. 変換した値を \(e\) 乗して \(n\) で割った余りを求める
  4. \(13^{23}=1,\)\(820,\)\(828,\)\(145,\)\(547,\)\(961,\)\(773,\)\(257,\)\(038,\)\(736,\)\(474,\)\(630,\)\(733,\)\(299,\)\(942,\)\(338,\)\(773\)
    で、それを247で割った余りは52になる。

  5. 得られた値を \(m\) ビットの符号とする
  6. \((52)_{10}=(0110100)_2\) なので、「0110100」とする

復号 (受信者が行う)
  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. 変換した値を \(d\) 乗して \(n\) で割った余りを求める
  3. 得られた値を \(m\) ビットの符号とする
例 (上で挙げた \(n=247\), \(e=23\), \(d=11\) のケース (\(m\) は \(7\) になる)

  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. 受け取った「0110100」から \((0110100)_2=(52)_{10}\) が得られる

  3. 変換した値を \(d\) 乗して \(n\) で割った余りを求める
  4. \(52^{11}=140,\)\(007,\)\(514,\)\(618,\)\(240,\)\(900,\)\(831,\)\(252\)
    で、それを247で割った余りは13になる。

  5. 得られた値を \(m\) ビットの符号とする
  6. \((13)_{10}=(0001101)_2\) なので、「0001101」とする (もとの符号が得られる)
実際の暗号化・復号はプログラムで行うが、この際に「**を**乗して**で割った余り」をまともに求めることはない。
概要の説明に出てきた \(13^{23}\), \(52^{11}\) は10進数で49桁、24桁という巨大な数になり、まともに求めようとすると int や long で扱える範囲を遥かに超えてしまう。
これはそれぞれの桁の数値を要素とした配列として数を扱って掛け算の処理を行って強引に求めたものだが、必要なのは余りだけなのでこの値自体は必要ない。
「13の2乗」を 247 で割り切れる部分 A と余り B に分けて考えると、「13の3乗」は「13の2乗」つまり A+B に 13をかけて 13A+13B になるが、13A は 247 で割り切れる。
つまり、「13の3乗」のかわりに「13B」を 247 で割っても余りは同じになる。
このようにしてひとつ 13 をかけるたびに余りを求めていけば、上の例のように巨大な数を扱わなくても最終的な余りは求められる。

課題2

課題2ヒント

以下のようなものを表示する Processing のプログラムを完成させよ。
(解答は7, 8行目のコメント文に対応するコード)
13を1乗して247で割った余り:13
13を2乗して247で割った余り:169
13を3乗して247で割った余り:221
13を4乗して247で割った余り:156
13を5乗して247で割った余り:52
13を6乗して247で割った余り:182
13を7乗して247で割った余り:143
13を8乗して247で割った余り:130
13を9乗して247で割った余り:208
13を10乗して247で割った余り:234
13を11乗して247で割った余り:78
13を12乗して247で割った余り:26
13を13乗して247で割った余り:91
13を14乗して247で割った余り:195
13を15乗して247で割った余り:65
13を16乗して247で割った余り:104
13を17乗して247で割った余り:117
13を18乗して247で割った余り:39
13を19乗して247で割った余り:13
13を20乗して247で割った余り:169
13を21乗して247で割った余り:221
13を22乗して247で割った余り:156
13を23乗して247で割った余り:52
int n = 247; // n
int d = 23; // d
int num = 13; // 元の数
int surplus = num; // 余り

for (int i=0; i<d; i++) {
  // 結果表示
  // 「surplusに元の数をかけてnで割った余り」を surplus に入れる
}

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
(課題1でExcelを使って組み合わせを求めた場合は、そのファイルも添付してください)
課題提出用フォーム
※ 締切は12/21(土) 正午です。提出によって出席・点数がつきます。