Terapkan SHA-256

18

Diberikan urutan byte, menampilkan nilai hash SHA-256 dari urutan.

Algoritma SHA-256

Pseudocode berikut diambil dari halaman Wikipedia untuk SHA-2 .

Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 2^32
Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63
Note 3: The compression function uses 8 working variables, a through h
Note 4: Big-endian convention is used when expressing the constants in this pseudocode,
    and when parsing message block data from bytes to words, for example,
    the first word of the input message "abc" after padding is 0x61626380

Initialize hash values:
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize array of round constants:
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
   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

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
    length (modulo 512 in bits) is 448.
append length of message (without the '1' bit or padding), in bits, as 64-bit big-endian integer
    (this will make the entire post-processed length a multiple of 512 bits)

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    create a 64-entry message schedule array w[0..63] of 32-bit words
    (The initial values in w[0..63] don't matter, so many implementations zero them here)
    copy chunk into first 16 words w[0..15] of the message schedule array

    Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
    for i from 16 to 63
        s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
        s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    Initialize working variables to current hash value:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7

    Compression function main loop:
    for i from 0 to 63
        S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        temp1 := h + S1 + ch + k[i] + w[i]
        S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        temp2 := S0 + maj

        h := g
        g := f
        f := e
        e := d + temp1
        d := c
        c := b
        b := a
        a := temp1 + temp2

    Add the compressed chunk to the current hash value:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Produce the final hash value (big-endian):
digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

Implementasi referensi

Berikut ini adalah implementasi referensi, dalam Python 3:

#!/usr/bin/env python3

import sys

# ror function modified from http://stackoverflow.com/a/27229191/2508324
def ror(val, r_bits):
   return (val >> r_bits) | (val << (32-r_bits)) % 2**32

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]

s = sys.stdin.read().encode()
msg = [int(x,2) for c in s for x in '{:08b}'.format(c)]
msg.append(1)
while len(msg) % 512 != 448:
    msg.append(0)
msg.extend([int(x,2) for x in '{:064b}'.format(len(s) * 8)])

for i in range(len(msg)//512):
    chunk = msg[512*i:512*(i+1)] # sloth love chunk
    w = [0 for _ in range(64)]
    for j in range(16):
        w[j] = int(''.join(str(x) for x in chunk[32*j:32*(j+1)]),2)
    for j in range(16, 64):
        s0 = ror(w[j-15], 7) ^ ror(w[j-15], 18) ^ (w[j-15] >> 3)
        s1 = ror(w[j-2], 17) ^ ror(w[j-2], 19) ^ (w[j-2] >> 10)
        w[j] = (w[j-16] + s0 + w[j-7] + s1) % 2**32
    work = h[:]
    for j in range(64):
        S1 = ror(work[4], 6) ^ ror(work[4], 11) ^ ror(work[4], 25)
        ch = (work[4] & work[5]) ^ (~work[4] & work[6])
        temp1 = (work[7] + S1 + ch + k[j] + w[j]) % 2**32
        S0 = ror(work[0], 2) ^ ror(work[0], 13) ^ ror(work[0], 22)
        maj = (work[0] & work[1]) ^ (work[0] & work[2]) ^ (work[1] & work[2])
        temp2 = (S0 + maj) % 2**32
        work = [(temp1 + temp2) % 2**32] + work[:-1]
        work[4] = (work[4] + temp1) % 2**32
    h = [(H+W)%2**32 for H,W in zip(h,work)]

print(''.join('{:08x}'.format(H) for H in h))

Batasan

  • Penggunaan builtin yang menghitung hash SHA-256 atau meremehkan tantangan dilarang
  • Input dan output mungkin dalam format yang masuk akal (dikodekan dalam pengodean byte tunggal, base64, heksadesimal, dll.)

Uji kasus

<empty string> -> e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
abc -> ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
Hello, World! -> c98c24b677eff44860afea6f493bbaec5bb1c4cbb209c6fc2bbb47f66ff2ad31
1234 -> 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
Mego
sumber

Jawaban:

7

J , 458 445 443 438 435 430 421 byte

3 :0
B=.32#2
A=.B&#:
P=.+&#.
'H K'=.A<.32*&2(-<.)2 3%:/p:i.64
for_m._512]\(,(1{.~512|448-#),(,~B)#:#)y
do.w=.(,B#:(15&|.~:13&|.~:_10|.!.0])@(_2&{)P/@,(25&|.~:14&|.~:_3|.!.0])@(_15&{),_7 _16&{)^:48]_32]\m
'a b c d e f g h'=.H=.8{.H
for_t.i.64
do.u=.A]P/((e<g)~:e*f),h,(~:/26 21 7|."{e),t{&>K;w
v=.A(a*b)P(c*a~:b)P~:/30 19 10|."{a
h=.g
g=.f
f=.e
e=.A]d P u
d=.c
c=.b
b=.a
a=.A]u P v
end.
H=.A]H P a,b,c,d,e,f,g,:h
end.
,H
)

Cobalah online!

Ini adalah kata kerja monadik yang mengambil daftar bit sebagai input dan output daftar bit. Pada TIO, konversi dari string ke daftar bit untuk input dan daftar bit ke heksadesimal diimplementasikan untuk kenyamanan. Untuk menguji input lain, cukup modifikasi teks di inputlapangan.

mil
sumber
Ini indah
Mego
@Mego Terima kasih, masih ada beberapa bagian redundan yang mungkin bisa di-golf untuk menghemat 10 atau lebih byte.
mil
Saya ingin melihat versi diam-diam: P
Mego
Jika hanya 13mendukung definisi dan penugasan multi-line juga.
mil
Pada J 8.06, sekarang ada builtin untuk menggunakan SHA-256 dan hash lainnya 128!:6,. Contoh
mil
8

Python 2, 519 byte

Q=2**32
G=lambda e:[int(x**e%1*Q)for x in range(2,312)if 383**~-x%x<2]
H=G(.5)[:8]
r=lambda v,b:v>>b|v<<32-b
M=input()
l=len(M)
M+=bin(l|1<<(447-l)%512+64)[2:]
while M:j=0;a,b,c,d,e,f,g,h=H;exec"H+=int(M[:32],2),;M=M[32:];"*16+"x=H[-15];y=H[-2];H+=(H[-16]+H[-7]+(r(y,17)^r(y,19)^y>>10)+(r(x,7)^r(x,18)^x/8))%Q,;"*48+"u=(r(e,6)^r(e,11)^r(e,25))+(e&f^~e&g)+h+G(1/3.)[j]+H[j+8];X=a,b,c,d,e,f,g,h=(u+(r(a,2)^r(a,13)^r(a,22))+(a&b^a&c^b&c))%Q,a,b,c,(d+u)%Q,e,f,g;j+=1;"*64;H=tuple(a+b&Q-1for a,b in zip(H,X))
print"%08x"*8%H

Saya mengerjakan kode pseudocode, tetapi beberapa bagian akhirnya sama dengan referensi golf yang diposting Mego karena tidak ada banyak golf (misalnya tabel konstan, di mana satu-satunya golf sebenarnya <2bukan ==1). Lebih dari 100 byte turun, tapi saya yakin masih banyak yang bisa didapat.

Input / output juga berupa string bit ke hex string.

Sp3000
sumber
Saya pikir Anda bisa alias int, yang akan menghemat 2B. Saya tidak begitu terbiasa dengan bermain golf di Python, jadi mungkin masih ada beberapa byte lagi yang bisa Anda simpan. Juga, apa fungsinya x**e%1*Q? Saya menjalankan beberapa tes dengan beberapa nilai acak untuk x dan e, tetapi selalu mengembalikan 0 ...
Luke
@ L.Serné inthanya digunakan dua kali, jadi aliasing tidak akan menyimpan apa pun. x**e%1memberikan bagian fraksional, jadi Anda harus menguji dengan fraksional euntuk efek yang diinginkan.
Sp3000
7

Python 2, 633 byte

n=range
f=2**32
q=512
r=lambda v,b:v%f>>b|(v<<32-b)%f
t=int
g=lambda e:[t(x**e%1*f)for x in n(2,312)if 383**~-x%x==1]
h=g(.5)
k=g(1/3.)
m=map(t,input())
l=len(m)
m+=[1]+[0]*((447-l)%q)+map(t,'{:064b}'.format(l))
for i in n(l/q+1):
 c=m[q*i:][:q];w=[t(`c[j*32:][:32]`[1::3],2) for j in n(16)];x=h[:8]
 for j in n(48):a,o=w[j+1],w[j+14];w+=[(w[j]+(r(a,7)^r(a,18)^(a>>3))+w[j+9]+(r(o,17)^r(o,19)^(o>>10)))%f]
 for j in n(64):a,o=x[::4];d=x[7]+(r(o,6)^r(o,11)^r(o,25))+(o&x[5]^~o&x[6])+k[j]+w[j];e=(r(a,2)^r(a,13)^r(a,22))+(x[1]&a|x[2]&a|x[1]&x[2]);x=[d+e]+x[:7];x[4]+=d
 h=[(H+W)%f for H,W in zip(h,x)]
print''.join('%08x'%H for H in h)

Solusi ini adalah hasil kolaborasi antara saya, Leaky Nun, dan Mars Ultor. Karena itu, saya membuatnya menjadi komunitas wiki karena keadilan. Dibutuhkan input sebagai string biner yang dibungkus dengan tanda kutip (misalnya '011000010110001001100011'untuk abc) dan menghasilkan string hex.

Mego
sumber
2
Setidaknya jelas bagaimana cara kerjanya? :)
enderland
4

C, 1913 1822 byte (hanya untuk bersenang-senang)

#define q unsigned
#define D(a,c)x->b[1]+=a>1<<33-1-c;a+=c;
#define R(a,b)(a>>b|a<<32-b)
#define S(x,a,b,c)(R(x,a)^R(x,b)^x>>c)
#define W(i,a)i=x->s[a];
#define Y(i,a)x->s[a]+=i;
#define Z(_,a)h[i+a*4]=x->s[a]>>(24-i*8);
#define J(a)x->d[a]
#define T(_,a)x->d[63-a]=x->b[a/4]>>8*(a%4);
#define Q(_,a)x->s[a]=v[a];
#define A(F)F(a,0)F(b,1)F(c,2)F(d,3)F(e,4)F(f,5)F(g,6)F(h,7)
#define G(a,b)for(i=a;i<b;++i)
typedef struct{q char d[64];q l,b[2],s[8];}X;q 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},v[]={0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19};a(X*x){q a,b,c,d,e,f,g,h,i,t,z,m[64];G(z=0,16)m[i]=J(z++)<<24|J(z++)<<16|J(z++)<<8|J(z++);G(i,64)m[i]=S(m[i-2],17,19,10)+m[i-7]+S(m[i-15],7,18,3)+m[i-16];A(W);G(0,64){t=h+(R(e,6)^R(e,11)^R(e,25))+(e&f^~e&g)+k[i]+m[i];z=(R(a,2)^R(a,13)^R(a,22))+(a&b^a&c^b&c);h=g;g=f;f=e;e=d+t;d=c;c=b;b=a;a=t+z;}A(Y)}i(X*x){x->l=*x->b=x->b[1]=0;A(Q)}p(X*x,char*w,q l){q t,i;G(0,l){J(x->l)=w[i];if(++x->l==64){a(x);D(*x->b,512)x->l=0;}}}f(X*x,char*h){q i=x->l;if(i<56){J(i++)=128;G(i,56)J(i)=0;}else{J(i++)=128;G(i,64)J(i)=0;a(x);G(0,56)J(i)=0;}D(*x->b,x->l*8)A(T)a(x);G(0,4){A(Z)}}

Saya mengambil implementasi referensi dan mulai bermain golf, target saya di bawah 2k.

Dapat ditingkatkan jika seseorang tahu cara menghasilkan konstanta (akar kubus bilangan prima, saya tidak bisa memikirkan cara ramah-golf).

Pemakaian:

X ctx;
unsigned char hash[32];

i(&ctx);                    // initialize context
p(&ctx,text,strlen(text));  // hash string
f(&ctx,hash);               // get hash
GB
sumber
Generator konstan golf (masih bisa golf). Cobalah online!
Max Yekhlakov
Lebih banyak generator konstan
golf