第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\) には \(d\) と \(e\) が対称な形で入っている。つまり、\(d\) も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
    この関係式の \(e\) と \(L\) にそれぞれ 23, 36を入れると \(23d=36k+1\) になり、1を移項して両辺を36で割れば

    \((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\) を送る
ステップ1と3では値を勝手に決める。
ステップ2と4で決まる値は一通りだけ。
ステップ3での「互いに素」の意味に注意。この場合は2, 3で割り切れないだけで、素数ということではない (候補のうち25, 35は素数ではない)
ステップ4で \(e\) から \(d\) を求めているので、\(e\) を通信路に通すのは危険なように見えるが、このステップには \(L\) の値も必要なので、これを通信路に通さなければ安全 (原理的には \(n\) を因数分解すれば求められるが、実際は \(n\) は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能)。
暗号化・復号の前にあらかじめ決めておくこと
  • 符号を区切る桁数 \(m\) を求める
  • RSA暗号では、最大 \(n-1\) 種類のものを扱える。上で挙げた例では \(n=247\) であるが、7ビットで \(2^7=128\) 通り、8ビットで \(2^8=256\) 通りなので、\(m\) は7ビットとなる。
    (実際のRSA暗号では \(m\) は非常に大きく、300~1000程度になる)
暗号化の手順
  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. 変換した値を \(e\) 乗して \(n\) で割った余りを求める
  3. 得られた値を \(m\) ビットの符号とする
復号の手順
  1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
  2. 変換した値を \(d\) 乗して \(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}=1820828145547961773257038736474630733299942338773\)
    で、それを247で割った余りは52になる。

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

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

  3. 変換した値を \(d\) 乗して \(n\) で割った余りを求める
  4. \(52^{11}=140007514618240900831252\)
    で、それを247で割った余りは13になる。

  5. 得られた値を \(m\) ビットの符号とする
  6. \((13)_{10}=(0001101)_2\) なので、「0001101」とする (もとの符号が得られる)
実際の暗号化・復号はプログラムで行うが、この際に「**を**乗して**で割った余り」をまともに求めることはない (まともに求めようとすると int や long で扱える範囲を遥かに超えてしまう)。
「52の2乗」をA+B、つまりA(247で割り切れる部分) とB(余り)に分けて考えると、「52の3乗」は52A+52Bになるが、52Aは247で割り切れる。
つまり、「52の3乗」のかわりに「52B」を247で割っても余りは同じになる。
このようにしてひとつ247をかけるたびに余りを求めていけば、上の例のように巨大な数を扱わなくても最終的な余りは求められる。 例えばProcessingなら次のようになる。
int n=247;
int d=11;
int num0=52;
int num=num0;

for (int i=0; i<d; i++) {
  print((i+1)+"乗して"+n+"で割った余り:");
  println(num);
  num=num*num0%n;
}			
1乗して247で割った余り:52
2乗して247で割った余り:234
3乗して247で割った余り:65
4乗して247で割った余り:169
5乗して247で割った余り:143
6乗して247で割った余り:26
7乗して247で割った余り:117
8乗して247で割った余り:156
9乗して247で割った余り:208
10乗して247で割った余り:195
11乗して247で割った余り:13

課題1

\(p=19, q=13\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。 ただし、導出過程も書くこと。

最終的な解答は以下の表のような形になる (すでに概要で求めた11と23の組み合わせは表に入れてある)。
\(e\) 5 7 11 13 17 19 23 25 29 31 35
\(d\) 23 11
  • 導出の際の試行で結果が整数にならなかったものをいちいち書く必要はない。概要の例の「\((23\times11-1)/36=7\)」のような、対応するものを見つけたときの計算だけで十分。
  • \(e\) と \(d\) が満たすべき条件式にはこれらが対称な形で入っているので、ひとつのペアが決まれば \(e\) と \(d\) を入れ替えた組み合わせも自動的に決まる。
  • 表の \(d\) の行に同じものが2回以上出てくることはない。
  • \(e=d\) になることもある(このケースでは3通り)。実際の暗号化ではそういう組み合わせは使用されない。

課題2

\(p=13, q=31\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。 ただし、導出過程も書くこと。
  • 課題1と同様に表の形で回答する。
  • 概要の例と同様にすると \(n=pq=403, L=lcm(12, 30)=60\) となる。
  • \(L=2^2\times3\times5\) なので、\(e\) の候補は2~59の範囲の整数のうちで 2, 3, 5の倍数でないもの。全部で15個ある。
  • \(e\) のそれぞれの候補に対応する \(d\) は、これらのリストの中のどれかであり、\((de -1)/60\) が整数になるもの。
inserted by FC2 system