Реализация алгоритма хеширования SHA-1

15

Цель этого code-golf состоит в том, чтобы создать программу, которая принимает строку в качестве входных данных, и вы должны вывести значение SHA-1 в виде шестнадцатеричного числа. Вы можете найти псевдокод для SHA-1 здесь

Другие правила:

  1. Нет доступа к сети
  2. Вы не можете запускать внешние программы
  3. Вы не можете использовать встроенные методы для хэширования ввода
  4. Самый короткий код выигрывает
  5. Необходимо только обрабатывать ввод ASCII
  6. Вывод может быть как строчным, так и прописным
  7. Ввод может быть предоставлен с использованием:

    1. Подсказка для ввода
    2. Использование аргументов командной строки
    3. Использование STDIN

Тестовые случаи:

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
источник

Ответы:

5

GolfScript, 374 322 символа

[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>}%''+

Это основано на точной реализации псевдокода в GolfScript, а также некоторых незначительных кодировках для сокращения кода (попробуйте онлайн ). Вход будет считан из STDIN.

Говард
источник
Это самый длинный GolfScript, который я когда-либо видел: P
дверная ручка
5

Python 3 - 645 символов

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]))

Просто гольф-версия псевдокода.

GRC
источник
UTF = U8 в Python3?
ВЫ
1
@YOU Да, это тоже работает. Я только что проверил, и оказалось, что .encode()по умолчанию используется UTF-8, что еще короче.
grc
2

D (759 символов)

Онлайн исполняемая версия: 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
источник
2

C 546 символов

Программа рассчитывает SHA-1 из содержимого его стандартного ввода.

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

Пара заметок:

  1. Эта программа предполагает, что intэто ровно 32 бита. Для платформ, где это не так, unsignedобъявление в самом начале должно быть заменено на 32-битный тип платформы без знака. ( uint32_tбыло бы очевидным выбором, если бы это не требовалось #include <stdint.h>.)
  2. Эта программа предполагает платформу с прямым порядком байтов. Для платформы с прямым порядком байтов просто удалите два вхождения ^3в программе и замените инициализацию k[]следующим блоком: {19088743,0x89ABCDEF,0,1985229328,0xF0E1D2C3}для размера 541 символов.
  3. Для реализаций, где charпо умолчанию нет подписи, можно удалить то, &255что появляется в последней строке, чтобы сохранить еще четыре символа.
Хлебница
источник
Это возвращает be417768b5c3c5c1d9bcb2e7c119196dd76b5570для The quick brown fox jumps over the lazy dogно он должен вернуться2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
ProgramFOX
@ProgramFOX Это значение хеша для строки плюс завершающая новая строка. Тестовые значения SHA-1, приведенные в описании, предназначены для строк без завершения новой строки, поэтому не добавляйте новую строку во входные данные, если вы хотите проверить эти строки.
хлебница
1

Мой код на Python немного длиннее, но он полностью работает.

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)
Кайл К
источник
Пожалуйста, укажите язык в ответе. Кроме того, поскольку это код-гольф, вы должны хотя бы попытаться минимизировать. Имена переменных, состоящие из одного символа, удаление ненужных пробелов, добавление дорогих констант ( 0xffffffff) в переменные (также будет -1достаточно?) ...
Джон Дворжак
выглядит как фитон для меня :)
Owais Qureshi
@JanDvorak Я изменил свой код.
Кайл К
h0..h4еще две буквы ;-)
Джон Дворак
Я получаю синтаксическую ошибку в строке 29.
ProgramFOX