どうも金ないニカチュウと申します。
Pythonでimportを用いずにSHA256のハッシュを計算するプログラムを書きました。
hashlib
PythonでSHA256のハッシュを計算するには偉大な hashlib ライブラリを用いるのが簡単。
1>>> import hashlib
2>>> hashlib.sha256(b"note.nikachu.net").hexdigest()
3'f3bb10e2172099a8a6425ef9c77ccfe5101e440c713e3b8e2362c0d748342af0'まあこんなライブラリで楽するのは良くないですね。
私の学校の教員も言っていました。
楽しちゃダメだから
— 某高専某教員
フルスクラッチ
以下に紹介するプログラムを用いて何が起きても責任は負いません
信頼性が必要ならhashlibを用いてください
SHA256の仕様は以下のPDFに記載されている。
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
まずはH, Kを用意する。
1H: list[int] = [
2 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19
3]
4
5K: list[int] = [
6 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,
7]次に使う関数を定義する。
1def Ch(x, y, z) -> int:
2 return (x & y) ^ (~x & z)
3
4
5def Maj(x, y, z) -> int:
6 return (x & y) ^ (x & z) ^ (y & z)
7
8
9def Rotr(x: int, n: int) -> int:
10 return (x << (32 - n)) & 0xFFFFFFFF | (x >> n)
11
12
13def Shr(x: int, n: int) -> int:
14 return x >> n
15
16
17def SmallSigma0(x: int) -> int:
18 return Rotr(x, 7) ^ Rotr(x, 18) ^ Shr(x, 3)
19
20
21def SmallSigma1(x: int) -> int:
22 return Rotr(x, 17) ^ Rotr(x, 19) ^ Shr(x, 10)
23
24
25def LargeSigma0(x: int) -> int:
26 return Rotr(x, 2) ^ Rotr(x, 13) ^ Rotr(x, 22)
27
28
29def LargeSigma1(x: int) -> int:
30 return Rotr(x, 6) ^ Rotr(x, 11) ^ Rotr(x, 25)右ローテートや右シフトなどは普通だが、加算や左シフトを行う場合気を付ける点がある。
Pythonの整数型は精度が無限(何桁でも保持できる)ので、32ビットで表せる範囲を超えてしまう可能性があるため、0xFFFFFFFF(0b1が32ビット分)でマスクして範囲を超えないようにしている。
メッセージブロックを生成
まずは、データの次に入力直後の0x80、末尾8バイトにデータのビット数を入れ、総バイト数が64バイトの倍数になるように調整する関数を作る。
1def padding(message: bytes) -> bytes:
2 meslen = len(message)
3
4 nullPadding = b"\x00" * (55 - (meslen % 64))
5
6 return message + b"\x80" + nullPadding + (meslen * 8).to_bytes(8, byteorder="big")次に64バイトごとの配列に分割する関数を作る。
1def split(input: bytes) -> list[bytes]:
2 buf: list[bytes] = []
3
4 for i in range(-(-len(input) // 64)):
5 buf.append(input[64 * i : (64 * i) + 64])
6
7 return bufこのようにしてメッセージブロックを生成する。
1inputData = "note.nikachu.net"
2
3pad = padding(inputData.encode())
4messageBlocks = split(pad)メッセージスケジュールを生成
次はメッセージブロックからメッセージスケジュールを生成する。
まずはバイト列を4バイト(32ビット)ごとint配列に変換する関数を実装する。
1def toIntArray(b: bytes) -> list[int]:
2 temp: list[int] = []
3
4 for i in range(len(b) // 4):
5 temp.append(int.from_bytes(b[i * 4 : i * 4 + 4], byteorder="big"))
6 return tempまた、以下からのコードはメッセージブロックごとに行う。
1for i in messageBlocks:メッセージスケジュールは、本来32bit*64=256バイトとなる。
メッセージブロックをint配列に変換しても、64バイト分しかないため、残りを計算する。
1 words = toIntArray(i)
2
3 for j in range(16, 64):
4 w = (SmallSigma1(words[j - 2]) + words[j - 7] + SmallSigma0(words[j - 15]) + words[j - 16]) & 0xFFFFFFFF
5 words.append(w)これでメッセージスケジュールが生成できた。
ローテーション処理
次にローテーション処理を行う。
1 a, b, c, d, e, f, g, h = H
2
3 for t, w in enumerate(words):
4 t1 = (h + LargeSigma1(e) + Ch(e, f, g) + K[t] + w) & 0xFFFFFFFF
5 t2 = (LargeSigma0(a) + Maj(a, b, c)) & 0xFFFFFFFF
6
7 h = g
8 g = f
9 f = e
10 e = (d + t1) & 0xFFFFFFFF
11 d = c
12 c = b
13 b = a
14 a = (t1 + t2) & 0xFFFFFFFF中間ハッシュ値の更新
1 H[0] = (a + H[0]) & 0xFFFFFFFF
2 H[1] = (b + H[1]) & 0xFFFFFFFF
3 H[2] = (c + H[2]) & 0xFFFFFFFF
4 H[3] = (d + H[3]) & 0xFFFFFFFF
5 H[4] = (e + H[4]) & 0xFFFFFFFF
6 H[5] = (f + H[5]) & 0xFFFFFFFF
7 H[6] = (g + H[6]) & 0xFFFFFFFF
8 H[7] = (h + H[7]) & 0xFFFFFFFFここまでの操作を全メッセージブロックに対して行う。
ハッシュ値の出力
1for i in H:
2 print(f"{i:04x}", end="")実行すると、以下のようにハッシュを取得できた。
1f3bb10e2172099a8a6425ef9c77ccfe5101e440c713e3b8e2362c0d748342af0全コード
コード全体
1def Ch(x, y, z) -> int:
2 return (x & y) ^ (~x & z)
3
4
5def Maj(x, y, z) -> int:
6 return (x & y) ^ (x & z) ^ (y & z)
7
8
9def Rotr(x: int, n: int) -> int:
10 return (x << (32 - n)) & 0xFFFFFFFF | (x >> n)
11
12
13def Shr(x: int, n: int) -> int:
14 return x >> n
15
16
17def SmallSigma0(x: int) -> int:
18 return Rotr(x, 7) ^ Rotr(x, 18) ^ Shr(x, 3)
19
20
21def SmallSigma1(x: int) -> int:
22 return Rotr(x, 17) ^ Rotr(x, 19) ^ Shr(x, 10)
23
24
25def LargeSigma0(x: int) -> int:
26 return Rotr(x, 2) ^ Rotr(x, 13) ^ Rotr(x, 22)
27
28
29def LargeSigma1(x: int) -> int:
30 return Rotr(x, 6) ^ Rotr(x, 11) ^ Rotr(x, 25)
31
32
33H: list[int] = [0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19]
34
35
36K: list[int] = [
37 0x428A2F98,
38 0x71374491,
39 0xB5C0FBCF,
40 0xE9B5DBA5,
41 0x3956C25B,
42 0x59F111F1,
43 0x923F82A4,
44 0xAB1C5ED5,
45 0xD807AA98,
46 0x12835B01,
47 0x243185BE,
48 0x550C7DC3,
49 0x72BE5D74,
50 0x80DEB1FE,
51 0x9BDC06A7,
52 0xC19BF174,
53 0xE49B69C1,
54 0xEFBE4786,
55 0x0FC19DC6,
56 0x240CA1CC,
57 0x2DE92C6F,
58 0x4A7484AA,
59 0x5CB0A9DC,
60 0x76F988DA,
61 0x983E5152,
62 0xA831C66D,
63 0xB00327C8,
64 0xBF597FC7,
65 0xC6E00BF3,
66 0xD5A79147,
67 0x06CA6351,
68 0x14292967,
69 0x27B70A85,
70 0x2E1B2138,
71 0x4D2C6DFC,
72 0x53380D13,
73 0x650A7354,
74 0x766A0ABB,
75 0x81C2C92E,
76 0x92722C85,
77 0xA2BFE8A1,
78 0xA81A664B,
79 0xC24B8B70,
80 0xC76C51A3,
81 0xD192E819,
82 0xD6990624,
83 0xF40E3585,
84 0x106AA070,
85 0x19A4C116,
86 0x1E376C08,
87 0x2748774C,
88 0x34B0BCB5,
89 0x391C0CB3,
90 0x4ED8AA4A,
91 0x5B9CCA4F,
92 0x682E6FF3,
93 0x748F82EE,
94 0x78A5636F,
95 0x84C87814,
96 0x8CC70208,
97 0x90BEFFFA,
98 0xA4506CEB,
99 0xBEF9A3F7,
100 0xC67178F2,
101]
102
103
104def padding(message: bytes) -> bytes:
105 meslen = len(message)
106
107 nullPadding = b"\x00" * (55 - (meslen % 64))
108
109 return message + b"\x80" + nullPadding + (meslen * 8).to_bytes(8, byteorder="big")
110
111
112def split(input: bytes) -> list[bytes]:
113 buf: list[bytes] = []
114
115 for i in range(-(-len(input) // 64)):
116 buf.append(input[64 * i : (64 * i) + 64])
117
118 return buf
119
120
121def toIntArray(b: bytes) -> list[int]:
122 temp: list[int] = []
123
124 for i in range(len(b) // 4):
125 temp.append(int.from_bytes(b[i * 4 : i * 4 + 4], byteorder="big"))
126 return temp
127
128
129inputData = "note.nikachu.net"
130
131pad = padding(inputData.encode())
132messageBlocks = split(pad)
133
134for i in messageBlocks:
135 words = toIntArray(i)
136
137 for j in range(16, 64):
138 w = (SmallSigma1(words[j - 2]) + words[j - 7] + SmallSigma0(words[j - 15]) + words[j - 16]) & 0xFFFFFFFF
139 words.append(w)
140
141 for k in words:
142 print(f"{k:032b}")
143
144 a, b, c, d, e, f, g, h = H
145
146 for t, w in enumerate(words):
147 t1 = (h + LargeSigma1(e) + Ch(e, f, g) + K[t] + w) & 0xFFFFFFFF
148 t2 = (LargeSigma0(a) + Maj(a, b, c)) & 0xFFFFFFFF
149
150 h = g
151 g = f
152 f = e
153 e = (d + t1) & 0xFFFFFFFF
154 d = c
155 c = b
156 b = a
157 a = (t1 + t2) & 0xFFFFFFFF
158
159 H[0] = (a + H[0]) & 0xFFFFFFFF
160 H[1] = (b + H[1]) & 0xFFFFFFFF
161 H[2] = (c + H[2]) & 0xFFFFFFFF
162 H[3] = (d + H[3]) & 0xFFFFFFFF
163 H[4] = (e + H[4]) & 0xFFFFFFFF
164 H[5] = (f + H[5]) & 0xFFFFFFFF
165 H[6] = (g + H[6]) & 0xFFFFFFFF
166 H[7] = (h + H[7]) & 0xFFFFFFFF
167
168for i in H:
169 print(f"{i:04x}", end="")