誤り検出方法 Checksumについて #Ruby

ブロックチェーン関連の実装を行なっていた際に、チェックサムで引っかかり「アドレスがinvalidです」と表示されることがあった。その際に、「チェックサムって誤り検出のやつだよな?仕組み知らないわ」となったので、少し調べて簡易的に実装してみた。

チェックサムとは?

チェックサムとは、データの信頼性を検査するための算出した値のことを言う。この値を元に、データが適切なものであるかを調べることができる

非常に単純な誤り検出方法の１つで、誤り検出の精度は低いが原理が簡単で容易に実装でき、計算コストも低いため、簡単な誤り検出方法として広く普及している

データの誤り検出の方法としてハッシュ関数を利用する方法もあるが、誤り検出のために送信する必要のあるデータのサイズが大きく、処理負荷が大きい。しかし、誤り検出の信頼性はチェックサムを利用する場合よりも高い。

チェックサムの求め方

チェックサムの求め方については、様々な手法があるが簡単な方法としては、データ列を整数値の列としてみなし和を求め、これをある定数で割った余りを検査用データとするものがある。

チェックサムの計算の例

[0xc0 0xA8 0xFF 0x58] から1バイトのチェックサムを算出するのは、
0xc0 + 0xA8 + 0xFF+0x58 = 0x2BFを求め、0x100で割った余りの0xBFがチェックサムになる

データのサイズが大きい場合は、一定の大きさごとに区切ってチェックサムを算出付加する方法が利用される

チェックサムを利用した誤り検知の実装

文字列に関してチェックサムを利用したデータの作成の関数と、誤り検出を行う関数を簡易的に実装した。

チェックサムを付加したデータを作る関数

文字列を整数値に変換して、その和を100で割ったものをチャックサムにし、データに付加して送信用のデータを作成する関数


def make_data(raw_data)
    checksum = 0
    raw_data.unpack("C*").each do |byte|
        checksum += byte
    end
    return raw_data.unpack("C*").push(checksum / 100)
end

付加されたチェックサムを確認する関数

受信したデータのチェックサムを確認し、適正なデータであれば表示し、データが破損していれば、その旨を表示する関数


def check_data(data)
    sent_checksum = data.pop
    checksum = 0
    data.each do |byte|
        checksum += byte
    end
    return sent_checksum == checksum / 100
end

def show_data(hex_data)
    data = ""
    if(check_data(hex_data)) then
        hex_data.each do |byte|
            data += byte.chr
        end
        p data + ":データは破損していません"
    else 
        p "データが破損しています"
    end
end

利用例


raw_data = "Hello"
send_data = make_data(raw_data)

show_data(send_data) # => "Hello:データは破損していません"


raw_data = "Hello"
send_data = make_data(raw_data)

send_data[1] = 0 # 通信経路で意図的にデータを書き換える

show_data(send_data) # =>"データが破損しています"

今回の例では、利用できるchecksumは0から99の100通りである。そのため、通信経路で改ざんや破損があった際に、必ず検出することができるとは限らない。和を割る数を100から大きいものにすれば、誤りを検出できる確率は高くなるが、検出に必要なデータサイズが大きくなってしまう。そうなってしまうと、データのハッシュ値を利用する方がより信頼性の高い誤り検出ができる。あくまで簡易的な誤り検出であることがわかった。

また、アルゴリズム的にもチェックを用いる方法では矛盾が生じないような改ざんも行うことができる。これに対して、ハッシュ関数では基本的にこのようなことを行うことができない。

まとめ

個人的に気になったことを簡単にまとめた。誤り検出に関しての知識がほとんどないので、これを機に理解を深めたい。