Implementacja algorytmu skrótu SHA-1

15

Celem tego golfa kodowego jest stworzenie programu, który pobiera ciąg znaków jako dane wejściowe, i musisz wyprowadzić wartość skrótu SHA-1 jako liczbę szesnastkową. Pseudokod dla SHA-1 można znaleźć tutaj

Inne zasady:

  1. Brak dostępu do sieci
  2. Nie możesz uruchamiać programów zewnętrznych
  3. Nie możesz używać wbudowanych metod do mieszania danych wejściowych
  4. Najkrótszy kod wygrywa
  5. Konieczna jest tylko obsługa danych ASCII
  6. Dane wyjściowe mogą być pisane małymi lub dużymi literami
  7. Dane wejściowe można podać za pomocą:

    1. Monitowanie o dane wejściowe
    2. Korzystanie z argumentów wiersza polecenia
    3. Używanie STDIN

Przypadki testowe:

Input: The quick brown fox jumps over the lazy dog
Output: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
----------------------------------------------------------
Input: The quick brown fox jumps right over the lazy dog
Output: 1c3aff41d97ada6a25ae62f9522e4abd358d741f
------------------------------------------------------------
Input: This is a code golf challenge
Output: f52ff9edd95d98e707bd16a7dead459cb8db8693
ProgramFOX
źródło

Odpowiedzi:

5

GolfScript, 374 322 znaków

[128]+.,.~55+64%1,*\(8*2
32?:?.*+256{base}:B~1>++"!Vi9y BRQ+@phoKD5Vj=]30z0"{96@32-*+}*?B\64/{4/{256B}%{0'=820'{64-
2$=^}/2*.?/+?%+}64*1$'&4$?(^3$&|1518500249{++[]@+@+@?*4/.?/+?%+2$+\@32*.?/++@(@+?%@-1%+}:Y~
^2$^1859775393Y
&4$3$&|3$3$&|2400959708Y
^2$^3395469782Y'n/{'~3$3$'\+20*~}/+]zip{~+?%}%}/{?+16B{.9>7*+48+}%1>}%''+

Opiera się to na dokładnej implementacji pseudokodu w GolfScript oraz kilku mniejszych kodowaniach w celu skrócenia kodu (spróbuj online ). Wejście zostanie odczytane ze STDIN.

Howard
źródło
To najdłuższy GolfScript, jaki kiedykolwiek widziałem: P
Klamka
5

Python 3 - 645 znaków

h=0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0
L=lambda v,s:(v<<s|v>>B-s)%2**B
B=32
R=range
m=input().encode()
l=len(m)
m+=b'\x80'+bytes((55-l)%64)+m.fromhex(hex(2**64+l*8)[3:])
for C in [m[i:i+64]for i in R(0,len(m),64)]:
 w=[sum(C[i+j]<<8*(3-j)for j in R(4))for i in R(0,64,4)];a,b,c,d,e=h
 for i in R(16,80):w+=[L(w[i-3]^w[i-8]^w[i-14]^w[i-16],1)]
 for i in R(80):f=[b&c|~b&d,b^c^d,b&c|b&d|c&d,b^c^d][i//20];k=[0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6][i//20];t=L(a,5)+f+e+k+w[i];e=d;d=c;c=L(b,30);b=a;a=t%2**32
 g=a,b,c,d,e;h=[(h[i]+g[i])%2**32for i in R(5)]
B=160
print('%x'%(L(h[0],128)|L(h[1],96)|L(h[2],64)|L(h[3],32)|h[4]))

Tylko golfowa wersja pseudokodu.

grc
źródło
czy utf = u8 w python3?
TY
1
@YOU Tak, to też działa. Właśnie sprawdziłem i okazuje się, że .encode()domyślnie używa UTF-8, który jest jeszcze krótszy.
grc
2

D (759 znaków)

Wersja wykonywalna online: http://dpaste.dzfl.pl/f0c8508f

import std.range,std.algorithm,std.bitmanip,std.stdio:g=writef;
void main(char[][]x){
    auto m=cast(ubyte[])x[1];
    uint a=0x67452301,b=0xEFCDAB89,i,t,f,k;
    uint[5]h=[a,b,~a,~b,0xC3D2E1F0],s;
    uint[80]w;
    auto r=(uint u,uint b)=>u<<b|u>>32-b;
    auto u=(uint i)=>[r(s[0],5)+f+s[4]+k+w[i],s[0],r(s[1],30),s[2],s[3]];
    ubyte[64]p;
    p[0]=128;
    m~=p[0..64-(m.length+8)%64]~nativeToBigEndian(8*m.length);
    foreach(ch;m.chunks(64)){
        16.iota.map!(i=>w[i]=ch[i*4..$][0..4].bigEndianToNative!uint).array;
        iota(16,80).map!(i=>w[i]=r(w[i-3]^w[i-8]^w[i-14]^w[i-16],1)).array;
        s=h;
        80.iota.map!(i=>(i<20?f=s[3]^s[1]&(s[2]^s[3]),k=0x5A827999:i<40?f=s[1]^s[2]^s[3],k=0x6ED9EBA1:i<60?f=s[1]&s[2]|s[3]&(s[1]|s[2]),k=0x8F1BBCDC:(f=s[1]^s[2]^s[3],k=0xCA62C1D6),s[]=u(i)[])).array;
        h[]+=s[];
    }
    g("%(%08x%)",h);
}
mleise
źródło
2

C, 546 znaków

Program oblicza SHA-1 zawartości standardowego wejścia.

unsigned b[16],k[]={1732584193,0xEFCDAB89,0,271733878,0xC3D2E1F0},i,j,n,p,t,u,v,w,x;
char*d=b;a(c){for(d[p++^3]=c,c=0,t=*k,u=k[1],v=k[2],w=k[3],x=k[4];
c>79?*k+=t,k[1]+=u,k[2]+=v,k[3]+=w,k[4]+=x,p=0:p>63;x=w,w=v,v=u<<30|u/4,u=t,t=i)
i=b[c-3&15]^b[c+8&15]^b[c+2&15]^b[j=c&15],c++>15?b[j]=i*2|i>>31:0,i=u^v^w,
i=(t<<5|t>>27)+x+b[j]+(c<21?(w^u&(v^w))+1518500249:c<41?i+1859775393:
c<61?(u&v|w&(u|v))-1894007588:i-899497514);}
main(){for(k[2]=~*k;i=~getchar();++n)a(~i);for(a(128);p-56;a(0));
for(;p<20?printf("%02x",(d=k)[p^3]&255):p>55;a(n*8L>>504-p*8));}

Kilka uwag:

  1. Program zakłada, że intma dokładnie 32 bity. W przypadku platform, na których tak nie jest, unsigneddeklarację na samym początku należy zastąpić 32-bitowym typem platformy bez znaku. ( uint32_tbyłby oczywistym wyborem, gdyby nie wymagał #include <stdint.h>).
  2. Ten program zakłada platformę little-endian. W przypadku platformy big-endian po prostu usuń dwa wystąpienia ^3programu i zastąp inicjalizację k[]następującym blokiem:, {19088743,0x89ABCDEF,0,1985229328,0xF0E1D2C3}dla rozmiaru 541 znaków.
  3. W przypadku implementacji, w których chardomyślnie nie jest podpisany, można usunąć ten, &255który pojawia się w ostatnim wierszu, aby zapisać cztery kolejne znaki.
chlebak
źródło
Spowoduje to powrót be417768b5c3c5c1d9bcb2e7c119196dd76b5570do The quick brown fox jumps over the lazy dogale musi wrócić2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
ProgramFOX
@ProgramFOX Ta wartość skrótu dotyczy łańcucha i kończącego nowego wiersza. Testowe wartości SHA-1 cytowane w opisie dotyczą ciągów znaków bez kończenia nowych linii, więc nie dołączaj nowej linii do danych wejściowych, jeśli chcesz przetestować te ciągi.
breadbox
1

Mój kod python jest trochę dłuższy, ale działa w pełni.

data="hello world"
bytes = ""
h0,h1,h2,h3,h4=0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0
for n in range(len(data)):bytes+='{0:08b}'.format(ord(data[n]))
bits=bytes+"1"
pBits=bits
while len(pBits)%512!=448:pBits+="0"
pBits+='{0:064b}'.format(len(bits)-1)
def chunks(l,n):return[l[i:i+n]for i in range(0,len(l),n)]
def rol(n,b):return((n<<b)|(n>>(32-b)))&0xffffffff 
for c in chunks(pBits,4512):
    words=chunks(c,32)
    w=[0]*80
    for n in range(0,16):w[n]=int(words[n],2)
    for i in range(16,80):w[i]=rol((w[i-3]^w[i-8]^w[i-14]^w[i-16]),1)
    a,b,c,d,e=h0,h1,h2,h3,h4
    for i in range(0,80):
        if 0<=i<=19:f=(b&c)|((~b)&d);k=0x5A827999
        elif 20<=i<=39:f=b^c^d;k=0x6ED9EBA1
        elif 40<=i<=59:f=(b&c)|(b&d)|(c&d);k=0x8F1BBCDC
        elif 60<=i<=79:f=b^c^d;k=0xCA62C1D6
        temp=rol(a,5)+f+e+k+w[i]&0xffffffff
        e,d,c,b,a=d,c,rol(b,30),a,temp 
    h0+=a
    h1+=b
    h2+=c
    h3+=d
    h4+=e 
print '%08x%08x%08x%08x%08x'%(h0,h1,h2,h3,h4)
Kyle K.
źródło
Proszę podać język w odpowiedzi. Ponieważ jest to kod-golf, powinieneś przynajmniej spróbować zminimalizować. Jednoznakowe nazwy zmiennych, usuwanie niepotrzebnych białych znaków, łączenie drogich stałych ( 0xffffffff) w zmienne (też czy -1wystarczy?) ...
John Dvorak
dla mnie wygląda jak fithon :)
Owais Qureshi
@JanDvorak Zmodyfikowałem swój kod.
kyle k
h0..h4są jeszcze dwuliterowe ;-)
John Dvorak
W wierszu 29 pojawia się błąd składniowy.
ProgramFOX