Kryptographisches Hashgolf (Räuber)

12

Dieser Wettbewerb ist vorbei.

Es gibt keine verbliebene Antwort bei der Cops Challenge.

Begleiter des kryptografischen Hash-Golfs

Zur Erinnerung, hier sind die Regeln für Räuber aus der Hauptherausforderung:

Aufgabe

Knacken jeden der Kopse Vorbringen durch die Veröffentlichung der folgenden in dem Räuber thread: zwei Nachrichten M und N in I , so dass H (M) = H (N) und M ≠ N .

Wertung

Wenn Sie jeden Cop-Beitrag knacken, erhalten Sie einen Punkt. Der Räuber mit den meisten Punkten gewinnt.

Bei einem Gleichstand gewinnt der Räuber, der die längste Einreichung geknackt hat.

Zusätzliche Regeln

  • Jeder Cop-Beitrag kann nur einmal geknackt werden.

  • Wenn sich ein Cop-Beitrag auf implementierungsdefiniertes oder undefiniertes Verhalten stützt, müssen Sie nur einen Riss finden, der (nachweislich) auf Ihrem Computer funktioniert.

  • Jeder Riss gehört zu einer eigenen Antwort im Räuber-Thread.

  • Wenn Sie einen ungültigen Cracking-Versuch veröffentlichen, können Sie diesen bestimmten Beitrag 30 Minuten lang nicht mehr knacken.

  • Sie können Ihre eigene Vorlage nicht knacken.

Beispiel

Python 2.7, 22 Bytes von user8675309

1

und

18

Bestenliste

  1. eBusiness: 3 Risse, 393 Bytes
  2. Martin Büttner: 3 Risse, 299 Bytes
  3. jimmy23013: 3 Risse, 161 Bytes
  4. Sp3000: 3 Risse, 44 Bytes
  5. Tucuxi: 2 Risse, 239 Bytes
  6. Vi .: 2 Risse, 87 Bytes
  7. Feersum: 1 Riss, 216 Bytes
  8. Mathemandan: 1 Riss, 139 Bytes
  9. zimperliches Ossifrage: 1 Riss, 134 Bytes
Dennis
quelle

Antworten:

5

C, 122 Bytes - von: Mr. Llama

bmaj8PCosFLAJjeHaevvvchnJedmg2iujpePOPivI2x2asw0yKa2eA15xvFJMFe82RGIcdlvxyaAPRuDuJhFjbh78BFsnCufJkarwEyKa0azHxccw5qegpcP9yaO0FKoohanxgiAfK1Lqwba51bKtjacbvdjMmcBkiv8kd62sBd98c4twa98sgj3iPh7nkP4
rlaejTPrua1DhBdg0jrIoDBi8fc1GIJAigivIGaxs1OmfPcctNadK3HErvzPLCeDPD8fkMNPCBcIwuoGfEHegOfk9k9pwktslqaBenaati1uNthMiyk9ndpy7gdIz88iot6A09cbNeIMheyjBvbeegL7aGp7mCb91hCxnvgV5abfImrPfLbrbraAsN6loJgh

Beide Saiten müssen gehasht werden bb66000000000000d698000000000000

Genau wie bei "C, 128 Bytes - By: Squeamish Ossifrage" beeinflussen die höherwertigen Bits niemals die niederwertigen Bits, dies kann ausgenutzt werden.

Code

Visual C ++ verwendet " unsichere " Zeichenfolgenoperationen

#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;
}
aaaaaaaaaaa
quelle
Genial! Eigentlich bin ich auf seltsame Weise geschmeichelt! : D
Mr. Llama
Was meinst du mit meiner persönlichen Bildung, wenn du sagst, dass die Bits höherer Ordnung niemals die niedrigeren beeinflussen? Die höherwertigen Bits der Eingabezeichenfolge oder des Hash-Zustands?
Mr. Llama
@ Mr.Llama Im Hash-Zustand beeinflussen die oberen Bits von x und y niemals die unteren Bits. Wenn Sie also beispielsweise während der Berechnung die mittleren Bits aktivieren, wird der untere Teil des Hash-Werts immer noch richtig ausgegeben. Dadurch kann ich zunächst alles außer den niedrigsten Bits des Hash-Zustands ignorieren. Wenn ich diese dann vollständig unter Kontrolle habe, gehe ich zur nächsten Bit-Schicht über und so weiter.
aaaaaaaaaaa
Cool! Danke für die Erklärung!
Mr. Llama
Herzlichen Glückwunsch zum Gewinn der Robbers Challenge!
Dennis
12

Python, 109 Bytes von Sp3000

Beachten Sie, dass Martin zuerst geknackt hat, daher bin ich mir nicht sicher, ob dies Punkte verdient. Andererseits habe ich eher einen Preimage-Angriff als eine einfache Kollision ausgeführt - ein viel stärkeres Ergebnis. Dies bedeutet, dass Sie ihm einen beliebigen Hash-Wert zuweisen können und eine Eingabe erstellen, die diesen Hash-Wert generiert.

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

Und um zu zeigen, dass es funktioniert:

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

Und um einen bestimmten Satz von Zahlen anzugeben, die kollidieren:

N: 2**128
M: 43617
orlp
quelle
3
Mein ursprünglicher Vorschlag in der Sandbox verlieh mir Punkte für Collison-, Preimage- und (etwas vereinfachende) Length Extension-Angriffe, aber ich entschied mich dafür, die Wertung einfach zu halten. Als ich diese Teile herausgeschnitten habe, ist die Tatsache, dass jede Einsendung nur einmal geknackt werden kann (so funktioniert Cops-and-Robbers normalerweise) irgendwie verloren gegangen. Als ich Ihre Antwort sehe, wünschte ich mir, ich hätte Preimage-Attacken aufrechterhalten ...
Dennis,
9

Python, 109 Bytes von Sp3000

340282366920938463463374607431768211414

und

113982837842983129870077688367927159293402923522160868689804433865221255200726

beide ergeben

132946164914354994014709093261515948032

Der Algorithmus teilt die Eingabe in 128-Bit-Chunks auf und ändert den Hash (Seed-to-Wert 42) für jeden Chunk wiederholt , bevor am Ende ein zusätzliches Hashing durchgeführt wird. Um eine Kollision zu finden, ist es unser Ziel, zwei Zahlen zu finden, die dasselbe Ergebnis liefern, nachdem der folgende Pseudocode für jeden Block ausgeführt wurde:

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

Da der Hash mod 2 128 ist , wollen wir nach Zahlen suchen, die alle interessanten Dinge außerhalb dieses Bitbereichs verschieben. Aber der Hash ist 42so angelegt , dass er zunächst einige nicht so wichtige Bits enthält:

000000000000000000000000 ... 000000000000000000101010

Meine Idee war, diese Teile loszuwerden, wenn ich den ersten Teil hinzufüge. Versuchen wir also 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

Das ist ziemlich einfach, also versuchen wir, das als eine der beiden Zahlen zu verwenden. (In der Tat ist die erste Nummer der Kollision, die ich verwendet habe, 2 128 -42.

Wie finden wir nun eine andere Zahl mit dem gleichen Ergebnis? Nun, nach einer Iteration ist der Hash nicht 42mehr vorhanden, aber 2**122wie wir gerade gezeigt haben. Durch Hinzufügen eines zweiten Teils zu unserer Eingabenummer können wir nun eine weitere Iteration ausführen. Wir können den zweiten Block mit demselben Argument wie diesen auswählen, dh wir wollen 2 128 -2 122 . Dann ist das Zwischenergebnis danach hash += chunkidentisch und wir erhalten am Ende dasselbe Ergebnis.

Wir können also die beiden Zahlen der Kollision berechnen:

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

Wir können leicht viel mehr Kollisionen wie diese erzeugen.

Martin Ender
quelle
Ich habe das auch geknackt - fast fertig. Ist dies die schnellste Waffe im West Contest oder kann ich trotzdem Punkte für die Veröffentlichung bekommen?
Orlp
@orlp Normalerweise bekommt nur der erste Räuber einen Punkt. Andernfalls könnten Menschen einfach Millionen zusätzlicher Risse erzeugen, sobald der erste Riss veröffentlicht wurde.
Martin Ender
1
Lame = / Denke, ich werde dann aufhören, diese Herausforderung zu tun. Ich fahre nicht gerne Rennen gegen andere - ich möchte nur rätseln. Kann es nicht ein Zeitfenster für Risse nach dem ersten geben, mit nur 1 Riss pro Person?
Orlp
@orlp Die Originalversion in der Sandbox hatte drei verschiedene Methoden, um einen Cop zu knacken, und alle drei konnten unabhängig voneinander gepostet werden. Ich denke, das ist ein interessantes Modell, das man irgendwann untersuchen sollte. Bislang hätten CNRs, die Mehrfachrisse zulassen, die Herausforderung jedoch mehr durchbrochen als verbessert.
Martin Ender
1
Siehe meine Antwort für einen Preimage-Angriff, anstatt eine Kollision :)
Orlp
8

Mathematica, 89 Bytes von LegionMammal978

0

und

16

Beide ergeben 0.

Das Prinzip dieses Cop besteht darin, einen "zufälligen" binären 1-D-Zellularautomaten aus einer "zufälligen" Anfangsbedingung für eine "zufällige" Anzahl von Schritten zu entwickeln und dann die ersten 128 Zellen des Ergebnisses als Ganzzahl zu interpretieren.

Das Problem besteht darin, dass die Regel einfach durch bestimmt wird Mod[#^2,256], sodass jedes Vielfache von 16 die Regel ergibt. Dies 0ist die triviale Regel, bei der alle Zellen immer Null sind. Wenn die Eingabe nicht durch 99 teilbar ist, werden wir mindestens 1 Schritt weiterentwickeln, sodass die Ausgabe immer Null ist. Also kollidieren zwei beliebige Vielfache, die keine Vielfachen von 99 sind, definitiv. Allerdings Eingang 0 auch gibt 0 (trotz nie der Regel verwendet wird ), weil die Anfangsbedingung nur die binäre Darstellung des Eingangssignals (die alle Nullen in diesem Fall).

Abgesehen davon können wir andere Kollisionen finden, die völlig unabhängig von der Regel sind. Wie oben erwähnt, bedeutet ein Vielfaches von 99, dass sich der Zellularautomat überhaupt nicht weiterentwickelt hat. Das Ergebnis ist also einfach das erste (höchstwertige) 128-Bit der Anfangsbedingung. Dies ist selbst nur die eingegebene Zahl. Wenn wir also zwei Vielfache nehmen, die sich in den ersten 128 Bits nicht unterscheiden (rechts mit Nullen aufgefüllt), erhalten wir auch eine Kollision. Das einfachste Beispiel dafür ist M = 99, N = 99*2 = 198.

Martin Ender
quelle
8

J, 39 Bytes

Die erste Nummer ist:

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000

Das heißt, 1000000064-mal wiederholt. Die zweite Zahl ist die plus eins, dh

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000001

Beide ergeben

322124197561777885386414076216564234267

Erläuterung

Beginnen wir mit x := H 10000000 = 146018215378200688979555343618839610915und y := 2^128. Anstatt zu finden , a, bso dass a == b mod y, suchen wir für a, bso dass x^a == x^b mod yim Algorithmus Verwendung der Macht Türme machen.

Aber es muss ksolche geben x^k == 1 mod y, da x, yes Koprime gibt, und dafür kmüssen wir haben a == b mod k. Wir können also den diskreten Logarithmus von 1 Mod yfinden und für den ersten Schritt erhalten wir

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

Also wollen wir jetzt zwei a, bsolche Zahlen finden a == b mod k. Um dies zu tun, setzen wir yzu sein kund versuchen zu finden , a, bso dass x^a == x^b mod ywieder. Mit der gleichen Logik nehmen wir den diskreten Logarithmus wieder und erhalten

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

Wir wiederholen dies, bis wir zu einem kleinen yPunkt kommen. An diesem Punkt ist es trivial, zwei Zahlen zu finden, die das gleiche Modulo haben y. Nach 63 Iterationen y = 4funktionieren grundsätzlich zwei beliebige Zahlen.

Hier ist der Mathematica-Code zum Generieren der diskreten Protokollkette:

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

Dies ergibt die folgende Ausgabe .

Sp3000
quelle
Die etwas kürzere Version ist, dass es unwahrscheinlich ist, dass der Rest der Eingabe in irgendeiner Weise von Bedeutung ist, wenn die ersten paar Hundert Ziffern gleich sind. Eigentlich Mathe zu machen, um das zu brechen, ist übertrieben.
aaaaaaaaaaaa 06.06.15
@eBusiness Das stimmt. Es stellte sich heraus, dass es hier nicht viel ausmachte, aber anfangs machte ich mir Sorgen, das 2^(2^30)Limit zu überschreiten, daher der Scheck.
Sp3000,
Eigentlich vermute ich, dass es unmöglich sein könnte, eine Zeichenfolge herzustellen, bei der etwas über die 512. Ziffer hinaus wichtig ist. Sie haben es geschafft, das Worst-Case-Szenario zu erstellen. Am einfachsten muss es sein, interne führende Nullen zu nutzen: "100000001" "1000000001".
aaaaaaaaaaaa 06.06.15
7

Pyth, 8 Bytes von FryAmTheEggman

99999999999999999999999999

und

99999999999999999999999998

Die Gleitkommapräzision ist dafür nicht groß genug.

Sp3000
quelle
Eigentlich bekomme ich unterschiedliche Ergebnisse, aber ich glaube, dass diese Strategie trotzdem funktionieren würde, also werde ich sie als geknackt markieren. Schnelle Arbeit: P
FryAmTheEggman
Hmm komisch. Ich verstehe 437409784163148für beide. Ich frage mich, warum es einen Unterschied gibt ...
Sp3000
Sie verwenden wahrscheinlich Python 3.5, oder? Ich habe noch nicht aktualisiert, immer noch auf 3.4. Vielleicht ist es das?
FryAmTheEggman
@FryAmTheEggman Ich verwende den Online-Dolmetscher, eigentlich ...
Sp3000
Eigentlich verstehe ich das 437409784163148und 37409784163148ich denke, es hat aus irgendeinem Grund nur die letzte Ziffer verloren, aber 99 ... 997 gibt die gleiche Antwort wie 999 ... 98.
FryAmTheEggman
6

CJam, 44 Bytes, Benutzer jimmy23013

Die Zahlen sind zu groß, um sie zu posten, also sind sie hier auf Pastebin: Nummer 1 , Nummer 2 .

Die erste Zahl ist 600^2 = 360000eins. Die zweite Zahl ist bis auf die folgenden Änderungen identisch:

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

Beides muss Hash sein 271088937720654725553339294593617693056.

Erläuterung

Werfen wir einen Blick auf die erste Hälfte des Codes:

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)

Also, wenn wir zwei Eingangszahlen finden können, so dass die Summen von S[i][j]*13^i*19^j16^20 sowohl für das ursprüngliche 600-breite Array als auch für das gezippte Array dasselbe Modulo aufweisen , sind wir fertig.

Um die Sache ein wenig einfacher zu machen, werden wir nur darüber nachdenken 600^2 = 360000 -stellige Eingabenummern, so dass das 600-breite Array nur ein Quadrat mit 600 mal 600 Ziffern ist. Dies erleichtert die Visualisierung und ist seitdem gültig10^360000 ~ 2^(2^20.19) < 2^(2^30) . Um die Sache noch weiter zu vereinfachen, betrachten wir nur solche Eingabezeichenfolgen, deren Ziffernquadrat entlang der Hauptdiagonale symmetrisch ist, so dass das ursprüngliche Array und das gezippte Array identisch sind. Dadurch können wir auch die anfängliche Umkehrung der Zeichenfolge und die Indexnummerierung von rechts nach links ignorieren, die sich gegenseitig aufheben.

Um uns anzufangen, können wir die erste Zahl als 360000eine annehmen . Um die zweite Zahl zu erhalten, möchten wir diese ändern, indem wir einige der Ziffern so ändern, dass die Summen das gleiche Modulo haben 16^20, wobei die Symmetrie des Ziffernquadrats erhalten bleibt. Wir erreichen dies, indem wir eine Liste von Tripeln finden, (i, j, k)damit

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

wo 1 <= k <= 8ist der Betrag, um den die Ziffer 1 erhöht werden muss (dh indem eine Ziffer von 2 auf 9 geändert wird - wir hätten 0 einschließen können, aber wir haben es nicht benötigt) und0 <= i < j < 600 sind Indexpaare.

Sobald wir die haben (i, j, k)Drillinge, ändern wir die Ziffern auf (i, j)und (j, i)zu , 1+kum die zweite Nummer. Die Drillinge wurden mit einem gierigen Backtracking-Algorithmus gefunden, und für die zweite Zahl über dem Ziffernquadrat sieht es folgendermaßen aus:

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

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

Zum Beispiel (i, j, k) = (0, 1, 7)entspricht das Ändern der Ziffern (0, 1)(Position 600*0 + 1 = 1) und (1, 0)(Position 600*1 + 0 = 600) zu 1 + 7 = 8.


Hier ist der Backtracker in Python 3, obwohl eine genauere Betrachtung ergab, dass wir ziemlich viel Glück hatten, da tatsächlich kein Backtracking stattgefunden hat:

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

Als Bonus gibt es hier einen nicht so effizienten Port des Hashes in Python 3. Es war nutzlos.

Sp3000
quelle
5

PHP 4.1, 66 Bytes von Ismael 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;

Gefunden mit einfachem iteriertem Hashing, beginnend mit 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.
quelle
Yup, das ist geknackt. Wie lange hat es gedauert, bis wir dort ankamen?
Ismael Miguel
Der zweite Versuch. Beim ersten Versuch wurden die Werte der ersten 100 Hashes überprüft, beim zweiten Versuch wurden die Hash-Ketten (dh hash(hash(hash(...(hash(1)...)))) erstellt. Die erste Kette formte sich fast augenblicklich zu einer Schleife. Ich brauchte nicht einmal meinen Multithread-Hash-Cracker aufzurufen.
Vi.
Übersetzung: ziemlich schwach Hash?
Ismael Miguel
Ja
.
5

Python 3 (216) von Sp3000

Meine Nachrichten sind

5012053369354645637214643587103597313576086380250249302980438772005248488380915054746146050001036696049972235875591571028140916001206596142280971107479334216535925703480968283657357930602076844092875640359192729378384507238123245417656548512647301639542279794868512420586823155070914644206130805893968511673770843170450832829657206145931885656157628306896903719624729809643572222159364893644113710867223921580178741177106141068298067479650611992859787419779579962211254029169589775046869542029842374359998053713002047081002506346875804341770199884355810931652447801492691887376948615365487982834690942054717077615539311699691010938426302886867891090301248321702485904291177813145565144089044261424329155436660979948932491709511914065619715728353376578192548334780893602675684085757434059540582004872746967999949306946618036846307799677491651967418565531672392468089533111553281620101129322575737949904022139471688252420467041529301533363008476437812216585923822571793353317799365005036029476865
5012053369354645637214643587103103086948976188724715498910865650846170784131001427390927276355140411160919276493388206817700368694224128444524223814513348177926532982330730066315320819293979046126543806115318009892783577432467861426768883700930779409885418980853424256180864755881414774514084197887594253752179391098292488771920695965135791582218083012144604515253506370334133858904659263953147111654656123599460222236152128559750436960308887683690915261431659087040402402092795259541564130228515353133867041828417398395559815392177084002004583988047406317670433664624642858480970640416500369367395538257341309676777745698712896295462462064271676447460293684100001583256400774270688958051470568447233589146620275159126426142305307007744396679875427883384557759778766330566230012377845843842097372663092379922300568052486301863154557664156185573021849420011058607321977550938866119133331529852821217331665195832442542012455132139770813510559894254061471149750738447764616026512400623344132554752

Ich habe diesen Python 2-Code verwendet, um sie zu generieren:

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)

Der große Modul war ein Produkt von zwei Primzahlen aundb . Ich denke, die Hoffnung war, dass es NP-unmöglich für uns sein würde, das Semiprime zu berücksichtigen, aber ich denke, 128 Bit sind zu klein, da mir eine Webseite die Antwort sofort gab.

Das multiplikative Gruppenmodulo abhat die Ordnung (a - 1) (b - 1), was bedeutet, dass, wenn wir eine Zahl auf diese Potenz erhöhen, dies zu 0 oder (normalerweise) 1 führen muss. Also habe ich 1 Bits an Stellen gesetzt, die resultierten 2 (a-1) (b-1) wird in den Hash multipliziert. Dann ist die andere Nachricht im Grunde genommen 0, aber ich setze in jeder Zahl ein weiteres Bit, um die Längen gleich zu machen.

Ich denke, es wäre ärgerlicher gewesen, wenn der Hash-Wert in jedem Punkt genau abgepasst worden wäre, anstatt erst, nachdem alle Primzahlen verwendet worden wären. Dann wäre es nicht so einfach gewesen, beliebige Exponenten für sie zu bauen.

Feersum
quelle
Gute Arbeit :) Ja, die Schwachstelle, an die ich gedacht hatte, war im Grunde, dass die Semiprime im Code sichtbar ist, und ich erkannte, dass Mathematica sie sofort berücksichtigen konnte.
Sp3000,
+1 Dein Code ist schwer zu lesen, aber ansonsten ein netter und lehrreicher Riss.
aaaaaaaaaaa
5

C, 128 Bytes - durch: zimperliches Ossifrage

Die folgenden beiden Zeichenfolgen haben beide einen Hash-Wert für alle Nullen:

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

Die Hash-Funktion ist so aufgebaut, dass höherwertige Bits niemals niederwertige Bits beeinflussen. Daher kann ich eine Sammlung von Zeichenfolgen generieren, bei denen alle xniederwertigen Bits Null sind. Dann kann ich verkettete Kombinationen dieser Zeichenfolgen versuchen, um einige zu finden, bei denen mehr der Zeichenfolgen vorhanden sind niedrigere Bits sind Null usw. Ich bin mir ziemlich sicher, dass es mehr Möglichkeiten gibt, dies zu unterbrechen, und auch Möglichkeiten, die deutlich kürzere Zeichenfolgen erzeugen, aber auf diese Weise habe ich es vermieden, viel zu rechnen.

aaaaaaaaaaa
quelle
Genial! Sie haben beide Probleme mit 0x0000000a0000000a0000000a0000000ameinem System, aber das ist immer noch ziemlich erstaunlich. ( echo -ne '\x0a' |./hashgibt auch das gleiche Ergebnis.)
r3mainer
1
@squeamishossifrage Nach jeder Zeichenfolge wird ein roter Zeilenumbruch angezeigt, ohne dass es sich um einfache Nullen handelt.
aaaaaaaaaaa
Oh ja, mein Fehler :-)
r3mainer
4

Python 3, 118 Bytes

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

und

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

(das heißt: 9E400 und 9E4000)

Beide produzieren

83909358607540647658718900164058931893

Etwas tiefer zu graben, scheint, dass jede ganze Zahl, gefolgt von k wiederholten Ziffern, so dass k> 128 und (k% 4 == 0) den gleichen Hash zurückgeben. Zum Beispiel H("1"+"1"*32*4)und H("1"+"1"*33*4)beides 13493430891393332689861502800964084413. Hmmm, 128 ...

Tucuxi
quelle
4

Python 2, 161 Bytes, von Puzzled

340282366920938463463374607431768211456 (decimal)
100000000000000000000000000000000 (hexadecimal)

und

340282366920938468780317283222139437056 (decimal)
100000000000001203B66F94300000000 (hexadecimal)

Beide haben die Ausgabe:

83F172CC3D050D131F64FD04B8181DC2

Die Zahlen sind 2 ^ 128 und 2 ^ 128 + (3 * 5 * 7 * 11 * 13 * 17) ^ 2 * 19 * 2 ^ 32.

jimmy23013
quelle
3

Java, 299 Bytes von SuperJedi224

Pastebin für M. In binärer MForm hat 65535 1s, gefolgt von 20 s.

Pastebin für N. In binärer NForm hat 21845 1s, gefolgt von 1747660 s.

Beide ergeben 0.

Beachten Sie, dass die Grundlage des Algorithmus ist i.bitCount()*i.bitLength()+1und wir das Ergebnis letztendlich zur Potenz von iund zu Mod 2 128 nehmen . Die Idee war also, nur zwei zu finden i, die durch vier teilbar sind, aber bei denen der erste Ausdruck 2 32 ergibt . Dies wurde leicht durch Faktorisierung von 2 32 erreicht -1 berücksichtigt und zwei Faktoren für die Anzahl der Einsen und die Gesamtbitbreite der Zahl ausgewählt wurden.

Bearbeiten: Eigentlich gibt es ein bisschen mehr MGründe , warum Null ergibt, aber wir können aufgrund meiner Erklärung leicht mehr Zahlen finden, die Null ergeben, indem wir andere Faktoren von 2 32 -1 verwenden, so dass am Ende mindestens 64 Nullen stehen.

Martin Ender
quelle
3

C, 134 Bytes (von Barteks2x)

10

und

20

beides hash zu

0xa609779942cb9ef1

weil der Algorithmus nur die letzte Ziffer hascht!

r3mainer
quelle
Das war ein dummer Fehler ...
barteks2x
3

C 87 Bytes

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

Mit meinem Kollisions-Bruteforcer gefunden.

Vi.
quelle
Vielleicht liegt es daran, dass es nur 64-Bit ist.
Vi.
Gut gemacht :-) Wie lange hat es gedauert?
r3mainer
Ungefähr 7 Minuten nach dem Ausführen des Programms. Nun begann wieder mit Messungen.
Vi.
1
Eine weitere Kollision gefunden: 473E0B6ED5AF2B92 7EC2BC9B5E9F5645 -> 0000000000000000 0EAC34C8A9F94389nach 3525078917 Hash-Funktionsaufrufen und real 14m24.970s user 48m42.410sUhrzeit.
Vi.
3

Python 2, 115 Bytes, durch zimperliche Ossifrage

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

und

2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Der Hashwert hatte nichts mit der Reihenfolge der Blöcke zu tun.

jimmy23013
quelle
2

C ++, 239 Bytes von SpelingMistake

Unter Verwendung des bereitgestellten "Haupt" -Programms erzeugen die folgenden zwei Eingaben den gleichen Hash:

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

und

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

Die ersten 8 Bytes der Eingabe werden aufgrund dieses Fehlers im Code nie verarbeitet :

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

weil das --iErgebnis falsch , wenn i==1, q[0](die ersten 8 Bytes Iist int64). Das Ersetzen der Schleifenbedingung durch for(I i=n;i--;)hätte dies behoben.

Tucuxi
quelle
Es sieht so aus, als würden die ersten 8 Bytes der Eingabe einfach ignoriert.
Vi.
Scheint wie ein Fehler im Code; Das Update wird anstelle des Präfixes durch ein Suffix ersetzt.
Tucuxi
1
Es gibt auch fehlerfreie Kollisionen (siehe Kommentare zur ursprünglichen Frage).
Vi.
2

Ruby, 90 Bytes, von MegaTom

4271974071841820164790043412339104229205409044713305539894083215644439451561281100045924173873152

und

23495857395130010906345238767865073260629749745923180469417457686044416983587046050252582956302336

Das sind 2 und 11, gefolgt von 40 Null-Bytes. Sie haben also beide 41 Bytes. Der Hash-Wert wird um die Eingabelänge für jedes Byte addiert und anschließend in Dezimalzahlen umgekehrt. Eine mit endende Eingabelänge 1kann sicherstellen, dass der Hash-Wert mit a endet0 ziemlich schnell . Beim Umkehren wird die Länge des Hash-Werts um 1 verringert.

Beide haben den Hash-Wert 259.

jimmy23013
quelle
2

C # - 393 bytes - von: Logan Dam

70776e65642062792031333337206861786f72und 70776e65642062792031333337206861786f7200beides zu haschen 18E1C8E645F1BBD1.

aaaaaaaaaaa
quelle
Cool! Können Sie erklären, wie Sie es geknackt haben? Und vielleicht die "fehlerhafte Polsterung"?
Dam
@LoganDam Es ist der gesamte Code, der die Eingabe umschaltet. Am Ende verarbeiten Sie ein Vielfaches von 8 Zeichen. Wenn die Eingabelänge kein Vielfaches von 8 ist, ersetzen Sie Nullen. Wenn ich an der richtigen Stelle einige Nullen hinzufüge, ersetzen sie einfach die Auffüllung, bei der es sich an erster Stelle um Nullen handelte.
aaaaaaaaaaa