015 Pythonでビットコインを学ぶ (シャー256 5)
015 Use python to learn bitcoin (sha256 5)

ニコニコ動画にアップした動画のまとめ記事です。

This is a summary blog post about a video I uploaded to NicoNico.

細かい部分は動画を参考にしてください。

Please refer to the video for details.

前回の続きです。

Continued from last time.

初期ハッシュ値を算出し終わったので、今度は16進数表記から2進数表記の配列に変換してみましょう。

Now that we have calculated the initial hash values, let's convert them from hex to a binary array.

因みに、後でアップする動画では文字列もファイル等のデータもバイト列に変換するので、16進数表記を使用します。

Incidentally, in the video to be uploaded later, strings and data such as files are converted to bytes, so 16 notation is used.

今回は2進数表記の文字列のほうが、バイナリ操作等が理解しやすいと思ったので、一時的に2進数表記の文字列を使用しているだけです。

This time, I thought that binary strings are easier to understand for bitwise operation, so I only use binary strings temporarily.

binメソッドを使うより、formatメソッドのほうが分かりやすいので、今回はformatメソッドを使用します。

The format method is easier to read than the bin method, so I'll use the format method this time.

これで初期ハッシュ値を16進数表記から2進数表記の配列に変換できました。

Now we can convert the initial hash values from hexadecimal strings to an array of binary strings

init_hash_values
H = init_hash_values.copy()

H[0]
'0x6a09e667'
bin(int(H[0], 16))
'0b1101010000010011110011001100111'
format(int(H[0], 16), '032b')
'01101010000010011110011001100111'

H = [format(int(h, 16), '032b') for h in H]
H
['01101010000010011110011001100111',
'10111011011001111010111010000101',
'00111100011011101111001101110010',
'10100101010011111111010100111010',
'01010001000011100101001001111111',
'10011011000001010110100010001100',
'00011111100000111101100110101011',
'01011011111000001100110100011001']

そして、これらの初期ハッシュ値は圧縮ループと言われる手法で最終的に出力されるハッシュ値へと変換されます。

These initial hash values are then converted into the final output hash value in a technique called a compression loop.

図で圧縮ループのアルゴリズムを見てみましょう。

Let's look at the compression loop algorithm in diagram.

[a,b,c,d,e,f,g,h]は初期ハッシュ値でそれぞれ32ビットです。

these [a,b,c,d,e,f,g,h] values are initial hash values, 32 bits each long.

Wtはハッシュされる入力データです。メッセージスケジュール（それぞれ32ビット）とも呼ばれていてｔはループ回数です。

Wt is input data to be hashed, and also called message schedule. [t] is loop count. 32 bits each long.

Ktはラウンド定数です。ｔはループ回数で、それぞれ32ビットになります。

Kt is Round constant. 32 bits each long. [t] is loop count.

これらを圧縮と言われるアルゴリズムでメッセージスケジュールやラウンド定数の要素数(64個)だけループさせます。(つまり64回ループされる)

These are looped by the number of elements of the message schedule and round constant (64 for both) in an algorithm called compression. (looped 64 times)

ハッシュ値[a,b,c,d,e,f,g,h]は図のようにそれぞれ新たにシャッフルされて次のループに使われます。

The hash values [a, b, c, d, e, f, g, h] are each shuffled anew and used in the next loop, as shown in the diagram.

圧縮アルゴリズム内で使われているハッシュ値を変える為のメソッドは以下の6つです。

There are six methods to change the hash value used in the compression algorithm.

Ch(Choose)の式はハッシュe,f,gに対してのビット演算です。(e and f) xor ((not e) and g)

The expression Ch (Choose) is a bitwise operation on hashes e, f, g. (e and f) xor ((not e) and g)

S1(Sigma1)の式はハッシュeに対してのビット演算です。(e right-rotate 6) xor (e right-rotate 11) xor (e right-rotate 25)

The expression S1 (Sigma1) is a bitwise operation on hash e. (e right-rotate 6) xor (e right-rotate 11) xor (e right-rotate 25)

temp1(temporary1)の式はKのt番目とWのt番目とハッシュhとS1とChを足して2の32乗で剰余計算したものです。h + S1 + ch + Kt + Wt

The expression for temp1 (temporary 1) is the sum of the t'th of K and the t'th of W, hash h, S1 and Ch. The summed values are modulo computed by 2 raised to the power of 32. h + S1 + ch + Kt + Wt

Ma(Majority)の式はハッシュa,b,cに対してのビット演算です。(a and b) xor (a and c) xor (b and c)

The expression Ma (Majority) is a bitwise operation on hashes a, b, c. (a and b) xor (a and c) xor (b and c)

S0(Sigma0)の式はハッシュaに対してのビット演算です。(a right-rotate 2) xor (a right-rotate 13) xor (a right-rotate 22)

The expression S0 (Sigma0) is a bitwise operation on hash a. (a right-rotate 2) xor (a right-rotate 13) xor (a right-rotate 22)

temp2(temporary2)の式はS0とMaを足して2の32乗で剰余計算したものです。S0 + Ma

The expression for temp2 (temporary 2) is the sum of S0 and Ma. The summed values are modulo computed by 2 raised to the power of 32. S0 + Ma

そしてこれらの作業を64回繰り返してハッシュ値を入れ替えることによってハッシュ値を導き出します。

These steps are then repeated 64 times to derive the hash value by swapping the hash values.

Python風にこのループを表すと以下のような図になります。括弧内は初期ハッシュ値とK(ラウンド定数)とW(メッセージスケジュール)。

The Python-like representation of this loop looks like this. The initial hash values, K (round constants) and W (message schedule) are shown in parentheses.

ではIPythonのコンソール画面に戻って、実際にスクリプトを書いて圧縮アルゴリズムの理解を深めましょう。

Let's go back to the IPython console screen and get started write a script to better understand the compression algorithm.

S1(Sigma1)の式を一行ずつ確かめてみましょう。

Then, let's examine the expression in S1 (Sigma1) line by line.

format(right_rotate(int(H[4], 2), 6, 32), '032b')
'11111101010001000011100101001001'
format(right_rotate(int(H[4], 2), 11, 32), '032b')
'01001111111010100010000111001010'
format(right_rotate(int(H[4], 2), 25, 32), '032b')
'10000111001010010011111110101000'

S1(Sigma1)の式をまとめた関数を作成しましょう。

Let's create a function that combines the expressions in S1 (Sigma1).

def sigma1(e):
    S1 = right_rotate(int(e, 2), 6, 32) \
        ^ right_rotate(int(e, 2), 11, 32) \
        ^ right_rotate(int(e, 2), 25, 32)
    return S1

この計算式にはハッシュ値eの値が使われます。初期ハッシュ値の配列の4番目の要素をeとういう名前の変数に代入して結果を確かめてみましょう。

This formula uses the value of the hash value e. Let's test the result by assigning the fourth element of the array of initial hash values to a variable named e.

e = H[4]
e
'01010001000011100101001001111111'

sigma1(e)
898049835

format(sigma1(e), '032b')
'00110101100001110010011100101011'

次にCh(Choose)の計算式で使われるハッシュ値e,f,gを変数として用意しましょう。

Next, let's take the hash values e, f, and g used in the formula for Ch (Choose) as variables.

f = H[5]
g = H[6]
e
'01010001000011100101001001111111'
f
'10011011000001010110100010001100'
g
'00011111100000111101100110101011'

Ch(Choose)の式を一行ずつ確かめてみましょう。

Then, let's examine the expression in Ch (Choose) line by line.

int(e, 2) & int(f, 2)
285491212
format(int(e, 2) & int(f, 2), '032b')
'00010001000001000100000000001100'

print("e      :", e)
print("f      :", f)
print("e and f:", format(int(e, 2) & int(f, 2), '032b'))
e      : 01010001000011100101001001111111
f      : 10011011000001010110100010001100
e and f: 00010001000001000100000000001100

ビット列に対してNOT演算をおこなう際に表示としてマイナス表記になってしまいます。

When the NOT operation is performed on the bits, the display becomes negative.

format(~ int(e, 2), '032b')
'-1010001000011100101001010000000'

なので分かりやすくする為にマスクを使用して正の数として表示できるようにしましょう。

So for clarity, use a mask to display positive numbers.

def bit_not(bits):
    num_of_bits = len(bits)
    mask = (1 << num_of_bits) - 1
    return mask ^ int(bits, 2)

format(bit_not(e), '032b')
'10101110111100011010110110000000'

print("e    :", e)
print("not e:", format(bit_not(e), '032b'))

print("not e      :", format(bit_not(e), '032b'))
print("g          :", g)
print("not e and g:", format(bit_not(e) & int(g, 2), '032b'))
not e      : 10101110111100011010110110000000
g          : 00011111100000111101100110101011
not e and g: 00001110100000011000100110000000
            

使われている関数やNOT演算に対する解説も動画シリーズのパート2からパート4あたりの動画を参考にしてください。

Also, see the videos in Parts 2 through 4 of the video series for an explanation of the functions used and NOT operations.

ではCh(Choose)の計算式を関数としてまとめましょう。

Then, let's summarize the formula for Ch (Choose) as a function.

def choose(e, f, g):
    return (int(e, 2) & int(f, 2)) ^ (bit_not(e) & int(g, 2))

ch = choose(e, f, g)
ch
528861580
format(ch, '032b')
'00011111100001011100100110001100'

ラウンド定数も先ほどのメッセージスケジュールの時と同様に、16進数表記から2進数表記の配列に変換しましょう。

As with the previous message scheduling, convert the round constants from hexadecimal notation to a binary notation array.

K = round_constants.copy()

K[0]
'0x428a2f98'
bin(int(K[0], 16))
'0b1000010100010100010111110011000'
format(int(K[0], 16), '032b')
'01000010100010100010111110011000'

K = [format(int(k, 16), '032b') for k in K]

ラウンド定数とメッセージスケジュールの配列要素0番目を使用して、圧縮ループ一回目を試してみましょう。

Try the first compression loop using the round constants and the 0 element of the message schedule array.

e, f, g, h = H[4:]
h
'01011011111000001100110100011001'

S1 = sigma1(e)
ch = choose(e, f, g)

K0 = K[0]
W0 = W[0] 

def temporary_one(h, S1, ch, Kt, Wt):
    return (int(h, 2) + S1 + ch + int(Kt, 2) + int(Wt, 2)) % (2 ** 32)

temp1 = temporary_one(h, S1, ch, K0, W0)

temp1
1541233108

format(temp1, '032b')
'01011011110111010101100111010100'

残りの圧縮ループのアルゴリズムのメソッドを作成していきましょう。

Let's write the remaining compression loop algorithm methods.

def sigma0(a):
    S0 = right_rotate(int(a, 2), 2, 32) \
        ^ right_rotate(int(a, 2), 13, 32) \
        ^ right_rotate(int(a, 2), 22, 32)
    return S0

def majority(a, b, c):
    return (int(a, 2) & int(b, 2)) \
            ^ (int(a, 2) & int(c, 2)) \
            ^ (int(b, 2) & int(c, 2))

def temporary_two(S0, maj):
    return (S0 + maj) % (2 ** 32)

temp1(temporary1)の式はKのt番目とWのt番目とハッシュhとS1とChを足して2の32乗で剰余計算したものです。h + S1 + ch + Kt + Wt

The expression for temp1 (temporary 1) is the sum of the t'th of K and the t'th of W, hash h, S1 and Ch. The summed values are modulo computed by 2 raised to the power of 32. h + S1 + ch + Kt + Wt

S0(Sigma0)の式はハッシュaに対してのビット演算です。(a right-rotate 2) xor (a right-rotate 13) xor (a right-rotate 22)

The expression S0 (Sigma0) is a bitwise operation on hash a. (a right-rotate 2) xor (a right-rotate 13) xor (a right-rotate 22)

Ma(Majority)の式はハッシュa,b,cに対してのビット演算です。(a and b) xor (a and c) xor (b and c)

The expression Ma (Majority) is a bitwise operation on hashes a, b, c. (a and b) xor (a and c) xor (b and c)

temp2(temporary2)の式はS0とMaを足して2の32乗で剰余計算したものです。S0 + Ma

The expression for temp2 (temporary 2) is the sum of S0 and Ma. The summed values are modulo computed by 2 raised to the power of 32. S0 + Ma

では初期ハッシュ値を使用して、圧縮ループ一回目を試してみましょう。

Now try the first compression loop using the initial hash values.

一回目のループで得られたtemp1とtemp2を組み合わせたハッシュ値を含む全てのハッシュ値はこのようにスワッピングされていきます。

All hash values, including the combined temp1 and temp2 hash values from the first loop, are swapped in this way.

a, b, c, d, e, f, g, h = H

S1 = sigma1(e)
ch = choose(e, f, g)

K0 = K[0]
W0 = W[0] 

temp1 = temporary_one(h, S1, ch, K0, W0)

S0 = sigma0(a)
maj = majority(a, b, c)
temp2 = temporary_two(S0, maj)

print('h[7] (h) <-', '(g)', g)
print('h[6] (g) <-', '(f)', f)
print('h[5] (f) <-', '(e)', e)
print('h[4] (e) <-', '(d + temp1)', format((int(d, 2) + temp1) % (2 ** 32), '032b'))
print('h[3] (d) <-', '(c)', c)
print('h[2] (c) <-', '(b)', b)
print('h[1] (b) <-', '(a)', a)
print('h[0] (a) <-', '(temp1 + temp2)', format((temp1 + temp2) % (2 ** 32), '032b'))

これを残り63回繰り返すわけですから、最終的なハッシュ値の予想は難しい理由が理解できるでしょう。

This is repeated 63 more times, so you can see why the final hash value is hard to predict.

では圧縮ループを関数にしましょう。

Let's turn the compression loop into a function.

ではそれぞれの変数や定数の中身を確認してみましょう。

Let's examine the contents of each variable and constant.

初期ハッシュ値と最終的なハッシュ値の中身を比べてみましょう。

Compare the contents of the initial and final hash values.

後は初期ハッシュ値と最終的なハッシュ値とを足し合わせるだけです。

All that remains is to add the initial hash values and the final hash values together.

もちろんそれらの値にも2の32乗の剰余計算を適用して32ビットにする必要があります。

Of course, you need to apply remainder calculation of 2 raised to the power of 32 to those values to get 32 bits.

いつものように上記の内容を関数としてまとめてみましょう。

As always, let's summarize the above as a function.

pythonのビルトインモジュールのhashlibモジュールのsha256メソッドを使って、値が正しいかどうかテストしてみましょう。

Let's test that the value is correct using the sha256 method in the hashlib module of the python built-in module.

では今までの内容の全てを複数の関数としてまとめてみましょう。

Let's summarize all of this into multiple functions.

色々な文字列を入力して試してみましょう。

Try typing different strings.

一応成功しましたが、入力される文字列が512ビットを越える場合はどうなるでしょうか？

It was successful, but what if the input string exceeds 512 bits?

今回は512ビットを超えた文字列に対応していないので、当然テストは失敗します。

This time it does not support strings longer than 512 bits, so of course the test will fail.

W（メッセージスケジュール）の中身を確認してみましょう。

Let's check the contents of W (message schedule).

解決策としては複数のメッセージブロック、そしてW（メッセージスケジュール）を作成する必要があります。

The solution is to create multiple message blocks and a W (message schedule).

では、画像ファイル等を読み込んだと仮定して、文字列ではなくバイナリデータならどうなるか試してみましょう。

Now, let's assume that you've loaded an image file or something, and see what happens with binary data instead of strings.

このように、バイナリデータにも対応していないので、当然テストは失敗します。

Thus, binary data is not supported, so of course the test will fail.

以上です。お疲れ様です。

That's all. Thank you for your hard work.