ハッシュとは
任意のサイズのデータに対して、特定の演算を施すことによって、一定のビット数の数値に変換する手順をハッシュ関数と呼び、ハッシュ関数で計算した数値をハッシュ値と呼びます。 ハッシュ関数は、同じデータに対しては常に同じハッシュ値を返すように設計します。
ハッシュの用途
大きなデータが多数あり、どれがどれと等しいかを確認する場合、総当りで全てのデータを比較すると時間がかかります。
こういった場合に、それぞれのデータのハッシュ値を取ってからそれらを比較する、という手法が有効です。
ハッシュ値が異なるならば、もとのデータも異なりますので、高い確率で短時間で不一致を見つけることができます。
ハッシュ値が等しいものに関しては、改めて元のデータを比較する必要があります（ハッシュ値が等しくても元データが同じであるとは限りません）が、
全体としては、比較に要する時間を大きく短縮することが可能です。
また、データが壊れていないかを確認することにもハッシュ値は用いることができます。
例えば、バックアップデバイスにセーブする際に、データの末尾にセーブデータ全体のハッシュ値を格納しておきます。
そうすると、ロード時にロードデータ全体のハッシュ値を取り、末尾に記録されていた数値と比較することによって、
データが壊れていないかどうかを確認することができます。
同様に、ネットワーク越しに送られてきたデータが壊れていないかの確認にも使えます。
メッセージダイジェスト
狭い意味でハッシュ関数を定義した場合、さらに一方向性というものが求められる場合があります。
一方向ハッシュ関数とは、ハッシュ値から元のデータが類推できないという性質を持つハッシュ関数で、ハッシュ値のサイズは最低でも80bit、用途によっては512bit程度となります。
一方向ハッシュ関数は、あるハッシュ値を与えられたときに、そのハッシュ値を生成する元データを求めることが不可能であるように設計されています。
ここで不可能というのは、現在の技術では計算するのに何万年といった時間がかかってしまうために、
計算することができないと見なすことができる、という意味です。
こうした一方向ハッシュ関数を改ざん検出に用いる場合、ハッシュ関数をメッセージダイジェスト関数、ハッシュ値をメッセージダイジェスト値と呼ぶことがあります。
メッセージダイジェストを使用した改ざん検出
メッセージダイジェスト値を用いると、悪意ある第三者によるデータの改ざんを防ぐことが可能になります。
メッセージダイジェスト値は固定長で短いため、安全な方法で配布することが容易です。
そして、メッセージダイジェスト値さえ安全に配布することができれば、
別に送った大きなデータのメッセージダイジェスト値がそれに一致すれば、
データのほうも正しいものが送受信できたことが分かります。
なぜならば、一方向性により、同じメッセージダイジェスト値を生成する偽データを
悪意ある第三者が作成することはできないからです。
HMAC を使用した改ざん検出
しかし、メッセージダイジェスト値をデータと一緒に送らないといけない場合はどうでしょう。
メッセージダイジェスト関数は、誰が使っても同じデータに対しては同じメッセージダイジェスト値を返します。
そのため、メッセージダイジェスト値をデータと一緒に送信する場合は、
悪意のある第三者が偽データと偽メッセージダイジェスト値をセットで送ってしまえば、
改ざんが出来てしまいますので、意味がありません。
そういった場合に、HMAC (Keyed Hashing for Message Authentication Code: メッセージ認証のための鍵付ハッシング)
を使用することができます。
HMAC は簡単に言えば、ハッシュ値をさらに暗号化する仕組みです。
HMAC 関数に、ハッシュ値を取りたいデータとデータサイズ、暗号化の鍵データと鍵サイズ、を渡すと、
鍵によって暗号化されたハッシュ値を得ることができます。
この値は、暗号化の鍵データを知らない限りは生成できませんので、
受信時に鍵付ハッシュ値が一致すれば、確かに鍵を知っている送信元が送ったデータである、と
確認することができます。
しかし、HMAC では送信側も受信側も同じ鍵を使用します（共有鍵方式）ので、
受信側のプログラムが何らかの手段で解析され、鍵が明らかになってしまうと、データを改ざんすることが可能になってしまいます。
これに対抗するためには、公開鍵方式の暗号化を利用した電子署名を導入する必要がありますが、
そのライブラリは NITRO-SDK には含まれていません。
SDK に含まれるハッシュ関数
NITRO-SDK では、（一方向ではない）ハッシュ関数として、以下のものを用意しています。
| 8bit Checksum | MATH_Checksum8* | 1の補数和の1の補数を 8bit 単位で計算します。 | |
|---|---|---|---|
| 16bit Checksum | MATH_Checksum16* | 1の補数和の1の補数を 16bit 単位で計算します。 | IP, TCP, UDP などで使用されている。 |
| CRC-8 | MATH_CRC8* | 8bit の CRC を計算します。生成多項式は x8+x2+x1+1。ビット反転はなし。初期値は0で、出力の not はありません。 | |
| CRC-16 | MATH_CRC16* | 16bit の CRC を計算します。生成多項式は x16+x15+x2+1。ビット反転はあり。初期値は0で、出力の not はありません。 | ARC, LHA などのツールで使用されている。 |
| CRC-16 / CCITT | MATH_CRC16CCITT* | 16bit の CRC を計算します。生成多項式は x16+x12+x5+1。ビット反転はなし。初期値は0xffffで、出力の not はありません。 | CCITT X.25 規格などで定められており、各種規格の通信フレームで使用されている。 |
| CRC-32 | MATH_CRC32* | 32bit の CRC を計算します。生成多項式は x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1。ビット反転はあり。初期値は0xffffffffで、出力は not します。 | PKZIP, PNG, Ethernet などで使用されている。ISO 3309, RFC 2083 などを参照。 |
| CRC-32 / POSIX | MATH_CRC32POSIX* | 32bit の CRC を計算します。生成多項式は x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1。ビット反転はなし。初期値は0で、出力は not します。 | POSIX 準拠 Unix の cksum コマンドで使用されている。POSIX 1003.2 (IEEE Std 1003.2-1992) で規定。 |
checksum は CRC の倍程度高速ですが、データの順番が入れ替わっていても同じ値になるなど、ハッシュ関数としての性質は良くありません。 なお、SDK に収められている checksum 関数は、checksum 値を元のデータに加えて全体の checksum を取ると結果が 0 になる、という性質を有しています。 また、1 の補数の世界では 0xffff と 0 が同じ値を表すため、checksum 値が 0 だったときには 0xffff に置き換えることにしても、 （元データ＋checksum 値）の checksum が 0 になるという性質は変わりません。これを利用して、正常な checksum 値として 0 を使わないようにでき、 0 を null 値（未計算など）として使用することが可能です。詳しくは、一般の UDP Checksum の解説を参照してください。
CRC はデータ長が一定長以下の場合、あるビット数までの誤りであれば確実に発見できることを保証するような数学的な設計がされています。
例えば、CRC-16, CRC-16/CCITT はデータ長が CRC を含めて 32767 ビットまでの時に、任意の 3bit までの誤り、
もしくは 16bit までの連続した誤りを確実に検出することができます。もちろん、この条件が満たされなくても高い確率で誤りを検出します。
なお、CRC は誤り訂正の機能も持っていますが、検出にのみ使用されることが多く、訂正に使われることはあまりありません。
SDK では MATH_CalcCRC16() と同じ結果を返す SVC_GetCRC16() も
用意していますが、MATH の CRC 関数では計算用のテーブルを事前に用意しておくことにより、処理を高速にしています。
なお、これらは一方向ハッシュ関数ではありませんので、同じハッシュ値になるようにデータを改ざんすることは容易です。
また、一方向ハッシュ関数としては、以下のものを用意しています。
| SHA-1 | MATH_CalcSHA1 |
メッセージダイジェスト値の長さは 160bit。 | MD5 の後継として広く使われている。RFC 3174 を参照。 |
|---|---|---|---|
| HMAC-SHA-1 | MATH_CalcHMACSHA1 |
SHA-1 を利用した HMAC。メッセージダイジェスト値の長さは 160bit。 | FIPS PUB 180-2 を参照。 |
| SHA-256 | MATH_SHA256* | メッセージダイジェスト値の長さは 256bit。 | SHA-1 の後継として使われる。RFC 3174 を参照。 |
| HMAC-SHA-256 | MATH_CalcHMACSHA256 | SHA-256 を利用した HMAC。メッセージダイジェスト値の長さは 256bit。 | FIPS PUB 180-2 を参照。 |
MD5 は一方向ハッシュ関数として広く使われてきましたが、 研究が進み、特定の状況下での弱点が次々と報告されています。 そのため、現在では一方向ハッシュ関数としては SHA-1 が利用されることが多くなっています。 新規に一方向ハッシュ関数を利用する場合には、SHA-1 を使用したほうがよいでしょう。
なお、これらの一方向ハッシュ関数は、結果の途中までのビットだけを用いても十分にハッシュ値として使用できます。 （HMAC-SHA-1 を最初の 80bit だけ保存して使用する、など。） 当然のことながら、結果を切り詰めるほど、ハッシュとしての性質は悪化します。
MATH関数一覧(ハッシュ値), MATH関数一覧(メッセージダイジェスト)
2007/10/31 最近の動向を踏まえ、MD5 に関する記述を削除
2006/05/24 最近の動向を踏まえ、MD5 よりも SHA-1 のほうが望ましいことを明記
2005/07/08 SHA-1 の実装変更に伴い、dgt-2 デモの出力サンプルを更新
2005/06/24 MD5 の実装変更に伴い、dgt-2 デモの出力サンプルを更新
2005/04/18 初版