第06回 公開鍵暗号

公開鍵暗号

前回の最初に紹介したように、暗号には大きく分けて以下の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\) とする。
    23456789
    10111213141516171819
    20212223242526272829
    303132333435

  7. \(d\) を求める
  8. 満たすべき関係式 \(de=kL+1\) には \(d\) と \(e\) が対称な形で入っている。つまり、\(d\) も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
    また、すでに分かっている値をこの関係式に入れると「\(23d=36k+1\)」、1を移項すれば「\(23d-1=36k\)」となる。つまり、候補の値それぞれについて「\(d\) を23倍して1を引き、それが36で割り切れるかどうか」を調べれば正解がわかる。
    • \(d\) が \(5\) → \(23\times5-1=114\) (36で割り切れない)
    • \(d\) が \(7\) → \(23\times7-1=160\) (36で割り切れない)
    • \(d\) が \(11\) → \(23\times11-1=252\) (36で割り切れる) → \(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ビットとなる。

暗号化の手順
  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」とする (もとの符号が得られる)
実際のRSA暗号では \(m\) は非常に大きく、300~1000程度になる。
実際に「**を**乗して**で割った余り」をまともに求める必要はない。
「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\) を求めよ。

要するに以下の表をすべて埋めればよい。
\(e\)57111317192325293135
\(d\)231135
  • \(e\) と \(d\) が満たすべき条件式にはこれらが対称な形で入っているので、ひとつのペアが決まれば \(e\) と \(d\) を入れ替えた組み合わせも自動的に決まる。
  • 「35と35」だけは計算が面倒なのであらかじめ表に値を入れてある。
  • 「35と35」のように暗号化と復号の鍵が同じになる組み合わせは実際には使用しない。
  • 紙に書いて写真で提出する場合は表の形でよいが、メール本文で書く場合は \(e\) と \(d\) の組み合わせがわかる形で書く。

課題2

課題1とは異なる素数 \(p, q\) の組み合わせ (ただし \(p\neq q\) でいずれも2桁のものにする) を決め、\(n\) と \(L\) を求めよ。また、\(e\) を1つ決め、それに対応する \(d\) を求めよ。
  • \(p, q\) をあまり大きい値にすると \(e\) の候補数が多くなる。小さめにしておいた方が楽。
  • \(e, d\) について課題1のように表を作る必要はない。ペアを1つだけ求めれば十分。
inserted by FC2 system