暗号化・ハッシュ・エンコーディングの簡単な概要を説明します。
暗号化やエンコーディングされたデータを元に戻すことは復号化ではなく 復号 (decryption, decoding) と呼びます。(平文を暗号に変換するのは暗号化だが、暗号を平文に戻すのは平文化であって復号化ではないので)
暗号化には、共通鍵で暗号化して共通鍵で復号する 共通鍵暗号系(common-key cryptosystem) と、鍵のペア(秘密鍵と公開鍵)を用いて、秘密鍵で暗号化したものを公開鍵で復号、または、公開鍵で暗号化したものを秘密鍵で復号する 公開鍵暗号系(public-key cryptosystem)があります。詳しくは後述します。
あるデータに対して決められたアルゴリズムを適用し、不可逆のデータを作成することを ハッシュ化 と呼びます。また、ハッシュ化されたデータを ハッシュ値 と呼びます。チェックサムのようなものですね。大きなデータであっても、128～512ビット程度の小さなデータにハッシュ化します。ハッシュ値が偶然に同じ値になる(衝突する)可能性はありますが、その確率は128ビット長でも 3.4×1038分の1の確率であり、「実用上十分に小さい」とされています。
ハッシュ値は不可逆なので元のデータに戻すことはできませんが、下記などの目的に使用されます。
例えば、ファイルをダウンロードする際、ダウンロードしたファイルをハッシュ化したハッシュ値と、ダウンロードサイトで公開されているハッシュ値を比較することで、ファイルが正常にダウンロードできていること、ファイルが改竄されていないことをチェックすることができます。
例えば、送信側はデータに秘密の情報を付加したものをハッシュ化してデータとともに送信します。受信側も受け取ったデータをあらかじめ共有しておいた秘密の情報を付加してハッシュ化します。計算したハッシュ値と受け取ったハッシュ値が合致すれば、そのデータは秘密の情報を知っている相手からの受信であることが確認できます。
ユーザのパスワードをDBに保存する場合、パスワードを暗号化したものではなく、パスワードをハッシュ化したものを保存します。ログイン時に送られてきたパスワードを同じアルゴリズムでハッシュ化し、ハッシュ値がDBに保存していたハッシュ値と合致すれば、正しいパスワードが入力されたと判断します。DBデータが流出してもハッシュ値は非可逆なので安全性が高まります。
公開鍵暗号 は大量の計算を必要とするため、大きなデータを公開鍵暗号で暗号化するにはCPUリソースを消費してしまいます。暗号化の目的ではなく、署名 の目的で暗号化する際には、大きなデータをハッシュ化し、そのハッシュ値を公開鍵暗号で暗号化することにより、署名のための計算量を減らすことができます。
ハッシュアルゴリズムには下記などがあります。
128ビットのハッシュ値を作成します。1992年に発表され、UNIX 系システムのパスワードのハッシュ化などに利用されていましたが、解析手法も確立し、現在では通常のコンピュータでも数秒で解読されてしまうため、セキュリティの目的で使用することはなくなりました。チェックサムの目的であればまだ利用されることがあります。
1993年発表の SHA-0 を改良し、1995年に発表されたたもので、160ビットのハッシュ値を生成します。こちらも2011年に解析理論が確立し、実際のハッシュ値衝突例もでてきたことから、現在ではセキュリティの目的で使用することは推奨されなくなってきました。
SHA-1 を改良して 2001年に発表されたもので、生成するビット数によって SHA-224、SHA-256、SHA-384、SHA-512 などの種類があります。よく使用されるのは SHA-256 と SHA-512 です。SHA-224 は 3DES の鍵長の倍数になるように後から追加されました。
# opensslで"ABCDEFG"をSHA256でハッシュ化する例 echo -n "ABCDEFG" | openssl dgst --sha256 # ハッシュ化したものをBASE64で文字列化する例 echo -n "ABCDEFG" | openssl dgst --sha256 --binary | base64
SHA-2 よりも強力なハッシュアルゴリズムとしていくつかのアルゴリズムの中から SHA-3 としての選出が行われ、2015年に公開されましたが、SHA-2 が解析されるようになるのは当分先になりそうなことから、まだあまり利用されていません。
巡回冗長検査と訳されます。生成されるハッシュ値のビット数によって CRC-8, CRC-16, CRC-32, CRC-64 などの種類があります。チェックサムの目的で使用されることがほとんどで、セキュリティの目的で使用されることはありません。
パスワードのハッシュ化には、ソルト(salt) と呼ばれるランダムデータをパスワードと連結してハッシュ化し、ソルトとハッシュ値をDB保存します。例えば、例えば100万件パスワードハッシュ情報が流出してしまった場合、ソルト無しの場合、よく利用されるパスワードをハッシュ化してDB検索することで簡単にユーザIDとパスワードのペアを見つけることができますが、ソルト有りの場合、ソルトとハッシュ値が流出しても1件1件毎にソルト付きでハッシュ計算しなくてはならず、解析のための計算量が増え、安全性が高まります。
パスワードをハッシュ化する際には、ソルトに加えて、ハッシュ値をさらに再度ハッシュ化することを数千～数万回繰り返して行う ストレッチング(stretching) を行います。これにより、ユーザ情報が流出した場合でも、1件1件のデータに対して数千～数万回のハッシュ化計算をしなければならなくなり、解析にかかる時間を増やすことが可能となります。
実際のパスワードのハッシュ化では、昔は MD5 が利用されてきましたが、最近では SHA-512 が、一部のディストリビューションでは bcrypt が使用されています。/etc/shadow ファイルのパスワード部の先頭数文字で、どのアルゴリズムが使用されているかを判断することができます。
$1 ... MD5 $5 ... SHA-256 $6 ... SHA-512 (Ubuntu 21.04 や CentOS 8など) $2a ... bcrypt 2a(Blowfish) (OpenBSD や SUSE Linuxなど)
ハッシュ関数の代わりに Blowfish というブロック暗号を使用します。いくつかのバージョンがあり、現在では 2a というバージョンがよく利用されています。下記は Python の bcrypt 使用例です。引数の 10 は 2の10乗(1024回)のストレッチングを行うことを、2a は bcrypt のバージョンを表しています。生成したハッシュ値の先頭にはバージョン(2a)、ストレッチ強度(10)、ソルト情報(WuEh...YYe)が付加されます。
import bcrypt password = b'my-secret-password' # パスワードのハッシュ値を求める salt = bcrypt.gensalt(10, b'2a') # => b'$2a$10$WuEhN51aj9BPVPIQ1pBYYe' hash = bcrypt.hashpw(password, salt) # => b'$2a$10$WuEhN51aj9BPVPIQ1pBYYeTJ227o8zr2QtechTilyqmayHMkHMIjq' # ハッシュ値とパスワードを検証する check = bcrypt.checkpw(password, hash) # => True
Django や iOS 9 などが採用しているアルゴリズムです。ハッシュ関数として HMAC-SHA1 や HMAC-SHA256 などを選択することができます。ソルトとストレッチ回数を指定します。下記は Python で PBKDF2 のハッシュ値を求めるサンプルです。ストレッチ回数は、2005年時点の推奨値で4,096回。iOS 9 では 10,000回のストレッチングを行っています。
import os
import hashlib
password = b'my-secret-password'
salt = os.urandom(16)
hash = hashlib.pbkdf2_hmac('sha256', password, salt, 100000)
print("hash=%s" % hash)
2015年に開催されたパスワードハッシュ協議会で優勝したアルゴリズムです。Argon2d と Argon2i の二つのバージョンがあります。PBKDF2 などは使用するメモリが少ないため、ASIC や GPU を用いた攻撃に弱い面がありましたが、Argon2 では使用するメモリ量や実行時間をパラメータとして制御することが可能です。デフォルトで 100MB のメモリを使用します。
from argon2 import PasswordHasher
password = b'my-secret-password'
ph = PasswordHasher(time_cost=2, memory_cost=102400)
hash = ph.hash(password)
print("hash=%s" % hash)
共通鍵で暗号化し、同じ共通鍵で復号するものを 共通鍵暗号系(common-key cryptosystem) と呼びます。例えば、クライアントとサーバが同じ共通鍵を保持しておき、クライアントがデータを共通鍵で暗号化したものをサーバに送信、サーバがこれを共通鍵で復号することにより暗号化通信を実現します。秘密鍵暗号系 と呼ばれることもあります。
データを一定サイズのブロックに分割し、ブロック毎に暗号化する方式を ブロック暗号 と呼びます。DES, AES などがあります。これに対してビット、バイトやワード単位で暗号化する方式を ストリーム暗号 と呼びます。RC4 などがあります。ブロック暗号ではブロックサイズ分のデータが溜まるまで暗号化を開始できませんが、ストリーム暗号ではデータを1バイト毎に逐次暗号化してストリーム通信できるのが特徴です。ただし、AES の CTR モードなど、ブロック暗号を用いてストリーム通信することもできるようになってきました。
暗号化には、下記などの情報が必要となります。これらは復号する側と意識を合わせておく必要があります。特に、異なる言語やライブラリで復号する場合は、アルゴリズムは同じものを選んでいても、その他のパラメータがずれているために復号エラーとなるケースがよくあります。
共通鍵暗号のアルゴリズムとしては下記などがあります。最近では AES が主流です。
1976年に米国の連邦情報処理標準(FIPS)として採用したブロック暗号です。64ビットのブロックを 56ビットの鍵で暗号化します。1980～1990年代は標準的に使用されていましたが、現在では暗号化の目的ではあまり使用されていません。
DES を強化する目的で1998年に策定したブロック暗号です。56ビットの鍵を3個(k1, k2, k3)使用し、k1 で暗号化したデータを k2 で復号し、再度 k3 で暗号化します。56×3＝168 ビットの鍵を使用しますが、既知の攻撃手法により実質的な暗号強度は 112ビット程度となります。
米国国立技術研究所(NIST)が1998年に採用したブロック暗号で、現在の主流です。ブロックサイズは 128ビット固定です。鍵長は 128, 192, 256ビットから選択することができ、それぞれ AES-128, AES-192, AES-256 と呼ばれます。最も多く利用されているのは AES-256 で、SSL/TLS, ZIP, 7z, Wi-Fi の暗号化でも利用されています。
1987年に開発されたストリーム暗号です。RC4 という名前は RSA 社の商標であるため、ARCFOUR と呼ばれることもあります。RSAWEP, WPA などで利用されていましたが、攻撃手法がいくつか見つかり、現在では推奨されていません。代わりに、ブロック暗号アルゴリズムを用いながらストリーム暗号化が可能な、OFB, CFB, CTR などのモードが利用されるようになってきました。
ブロック暗号では、64ビットや 128ビットなどのブロック単位で暗号化するため、元データがブロックサイズの整数倍でない場合、パディングを追加して整数倍にする必要があります。パディングの方式には下記などがあります。共通鍵暗号の AES では PKCS#7 が、公開鍵暗号の RSA では OAEP がよく使用されます。
データがブロックサイズの整数倍に1バイト足りない場合は末尾に 0x01 を、2バイト足りない場合は 0x02 0x02 を、3バイト足りない場合は 0x03 0x03 0x03 を付加します。最後の1バイトがパディングサイズを示します。データがブロックサイズの整数倍の場合は1ブロック余分にパディングが付加されます。AES の場合ブロック長は128ビット(16バイト)なので、パディングサイズは 0x01～0x10 のいずれかとなります。
PKCS#7 のサブセットで、パディングサイズを 0x01～0x08 に限定し、最大8バイトのパディングを行うものです。AES 暗号化で PKCS#5 を使用すると表記されていることがありますが、AES が 128ビット(16バイト)に対して PKCS#5 は8バイトにしか対応しておらず、実態は PKCS#7 でパディングしていることが多いそうです。
スマートカード規格の ISO/IEC 7816-4 で規格化されている方式で、1バイトパディングする場合は 0x80 を、N バイトパディングする場合は 0x80 の後ろに 0x00 を N - 1 個付加します。パディングを取り除く際は、末尾のデータから 0x80 が出現するまでのバイトを取り除きます。
基本的には PKCS#7 と同様、最後の1バイトがパディングサイズを示しますが、最後の1バイト以外は乱数が格納されます。
最適非対称暗号化パディングと訳されます。RSA 組み合わせて利用されることが多く、この場合は RSA-OAEP と呼ばれます。元データに 0 を付加し、ランダム値をハッシュしたものとの XOR をとり、また、これをハッシュしたものと連結します。(→ 詳細)
nビットのブロック暗号では nビットのデータを暗号化するアルゴリズムのみを定義しますが、連続するブロック列を暗号化する際の方式として暗号利用モードを指定します。主な暗号利用モードには下記などがありますが、現時点では CBC や CTR の利用が多いようです。最近では認証と暗号化を組み合わせた GCM や EAX も利用されるようになってきました。
元データを複数のブロック Di に分割し、それぞれに対して単純に秘密鍵で暗号化を行います。ブロックの内容が同じであれば暗号化の結果も同じになるため、解析されやすいという弱点があります。例えば、画像データを ECBモードで暗号化しても、元画像の輪郭がうっすらと残ってしまうことがあります。(→ 詳細)
Ci = enc(key, Di)
前ブロックの暗号化の結果を、次ブロックとXORをとったものを暗号化します。ブロックの内容が同じであっても異なる結果となり、解析されにくくなります。最初のブロックは、初期化ベクトル(IV)と呼ばれるデータとXORをとります。ブロックがひとつでも欠損すると XOR に渡す値を失ってしまうため、後続のデータは復号できなくなります。
C0 = enc(key, IV) Ci = enc(key, Di XOR Ci-1)
初期化ベクトル(IV)を暗号化したものをR0、R0 の上位 kビットと元データの先頭 kビットの XOR を結果 C0 とします。R0 を k ビット上位にシフトして下位 k ビットに C0 を埋め込み、これを暗号化したものを R1 とし、次の元データと XOR する処理を繰り返します。ブロックサイズ n とは異なる k ビット単位で暗号化できること、データが欠損しても直前データがあれば後続データを復号できることから、ストリーム暗号としても用いられます。
R0 = enc(key, IV) Ri = enc(key, (Ri-1 << k) OR Ci-1) Ci = (Ri >> (n - k)) XOR Di
初期化ベクトル(IV)を暗号化したものを R0 とし、これを暗号化したものを R1、これを暗号化したものを R2... とします。元データを D0、D1、D2... に分割し、Ri と Di の XOR を暗号化の結果とします。CFB と同様 k ビット毎に処理する方式もありましたが、セキュリティ的に弱いことが判明し、現在では使用されていません。
R0 = enc(key, IV) R1 = enc(key, Ri-1) Ci = Ri XOR Di
初期化ベクトル(IV)の代わりにノンス(Nonce)と呼ばれる情報を持ち、ノンスとカウンター値を組み合わせたものを Ri とします。Ri を暗号化したものと元データの XOR をとったものを結果 Ci とします。単純なアルゴリズムですが、ストリーム暗号にも利用できること、パディングが不要であること、データ欠損にも対応できること、並列計算も可能なことから利用が増えています。
Ri = Nonce + i Ci = enc(key, Ri) XOR Di
認証付き暗号(AEAD)のひとつ。ストリーム暗号として利用でき、また、暗号化と同時に認証も行うことができるモードです。
認証付き暗号(AEAD)のひとつ。CTR と OMAC を組み合わせたもので、CCM と同様、認証機能付きストリーム暗号として利用できます。CCM の決定をカバーするものとして採用されました。
認証付き暗号(AEAD)のひとつ。暗号化として CTR を、認証として Galois Mode を使用します。128ビットのブロック暗号で利用可能です。暗号化も復号も並列処理が可能で、効率や性能がよいことから、パケットの暗号化に適しており、IEEE 802.11ad, IPsec, SSH, TLS 1.2 などに採用されています。
メッセージ認証コードと訳されます。送信側と受信側で同じ共通鍵を使用します。送信側はメッセージと共通鍵から署名データ(MAC値, タグとも呼ばれます)を生成しメッセージに添付して送付します。受信側はこれを共通鍵を用いて確認し、メッセージが改竄されていないことを確認します。署名アルゴリズムとしてハッシュを用いる方式(HMAC) と、暗号化を用いる方式(CBC-MAC, OMAC, CMACなど)に大別されます。
任意のハッシュアルゴリズムを用いて署名データ(MAC値)を生成します。MD5 を用いる場合は HMAC-MD5、SHA256 を用いる場合は HMAC-SHA256 などと表記されます。下記の計算で、hash() は SHA256 などのハッシュ関数、|| はビット列の連結、key は共通鍵を 0x00 でパディングしたもの、ipad はブロック長の 0x36 の繰り返し、opad はブロック長の 0x5c の繰り返し、m が署名対象メッセージを意味します。
HMAC = hash((key XOR opad) || hash((key XOR ipad) || m))
ブロック暗号の CBC モードを用いてメッセージ認証を行う方式です。
CBC-MAC の改良版です。
XCBC の改良版です。
OMAC の改良版です。OMAC1 とも呼ばれていました。
並行処理が可能な MAC です。
公開鍵暗号系では、まず、公開鍵と秘密鍵のペアを作成します。秘密鍵は人に知られてはならない秘密の情報ですが、公開鍵は広く人に公開します。この鍵のペアは、公開鍵で暗号化したものは秘密鍵で復号できる、また、秘密鍵で暗号化したものは公開鍵で復号できるという特徴があります。この特質を利用してデータを暗号化するだけではなく、様々な目的で利用されます。
例えば、AさんがBさんに情報を送る場合、AさんはBさんの公開鍵で暗号化してBさんに送ります。Bさんは自分の秘密鍵でこれを復号します。復号できるのは秘密鍵を知っているBさんのみであり、情報の秘匿が守られます。ただ、公開鍵暗号系は共通鍵暗号系にくらべて計算負荷が高いため、実データの暗号化は共通鍵暗号で暗号化し、その鍵情報のみを公開鍵で暗号化して送付したりもします。
例えば、AさんはBさんから、Bさんの秘密鍵で暗号化されたデータを受け取り、これをBさんの公開鍵で復号します。Bさんの公開鍵で復号できるということは、そのデータを作成したのはBさんの秘密鍵を知っているBさん自身だということが確認でき、Bさんの本人確認を行うことができます。
デジタル署名は、データに電子印鑑を押すようなものです。たとえば、Aさんは、元データのハッシュ値を秘密鍵で暗号化したものをシグネチャ(署名)として元データに付加して、Bさんに送ります。Bさんは付加されたシグネチャをAさんの公開鍵で復号し、元データのハッシュ値と合致すれば、その文書は確かにAさんが送信してきたものであることが確認できます。
HTTPS などで利用する証明書は、ドメイン名や管理者名などの情報に対して、認証局(CA: Certification Authority)がデジタル署名を行い、その確からしさを保証するものです。証明書を作成するにはまず、秘密鍵(*.key)を作成し、秘密鍵を用いてドメイン名や管理者名などの情報を含む証明書署名要求(CSR: Certificate Signing Request)(*.csr)を作成します。これをベリサイン(現:シマンテック)、ジオトラストなどの認証局に送って署名してもらい、証明書(*.crt)とします。有名な認証局の公開鍵はルート証明書として OS にプリインストールされており、クライアントは、この公開鍵を用いて HTTPS サーバから送られてきた証明書が正しいものであることを検証します。
1976年にスタンフォード大学の Diffie と Hellman が考案した鍵交換の方式で、盗聴の可能性のある通信経路上で二者が安全に鍵を交換するための方式です。現在でも様々なプロトコルで利用されています。方式自体は公開鍵暗号ではありませんが、この方式が公開鍵暗号の概念の元となり、両者は公開鍵暗号の論文を掲載しました。
Diffie と Hellman の公開鍵暗号論文に触発され、MIT の Rivest, Shamir, Adleman の3名が開発したアルゴリズムです。大きな素数を掛け合わした値を素因数分解することが難しいことを利用しています。3名は後に RSA 社を設立します。RSA のアルゴリズムは RSA 社が特許を保持していましたが、2000年9月6日に有効期限が切れました。現在でも公開暗号のデファクトとしてよく利用されています。
1984年にエジプトの Taher Elgamal が発表したアルゴリズムです。位数が大きな群の離散対数問題が困難であることを利用しています。同氏はまた、同様の技術を電子署名に応用した、ElGamal署名も発表しています。
楕円曲線上のひとつの点が分かっていても、楕円曲線離散対数を解決することが難しいことを利用しています。RSA に比べて短い鍵長で同程度のセキュリティを提供できることから、RSA の代わりに広まりつつあります。
あるデータをアルゴリズムに基づき変換しますが、鍵情報が無くてもアルゴリズムさえ知っていれば元のデータに戻せるものをエンコーディング(encoding)と呼びます。バイナリデータを文字列化したり、文字コードをバイナリデータ化したりする際に用いられます。
バイナリデータを単純に16進数文字列で表現する方法です。バイナリデータの \x01 \x02 \x03 というデータは、文字列の 010203 となります。データ量は2倍となります。01 02 03 の様に間にスペースを入れる場合もあります。この場合のデータ量は3倍となります。
xxxxxxxx yyyyyyyy zzzzzzzz という3バイトの各ビットを、00xxxxxx 00xxyyyy 00yyyyzz 00zzzzzz という4バイトのデータに変換します。元データが3の倍数でない場合は末尾に = または == を付加します。例えば \x01\x02\x03\x04 というデータは AQIDBA== となります。データ量は約4/3倍となります。
X.509 証明書や秘密鍵をバイナリ形式にエンコーディングする際に使用されます。
証明書関連では PEM 形式のファイルがよく利用されます。DER で生成したバイナリデータを BASE64 で文字列化し、適度な長さで改行し、先頭と末尾に -----BEGIN ○○----- と -----END ○○----- を付加します。
-----BEGIN CERTIFICATE----- MIIGbzCCBFegAwIBAgIICZftEJ0fB/wwDQYJKoZIhvcNAQELBQAwfDELMAkGA1UE : y702dmPTKEdEfwhgLx0LxJr/Aw== -----END CERTIFICATE-----
文字コードをバイナリデータに変換するためのアルゴリズムです。JIS X 0208 で定められた文字コードをバイナリ化するアルゴリズムとして Shift_JIS, ISO-2022-JP, EUC-JP などがあります。Unicode で定められた文字コードをバイナリ化するアルゴリズムとして UTF-8, UTF-16 などがあります。詳細は「とほほの文字コード入門」を参照してください。