2−4 暗号化アルゴリズム


暗号アルゴリズムには共通鍵暗号アルゴリズム(対称鍵)と公開鍵暗号アルゴリズム(非対称鍵)がある。共通鍵方式は任意の長さのメッセージの暗号化のみに用いられるが、公開鍵方式は短いメッセージの暗号化、電子署名、鍵交換など各種の異なった目的に使われる。共通鍵暗号方式にはブロック暗号化とストリーム暗号化の方式がある。

共通鍵方式

公開鍵方式 共通鍵暗号のアルゴリズム(ブロック暗号化方式)

3-Way

Joan Daemenの開発した96ビットブロック暗号で、96ビットの鍵サイズをもつ。nラウンド(11ラウンドを推奨)の繰り返しを行うが、DESとは異なりFiestel Networkを持たない。この暗号化方式はハードウェアで効率的な暗号化を行えるように設計された。

AES (Advanced Encryption Standard)

時代遅れになったDESに代わって次世代の共通鍵方式の暗号アルゴリズムの標準を定めようとNIST(米情報標準技術局)のプログラムがスタートしている。1998年6月までに候補となるアルゴリズムの公募が行われている。

Blowfish

Bruce Schneierが開発した方式。32〜448ビットの可変のサイズの鍵を持ち、64ビットのブロック暗号化方式をとる。特許なし、ライセンスなしでフリーに使える。
http://www.informatik.uni-mannheim.de/~rweis/rgp/blowfish/blowfish.html

以下のサイトにソースコード、ドキュメントがある。
ftp://ftp.ox.ac.uk/pub/crypto/misc/

CAST128

Entrust Technologies社(Northern Telecomのグループ会社)のCarlisle AdamsとStafford Travarsesの開発した64ビット・ブロック暗号化方式で鍵が1〜128ビットまで可変である。12〜16段のラウンドを持ちDESに似た暗号アルゴリズムを用いている。このアルゴリズムは特許になっているが、その使用はフリーになっており、RFC 2144として公開されている。PGP 5.0ではCASTがデフォルトで使われている。
http://info.internet.isi.edu/in-notes/rfc/files/rfc2144.txt

CRAB

RSA社のBart KalinskiとMatt Robshawの開発したブロック暗号化の方法で、1024ビットと大きなブロックサイズを持ち、80ビットの鍵を使う。この方式はMD5のハッシュ関数を暗号化に使い、高速な処理を狙ったものである。この方式は実用に用いるというより新しい方法の可能性を検討する実験的なものである。

DES (Data Encryption Standard)

DESはIBMの開発した暗号方式をベースにして、1977年に米NBS(後のNIST)が標準化した共通鍵方式である。DESは最も広く知られ使われている暗号アルゴリズムである。DESは56ビットの暗号鍵を使い(実際の鍵の長さは8バイトの64ビットを必要とする、各バイトに鍵とは無関係な1ビットのパリティを付けているので実質の鍵の長さは56ビットとなる)、64ビットのブロック暗号化方式をとっている。1つのブロックの暗号化は16段のラウンドをとってスクランブルを行っている。各ラウンドではS-boxという非線型要素を導入した変換を行っている。

FIPS PUB 46-2 ~ Data Encryption Standard (DES), 1993 December 30.
http://www.nist.gov/itl/div897/pubs/fip46-2.htm

Triple DES

1つの平文ブロックの暗号化をDESのアルゴリズムを3回通す。3つの異なる共通鍵(Key1、Key2、key3)を用いる(E-E-E)方式と、2つの共通鍵(Key1、Key2)を使ってDESを3回通す(E-D-E)方式がある。後者はKey1でDESの暗号を行い、その結果をKey2で復号し、さらにKey1で再暗号化を行う。受信した暗号文の復号はこの逆をとる。DESのアルゴリズムをそのまま使い、暗号の強度を増す方法として使われる。この暗号方式の実質的な暗号の強度は80ビット程度の鍵に相当するという。最近は56ビット鍵のDESの弱さが指摘されているのでTriple DESの使用が薦められている。E-D-E方式はANSIでバンキングの標準になっておおり、米金融界ではこのTriple DESを使うようにしている。

FEAL-N (First Encryption Algorithm - N)

NTTで開発した共通鍵方式の暗号アルゴリズム。Nはラウンド数を表しており、N=4,8,16,32などがある。64ビット鍵を使う64ビットのブロック暗号化方式。DESより高速処理が出来るという。しかし、オリジナルのFEAL-4は高々20の平文暗号解析で解けることが分かり、またFEAL-8も2**25の選択平文での線形解読法で解けることが示されている。FEAL-Nは少ないラウンド数では安全ではないとされる。

FEAL-NX (First Encryption Algorithm - NX)

NTTで開発した共通鍵方式のブロック暗号アルゴリズム。FEAL-Nの弱点を改良するために128ビットの鍵を使う方式。

GOST

旧ソ連の政府が開発したブロック方式の暗号。64ビットブロック暗号化方式で256ビットの鍵サイズで32ラウンドを持つ。

IDEA (International Data Encryption Algorithm)

Xuejia LaiとJames Masseyによって設計された、64ビットの共通鍵方式のブロック暗号化方式で、128ビットの鍵を用いる。 8ラウンドのスクランブルを行っている。IDEAはPGPで使われている。
http://www.ascom.ch/Web/systec/security/main.htm

RC2

RSA Data Security Inc.で開発された共通鍵方式のブロック暗号化方式で64ビットの平文の入力ブロックから64ビットの暗号文を生成する。可変サイズの暗号鍵が使えるのが特徴である。この暗号化の方式は16ビットオペレーションに最適化したアルゴリズムでDESより2倍の高速化が可能であるという。最近RSA社はこのアルゴリズムをインターネットRFCとするためにIETFにドラフトを提出した(97/6)。RC2はRon*s Cipher #2を表している(RonはRon Rivest)。

RC5

RSA社のRCシリーズの暗号方式で1995年に提案されたもの。可変長ブロックサイズと可変長の鍵サイズ、さらに可変長回数のラウンドを持つブロック暗号化方式である。ブロックサイズは32、64、128ビットがとれる。ラウンド数は0から255、鍵サイズは0から2048ビットまで可変である。この方式はシンプルであるが強固なもので差分解読や線形解読に強いといわれる。

The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms
ftp://ftp.rsa.com/pub/rc5/rfc2040.txt

MULTI2

日立の開発した共通鍵方式のブロック暗号アルゴリズム。MULTI2はアルゴリズムを公開しているが、その他MULTI4など公開していないアルゴリズムもある。日本のディジタル放送の暗号化の標準として使われている。

MYSTY

三菱電気の松井充の開発した共通鍵方式のブロック暗号アルゴリズム。DESを解読できる線形解読法では解けないことを証明している。処理速度もDESに比べて速い。128ビット鍵を使う。同社の情報携帯端末に使われている。

SAFER (Secure And Fast Encryption Routine)

Cylink CorporationのMasseyが1993年に公表したブロック暗号方式で特許にしていないアルゴリズム。64ビットのブロックで64ビットの鍵(K-64)と128ビットの鍵(K-128)のバージョンがある。バイト処理が可能なアルゴリズムをとっており可変長のラウンド(10ラウンドまで)が使える。最近差分暗号解析や線形暗号解析では解けないとするSK-64やSK-128が提案されている。

SKIPJACK

NSAで開発された共通鍵方式で、64ビットのブロック方式で80ビットの鍵を使い、32回のスクランブル(ラウンド)をとる。DESよりセキュリティが強化されたものと言われる。アルゴリズムの詳細は公表されていない。このアルゴリズムのソフトウェアの実装はなくClipper Chipに埋め込まれている。このClipper Chipには米政府によってキーエスクロー(鍵の預託)が埋め込まれており、政府がこれを一定の制限の元に開けることが出来ることになっている。また第3の落とし戸が更に隠されているのではないかとも疑われており、多くの人はこれは安全でないと考えている。

FIPS 185 - (EES), Escrowed Encryption Standard
http://www.nist.gov/itl/div897/pubs/fip185.htm
 

共通鍵暗号のアルゴリズム(ストリーム暗号化方式)

A5

GSM(Global Standard Mobile)方式のディジタル携帯電話の秘話機能として導入したストリーム暗号。3つの異なる長さ(19、22、23)のLFSRを使いそれを合成して用いる。強度は高くないが(40ビットの暗号に相当)効率がよい。

CRYPT(1)

オリジナルのUNIXのストリーム暗号アルゴリズム。これは第2次世界大戦でドイツが使った暗号器(Enigma)と同様な方法を取っている。これは簡単に破ることが出来て、パブリック・ドメインのツールがCrypt Breakers Workbench(CBW)にある。

GCC (Gao's Chaos Cryptosystem)

株式会社 国際情報科学研究所が開発したGCCカオス暗号法:カオス理論により乱数を発生させる共通鍵&ストリーム型暗号方式。マルチメディアデータなど同じパターンの平文が続く場合でも異なる暗号文が生成でき、高速な処理が出来るという。可変長キー(1〜256ビット)方式をとっている。特許出願番号:特願平6-148645
http://www.iisi.co.jp/

LFSR暗号

LFSR (Linear Feedback Shift Resister)が生成する擬似乱数と平文を排他ORして作る暗号法。多くはハードウェアで実現するLFSRを使う。暗号学的な特性を持つ数学上のアルゴリズムに基く簡単なロジックでLFSRが出来て、多くのバリエーションがある。解読を困難にするために非線型的要素を導入して実際の暗号文を作る。実用的な強度を持つ暗号をソフトウェアのLSFRで作ろうとすると、ロジックは極めて簡単であるが、ソフトウェアのシフトレジスタの処理コストが重く、DESなどのブロック暗号方式より遅くなる。

RC4

RC4は可変長の鍵サイズを持つバイト処理方式のストリーム暗号である。アルゴリズムは鍵の生成にランダムな置換を行いその周期は10**100と極めて長い。1バイトの処理を行うのに8から16マシンオペレーションですむので高速な処理が可能で、DESより10倍以上高速に処理できる。

RC4はRSA社プロプライエトリーな技術で暗号アルゴリズムは公開されていないことになっていたが、1994年に誰かがインターネットのメーリングリストにソースコードを流した。これが直ちにUsenetのニュースに流れ、現在、世界中のFTPサイトに公開されている。

SEAL

SEALはIBMのRogaway等が設計したストリーム暗号で、32ビットコンピュータに最適化して、ソフトウェアで効率の良い実装が可能である。ソフトウェアによるストリーム暗号としては極めて高速な処理ができる。これは擬似乱数発生器に基くもので、160ビットの鍵と32ビットの値を基にして64Kバイトまでの擬似乱数を発生する。これは、また擬似乱数発生器としての用途にも用いられる。

ブロック暗号化のモード

ECB (Electronic Code Book Mode)

電子コードブック・モード:平文をブロック毎に処理した暗号ブロックを単純に連結して暗号文を作る方式。この方法だと平文のブロックの同じパターンに対して暗号文のブロックに同じパターンが生じることになり、暗号解読の手段に使われる恐れがある。このモードはそれぞれのブロックが独立しているので、短文のメッセージの暗号化に使われることが多い。長い実際の文書の暗号化には実用上はこの方法は使われず、CBCが使われる。

CBC (Cipher Block Chaining Mode)

暗号ブロック連鎖モード:1つ前の暗号化したブロックと暗号化対象の現在の平文のブロックとの排他ORをとってから暗号化鍵でこのブロックの暗号化を行う。結果の暗号文は次のブロックとの排他ORに使われる。このように前のブロックと次々に連鎖させて暗号文を作る。ブロックの最初はその前のブロックがないので初期ベクトル(IV:Initial Vector)を与えて排他ORをとる。このようにすることでECBのように、平文のブロックに同じパターンがあっても暗号文には同じパターンを生じないので、暗号解読を困難にさせることが出来る。復号はこの逆の手法をとる。実用に使われる文書の暗号化はこのCBCが多く用いられる。ただしこの方法は前のブロックの通信の過程でビットエラーが生じるとこのエラーが次々と次のブロックにエラーを波及させてしまう欠点を持っている。

OFB (Output Feed Back)

アウトプット・フィードバック・モード:OFBはECBの欠点である統計的な類推(平文の同じビットパターンで暗号文の同じビットパターンを生成する)の可能性を防ぐとともに、CBCで問題となるエラービットの波及を防ぐ。はじめにブロック長と同じ長さの初期ベクトルをブロック暗号方法で暗号化し第1乱数ブロックを作る、この乱数ブロックと平文のブロックとの排他ORをとったものが暗号文の第1ブロックとなる。次に第1乱数ブロックを次のブロック暗号の入力にフィードバックし、第2乱数ブロックを作る。これと平文の第2ブロックの排他ORをとって暗号文の第2ブロックをつくる。この操作を繰り返す。OFBでは初期ベクトルは同じ鍵を使う場合は異なったものを使わなければならない。OFBでは乱数ブロックを作るのにブロック暗号化を使うが、送信する暗号文は乱数列と平文の排他ORをとるストリーム暗号法となる。ブロックサイズが短いと同じ乱数ブロックを生成する確率が高くなり、解読にヒントを与えることになる。64ビットのブロックでは約300Gビット毎に繰り返しが現れることになる。この方法は伝走路にエラーの発生が生じる頻度の高いディジタル放送や電話などの音声のスクランブルなどに用いられる。

CFB (Cipher Feedback Mode)

暗号フィードバック・モード:CFBはOFBと非常に似た方法である。違いはOFBでは生成した乱数ブロックを次の乱数ブロックを生成する入力としたが、CFBでは前に生成した暗号文を次の乱数ブロックを作るための入力にする方法をとる。OFBと同様にストリーム暗号となる。

公開鍵暗号のアルゴリズム

El Gamal

大きな数の素因数分解問題が手におえないと同様に、離散対数問題が手におえないという性質を使った公開鍵方式の暗号アルゴリズム。この方式は1つの平文に対して公開鍵を適用すると2つの暗号文が生成され、RSA方式とはかなり異なったものである。この方式は電文の暗号化にも使えるが、電子署名のために使われることが多い。オリジナルのElGamal方式を修正し、鍵の長さを短縮したものがNISTの標準としての電子署名DSSに使われている。

ECC (Elliptic Curve Cipher)

楕円曲線暗号: Neal koblitzとMillerが1985年に独立に提案した方式で、離散対数暗号方式に楕円曲線の点のグループを適用させた方式。公開鍵方式で、電文の暗号化、電子署名、鍵交換の目的に使える。鍵の長さがRSAに比べて1/5〜1/10と短くても強度があり(160ビットのECCの鍵は1024ビットのRSAの鍵と同等といわれる)、今後RSAに代る可能性があると注目されている。選択出来る楕円曲線の群にはE(Fq)とE(F(2**m))がある。この方法は鍵の生成方法が難しいとされるが、近年、効率的なソフトやハードへの実装が行われるようになってきた。カナダのCirticom社がツールや製品を出しており1歩進んでいるが、松下電気の宮地充子の開発した方式も有名になっているという。

最近(97/6)HPのSmart等がこの楕円曲線の特別なグループに致命的な欠陥が存在することを見つけた。これで、楕円暗号として各種標準として提案されているものは見直しが余儀なくされた。

Diffie-Hellman

通信する両者の間で、法指数の計算法を使って生成した公開情報を交換し、互いが持つ秘密情報と合わせて共通鍵を生成する方法。この方法は公開鍵をメッセージの暗号化に使うのではなく共通鍵暗号で使う鍵を安全でない通信路を使って互いに生成するために用いられる。1976年に発表された考え方は従来の暗号の概念を大きく変え、続くRSAなどの画期的な公開鍵暗号の火蓋を切ることになった。

この方法には重大な欠陥があって、もし通信するAとBの両者の中間に鍵交換の手順を盗聴できるXが存在すると、AとBからの公開情報を盗聴者は自分の公開情報にすり替えることでAとBの間で送信される暗号文を解読でき、AとBはまったく盗聴されたことを気づかないという中間者攻撃が可能になる。この中間者攻撃を避ける方法はDiffie-Hellman key exchange with authenticationの項を見よ。

Merkle-Hellman napsack

ナップサック暗号系として、Merkle-Hellmanの方法のバリエーションが多く発表された。これは部分和判定問題と言われるNP-完全問題の1つで、この問題を解く多項式時間アルゴリズムが知られていないことを使った数学的にエレガントな方法であるが、Merkle-Hellman法は1980年代にShamirによって整数計画法を使って解かれ、その他のバリエーションも次々に解かれることになった。

Rabin

素因数分解が困難であることに基く公開鍵暗号方式。2つの素数(p,q)を秘密の鍵とし、その積(n)を公開鍵とし、暗号化は法nでのメッセージの2乗を暗号文とする。

RSA

RSAはMITのRivest、Shamir、Adlemanが1978年に開発した公開鍵方式。最も有名で最も普及している公開鍵暗号アルゴリズムであり、短い電文の暗号化や電子署名に用いられる。RSAは公開鍵方式としてMITが特許を持っており、RSA社ライセンスを供与している。RSA方式は2つの大きな素数(256ビット以上)の積で作った数が素因数に分解するのが極めて困難であるという性質を使って公開鍵と秘密鍵を作り、公開鍵で暗号化した暗号文は秘密鍵でしか復号できない。このことを使って、AがBに暗号文を送信する場合、Bの公開鍵で暗号化したものをBに送り、Bは受信した暗号文をBの秘密鍵で平文にする。

RSA方式は、この手順を逆に使うことで電子署名にも使われる。すなわち、Aの秘密鍵で作った暗号文はBに配ったAの公開鍵しか開けられないために、Bは確かにAが作成した文書であることを確認できる。この性質が電子署名として使われる。

この方式はDESなどの共通鍵方式に比べて1000倍以上もコストがかかるので長文の暗号化には使われず、DESなどの共通鍵の配布や電子署名などの短い文の暗号に用いられる。以下のURLにRSAについての優れたFAQがある。
http://www.rsa.com/rsalabs/newfaq/

日本語版が以下にある
http://www.rsa-japan.co.jp/faq/index.html

その他の暗号方式

量子暗号(Quantum Cipher)

量子力学の不確定性原理によると量子の観測を行えば量子の状態は変ってしまう。この事を使って光子の転送において途中に盗聴者がいた場合光子の偏向面が変化してしまうことで盗聴の存在を知ることが出来る。この方式で通常の共通鍵の交換に使おうとする方法でIBMなどで試作機が作られた。

以上SIS(セコム情報システム)ホームページのネットワークセキュリティ読本を参照。