図? 暗号の考え方
分散システム
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/dsys-2000/2000-02-13
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html
認証に使う。分散システムでは物理的な位置が使えない。
暗号が使われてきたグループ４つ
暗号とは、情報の意味が当事者以外にはわからないように情報を変
換することである。
図? 暗号の考え方
暗号化の方法が秘密になっていると、一見、より強そうにみえる。しかし、そ の暗号が、強いのか弱いのか調べる方法がない
暗号の安全性は、鍵の安全性によっている。 鍵の管理が非常に重要となる。
暗号化のプログラムを作成した人でも、鍵を知らなければ平文を得ることがで きない。
鍵を長くするだけで、安全性が指数関数的に高くなる。
鍵を１ビット長くすると、解読時間が２倍になる。
図? 指数関数 図? 指数関数
パスワードは、コンピュータの中では、暗号化の鍵として使われる。 長いパスワードは、破られにくい。１文字(大文字小文字数字記号)増やすと、 総当たりで解読に要する時間が、５０倍から１００倍近くかかるようになる。
暗号の安全にとって、最近のコンピュータの高速化と低下価格下は、 １つの脅威となっている。
SETI (the Search for Extraterrestrial Intelligence)。
暗号の方法は、大きく２つに分類される
Caesar暗号は、知れている最後の暗号である。 平文アルファベットをＮ文字ずらした暗号文アルファベットに変える。
N=2 の時の対応表
abcdefghijklmnopqrstuvwxyz CDEFGHIJKLMNOPQRSTUVWXYZAB暗号の説明では、平文を小文字で、暗号文を大文字で書く習慣がある。 カルタゴ人以来騙された人はいない。
N=13 で、大文字小文字を保存する方法を、rot13 暗号という。rot13 は、電 子メールやネットワーク・ニュースで「ネタばらし」の部分を書く時に使われ る。
コード化されたメッセージを暗号化する。 うまくつかえば、解読が難しくなる。
第２次世界大戦中、アメリカの日本大使館と本国の間の通信では、ローマ字で かかれた日本語が使われていた。それは、すべてアメリカ側に解読されてた。
解読されたという事実がシカゴの新聞に出たのに、日本政府はそれを信用せず、 終戦までそのコードを使い続けた。
真理値表
------------------------ 入力1 入力2 出力 ------------------------ 0 0 0 1 0 1 0 1 1 1 1 0 ------------------------
ＡＮＤ、ＯＲ、ＮＯＴで表わすと次の通り
OR(AND(入力1,NOT(入力2)),AND(NOT(入力1),入力2))
次のような性質がある。
数の集合から、無作為抽出で抜き出された数。
真性乱数。ビット列にすると、０と１の発生確率がそれぞれ１／２で、各ビッ トは他の部分と独立(ｉｉｄ（independent and identically distributed）) である。
物理乱数。量子力学の効果を増幅してディジタル化したもの。 平滑化して０，１のバランスをとれば、真性乱数になる。
疑似乱数(pseudo random number)。種(seed)と呼ばれる入力ビットパタンを基 に計算された、種よりも長いランダムに見えるビット・パタン。種が決まれば 出力乱数は一意に決まる。
例:
乱数表: 0 18 19 22 22 7 9 4 14 3
平文: h e l l o w o r l d
8 5 12 12 15 23 15 18 12 4
暗号文: H W E H K D X V Z G
: 8 23 5 8 11 4 24 22 26 7
乱数表そのものや、大きな乱数表の中でどこから使い始めるかを鍵にすること
ができる。
一度しか乱数列を使わないので、One-time Padとも呼ばれる。
真性乱数を使うと、解読する方法は数学的に存在しないことが証明されている。
しかし、使うのが大変。送信側と受信側で同じ真性乱数を作るのが大変。
乱数表を記憶する変わりに、疑似乱数を使う方法がある。 疑似乱数を使ったものは、他の暗号法と同じく解読される。 使う疑似乱数の性質が悪いと簡単に解読される。
実際には、文字をずらすのではなく、足し算、引き算や、排他的論理和と呼ば れる計算が使われることが多い。
Caesar暗号やバーナム暗号では、平文の文字の順序を変えずに、文字を置き換 える。これを置換暗号という。これにたいして、転置暗号（transposition cipher）では、平文の文字の順序を入れ替えるが、文字の置き換えは行わない。 （下の例では、大文字小文字が変わっているが、これは暗号化の説明のために 変えて書いているだけである。）
次は、転置暗号の１つ、コラム転置の例である。キーは、同じ文字を含まない １個の単語や熟語である。このキーでコラムに番号付けをする。たとえばコラ ム１は、アルファベットで先頭に近い文字の下のコラムとなる。
MEGABUCK -------- 74512836 -------- pleasetr ansferon emillion dollarst omyswiss bankacco untsixtw otwoabcd
平文: pleasetransferonemilliondollarstomyswissbankaccountsixtwotwo 暗号文: AFLLSKSOSELAWAIATOOSSCTCLNMOMANTESILYNTWRNNTSOWDPAEDOBUOERIRICXB
ＤＥＳ（Data Encryption Standard）は、アメリカ商務省標準局 （NBS, National Bureau of Standard, 現在のNIST, National Institute of Standrds and Technology）が１９７７年に定めた暗 号標準である。ＩＢＭ社による提案が元になっている。ＤＥＳは、 アメリカ政府内で、コンピュータ・データのうち、非機密だが取扱 い注意（unclassified but sensitive）のデータを暗号化するため の標準である。ＤＥＳを一般の商用にも使うことを推奨している。 たとえば、ＵＮＩＸのパスワード・ファイルは、ＤＥＳにより暗号 化されている。
ＤＥＳは、対称暗号系（慣用暗号系）の１つであり、暗号化と復号 化に同一の鍵（５６ビット）を用いる。ＤＥＳは、転時暗号の一種 である。転時暗号では、平文の文字の順序（コンピュータでは、ビッ ト）を入れ替えるものである。ＤＥＳでは、６４ビットの平文につ いて、鍵をもとにビットの入れ替えを１６段繰り返す。
アメリカでは、ＤＥＳを取り扱うチップ（ＩＣ）が多く利用されて いる。アメリカは、暗号に関する製品がソフトウェアも含めて輸出 禁止になっており、ＤＥＳチップもその制約を受けている。ＤＥＳ 暗号化を行うソフトウェアについては、アメリカ以外で開発された ものが広くインターネット上で配布されている。
ＤＥＳが作られる時、コンピュータ科学者は、５６ビットのキーの長さでは短 すぎると主張した。ＩＢＭの提案は、１２８ビットだった。安全保証局の要求 で、５６ビットに減らされた。１９８８年にアメリカ連邦政府は、１９８８年 にＤＥＳの効果を保証しないと決定した。
２０００年に次世代の標準、ＡＥＳ(Advanced Encryption Standard)が選定された。
Rijndael
ブロックサイズ:128ビット
キー・サイズ：128, 192, 256ビット。
http://csrc.nist.gov/encryption/aes/
引数から結果を求めるのは簡単だが、結果から引数を求めることは難しい。
y = f(x)
暗号で使われるのは、Collision Proof 性が求められる。
暗号を使えば、一方向関数が作れる。
one_way_function( x )
{
return x をキーとして 0 を暗号化したもの ;
}
Unix の /etc/passwd に保存されているものは、DES を25回繰り返して使って
作った一方向関数の結果。パスワードそのものは、保存されてない。
チェックサムや CRC (Cyclic Redundancy Check) にも似ているが、一方向関 数としての Collision Proof 性が求められる。
元データが壊れていないか（誰かに改ざんされていないか）を調べる時には、 メッセージ・ダイジェストを計算して比較する。
公開鍵暗号系（非対称暗号系）では２つの異なる鍵を用いる。 便宜上、この２つを公開鍵と秘密鍵と呼ぶ。
これらの鍵は、互いに相手の逆関数になっている。
図? 公開鍵暗号を使った暗号通信の手順
ここで、公開鍵から秘密鍵を計算することは難しい。ある平文を公開鍵で暗号 化してみたところで、秘密鍵を得ることは難しい。
公開鍵暗号の利点は、鍵を管理する手間が掛らないこと。
o
ＲＳＡ暗号の安全性は、大きな数を素因数分解することの難しさに基づく。 北米でのＲＳＡの特許は、２０００年で切れた。
ＲＳＡの技術は、Netscape社の SSL でも利用されている。
認証とは、情報の正当性や完全性を確保する技術である。
乱数を送って、秘密鍵で暗号化してもらう。
公開鍵で復号化して、元の乱数が得られたら Ok。
毎回違う数を使えば、傍受されていても平気。
ディジタル署名では、次のようなシステムが必要である。
公開鍵暗号系を使ってディジタル署名を行うことができる。
図? 公開鍵暗号を使ったディジタル署名の手順
メッセージ全体を暗号化する代わりに、メッセージを平文で送り、それにメッ セージを一方向関数（ハッシュ関数）と呼ばれる方法で計算した結果だけを、 秘密鍵で暗号化したものを送る方法もある。一方向関数では、計算結果から元 の値（メッセージ）を計算することが難しい。
ディジタル署名や利用者認証は、公開鍵暗号系ではなく、共通鍵暗号系を用い ても可能である。ただし、この場合、鍵を管理する信用できる管理センターが 必要となる。
もともとRSAのみ。後に、DH/DSS (Diffie-Hellman/Digital Signature Standard)に対応。
データの暗号化は、対称暗号系(DES, 3DES, IDEA, SHA)で行う。その対称暗号 系の鍵の管理に公開鍵を使う。
いいろろなＯＳで使える。
主な利用方法。
アメリカ政府による暗号技術独占に対抗する形で開発が始まった。
アメリカ政府による輸出規制は、1999年に緩和された。
それ以前は、次のような分類があった。
系列
PGP Users Manual for Windows by daasan@anet.ne.jp'
GNU による PGP 互換のソフトウェア。
PGP の機能のうち、特許に触れるもの(IDEAアルゴリズム)を使わない。
http://hp.vector.co.jp/authors/VA019487/
The GNU Privacy Guard講座
http://www.gnupg.org/rfc2440.html
RFC 2440 (html)
http://hp.vector.co.jp/authors/VA019487/openpgp.html
RFC 2440 日本語訳 (html)
IP spoofing (なりすまし).
rsh のセッションで行われるであろうパケットを偽造する。
IP アドレスでホストを認証すると危ない。
DNS spoofing.
偽のDNSのサーバを立てる。
source routing。
サーバは、２つの鍵と６４ビットの乱数を送る。 クライアントは、乱数を送り返す。 乱数が一致したら、IP spoofing されていない。
クライアントは、セッション鍵（対称暗号系の鍵）をサーバの２つの公開鍵で 暗号化して送る。
対象暗号の鍵（セッション鍵）を生成し、公開鍵で送る。
これ以降の通信は、セッション鍵で暗号化される。
個人ごとに RSA 公開鍵での認証機能を利用したほうがよい。
+------------+------------------+------+----------------+----------------+ | パケット長 | 乱数のパディング | 種類 | データ | チェックバイト | +------------+------------------+------+----------------+----------------+パケット長以外が暗号化される。データの圧縮も行われる。
よくつかわれるもの。
ssh -L 10110:remote:110 remote
ローカルのポート番号 10110 に来た要求を、remote の 110 に転送する。
ftp は、使いにくい。
フリーの実現がある。
３種類認証モデル
クライアントは、サーバから証明書を取り寄せる。 その証明書を、予め持っている認証局に問い合わて確認する。
セッション鍵と乱数の交換
セッション鍵と乱数から一方向関数（ハッシュ）で、接続ごとに変わるデータ 暗号化鍵とMACシークレット（乱数）を生成する。
データは、MAC (Message Authentication Code)で保護される。
接続ごとの暗号化鍵が破られただけでは、MACシークレットによりメッセージ の改ざんはできない。
少し前まで、輸出用 WWW ブラウザは、鍵の長さが４０ビットに制限されてい た。今は、128ビットまで使える。
サーバの証明書の値段が、使える鍵の長さで違う。安い４０ビットを使っても 意味はない。
協調して動作しているプログラムの間で、ある一連の作業を識別するための数 を意味する。
RPC、HTTP(WWW)で使われる。
NFS が利用している SunRPC では、UDP/IP実装の制限から最大のメッセージの 長さが決まっている。上限を越えるディレクトリを読み込む場合、１回のRPC で終らない。
nfsproc_readdir() の１回目と２回目の RPC の間にディレクトリの内容が更 新された場合、どのような結果になるのか予想できない。
ＷＷＷ（World Wide Web）では、１回のデータ転送ごとに通信路が切断される ので、通常はＷＷＷのブラウザ（クライアント）とＷＷＷサーバの間では、途 中経過を保持することができない。
途中経過を保存したい時：
ＷＷＷで途中経過を保存するためには、cookie が使われる。
普通のＷＷＷサーバでは、要求を送ってきたコンピュータのＩＰアドレスを記 録しているので、コンピュータ単位でのアクセス状況を記録することはできる が、個人を特定することはできない。
クッキーを利用することにより、コンピュータではなくどの個人がアクセスし てきたかを記録することができる。
クッキーから電子メールのアドレスや氏名まで調べることはできない。 しかし、インターネットをサーフしている間にどこかでそれを打ち込んだが最 後、クッキーと電子メール・アドレスや氏名との対応が記録されてしまう危険 性がある。
参考
Netscape社によるＷＷＷにおけるクッキー実現の案
http://www.netscape.com/newsref/std/cookie_spec.html