図? 暗号の考え方
2006年06月16日
コンピュータリテラシ
筑波大学 電子・情報工学系
コンピュータサイエンス専攻
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/literacy-2006/2006-06-16
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/
http://www.gnu.org/
(http://www.gnu.org/home.ja.html)
Emacs, gcc, Gimp, bash
http://www.mozilla.org/
Firefox, Thunderbird
http://www.x.org/,
http://www.x.org/,
http://www.xfree86.org/, X11
http://www.openssh.org/,
http://www.jp.openbsd.org/openssh/ja/, ssh
http://www.isc.org/ BIND (DNS server), INN (news server)
http://www.apache.org/, Apache (Web Server)
http://sourceforge.net/
http://sourceforge.jp/
ネットワークには、次のものを含めて考える
暗号とは、情報の意味が当事者以外にはわからないように情報を変
換することである。
図? 暗号の考え方
暗号化の方法が秘密になっていると、一見、より強そうにみえる。しかし、そ の暗号が、強いのか弱いのか調べる方法がない。攻撃すると、簡単に落ちるか もしれない。暗号化の方法を提供している者が信頼できない時には使えない。
鍵を長くするだけで、安全性が指数関数的に高くなる。
鍵を１ビット長くすると、解読時間が２倍になる。
（「鍵の長さを２倍にすると解読時間が２倍になる」は、誤り）。
図? 指数関数 図? 指数関数
パスワードは、コンピュータの中では、暗号化の鍵として使われる。 長いパスワードは、破られにくい。１文字(大文字小文字数字記号)増やすと、 総当たりで解読に要する時間が、５０倍から１００倍近くかかるようになる。
暗号の方法は、大きく２つに分類される
例
図? 共通鍵暗号系による暗号通信
Caesar暗号は、知れている最後の暗号である。 平文アルファベットをＮ文字ずらした暗号文アルファベットに変える。
N=2 の時の対応表
abcdefghijklmnopqrstuvwxyz CDEFGHIJKLMNOPQRSTUVWXYZAB暗号の説明では、平文を小文字で、暗号文を大文字で書く習慣がある。
N=13 で、大文字小文字を保存する方法を、rot13 暗号という。rot13 は、電 子メールやネットワーク・ニュースで「ネタばらし」の部分を書く時に使われ る。
漢字の場合、rot47 という方法がある。nkf -r で、rot13/47 が使える。
数の集合から、無作為抽出で抜き出された数。
真性乱数。ビット列にすると、０と１の発生確率がそれぞれ１／２で、各ビッ トは他の部分と独立(ｉｉｄ（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
乱数表そのものや、大きな乱数表の中でどこから使い始めるかを鍵にすること
ができる。
真性乱数を使うと、解読する方法は数学的に存在しないことが証明されている。
しかし、真性乱数を使うことはコストが大きい。 送信側と受信側で同じ真性乱数を作るのが大変である。
乱数表を記憶する変わりに、疑似乱数を使う方法がある。使う疑似乱数の性質 が悪いと簡単に解読される。
実際には、文字をずらすのではなく、足し算、引き算や、排他的論理和と呼ば れる計算が使われることが多い。
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）のデータを暗号化するため の標準である。ＤＥＳを一般の商用にも使うことを推奨している。 たとえば、Unixのパスワード・ファイルは、ＤＥＳにより暗号 化されている。
ＤＥＳは、対称暗号系（慣用暗号系）の１つであり、暗号化と復号 化に同一の鍵（５６ビット）を用いる。ＤＥＳは、転時暗号の一種 である。転時暗号では、平文の文字の順序（コンピュータでは、ビッ ト）を入れ替えるものである。ＤＥＳでは、６４ビットの平文につ いて、鍵をもとにビットの入れ替えを１６段繰り返す。
DES は、Unix のパスワードのハッシュ関数として使われている。
アメリカ NIST (National Institute of Standards and Technology) が 定めたDES に変わる新しい標準。 全世界に対して公募され、ベルギーのJoan Daemen とVincent Rijmenにより開発されたRijndael方式が採用された。鍵の長さは、 128ビット、192ビット、256ビットから選べる。
チェックサムや CRC (Cyclic Redundancy Check) にも似ているが、暗号やディ ジタル署名で使われるのは、Collision Proof 性が求められる。
one_way_function( x )
{
return x をキーとして 0 を暗号化したもの ;
}
Unix の /etc/passwd や Apache の
htpasswd で遣われているものは、DES を25回繰り返して使って
作ったハッシュ関数の結果。パスワードそのものは、保存されてない。
公開鍵暗号系（非対称暗号系）では２つの異なる鍵を用いる。 便宜上、この２つを公開鍵と秘密鍵と呼ぶ。
これらの鍵は、互いに相手の逆関数になっている。
図? 公開鍵暗号を使った暗号通信の手順
ここで、公開鍵から秘密鍵を計算することは難しい。ある平文を公開鍵で暗号 化してみたところで、秘密鍵を得ることは難しい。
公開鍵暗号の利点は、鍵を管理する手間が掛らないこと。
ＲＳＡ暗号は、Rivest, Shamir, Adleman の３人によって開発され た公開鍵暗号系である。ＲＳＡ暗号の安全性は、大きな数を素因数 分解することの難しさに基づく。北米では、ＲＳＡは、２０００年 に特許が切れた。
公開鍵に基づく暗号化の１つの方法。買得の難しさは、楕円曲線上の離散対数 問題を解くのと同程度と言われている。RSA よりも鍵が短くて高速である。
認証とは、情報の正当性や完全性を確保する技術である。
図? man-in-the-middle攻撃
ディジタル署名では、通常の署名と同様に、次のような性質が必要である。
公開鍵暗号系を使ってディジタル署名を行うことができる。
図? 公開鍵暗号を使ったディジタル署名の手順
メッセージ全体を暗号化する代わりに、メッセージを平文で送り、それにメッ セージを一方向関数（ハッシュ関数）と呼ばれる方法で計算した結果だけを、 秘密鍵で暗号化したものを送る方法もある。一方向関数では、計算結果から元 の値（メッセージ）を計算することが難しい。
ディジタル署名や利用者認証は、公開鍵暗号系ではなく、共通鍵暗号系を用い ても可能である。ただし、この場合、鍵を管理する信用できる管理センターが 必要となる。
サーバへのログインを例に、これを説明する。
単なる暗証番号の場合、通信を傍受されたら終り。 毎回違う数を使えば、傍受されていても平気。
鍵がが本物であるかをどうやって確認するか。
サーバは、２つの鍵と６４ビットの乱数を送る。 クライアントは、乱数を送り返す。 乱数が一致したら、IP spoofing されていない。
クライアントは、セッション鍵（対称暗号系の鍵）をサーバの２つの公開鍵で 暗号化して送る。
対象暗号の鍵（セッション鍵）を生成し、公開鍵で送る。
これ以降の通信は、セッション鍵で暗号化される。
個人ごとに公開鍵での認証機能を利用したほうがよい。
ssh (scp, WinSCP, Tera Term, PuTTY含む) で始めてあるホストに接続する時 には、警告が現れる。
ssh コマンド
% ssh ホスト名 -l ユーザ名PuTTYThe authenticity of host 'ホスト名 (IPアドレス)' can't be established. RSA key fingerprint is 16進数32桁. Are you sure you want to continue connecting (yes/no)? yes Warning: Permanently added 'ホスト名 (IPアドレス)' (RSA) to the list of known hosts. ホスト名%
The server's host key is not cached in the registry. You have no guarantee that the server is the computer you think it is. The server's rsa2 key fingerprint is ssh-rsa 1024 16進数32桁 If you trust this host, hit Yes to add the key to PuTTY's cache and carry on connecting. If you wan to carry on connecting just once, without adding the key to the cache, hit No. If you do not trust this host, hit Cancel to abandon the connection.
この 16進数32桁 の数は、接続先のホストの公開鍵を、ハッ
シュ関数 MD5 にかけた結果である。この32桁の数を目で確認することにより、
接続先のホストが正しい(
man-in-the-middle攻撃が
行われていない)ことがわかる。
目で確かめる時には、次のものと比較する(2006年6月2日現在。変更される可能 性もある)。
87:4d:e0:31:da:77:a7:7e:f0:c6:83:4c:e3:28:18:06
d8:b2:bd:32:c0:9d:80:16:dc:40:7e:73:03:25:4f:b9
よくつかわれるもの。
% cat bin/ssh-coins-mail![[]](../icons/screen-cursor.gif)
自分自身(localhostが便利)のポート番号10143, 10110, 10025 に来た接続要
求を、リモートの host の143, 110, 25 に転送する。ssh の接続先(最後の
$host)と、-L で指定するホストは必ずしも一致していなくてもよい。
ssh コマンドは、Unix、MacOSX、Cygwin で使える。Windows の TeraTerm や
PuTTY でも使える。
図 ssh によるトンネリング(SMTP)
SSH2 を使った方がよい。
RSA社が提唱している公開鍵を使ってセッション鍵（秘密鍵）を交換する 方式(PKCS1 1.5 )そのものに、脆弱性がある [1]。
PKCS -- Public-Key Cryptography Standards
[1] Daniel Bleichenbacher, "Chosen ciphertext attacks on RSA encryption standard PKCS #1", Advances in Cryptology, CRYPTO 98. Springer.
サーバ鍵を１時間に１回しか変えない。
SSH 1.5 は、1024 ビットの鍵を使っている。 これを破るには、2 20 + 2 19 回接続でよい。毎 秒、約 400 回。
１個所からの接続に上限を付ける。OpenSSH はそうなっている。 Distributed 攻撃には、弱そう。
OpenSSH
http://www.openssh.org/
準備
利用
Unix のパスワードを利用する方法と比較した時の利点
認証には、証明書が使われる。 鍵の交換には、証明書に含まれている
X.509 形式(バイナリ)を、テキストに変換したものの例:
Certificate:
Data:
Version: 3 (0x2)
Serial Number: 225985 (0x372c1)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=US, O=Equifax Secure Inc., CN=Equifax Secure Global eBusiness CA-1
Validity
Not Before: Mar 13 03:01:02 2006 GMT
Not After : Mar 13 03:01:02 2010 GMT
Subject: C=JP, O=www.coins.tsukuba.ac.jp, OU=businessprofile.geotrust.com/get.jsp?GT22591421, OU=See www.rapidssl.com/cps (c)05, OU=Domain Control Validated - RapidSSL(R), CN=www.coins.tsukuba.ac.jp
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit):
00:c8:11:30:5b:af:05:2a:22:9d:2a:4e:1d:b7:00:
5c:96:70:b4:c3:c1:6d:30:50:d2:5e:1e:0e:87:83:
df:5e:b1:ea:c0:98:d8:c5:cd:51:0c:34:3f:74:06:
0c:31:e5:9d:5d:b2:cc:b7:e5:2d:d4:c1:33:a0:bc:
21:3c:f3:d0:fb:0e:36:95:7f:37:59:1a:41:c3:84:
9b:12:3b:6f:39:70:ac:25:b4:4b:30:f6:fa:31:5f:
36:64:fd:56:d6:70:60:21:3a:51:0f:39:f8:42:95:
09:36:f9:fb:73:db:e7:34:59:c4:96:fa:fa:24:5e:
10:af:bc:a9:55:9d:7b:78:9d
Exponent: 65537 (0x10001)
X509v3 extensions:
X509v3 Key Usage: critical
Digital Signature, Non Repudiation, Key Encipherment, Data Encipherment
X509v3 Subject Key Identifier:
DD:FA:B7:F1:41:4A:49:4D:31:BE:87:A1:4A:56:5D:2A:76:CF:E6:E4
X509v3 CRL Distribution Points:
URI:http://crl.geotrust.com/crls/globalca1.crl
X509v3 Authority Key Identifier:
keyid:BE:A8:A0:74:72:50:6B:44:B7:C9:23:D8:FB:A8:FF:B3:57:6B:68:6C
X509v3 Extended Key Usage:
TLS Web Server Authentication, TLS Web Client Authentication
X509v3 Basic Constraints: critical
CA:FALSE
Signature Algorithm: md5WithRSAEncryption
56:1c:4a:f7:e7:a6:16:b0:6d:ed:cf:0c:c9:60:5b:3d:bc:43:
a5:62:06:13:75:ec:6d:7c:b7:75:cc:0d:f3:02:8f:af:74:90:
0f:69:8e:28:cc:e5:f8:7f:a2:5d:61:b1:fb:63:3b:31:83:15:
da:11:c7:ea:62:b2:c9:ad:2e:26:4e:a0:fc:44:a1:16:90:11:
79:7e:06:c8:23:63:59:7c:09:5f:5b:76:8f:f5:e2:27:66:9c:
ac:de:ee:49:ee:ea:8b:8c:60:b5:cf:00:52:0b:9b:fa:be:5e:
c2:8c:02:79:cd:55:c1:d9:04:8c:d1:e4:f7:bc:44:95:80:a7:
4d:3b
証明書がついていたとして、それが本物であるかをどうやって確認するか。
認証局(CA, Certificate Authority)に、証明書を発行してもらう。(認証局の 秘密鍵でディジタル署名をしてもらう)
その認証局は、信頼できるか？
ＷＷＷブラウザには、ルート認証局の証明書が予め含まれている。
末端のＷＷＷサイトは、ルート認証局、または、中間認証局から発行された証 明書を提示する。
接続時に、乱数(共通鍵暗号に基づく暗号化の鍵を生成するため)を交換する。 その乱数は、普通、サーバ側が提示した証明書に含まれている公開鍵で暗号化 される。
ハンドシェークで使われる公開鍵暗号系
データを暗号化するために使われる共通鍵暗号系
Web ブラウザは、証明書を検査できない時には、次のような警告を表示する。
図? Firefox による man-in-the-middle攻撃の可能性の通知
一般的には、このような Web サイトには接続すべきではない。
~/Library/Keychains/login.keychain
「キーチェーンアクセス.app」のパスワードとログインの時に打つパスワード を同じにしていると、自動的に機密データの暗号を解いてアプリケーションに 渡す機能がある。注意すべきことは、ログイン・パスワードを変更しても、 「キーチェーンアクセス.app」のパスワードは変更されないことである。 活用するには、ログイン・パスワードを変更したら、 「キーチェーンアクセス.app」のパスワードも変更するとよい。
何も使っていなければ、「キーチェーンアクセス.app」のパスワードは、初期 パスワードのままになっている。重要な情報を保存していなければ、上記のファ イルを削除し、ログインしなおすことで、リセットするとよい。
次のような MacOSX のアプリケーションが、「キーチェーンアクセス.app」を 使って機密情報を暗号化して保存している。
対象
Firefox
Safari
Firefox
ssh-keygen コマンドを使って、公開鍵と秘密鍵の組を生成しなさい。鍵の種類
としては、rsa 、または、dsa を使うとよい。生成に成功すると、標準では、
~/.ssh というディレクトリの下に、２つのファイルが作られる。
ssh でログインする時に、生成した鍵の組を使って認証を行いなさい。 それには、クライアント側に秘密鍵を置き、サーバ側の ~/.ssh/authorized_keys (OpenSSHの場合)に、公開鍵を設定すればよい。 接続時には、秘密鍵を暗号化するために使ったパス レーズを打つ込む。(通常の通常のログインのパスワードを打つことはない。)
coins 内で実験する時には、クライアントもサーバも同じ ~/.ssh を参照する。 したがって、authorized_keys を作成するには、次のようにする(どちらか一方 をやる。両方やってはならない。)。
rsaの場合:
% cd ~/.sshdsaの場合:
% cd ~/.ssh
authorized_keys を作成する前には、ssh で接続する時に次のように 「パスワード Password 」が聞かれる。
% ssh azalea20authorized_keys を作成した後には、ssh で接続する時に次のように 「パスフレーズ passphrase」が聞かれる。
% ssh azalea20これに対して、ssh-keygen でパスフレーズを打ち込む。(公開鍵による認証に 失敗すると、通常のパスワードによる認証に落ちるのが一般的である。システ ムによっては、認証方式に制限を加えていることがある。)
coins% ssh IPEのログイン名@icho.ipe.tsukuba.ac.jpicho に ~/.ssh/authorized_keys を作成した、icho への ssh による接続 (scp も含む) は、公開鍵による認証方法が利用可能になる。
% ssh-agent tcshssh-agent にコマンド(上の例ではtcsh)を与える代りに、csh の環境変数を設 定させるコマンドを出力させ、eval で実行する方法もある。
% eval `ssh-agent`ただし、この方法ではログアウトした時に ssh-agent のプロセスが残ること がある。そうならないように ログアウト時に実行させるプログ ラムで殺す(ssh-agent -k)ようにする。
% ssh -L lport:rhost:rport rhost-L に与える rhost のホスト名としては、localhost (127.0.0.1) もよく使わ れる。まったく別のホストでもかまわない。
% ssh -L lport:rhost2:rport rhost1ただし、rhost1 と rhost2 の間の通信は、暗号化されないことに注意しなさ い。
急に電源が落ちた時などには、ハードディスクの状態が「ファイル」や「ディ レクトリ」としては正常にアクセスできなくなることがある。「ディスクユー ティリティ.app」は、このような時に不整合を修復する 機能がある。コンピュータの電源を入れた時に自動的に実行されることもある。
「ディスクユーティリティ.app」を使うと、１つの大きなファイルを、１個の ハードディスクのように扱うことができる。このように、ディスクに見立てる ことができるデータのことを「ディスク・イメージ」という。「ディスクユー ティリティ.app」を使うと、ディスク・イメージをファイルに保存することが でき、また、ファイルに保存されたディスク・イメージを、「マウント」とい う操作を行い、通常のアプリケーションからファイルとディレクトリの集合と してアクセス可能にする。
MacOSX では、ディスク・イメージを含むファイルの拡張子は、「.dmg」である。
自分で CD-R や DVD-R にファイルを保存する時には、まず、 「ディスクユーティリティ.app」を使って ディスク・イメージをファイルに保存する方法が一般的である。
次のような操作を行いなさい。
% open /Applications/Utilities/Disk\ Utility.app「新規イメージ」ボタン、または、「ファイル」メニューから「空のディスク イメージ」を選択し、ディスク・イメージを作成する。名前と場所（ディレク トリ（フォルダ））、サイズ、暗号化するかどうか、フォーマットを選択し、 「作成」ボタンを押す。
% ls /Volumes/
MacOSX の「ディスクユーティリティ.app (Disk Utility.app) 」を 使って、暗号化されたディスク・イメージを作成しなさい。 暗号化の方式としては、AES が使われることを確認しなさい。
MacOSX の「ディスクユーティリティ.app (Disk Utility.app) 」は、 ディスク・イメージを暗号化する時のパスワードを、
(1) 情報学類の SSL 付きのページを見る時、暗号やディジタル書名について、 どのような技術が使われているか。このページで説明されている範囲で３つ選 んで説明しなさい。
(2) ssh-agent を使って、パスフレーズなしに icho にログインできるように しなさい(加点)。
ssh-add -l コマンドの結果、および、ssh コマンドによる icho への接続の様 子、および、icho における次のコマンドの結果を、シェルのプロンプトや打ち 込んだコマンドを含めてレポートに張りなさい。
(3) 暗号化されていないディスク・イメージと暗号化されてたディスク・イメー ジの２つを作成し、次のようにして暗号化の効果を確認しなさい(加点)。
% strings ディスクイメージを含むファイル | egrep 文字列ここで「
文字列」には、1 でコピーしたテキスト・ファイル
の内容を指定する。コマンドラインからは漢字を打つことが難しいので、
「文字列」には、ASCIIによる簡単なものを指定しなさい。