自由研究・C1

公開鍵暗号の仕組み


2011/09/24-2011/09/29
Copyright (C) 2011, cazz
アドレス

はじめに

公開鍵暗号について調べてみようと思ったのは、単純な理由で、「どうして暗号と復号に異なる鍵を用いることができるのだろう。公開鍵から秘密鍵を作ることがそんなに難しいのだろうか。」という疑問を持ったからだ。調べてみると、確かに理論は難しい(ややこしい)が、鍵の秘匿性は、大きな数の素因数分解の困難性のみに完全に依存しており、現在のように大きな素数が発見されると公表されるような時代では、素数の表を作っておけば公開鍵から秘密鍵が作成可能なのではと考えてしまう。この疑問の答えはまだ見つかっていない。

話を進めるに当たって、あまり暗号に縁がない読者を念頭に置いて、暗号と数学の簡単な復習から始めることとする。

秘匿通信

一般的には、他人に知られないように情報を秘匿したものを「暗号」と呼ぶことが多いと思いが、そのような情報伝達法は、正式には「秘匿通信」と呼ばれる。秘匿の方法には以下のような方法がある。

正式な用語としては、この「サイファ」を暗号と呼ぶ。この自由研究で取り扱う「暗号」も「サイファ」である。コンピュータで処理する場合、元の文章(文字列)は長大な2進数と見なすことができる(実際には一定の長さに区切って、複数の2進数として処理する)。この2進数を暗号関数に入れて計算させ、その結果として暗号文を得るのである。暗号文を元の文に戻す(復号)も同様の処理となり、暗号文を2進数として復号関数に入れて計算し、結果として元の文章を得る。

暗号とハッシュ

ハッシュは暗号と共によく用いられるが、暗号ではない。暗号とは、暗号処理と復号処理によりメッセージの伝達を行なう仕組みであり、暗号は復号してはじめて意味を持つ。それに対し、ハッシュは一方向の処理によりメッセージの改変がないかどうかを確認する仕組みである。ハッシュもある数(2進数で表された文)から、別の数(ハッシュ値)を得るところは同じだが、ハッシュ値は長さがあまり大きくなく一定で、しかもハッシュ値から元の数を求めることはできない。元の数が異なれば、ハッシュ値も異なると見なせる(実は同じハッシュ値になることがあり得るが、同じハッシュ値になる場合、元の数は全く異なっている。似ている数のハッシュ値は必ず異なると言って良い)ので、同じメッセージかどうか(メッセージに改竄がないかどうか)ハッシュ値を比較して検証する目的に使用される。

暗号方式

暗号は、様々な方式が古来から工夫されてきた。古代ローマでは、細長い紙に文章を書いて棒に巻き付けたものを縦に読んで暗号にしたと言うし、エドガー・アラン・ポーの小説「黄金虫」にはキャプテンキッドの宝のありかを示す暗号として換字式暗号が登場する。しかし、暗号は計算機の登場により様変わりした。とくに高性能のデジタル計算機(コンピュータ)が登場してから、非常に高度な暗号(デジタル暗号方式)が実用化された。

暗号方式
古典暗号 換字式暗号 別の文字を割り当てる
単一換字、多表式換字など
転置式暗号 文字を並べ替える
現代暗号 共通鍵暗号 暗号化・復号で同じ鍵を使う
公開鍵暗号 暗号化・復号で異なる鍵を使う

その中でも重要なものが「鍵暗号」で、「鍵」と呼ばれる数字を暗号・復号アルゴリズムに組み合わせることで高度な秘匿を可能とするものである。鍵暗号の特徴として、(暗号・復号の)アルゴリズム自体を知られても構わないことが挙げられる。鍵を変えることで何度でも使えるからである。逆に、アルゴリズムの公開により信頼性(解読のしにくさ)を検討することさえできる。鍵暗号の解読は数学的に不可能な訳ではない。解読に非常に長い時間を要するのである。暗号化されている情報自体は、ある期間が過ぎると価値がなくなってしまうのが普通である。従って、解読に非常に長い時間を要する場合、暗号を解読する意味がなくなってしまうのである。つまり、解読までの時間の長さが暗号の安全性を表すことになる。ある暗号の解読法が発見されたと言われるときは、実用的な時間で有効な解が求まるアルゴリズムが発見された(発明された)ということである。

鍵暗号の解読しにくさの指標が「鍵の長さ」である。これは鍵の「桁数」であるが、2進数表現した際のビット長(桁数)と規定されている。鍵の長さは、鍵が取り得るパターン数であるとも言える。

鍵暗号のうち、公開鍵暗号は、暗号と復号に異なる鍵を用いるもので、暗号化の鍵から公開化の鍵を突き止めることが非常に困難であることから、暗号化の鍵を公開しても安全性が保てる方式であるとされ、多方面に応用されている。以下に鍵暗号の分類と例を示す。

鍵暗号の分類
方式 特徴
共通鍵暗号

暗号と復号に
同じ鍵を用いる

AES、DES(ブロック暗号)、RC4(ストリーム暗号)  
公開鍵暗号 暗号と復号に
異なる鍵を用いる
RSA、楕円曲線暗号 RSA暗号の公開鍵長1024bitと楕円曲線暗号の公開鍵長160bitの計算量的安全性はほぼ等しいが、後者は前者より総当り攻撃をされやすい。
RSA
公開鍵暗号の一つ。
桁数が大きい数の素因数分解が困難なことを安全性(解読に時間がかかること)の根拠とする。
n = a×b でnから公開鍵を、aとbから秘密鍵を生成する。
暗号とデジタル署名を実現できる方式として、1977年にRon Rivest、Adi Shamir、Len Adlemanにより最初に公開された。名称は開発者の頭文字。
DES(Data Encryption Standard)
共通鍵暗号方式(ブロック暗号)。
ブロック長:64ビット、鍵長:56ビット。
米国内での暗号方式の公募に応募したものの中から、IBMが提案した暗号方式LuciferにNSAが修正を施したもの。1976~77年に連邦規格(FIPS PUB 46)となり、1981年に ANSIに採用された。
1990年代末に総当たり攻撃(Brute Force Attack) により完全解読が可能であることが実証され、以来使用されなくなってきている。
AES(Advanced Encryption Standard)
共通鍵暗号方式(ブロック暗号)。
ブロック長:128ビット、鍵長:128ビット、192ビット、256ビットの3つ。
1977年に発行されたDESが時代遅れとなったため、新たな暗号方式の公募により採用されたもので、2001年3月、米国の暗号規格として規格化された(FIPS PUB 197)。

公開鍵暗号の使用法

公開鍵暗号の利用法には2つの意味合いがある。公開鍵暗号方式の場合、公開鍵と秘密鍵の2つの鍵があるが、もちろん公開鍵が「公開」される。情報の送り手に公開鍵を送って、送信する情報を暗号化してもらう場合、受信された情報は秘密鍵を持った者しか解読できないので、情報が秘匿されることになる。この使用法が一般的に暗号通信と呼ばれる使用法である。これに対し、情報の送り手が受け手に公開鍵を送る場合がある。この場合、送り手の作成した暗号文は秘密鍵を持っている者のみが作成可能であるから、情報の受け手は、送られてきた情報が秘密鍵の持ち主から者であると確認することができる。これが電子署名である。

関連する数学

累乗

aを複数回掛け合わせたものをaの累乗と呼ぶ。n回乗算したものをan乗と呼び、anと表記する。とくに、

a×a×…×a = an
am× an = am+n  (am)n = amn

剰余系

abn があって、a ÷ n = q あまり b のとき「abnを法として合同」であると言い、

ab (mod n) 

と書く。とくに、

abbc なら ac
abcd なら abcd(○は四則演算)

である。また、

ab (mod n) 

であれば、ある整数qがあって、

a = nq + b

と書くことができる。この q は最初に示した除算の商(答え)である。

ユークリッドの互除法

2数の最大公約数を求める方法で、交互に剰余(割り算の余り)を求め除算を繰り返す。

例:9と24の最大公約数ユークリッドの互除法を用いた9と24に最大公約数の計算

最大公約数を求めるアルゴリズムとしては非常に高速であると言われている。

オイラーの定理

オイラーの定理を説明するには、オイラーの特性関数を説明しておかなければならない。

オイラーの特性関数(φ関数)

オイラーの特性関数は、φ関数、トーシェント関数注1(totient function)などとも呼ばれる。一般にφ(n)と書かれるのが普通で、「自然数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を与える」と定義される。「互いに素」とは、共通約数(公約数)が1以外にない(最大公約数が1)ということである。つまり

φ(1) = 1(1は自分自身しか約数を持たない。これは特例)
φ(4) = 2(1と3が素)
φ(5) = 4(1、2、3、4が素、つまり、5未満のすべての自然数が素)
φ(6) = 2(1と5が素)
φ(7) = 6(7未満のすべての自然数が素)

とくに、

n が素数のとき φ(n) = n - 1

m, n が互いに素なとき φ(mn) = φ(m) φ(n)

である。

任意の n に対してφ(n)を求める計算方法についてはここでは触れない。「http://ja.wikipedia.org/wiki/オイラーのφ関数」 の「性質」の項を参照されたい。

オイラーの定理

オイラーの定理はφ関数を用いて以下のように書ける。

互いに素である自然数nMに対して
     Mφ(n) ≡ 1 (mod n)

オイラーの定理の証明

2段階で証明することとする。まず、「n と互いに素な n 以下の正の整数の集合」と、「その集合の各要素に n と互いに素な自然数 M を乗じて作成した集合」が n を法として等しいことを証明しよう。

n と互いに素な n 以下の正の整数の集合を

A = {b1, b2, ..., bφ(n)}

とし、この集合 A の要素のそれぞれに n と互いに素な自然数 M を乗じた集合を

B = {Mb1, Mb2, ..., Mbφ(n)}

とする。Mn は互いに素だから、集合 A の異なる2つの要素 bxbyについて、

bxby であるから
bx - by = kk ≠ 0)
Mbx - Mby = MkM ≠ 0, k ≠ 0)
MbxMby

また、逆に集合 B の要素についても、要素が異なれば集合 A の異なる要素に対応することが分かる。ゆえに、集合 A, B の各要素は1対1に対応する。従って、集合 A, Bn を法として等しい(一致する)。
(証明終)

次に、集合 A, B の全ての要素の積を考え、それらが等しいことからオイラーの公式を証明する

集合 A, Bn を法として等しいので、その要素の積も法 n において等しくなる。すなわち A の全ての要素の積を P とすれば、

P = b1 b2 ... bφ(n) (b1 からbφ(n) までの φ(n) 個の自然数の積)

であり、B の要素の積は

Mb1 Mb2 ... Mbφ(n) = Mφ(n) (b1 b2 ... bφ(n)) = Mφ(n) P

となる。これらが等しいから、

PMφ(n) P (mod n

nP は互いに素だから

1 ≡ Mφ(n)(mod n

(証明終)

オイラーの定理の応用例

例えば72009の下2桁を求めたい場合、次のように計算する。

φ(100) = 40 なので(ここは計算で求める。あるいは既存の知識を利用する。「下2桁」なので100を選択している)、オイラーの定理から

740 ≡ 1 (mod 100)

よって

72009 = 79 × (740)50 ≡ 79 ≡ 7 (mod 100)

ゆえに下2桁は07になる。

2009を40で割ると商が50、余りが9となることは手計算で行う。また、79 = 40353607も手計算で求める。ここでわかることは、7の累乗の下2桁は、40を周期として循環しているということである。もっと短い周期があるかもしれないが、それは40の約数でなければならない。

オイラーの定理とRSAの仕組み

RSAの仕組み

素数 p, q を選択し、その積 n を求める。φ(n)未満の正の整数で、φ(n) と互いに素な数を1つ決める(それを e と書くこととする)。公開鍵は{e, n}となる。この公開鍵を用い、平文 M を以下のとおり暗号化する。

暗号化:MeC (mod n)

つまり、元の平文を数と見なし(実際にコンピュータ内で扱われる文字列は、長大な2進数である)、それを e 乗した上で、nで割った余りを求め、それを暗号文とするのである。従って、暗号文は n 以下の長さのものしか作れない。実際に暗号化するには、元の平文を分割して、それぞれ暗号化することとなる。

復号化には、n を法とした e の逆数を用いる(詳細は「鍵の生成」の項で解説する)。n を法とした e の逆数を d とすると、

復号化: CdM (mod n)

つまり、暗号文を d 乗し、n で割った余りを計算すると元の文字列が求まるので、この d を秘密鍵とする。資料によっては{p, q, n}や{p, q, e}を秘密鍵としている。実際の計算に用いるのは dn であるが、n は公開鍵に含まれ、de, p, q から求めることができる。

この de の逆数)を求めるのに p, q が必要(p, q がないと計算に非常に時間がかかる)なので、d のみを公開鍵とする場合は、n を生成した後に p, q を安全に破棄する。

RSA鍵の生成

秘密鍵 d を生成することは、既に述べたとおり、φ(n)を法とした e の逆数 d を求めることである。定義より

ed ≡ 1 (mod φ(n))
ここで φ(n) = φ(pq) = φ(p)φ(q) = (p -1)(q -1)

このとき
ed = (p -1)(q -1)x + 1 (x は任意の整数)
と表せる。

以下、2つの方法に分かれる。

  1. x = 1, 2, …, φ(n)として上式が e で割り切れるものを求める。
  2. e と φ(n)からユークリッドの互除法により d を求める。

方法1については解説が不要であると考えられるので、方法2については後で若干解説したい。この部分が調べていったときにもっとも分かりにくい箇所だった。大体、剰余系における逆数と言うのがイメージを掴みにくい。秘密鍵の計算の前に、大まかな全体像について説明しておく。

RSA復号の証明

C dM (mod n) を証明する。

ここで d はφ(n)を法とした e の逆数であるから

ed ≡ 1 (mod φ(n))

である。この式を書き換えると、ある x があって

ed = x φ(n) + 1

C d ≡ (M e)dM ed (mod n)だから

M edM x φ(n) + 1M x φ(n) × M (mod n) となる。

ここで M x φ(n) = (M φ(n)) x ≡ 1x = 1 (mod n

従って、C dM ed ≡ 1x × M = M (mod n

(証明終)

RSAの使用例

鍵ペアを実際に生成してみる。

  1. 2つの素数として5、7を選択する。
  2. 2つの素数の積(n)を求める。
    n = 5×7 = 35
  3. 35未満でφ(n)と互いに素となる e を決める。
    ここでφ(n) = (5 − 1)(7 − 1) = 24
    e = 5とする。
    ★公開鍵は {5, 35} となる。{p, q, e}を秘密鍵とする場合、秘密鍵は {5, 7, 5} となる。
  4. ed ≡ 1(mod φ(n))となる d を求める。
    ここでφ(n) = (5 − 1)(7 − 1) = 24
    5×5 = 25 ≡ 1(mod 24)
    であるから、
    d = 5
    ★復号化鍵を秘密鍵とする場合、秘密鍵は {5} となる。

実際には d の値は計算により求める。この後に解説する。

この鍵ペアを用いた暗号化、復号化の例を示す。

復号鍵の計算

RSAの仕組みのうち、ユークリッドの互除法の応用による秘密鍵の計算が調べていてもっとも分かりにくい箇所だった。

なぜ分かりにくいかというと、ユークリッドの互除法は、実際の数を使って行うと、非常に簡単な方法であるが、一般式として説明しようとすると全貌が掴みにくいからであると思う。

例:5と24の最大公約数ユークリッドの互除法を応用した剰余系での逆数の計算

この例で分かるように、互いに素な2数(ここではeとφ)に対してユークリッドの互除法を行うと、最後から2つ目には必ず1が出てくる。そこで

x - y = 1

のような等式を作成すると、xyはいずれもeとφの1次式として表すことができる。従って、

Ae + Bφ = 1

と変形することができる注2。それならば Bφを移項すれば

Ae = - Bφ + 1

となるので、

Ae ≡ 1(mod φ)

となり、e の逆数(この場合はA)が求まる。

e と φ(n) にユークリッド互除法を適用した場合を一般式で説明すると以下のようになる。

φ(n) をφと書くと、φ > e であり、e, φ(n)は互いに素であるから

φ = eq1 + φ1
e = φ1p1 + e1
φ1 = e1q2 + φ2
e1 = φ2p2 + e2

φk-1 = ek-2qk + φk
ek-1 = φkpk + 1(互いに素であるから、最大公約数は1)
φk = 1qk+1 + 0

という一連の式に展開される。

下から3行目の式を変形し、下から2行目の式に代入すると、

φk= φk-1 - ek-2qk
1 = ek-1 - φkpk = ek-1 - (φk-1 - ek-2qk)pk = ek-1 - φk-1 pk + ek-2pkqk

下から4行目の式を変形し、さらに代入すると

ek-2 = φk-1pk-1 + ek-1(下から4行目の式) を
ek-1 = ek-2 - φk-1pk-1 と変形し
1 = e k-1 - φk-1 pk + ek-2pkqk = (ek-2 - φk-1pk-1) - φk-1 pk + ek-2pkqk = ek-2(1 + pkqk) - φk-1(pk-1+ pk)

などとなり、最終的には

Ae + Bφ = 1

と書けることが分かる。以下前の説明と同様。
(証明終)

実際のプログラムでは、再帰呼び出しを用いれば簡単に実装できるだろう注3


  1. totientの発音は調査中。YouTubeに数学ビデオを多数アップロードしているjonesmathedは「トーシェント/touʃənt/と発音しているので、ここでは取り敢えず「トーシェント」を採用した。日本語版ウィキペディア内部でも統一が取れていないが、「トーティエント」が優勢。
  2. 互いに素な e とφの1次式

    Ae + Bφ = 1

    に整数解が存在すると言うのは「中国の剰余定理」と言うらしく、ウィキペディアにも証明がある。先に中国の剰余定理を証明しておけば、その先は簡単。

  3. 実際に計算する場合、再帰呼び出しは分かり易いが、大きな数の場合、非常にメモリを食う可能性がある。ループで実装するほうが効率的だろう。

参考文献


このページの一部または全部を著者に無断で転載・複製することを禁ずる