Ten konkurs się zakończył.

W wyzwaniu gliniarzy nie ma już odpowiedzi na cracka.

Wątek towarzyszący Cryptographic hash golf

Dla przypomnienia oto zasady dla złodziei z głównego wyzwania:

Zadanie

Pęknięcia jednego z COP zgłoszeń zamieszczając Podążając napadu na nici: dwie wiadomości M i N w I , tak że H (M) = h (N), a 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 tylko 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

1. eBiznes: 3 pęknięcia, 393 bajty
2. Martin Büttner: 3 pęknięcia, 299 bajtów
3. jimmy23013: 3 pęknięcia, 161 bajtów
4. Sp3000: 3 pęknięcia, 44 bajty
5. tucuxi: 2 pęknięcia, 239 bajtów
6. Vi .: 2 pęknięcia, 87 bajtów
7. feersum: 1 crack, 216 bajtów
8. matmandan: 1 crack, 139 bajtów
9. piskliwy ossifrage: 1 crack, 134 bajty

C, 122 bajty - autor: Mr. Llama

bmaj8PCosFLAJjeHaevvvchnJedmg2iujpePOPivI2x2asw0yKa2eA15xvFJMFe82RGIcdlvxyaAPRuDuJhFjbh78BFsnCufJkarwEyKa0azHxccw5qegpcP9yaO0FKoohanxgiAfK1Lqwba51bKtjacbvdjMmcBkiv8kd62sBd98c4twa98sgj3iPh7nkP4
rlaejTPrua1DhBdg0jrIoDBi8fc1GIJAigivIGaxs1OmfPcctNadK3HErvzPLCeDPD8fkMNPCBcIwuoGfEHegOfk9k9pwktslqaBenaati1uNthMiyk9ndpy7gdIz88iot6A09cbNeIMheyjBvbeegL7aGp7mCb91hCxnvgV5abfImrPfLbrbraAsN6loJgh

Oba ciągi mają skrót bb66000000000000d698000000000000

Podobnie jak „C, 128 bajtów - przez: piskliwy ossifrage”, bity wyższego rzędu nigdy nie wpływają na bity niższego rzędu, można to wykorzystać.

Kod

Visual C ++ używa „ niebezpiecznych ” operacji na łańcuchach

#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>

long long x, y;

//Original hash function (not used for cracking).
void h(char inp[]){
    long long c;
    int index = 0;
    int len = strlen(inp);
    x = 0;
    y = 0;
    long long p = 0;
    for (c = 9; c ; c = (index<len?inp[index++]:-1) + 1) {
        for (++p; c--;) {
            x = x*'[3QQ' + p;
            y ^= c*x;
            y ^= x ^= y;
        }
    }
    printf("%016llx%016llx\n", x, y);
}

//Partial hash, takes a string and a starting point in the stream.
//The byte 0x08 must be prepended to a string in order to produce a full legal hash.
void hp(char inp[],long long p){
    long long c;
    int index = 0;
    int len = strlen(inp);
    x = 0;
    y = 0;
    for (index = 0; index<len; index++) {
        c = inp[index] + 1;
        for (++p; c--;) {
            x = x*'[3QQ' + p;
            y ^= c*x;
            y ^= x ^= y;
        }
    }
}

//Reverse partial hash, backtracks the inner state.
void hprev(char inp[], long long p){
    long long c;
    long long clim;
    int index = 0;
    int len = strlen(inp);
    p += len + 1;
    x = 0;
    y = 0;
    for (index = len-1; index>=0; index--) {
        clim = inp[index] + 1;
        c = 0;
        for (--p; c<clim;c++) {
            y ^= x;
            x ^= y;
            y ^= c*x;
            x -= p;
            x = x * 17372755581419296689;
            //The multiplicative inverse of 1530089809 mod 2^64.
        }
    }
}
const int rows = 163840;
const int maprows = 524288;

//Store for intermediate input strings, row 0 contains 64 columns with 3-char strings,
//row 1 contain 32 columns with 6-char strings and so forth, the final strings will
//contain one string from each column, in order.
char store[7][rows][512];

//Storage for a hashmap, used for matching n strings with n string in O(n) time.
char map[maprows][512];

int _tmain(int argc, _TCHAR* argv[])
{
    char alpha[] = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int row;
    int col;
    int layer;
    int a=0, b=0, c=0;
    int colzero;
    //Produce some starting strings.
    for (row = 0; row < rows; row++){
        //All column 0 strings begin with 0x08 in order to imitate the hash.
        store[0][row][0] = 8;
        colzero = 1;
        for (col = 0; col < 64; col++){
            store[0][row][col * 8 + colzero] = alpha[a];
            store[0][row][col * 8 + colzero + 1] = alpha[b];
            store[0][row][col * 8 + colzero + 2] = alpha[c];
            store[0][row][col * 8 + colzero + 3] = 0;
            colzero = 0;
        }
        a++;
        if (a >= 52){
            b++;
            a = 0;
            if (b >= 52){
                c++;
                b = 0;
            }
        }
    }
    //Layer for layer, column for column, build strings that preserve successively
    //more zero bits. Forward calculated partial hashes are matched with backwards
    //calculated partial hashes.
    for (layer = 1; layer < 7; layer++){
        int slayer = layer - 1;
        int swidth = 1 << (slayer + 3);
        int width = 1 << (layer + 3);
        int slen = 3 << slayer;
        int len = 3 << layer;
        int colnum;
        int layershift=slayer*8;
        for (col = 0,colnum=0; col < 512; col+=width,colnum++){
            printf("Layer: %i, column: %i\n",layer,colnum);
            memset(map, 0, sizeof map);
            int col2 = col + swidth;
            for (row = 0; row < rows; row++){
                hprev(store[slayer][row] + col2, 1 + slen*(1 + colnum * 2));
                x = (x >> layershift) & 255;
                y = (y >> layershift) & 255;
                int index = (x << 3) | (y << 11);
                for (a = 0; a < 8; a++){
                    if (map[index + a][0] == 0){
                        strcpy_s(map[index + a], store[slayer][row] + col2);
                        break;
                    }
                }
            }
            int destrow = 0;
            for (row = 0; row < rows && destrow < rows; row++){
                hp(store[slayer][row] + col, !!colnum + slen*(colnum * 2));
                x = (x >> layershift) & 255;
                y = (y >> layershift) & 255;
                int index = (x << 3) | (y << 11);
                for (a = 0; a < 8 && destrow < rows; a++){
                    if (map[index + a][0]){
                        strcpy(store[layer][destrow] + col, store[slayer][row] + col);
                        strcat(store[layer][destrow] + col, map[index + a]);
                        destrow++;
                    }
                }
            }
        }
    }
    memset(map, 0, sizeof map);
    char temp[1000];
    std::ofstream myfile;
    myfile.open("hashout.txt");
    for (row = 0; row < rows; row++){
        hp(store[6][row], 0);
        sprintf(temp, "%016llx%016llx", x, y);
        myfile << store[6][row] <<" " << temp << "\n";
    }
    myfile << "\n";
    //The final hash set has 96 of 128 output bits set to 0, I could have gone all
    //the way, but this is enough to find a collision via the birthday paradox.
    for (row = 0; row < rows; row++){
        hp(store[6][row], 0);
        long long xc = x;
        long long yc = y;
        int pos = (xc >> 45 | ((yc >> 48) & 7)) & (maprows-1);
        while (map[pos][0]!=0){
            hp(map[pos], 0);
            if (x == xc && y == yc){
                myfile << store[6][row] << "\n" << map[pos] << "\n";
                sprintf(temp,"%016llx%016llx", x, y);
                myfile << temp << "\n\n";
            }
            pos = (pos + 1) % maprows;
        }
        strcpy_s(map[pos], store[6][row]);
    }
    myfile.close();
    printf("done");
    getchar();
    return 0;
}

Python, 109 bajtów przez Sp3000

Zauważ, że Martin pękł jako pierwszy, więc nie jestem pewien, czy to zasługuje na punkty. Z drugiej strony zrobiłem atak przedobrazowy zamiast zwykłej kolizji - znacznie silniejszy wynik. Oznacza to, że możesz nadać mu dowolną wartość skrótu i ​​skonstruuje dane wejściowe, które wygenerują tę wartość skrótu.

M = 2**128

# The hash to crack.
def jenkins(n):
    h = 42
    while n:
        h += n & (M - 1)
        n >>= 128
        h *= 1025
        h ^= h >> 6
        h %= M

    h *= 9
    h ^= h >> 11
    h *= 32769

    return h % M

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def invxorshift(h, s):
    r = h >> s
    while r:
        h ^= r
        r >>= s
    return h

def moddiv(a, b):
    return (a * modinv(b, M)) % M

def jenkins_crack(h):
    h = moddiv(h, 32769)
    h = invxorshift(h, 11)
    h = moddiv(h, 9)
    h = invxorshift(h, 6)
    h = moddiv(h, 1025)
    h -= 42
    return h

I aby pokazać, że to działa:

>>> from crack import *
>>> n = 2**128 + 1337
>>> h = jenkins(n)
>>> n2 = jenkins_crack(h)
>>> h2 = jenkins(n2)
>>> n != n2
True
>>> h == h2
True

I aby podać określony zestaw liczb, które kolidują:

N: 2**128
M: 43617

Python, 109 bajtów przez Sp3000

340282366920938463463374607431768211414

i

113982837842983129870077688367927159293402923522160868689804433865221255200726

oba dają

132946164914354994014709093261515948032

Algorytm dzieli dane wejściowe na fragmenty 128 bitów i wielokrotnie modyfikuje skrót (zaszczepiony do 42) z każdym fragmentem, zanim na końcu dokona dodatkowego haszowania. Aby znaleźć kolizję, naszym celem jest znalezienie dwóch liczb, które dają taki sam wynik po uruchomieniu następującego pseudo kodu na każdej porcji:

hash += chunk
hash += (hash << 10)
hash ^= (hash >> 6)
hash %= 2**128

Ponieważ hash jest pobierany mod 2 ¹²⁸ , chcemy szukać liczb, które przesuwają wszystkie interesujące rzeczy poza ten zakres bitów. Ale hash jest zaszczepiony, 42więc na początku ma kilka mniej znaczących bitów:

000000000000000000000000 ... 000000000000000000101010

Moim pomysłem było pozbycie się tych fragmentów podczas dodawania pierwszego fragmentu. Więc spróbujmy 2 ¹²⁸ -42:

           000000000000000000000000 ... 000000000000000000101010     hash = 42
           111111111111111111111111 ... 111111111111111111010110     chunk = 2**128 - 42
          1000000000000000000000000 ... 000000000000000000000000     hash += chunk
10000000001000000000000000000000000 ... 000000000000000000000000     hash += hash << 10
10000010001000001000000000000000000 ... 000000000000000000000000     hash ^= hash >> 6
           000001000000000000000000 ... 000000000000000000000000     hash %= 2**128

To dość proste, więc spróbujmy użyć tego jako jednej z dwóch liczb. (Rzeczywiście, pierwszy numer kolizji, którego użyłem, to 2 ¹²⁸ -42.

Jak znaleźć kolejny numer z takim samym wynikiem? Po jednej iteracji hash już nie jest 42, ale 2**122jak właśnie pokazaliśmy. Teraz, dodając drugi fragment do naszego numeru wejściowego, możemy uruchomić kolejną iterację. Możemy wybrać drugi fragment za pomocą tego samego argumentu, co ten, tzn. Chcemy 2 ¹²⁸ -2 ¹²² . Następnie wynik pośredni hash += chunkbędzie identyczny i na końcu otrzymamy ten sam wynik.

Możemy więc obliczyć dwie liczby kolizji:

>>> 2**128-42
340282366920938463463374607431768211414L
>>> 2**128-42 + ((2**128-2**122)<<128)
113982837842983129870077688367927159293402923522160868689804433865221255200726L

Możemy łatwo wygenerować o wiele więcej takich kolizji.

Mathematica, 89 bajtów autorstwa LegionMammal978

0

i

16

Oba zbiory 0.

Zasadą tego policjanta jest ewolucja „losowego” binarnego automatu komórkowego 1-D z „losowego” stanu początkowego dla „losowej” liczby kroków, a następnie interpretacja pierwszych 128 komórek wyniku jako liczby całkowitej.

Problem polega na tym, że reguła jest określana po prostu przez Mod[#^2,256], że dowolna wielokrotność 16 daje regułę 0, która jest banalną regułą, w której wszystkie komórki są zawsze zerowe. Jeśli dane wejściowe nie są podzielne przez 99, będziemy rozwijać co najmniej 1 krok, więc wynik zawsze wynosi zero. Zatem dowolne dwa wielokrotności, które nie są wielokrotnościami 99, zdecydowanie się zderzają. Jednak wejście daje 0 również 0 (mimo że nigdy nie używa reguły), ponieważ warunkiem początkowym jest tylko binarna reprezentacja wejścia (w tym przypadku wszystkie zera).

Poza tym możemy znaleźć inne kolizje, które są całkowicie niezależne od reguły. Jak wspomniano powyżej, dowolna wielokrotność 99 oznacza, że ​​automat komórkowy wcale się nie rozwinął, więc wynikiem są po prostu pierwsze (najbardziej znaczące) 128 bitów stanu początkowego ... który sam jest tylko liczbą wejściową. Jeśli więc weźmiemy dwa wielokrotności, które nie różnią się w pierwszych 128 bitach (wypełnione zerami po prawej stronie), otrzymamy również kolizję. Najprostszym przykładem jest to M = 99, N = 99*2 = 198.

J, 39 bajtów

Pierwszy numer to:

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000

To znaczy 10000000powtórzone 64 razy. Druga liczba to ta plus jeden, tj

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000001

Oba zbiory

322124197561777885386414076216564234267

Wyjaśnienie

Zacznijmy od x := H 10000000 = 146018215378200688979555343618839610915i y := 2^128. Zamiast znajdować a, btakie a == b mod y, będziemy szukać a, btakich x^a == x^b mod y, wykorzystując wieże mocy w algorytmie.

Ale musi być jakiś ktaki, że x^k == 1 mod y, ponieważ x, ysą względnie pierwsze, a do tego kmusimy mieć a == b mod k. Możemy więc znaleźć dyskretny logarytm 1 mod y, a na pierwszy krok dostajemy

x ^ (k = 85070591730234615865843651857942052864) == 1 mod 2^128

Teraz chcemy znaleźć dwie a, btakie liczby a == b mod k. Aby to zrobić, postanowiliśmy ybyć ki staramy się znaleźć a, btakie x^a == x^b mod yponownie. Używając tej samej logiki, bierzemy logarytm dyskretny ponownie i otrzymujemy

x ^ (k = 21267647932558653966460912964485513216) == 1 mod 85070591730234615865843651857942052864

Powtarzamy to, dopóki nie dojdziemy do małego y, w którym to momencie znalezienie dwóch liczb, które mają tę samą modulo, jest banalne y. Po 63 iteracjach y = 4, w tym momencie w zasadzie działają dowolne dwie liczby.

Oto kod Mathematica do generowania dyskretnego łańcucha dziennika:

k = 0; x = 146018215378200688979555343618839610915; y = 2^128; While[y > 10, y = MultiplicativeOrder[x, y]; k++; Print[k, " ", y]];

Daje to następujący wynik .

Pyth, 8 bajtów FryAmTheEggman

99999999999999999999999999

i

99999999999999999999999998

Precyzja zmiennoprzecinkowa nie jest na to wystarczająco duża.

CJam, 44 bajty, użytkownik jimmy23013

Liczby są zbyt duże, aby je opublikować, więc tutaj są na Pastebin: num 1 , num 2 .

Pierwsza liczba to 600^2 = 360000jedynki. Drugi numer jest taki sam, z wyjątkiem następujących zmian:

Positions to change to "2": 605, 1811, 3001, 6603
Positions to change to "4": 1805, 3003, 57348, 208895
Positions to change to "5": 602, 1201, 2405, 3004
Positions to change to "6": 1203, 1802
Positions to change to "7": 12, 609, 5401, 7200
Positions to change to "8": 1, 2, 4, 6, 600, 1200, 1808, 2400, 3600, 4803

Oba hash do 271088937720654725553339294593617693056.

Wyjaśnienie

Rzućmy okiem na pierwszą połowę kodu:

lW%                e#  Read input number as string, and reverse
600/               e#  Split every 600 digits, forming a 2D array
_z                 e#  Duplicate and zip, swapping rows and columns
{           }%     e#  For both arrays...
 JfbDb             e#  Find sum of S[i][j]*13^i*19^j, where S are the character values
                   e#  and the indices are from right to left, starting at 0.
      GK#          e#  Take modulo 16^20

         ...  ...  e#  (Rest of code irrelevant)

Jeśli więc możemy znaleźć dwie liczby wejściowe, aby sumy S[i][j]*13^i*19^jbyły tego samego modulo 16^20zarówno dla początkowej tablicy o szerokości 600, jak i tablicy spakowanej, to jesteśmy skończeni.

Aby trochę ułatwić, rozważymy tylko 600^2 = 360000cyfry cyfrowe, tak że tablica o szerokości 600 ma po prostu kwadrat 600 x 600 cyfr. Ułatwia to wizualizację i jest ważny od tego czasu 10^360000 ~ 2^(2^20.19) < 2^(2^30). Aby jeszcze bardziej uprościć sprawę, rozważymy tylko takie ciągi wejściowe, których kwadrat cyfrowy jest symetryczny wzdłuż głównej przekątnej, tak że pierwotna tablica i tablica spakowana są takie same. Pozwala nam to również zignorować początkowe odwrócenie łańcucha i numerację indeksów od prawej do lewej, które się wzajemnie znoszą.

Na początek możemy przyjąć pierwszą liczbę 360000. Aby uzyskać drugą liczbę, chcemy to zmienić, zmieniając niektóre cyfry, aby sumy były takie same modulo 16^20, zachowując symetrię kwadratu cyfry. Osiągamy to, znajdując listę trójek (i, j, k), aby

sum of k*(13^i 19^j + 19^i 13^j) == 0 mod 16^20

gdzie 1 <= k <= 8jest kwota na zwiększenie cyfry 1 o (tj. przejście na cyfrę od 2 do 9 - moglibyśmy uwzględnić 0, ale nie potrzebowaliśmy jej) i 0 <= i < j < 600są parami indeksów.

Raz mamy (i, j, k)trojaczki, zmieniamy cyfry na (i, j)i (j, i)aby 1+kuzyskać drugą liczbę. Trojaczki zostały znalezione przy użyciu chciwego algorytmu cofania, a dla drugiej liczby powyżej cyfry kwadrat wygląda następująco:

188181811111711 ...
815112111711111 ...
851611111111111 ...
116114118112111 ...
811115111111111 ...
121451111111111 ...
811111111111111 ...
111111111111111 ...
111811111111111 ...
171111111111111 ...
111111111111111 ...
111211111111111 ...
711111111111111 ...
111111111111111 ...
111111111111111 ...

............... .
...............  .
...............   .

Na przykład (i, j, k) = (0, 1, 7)odpowiada zmianie cyfr (0, 1)(pozycji 600*0 + 1 = 1) i (1, 0)(pozycji 600*1 + 0 = 600) na 1 + 7 = 8.

Oto backtracker w Pythonie 3, chociaż dokładniejsza analiza wykazała, że ​​mieliśmy szczęście, ponieważ tak naprawdę nie nastąpiło cofnięcie:

n = 16**20
L = [(k *(pow(13,i,n)*pow(19,j,n) + pow(19,i,n)*pow(13,j,n)) % n, i, j, k)
     for i in range(600) for j in range(600) for k in range(1, 9) if i < j]

L.sort(reverse=True)
stack = [(n, 0, [])]

while stack:
    k, index, result = stack.pop()

    if k == 0:
        print(result)
        break

    if index == len(L):
        continue

    stack.append((k, index+1, result)) # Don't include triplet

    if L[index][0] <= k:
        stack.append((k - L[index][0], index+1, result + [L[index][1:]])) # Include

Jako bonus, oto niezbyt wydajny port skrótu w Pythonie 3. To było bezużyteczne.

PHP 4,1, 66 bajtów przez Ismaelowi Miguel

$ A=0111129112911291111111111111111111111111 php hash.php 2> /dev/null ; echo
0100038003800381129111111111111111111111
$ A=0111129112911291129111111111111111111111 php hash.php 2> /dev/null ; echo
0100038003800381129111111111111111111111
$ cat hash.php 
<? $a = getenv("A"); for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

Znaleziono przy użyciu prostego iterowanego mieszania, zaczynając od 1:

$ i=1; while true; do i=$(A=$i php hash.php  2> /dev/null); echo $i; done | head -n 10
0111111111111111111111111111111111111111
0100000000000001129111111111111111111111
0111129111111111111111111111111111111111
0100038000000001129111111111111111111111
0111129112911111111111111111111111111111
0100038003800001129111111111111111111111
0111129112911291111111111111111111111111
0100038003800381129111111111111111111111
0111129112911291129111111111111111111111
0100038003800381129111111111111111111111

Python 3 (216) autorstwa Sp3000

Moje wiadomości są

5012053369354645637214643587103597313576086380250249302980438772005248488380915054746146050001036696049972235875591571028140916001206596142280971107479334216535925703480968283657357930602076844092875640359192729378384507238123245417656548512647301639542279794868512420586823155070914644206130805893968511673770843170450832829657206145931885656157628306896903719624729809643572222159364893644113710867223921580178741177106141068298067479650611992859787419779579962211254029169589775046869542029842374359998053713002047081002506346875804341770199884355810931652447801492691887376948615365487982834690942054717077615539311699691010938426302886867891090301248321702485904291177813145565144089044261424329155436660979948932491709511914065619715728353376578192548334780893602675684085757434059540582004872746967999949306946618036846307799677491651967418565531672392468089533111553281620101129322575737949904022139471688252420467041529301533363008476437812216585923822571793353317799365005036029476865
5012053369354645637214643587103103086948976188724715498910865650846170784131001427390927276355140411160919276493388206817700368694224128444524223814513348177926532982330730066315320819293979046126543806115318009892783577432467861426768883700930779409885418980853424256180864755881414774514084197887594253752179391098292488771920695965135791582218083012144604515253506370334133858904659263953147111654656123599460222236152128559750436960308887683690915261431659087040402402092795259541564130228515353133867041828417398395559815392177084002004583988047406317670433664624642858480970640416500369367395538257341309676777745698712896295462462064271676447460293684100001583256400774270688958051470568447233589146620275159126426142305307007744396679875427883384557759778766330566230012377845843842097372663092379922300568052486301863154557664156185573021849420011058607321977550938866119133331529852821217331665195832442542012455132139770813510559894254061471149750738447764616026512400623344132554752

Użyłem tego kodu Python 2 do ich wygenerowania:

a,b = 14460445391122031029,16815296360833931837 #http://www.numberempire.com/numberfactorizer.php
pr = ~-a * ~-b

m0 = reduce(long.__or__, [long(b) << 26*i for i,b in enumerate(bin(pr)[2:])])
m1 = 1 << 26*i-1
m0 |= m1

#print m0, m1
print f(m0), f(m1)

Duży moduł był iloczynem dwóch liczb pierwszych ai b. Wydaje mi się, że mieliśmy nadzieję, że uwzględnienie semiprime nie byłoby możliwe, ale wydaje mi się, że 128 bitów jest za małe, ponieważ jakaś strona internetowa od razu dała mi odpowiedź.

Modulo grupy multiplikatywnej abbędzie miało kolejność (a - 1) (b - 1), co oznacza, że ​​jeśli podniesiemy dowolną liczbę do tej potęgi, będzie to musiało dać 0 lub (zwykle) 1. Więc umieszczam 1 bit w miejscach, które skutkowały 2 ^{(a-1) (b-1)} są mnożone w hasz. Wtedy druga wiadomość jest w zasadzie 0, ale ustawiam jeden inny bit w każdej liczbie, aby długości były takie same.

Myślę, że byłoby bardziej denerwujące, gdyby hash był wyrównany pod każdym względem, a nie tylko po użyciu wszystkich liczb pierwszych. Wtedy zbudowanie dla nich dowolnych wykładników nie byłoby tak proste.

C, 128 bajtów - autor: squeamish ossifrage

Następujące dwa ciągi znaków mają skrót do wszystkich zer:

dddl|lddH4|@dhxdxXdh0TXPdhhdx(dTxtlpdd@4Lhd|hdDpdhDdXLdXP4(PdddL|ldXdD(lddX4|0hddp4|ddP4Lxdp0dP@dhpTxPdhXdXxdhHDxHdllLttdhPT8pd(pT8Pdd0TL8dlLLTtddPtl8dP@DPPdhhDxhd804(pdh0Txpd@DDpLdhL4xtdXXdHXdd04lXht40dlddh4|@ddPTLXdhhDXHhtPH40dh0t8pd(pt80dhPtX0dhLtXtdhLT8thlLplTdhpt80dh0txpdhHDX(hdX8txdhhdxHdp|d@tdhlTx4dlptdxdh0T8PdT@t|Hdd@tL(ht(8DhdhHD8(hpHHP8dhLtXtdX8dhxdhpt8Pd@(D@Hdd@tLhdtxTLPdd0tlxhhL8X|dd8t|0dT04|Xddxt|phxxxhhdhpt8PhhxX8hdhlTX4dd4l||dd@TLHdXlTHtdhHd8hdX0THPdh(D8(d8xdh8dhp4xPd0HDp(dhl4xTdxlthtdhlTx4d8lT(TdhhdXHdphdP(dhp4x0d0Xd0XddTl||d88DH8dhhdxhdx|tHDdhLT8Thll0lTddPTlXdxXd(xdd0Tlxdhp480dhp4x0dd|LltdhPt80dtll|dddPTlXdxXd(xdd0Tlxdhp480dhp4x0dd|LltdhPt80dtll|dddP4Lxd|ptT8dhddxldH|4xDdhp4x0dDdl|LdhtD8|hhHx88ddpTL8hhphx@dhtd8|dphDP(dh0tx0hhDHx4dhpt8Pd@(D@HddLLLDhh|xxldhl4xTdhL4x4dhPt8Pd(HDx(dh(D8Hd4PT|8ddH4|@hh4H8ddhxd8XdDP4lxdhHd8hdl04d8ddXT|phdh8Thdd@TlHdhXdxxdllL44dD@4lHdhxdxXhd8XtxddLlLddT@T|(dhxdXXd|P44Xdhpt8pdlHDT0dhL4Xtd@ldpDdddl|LdXP4h0dhltXtdX8d(Xdh|tXdhhLXX|dhxd8XdP@D0PdhXDxXhtpHtPdd84|pddtl||dh(dx(d88Dh8ddx4|PhtT0DLdd@tL(hdX8Txdhp480d08d08dlll44d4dLLldhTdX|hh8Xxhdh048pd08d08ddPtL8d4H4l@dhhdxHd|pt4Xddp4lXhp(hPxdh|48DdxhDh(ddLlldd8XdH8dddl|LdLHDT0dhpt8pdlHDT0dh(d8hdTHtl@ddptl8dt84LPdh8dxxdlptD8dd04lxhhH8XxddDl|ldP|D@4ddTl||d|ptT8dh(dXhhd8X48dhPtXpd(8DxXdh@TX@dDP4L8dhpTX0d4@4|hdhHdxHdX8DHxdhPT8PhllplTdh0TXPhlXHLXddp4lXhtHXD(dhP4X0htH8dhdhLTx4hpxHPHdhhd8(dX8DHxdhpt80hhdHxTdlll44d@Hd@(dhhDxhdh0t8Pddh4|@ddh4|@dhptx0dpPD0@ddPtlxdhPT8pdhhdX(htTpDLdd@4L(dLHDtpdhxd8xdt84lPdlpTdxdDPTLXddLLLDdxlThtdlhd4PdXLTh4ddptLxd|@44(dhhd8HdtDLLlddxt|pd|hDd0ddPtLXhl@H|pdhDD8ld8dDhLdhXDXxdDxT|PdhHD8hdp8dpxdhp480d@XD@xddpTLXdHhD8(ddllLDdD|LL4dhpt80d@LdPDdh|4xDdP8dpXddLllddl8d4@dhptXpdd(4|@dhltx4d0Dd@LdhptxphdPHdpdhl4xTdxlthtdhHD8HdTdllldhLtX4dXP4(PdhLTxTd4X4LpddlllDdlpTD8dllltTdL(dtPdhDDxLdhLTx4dhptx0d|0T4Xdhl4xTdHL4XtdhpTXpdLp4dxddHt|@dHL484dhHDXHdHLtxtdhDdXldxL4H4dh|TxDhh8xX(dhLt8td8Lt(TdhHDx(d4DlLlddXT|PdHHD8(dlll44dlP4dxdd@tL(dL@4dhdd0tLxd4X4l0dhhdxhdDlLldddLLlddD04l8ddPtlxd(hd8hdd(T|@hdDp4|ddP4Lxdp0dP@dhptXpd(p4X0dhhd8(d8pT(0dh8d8Xhd(XT(dhddxLd@XD@8dd@tlhd@ld0ddhTD8|hhPH8@ddtl||dH0Tx0ddLlLddhp480dhHdxhd4lL|DdhXD8xdhhDX(dh048pd4Ll|ddddl|LdXP4h0dlll4thhdhxtddP4LXdhXdxXdhpTX0hdXXtxddlLLddx0Th0ddTl||hlhhlHdd|Ll4dHDdXldhhDX(hpxh0HdhDDXLdXDDhLdlhDTpht8Xdxdhpt8phhHXX8dd(t|@dHl4xtddp4LXhxhXH8dhDDxldDXt|PdhTDX|d|0ttxdhdDXLdDLLLddd84|PdT84LpdlhDTphl8hlxdhXD8xdHpt8Pdlhd40ddHT|@dhxdX8dhlT84dh|T8dhlXHLxdhxDxXdT4lL|dlllttd@xd@xdhhDXHhtXXD8dh(d8(d4p4|8dd04lxdxPThpdhHD8Hhdhx4hdhl4xthl|pLDdhltX4dhP4XPdd0Tlxdl@tDhddP4lXd0xD0xdhHD8Hd@8D@xdh0T8Pd0XDpxddPtl8dP@DPPdhhDxhd804(pdd04L8hpxHphdhDdxLdppD0@dd@tl(d88dHXdh0txpdXhDhHdd@Tlhdx8DHXdh0tXPdxxdH8dhPT8Pd484LPdlhD4pdxxdHxdd|Lltdhptx0dhlTx4hp8HPhdhPt8pdt4lL|ddtl||dH0Tx0dhxd8xhl@H|pddLllDhldP||dhdD8ldXLTHTdlhDTpddllLddd04lxhhH8Xxdh|48DdP8d0XddLLldd|@44hdhhd8hd4x4L0dhltXthh4H8Ddh4DX|dD@Tlhdh0tXpd8|T(ddhtDX|dlhdTPdd@tLhdThTl@dh8D8xdT(TL@dd@Tl(d8Hd(hdhXdxxhtHXdhdd0tl8d|HDDPdd8T|PdH04xPdd@Tl(d|@4t(dd(4|@dHp4xpdhpt80dh0txpdhp48phdXxTxdhhDXHhtPH40dh0t8pd(pt80dd8T|pdlxdt@dhp48PdD0TLXdh0t8Pd|lldTdh|t8DhphHp8

ddTl||d4|L|4dhptX0d4dllLddxT|pdxXdH8dlhDtPhlpH|@dd|Lltdhptx0dhlTx4hp8HPhdhPt8pdt4lL|ddtl||dH0Tx0ddLLLDd8tdH|dhDD8LdtxtLpdhxD8Xhd8xtxdhPt8Pd(8DX8dhddxLd0xd08dd0Tlxdxdd(Lddh4|@dXpt(Pdh048pd0xd0xdhhDX(d8p4Hpdh0480d(8DX8dhL4x4d4PT|XddPTLXdPDd@Ldddl|ld(P4X0ddDL|lht88DXdhPtxpd((Dx(dh0tx0dxXd(8dhpT8Pd0xD0XdlhD4pdT0T|8dh04XPht0H40dlhDtpdpHDP(dhlTXtdPHdpHdhXDxXhpPH0pddDl|lhltp|Ldh04x0dtXTL0ddLLLDdLhdtpdhL4xtdHDdXLddxt|0d4X4l0dh(Dxhdx04h0ddllLDd0PD0@dhXDxxhdx848dhDDxldpXDpXdhPt8pdhltxTdd04lxhhH8Xxdh|48DdP8d0XddLLldd|@44hdhhd8hd4x4L0dhltXthh4H8Ddh4DX|dD@Tlhdh0tXpd8|T(ddhtDX|dlhdTPdhlTXtdTX4L0dd@Tlhhh8xXHdhPt80d|XdD@dhp4xphd4Ptldd|LL4dL|ltDdhPTx0d80T(pdhpt8pd|pTtXdhpTX0hhth8Ddhxd8xdphdP(dh8D88dp(DPhdhHD8(htxXdXdh8dXXdXpTH0ddx4|PdpXDPxdhXDXXdxxdhXdhlt8Td@xD@8dhP4XPdhltX4dd@tlHdhXDxxdhPtXPd(8Dxxdh0t8PhdpHd0dh(D8HdX(D(Hdd@tLhht|@4Tdd@4lHdttll|dd0tlXhh|xxldd@TLHdlHdTPdd|LL4dt@T|hddx4|PdlHdtPddTl||d88DH8dlhdTpd40t|xddht|@dpPDP@dhHDxHhxthHDdhddxldxtDH|dhltx4d8Dd(ldd|LLthp0H0Pdhl4x4d|0T4Xdd|ll4dt8tLPdd@4lhd|0TTXddPtLXd(8d8xdhPTxPdHxd8xdhHDX(ddLllddhp48Pd0@d0PdhptxpdX(DhHdd0TlXhtPHTPddh4|@dTDlLldhDDxLhp(hPxdhdD8ldXLTHTddPtLXdTh4L@dhLtxTdlpTd8dhPtXpdhLtX4ddPTlXdxxdhXdhhd8(d404|8dhTd8|dhL4Xtddp4l8d4X4LpdhL4Xtd@ldpDdddl|LdXP4h0dhpTX0htXxDxdhpt8pddLlLddhp4XPhp0H00dh4Dx|dlp4D8dhPtxpd((Dx(dh0tx0dxXd(8dhDDxlhlL0ltdhhDxHd@|d0TdhHdxhdL0tD8dhhD8hhl|pLdddxt|pd|hDd0ddPtLXhl@H|pdhxDXxd8DdhldlhdtphpphppdhpT8PdH8dxXdlhd40dtXtlPdhTd8|dXlthtdhTDX|dx|4HDddxT|pdHDd8ldhL4X4dhP4XpdhtDx|ddXt|Pdh|T8DdHhdxhddLLLDhlxHl8dh0tXPd|(ddPddDL|LdHhdxhdhp4x0dl8dT@ddXT|phdh8Thdh(DXhd0HDP(dddl|lhd(xT(dhXdXxdTxtl0dd|lLtd8|4hddd4l||dXLTh4dd04lxdP8DP8ddxT|0dXXdh8ddP4lxd0@DpPdh8dXxddp4lxdhLt8tdHTdx|dh4Dx|dxLTHtdhhd8hd@DDpldd04LXdXlT(tdhXdXxdhPT8pdh(DXHdP@dp0ddP4LXdXpThPdllL4td((D8(dh0tXpd|(ddpdh(DxhhdL@DDdhHDx(dxL4(tdhLtXtdl@4dHdhxd8xdTh4L@dhXDXXhhdH8Tdd8T|PdH04xPdlllT4hllpLtdhhDXHhxxXhhdhXDxXdPDd@Ldd0TlXdHLtX4ddDL|ldXLT(4dhPtXPdXXd(8dhpt8phdH8thddxT|pd(ptXpddP4LxdLXDT@dhpT80dLptDxddxt|pdP@Dp0dhptx0d|0T4XdlpTdxdxpt(PdhHD8(d4TlL|dhHDx(d@hD@(dd@tl(d88dHXdh(Dx(d4pT|xddPtl8dP@DPPdhhDxhd804(pdhHD8Hhdhx4hddP4lxhdhXt(dhxdX8dp@DppdlllT4dP0dp@dddl|ldH8DXXdllLT4dPXdp8dd@tLHdlPTd8ddtL||d8PtHpddHt|@hd|@d4dh(dX(hdhXT(dhpT80hdHX4(dlpTdxdtDlLlddxT|pd(ptXpddP4LxdLXDT@dhpT80dLptDxddxt|pdP@Dp0dhptx0d|0T4XdlpTdxdxpt(PdhHD8(d4TlL|dhHDx(d@hD@(dddL|lhtph40dhpTxPdlp4dXdhDDxldpxD08dh(dX(dHlTxTdd|ll4d40t|Xdh0480ht@hT@dhptXphdHxT(dh(D8Hd4PT|8dhpt8pd88dhXddDl|LhxdHHtddPtlXd|pt4Xdd0Tl8d0(D0hdhhd8hdppd0@ddPTlXd8P4hpdhlTx4d8dDhLdd@TLhhllplTddXT|0dH|4XDdh|4xDht8XD8ddptl8dH8d88dd|LLTdh(DXhddHt|@hpXhp(dhdDxLdDhT|@dhP4X0dXhDHhdh0T8Pd((dxhdhhDx(hdx8Txddp4LXd8xDH8dhPTXpdlPtD8dh(DxHd@8D@Xdhl48Td00Dp@dhLT8Tdp(d0(dhhd8(d404|8dhhdx(dx0T(pdd|lL4ddXt|Pdd0TlXhxdH(4ddllLDhhLXX|dhXDx8hl8hLxdhpT80dLPtDXdhptX0dPXd0XddP4lxd0@DpPdlptd8dl(dTPdhxDx8d(ptX0dhpT80htxxdXdhhDxhdXltHtddh4|@d@|dPTdhdDXLhpph0Pdhp48Pdt4lL|dh04xpdLpTD8dd@4lhdl8dt@ddhT|@dPxDp8dd04lXd40t|xdd0TLxdTdlLLddpTLXd|pTT8dd04lxhhH8XxdhddxlhddPT|dd04LXdlhd4pdh8d8xhh|8XLdhxd8xd(8d8xdhp48pd(8DX8dhhDXHd4dllLddx4|0d8PTH0ddPtlxd|P44XdlpTdxd(XDXXddpTlxdHltX4dhLTxtd|HDD0

Funkcja skrótu jest zbudowana w taki sposób, że bity wyższego rzędu nigdy nie wpływają na bity niższego rzędu, dlatego mogę wygenerować kolekcję ciągów, w których wszystkie xbity niższego rzędu są zerowe, a następnie mogę wypróbować połączone kombinacje tych ciągów, aby znaleźć gdzieś więcej niższe bity wynoszą zero itp. Jestem pewien, że istnieje więcej sposobów na przełamanie tego, a także sposoby, które wytwarzają znacznie krótsze łańcuchy, ale w ten sposób uniknąłem mnożenia matematyki.

Python 3, 118 bajtów

int(H("9"+"0"*400))

i

int(H("9"+"0"*4000))

(to znaczy: 9E400 i 9E4000)

Oba produkują

83909358607540647658718900164058931893

Kopiąc nieco głębiej, wydaje się, że jakakolwiek liczba całkowita, po której następuje k powtórzonych cyfr, tak że k> 128 i (k% 4 == 0) zwrócą ten sam skrót. Na przykład H("1"+"1"*32*4)i H("1"+"1"*33*4)są oba 13493430891393332689861502800964084413. Hmmm, 128 ...

Python 2, 161 bajtów, autor: Puzzled

340282366920938463463374607431768211456 (decimal)
100000000000000000000000000000000 (hexadecimal)

i

340282366920938468780317283222139437056 (decimal)
100000000000001203B66F94300000000 (hexadecimal)

Oba mają wyjście:

83F172CC3D050D131F64FD04B8181DC2

Liczby to 2 ^ 128 i 2 ^ 128 + (3 * 5 * 7 * 11 * 13 * 17) ^ 2 * 19 * 2 ^ 32.

Java, 299 bajtów autorstwa SuperJedi224

Pastebin dla M. W trybie binarnym Mma 65535 1s, a następnie 2 0s.

Pastebin dla N. W trybie binarnym Nma 21845 1s, a następnie 174766 0s.

Oba zbiory 0.

Zauważ, że podstawą algorytmu jest i.bitCount()*i.bitLength()+1i ostatecznie bierzemy wynik do potęgi ii przyjmujemy mod 2 ¹²⁸ . Pomysł polegał więc na znalezieniu dwóch, iktóre można podzielić przez cztery, ale gdzie pierwsze wyrażenie daje 2 ³² . Można to łatwo zrobić , biorąc pod uwagę fakt, że 2 ³² -1 i wybierając dwa czynniki dla liczby 1s i całkowitej szerokości bitu liczby.

Edycja: Właściwie jest nieco więcej powodów, dla których Mdaje zero, ale możemy łatwo znaleźć więcej liczb, które dają zero z powodu mojego wyjaśnienia, używając innych czynników 2 ³² -1, takich, że na końcu jest co najmniej 64 zer.

C, 134 bajtów (autor Barteks2x)

10

i

20

oba hash do

0xa609779942cb9ef1

ponieważ algorytm haszywa tylko ostatnią cyfrę!

C, 87 bajtów

$ echo B075343F9832CD60 | ./hash6_ ; echo
fc2e9f02bd284bd1
$ echo 5914BD1B71164C77 | ./hash6_ ; echo
fc2e9f02bd284bd1

Znaleziono za pomocą mojego bruteforcer kolizyjnego.

Python 2, 115 bajtów, przez piskliwy ossifrage

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

i

2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Wartość skrótu nie miała nic wspólnego z kolejnością bloków.

Python 2.x, 139 bajtów według Puzzled

H(2)

i

H(128)

oba wracają

16645614427504350476847004633262883518.

C ++, 239 bajtów autorstwa SpelingMistake

Za pomocą dostarczonego programu „głównego” następujące dwa dane wejściowe generują ten sam skrót:

echo -n "dog" | ./h
481c27f26cba06cf

i

echo -n "fog" | ./h
481c27f26cba06cf

Te pierwsze 8 bajtów wejściowych nie są przetwarzane , ze względu na ten błąd w kodzie:

 for(I i=n;--i;) // and then we use q[i] for this iteration

bo --iFALSE gdy i==1, q[0](pierwsze 8 bajtów: Ijest int64). Zastąpienie warunku pętli for(I i=n;i--;)rozwiązałoby to.

Ruby, 90 bajtów, autor: MegaTom

4271974071841820164790043412339104229205409044713305539894083215644439451561281100045924173873152

i

23495857395130010906345238767865073260629749745923180469417457686044416983587046050252582956302336

które są 2 i 11, po których następuje 40 bajtów zerowych. Więc oba mają 41 bajtów. Wartość skrótu jest dodawana na podstawie długości wejściowej każdego bajtu, a następnie jest odwracana dziesiętnie. Długość wejściowa kończąca się na1 może zapewnić, że wartość skrótu zakończy się na0 dość szybko. Następnie odwrócenie powoduje zmniejszenie długości wartości skrótu o 1.

Oba mają wartość skrótu 259.

C # - 393 bajtów - autor: Logan Dam

70776e65642062792031333337206861786f72i 70776e65642062792031333337206861786f7200oba hash do 18E1C8E645F1BBD1.