チェックサムとは (チェックサムとは) [単語記事]

チェックサム(checksum)とは、総和を調べることにより手軽にエラーをチェックする手法のことである。

概要

例として文字列「#nicopedia」について考える。

この文字列を送信したり記録したりする際に何らかの要因でデータが書き換わっていたとき、それに気づけないと困ってしまうだろう。そこで文字列についての総和をとることにより調べられるようにする。

ここでは文字列「#nicopedia」をASCIIにおける数値に変換して足し算する。(ここの足し算のやり方は他のやり方でもよい)

文字	#	n	i	c	o	p	e	d	i	a	合計
ASCII	35	110	105	99	111	112	101	100	105	97	975

さらにこの情報を1バイトで扱えるように、256で割った余りを情報として加えるようにしよう。
975÷256 = 3余り207
よって「207」という情報を「#nicopedia」という文字列に付け加えるようにする。(ちなみにこの「207」のような合計値のことをチェックサムと呼ぶ場合も多いので各自文脈で判断してほしい)

さて、このときチェックサム「207」が保たれたまま文字列が「#Nico pedia」に改ざんされたとする。n, Nに対応するASCIIの値はそれぞれ110, 78(32減っている)なので、文字列の合計値は32減って943。さらに256で割った余りも32減って175となる。これは207と一致しないので元の文字列とは異なることが分かる。

チェックサムが一致していてもデータが保たれているとは限らないが、チェックサムが一致しないときデータは確実に間違っている。数学的に考えると自明に真である命題
「同じデータならばチェックサムは一致する」
の対偶である
「チェックサムが一致しないならば異なるデータである」
も同様に真であると言える。

先述したとおりチェックサムが一致してもデータが保たれているとは限らない。上記の単純な足し算による例ならば、チェックサムを一致したままデータを改ざんする簡単な方法は「単純な入れ替え」である。上記で用いた「#nicopedia」という文字列はいくら入れ替えたところで総和が975であり、256で割った余りは207である。

さらに、総和さえ合っていれば何をしてもよいので上手に改ざんすれば何事もなかったかのようにチェックを通過できる。

そのうえ故意ではなくても偶然チェックサムが一致してしまう可能性だってある。先程の例のように1バイトのデータを付加する場合、単純計算で1/256の確率で一致してしまう。これは状況によっては無視できない確率といえるだろう。

このようにチェックサムはエラーを検出する方法としては手軽であるが信頼性は高いとは言い切れない。「誤り検出」などのキーワードで検索するとより良い手法がたくさん見つかるだろう。

実例

バーコード

日本におけるバーコードの種類はいくつかあるが、ここでは

(2桁) 国コード
(5桁) メーカコード
(5桁) 商品コード
(1桁) チェックディジット

の13桁のバーコードについて考える。(他の場合についても本質はほぼ変わらない)

国コードは日本は45または49であるから今回は45として、メーカコードと商品コードは適当に12345と67890にして残りのチェックディジットを計算していく。バーコード風に書くと
4 512345 67890?
といった具合である。(?の部分がチェックディジットに当たる)

このタイプのバーコードのチェックディジットの計算には「モジュラス10ウェイト3」という手法が使われる。modulusとは剰余の計算で用いる「法」であり、「10を法とする…」や「mod10」のことである。weightとは計算する際の「重み付け」のことであり今回は特定の桁を3倍する。

「モジュラス10ウェイト3」の計算方法は次の通りである。

チェックディジットを除いた数字に対し先頭を1桁目として奇数桁と偶数桁に分ける
奇数桁の数値を合計し3倍する
偶数桁の数値を合計する
2と3で求めた値を合計し一の位の10の補数が答え(すなわち次の10の倍数までの値)

具体的に見ていこう。

バーコード	4	5	1	2	3	4	5	6	7	8	9	0	合計
奇数桁		5		2		4		6		8		0	25
偶数桁	4		1		3		5		7		9		29

25×3+29=104
なので、求めるチェックディジットは6となった。よってバーコードは
4 512345 678906
となる。

かなり複雑な計算をしたが、本質的な部分である
「チェックサムが一致しないならば異なるデータである」
の部分はきちんと成立しており、適当にバーコードの値を改ざんしたとしても約9割の確率で発見できる。

サブフレームリセット

サブフレームリセットとは、ゲームにおいて機械語1命令単位の任意のタイミングでリセットを行う技のことである。

これをセーブデータの書き込みの最中に行うと、通常はデータが中途半端な書き込みで終了し"データが破損した"状態になる。(一般にデータが破損した状態だと判定されるとデータは消去される)

ところでデータが破損した状態というのはどうやって判定されるのだろうか？この判定にチェックサムが使われる場合が多い。そして先述の通りチェックサムは総和さえ合っていれば何をしてもよい。すなわちあらかじめチェックサムを通るように準備してサブフレームリセットを行えばとんでもないデータの改ざんを行うことが可能である。

従来のエミュレータは1フレームごとに操作を受け付けるものであったため、サブフレームリセットは実機でのみ(理論上は)可能である行動として提唱されていた。ただし、実機でサブフレームリセットを行おうとすると、状況にもよるが1ミリ秒未満のシビアなタイミングを要求される。その後TAS用エミュレータであるLsnesがサブフレームリセットに対応(Lsnes上の名称はDelayed Reset)すると、TASにおける記録更新の手法として用いられるようになった。特に人間の手では困難だったシビアなタイミングでのリセットの問題はTASでは問題にならないため、チェックサムを通過しつつ最速を目指すというシンプル(かつそれはそれで困難)な問題へと変えることが可能になった。