Zaimplementuj SHA-256

18

Biorąc pod uwagę sekwencję bajtów, wypisz wartość skrótu SHA-256 sekwencji.

Algorytm SHA-256

Poniższy pseudokod pochodzi ze strony Wikipedii dla 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

Realizacja referencyjna

Oto implementacja referencyjna w Pythonie 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))

Ograniczenia

  • Używanie wbudowanych funkcji, które obliczają skróty SHA-256 lub w inny sposób trywializują wyzwanie, jest zabronione
  • Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie (zakodowane w kodowaniu jednobajtowym, base64, szesnastkowym itp.)

Przypadki testowe

<empty string> -> e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
abc -> ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
Hello, World! -> c98c24b677eff44860afea6f493bbaec5bb1c4cbb209c6fc2bbb47f66ff2ad31
1234 -> 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
Mego
źródło

Odpowiedzi:

7

J , 458 445 443 438 435 430 421 bajtów

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
)

Wypróbuj online!

Jest to czasownik monadyczny, który pobiera listę bitów jako dane wejściowe i wysyła listę bitów. W TIO konwersja z łańcucha znaków na listę bitów dla danych wejściowych i listy bitów na szesnastkową jest wprowadzana dla wygody. Aby przetestować inne dane wejściowe, wystarczy zmodyfikować tekst w inputpolu.

mile
źródło
To jest piękne
Mego
@Mego Dzięki, wciąż istnieje kilka zbędnych części, które prawdopodobnie można by zagrać w golfa, aby zaoszczędzić około 10 bajtów.
mile
Chciałbym zobaczyć milczącą wersję: P
Mego
Jeśli 13obsługiwane są również definicje i przypisania wieloliniowe.
mile
A J 8,06, jest teraz wbudowany do stosowania SHA-256 i inne skrótów, 128!:6. Przykład
mile
8

Python 2, 519 bajtów

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

Pracowałem nad pseudokodem, ale niektóre części były takie same, jak napisane przez Mego odniesienie do gry w golfa, ponieważ nie ma wiele do golfa (np. Stałe stoły, dla których jedynym prawdziwym golfem była <2zamiast==1 ). Ponad 100 bajtów w dół, ale jestem pewien, że jest jeszcze wiele do zdobycia.

Wejście / wyjście to także ciąg bitów do ciągu szesnastkowego.

Sp3000
źródło
Myślę, że możesz alias int, który zaoszczędziłby 2B. Nie znam się na golfie w Pythonie, więc możesz jeszcze zaoszczędzić kilka bajtów. Co też x**e%1*Qrobi? Przeprowadziłem kilka testów z pewnymi losowymi wartościami dla xe, ale zawsze zwracało 0 ...
Luke
@ L.Serné intjest używany tylko dwa razy, więc aliasing niczego nie uratuje. x**e%1daje część ułamkową, więc będziesz musiał przetestować ułamkowo edla zamierzonego efektu.
Sp3000,
7

Python 2, 633 bajtów

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)

To rozwiązanie jest wynikiem współpracy między mną, Leaky Nun i Mars Ultor. Jako takie, stworzyłem wiki społeczności z uczciwości. Pobiera dane wejściowe jako ciąg binarny zawinięty w cudzysłów (np. '011000010110001001100011'Dla abc) i wysyła ciąg szesnastkowy.

Mego
źródło
2
Przynajmniej jest jasne, jak to działa? :)
enderland
4

C, 1913 1822 bajtów (tylko dla zabawy)

#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)}}

Wziąłem referencyjną implementację i zacząłem grać w golfa, mój cel był poniżej 2 tys.

Można poprawić, jeśli ktoś wie, jak wygenerować stałe (pierwiastek sześcienny liczb pierwszych, nie mogę wymyślić żadnego przyjaznego dla golfa sposobu).

Stosowanie:

X ctx;
unsigned char hash[32];

i(&ctx);                    // initialize context
p(&ctx,text,strlen(text));  // hash string
f(&ctx,hash);               // get hash
GB
źródło
Stały generator w golfa (choć nadal można w niego grać). Wypróbuj online!
Max Yekhlakov
Bardziej golfowy stały generator 275 bajtów
ceilingcat