チェックサム

チェックサムは、デジタルデータの転送中または保存中に発生したエラーを検出するために、別のデジタルデータブロックから抽出された小さなサイズのデータ​​ブロックです。チェックサム自体はデータの整合性を検証するために使用されることが多いですが、データの信頼性を検証するためには頼りにされていません。^[1]

このチェックサムを生成する手順は、チェックサム関数またはチェックサムアルゴリズムと呼ばれます。設計目標によって異なりますが、優れたチェックサムアルゴリズムは通常、入力に小さな変更が加えられた場合でも大幅に異なる値を出力します。^[2]これは特に、多くのデータ破損エラーを検出し、全体的なデータ整合性を検証するために使用される暗号化ハッシュ関数に当てはまります。現在のデータ入力に対して計算されたチェックサムが、以前に計算されたチェックサムの保存値と一致する場合、データが誤って変更または破損されていない可能性が非常に高くなります。

チェックサム関数は、ハッシュ関数、フィンガープリント、ランダム化関数、および暗号ハッシュ関数に関連しています。ただし、これらの概念はそれぞれ用途が異なり、したがって設計目標も異なります。たとえば、文字列の先頭を返す関数は、一部の用途に適したハッシュを提供できますが、適切なチェックサムにはなりません。チェックサムは、大規模な認証アルゴリズムの暗号プリミティブとして使用されます。これら 2 つの特定の設計目標^{[明確化が必要]}を持つ暗号システムについては、HMAC を参照してください。

チェック ディジットとパリティ ビットは、チェックサムの特殊なケースであり、小さなデータ ブロック (社会保障番号、銀行口座番号、コンピュータ ワード、単一バイトなど) に適しています。一部のエラー訂正コードは、一般的なエラーを検出するだけでなく、特定のケースで元のデータを復元できるようにする特殊なチェックサムに基づいています。

最も単純なチェックサムアルゴリズムは、いわゆる縦方向パリティチェックです。これは、データを固定数nのビットを持つ「ワード」に分割し、それらのすべてのワードのビット単位の排他的論理和(XOR) を計算します。結果は、追加のワードとしてメッセージに追加されます。簡単に言えば、n =1 の場合、これはデータビットの末尾にビットを追加して、偶数個の「1」があることを保証することを意味します。メッセージの整合性をチェックするために、受信側は、チェックサムを含むすべてのワードのビット単位の排他的論理和を計算します。結果がn個のゼロで構成されるワードでない場合、受信側は送信エラーが発生したことを認識します。^[3]

このチェックサムでは、メッセージの 1 ビットまたは奇数ビットを反転させる送信エラーは、不正なチェックサムとして検出されます。ただし、2 ビットに影響するエラーは、それらのビットが 2 つの異なるワードの同じ位置にある場合は検出されません。また、2 つ以上のワードの入れ替えも検出されません。影響を受けるビットが独立してランダムに選択される場合、2 ビット エラーが検出されない確率は1/ nです。

前述のアルゴリズムの変形では、すべての「ワード」を符号なしの 2 進数として追加し、オーバーフロー ビットを破棄し、合計の2 の補数をチェックサムとして追加します。メッセージを検証するには、受信側はチェックサムを含むすべてのワードを同じ方法で追加します。結果がゼロでいっぱいのワードでない場合は、エラーが発生しているはずです。この変形でも、1 ビットのエラーが検出されますが、SAE J1708ではプロ モジュラー サムが使用されます。^[4]

上で説明した単純なチェックサムでは、データ ワードの順序の変更や、すべてのビットがゼロに設定されたワードの挿入または削除など、一度に多くのビットに影響する一般的なエラーを検出できません。Fletcherのチェックサム、Adler-32、巡回冗長検査(CRC) など、実際に最もよく使用されるチェックサム アルゴリズムは、各ワードの値だけでなく、シーケンス内の位置も考慮することで、これらの弱点に対処します。この機能により、チェックサムの計算コストが一般的に増加します。

ファジー チェックサムのアイデアは、スパムの疑いのある電子メールの複数の ISP の協力データベースを構築することで、電子メール スパムを検出するために開発されました。このようなスパムの内容は細部が変化することが多く、通常のチェックサムは効果がありません。対照的に、「ファジー チェックサム」は、本文をその特徴的な最小値にまで縮小し、通常の方法でチェックサムを生成します。これにより、わずかに異なるスパム メールが同じチェックサムを生成する可能性が大幅に高まります。協力 ISP のSpamAssassinなどの ISP スパム検出ソフトウェアは、すべての電子メールのチェックサムをDCCなどの集中サービスに送信します。送信されたファジー チェックサムの数が特定のしきい値を超えると、データベースはこれがおそらくスパムであると記録します。ISP サービスのユーザーも同様に、各電子メールのファジー チェックサムを生成し、サービスにスパムの可能性を要求します。^[5]

mビットの長さのメッセージは、 m次元のハイパーキューブのコーナーとして見ることができます。nビットのチェックサムを生成するチェックサム アルゴリズムの効果は、各mビットのメッセージを、次元がm + nであるより大きなハイパーキューブのコーナーにマッピングすることです。このハイパーキューブの2 ^{m + n}コーナーは、受信可能なすべてのメッセージを表します。有効な受信メッセージ (正しいチェックサムを持つメッセージ) は、 2 ^mコーナーのみを持つ小さなセットで構成されます。

1 ビットの伝送エラーは、有効なコーナー (正しいメッセージとチェックサム) からm 個の隣接するコーナーの 1 つへの変位に対応します。k ビットに影響するエラーは、メッセージを正しいコーナーからkステップ離れたコーナーに移動します。優れたチェックサム アルゴリズムの目標は、有効なコーナーを可能な限り互いに離して分散させ、「一般的な」伝送エラーが無効なコーナーで終わる可能性を高めることです。

一般的なトピック

• アルゴリズム
• チェックデジット
• ダムアルゴリズム
• データの腐敗
• ファイル検証
• フレッチャーのチェックサム
• フレームチェックシーケンス
• 合計
• md5sum
• sha1sum
• パーアーカイブ
• 合計 (Unix)
• SYSV チェックサム
• BSD チェックサム
• xxハッシュ

エラー訂正

• ハミングコード
• リード・ソロモン誤り訂正
• IPv4 ヘッダー チェックサム

ハッシュ関数

• ハッシュ関数のリスト
• ルーンアルゴリズム
• パリティビット
• ローリングチェックサム
• ヴェルホエフアルゴリズム

ファイルシステム

• ZFS  – チェックサムを使用してファイルの整合性を自動的にチェックするファイルシステム

関連概念

• イソプセフィ
• ゲマトリア
• ファイルの固定性

• Koopman, Philip、Driscoll, Kevin、Hall, Brendan (2015 年 3 月)。「重要なデータの整合性を確保するための巡回冗長コードとチェックサム アルゴリズム」(PDF)。連邦航空局。DOT/FAA/TC-14/49。2015年 5 月 18 日にオリジナルからアーカイブ(PDF) 。
• Koopman, Philip (2023). 「大規模ブロックモジュラー加算チェックサムアルゴリズム」. arXiv : 2302.13432 [cs.DS].

Wikibookのアルゴリズム実装には、チェックサムに関するページがあります。

• Barr グループの加法チェックサム (C) 理論
• 暗号チェックサムの実用的応用 *A4 *USレター *USレター2段組
• チェックサム計算機
• ダウンロードの検証に使用される GUI を備えたオープンソースの Python ベースのアプリケーション。