暗号の世界はわかりづらい。3DES は DES より強力だが 2DES は大した強度にならないことが知られていたりする。
Wikipedia によると「SHA-2は、Secure Hash Algorithmシリーズの暗号学的ハッシュ関数」となっている。計算方法は単純なので Python での実装はそう難しくない。
終端ブロックに完全に対応しておらず、いささかやっつけ感があるがソースを示そう。
sha256_func.py
from polyphony import testbench, module, is_worker_running
from polyphony import rule
_k = [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]
_h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
def rotr(x, y):
return ((x >> y) | (x << (32 - y))) & 0xFFFFFFFF
def _sha256(msg, _h, w):
for i in range(16):
w[i] = msg[i]
for i in range(16, 64):
wi_15 = w[i - 15]
s0 = rotr(wi_15, 7) ^ rotr(wi_15, 18) ^ (wi_15 >> 3)
wi_2 = w[i - 2]
s1 = rotr(wi_2, 17) ^ rotr(wi_2, 19) ^ (wi_2 >> 10)
wi_16 = w[i - 16]
wi_7 = w[i - 7]
w[i] = (wi_16 + s0 + wi_7 + s1) & 0xFFFFFFFF
a = _h[0]
b = _h[1]
c = _h[2]
d = _h[3]
e = _h[4]
f = _h[5]
g = _h[6]
h = _h[7]
for i in range(64):
s0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
maj = (a & b) ^ (a & c) ^ (b & c)
t2 = s0 + maj
s1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
ch = (e & f) ^ ((~e) & g)
t1 = h + s1 + ch + _k[i] + w[i]
h = g
g = f
f = e
e = (d + t1) & 0xFFFFFFFF
d = c
c = b
b = a
a = (t1 + t2) & 0xFFFFFFFF
_lst = [a, b, c, d, e, f, g, h]
for i in range(8):
_h[i] = (_h[i] + _lst[i]) & 0xFFFFFFFF
def sha256(msg, h):
for i in range(len(_h)):
h[i] = _h[i]
work = [None] * 64
_sha256(msg, h, work)
tail_blk = [0] * 16
tail_blk[0] = 0x80000000
tail_blk[15] = 0x00000200
_sha256(tail_blk, h, work)
@testbench
def test():
msg_lst = [0x61616161] * 16
h = [None] * 8
sha256(msg_lst, h)
for i in h:
print(i)
# print('R {:08x}'.format(i))
test()
sha256 を実際に作ってみてわかるのは並列計算ができない点にある。１つのブロックを全部計算してからでないと次のブロックの計算ができない。暗号に関連するコードだけにそのように設計されているようだ。したがって、処理時間は単純にブロック数に比例するだろう。
ソース上は 32bit の配列(リスト)をつかうようになっている。Polyphony では 32bit より広いビット数の値を扱うことが出来る。デフォルトでは 128bit まで扱えるが、無理矢理、コンパイラの中身をちょっと変えることで 256bit や 512bit も扱うことが出来る。
sha256.py
from polyphony import testbench, module, is_worker_running
from polyphony.typing import bit, bit512, bit256, bit32, uint3, uint4, List
from polyphony.io import Port, Queue
from polyphony.timing import clksleep, clkfence, wait_rising, wait_falling
from polyphony import rule
k = [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]
h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
def bit32x8_bit256(lst:List[bit32])->bit256:
rv256:bit256
rv256 = 0
for i in range(8):
rv256 <<= 32
rv256 |= lst[i]
return rv256
def bit32x16_bit512(lst:List[bit32], start_i = 0)->bit512:
rv512:bit512
rv512 = 0
#print('start_i', start_i)
for i in range(16):
rv512 <<= 32
rv512 |= lst[start_i]
start_i += 1
#print('end start_i', start_i)
return rv512
def rotr(x, y):
return ((x >> y) | (x << (32 - y))) & 0xFFFFFFFF
@module
class sha256:
def __init__(self):
self.data_in = Queue(bit512, 'in')
self.data_out = Queue(bit256, 'out')
self.append_worker(self.process_sha256)
def process_sha256(self):
work = [0] * 64 # type: List[bit32]
_h = [0] * 8 # type: List[bit32]
__h = [0] * 8 # type: List[bit32]
while is_worker_running():
update = True
for i in range(8):
_h[i] = h[i]
block_len512:bit512 = self.data_in.rd()
block_len32 = block_len512
count = 0
#print(block_len512)
#print(block_len32)
while count < block_len32:
#print(count, block_len32)
count += 1
#print("--=========")
d512 = self.data_in.rd()
shift_n = 480
with rule(unroll='full'):
for i in range(16):
work[i] = (d512 >> shift_n) & 0xFFFFFFFF
shift_n -= 32
for i in range(16, 64):
wi_15 = work[i - 15]
s0 = rotr(wi_15, 7) ^ rotr(wi_15, 18) ^ (wi_15 >> 3)
wi_2 = work[i - 2]
s1 = rotr(wi_2, 17) ^ rotr(wi_2, 19) ^ (wi_2 >> 10)
wi_16 = work[i - 16]
wi_7 = work[i - 7]
work[i] = (wi_16 + s0 + wi_7 + s1) & 0xFFFFFFFF
for i in range(8):
__h[i] = _h[i]
for i in range(64):
s0 = rotr(__h[0], 2) ^ rotr(__h[0], 13) ^ rotr(__h[0], 22)
maj = (__h[0] & __h[1]) ^ (__h[0] & __h[2]) ^ (__h[1] & __h[2])
t2 = s0 + maj
s1 = rotr(__h[4], 6) ^ rotr(__h[4], 11) ^ rotr(__h[4], 25)
ch = (__h[4] & __h[5]) ^ ((~__h[4]) & __h[6])
t1 = __h[7] + s1 + ch + k[i] + work[i]
__h[7] = __h[6]
__h[6] = __h[5]
__h[5] = __h[4]
__h[4] = (__h[3] + t1) & 0xFFFFFFFF
__h[3] = __h[2]
__h[2] = __h[1]
__h[1] = __h[0]
__h[0] = (t1 + t2) & 0xFFFFFFFF
with rule(unroll='full'):
for i in range(8):
_h[i] = (_h[i] + __h[i]) & 0xFFFFFFFF
self.data_out.wr(bit32x8_bit256(_h))
@testbench
def test(m):
lst = [0x61616161] * 16
blen = len(lst)
blocks = ((blen * 4 + 5) + 63) // 64
print("blocks", blocks)
start_i = 0
m.data_in.wr(blocks)
for i in range(blocks - 1):
v512= bit32x16_bit512(lst, start_i)
print('v512', v512)
m.data_in.wr(v512)
start_i += 16
#send last block
last_block = [0] * 16
for i in range(blen - start_i):
last_block[i] = lst[start_i]
start_i += 1
last_block[blen - start_i] = 0x80000000
last_block[15] = (blocks << 8)
v512_last = bit32x16_bit512(last_block)
#print(v512_last)
m.data_in.wr(v512_last)
v256:bit256 = m.data_out.rd()
print('sha256', v256)
#print('R {:032x}'.format(v256))
m=sha256()
test(m)
今度のソースはちゃんとブロックも考慮するようにした。現状では Python の format が使えないのでその部分はコメントアウトされている。Python でのデバッグ時に有効にすれば、実際の SHA-256 と比較出来て便利だろう。
おまけ 256bit と 512bit 追加
256bit と 512bit 用のパッチをおまけとしてつけておく。
diff --git a/polyphony/_internal/_typing.py b/polyphony/_internal/_typing.py
index c43b648..2cb800f 100644
--- a/polyphony/_internal/_typing.py
+++ b/polyphony/_internal/_typing.py
@@ -52,6 +52,8 @@ __all__ = [
'uint121', 'uint122', 'uint123', 'uint124', 'uint125', 'uint126', 'uint127', 'uint128',
'List',
'Tuple',
+ 'bit512',
+ 'bit256',
]
class bit: pass
@@ -183,6 +185,9 @@ class bit126: pass
class bit127: pass
class bit128: pass
+class bit256: pass
+class bit512: pass
+
class int2: pass
class int3: pass
class int4: pass
diff --git a/polyphony/typing.py b/polyphony/typing.py
index 6f3078d..08c0dd9 100644
--- a/polyphony/typing.py
+++ b/polyphony/typing.py
@@ -176,6 +176,8 @@ class bit125(int_base): pass
class bit126(int_base): pass
class bit127(int_base): pass
class bit128(int_base): pass
+class bit256(int_base): pass
+class bit512(int_base): pass
class int2(int_base): pass
class int3(int_base): pass