Kryptograficzny hash golf

34

Ten konkurs się zakończył.

Ze względu na charakter wyzwań dla wyzwanie dla gliniarzy staje się znacznie łatwiejsze, gdy zainteresowanie związanym z nim wyzwaniem spadnie. Dlatego, mimo że nadal możesz publikować funkcje skrótu, twoja odpowiedź nie zostanie zaakceptowana ani nie będzie częścią tabeli wyników.

To wyzwanie jest poszukiwanie najkrótszej realizacji funkcji skrótu , która jest odporna na zderzenia , czyli powinno być niemożliwe do znalezienia dwóch różnych wiadomości z tego samego skrótu.

Jako policjant próbujesz wymyślić i wdrożyć funkcję skrótu, znajdując najlepszy kompromis między rozmiarem kodu a odpornością na kolizje. Użyj zbyt wielu bajtów, a inny policjant cię obezwładni!

Jako złodziej próbujesz udaremnić próby gliniarzy, łamiąc ich funkcje, udowadniając, że nie są one odpowiednie. Zmusi ich to do użycia większej liczby bajtów w celu wzmocnienia algorytmów!

Wyzwanie gliniarzy

Zadanie

Zaimplementuj kryptograficzną funkcję skrótu H: I -> O twojego wyboru, gdzie I jest zbiorem wszystkich nieujemnych liczb całkowitych poniżej 2 2 30, a O jest zbiorem wszystkich nieujemnych liczb całkowitych poniżej 2 128 .

Możesz albo wdrożyć H. jako rzeczywistą funkcję, która przyjmuje i zwraca pojedynczą liczbę całkowitą, ciąg znaków reprezentujący liczbę całkowitą lub tablicę liczb całkowitych lub pełny program, który odczytuje STDIN i drukuje do STDOUT w bazie 10 lub 16.

Punktacja

  • H , że musi oprzeć się wyzwaniu złodziei zdefiniowanemu poniżej.

    Jeśli złodziej pokona twoje zgłoszenie w ciągu pierwszych 168 godzin po opublikowaniu, uznaje się je za pęknięte .

  • Implementacja H powinna być jak najkrótsza. Najkrótsze niezłapane zgłoszenie będzie zwycięzcą wyzwania gliniarzy.

Dodatkowe zasady

  • Jeśli implementujesz H jako funkcję, podaj opakowanie, aby wykonać funkcję z poziomu programu, który zachowuje się jak wyjaśniono powyżej.

  • Podaj co najmniej trzy wektory testowe dla swojego programu lub opakowania (przykładowe dane wejściowe i odpowiadające im dane wyjściowe).

  • H. może być twoim nowym projektem (preferowanym) lub znanym algorytmem, o ile sam go zaimplementujesz. Zabrania się korzystania z jakichkolwiek wbudowanych funkcji skrótu, funkcji kompresji, szyfru, PRNG itp.

    Wszelkie wbudowane powszechnie używane do implementacji funkcji skrótu (np. Konwersja bazy) to uczciwa gra.

  • Wynik działania programu lub funkcji musi być deterministyczny.

  • Powinien istnieć darmowy (jak w przypadku piwa) kompilator / interpreter, który można uruchomić na platformie x86 lub x64 lub z poziomu przeglądarki internetowej.

  • Twój program lub funkcja powinna być dość wydajna i musi mieszać każdą wiadomość w I poniżej 2 2 19 w mniej niż sekundę.

    W przypadkach krawędziowych decydujący będzie czas (ścienny) na moim komputerze (Intel Core i7-3770, 16 GiB pamięci RAM).

  • Biorąc pod uwagę naturę tego wyzwania, zabronione jest zmienianie kodu odpowiedzi w jakikolwiek sposób, niezależnie od tego, czy zmienia on wynik, czy nie.

    Jeśli Twoje zgłoszenie zostało złamane (lub nawet jeśli nie zostało), możesz opublikować dodatkową odpowiedź.

    Jeśli twoja odpowiedź jest nieprawidłowa (np. Nie jest zgodna ze specyfikacją I / O), usuń ją.

Przykład

Python 2.7, 22 bajty

def H(M):
 return M%17

Obwoluta

print H(int(input()))

Wyzwanie rabusiów

Zadanie

Złam dowolne oświadczenie gliniarzy, zamieszczając w wątku rabusiów : dwie wiadomości M i N w I takie, że H (M) = H (N) i M ≠ N .

Punktacja

  • Złamanie każdego zgłoszenia gliny daje ci jeden punkt. Złodziej z największą liczbą punktów wygrywa.

    W przypadku remisu wygrywa ten związany bandyta, który złamał najdłuższe poddanie.

Dodatkowe zasady

  • Każde zgłoszenie policjanta może zostać złamane tylko raz.

  • Jeśli przesłanie policjanta opiera się na zachowaniu zdefiniowanym lub niezdefiniowanym, musisz jedynie znaleźć pęknięcie, które działa (weryfikowalnie) na twoim komputerze.

  • Każde pęknięcie należy do osobnej odpowiedzi w wątku złodziei.

  • Opublikowanie nieważnej próby złamania uniemożliwi zablokowanie tego konkretnego zgłoszenia przez 30 minut.

  • Nie możesz złamać własnego zgłoszenia.

Przykład

Python 2.7, 22 bajty według użytkownika8675309

1

i

18

Tabela liderów

Bezpieczne zgłoszenia

  1. CJam, 21 bajtów eBiznesu
  2. C ++, 148 bajtów przez tucuxi
  3. C ++, 233 (?) Bajtów autorstwa Vi.

Nieprzetworzone zgłoszenia

Możesz użyć tego fragmentu stosu, aby uzyskać listę jeszcze nie spękanych odpowiedzi.

function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>

Dennis
źródło
Jeśli funkcja skrótu błędnie zwraca liczby większe niż 2 ^ 128-1, czy to unieważnia przesłanie, czy po prostu weźmiemy wynik modulo 2 ^ 128?
Martin Ender
@ MartinBüttner: Tak, musisz wziąć wynik modulo 2 ^ 128.
Dennis
1
@ Scimonster Nie spełnia wymagań (do 2 ^ 30 bitów wejściowych, 128 bitów wyjściowych)
CodesInChaos
1
Czy gliniarze i złodzieje zwykle nie odwracają się?
haneefmubarak
2
Być może moglibyśmy mieć zasadę, że przesyłanie musi zawierać przykładowe skróty, dość denerwujące jest uruchamianie wybranego języka programowania przez zgłaszających, aby uzyskać wynik do porównania z implementacją crackingu.
aaaaaaaaaaaa

Odpowiedzi:

6

CJam, 21 bajtów

1q3*{i+_E_#*^26_#)%}/

Pobiera ciąg bajtów jako dane wejściowe.

W pseudokodzie:

hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

Przykładowe skróty:

„” (pusty ciąg) -> 1
„Test” -> 2607833638733409808360080023081587841
„test” -> 363640467424586895504738713637444713

Może to być trochę proste, zakres wyjściowy jest tylko nieco większy niż 122 bity, potrójne wzmocnienie iteracji jest już nieco zepsute, ponieważ robi dokładnie to samo za każdym razem, więc wprowadź hash do 1 w pierwszym iteracja będzie pełną przerwą. Ale jest krótki i nie jest fajnie być zbyt bezpiecznym.

aaaaaaaaaaaa
źródło
Czy istnieje towarzysząca wersja C, jak w innym poście CJam?
Vi.
@Vi. Nie, przynajmniej jeszcze nie. Nigdy nie zajmowałem się bigintem w C, czy jest do tego standardowa biblioteka?
aaaaaaaaaaaa
GMP ?
Vi.
3
Tutaj: pastebin.com/SDzA3JK4
squeamish ossifrage
1
@ Agawa001 Zmieszałeś swoją terminologię. Jest to algorytm mieszania z funkcją potrójnego przejścia gąbki. Szyfr Cezara to jeden specyficzny algorytm szyfrowania bez stanu wewnętrznego.
aaaaaaaaaaaa
7

Pyton, 109 bajty [ krakingu , i ponownie ]

def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

Próbowałem wdrożyć Jenkinsa pojedynczo funkcję jaka jest, z tą różnicą, że była to liczba początkowa i liczba bitów.

Ciekawostka: najwyraźniej Perl w pewnym momencie użył skrótu Jenkinsa .

Obwoluta

print(f(int(input())))

Przykłady

>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167
Sp3000
źródło
6

C ++, 148 bajtów

typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<<i)|(o>>(128-i));o*=p;o^=b[n];}}

__uint128_t jest rozszerzeniem GCC i działa zgodnie z oczekiwaniami. Hash opiera się na iteracji hash FNV (chociaż pożyczyłem ich primea liczbę pierwszą są to pierwsze cyfry Pi w heksie) z rotacją podobną do sha1 na początku każdej iteracji. Kompilowanie z -O3haszowaniem pliku 10 MB zajmuje mniej niż 2 sekundy, więc wciąż jest margines na zwiększenie iteracji w wewnętrznej pętli - ale dzisiaj czuję się hojny.

Odblokowane (zmienione nazwy zmiennych, dodane komentarze, białe znaki i para nawiasów klamrowych) dla Twojej przyjemności z łamania:

typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;    
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<<i)|(output>>(128-i)); // variable roll 
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];        
        }
    }
    // computed hash now available in output
}

Sugestie dotyczące gry w golfa są mile widziane (nawet jeśli nie uda mi się poprawić kodu na ich podstawie).

edytuj: poprawiono literówki w nieblakowanym kodzie (wersja w golfa pozostaje niezmieniona).

Tucuxi
źródło
owydaje się niezainicjowany. Gdzie outputjest zadeklarowany? A może ojest output?
Vi.
To samo dotyczy n. Czy rzeczywiście sprawdziłeś kod „nienablowany”, aby go uruchomić?
Vi.
Zaczął bruteforcer ...
Vi.
Nawet wersja 3-rundowa nie jest łatwa.
Vi.
@Vi. Naprawiono wersję nieglifikowaną - przepraszam, że nie sprawdziłem jej lepiej. Jestem dumny z tej wewnętrznej pętli; U i=81;i-=3mogłoby być jeszcze bardziej podłe, bez znacznych kosztów w czasie wykonywania.
tucuxi
5

CJam, 44 bajty [ pęknięty ]

lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

Dane wejściowe są w bazie 10.

CJam jest wolny. Mam nadzieję, że uruchomi się w ciągu 1 sekundy na jakimś komputerze ...

Objaśnienia

lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

Cóż, dwuwymiarowe rzeczy wydawały się słabością ... Miał na celu przyspieszenie niektórych powolnych obliczeń na początku. Ale nie może uruchomić się w sekundę bez względu na to, co robię, więc w końcu usunąłem wolny kod.

Powinno być również lepiej, jeśli użyłem bitów binarnych i wyższych zasad.

Wersja C.

__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}
jimmy23013
źródło
Czy możesz dodać opis? Nie wszyscy znają CJam.
orlp
@orlp Edytowano ...
jimmy23013
To zajmuje 0,4 s na moim komputerze, więc jest w dozwolonym zakresie.
Dennis
Co to jest A, B, C itd.? Jakieś macierze? Jakie wymiary? Czy można to łatwo wdrożyć w C?
Vi.
1
Pęknięty , jak sądzę.
Sp3000,
5

C ++, 182 znaków (+ około 51 znaków na płycie grzewczej)

h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

Płyta grzewcza:

void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

Program uruchamiany z funkcją gry w golfa

#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}
Vi.
źródło
2
Myślę, że deklaracja funkcji itp. Liczy się do liczby znaków.
Ypnypn
@Ypnypn, policzył znaki w deklaracji funkcji w golfa.
Vi.
Co to jest skrót wyjściowy? Zakładam, że jest ((h << 64) | j).
tucuxi
Tak. Lub tylko para 64-bitowych liczb. Dowiedziałem się o tym __uint128_tdopiero po wdrożeniu tego.
Vi.
1
@Dennis, Done.󠀠
Vi.
4

Pyth, 8 Cracked

sv_`.lhQ

Wypróbuj online

Trochę głupia odpowiedź, wyjaśnię, jak to działa, ponieważ większość ludzi nie umie czytać w Pyth. Pobiera logarytm naturalny z jednego plus danych wejściowych, a następnie konwertuje go na ciąg. Ten ciąg znaków jest odwracany, a następnie analizowany, a następnie konwertowany na liczbę całkowitą.

Tłumaczenie python wyglądałoby następująco:

import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))
FryAmTheEggman
źródło
Pęknięty ?
Sp3000
4

Python 3, 216 bajtów [ pęknięty ]

def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

Ze względu na niezgodność ze specyfikacją mogę wymyślić przynajmniej jedną drobną lukę, ale poza tym uważam, że jest to dowód przynajmniej na brutalną siłę. Sprawdziłem między innymi pierwsze 10 milionów skrótów.

Pod względem golfa byłoby to krótsze w Pythonie 2, ale poświęciłem kilka bajtów na wydajność (ponieważ prawdopodobnie i tak nie wygra).

Edycja: To była moja próba zaimplementowania Very Smooth Hash , ale niestety 128 bitów było zdecydowanie za małe.

Obwoluta

print(f(int(input())))

Przykłady

>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

Wyjaśnienie kodu

def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

Przykład wypełnienia dla f(6):

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)
Sp3000
źródło
Pęknięty
feersum
4

C, 87 bajtów [ pęknięty ]

To jest kompletny program; nie wymaga opakowania. Akceptuje dane binarne przez stdin i wysyła szesnastkowy skrót do standardowego wejścia.

c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

Oblicza to tylko 64-bitowy skrót, więc biorę tutaj trochę ryzyka.

Jeśli ktoś się zastanawia, dwie stałe 'foo+'i 'bar/'są liczbami pierwszymi 1718578987 i 1650553391.


Przykłady:

Ignoruje wiodące zera:

echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

Dane wejściowe jednobajtowe:

echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

Dane wejściowe wielobajtowe:

echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c
piskliwy kostuch
źródło
Jak zachowywać się z „” i „aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”?
Ismael Miguel
1
foo|(d5c9bef71d4f5d1b) i foo\(d5c9bef71d4f5d1b) wytwarzają BARDZO podobne skróty.
Ismael Miguel
1
Zniszcz to!!! \x00i \x00\x00!
Ismael Miguel
1
Opierając się na komentarzach na czacie, uważam, że to jeszcze nie jest złamane? Tylko podwójne sprawdzanie, ponieważ głosowany komentarz może być mylący dla tych, którzy szukają niezrackowanych skrótów.
Sp3000
3

J - 39 bajtów - pęknięty

Funkcja przyjmuje ciąg znaków jako dane wejściowe i zwraca liczbę całkowitą <2 128 . Zakładam, że musimy nazwać naszą funkcję, aby była poprawna, więc usuń kolejne 3 znaki z liczby, jeśli możemy przesłać anonimowe funkcje.

H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

Dla tych z was, którzy nie czytają hieroglifów, oto podsumowanie tego, co robię.

  • a=.(2^128x)&|@^/@ Jest to podprogram *, który pobiera tablicę liczb, a następnie traktuje go jako wieżę mocy, w której potęguje się mod 2 128 . Przez „wieżę mocy” mam na myśli, że jeśli podasz dane wejściowe 3 4 5 6, to się obliczy 3 ^ (4 ^ (5 ^ 6)).
  • (".p:@+5,9:)aTa funkcja pobiera ciąg znaków, konwertuje go na liczbę N , a następnie oblicza ( n +5) -te i ( n +9) -te liczby pierwsze, a następnie wyrzuca ana nią przed nim. To znaczy, znajdujemy p(n+5) ^ p(n+9)mod 2 128, gdzie p(k)jest k-ta liczba pierwsza.
  • H=:_8...\(a...)]Wykonaj powyższą funkcję na 8-znakowych podblokach wejścia, a następnie awszystkie wyniki razem i wywołaj wynikową funkcję skrótu H. Używam 8 znaków, ponieważ kfunkcja „ -ta liczba pierwsza” J kończy się niepowodzeniem, gdy p(k)> 2 31 , tj. k=105097564Jest największym sejfem k.

Mam kilka przykładowych wyników. Możesz spróbować tego samemu online na tryj.tk , ale naprawdę polecam robienie tego w domu, pobierając interpreter z Jsoftware .

   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

* Technicznie rzecz biorąc, nie jest to funkcja sama w sobie, przywiązuje się do innych funkcji i działa na ich wynik. Jest to jednak kwestia semantyczna J, a nie różnica konceptualna: przebieg programu jest taki, jak to opisałem powyżej.

algorytmshark
źródło
Pęknięty
Sp3000,
2

Python 3, 118 bajtów [ pęknięty ]

def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

Wcięcie to pojedyncza karta. Prosty skrót, jeszcze nie przetestowałem go dokładnie.

Zadzwoń w następujący sposób:

print(H("123456789"))

wynik: 73117705077050518159191803746489514685

Tomsmeding
źródło
Jak wejściową liczbę całkowitą należy przekonwertować na ciąg znaków w celu użycia w algorytmie?
feersum
Testowałem @feersum base-10 string. Nie używa niczego, ale ord(c)tak naprawdę, każdy ciąg znaków zrobi :) (oprócz rzeczy takich jak nul chars, myślę, że dzięki temu kolizje skrótów są naprawdę łatwe. Więc trzymaj się łańcucha 0-9.)
tomsmeding
1
Złamałem : codegolf.stackexchange.com/a/51160/41288 . Zacząłem od obserwacji, że ciągi takie jak „10000” i „20000” wytwarzają bardzo bliskie skróty. Zaczął się bawić z coraz większą liczbą zer, a po około 128 dowolna cyfra + k * 4 zera powtarza zwraca ten sam skrót niezależnie od k.
tucuxi
@tucuxi Już myślałem, że nie powinno być zbyt trudne; Cieszę się, że to nie było trywialne, ale i tak ktoś to złamał. Dobra robota.
tomsmeding
2

C ++, 239 bajtów

Mój pierwszy golf golfowy! [ Proszę, bądź delikatny ]

#define r(a,b) ((a<<b)|(a>>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

Wersja bez golfa:

I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

Nie najlepszy skrót, a na pewno nie najkrótszy istniejący kod. Akceptowanie wskazówek golfowych i liczenie na poprawę!

Obwoluta

Prawdopodobnie nie najlepszy na świecie, ale mimo wszystko

I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}
SpelingMistake
źródło
2
Wygląda solidnie, ale z 64 bitami może podlegać brutalnemu forsowaniu. Istnieje około 50% szans na znalezienie kolizji w testach ~ sqrt (n) (spośród n wszystkich wyników); 2 ^ 32 próby to niewiele dla współczesnego komputera.
tucuxi
Wrapper nie ma wtrąceń nagłówka i ogólnie prowadzi do wielu równych skrótów.
Vi.
Podaj próbki skrótu. Dla mnie zarówno „3”, jak i „33” prowadzą do 481c27f26cba06cf (przy użyciu tego opakowania).
Vi.
Pęknięty: codegolf.stackexchange.com/a/51215/41288 . Podejrzewam tuż przed @Vi. dowiedziałem się, dlaczego tak wiele skrótów było równych.
tucuxi
1
Prawidłowa kolizja (bez użycia błędów): printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_-> a4baea17243177fd; printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_-> a4baea17243177fd. Bruteforcer znajduje tutaj kolizje znacznie szybciej niż w innym 64-bitowym haszu tutaj.
Vi.
2

Java, 299 291 282 bajtów, pęknięty.

import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

Wykonuje niektóre operacje na BigIntegers, a następnie przyjmuje wynik modulo 2 128 .

SuperJedi224
źródło
How do I run this? Ideone refuses to compile it.
Martin Ender
1
You can run it on Ideone by renaming the class to "Main" or removing the first "public" keyword (but NOT the second one). Either one will work.
SuperJedi224
Cracked.
Martin Ender
1
@SuperJedi224 Why not remove the first public yourself, saving 7 chars?
user253751
@immibis Because then I don't think it would work right on Eclipse. I'll try it though. EDIT: I guess it does. That's a surprise.
SuperJedi224
2

C, 128 bytes [cracked]

p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

This is more or less the same algorithm as my last effort (cracked by Vi.), but now has enough hamster wheels to generate proper 128-bit hashes.

The four prime constants in the code are as follows:

'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

As before, this is a complete program with no need for a wrapper. The integer I is input via stdin as raw binary data (big-endian), and the hash O is printed in hex to stdout. Leading zeroes in I are ignored.

Examples:

echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a
squeamish ossifrage
źródło
Didn't your example show a collision right there (the first two)?
mbomb007
@mbomb007 No. The input is a number between 0 and 2^(2^30). 0x00 and 0x0000 are both equal to zero, so they produce the same output.
squeamish ossifrage
2

C, 122 bytes [cracked]

long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

Nested loops, half-assed LCGs, and variable swapping. What's not to love?

Here's a ungolf'd version to play around with:

long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

This is a fully self-contains program that reads from STDIN and prints to STDOUT.

Example:

> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

In some simple benchmarks, it hashes around 3MB/s of text data. The hash speed depends on the input data itself, so that should probably be taken into consideration.

Mr. Llama
źródło
1
Cracked: codegolf.stackexchange.com/a/51354/101
aaaaaaaaaaaa
1

PHP 4.1, 66 bytes [cracked]

I'm just warming up.

I hope you find this insteresting.

<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

I've tried it numbers as large as 999999999999999999999999999.
The output seemed to be within the 2128 range.


PHP 4.1 is required because of the register_globals directive.

It works by automatically creating local variables from the session, POST, GET, REQUEST and cookies.

It uses the key a. (E.G.: access over http://localhost/file.php?a=<number>).

If you want to test it with PHP 4.2 and newer, try this:

<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

This version only works with POST and GET.


Example output:

0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

(I assure you that there are numbers that produce the same hash).

Ismael Miguel
źródło
1

C, 134 bytes, Cracked

This is complete C program.

long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

What it does: The idea is to take input as byte array and append pseudo random (but deterministic) bytes at the end to make the length equal to about 2230 (a bit more). The implementation reads input byte by byte and starts using pseudo random data when it finds the first character that isn't a digit.

As builtin PRNG isn't allowed I implemented it myself.

There is undefined/implementation defined behavior that makes the code shorter (the final value should be unsigned, and I should use different types for different values). And I couldn't use 128 bit values in C. Less obfuscated version:

long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}
barteks2x
źródło
Cracked
squeamish ossifrage
1

Python 2.X - 139 bytes [[Cracked]]

This is quite similar to all the other (LOOP,XOR,SHIFT,ADD) hashes out here. Come get your points robbers ;) I'll make a harder one after this one is solved.

M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

Wrapper (expects one argument in base-16 also known as hexadecimal):

import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()
Puzzled
źródło
1
Also, I am not sure that this entry meets the OP's spec, since on my machine the function takes multiple seconds on large inputs. For example, H(2**(2**10)) took around 8 or 9 seconds, while H(2**(2**12)) took around 29 seconds and H(2**(2**14)) took over two minutes.
mathmandan
You are absolutely right, I obviously should have tested the timing for larger inputs. Also, I appear to have forgot to run my own test after that shift was added. The original version was without shift (before posting) and it was passing my "no collisions in the first 100000 integers" test :/
Puzzled
1

Python 2.7 - 161 bytes [[Cracked]]

Well since I managed to change my first hash function into an useless version before posting it, I think I will post another version of a similar structure. This time I tested it against trivial collisions and I tested most of the possible input magnitudes for speed.

A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

Wrapper (not counted in the bytecount)

import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

Run example (input is always a hexadecimal number):

$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB
Puzzled
źródło
1
Cracked.
jimmy23013
Well done jimmy :)
Puzzled
1

Ruby, 90 Bytes

def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

A highly random hash algorithm I made up without looking at any real hashes...no idea if it is good. it takes a string as input.

Wrapper:

def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end 
puts H buildString gets
MegaTom
źródło
Could you please provide the wrapper the question requires?
Dennis
What's the input format? I tried with a number but it says comparison of String with 255 failed (ArgumentError).
jimmy23013
H takes a string, Build string takes the number required by the OP and transforms it to a string.
MegaTom
I think you need a gets.to_i in the wrapper.
jimmy23013
Cracked.
jimmy23013
0

Mathematica, 89 bytes, cracked

Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

Not the shortest.

LegionMammal978
źródło
3
How do you run this without Mathematica? "There should be a free (as in beer) compiler/interpreter that can be run on a x86 or x64 platform or from within a web browser."
Martin Ender
2
@MartinBüttner wolfram.com/mathematica/trial
LegionMammal978
Cracked.
Martin Ender
0

PHP, 79 Bytes (cracked. With a comment):

echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

This does alot of scary things via type-conversions in php, which makes it hard to predict ;) (or at least I hope so). It's not the shortest or most unreadable answer, however.

To run it you can use PHP4 and register globals (with ?i=123) or use the commandline:

php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"
Sebb
źródło
5
The hash's output value looks floating-point. And It's the same for 3000000000000000000000000000000000000000000001 and 3000000000000000000000000000000000000000000000.
Vi.
0

C# - 393 bytes cracked

using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

Ungolfed:

using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

I have never touched cryptography or hashing in my life, so be gentle :)

It's a simple implementation of an FNV-1a hash with some array pivoting on the input. I am sure there is a better way of doing this but this is the best I could do.

It might use a bit of memory on long inputs.

ldam
źródło
Cracked: codegolf.stackexchange.com/a/51277/101 On top of having faulty padding, this is not a cryptographic hash, there is so many ways to break it.
aaaaaaaaaaaa
0

Python 2, 115 bytes [Cracked already!]

OK, here's my last effort. Only 115 bytes because the final newline isn't required.

h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

This is a complete program that inputs a decimal integer on stdin and prints a decimal hash value on stdout. Extra leading zeroes will result in different hash values, so I'll just assume that the input doesn't have any.

This works by stuffing 197-digit chunks of the input number through a modular exponentiation. Unlike some languages, the int() function always defaults to base 10, so int('077') is 77, not 63.

Sample outputs:

$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s
squeamish ossifrage
źródło
1
It didn't use the order of blocks... Cracked.
jimmy23013
Ugh. I give in :-(
squeamish ossifrage