情報理論 第15回 公開鍵暗号

公開鍵暗号とは、暗号化と復号に使う鍵が異なる暗号のこと。第三者が暗号化の鍵を得ても、復号の鍵は簡単には得られないので解読するのが難しい。

RSA暗号

暗号化の鍵 : en
復号の鍵 : dn

鍵の準備 (あて先 (受信者) が行う)
  1. 大きな素数 pq を決める
  2. pq の積 n と、p-1q-1 の最小公倍数 L を求める
  3. L と互いに素 (2以上で1以外の共通の約数を持たない) な、L より小さい正の整数 e を決める
  4. de=kL+1 (kは整数) を満たす、L より小さい正の整数 d を求める
  5. 情報源 (送信者) に en の値を渡す

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

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

  5. e を決める
  6. L=36 を素因数分解すると 22×32 となる。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 には de が対称な形で入っている。つまり、d も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
    また、すでに分かっている値をこの関係式に入れると「23d=36k+1」、1を移項すれば「23d-1=36k」となる。つまり、候補の値それぞれについて「d を23倍して1を引き、それが36で割り切れるかどうか」を調べれば正解がわかる。
  9. 情報源に en の値を渡す
  10. 通信路を通して e=23n=247 を送る
ステップ1と3では値を勝手に決める。
ステップ2と4で決まる値は一通りだけ。
ステップ3での「互いに素」の意味に注意。この場合は2, 3で割り切れないだけで、素数ということではない (候補のうち25, 35は素数ではない)
ステップ4で e から d を求めているので、e を通信路に通すのは危険なように見えるが、このステップには L の値も必要なので、これを通信路に通さなければ安全 (原理的には n を因数分解すれば求められるが、実際は n は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能)。

暗号化・復号の前にあらかじめ決めておくこと
暗号化の手順
  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. 1323=1820828145547961773257038736474630733299942338773 で、それを247で割った余りは52になる。

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


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

  3. 変換した値を d 乗して n で割った余りを求める
  4. 5211=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)+"乗:");
  println(num);
  num=num*num0%n;
}
1乗:52
2乗:234
3乗:65
4乗:169
5乗:143
6乗:26
7乗:117
8乗:156
9乗:208
10乗:195
11乗:13

練習問題1

p=19, q=13 のRSA暗号で、e のすべての候補についてそれに対応する d を求めよ。

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

練習問題2

練習問題1とは異なる素数 p, q の組み合わせ (ただしpq でいずれも2桁のものにする) を決め、nL を求めよ。また、e を1つ決め、それに対応する d を求めよ。

p, q をあまり大きい値にすると e の候補数が多くなる。小さめにしておいた方が楽。
e, d について練習問題1のように表を作る必要はない。ペアを1つだけ求めれば十分。 inserted by FC2 system