Golf kryptograficzny hash (rabusie)

12

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
Dennis
źródło

Odpowiedzi:

5

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;
}
aaaaaaaaaaaa
źródło
Niesamowite! Właściwie jestem pochlebiony w dziwny sposób! : D
Pan Llama,
Co do mojego osobistego wykształcenia, kiedy mówisz, że bity wyższego rzędu nigdy nie wpływają na niższe, co masz na myśli? Bity wyższego rzędu ciągu wejściowego lub stanu skrótu?
Pan Llama,
@ Mr.Llama W stanie skrótu górne bity xiy nigdy nie będą miały wpływu na dolne bity, więc na przykład, jeśli włączysz środkowe bity podczas obliczeń, dolna część skrótu nadal będzie dobrze wyglądać. To pozwala mi zacząć od ignorowania wszystkiego oprócz najniższych bitów stanu skrótu, a następnie, kiedy mam te pod pełną kontrolą, przechodzę do następnej warstwy bitów i tak dalej.
aaaaaaaaaaaa
Chłodny! Dziękuję za wyjaśnienie!
Pan Llama,
Gratulujemy wygranej wyzwanie złodziei!
Dennis
12

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
orlp
źródło
3
Moja początkowa propozycja w piaskownicy przyznała punkty za ataki na kolizję, preimage i (nieco upraszczając) przedłużenie długości, ale postanowiłem utrzymać prostą punktację. Kiedy zredagowałem te części, fakt, że każde zgłoszenie można złamać tylko raz (tak zwykle działa gliniarze i rabusie), jakoś zgubił się. Widząc twoją odpowiedź, żałuję, że nie zatrzymałem ataków preimage ...
Dennis
9

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 128 , 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 128 -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 128 -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 128 -2 122 . 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.

Martin Ender
źródło
Ja też to łamałem - prawie gotowe. Czy to najszybsza broń w konkursie zachodnim, czy nadal mogę zdobyć punkty za jej opublikowanie?
lub
@orlp Zwykle tylko pierwszy rabuś dostaje punkt. W przeciwnym razie ludzie mogą wygenerować miliony dodatkowych pęknięć po opublikowaniu pierwszego pęknięcia.
Martin Ender
1
Lame = / Myślę, że przestanę wtedy robić to wyzwanie. Nie lubię ścigać się z innymi - chcę tylko układać puzzle. Czy nie może być jakiś czas na pęknięcia po pierwszym, z tylko 1 pęknięciem na osobę?
lub
@orlp Oryginalna wersja w piaskownicy miała trzy różne metody łamania gliny, a wszystkie trzy mogły być publikowane niezależnie. Myślę, że to interesujący model do zbadania w pewnym momencie. Ale do tej pory w poprzednich CnR dopuszczanie wielu pęknięć zawsze przełamało wyzwanie bardziej, niż je poprawiło.
Martin Ender
1
Zobacz moją odpowiedź na atak preimage, a nie na kolizję :)
lub
8

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.

Martin Ender
źródło
8

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 .

Sp3000
źródło
Nieco krótsza wersja jest taka, że ​​jeśli kilka pierwszych cyfr jest takich samych, jest nieprawdopodobne, aby reszta danych wejściowych miała jakiekolwiek znaczenie. Właściwie robienie matematyki, aby to przełamać, to przesada.
aaaaaaaaaaaa
@eBusiness To prawda. Okazało się, że tutaj nie miało to większego znaczenia, ale początkowo martwiłem się przekroczeniem 2^(2^30)limitu, stąd czek.
Sp3000,
Podejrzewam, że może być niemożliwe wytworzenie łańcucha, w którym liczy się cokolwiek poza cyfrą 512. Udało ci się stworzyć najgorszy scenariusz. Najłatwiejszym crackem jest skorzystanie z wewnętrznych zer wiodących: „100000001” „1000000001”.
aaaaaaaaaaaa
7

Pyth, 8 bajtów FryAmTheEggman

99999999999999999999999999

i

99999999999999999999999998

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

Sp3000
źródło
Właściwie otrzymuję różne wyniki, ale wierzę, że ta strategia i tak zadziała, więc oznaczę ją jako złamaną. Szybka praca: P
FryAmTheEggman
Hmm dziwne. Dostaję 437409784163148za oba. Zastanawiam się, dlaczego jest różnica ...
Sp3000
Prawdopodobnie używasz Pythona 3.5, prawda? Nie zaktualizowałem jeszcze, wciąż na 3.4 może to jest to?
FryAmTheEggman
@FryAmTheEggman Korzystam z internetowego tłumacza, właściwie ...
Sp3000
Właściwie tak mam 437409784163148i 37409784163148tak myślę, że to właśnie stracił ostatnią cyfrę z jakiegoś powodu, ale 99 ... 997 daje tę samą odpowiedź jak 999 ... 98.
FryAmTheEggman
6

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.

Sp3000
źródło
5

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
Vi.
źródło
Tak, ten jest pęknięty. Jak długo to trwało?
Ismael Miguel
Druga próba. Pierwszą próbą było sprawdzenie wartości pierwszych 100 skrótów, drugą próbą było utworzenie łańcuchów skrótów (tj hash(hash(hash(...(hash(1)...))).). Pierwszy łańcuch niemal natychmiast zszedł w pętlę. Nie musiałem nawet przywoływać mojego wielowątkowego urządzenia do krakowania skrótów.
Vi.
Tłumaczenie: dość słaby skrót?
Ismael Miguel
Tak. 󠀠󠀠󠀠󠀠󠀠󠀠
Vi.
5

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.

feersum
źródło
Dobra robota :) Tak, luka, którą miałem na myśli, polegała na tym, że semiprime jest widoczny w kodzie i zdałem sobie sprawę, że Mathematica może to natychmiast uwzględnić.
Sp3000,
+1 Twój kod jest trudny do odczytania, ale poza tym przyjemny i pouczający crack.
aaaaaaaaaaaa
5

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.

aaaaaaaaaaaa
źródło
Niesamowite! Oba mają skrót do 0x0000000a0000000a0000000a0000000amojego systemu, ale wciąż jest to całkiem niesamowite. ( echo -ne '\x0a' |./hashdaje również ten sam wynik.)
r3mainer
1
@ squeamishossifrage Po każdym z ciągów masz różową linię, bez niej są to zwykłe zera.
aaaaaaaaaaaa
O tak, mój błąd :-)
r3mainer
4

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 ...

Tucuxi
źródło
4

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.

jimmy23013
źródło
3

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 128 . Pomysł polegał więc na znalezieniu dwóch, iktóre można podzielić przez cztery, ale gdzie pierwsze wyrażenie daje 2 32 . Można to łatwo zrobić , biorąc pod uwagę fakt, że 2 32 -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 32 -1, takich, że na końcu jest co najmniej 64 zer.

Martin Ender
źródło
3

C, 134 bajtów (autor Barteks2x)

10

i

20

oba hash do

0xa609779942cb9ef1

ponieważ algorytm haszywa tylko ostatnią cyfrę!

r3mainer
źródło
To był głupi błąd ...
barteks2x
3

C, 87 bajtów

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

Znaleziono za pomocą mojego bruteforcer kolizyjnego.

Vi.
źródło
Może to dlatego, że jest tylko 64-bitowy.
Vi.
Dobra robota :-) Jak długo to trwało?
r3mainer
Około 7 minut od uruchomienia programu. Teraz zacząłem od pomiarów.
Vi.
1
Znaleziono kolejną kolizję: 473E0B6ED5AF2B92 7EC2BC9B5E9F5645 -> 0000000000000000 0EAC34C8A9F94389po 3525078917 wywołaniach funkcji skrótu i real 14m24.970s user 48m42.410sczasie.
Vi.
3

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.

jimmy23013
źródło
2

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.

Tucuxi
źródło
Wygląda na to, że pierwsze 8 bajtów danych wejściowych jest po prostu ignorowanych.
Vi.
Wygląda na błąd w kodzie; poprawka będzie sufiksem zamiast prefiksu.
tucuxi
1
Istnieją również kolizje niezwiązane z błędami (patrz komentarze do pierwotnego pytania).
Vi.
2

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.

jimmy23013
źródło
2

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

70776e65642062792031333337206861786f72i 70776e65642062792031333337206861786f7200oba hash do 18E1C8E645F1BBD1.

aaaaaaaaaaaa
źródło
Chłodny! Czy możesz wyjaśnić, jak to złamałeś? A może „wadliwe wypełnienie”?
dam
@LoganDam Cały ten kod przełącza się wokół danych wejściowych, w końcu przetwarzasz wielokrotność 8 znaków, a jeśli długość wejściowa nie jest wielokrotnością 8, zastępujesz zerami. Jeśli dodam kilka zer we właściwym miejscu, po prostu zajmą miejsce dopełnienia, które w pierwszej kolejności było zerami.
aaaaaaaaaaaa