目次
この記事は、 SHA256を計算する in Pythonのステップ4です。
ステップ3までで、変換で多用する関数を定義しました。 ここでは、それらの関数を使って SHA-256 を計算します。 ただ文字列の変換には追加で関数を定義します。
ビット配列への変換
SHA-256 は、 ある特定の長さ以下のビット列をハッシュ化できます。 しかしビット列を作ってテストしていくのもやりにくい気がするので、テキストからビット列にする関数を定義しておきます。 今回の実装では、ビット列を表すのに 0 と 1 でできた文字列を使いました。
|
1 2 3 4 5 6 7 |
def message_to_bitstring(message): bitstring = "" for char in message: # ASCII コードを 8 ビットのビット列に変換する bit = bin(ord(char))[2:].zfill(8) bitstring += bit return bitstring |
入力は ASCII 文字列 を前提としています。 バイト列への変換さえできればいいので、原理的には UTF-8 でもなんでもハッシュにできます。
ワードへの変換
SHA-256 では、 ビット演算を始める前に、 受け取ったメッセージを ブロックに分け、 その後でブロックをワードに分けます。 そのための関数を定義しておきます。
メッセージの補完
SHA-256 では受け取ったビット列に情報を加えます。 受け取ったメッセージの最後に1を加えた後、メッセージ全体の長さが (512の倍数 – 64) bit になるように末尾に0を加えます。 64 bit はメッセージの長さ (数値) を加えるためのスペースです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def padding(bitstring): # メッセージの長さを保存する length = len(bitstring) # メッセージの末尾に 1 ビットの 1 を追加する bitstring += "1" # メッセージの長さが 448 mod 512 になるまで 0 ビットを追加する remainder = len(bitstring) % 512 bitstring += "0" * ((448 - remainder) + (remainder > 448) * 512) # メッセージの長さを 64 ビットのビット列に変換し、メッセージの末尾に追加する bitstring += bin(length)[2:].zfill(64) # この時点で、 448 + 64 = 512 ビットになっている # 64 bit で表される数値の最大値は 2^64 - 1 = 18446744073709551615 であり # これを超えるメッセージは SHA-256 でハッシュ化できない # 厳密には 2^64 - 1 - 1 - 64 = 18446744073709551550 ビットまでしかハッシュ化できない return bitstring |
メッセージブロックへの分割
入力メッセージの長さが、 ビット単位で 512 の倍数になったところで、 1ブロックが 512 bit のメッセージブロックへ変換します。
|
1 2 3 4 5 6 7 |
def split_blocks(bitstring, block_size=512): blocks = [] # ビット列を 512 ビットずつに切り出す for i in range(0, len(bitstring), block_size): block = bitstring[i:i+block_size] blocks.append(block) return blocks |
ワードへの分割
512 bit のメッセージブロック列を、 32-bit の word 16個 に変換します。
|
1 2 3 4 5 6 7 |
def split_words(block, w=32): words = [] # ブロックを 32 ビットずつに切り出す for i in range(0, len(block), w): word = block[i:i+w] words.append(word) return words |
固定値の計算
暗号化に使用するための固定数値を計算しておきます。 ここで計算するのは、 素数の3乗根の小数部分32ビットです。 PDFでは、16新数で表記しているので、文字列のように見えますが、数値としてしか利用しないのでここで数値に変換しています。 K はPDFに使われていた文字をそのまま使った変数名です。
ここで計算するのは K のみで、 H は計算しません。 今回は H の値を更新しながら Hash を計算するプログラムにするので、 SHA-256 を生成する中で、 初期値 H を計算します。
|
1 2 3 4 5 6 7 8 9 |
p = Prime() # cube roots of first 64 primes K = list( map( lambda x: ValueConversion.hex_to_integer(ValueConversion.decimal_hex_digits(curt(x))), p.numbers(64) ) ) |
SHA-256 の計算
ビット列を受け取ってSHA256を計算する関数を作ります。 受け取ったビット列を補完した後、512ビットのブロックごとにHを更新し、最後のHの値を繋ぎ合わせて最終的な値にします。 ここでは最終結果を16進数で表すことにしました。
|
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 48 49 50 51 52 53 54 55 56 57 |
def sha256(bitstring: str): """ calculate sha256 hash value >>> text = "Python" >>> a = sha256(message_to_bitstring(text)) >>> import hashlib >>> b = hashlib.sha256(text.encode('ascii')).hexdigest() >>> a == b True >>> text = "Hello" * 100 >>> a = sha256(message_to_bitstring(text)) >>> import hashlib >>> b = hashlib.sha256(text.encode('ascii')).hexdigest() >>> a == b True :param bitstring: :return: """ global K, p H = list(map(lambda x: ValueConversion.hex_to_integer(ValueConversion.decimal_hex_digits(sqrt(x))), p.numbers(8))) w = 32 bitstring = padding(bitstring) M = split_blocks(bitstring) for m in M: W = list(map(lambda x: ValueConversion.bitstring_to_integer(x), split_words(m))) for t in range(16, 64): W.append( (sig_1(W[t - 2]) + W[t - 7] + sig_0(W[t - 15]) + W[t - 16]) % (2 ** w) ) a, b, c, d, e, f, g, h = H for t in range(64): T1 = (h + sum_1(e) + ch(e, f, g) + K[t] + W[t]) % (2 ** w) T2 = (sum_0(a) + maj(a, b, c)) % (2 ** w) h = g g = f f = e e = (d + T1) % (2 ** w) d = c c = b b = a a = (T1 + T2) % (2 ** w) H = list(map( lambda x: x % (2 ** w), [a + H[0], b + H[1], c + H[2], d + H[3], e + H[4], f + H[5], g + H[6], h + H[7]] )) return "".join(ValueConversion.integer_to_hexstring(h, 8) for h in H) |
この関数内では、 H をまず計算しています。 H は 素数の2乗根の小数部分32ビットです。 変数名はPDFに使われていた文字をそのまま使っています。
1つのブロックを64個の32ビットワードに分割します。 ブロックは16ワードでできているので、64個のワードのうち、最初の16個はブロックを単純に分割したものです。 17〜64番目のワードは \(W_t = \sigma_1^{256} (W_{t-2}) + W_{t-7} + \sigma_0^{256} (W_{t-15}) + W_{t-16}\) によって計算されます。
a, b, c, d, e, f, g, h へ H の値を代入します。 そして t in range(64) について、 T1, T2, a, b, c ,d, e, f, g, h を計算します。 T1, T2 を大文字にしているのは、 PDF に大文字で記載されていたからで、他意はありません。
この更新の後で、 a, b, c, d, e, f, g, h と H を使って H を更新します。 H を更新する式を見ると、 a, b, c, d, e, f, g, h も配列にした方が良かったように見えますが、 PDFと同じ記号を使用することを重視したので配列を使いませんでした。
最後に H を 16進数文字列にして結合すると SHA-256 の完成です。
