取りあえずはFIPS 180-2とこれを読めばどうやって実装するのかは分かるはず。特に前者は計算のサンプルと途中経過が書いてあるのでデバッグにも最適。
ついでに言うと、当然ながら
import hashlibはダメな模様。それでは。
import os msg = os.read(0,9999) H = [ 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 ] 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 ] ch = lambda x,y,z: x&y ^ ~x&z maj = lambda x,y,z: x&y ^ x&z ^ y&z shr = lambda x,n: (0xFFFFFFFF & x) >> n rotr = lambda x,n: ((0xFFFFFFFF & x) >> n) | x << (32 - n) sigma0 = lambda x: rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3) sigma1 = lambda x: rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10) SIGMA0 = lambda x: rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22) SIGMA1 = lambda x: rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25) def padding(w): x = map(ord, w) + [0x80] l = len(x) i = tmp = 0 t = [ ] while i < l: tmp |= (x[i] << (24 - (i % 4) * 8)) i += 1 if i and i % 4 == 0: t.append(tmp) tmp = 0 if i % 4: t.append(tmp) ts = len(t) while (ts + 2) % 16: t.append(0) ts += 1 t.append(0) t.append((l - 1) * 8) result = [] for i in range(0, len(t), 16): result.append(t[i:i+16]) return result for m in padding(msg): a, b, c, d, e, f, g, h = H m += [0] * 48 for t in range(16,64): m[t] = sigma1(m[t - 2]) + m[t - 7] + sigma0(m[t - 15]) + m[t - 16] for t in range(64): T1 = h + SIGMA1(e) + ch(e, f, g) + K[t] + m[t] T2 = SIGMA0(a) + maj(a, b, c) h = g g = f f = e e = d + T1 d = c c = b b = a a = T1 + T2 H[0] += a H[1] += b H[2] += c H[3] += d H[4] += e H[5] += f H[6] += g H[7] += h print''.join(map(lambda x:'%08x'%(x&0xFFFFFFFF), H))コードを短くするという考えを一切捨てて、取りあえず動くもの。動くもの、といっても上記コードは入力データに制限がある。全部読めよ、という気もするが、データ長を入れるところも端折っているのでまあいいか。
で、これを短くする。いきなり短い(汚い)コードにすると後々困ることになるが、取りあえずどの程度短くなるかを確認する。
import os M=0xFFFFFFFF r=range H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19] S=lambda x,n:(M&x)>>n R=lambda x,n:(M&x)>>n|x<<32-n x=map(ord,os.read(0,9999))+[0x80] l=len(x) i=z=0 t=[] while i<l: z|=(x[i]<<(24-(i%4)*8));i+=1 if i%4==0:t+=[z];z=0 if i%4:t+=[z] s=len(t) while(s+2)%16:t+=[0];s+=1 t+=[0,8*l-8] w=[] for i in r(0,len(t),16):w+=[t[i:i+16]] for m in w: a,b,c,d,e,f,g,h=H;m+=[0]*48 for t in r(16,64):x=m[t-15];y=m[t-2];m[t]=(R(y,17)^R(y,19)^S(y,10))+m[t-7]+(R(x,7)^R(x,18)^S(x,3))+m[t-16] for t in r(64):T1=h+(R(e,6)^R(e,11)^R(e,25))+(e&f^~e&g)+[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][t]+m[t];T2=(R(a,2)^R(a,13)^R(a,22))+(a&b^a&c^b&c);h=g;g=f;f=e;e=d+T1;d=c;c=b;b=a;a=T1+T2 H[0]+=a;H[1]+=b;H[2]+=c;H[3]+=d;H[4]+=e;H[5]+=f;H[6]+=g;H[7]+=h print''.join(map(lambda x:'%08x'%(x&M), H))この段階で1507byte。pythonのトップは468byte。まさに問題外。土俵に上がれてすらいない。定数Kのテーブルサイズだけで700byteを超えるので、どう足掻いても無理なようだ。よって、単純な短縮をする前に考え直し。
まず定数Kの参照方法を変える。
def K(): k=0xc67178f2bef9a3f7a4506ceb90befffa8cc7020884c8781478a5636f748f82ee682e6ff35b9cca4f4ed8aa4a391c0cb334b0bcb52748774c1e376c0819a4c116106aa070f40e3585d6990624d192e819c76c51a3c24b8b70a81a664ba2bfe8a192722c8581c2c92e766a0abb650a735453380d134d2c6dfc2e1b213827b70a851429296706ca6351d5a79147c6e00bf3bf597fc7b00327c8a831c66d983e515276f988da5cb0a9dc4a7484aa2de92c6f240ca1cc0fc19dc6efbe4786e49b69c1c19bf1749bdc06a780deb1fe72be5d74550c7dc3243185be12835b01d807aa98ab1c5ed5923f82a459f111f13956c25be9b5dba5b5c0fbcf71374491428a2f98 while 1:yield k;k>>=32こんな感じにジェネレータを作ってみる。
import os M=0xFFFFFFFF r=range q=16 H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19] S=lambda n:(M&x)>>n R=lambda n:S(n)|x>>32-n def K(): k=0xc67178f2bef9a3f7a4506ceb90befffa8cc7020884c8781478a5636f748f82ee682e6ff35b9cca4f4ed8aa4a391c0cb334b0bcb52748774c1e376c0819a4c116106aa070f40e3585d6990624d192e819c76c51a3c24b8b70a81a664ba2bfe8a192722c8581c2c92e766a0abb650a735453380d134d2c6dfc2e1b213827b70a851429296706ca6351d5a79147c6e00bf3bf597fc7b00327c8a831c66d983e515276f988da5cb0a9dc4a7484aa2de92c6f240ca1cc0fc19dc6efbe4786e49b69c1c19bf1749bdc06a780deb1fe72be5d74550c7dc3243185be12835b01d807aa98ab1c5ed5923f82a459f111f13956c25be9b5dba5b5c0fbcf71374491428a2f98 while 1:yield k;k>>=32 i=z=0 t=[] for c in os.read(0,9999)+'\x80': z|=ord(c)>>24-i%4*8;i+=1 if i%4==0:t+=[z];z=0 if i%4:t+=[z] t+=[0]*((q-len(t)-2%q)%q)+[0,8*i-8] for m in[t[i:i+q]for i in r(0,len(t),q)]: a,b,c,d,e,f,g,h=H for t in r(q,64):x=m[t-2];A=R(17)^R(19)^S(10);x=m[t-15];m+=[A+m[t-7]+(R(7)^R(18)^S(3))+m[t-q]] for k,t in zip(K(),r(64)):x=e;T=h+(R(6)^R(11)^R(25))+(e&f^~e&g)+k+m[t];x=a;U=(R(2)^R(13)^R(22))+(a&b^a&c^b&c);a,b,c,d,e,f,g,h=T+U,a,b,c,d+T,e,f,g H=map(sum,zip(H,(a,b,c,d,e,f,g,h))) print''.join(map(lambda x:'%08x'%(x&M),H))その他色々弄って、1248byte。
lambdaのあまりの文脈依存っぷりに自分でも驚くが、依然として話にならない。もう少しまじめに。FIPS 180-2による定数Kの定義は以下の通り。
These words represent the first thirty-two bits of the fractional parts of the cube roots of the first sixtyfour prime numbers.…へぇ。何？素数の立方根？64個の素数？64個目？なんだか分からないが、おそらくこれは動的に生成出来る、気がする。
と言うわけで、この定義について、色々動かして確認して予想する。最初の素数である2から64個分の素数の立方根の小数部分のことか？というあたりを付けて確認。
def K(): for p in 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311: t=0;n=p**(1.0/3) for j in r(8):n*=16;t=t<<4|int(n) yield t結果、正解。上記ジェネレータで定数Kが取得できた。ベースとなるテーブルサイズは226byte。かなり小さくなった。
226byteより小さいサイズで素数を求める事が出来ればさらに小さくなるはず。…で、素数ってどうやって求めるの？
def P(): yield 2;p=3 while 1: d=2 while d<p: if p%d==0:break d+=1 else:yield p p+=2単純に割っていく方法しか知らないのでそれで実装。よく分からないので改良の余地を多分に残しているであろうコードだが、テーブルサイズよりは小さい。とりあえずコレでやってみる。
import os M=0xFFFFFFFF r=range q=16 H=[0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19] S=lambda n:(M&x)>>n R=lambda n:S(n)|x<<32-n def P(p): yield 2 while 1: d=2 while p%d and d<p:d+=1 if p==d:yield p p+=2 def K(): for p in P(3): t=0;n=p**(1.0/3) for j in[0]*8:n*=16;t=t<<4|int(n) yield t i=z=0 t=[] for c in os.read(0,9999)+'\x80': z|=ord(c)<<24-i%4*8;i+=1 if i%4==0:t+=[z];z=0 if i%4:t+=[z] t+=[0]*((q-len(t)-2%q)%q)+[0,8*i-8] for m in[t[i:i+q]for i in r(0,len(t),q)]: a,b,c,d,e,f,g,h=H for t in r(q,64):x=m[t-2];A=R(17)^R(19)^S(10);x=m[t-15];m+=[A+m[t-7]+(R(7)^R(18)^S(3))+m[t-q]] for k,t in zip(K(),r(64)):x=e;T=h+(R(6)^R(11)^R(25))+(e&f^~e&g)+k+m[t];x=a;U=(R(2)^R(13)^R(22))+(a&b^a&c^b&c);a,b,c,d,e,f,g,h=T+U,a,b,c,d+T,e,f,g H=map(sum,zip(H,(a,b,c,d,e,f,g,h))) print''.join(map(lambda x:'%08x'%(x&M),H))ジェネレータを若干弄って組み込んで、872byte。かなり短くなったはずだが、それでもトップの倍近いサイズ。もうちょっと細かくみないとダメか。
