暗号の話

-- 目次 --

  1. 前書き
  2. 暗号について, 一般論
  3. DES (Data Encription Standard) -- データ暗号化規格
  4. 公開鍵 (public key) 暗号
  5. デジタル署名
  6. ハッシュ関数 (Hash Function)
  7. 各種アルゴリズム
  8. 雑多なこと

1. 前書き

暗号のことを最初に知ったのは, 1980 年頃, 本屋で買った本 (文献 1) の『新種の暗号』を読んだときが最初です (RSA 暗号を紹介した記事です)。 これは勉強のために 読んだわけではなかったのですが どういうわけだか、その後色々な本で勉強するハメになりました。 最近ではインターネットで検索すると、 暗号に関連したページが随分たくさん出てきますが、 ほぼ大半が英文で書かれています。 そこで 英語を読むのが面倒くさいという人を対象にページを作ってみることにしました。 (但し、少し難しい話になってしまっているかもしれません。 その場合は悪しからず。)

また暗号と言えば、暗号メールの PGP を思い出す人も多いと思います。 これに関してはインストール方法などを別のページで扱っています。

PGP -- 暗号ソフト

参考文献

  1. マーチン・ガードナー (一松信訳), 数学ゲーム I, 日本経済新聞社
  2. Knuth, The Art of Computer Programming, Vol 2, Addison-Wesely
    (邦訳, 準数値算法 / 算術演算, サイエンス社)
  3. N. Koblitz, A course in Number Theory and Cryptography, GTM 114, Springer-Verlag
  4. D. R. Stinson, Cryptography, theory and practice, CRC, (邦訳, 暗号理論の基礎, 共立)
  5. FIPS HOME にある電子文書,具体的には
2. 暗号について, 一般論

古典暗号でよく知られているものに次のものがある. アルファベット A, B, C, ... , Z (26 文字) を使用した文章が 与えられたときに


A B C D E F G ...... S T U V W X Y Z
D E F G H I J ...... V W X Y Z A B C

のように右に周期的にずらした文字の列を与え, 平文 (もとの文章) の文字 を下の列の文字で置き換える. そうすると例えば


YES --> BHV
 

のように暗号化される. 読み取る場合には逆の対応を与えることによって 文章を復元する (シーザー暗号, Julius Caesar). この例では


S = { A, B, C, ... , Z }
 

とおけば, 暗号化することは全単射写像


f : S ---> S
 

を与えることであり, 解読することは, その逆写像


f - 1 : S ---> S
 

を与えることである.

暗号化の方法には実は 2 種類の方法があります。

  1. 秘密鍵暗号方式 (private key cryptography)
  2. 公開鍵暗号方式 (public key cryptography)
公開鍵暗号方式は『閉じる鍵』 f と『開ける鍵』 f - 1 が違っているもので、f がわかっても f - 1 が事実上 計算できないものです。このとき f は落し戸関数 ( trap door function) あるいは一方向関数(one-way function) と呼ばれ、 『閉じる鍵』 f は公開しても支障がありません。あとで紹介する RSA 暗号、 Diffie-Hellman 暗号などが公開暗号方式の代表的なものです。

秘密暗号方式では『閉じる鍵』 f と『開ける鍵』 f - 1 が 事実上同じもので、上で与えたシーザー暗号がこれに相当します。 この暗号では『閉じる鍵』も『開ける鍵』も、どちらも絶対に秘密にしないと いけません。また通常は閉じる場合の処理と開ける場合の処理が 本質的に同じになるように工夫されているため、 対称暗号方式(symmetric key cryptography) (あるいは対称暗号, symmetric cipher) などとも呼ばれています。

3. DES (Data Encription Standard) -- データ暗号化規格

DES は 1970 年代に IBM によって開発された暗号化アルゴリズムで、 1975 年に National Bureau of Standards and Technology (後の National Institute of Standards and Technology = NIST) によって公表され、 1977 年に (国防目的など以外の) 米国連邦政府の標準として採用され、 以後数年おきに再検討されている。 DES は米国の銀行などで広く使われていますが、 現在ではハードウェアー的な方法で解読が可能となったため、 1999 年の再検討に際しては DES を 3 段にした triple DES への移行が推奨されています。 将来的には (21 世紀には) 現在開発途中の AES (= Advanced Encription Standard) が標準となるようです。詳しくは

Cryptographic Module Validation (CMV) Program
の中の announcement もしくは Draft FIPS 46-3 (1999 年四月に正式正式採用) を参照してください (後者は Acrobat reader が必要です)。

DES の仕組み

DES の規格は FIPS 46-2 あるいは FIPS 46-3 (FIPS = Federal Information Processing Standards Publication) に詳細が記載されていて、上で引用した

Cryptographic Module Validation (CMV) Program
の中で読むこともできます。また NIST の
FIPS HOME
で公表されている FIPS 文書を読むことができます。 文書は英文ですが、懇切丁寧な説明があり、 随分わかりやすく書かれています。 しかし、英文を読むのが億劫な人のために 簡単に紹介することにしましょう。

DES の鍵 K は 64 ビットで、そのうち 8 ビットはパリティー検査ビットで、 実質は残りの 56 ビットから構成されている。 DES では以下のようにして、鍵 K を用いて、64 ビットの平文 x が 64 ビット の暗号文 y に変換される。

  1. x を長さ 64 のビット列とする。 最初に定められた置換 (initial parmutation) IP を x に施す。 これを次のように略記する。


    x 0 = IP( x ) = ( L 0 , R 0 )    ( L 0 は左 32 ビット、 R 0 は右 32 ビット)
     

  2. ( L i , R i ) (1≦i≦16)  を次のようにして順番に定める。


    ( L i - 1 ,  R i - 1 ) ---> ( L i ,  R i ) = ( R i - 1 ,  L i - 1  XOR  f ( R i - 1 , K i ) )
     

    但し、

もう少し詳しく説明をしよう。

解読の方法

f の構成法を知らなくても、暗号化 x --->y の逆写像はすぐわかる。 基本的には ( L i ,  R i ) から ( L i - 1 ,  R i - 1 ) が決定できればよいだけであるが、

R i - 1 =L i
L i - 1 = R i  XOR  f ( L i , K i )

となるから明らかである。(mod 2 では 1 = -1 であることに注意。)

初期置換 IP

初期置換 IP は次で与えられる置換である。 


58    50   42    34    26   18    10    2
60    52   44    36    28   20    12    4
62    54   46    38    30   22    14    6
64    56   48    40    32   24    16    8
57    49   41    33    25   17     9    1
59    51   43    35    27   19    11    3
61    53   45    37    29   21    13    5
63    55   47    39    31   23    15    7

すなわち、IP によってもとの 58 番目のビットが 1 番目に来て、50 番目のビットが 2 番目に来て、 ... もとの最期のビットが 7 番目のビットとなるわけである。 IP - 1 は次で与えられる。 

40     8   48    16    56   24    64   32
39     7   47    15    55   23    63   31
38     6   46    14    54   22    62   30
37     5   45    13    53   21    61   29
36     4   44    12    52   20    60   28
35     3   43    11    51   19    59   27
34     2   42    10    50   18    58   26
33     1   41     9    49   17    57   25

関数 f に関して

長さ 32 のビット列 R と長さ 48 のビット列 K に対して、 f( R, K ) の構成法を説明しよう。 最初に、次の対応で R に対して長さ 48 のビット列 E(R) を生成する。 


32    1     2    3     4     5
 4    5     6    7     8     9
 8    9    10   11    12    13
12   13    14   15    16    17
16   17    18   19    20    21
20   21    22   23    24    25
24   25    26   27    28    29
28   29    30   31    32     1

即ち、E(R) の最初の 3 ビットは R の 32 番目、1 番目、 2 番目のビットである。 このあとで、E(R) と K の排他的論理和  E(R) XOR K  を考え、これを、長さ 6 の 8 個のビット列 B 1 , B 2 , ... B 8 にわける :


E(R)  XOR  K = B 1 B 2 ... B 8    (右辺は単に横にならべたビット列である)
 

更に長さ 6 の各ビット列 B i を長さ 4 のビット列 S i ( B i ) に変換し、 これをならべたものを更に置換 P で変換したものが f ( R, K ) である :


f ( R, K ) = P( S 1 ( B 1 ) S 2 ( B 2 ) ... S 8 ( B 8 ) )
 

但し、置換 P は 


16   7  20  21
29  12  28  17
 1  15  23  26
 5  18  31  10
 2   8  24  14
32  27   3   9
19  13  30   6
22  11   4  25

で与えられ、ビット列 S i ( B i ) は次のようにして決める。 S i は成分が 0 から 16 までの整数からなる (4, 16) 行列で、例えば S 1 は次によって与えられる : 


14  4 13  1  2 15 11  8  3 10  6 12  5  9  0  7
 0 15  7  4 14  2 13  1 10  6 12 11  9  5  3  8
 4  1 14  8 13  6  2 11 15 12  9  7  3 10  5  0
15 12  8  2  4  9  1  7  5 11  3 14 10  0  6 13

i = 1 の場合を例に取って、 長さ 4 のビット列 S 1 ( B 1 ) の定め方を説明する。 B 1 は長さ 6 のビット列であるから、最初と最期のビットから、 2 桁の 2 進数が構成でき 0 から 3 までの整数を表す。 B i の中央の 4 個のビットから 4 桁の 2 進数を構成でき 0 から 15 までの 整数を表す。そこでこれらをそれぞれ S 1 の行番号、列番号とみなす。 (但し番号は 0 から始める。) すると S 1 の成分が定まることになり、0 から 15 までの整数、 すなわち長さ 4 のビット列 S 1 (B 1 ) が定まることになるのである。例えば B 1 = 011011 であれば、行番号は 01 (=1), 列番号は 1101 (= 13) となり、 S 1 の (1,13) 成分は 5 (表の赤の文字) であるから


S 1 ( B 1 ) = 0101
 

となる。S i (1≦i≦8) に関しては FIPS 46-3 に具体的な形が載っている。

キー スケジュール (key schedule)

56 ビットの K から 48 ビットの K 1 , K 2 , ..., K 16 を生成するアルゴリズムをキー スケジュールと呼ぶ。 キー スケジュールにおいては最初にビット列 K に適当な置換選択 (permuted choice) PC-1 をほどこす。置換選択とは、置換と本質的に 同じであるが、この場合には 64 ビットのうち 8, 16, ..., 64 の位置以外のビットを 1 から 56 の位置に動かす。(もともと 8, 16, ..., 64 のビットは各バイトが奇数パリティー になる目的で使用されていた。)


PC-1 : { 長さ 64 のビット列 } ---> { 長さ 56 のビット列 }
 

更に長さ 56 のビット列を上、下 28 ビットにわけてその各々に 左巡回シフトを適当にほどこしてから置換選択 PC-2 をほどこす。


PC-2 : { 長さ 56 のビット列 } ---> { 長さ 48 のビット列 }
 

置換選択 PC-1 の具体的な形は 


57   49    41   33    25    17    9
 1   58    50   42    34    26   18
10    2    59   51    43    35   27
19   11     3   60    52    44   36

63   55    47   39    31    23   15
 7   62    54   46    38    30   22
14    6    61   53    45    37   29
21   13     5   28    20    12    4

上の表の成分に 8, 16, ..., 64 があらわれていないことに注意する。左巡回シフトの回数は 


 1      1
 2      1
 3      2
 4      2
 5      2
 6      2
 7      2
 8      2
 9      1
10      2
11      2
12      2
13      2
14      2
15      2
16      1

この表は第 1 段、第 2 段、第 3 段、...では左巡回シフトをそれぞれ 1 回、1 回、2 回 ... することを意味し、 例えば K 3 を得るためには 1 + 1 + 2 回左巡回シフトする。 置換選択 PC-2 の具体的形は 


14   17    11   24     1     5
 3   28    15    6    21    10
23   19    12    4    26     8
16    7    27   20    13     2
41   52    31   37    47    55
30   40    51   45    33    48
44   49    39   56    34    53
46   42    50   36    29    32

成分は全部で 48 個であるから、1 から 56 までの数が全部出てはいない。

3 重 DES (triple DES)

56 ビットの鍵 K に対しての DES の暗号化、解読をそれぞれ e K , d K であらわす。 3 個の 56 ビットの鍵 K 1 , K 2 , K 3 に対して


x ---> e K 3 ( d K 2 ( e K 1 (x) ) )   (x は長さ 64 のビット列)
 

が 3 重 DES である。この暗号化ではキーが大きくなるため、 しらみつぶしにキーを探す攻撃に対しては、 DES よりはるかに安全になり、 しかも K 1 = K 2 = K 3 であれば、 既存の DES に一致するため、DES との互換性が保証されることになる。

DES の使用モード

長さ 64 のビット列の場合の DES の暗号化の方法を適用することによって、 より長いビット列を暗号化することができるが、それには幾つかのモードがある。 いずれの場合も平文を 64 ビットごとのブロック x 1 , x 2 , x 3 ... に分割し、 暗号分のブロック y 1 , y 2 , y 3 ... を出力する。 以下では y = e K ( x ) は 64 ビットの平文 x の鍵 K による暗号化 y を表す。

ECB (=electronic codebook) モード

最も簡単なモードで、鍵 K を固定して、各 y i を次で定める

y i = e K ( x i )


OFB (=output feedback) モード

64 ビットの初期ベクトル V を与え、

z 0 = V,    z i = e K (e i - 1 )   (i = 1, 2, 3, .. )

によって鍵 (あるいは鍵ストリーム) z 1 , z 2 , ... を生成し、 y i を次で定める。

y i = x i  XOR z i


CFB (=cipher feedback) モード

64 ビットの初期ベクトル V を与え、y i を次で定める。

y 0 = V,   y 1 = x 1  XOR e K ( y 0 ),   y 2 = x 2  XOR e K ( y 1 ), ...


他の対称暗号

暗号ソフトして有名な PGP で使用することができる対称暗号は 3 重 DES (triple DES) 以外に、 CAST, IDEA がありますが、 それ以外にも簡単に情報が得られるものを 2, 3 挙げると

CAST

CAST は NIST の次期の標準 AES (= Advanced Encription Standard) の候補の一つにあげられているものです。 詳しくは

AES Development effort
を参照してください。その中の AES Candidate Algorithms に CAST の詳しい説明があります。 (読むためには Acrobat Reader が必要です。) あるいは
The Block Cipher Lounge - AES
も参考になります。

RC2, RC4, RC5, RC6

RC2, RC4, RC5, RC6 は Ron Rivest が RSA データ セキューリティー社のためにデザインした ものです。各々仕組みが違うようですが、RC は Rivest's cipher (あるいは Ron's code) の頭文字のようです。RC6 は RC5 の改良版です。 RC5 に関しては RSA データセキューリティー社の FTP サーバー

ftp://ftp.rsa.com/pub/
から資料を手に入れることができ、RC6 に関しては
http://www.rsa.com/rsalabs/aes/
から資料を手に入れることができます。RC6 も AES の候補の一つです。 上で挙げた
The Block Cipher Lounge - AES
も参考になります。

IDEA (International Data Encription Algorithm)

IDEA は Ascom 社 (スイス) がパテントを保有していますが、

IDEA Algorithm
に簡単な絵の説明があります。また Ascom 社の Free Downloads のページ
Free Downloads
には関連した各種の資料があり、IDEA の C のソースコードまであります。

4. 公開鍵 (public key) 暗号

冒頭にも説明したように、公開鍵暗号とは暗号化の方式 f から解読の方式 f - 1 を事実上計算することができないような暗号方式のことで、 そのため暗号化の鍵を公開しても支障がないものです。 このような暗号は意識して使用することもありますが、 計算機のパスワードなどの暗号化などユーザが意識せずに使用することもあります。 公開鍵暗号は Diffie-Hellman の方式が始まりですが、 計算機のパスワードの暗号化、インターネットコマースなどで普及するきっかけを あたえたのは RSA です、そこで RSA の解説から始めることにしましょう。 (RSA の名前は開発者 Rivest, Shamir, Adleman の 3 人の頭文字をとって付けたものです。)

RSA 暗号

B が A に秘密の通信を送ることを考える。

RSA 暗号

  1. A は最初に次をする。
    • 非常に桁数の大きい 2 つの素数 p, q を用意し、m = pq とおく。
    • φ(m)=(p-1)(q-1) と互いに素な整数 s > 0 を与え、次の式を満たす t を計算する。

      st ≡ 1  mod φ(m)

    このあとで A は m, s を公開する。これが A の公開鍵である。

  2. B は送信文を数列

    a 1 , a 2 , a 3 , ...   ( 0 ≦ a i ＜ m )

    とみなして、次の式から b 1 , b 2 , b 3 , ... を計算する。

    b i ≡ (a i )s  mod m,    ( 0 ≦ i ＜ m,   i = 1, 2, ...)

    b 1 b 2 b 3 ... が暗号文である。これを A に送信する。

  3. 受信した A は (b i ) t を m で割った余りを計算する。

    a i ≡(b i )t  mod m

    であるから、もとの文面が復元される。


RSA の基礎になっていることは、上の条件の下で、次の写像が互いに逆写像であることである。


f : Z/pqZ --> Z/pqZ ( x  mod pq ---> xs  mod pq )
f - 1 : Z/pqZ --> Z/pqZ ( x  mod pq ---> xt  mod pq )

この証明には, 初等整数論の知識が必要である。f から f - 1 を決定するには s と積 m = pq は公表されているから

st ≡ 1 mod (p-1)(q-1)

によって t が求めるだけでよい, このためには p, q をそれぞれ求める必要があり、 pq の素因子分解が必要となる。 ところが素因子分解は桁数が増えると事実上不可能となるため, 十分大きな桁の素数を選ぶだけで f が一方向関数となるのである。
RSA 社 と懸賞金

RSA の開発者は 1982 年 RSA データ・セキュリティ社を創設し, そのホームページ

RSA Data Security
からは関連する色々な情報を手に入れることができます。とりわけ RSA 研究所の FAQ (RSA Laboratories' Frequently Asked Questions) は随分有益です。またページの下の方の
http://www.rsa.com/html/licensees.html
などには、現在 RSA にライセンス料を支払っている企業の名前が 列挙してあり、どれほど浸透しているかを示しています。

RSA の仕組は非常に簡単で, そのためかどうか知りませんが, 1977 年 Rivest, Shamir, Adleman が RSA 暗号を発見した直後に 129 桁の数 (積 pq) と暗号文を公開し, 100 ドルの懸賞金をかけたことが文献 1 に載っています。 賞金はそれに必要とされる労力に比べれば, 非常に微々たるものですが, RSA が非常にセンセーショナルだったため, 米国国防省の介入やら (文献 1 の訳者ノート), 暗号を解くための素因子分解法の改良やら, 既存の数論を暗号論に役立てる試みが世に氾濫することになりました。

1991 年 RSA 社は自社の暗号解読に懸賞金をつけました。 これによって, 暗号解読の技術と理論の発展の最先端レベルを知ることができ, 都合が悪くなれば RSA 暗号の桁を大きくすればよいだけだからです (しかし, 根底から覆る可能性は否定されているわけではありません)。

RSA の研究所
の
challenge
に説明があり, 懸賞問題は e-mail で送ってくれるそうです。 問題の形式は 100 桁, 110 桁, ... ごとに一個づつの数が与えられ, それぞれ RSA-100, RSA-110,.. と呼ばれています。
懸賞金は 三箇月毎に決められ, 該当者がなければ, 次回に上積みされます。 現在までの経過 も記載されていて, それによると

numbermonth MIPS-yearsalgolithm
RSA-100 April 1991 7 quadratic sieve
RSA-110 April 1992 75 quadratic sieve
RSA-120 June 1993 830 quadratic sieve
RSA-129 April 1994 5000 quadratic sieve
RSA-130 April 1996 500 generalized
number field
sieve
RSA-140 February 1999 2000 general number
field sieve

とのことです。

離散対数問題 -- Diffie-Hellman の鍵交換

整数 n, x > 0 が非常に大きい場合でも、任意の b を 固定すれば

bx  mod n

の計算は比較的簡単である。しかし、仮に y が 適当な整数 x によって

y ≡ b x  mod n

の形をしていることがわかっても x を求めることは簡単であろうか ? x はいわば b を底とした y の対数

x = log b y

であるから、問題は b を底とした y の対数を求めることが簡単であろうかということになる。 このため、この問題は『離散対数問題』とよばれる。 用語を正確にしておこう:

定義

有限群 G の元 b を固定する。G の元 y が b の累乗のとき、 b を底とした y の離散対数 (discrete logarithm) とは

bx = y

を満たす (任意の) 整数のことである。
 

特別な場合を除いては一般には離散対数問題は非常に困難であることが経験的に 知られている。いかに述べる Diffie-Hllman の鍵交換は、この離散対数問題の 困難さを利用したものである。 なお Diffie-Hellman では鍵の交換しか できないが、たとえば 3 重 DES などの秘密暗号方式と併用すれば、完全な公開暗号 になる。

Diffie-Hellman の鍵交換

素数 p に対して (Z/pZ)×  においては離散対数問題が手に負えないものとし、 mod p の原始根 g を固定する ( g の位数がなるべく大きな素数で割りきれれば 十分である )。
  1. A は秘密の整数 a を選び、

    g a   mod p

    を公開する。 B も秘密の b を選び、 ｇ b mod p  を公開する。

  2. A は g b と a から

    g ab ≡ (g b ) a   mod p

    を計算できる。B も同様に g ab を計算できる。 g ab mod p が A, B に共通な鍵となる。


g a と g b から g ab を決定する問題 を Diffie-Hellman の問題という。第 3 者が秘密の鍵を知ろうとすれば、 Diffie-Hellman の問題を解く必要がある。 Diffie-Hellman の問題と離散対数問題は同等の問題であろうとされているが、 実際に証明されているわけではない。

ElGamal 暗号

Diffie-Hellman の鍵交換を少し修正すれば別の公開鍵暗号ができる。

ElGamal 暗号

素数 p に対して (Z/pZ)×  においては離散対数問題が手に負えないものとし、 mod p の原始根 g を固定する (g の位数がなるべく大きな素数で割りきれれば 十分である)。 p, g はだれもが知っている数とする。ここで B が A に秘密の手紙を 送ることを考える。
  1. A は秘密の整数 a を選び

    α≡g a   mod p   (0＜α＜p)

    を公開する。(α が A の公開鍵である。)

  2. B は乱数 k を選んで、平文 x (0＜x＜p) を次のように暗号化する。

    e K : (x, k) ---> (y 1 , y 2 ) = (g k , xαk )   (どちらも mod p)

  3. A は a を知っているため、次のようにして解読ができる。

    d K : (y 1 , y 2 ) ---> y 2 ( y 1) -a


次の等式から、ちゃんと解読ができことに注意しよう。

y 2 ( y 1) -a ≡ (xα k )((g k) a ) - 1 ≡ x  mod p

楕円曲線暗号

ElGamal 暗号は離散対数問題が困難であるすべての群で そのまま実現できる (但し平文を群の要素に対応させなければならない という制約がある)。 このような群としてすぐに思いつくものに

などがある。最初の方は群の要素の表記上のことが問題となりそうである。 2 番目の方に関しても暗号の場合に話題となるのは 主に mod p の楕円曲線である。

簡単に楕円曲線の解説をしよう。mod p の楕円曲線の話の前に実数体上の 楕円曲線の説明をする方がわかりやすい。楕円曲線 E とは


y 2 = f ( x )    ( f ( x ) は重根を持っていない 3 次式 )

で与えられる 3 次曲線に『無限遠点』と呼ばれる特別な点 O を付けたものである:


E = { (x, y) | x, y は実数、 y 2 = f ( x ) } ∪ O

変数変換をして


y 2 = x 3 + ax + b    ( 4 a 3 + 27 b 2 ≠ 0)

の形にすることができる (カッコ内の式は重根を持っていない条件である)。 重要な点は E には次のようにして 2 項演算 (加法) を定義できることである。

楕円曲線上の 2 項演算

E 上の 2 点 P = ( x 1 , y 1 ), Q = ( x 2 , y 2 ) に対して
  1. (x 1 , y 1 ) ＝ (x 2 , y 2 ) であれば   P + Q = O
  2. (x 1 , y 1 ) ≠ (x 2 , y 2 ) であれば   P + Q = R、 但し R = (x 3 , y 3 ) は次で定める。
    • (x 3 , y 3 ) = (λ2 - x 1 - x 2 ,  λ( x 1 - x 2 ) - y 1 )
    • P ≠ Q のとき λ = ( y 2 - y 1 )/( x 2 - x 1 )
    • P ＝ Q のとき λ = ( ( 3 x 1 )2 + a )/( 2 y 1 )

2 項演算を図示すると次のようになっている。P, Q を通る直線と E との第 3 の交点の x 軸に対称な 点が R である。

以上の演算で楕円曲線がアーベル群となることを確かめることができ (結合法則のチェックだけは非常に面倒)、単位元が O, E 上の点 P = (x, y) の逆元は (x, -y) となる。

mod p の有限体上の楕円曲線は、 整数 a, b に対して


4 a 3 + 27 b 2 ≠ 0 mod p

のときに y 2 ≡ x 3 + a x + b mod p で定義できると考えてよい。但し 3 次式の処理に際して、 2 や 3 で割る必要があるため素数 p は


p ＞ 3

の条件をつける。 楕円曲線の 2 項演算の定義式が文字式 (有理式) であるため、 実数の場合にアーベル群であることを確かめていれば、mod p の有限体の場合に、 あえて別に確かめる必要はない。

例えば mod 11 の楕円曲線 E : y 2 = x 3 + x + 6 の上の点は次で与えられる。

x x 3 + x + 6  mod 11平方数 y
0 6 ×  
1 8 ×  
2 5 〇 4, 7
3 3 〇 5, 6
4 8 ×  
5 4 〇 2, 9
6 8 ×  
7 4 〇 2, 9
8 9 〇 3, 8
9 7 ×  
10 4 〇 2, 9

従って E 上には (無限遠点を含めて) 全部で 13 個の点があるが、13 は 素数であるから E は巡回群である。

さて楕円曲線による暗号を説明しよう。ElGamal の方法をそのまま適用すると 若干不都合なことがあるが、次のようにすると話が単純になる。

Menezes-Vanstone の楕円曲線暗号

p を素数 (＞3) とし、簡単のため Fp = Z/pZ とおく。 E を Fp 上定義された (あるいは mod p の) 楕円曲線とする。 E が巡回部分群 H を含み H においては離散対数問題が手に負えないものとする。 H の生成元を g とし、E, p, g はすべて公開されているものとする。ここで B が A に 秘密の手紙を送ることを考える。
  1. A は秘密の整数 a を選び (E 上の点) ag (の座標) を公開する。 (ag が A の公開鍵である。なお ag は O など特別な点であってはならない。)

  2. B は秘密の乱数 k を選んで、平文

    x ＝ ( x 1 , x 2 )   (0 ＜ x i ＜p,   Fp の元とみなす)

    を次のように暗号化する。

    e K : ( x, k ) ---> ( y 0 , y 1 , y 2 )

    但し y 0 ＝ kg  ( E 上の点 ) で、 y 1 , y 2 は次で定める。

    • k( ag ) ＝ ( c 1 , c 2 )   ( c 1 , c 2 ≠ 0  mod p,  こうでなければ k を選び直す )
    • y 1 ≡ c 1 x 1  mod p,    y 2 ≡ c 2 x 2  mod p

  3. A は a を知っているため、

    ay 0 ＝ a ( kg ) ＝ ( c 1 , c 2 )

    によって c 1 , c 2 (共に Fp の元) を計算でき、従って

    x i ≡ ( c i ) - 1 y i   mod p    (i ＝ 1, 2)

    によって平文 ( x 1 , x 2 ) を復活できる。


5. デジタル署名

デジタル署名は短い文章に署名する方式である。 (長い文章に署名するときには後述するハッシュ関数を使ってメッセージダイジェスト に署名する。) 典型的なものから話をしよう。

RSA 署名方式

今 Alice が

『自分 (Alice) の銀行口座から 100 ドルおろすことを Bob に許可する。』
という文書に署名することを考える。RSA 署名方式では RSA 暗号と基本的に 同じことをする。

RSA 署名方式

Alice は RSA 公開鍵を用意する :
  1. 非常に桁数の大きい互いに相異なる素数 p, q を与え、その積 m を計算し、
  2. st ≡ 1 mod φ(m)  を満たす s, t を与える。
(m, s) が Alice の公開鍵である。暗号化

e K : x ----> x s  mod m

は誰もが実行できるが、解読

d K : x ---> x t   mod m

は Alice しかできない。そこで Alice は自分が署名すべき文書 x (0 < x < m) に対して、

sig K = d K : x ---> y = x t   mod m

によって署名する。 組 (x, y) が署名された文書である。署名の確認は

x ≡ y s   mod m

によって行う。(x から y の計算は Alice しかできなかったことを思い出そう。)
 

ElGamal 署名方式

RSA は公開鍵暗号方式と署名方式のどちらにも用いることができるが、 ElGamal 署名方式は署名専用である。

ElGamal 署名方式

Alice が文書 x に署名するために、ElGamal 暗号方式の公開鍵を用意する :
  1. 素数 p に対して、(Z/pZ)× においては離散対数問題が 手に負えないものとし、mod p の原始根 g を固定する。 (原始根でなくても、位数が十分大きな素数で割りきれればよい。) p, g は公開されている数である。

  2. Alice は秘密の整数 a を選び

    α ≡ g a   mod p   ( 0 < α < p )

    を計算し α を公開する ( α が Alice の公開鍵である。)

Alice は文書 x ( 0 < x < p ) に対して、秘密の乱数 k を選ぶ ( k は p - 1 と互いに素でなければならない。こうでなければ k を選び直す)。 そして

sig K : ( x, k ) ---> (γ, δ)

によって署名する。但し

γ ≡ g k   mod p
δ ≡ ( x - aγ ) k - 1  mod ( p - 1 )

( x, γ, δ) が署名された文書で、次の式で署名の確認をする。

αγ γδ ≡ γ mod p


署名の確認をチェックしてみると


αγ γδ ≡ ( g a ) γ( g k ) δ  mod p
  ≡ g aγ + kδ mod p
  ≡ g x  mod p
  ≡ γ mod p

となり確かによい。

DSS (Degital Signature Standard -- デジタル署名標準)

DSS (Degital Signature Standard --- デジタル署名標準) は DES と同様に (国防などの目的以外の) アメリカ連邦政府の標準を決めるものです。 DSS の規格は FIPS PUB 186-1 に詳細が記載されており、NIST の FIPS ホームページ

FIPS HOME
で直接文書を読むことができます。 DSS は 1991 年に最初に提案され、1994 年に標準として採用されています。 これも DES などと同様に数年おきに再検討されており、上で挙げた文書 FIPS PUB 186-1 は再検討後のものです。1991 年に提案された時点では、 デジタル署名標準としては 以下に述べる DSA (= Degital Signature Algorithm) が採択されていましたが、 この決定にはかなり異論があったようで、RSA 社の FTP サーバ
ftp://ftp.rsa.com/pub/
で、今だに 1991 年の DSS に対しての RSA 社の抗議文 (NIST.DSS.response ) を読むことができます。 しかし今回の再検討に際しては DSA を使用してもよいし、 RSA を使用してもよい、と書かれています。 1999 年 3 月の時点では日本 RSA のホーム頁
日本 RSA
には次のような記事が掲載されていました。
......米国商務省がRSA社のデジタル署名技術を認可し、米国標準 規格（ANSI） X9.31にRSA社のデジタル署名技術を取り入れるための改訂を米国連邦デジタ ル署名標準(FIPS 186-1)に許可した......
DSS の選択肢に RSA も入ることになりましたが、 FIPS PUB 186-1 ではもっぱら DSA の説明に本文を使っており、 ここでも簡単に説明を加えることにします (英文を読める人は原文を読む方を勧めます)。

DSA は ElGamal 署名方式の改良版である。 ElGamal 署名方式の問題点は、素数 p が仮に L ビットあれば、 署名が 2 L ビットになる点である。 デジタル署名の適用例にはスマートカードのようなものも 考えられ、署名はなるべく短い方がよい。DSA は ElGamal 署名方式を補整して、 L ビットの素数 p を使って 160 ビットのメッセージに 320 ビットの署名を 付けるものである。

ElGamal 署名方式において、q を p - 1 を割り切る素数とし、g を mod p で位数 q の 元とする。 ElGamal 署名方式の δ の定め方を


δ≡ ( x + a γ) k - 1   mod ( p - 1 )

とすれば署名の確認の式は


g x αγ ≡ γδ mod p

となる。g, α, γ はすべて g の累乗であるから、位数は q の約数 ( 1 or q ) である。仮に δ が q と互いに素であれば δ は mod q で逆元を持ち、上の式は 次と同値である。


      g x δ-1 αγδ-1 ≡ γ mod p     (*)

g xδ-1, αγδ-1 の 値は xδ-1 mod q,  γδ-1 mod q のみにしか依存しない。また式 (*) は g xδ-1 αγδ-1 を p で割った剰余と γ を p で割った剰余が一致していることを意味するから、 γ を mod q で計算しておけば


( (g x δ-1 αγδ-1 ) mod p) mod q ＝ γ

が成立することになる ( mod q は最小の正の剰余の意味で使っている)。 以上が DSS の仕組である。より正確に説明すると

DSA

Alice が文書に署名することを考える。
  1. p は素数で次の条件を満たす。

    2 L - 1 ＜ p ＜ 2 L ,    512 ≦ L ≦ 1024,  L は 64 で割りきれる

  2. q は p - 1 の素因子で、  2 159 ＜ q ＜ 2 160
  3. g (0 ＜ g ＜ p) は mod p で位数が q の元。
  4. 整数 a は 0 ＜ a ＜ q を満たす乱数 (あるいは疑似乱数)
  5. α = g a  mod p とおく。α は公開鍵である。
以上の条件の下で Alice は文書 x ( 0 < x < q ) に対して、 秘密の乱数 k を選び ( k は q - 1と互いに素でなければならない。 そうでなければ k を選び直す)、

sig K : (x, k) ---> (γ,δ)

によって署名する。但し

γ ≡ g k   mod q
δ ≡ ( x - aγ) k - 1   mod (q - 1)

(x, γ, δ) が署名された文書で、署名の確認は次の式でする。

(( gxδ-1 αγδ-1)  mod p ) mod q ＝ γ


6. ハッシュ関数 (Hash Function)

今まで登場したデジタル署名方式では非常に小さな文章にしか署名することが できない。 (DSS の場合であれば 160 ビットのメッセージに 320 ビットの 署名が付けられた。)

一般にはもっと長い文章に署名する必要がある。 例えば 160 ビットごとに分割して、各々に署名してもよさそうに思えるが、 この場合には

  1. 署名が大きくなりすぎる (本文の 2 倍の大きさ)
  2. デジタル署名のアルゴリズムが複雑なため、全体では計算量が膨大なものになる。
  3. 文章の各々の部分に署名した場合には適当にならべ変えられて全体では まったく違った意味にされてしまうことがある。
このような問題は非常に高速な『公開ハッシュ関数』を使うことによって、 解決される。 ハッシュとは細切れ料理の意味であるが、暗号理論においてはハッシュ関数とは メッセージダイジェスト (これがつまりハッシュ) を作る関数のことで、DSS の場合には長い文章から 160 ビットのメッセージダイジェストを作成する関数である。

DSS の場合の署名方式
メッセージ x任意長
  ↓ 
メッセージダイジェスト z = h(x) 160 ビット
  ↓ 
署名  y = sig K (z)  320 ビット

衝突のないハッシュ関数

署名の安全正を低下させないためにはハッシュ関数 h はいくつかの性質を 満たす必要がある。

正当な署名入りの文書 (x, z) が与えられたとしよう (但し y = sig K ( h( x ) ) )。 もしも仮に h( x' ) = h( x ) となる文書 x' を見つけることができれば、 このとき偽造文書

( x', y )

を作成することができる。これはあってはならない。そこで

定義

h をハッシュ関数、x をメッセージとする。

x' ≠ x,    h( x' ) = h( x )

となる文書 x' を見つけることが計算量的に不可能であるときに、 ハッシュ関数 h は文書 x に対して弱い意味で衝突がない ( weakly collision free ) という。
 

仮に相異なる文書 x', x があって、

h( x' ) ＝ h( x )

となることがあれば、文書 x に署名させてしまえば、 偽造文書 ( x', y ) ができあがる。

定義

ハッシュ関数 h に対して

h( x' ) ＝ h( x )

となる相異なる文書 x', x をみつけることが計算量的に不可能であるときに h は 強い意味で衝突がない ( strongly collision free ) と いう。
 

要するにハッシュ関数は衝突がないように作る必要があるのである。

SHA (Secure Hash Algorithm)

ハッシュ関数として有名なものの一つに 1990 年に Rivest によって 発表された MD4 があり、これは翌年 MD5 として強化された。 MD5 は 1996 年に弱点があることが見付かっている。 MD4, MD5 に関しては RSA 社の FTP サーバ ftp://ftp.rsa.com/pub/ に資料があります。

一方 1992 年に同じ原理に基づいて (あるいは MD5 の修正版を)、 NSA (= National Secrurity Agency) は NIST (= Natinal Institute of Standards and Technology) のために標準的なハッシュ関数

安全ハッシュ標準 (SHS = Secure Hash Standard)
を公表し、1993 年公式にアメリカ連邦政府の (国防目的以外の) 標準として採用された。 この修正版が 1994 年に公表され、その中のアルゴリズムは
安全ハッシュアルゴリズム (SHA = Secure Hash Algorightm)
と呼ばれた。更に 1995 年に修正版 SHA-1 が公表され、これが 現在に至るまでの NIST の推奨する標準となっている。 NIST による SHA-1 の規格を定めた文書 FIPS PUB 180-1 (= Federal Information Standard Publication 180-1) はインターネットの
FIP180-1
で読むことができる。(非常に読みやすく書かれている。)

この文書に沿って SHA-1 の概要を説明することにしよう。 SHA-1 は長さが 2 64 より小さなビット列から 160 ビットの メッセージダイジェストを作成するためのハッシュ関数である。 若干の用語と注意が必要となる :


  • (32 ビット) ワードは長さが 32 のビット列で

    c 1 ... c 8    ( c i は 16 進数 )
    a 1 ... a 4    (a i は 2 桁の 16 進数、あるいは 0 ≦ a i ＜ 256)

    のような表示ができる。

  • 32 ビットの整数 n ( 0 ≦ n ＜ 2 32 ) はワードで表示できるが、 計算機によって内部表示の方法が違っている。たとえば

    a 1 a 2 a 3 a 4    ( 0 ≦ a i ＜ 256)

    の表示する整数は

    • big-endian 構造 (Sun SPARCstation など) では

      a 1 2 24 + a 2 2 16 + a 3 x 8 + a 4

    • little-endian 構造 (Intel 80xxxx など) では

      a 1 + a 2 x 8 + a 3 2 16 + a 4 2 24

    である。 SHA-1 では数値の内部表示が big-endian であることを 前提にする (従って little-endian の場合には若干補正が必要となる)。

  • ブロックとは長さ 512 のビット列のことで 16 個のワードの列の ことである。

  • 32 ビットワード X, Y に対して

    X ∨ Y X と Y のビットごとの論理積 (AND)
    X ∧ Y X と Y のビットごとの論理和 (OR)
    X ＾ Y X と Y のビットごとの排他的論理和 (XOR)
    〜X X の補数 (NOT)
    X + Y mod 2 32 の整数の加算
    S n (X) X の n 桁左巡回シフト ( 0 ≦ n ＜ 32 )
    ( i.e. S n (X)= ( (X<<n) OR (X>>32-n) )

    以上の演算が極めて高速に実行できるという点を注意する。


SHA-1 では最初に次のようにしてメッセージの長さが 512 の倍数になるようにする。

Step 1. もとのメッセージをビット列とみなしたときに直後にビット 1 を付け加え
Step 2. その後ろにビット 0 を幾つか付け加えビット列の長さが 512 の倍数になるようにする。
Step 3. 但し、最期の 2 ワードには、 もとのメッセージのビット列としての長さ L を 64 ビット整数として 書き込む。

実例を挙げて説明する方がわかりやすいであろう :

実例

もとのメッセージのビット列が 


01100001 01100010 01100011 01100100 01100101 

( 16 進では 61626364 65 )

のとき ( 40 ビット、L = 40 )、Step 1 でこれは 


01100001 01100010 01100011 01100100 01100101 1

(0を 7 個付け加えると 16 進では 61626364 658 )

になり、L = 40 を 2 ワードで 16 進表現すると 00000000 00000028 であるから 


61626364 65800000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000000 
00000000 00000000 00000000 00000028

となる。
 

SHA-1 では 80 個の関数 f 0 , f 1 , ... , f 79 が 使用される。各 f t ( 0 ≦ t ≦ 79 ) は 3 個の 32 ビットワード B, C, D に対して、 一個の 32 ビットワード f t ( B, C, D ) を対応させる。具体的には

f t ( B, C, D ) = (B ∧ C) ∨ ((〜B)∧ D) ( 0 ≦ t ≦ 19)
B ＾ C ＾ D (20 ≦ t ≦ 39)
(B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D) (40 ≦ t ≦ 59)
B ＾ C ＾ D (60 ≦ t ≦ 79)

SHA-1 では 80 個のワード定数 K t ( 0 ≦ t ≦ 79 ) が使用される。 16 進表示では

K t = 5A827999   ( 0 ≦ t ≦ 19)
6ED9EBA1 (20 ≦ t ≦ 39)
8F1BBCDC (40 ≦ t ≦ 59)
CA62C1D6 (60 ≦ t ≦ 79)

メッセージは先にも述べた方法で長さが 512 の倍数になるように調節し、 これをブロック M 1 , M 2 , ... , M n に分割する (ブロック = 512 ビット = 16 ワード)。 メッセージダイジェストを作成するためには各ブロック M i に 80 ステップからなる処理をほどこす必要があるが、その前に 次のバッファ (一時記憶) が必要となる。

A, B, C, D, E 5 個の 32 ビットバッファ
H 0 , H 1 , H 2 , H 3 , H 4 5 個の 32 ビットバッファ
W 0 , W 1 , ..., W 79 80 個の 32 ビットバッファ
TEMP 一時記憶用の 32 ビットバッファ

処理を開始する前に H 0 , H 1 , H 2 , H 3 , H 4 を次のように初期化する。

H 0 = 67452301
H 1 = EFCDAB89
H 2 = 98BADCFE
H 3 = 10325476
H 4 = C3D2E1F0

以上で準備ができた。各ブロック M i を次のように処理をする。


  1. M i を 16 個のワード W 0 , W 1 , ..., W 15 に分割する。
  2. for t = 16 to 79 let

    W t = S 1 ( W t - 3 ＾ W t-8 ＾ W t - 14 ＾ W t - 16 )

  3. Let A = H 0 , B = H 1 , C = H 2 , D = H 3 , E = H 4
  4. for t = 0 to 79 do

    TEMP = S 5 ( A ) + f t ( B, C, D ) + E + W t + K t ;
    E = D;   D = C;   C = S 30 ( B );  B = A;   A = TEMP;

  5. Let H 0 = H 0 + A,   H 1 = H 1 + B,   H 2 = H 2 + C,   H 3 = H 3 + D,   H 4 = H 4 + E
M n の処理を負えたときの 5 個のワード H 0 H 1 H 2 H 3 H 4 で表示される長さ 160 のビット列が メッセージダイジェストである。
 

7. 各種アルゴリズム

DSS (Digital Signature Standard) を定めている FIPS PUB 186-1 では付録に 各種のアルゴリズムを載せています。 2,3 紹介することにします。

素数の確率的判定法

DSS の規格を定めた FIPS PUB 186-1 には付録が付いており、 各種のアルゴリズムを紹介しています。 紹介されている確率的素数の判定法は Miller-Rabin の判定法です。 これは例えば

に紹介されています。FIPS PUB 186-1 ではアルゴリズムを次のように書いています。 (ループは n 回繰り返され、1 / 4 n の確率で素数でない可能性が ありますが、 n≧50 であれば実用に差し支えありません。)

Miller-Rabin の素数判定法

Step 1.  i = 1,  n を 50 以上とする。

Step 2.  w を素数判定したい整数とし、w を次のように書く

w = 1 + 2 s m    (m 奇数)

Step 3.  1 < b < w  を満たす乱整数を生成する。

Step 4.  j = 0,  z = b m  mod w とおく。

Step 5. 『 j = 0, z = 1 』  もしくは  『 z = w - 1 』  ならば Step 9 へ

Step 6.  『 j > 0, z = 1 』  ならば Step 8 へ

Step 7.  j = j + 1  とおく。
      j < a であれば z = z 2  mod w とおき Step 5 へ

Step 8.  w は素数でない。アルゴリズムの停止

Step 9.  『 i < n 』 であれば i = i + 1 とおき Step 3 へ。
      そうでなければ w は多分 (確率的に) 素数である。
 

関連して少し紹介すると

強擬素数

w を奇数とし、  w - 1 = 2 s m   とおき、 w と互いに素な b ( 0 ＜ b ＜ w ) を選ぶ。 このとき次の 1 もしくは 2 のいずれかが成立して、しかも w が合成数の時、 w を b を底とする強擬素数という。
  1.   b m ≡ 1   mod w
  2.   b 2 r m ≡-1  mod w を満たす r ( 0 ≦ r ＜ s ) が存在する。

b を色々選んで、w が常に b を底とする強擬素数であれば、w が素数である確率が 高くなるわけです。これが Miller-Rabin の素数判定法の背景です。 証明はかなり難しいのでここでは省略します。

疑似乱数

線型合同法のような乱数生成器は計算機シミュレーションなどには 有効であっても、暗号理論で使用するための方法ではない (規則性がすぐわかるためである)。

DSS (Digital Signature Standard) を定めている FIPS PUB 186-1 では

SHA (Secure Hash Algorithm)
を使用して、各種の乱数を生成する方法を与えている。

DSA における素数 p, q の生成

DSA (Digital Signature Algorithm) では次の条件を満たす任意の素数 p, q を生成しておく必要がある。

  1.   2 159 ＜ q ＜ 2 160
  2.   2 L - 1 ＜ p ＜ 2 L ,   L = 512 + 64 j  ( 0 ≦ j ≦ 8 )
  3.   q は p - 1 を割り切る
そこで次の方針で p, q を生成する。 SHA-1 を使用してシード (seed, 種) から乱数を生成して、 2 159 ＜ q ＜ 2 160 を満たす素数 q を構成する。 これがうまく行けば再び同じシードから 2 L - 1 ＜ X ＜ 2 L を 満たす整数 X を構成する。X をまるめて X ≡ 1  mod 2q を 満たすように選び、更に素数になる場合を探す。これが p である。

具体的なアルゴリズムを述べる前に表記上の注意を述べる。

8. 雑多なことなど

RSA 研究所の FAQ には e コマースに関してのリンクが紹介されています。 参考までに付け加えておきます。(RSA Laboratories FAQ は RSA 社のホーム頁から手に入れることができます。)