Blockchain

RIPEMD160 を Golang で実装する

By なんぞー 12 October 2018
RIPEMD160 を Golang で実装する

こんにちは、なんぞーです！

今回も前回(SHA256 を Golang で実装する)に引き続き Bitcoin で使われているハッシュ関数の一つである RIPEMD-160 を学ぶために Golang でフルスクラッチで実装してみたいと思います！

あくまでも、仕組みを理解するためのコーディングなので、処理速度などは考慮せずに進めていきたいと思います。
コードについてのご指摘やアドバイスなどは Twitter()にいただけると非常にありがたいです！

RIPEMD

RIPEMD はMD4 の設計原理に基づいたものであり、SHA-1 と同程度パフォーマンスを有している。
SHA-1[1]や SHA-2[2]が NSA[3]によって開発されたのと対照的に、RIPEMD はオープンな学術コミュニティによって開発され、特許による制限を受けない。(引用:Wikipedia)

RIPEMD-160

RIPEMD-160 とは、RIPEMD の中でもハッシュ長が 160 ビット(20 バイト)のものを指している。
ビットコインのブロックチェーンでも SHA-256 と共に重要な役割を果たしている。

RIPEMD の大まかな説明はこんな感じです！
では、早速コーディングに移っていきたいと思います！

記号と演算子

今回 RIPEMD-160 を実装していくにあたって、【RIPEMD-160: A Strengthened Version of RIPEMD】[4]を参考に進めていくのですが、そこで使われる記号と演算子について軽く説明しておきます。

記号意味例
lor論理和(OR)lor
land論理積(AND)land
oplus排他的論理和(XOR)oplus
lnot否定(NOT)lnot
ll左シフト(x を n ビット左にシフトする)ll
gg右シフト(x を n ビット右にシフトする)gg
1
2
3
4
// ROTL ...
func ROTL(x uint32, n uint) uint32 {
    return (x << n) | (x >> (32 - n))
}

各関数の作成

まずはじめに、hash を計算するにあたって使用する関数を作成していきます！
RIPEMD-160 の計算ではラウンドごとに決められた関数を用いて計算します。

Nonlinear Functions

引用元:[RIPEMD-160:A Strengthened Version of RIPEMD]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// F ...
func f(j, x, y, z uint32) uint32 {
    if 0 <= j && j <= 15 {
        return x ^ y ^ z
    } else if 16 <= j && j <= 31 {
        return (x & y) | ((^x) & z)
    } else if 32 <= j && j <= 47 {
        return (x | (^y)) ^ z
    } else if 48 <= j && j <= 63 {
        return (x & z) | (y & (^z))
    } else if 64 <= j && j <= 79 {
        return x ^ (y | (^z))
    }
    return 0
}

Padding

次にパディングというデータの長さを整える処理をおこなっていきます。
冒頭で述べたように RIPEMD 関数は MD4 関数の設計原理に基づき開発されました。
従って、これからおこなう Padding 処理は MD4 関数で行われるものと同様のものとなっていますので、
既知の方は読み飛ばしていただいて構いません。


RIPEMD-160では、ハッシュ化するメッセージ長が512ビット(64バイト)の倍数になっていなくてはなりません。 したがって足りないデータを補うためにこのパディングという処理を行います。

パディング処理ではあるメッセージ M の長さを l(エル)とし

を満たす k を用いて表された以下の形式のデータを末尾に追加する処理です。
メッセージの後ろにビットの”1”を加え 0 で埋め、残り 64 ビットにメッセージの長さ l(エル)を加えます。

ここで注意点なのですが、前回の SHA-256 の実装では残り 64 ビットにメッセージ長 l(エル)を加える際にビックエンディアンで追加したのですが、 今回の RIPEMD-160 ではリトルエンディアンで追加しなければなりません。

バイトオーダーに関しましては下記の画像がわかりやすいと思います！

Difference of Byte-Order

引用元:バイトオーダ - ビッグエンディアン/リトルエディアン

こちらがそのコードになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Padding ...
func Padding(message []byte) []byte {
    l := len(message)
    if l%64 < 56 {
        newlen := l % 64
        message = append(message[:], []byte{0x80}...)
        zero := make([]byte, 56-(newlen+1))
        message = append(message[:], zero[:]...)
        ms := make([]byte, 8)
        binary.LittleEndian.PutUint64(ms, uint64(l*8))
        message = append(message[:], ms[:]...)
    } else {
        message = append(message[:], []byte{0x80}...)
        newlen := l%64 + 1
        zero := make([]byte, 120-newlen)
        message = append(message[:], zero[:]...)
        ms := make([]byte, 8)
        binary.LittleEndian.PutUint64(ms, uint64(l*8))
        message = append(message[:], ms[:]...)
    }
    return message
}

先ほど述べたように SHA-256 の時とは違い LittleEndian でメッセージ長を追加します。

1
2
3
4
5
6
7
// RIPEMD-160
binary.LittleEndian.PutUint64(ms, uint64(l*8))
message = append(message[:], ms[:]...)
// SHA-256
binary.BigEndian.PutUint64(ms, uint64(l*8))
message = append(message[:], ms[:]...)

Parse

次に 512 ビットの倍数長に整えられたメッセージブロックを 32 ビット 16 個のかたまりに分割します。

1
2
3
4
5
6
7
8
9
10
11
12
// Parse ...
func Parse(message []byte) [][16]uint32 {
    fmt.Println(message)
    M := make([][16]uint32, len(message)/64)
    fmt.Println(M)
    for i := 0; i < len(message)/64; i++ {
        for j := 0; j < 16; j++ {
            M[i][j] = uint32(message[64*i+j*4]) | uint32(message[64*i+j*4+1])<<8 | uint32(message[64*i+j*4+2])<<16 | uint32(message[64*i+j*4+3])<<24
        }
    }
    return M
}

こちらの処理においても SHA-256 と異なる箇所があります。
メッセージブロックに関しても LittleEndian でメッセージを格納していきます。

1
2
3
4
5
6
// RIPEMD-160
M[i][j] = uint32(message[64*i+j*4]) | uint32(message[64*i+j*4+1])<<8 | uint32(message[64*i+j*4+2])<<16 | uint32(message[64*i+j*4+3])<<24
//SHA-256
M[i][j] = uint32(message[64*i+j*4+3]) | uint32(message[64*i+j*4+2])<<8 | uint32(message[64*i+j*4+1])<<16 | uint32(message[64*i+j*4])<<24

圧縮処理

次に、メインの計算部分に入っていきます。
まず、初期値に 32 ビットの 5 つのワードを指定します。

1
2
3
4
5
6
7
8
// Initial Hash Value
var H = []uint32{
    0x67452301,
    0xefcdab89,
    0x98badcfe,
    0x10325476,
    0xc3d2e1f0,
}

この設定した初期値と、32 ビット 16 個のかたまりに分割されたメッセージブロックを用いて計算していきます。
この圧縮処理はそれぞれ 16 ステップの 5 つの並列ラウンドで構成されています。
MD4 では 16 ステップの 3 つのラウンドなので 16*3 の合計 48 ステップに対して、RIPEMD-160 では 16*5*2 の合計 160 ステップの計算を行うこととなります。

まず初期値から、２つのコピーを作成します。

1
2
3
4
5
6
7
8
9
10
11
12
// 左ラウンド用
a := H[0]
b := H[1]
c := H[2]
d := H[3]
e := H[4]
// 右ラウンド用
_a := H[0]
_b := H[1]
_c := H[2]
_d := H[3]
_e := H[4]

作成された２つの初期値のコピーは、それぞれ別の処理を行い、最後にまとめられます。
各ステップでは、メッセージブロック 16 個のうちの一つと、他 4 つの値から新しい値を計算します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1ステップの処理(左ラウンド)
T = ROTL(a+f(t, b, c, d)+m[r[t]]+K(t), s[t]) + e // m[r[t]] メッセージブロック
a = e
e = d
d = ROTL(c, 10)
c = b
b = T
// 1ステップの処理(右ラウンド)
T = ROTL(_a+f(79-t, _b, _c, _d)+m[_r[t]]+_K(t), _s[t]) + _e // m[r[t]] メッセージブロック
_a = _e
_e = _d
_d = ROTL(_c, 10)
_c = _b
_b = T

なお、シフト量や変化をつけるための定数に関してはあらかじめ決められています。そちらに関しましては今回のコードをご覧ください。
最後に、左側のラウンドの結果と右側のラウンドの結果を合わせることによってハッシュを計算しています。

1
2
3
4
5
6
T = H[1] + c + _d
H[1] = H[2] + d + _e
H[2] = H[3] + e + _a
H[3] = H[4] + a + _b
H[4] = H[0] + b + _c
H[0] = T

大まかな流れについては下図を見ていただけるわかると思います！

引用元:[RIPEMD-160:A Strengthened Version of RIPEMD]

ここまでの処理をまとめるとこのように表すことができます。

Pseudo-code

引用元:[RIPEMD-160:A Strengthened Version of RIPEMD]

上記の画像は擬似コードと呼ばれる、高級言語に似た架空の書式で書かれているので、これをコードに落とし込んでいきます。
こちらがそのコードになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// HashComp ...
func HashComp(M [][16]uint32) [20]byte {
    T := uint32(0)
    for _, m := range M {
        a := H[0]
        b := H[1]
        c := H[2]
        d := H[3]
        e := H[4]
        _a := H[0]
        _b := H[1]
        _c := H[2]
        _d := H[3]
        _e := H[4]
        for t := uint32(0); t < 80; t++ {
            T = ROTL(a+f(t, b, c, d)+m[r[t]]+K(t), s[t]) + e
            a = e
            e = d
            d = ROTL(c, 10)
            c = b
            b = T
            T = ROTL(_a+f(79-t, _b, _c, _d)+m[_r[t]]+_K(t), _s[t]) + _e
            _a = _e
            _e = _d
            _d = ROTL(_c, 10)
            _c = _b
            _b = T
        }
        T = H[1] + c + _d
        H[1] = H[2] + d + _e
        H[2] = H[3] + e + _a
        H[3] = H[4] + a + _b
        H[4] = H[0] + b + _c
        H[0] = T
    }
    var hash [20]byte
    for i, s := range H {
        hash[i*4] = byte(s)
        hash[i*4+1] = byte(s >> 8)
        hash[i*4+2] = byte(s >> 16)
        hash[i*4+3] = byte(s >> 24)
    }
    return hash
}

Sum 関数

上記の一連の処理をまとめた関数を作成しました。

1
2
3
4
5
func Sum160(data []byte) [20]byte {
	padData := Padding(data)
	parsedData := Parse(padData)
	return HashComp(parsedData)
}

出力結果

今回は既存のライブラリである’crypto/ripemd160’を用いて検証を行いました。

1
2
3
4
5
6
7
8
9
func main() {
    data := []byte("abcdefg")
    fmt.Printf("RIPEMD-160 : %x\n", Sum160(data))
    rip := ripemd160.New()
    io.WriteString(rip, "abcdefg")
    fmt.Printf("RIPEMD-160 : %x\n", rip.Sum(nil))
}
> RIPEMD-160 : 874f9960c5d2b7a9b5fad383e1ba44719ebb743a
  RIPEMD-160 : 874f9960c5d2b7a9b5fad383e1ba44719ebb743a

まとめ

今回一から RIPEMD-160 を実装してみて、ハッシュ関数によってバイトオーダーが異なった状態で処理したりだとか、それぞれのハッシュ関数の違いがより理解できたと思います。
また RIPEMD-160 は、CRYPTREC の暗号リストにおいて運用監視暗号リストに含まれていて、互換性維持の目的以外での利用は推奨されていないにも関わらず、Bitcoin で使用されているのはなぜかと思い調べてみると、強衝突耐性がまだ破られていない一方向ハッシュの中で十分一意性が保たれていてかつ短いハッシュを生成できるゆえに使用されているということもわかりました。

今後もブロックチェーンを支えている技術の理論的なところをコードも交えて、紹介できたらなと思っています！

最後まで読んで頂きましてありがとうございました！

コード全体はGithub Gistに上がっています。

Twitter()もやっておりますのでぜひご感想やアドバイスお待ちしております！

参考文献