Checksum

提供: tezos-wiki
移動先: 案内検索
ファイル:Ext 38dKJsdjh Checksum.svg
一般的なチェックサム関数の効果(Unix cksum< / tt>ユーティリティ)

A チェックサム は、エラー検出の目的でデジタルデータのブロックから派生した小さなdatum 伝送またはストレージ。これは通常、ダウンロードサーバーから受信された後にインストールファイルに適用されます。それ自体では、チェックサムはデータの整合性を検証するためによく使用されますが、データ信頼性を検証するためには使用されません。

データ入力からチェックサムを生成する実際の手順は、 チェックサム関数 チェックサムアルゴリズム と呼ばれます。その設計目標に応じて、チェックサムアルゴリズムは、入力に対するわずかな変更に対しても、通常は大幅に異なる値を出力します。これは、多くのデータ破壊エラーを検出し、全体的なデータの整合性を検証するために使用される暗号ハッシュ関数に特に当てはまります。現在のデータ入力に対する計算されたチェックサムが、以前に計算されたチェックサムの記憶された値と一致する場合、データが偶然に変更されたり壊れていない可能性が非常に高い。

チェックサム関数は、ハッシュ関数指紋ランダム化関数暗号ハッシュ関数しかし、これらの概念のそれぞれは、異なるアプリケーションと、異なる設計目標を持っています。たとえば、文字列の先頭を返す関数は、いくつかのアプリケーションに適したハッシュを提供できますが、決して適切なチェックサムにはなりません。チェックサムは、より大きな認証アルゴリズムで暗号プリミティブとして使用されます。これら2つの具体的な設計目標を持つ暗号システムについては、 HMACを参照してください。

チェックデジット sとパリティビットは小さなデータブロック([社会保障番号]、[銀行口座]]、コンピュータ語、単一バイトなど)。一部の[エラー訂正コード]は、一般的なエラーを検出するだけでなく、場合によっては元のデータを回復できる特別なチェックサムに基づいています。

アルゴリズム[編集]

パリティバイトまたはパリティワード[編集]

最も簡単なチェックサムアルゴリズムは、データを固定数nのビットで「ワード」に分割し、縦方向パリティチェック(排他的論理和)を計算します。結果はメッセージに余分な単語として追加されます。受信者は、メッセージの完全性をチェックするために、チェックサムを含むその単語のすべてまたは排他的なものを計算します。結果が「n」のゼロからなる語でない場合、受信機は伝送エラーが発生したことを知る。

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

モジュール合計[編集]

以前のアルゴリズムの変形は、すべての "ワード"を符号なし2進数として追加し、オーバーフロービットを破棄し、合計の[2の補数]をチェックサムとして付加することです。 メッセージを検証するために、受信者はチェックサムを含む同じ方法ですべての単語を追加します。 結果がゼロでいっぱいの単語でない場合は、エラーが発生しているに違いありません。 この変種も単一ビットエラーを検出しますが、 SAE J1708では前者の合計が使用されます。

位置依存[編集]

上記で説明した単純なチェックサムは、データワードの順序を変更する、またはすべてのビットをゼロに設定してワードを挿入または削除するなど、多くのビットに同時に影響を与えるいくつかの一般的なエラーを検出することはできません。 [Fletcher's checksum]、[Adler-32]、[CRC(cyclic redundancy check)]など、実際に最もよく使用されるチェックサムアルゴリズムは、各単語の値だけでなく シーケンス内の位置も示します。 この機能は一般に、チェックサムを計算する際のコストを増加させます。

一般的な考察[編集]

"m"ビット長のメッセージは、 "m"次元の超立方体の角として見ることができます。 nビットのチェックサムを生成するチェックサムアルゴリズムの効果は、各「m」ビットメッセージを、ディメンションを持つより大きな超立方体の隅にマッピングすることです。 2 'この超立方体の角は、すべての可能な受信メッセージを表す。有効な受信メッセージ(正しいチェックサムを有するもの)は、2つの "m"コーナー。

シングルビット送信エラーは、有効なコーナー(正しいメッセージとチェックサム)から隣接する「m」のコーナーの1つに移動することに相当します。 k ビットに影響を及ぼすエラーは、正しいコーナーから k ステップが削除されたコーナーにメッセージを移動します。良いチェックサムアルゴリズムの目的は、有効なコーナーを可能な限り互いに遠くに広げて、「典型的な」伝送エラーが無効なコーナーになる可能性を高めることです。

関連項目==

一般的な話題

エラー訂正

ハッシュ関数

関連概念

ソース[編集]

http://wikipedia.org/