Published Date : 2021年8月11日4:14
ニコニコ動画にアップした動画のまとめ記事です。
This is a summary blog post about a video I uploaded to NicoNico.
細かい部分は動画を参考にしてください。
Please refer to the video for details.
目次
Table of Contents
前回の続きです。
Continued from last time.
前回までの動画で、文字列をバイナリ文字列に変換し、512ビットのメッセージブロックを作成しました。
In my previous video, we converted a string to a binary string and created a 512 bit message block.
そして、初期ハッシュ値とラウンド定数を作成しました。
We then created initial hash values and round constants.
これら一連の作業の流れを復習するために、前回のスクリプトをまとめてみましょう。
To review this sequence of tasks, let's summarize the previous scripts.
import math
import textwrap
import sympy
import numpy as np
input_str = "hello world"
converted_str = [format(ord(c), '08b') for c in input_str]
padded = converted_str.copy()
padded.append('1')
num_zeros = 512 - 64 - (((len(padded) - 1) * 8) + 1)
for i in range(math.ceil(num_zeros / 8)):
if len(padded[-1]) != 8:
padded[-1] += '0' * (8 - len(padded[-1]))
else:
padded.append('0' * 8)
len_bitstr = format(len(converted_str) * 8, '064b')
n = 8
padded.extend([len_bitstr[i * n:(i + 1) * n] for i in range(len(len_bitstr) // n)])
init_hash_values = []
num_primes = 8
n = 0
while len(init_hash_values) < num_primes:
if sympy.isprime(n):
f, i = math.modf(math.sqrt(n))
init_hash_values.append(hex(int(f * (2 ** 32))))
n += 1
round_constants = []
num_primes = 64
n = 0
while len(round_constants) < num_primes:
if sympy.isprime(n):
f, i = math.modf(np.cbrt(n))
round_constants.append("0x" + format(int(f * (2 ** 32)), '08x'))
n += 1
init_hash_values
['0x6a09e667',
'0xbb67ae85',
'0x3c6ef372',
'0xa54ff53a',
'0x510e527f',
'0x9b05688c',
'0x1f83d9ab',
'0x5be0cd19']
textwrap.wrap(" ".join(round_constants), width=89)
['0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 0x3956c25b 0x59f111f1 0x923f82a4 0xab1c5ed5',
'0xd807aa98 0x12835b01 0x243185be 0x550c7dc3 0x72be5d74 0x80deb1fe 0x9bdc06a7 0xc19bf174',
'0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc 0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f988da',
'0x983e5152 0xa831c66d 0xb00327c8 0xbf597fc7 0xc6e00bf3 0xd5a79147 0x06ca6351 0x14292967',
'0x27b70a85 0x2e1b2138 0x4d2c6dfc 0x53380d13 0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85',
'0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 0xd192e819 0xd6990624 0xf40e3585 0x106aa070',
'0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 0x391c0cb3 0x4ed8aa4a 0x5b9cca4f 0x682e6ff3',
'0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208 0x90befffa 0xa4506ceb 0xbef9a3f7 0xc67178f2']
ではメッセージスケジュールをメッセージブロックから作成しましょう。
Let's create a message schedule from a message block.
メッセージスケジュールは全部で64個の32ビットのバイナリになります。
The message schedule consists of 64 32 bit binaries.
つまりこの64個のバイナリと64個のラウンド定数を使用して64回初期ハッシュ値をバイナリ操作することによって、最終的なアウトプットのハッシュ値を得ることができるのです。
In other words, using these 64 binaries and 64 round constants, you can binary-manipulate the initial hash values 64 times to get the final output hash value.
メッセージブロックの配列の各要素は8ビットになっているので、4つずつ抜き出して32ビットのバイナリ文字列になるようにしましょう。
Each element of the message block array is 8 bits, so pull out 4 at a time to get a 32 bit binary string.
For LoopとPrint関数を使ってメッセージブロックから要素を4つずつ取り出す方法を考えてみましょう。
Consider how to use the For-Loop and print function to retrieve four elements from a message block.
これでメッセージブロックを32ビットずつのバイナリ文字列の配列に変換することができました。
You can now convert the message block to an array of binary strings, 32 bits each.
この配列は全部で16個の要素があります。配列の要素のインデックス番号は0から15までです。
This array has a total of 16 elements. The array elements are indexed from 0 to 15.
そして最後に配列の要素数が全部で64個になるように、32ビットのゼロでパディングしていきます。
Finally, the array is padded with 32 bit zeros so that it contains 64 elements.
これでメッセージスケジュールの初期値を作成することができました。
You have now created initial values for the message schedule.
これがメッセージスケジュールを作る時のアルゴリズムです。
This is the algorithm for creating message schedules.
右ロテートや右シフト等の基本的な考え方はこの動画シリーズの第二回から第四回を見て復習してください。
See Part 2 through Part 4 of this video series for a review of the basic concepts of right rotation and right shift.
それではまずs0の値がどのように作られるかを[i-15]番目の配列要素(一番最初は[16-15]で1番目)で確かめてみましょう。
Let's start with the [i-15]th array element (The first element is 16 minus 15, so the index number is 1.) to see how the value of s0 is constructed.
ここで第四回目の動画（ロテートシフト操作編）で使用したライトロテート関数を使います。
Here, use the right rotate function used in the fourth video (Rotate Shift Operation).
def right_rotate(bits, shift_num, num_of_bits):
shift_num = shift_num % num_of_bits
mask = (1 << num_of_bits) - 1
difference = num_of_bits - shift_num
return (bits >> shift_num) | ((bits << difference) & mask)
もちろん0ビッツに右ロテートや右シフトをしても0ビッツのままです。
Of course, it remains 0 bits even if you right-rotate or right-shift to 0 bits.
その為このs1の値は0ビッツになります。
Therefore, the value of s1 is 0 bits.
後でやり直しがきくようにメッセージスケジュールをコピーしておきましょう。
Make a copy of your message schedule so you can redo it later.
一回目のループの合計値を表示してみましょう。
Let's display the total value of the first loop.
しかし、今回の値は33ビットになっています。
However, this time the value is 33 bits.
この値を32ビットにする為には[2の32乗]で剰余演算をして32ビットを越えないようにします。
To make this value 32 bits, do a remainder operation with [2 to the 32 power] so that it does not exceed 32 bits.
スクリプトを一行ずつ書いていけば、[2の32乗]で剰余演算をするということについての理解が深まります。
If you write the script line by line, you'll get a better understanding of the modulo operation with [2 to the 32 power].
2**32 4294967296 (4294967296 - 1) % 4294967296 4294967295 4294967296 % 4294967296 0 (4294967296 + 1) % 4294967296 1
このように32ビットで剰余演算を行うということは、32ビット(整数なら4294967296)で割った数の余りが取り出されることになります。
Doing a remainder operation on 32 bits in this way means taking the remainder of a number divided by 32 bits (or 4294967296 if it is an integer).
これを整数ではなくビットの文字列で見ると32ビットを越えたビットが削られていることに気付くはずです。
If you look at this as a string of bits rather than integers, you will notice that greater than 32 bits have been trimmed.
format(2 ** 32 + 1, '032b') '100000000000000000000000000000001' format((2 ** 32 + 1) % (2 ** 32), '032b') '00000000000000000000000000000001' format(2 ** 32 + 2147483649, '032b') '110000000000000000000000000000001' len(format(2 ** 32 + 2147483649, '032b')) 33 (2 ** 32 + 2147483649) % (2 ** 32) 2147483649 format((2 ** 32 + 2147483649) % (2 ** 32), '032b') '10000000000000000000000000000001' len(format((2 ** 32 + 2147483649) % (2 ** 32), '032b')) 32
では先ほどのメッセージスケジュール作成手順に戻って、それを確認してみましょう。
Let's go back to the procedure for creating a message schedule and check it.
このように最初のループでは配列の16番目の要素に新しくビット列が加わりました。
Therefore, the first loop added a new bit string to the 16th element of the array.
これらの作業を配列の16番目から最後（63番目の要素）まで繰り返します。
Repeat these steps from the 16th to the end (63rd element) of the array.
ではこれらの作業をまとめた関数を用意して、実際にメッセージスケジュールを作成しましょう。
Now let's create a function that summarizes these tasks, then use that function to actually create a message schedule.
W = create_message_schedule(message_schedule)
textwrap.wrap(" ".join(W), width=(32*2)+(2-1))
['01101000011001010110110001101100 01101111001000000111011101101111',
'01110010011011000110010010000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000000000000',
'00000000000000000000000000000000 00000000000000000000000001011000',
'00110111010001110000001000110111 10000110110100001100000000110001',
'11010011101111010001000100001011 01111000001111110100011110000010',
'00101010100100000111110011101101 01001011001011110111110011001001',
'00110001111000011001010001011101 10001001001101100100100101100100',
'01111111011110100000011011011010 11000001011110011010100100111010',
'10111011111010001111011001010101 00001100000110101110001111100110',
'10110000111111100000110101111101 01011111011011100101010110010011',
'00000000100010011001101101010010 00000111111100011100101010010100',
'00111011010111111110010111010110 01101000011001010110001011100110',
'11001000010011100000101010011110 00000110101011111001101100100101',
'10010010111011110110010011010111 01100011111110010101111001011010',
'11100011000101100110011111010111 10000100001110111101111000010110',
'11101110111011001010100001011011 10100000010011111111001000100001',
'11111001000110001010110110111000 00010100101010001001001000011001',
'00010000100001000101001100011101 01100000100100111110000011001101',
'10000011000000110101111111101001 11010101101011100111100100111000',
'00111001001111110000010110101101 11111011010010110001101111101111',
'11101011011101011111111100101001 01101010001101101001010100110100',
'00100010111111001001110011011000 10101001011101000000110100101011',
'01100000110011110011100010000101 11000100101011001001100000111010',
'00010001010000101111110110101101 10110000101100000001110111011001',
'10011000111100001100001101101111 01110010000101111011100000011110',
'10100010110101000110011110011010 00000001000011111001100101111011',
'11111100000101110100111100001010 11000010110000101110101100010110']
メッセージスケジュールが作られる過程を見てみましょう。
Let's see the process of message schedule being made.
w = message_schedule.copy()
input('Initial Message Schedule: ')
print(textwrap.fill(" ".join(w), width=(32*2)+(2-1)))
for i in range(16, 64):
input(f"w[{i-15}] right-rotate 7.")
print(format(right_rotate(int(w[i-15], 2), 7, 32), '032b'))
input(f"w[{i-15}] right-rotate 18.")
print(format(right_rotate(int(w[i-15], 2), 18, 32), '032b'))
input(f"w[{i-15}] right-shift 3.")
print(format(int(w[i-15], 2) >> 3, '032b'))
s0 = right_rotate(int(w[i-15], 2), 7, 32) \
^ right_rotate(int(w[i-15], 2), 18, 32) \
^ int(w[i-15], 2) >> 3
input("s0 = ")
print(format(right_rotate(int(w[i-15], 2), 7, 32), '032b'))
print("+")
print(format(right_rotate(int(w[i-15], 2), 18, 32), '032b'))
print("+")
print(format(int(w[i-15], 2) >> 3, '032b'))
print("=")
print(format(s0, '032b'))
input(f"w[{i-2}] right-rotate 17.")
print(format(right_rotate(int(w[i-2], 2), 17, 32), '032b'))
input(f"w[{i-2}] right-rotate 19.")
print(format(right_rotate(int(w[i-2], 2), 19, 32), '032b'))
input(f"w[{i-2}] right-shift 10.")
print(format(int(w[i-2], 2) >> 10, '032b'))
s1 = right_rotate(int(w[i-2], 2), 17, 32) \
^ right_rotate(int(w[i-2], 2), 19, 32) \
^ int(w[i-2], 2) >> 10
input("s1 = ")
print(format(right_rotate(int(w[i-2], 2), 17, 32), '032b'))
print("+")
print(format(right_rotate(int(w[i-2], 2), 19, 32), '032b'))
print("+")
print(format(int(w[i-2], 2) >> 10, '032b'))
print("=")
print(format(s1, '032b'))
w[i] = format((int(w[i-16], 2) + s0 + int(w[i-7], 2) + s1) % (2 ** 32), '032b')
# 現在のメッセージスケジュール (i番目のループ)
input(f"Current Message Schedule. ({i - 15}th loop) (Elements of w[{i}])")
print(textwrap.fill(" ".join(w), width=(32*2)+(2-1)))
以上です。お疲れ様です。
That's all. Thank you for your hard work.