Golf hash kriptografis (perampok)

12

Kontes ini sudah berakhir.

Tidak ada jawaban yang bisa diperbaiki dalam tantangan polisi.

Thread pendamping golf hash Cryptographic

Sebagai pengingat, berikut adalah aturan untuk perampok dari tantangan utama:

Tugas

Crack salah satu polisi kiriman dengan posting berikut di perampok thread: dua pesan M dan N di saya sehingga H (M) = H (N) dan M ≠ N .

Mencetak gol

Memecahkan setiap pengiriman polisi memberi Anda satu poin. Perampok dengan poin terbanyak menang.

Dalam kasus dasi, perampok terikat yang memecahkan pengajuan menang paling lama.

Aturan tambahan

  • Setiap pengajuan polisi hanya bisa dibobol sekali.

  • Jika pengiriman polisi bergantung pada perilaku yang ditentukan atau tidak ditentukan implementasi, Anda hanya perlu menemukan celah yang berfungsi (dapat diverifikasi) pada mesin Anda.

  • Setiap celah milik jawaban terpisah di utas perampok.

  • Memposting upaya cracking yang tidak valid membuat Anda tidak bisa memecahkan pengiriman tertentu selama 30 menit.

  • Anda tidak boleh merusak kiriman Anda sendiri.

Contoh

Python 2.7, 22 byte oleh pengguna8675309

1

dan

18

Papan peringkat

  1. eBusiness: 3 celah, 393 byte
  2. Martin Büttner: 3 celah, 299 byte
  3. jimmy23013: 3 retak, 161 byte
  4. Sp3000: 3 celah, 44 byte
  5. tucuxi: 2 celah, 239 byte
  6. Vi .: 2 celah, 87 byte
  7. feersum: 1 crack, 216 byte
  8. mathmandan: 1 crack, 139 bytes
  9. osifrque melengking: 1 retak, 134 byte
Dennis
sumber

Jawaban:

5

C, 122 byte - oleh: Mr. Llama

bmaj8PCosFLAJjeHaevvvchnJedmg2iujpePOPivI2x2asw0yKa2eA15xvFJMFe82RGIcdlvxyaAPRuDuJhFjbh78BFsnCufJkarwEyKa0azHxccw5qegpcP9yaO0FKoohanxgiAfK1Lqwba51bKtjacbvdjMmcBkiv8kd62sBd98c4twa98sgj3iPh7nkP4
rlaejTPrua1DhBdg0jrIoDBi8fc1GIJAigivIGaxs1OmfPcctNadK3HErvzPLCeDPD8fkMNPCBcIwuoGfEHegOfk9k9pwktslqaBenaati1uNthMiyk9ndpy7gdIz88iot6A09cbNeIMheyjBvbeegL7aGp7mCb91hCxnvgV5abfImrPfLbrbraAsN6loJgh

Kedua string hash to bb66000000000000d698000000000000

Sama seperti "C, 128 byte - oleh: squeamish ossifrage" bit orde tinggi tidak pernah mempengaruhi bit orde rendah, ini dapat dieksploitasi.

Kode

Visual C ++, menggunakan operasi string " tidak aman "

#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
sumber
Luar biasa! Aku benar-benar tersanjung dengan cara yang aneh! : D
Mr. Llama
Juga, untuk pendidikan pribadi saya, ketika Anda mengatakan bit urutan yang lebih tinggi tidak pernah memengaruhi yang lebih rendah, apa maksud Anda? Bit urutan yang lebih tinggi dari string input, atau status hash?
Tn. Llama,
@ Mr.Llama Dalam kondisi hash, bit atas x dan y tidak akan pernah mempengaruhi bit lebih rendah, jadi misalnya jika Anda menyalakan bit tengah selama perhitungan, bagian rendah hash masih akan keluar dengan benar. Ini membuat saya mulai mengabaikan segalanya kecuali bit terendah dari status hash, lalu ketika saya memiliki yang di bawah kendali penuh saya beralih ke lapisan bit berikutnya, dan seterusnya.
aaaaaaaaaaaa
Keren! Terima kasih untuk penjelasannya!
Tn. Llama,
Selamat telah memenangkan tantangan perampok!
Dennis
12

Python, 109 byte oleh Sp3000

Perhatikan bahwa Martin retak terlebih dahulu, jadi saya tidak yakin apakah ini layak mendapat poin. Di sisi lain, saya memang membuat serangan preimage daripada tabrakan sederhana - hasil yang jauh lebih kuat. Ini berarti bahwa Anda dapat memberikan nilai hash sewenang-wenang, dan itu akan membangun input yang menghasilkan nilai hash itu.

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

Dan untuk menunjukkan bahwa itu berfungsi:

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

Dan untuk memberikan satu set angka tertentu yang bertabrakan:

N: 2**128
M: 43617
orlp
sumber
3
Proposal awal saya di kotak pasir memberikan poin untuk collison, preimage, dan (sedikit penyederhanaan hal) serangan ekstensi panjang, tapi saya memutuskan untuk menjaga penilaian sederhana. Ketika saya mengedit bagian-bagian itu, fakta bahwa setiap pengiriman hanya dapat dibobol sekali (yang merupakan cara kerja polisi dan perampok) entah bagaimana tersesat. Melihat jawaban Anda membuat saya berharap saya terus melakukan serangan preimage ...
Dennis
9

Python, 109 byte oleh Sp3000

340282366920938463463374607431768211414

dan

113982837842983129870077688367927159293402923522160868689804433865221255200726

keduanya menghasilkan

132946164914354994014709093261515948032

Algoritma membagi input menjadi potongan 128 bit, dan berulang kali memodifikasi hash (diunggulkan 42) dengan masing-masing potongan, sebelum melakukan beberapa hashing tambahan di akhir. Untuk menemukan tabrakan, tujuan kami adalah menemukan dua angka yang menghasilkan hasil yang sama setelah menjalankan kode pseudo berikut pada setiap chunk:

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

Karena hash diambil mod 2 128 kami ingin mencari angka yang menggeser semua hal menarik di luar kisaran bit ini. Tetapi hash diunggulkan 42sehingga memiliki beberapa bit yang tidak terlalu signifikan untuk dimulai dengan:

000000000000000000000000 ... 000000000000000000101010

Ide saya adalah untuk menyingkirkan bit-bit itu ketika menambahkan potongan pertama. Jadi mari kita coba 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

Itu cukup sederhana jadi mari kita coba gunakan itu sebagai salah satu dari dua angka. (Memang, jumlah pertama tabrakan yang saya gunakan adalah 2 128 -42.

Sekarang bagaimana kita menemukan nomor lain dengan hasil yang sama? Baik setelah satu iterasi hash tidak 42lagi, tetapi 2**122seperti yang baru saja kita tunjukkan. Sekarang dengan menambahkan potongan kedua ke nomor input kami, kami dapat menjalankan iterasi lain. Kita dapat memilih potongan kedua dengan argumen yang sama seperti argumen ini, yaitu kita ingin 2 128 -2 122 . Kemudian hasil antara setelah hash += chunkakan sama dan kami berakhir dengan hasil yang sama di akhir.

Jadi kita bisa menghitung dua angka tabrakan:

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

Kita dapat dengan mudah menghasilkan lebih banyak tabrakan seperti ini.

Martin Ender
sumber
Saya juga memecahkan ini - hampir selesai. Apakah ini senjata tercepat di kontes barat atau bisakah saya masih mendapatkan poin untuk mempostingnya?
orlp
@ Atlp Biasanya hanya perampok pertama yang mendapatkan poin. Kalau tidak, orang hanya bisa menghasilkan jutaan retakan tambahan setelah retakan pertama telah diposting.
Martin Ender
1
Lame = / Pikir saya akan berhenti melakukan tantangan ini kalau begitu. Saya tidak menikmati balapan melawan orang lain - Saya hanya ingin bermain puzzle. Tidak bisakah ada jendela waktu untuk retakan setelah yang pertama, dengan hanya 1 retak per orang?
orlp
@ orlp Versi asli di kotak pasir memiliki tiga metode berbeda untuk memecahkan polisi, dan ketiganya dapat diposting secara independen. Saya kira itu model yang menarik untuk diselidiki di beberapa titik. Namun sejauh ini dalam CnR sebelumnya yang memungkinkan banyak celah akan selalu memecahkan tantangan lebih dari itu akan memperbaikinya.
Martin Ender
1
Lihat jawaban saya untuk serangan preimage, daripada tabrakan :)
orlp
8

Mathematica, 89 byte oleh LegionMammal978

0

dan

16

Keduanya menghasilkan 0.

Prinsip dari polisi ini adalah untuk mengembangkan otomat seluler 1-D biner "acak" dari kondisi awal "acak" untuk sejumlah langkah "acak", dan kemudian menginterpretasikan 128 sel pertama hasil sebagai bilangan bulat.

Masalahnya adalah bahwa aturan ditentukan hanya dengan Mod[#^2,256], sedemikian sehingga kelipatan 16 memberi aturan 0, yang merupakan aturan trivial di mana semua sel selalu nol. Jika input tidak habis dibagi 99 maka kita akan berevolusi setidaknya 1 langkah, sehingga output selalu nol. Jadi, dua kelipatan yang bukan kelipatan 99 pasti bertabrakan. Namun, input 0 juga memberikan 0 (meskipun tidak pernah menggunakan aturan), karena kondisi awal hanyalah representasi biner dari input (yang semuanya nol dalam kasus ini).

Selain itu, kita dapat menemukan tabrakan lain yang sepenuhnya independen dari aturan. Seperti disebutkan di atas, setiap kelipatan dari 99 berarti bahwa otomat seluler tidak berevolusi sama sekali, sehingga hasilnya hanyalah 128 bit pertama (paling signifikan) dari kondisi awal ... yang dengan sendirinya hanya nomor input. Jadi jika kita mengambil dua kelipatan yang tidak berbeda dalam 128 bit pertama (empuk ke kanan dengan nol), kita juga mendapatkan tabrakan. Contoh paling sederhana dari hal ini adalah M = 99, N = 99*2 = 198.

Martin Ender
sumber
8

J, 39 byte

Angka pertama adalah:

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000

Yaitu, 10000000diulang 64 kali. Angka kedua adalah yang ditambah satu, yaitu

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000001

Keduanya menghasilkan

322124197561777885386414076216564234267

Penjelasan

Mari kita mulai dengan x := H 10000000 = 146018215378200688979555343618839610915, dan y := 2^128. Daripada menemukan yang a, bseperti itu a == b mod y, kita akan mencari yang a, bseperti itu x^a == x^b mod y, menggunakan menara listrik dalam algoritma.

Tetapi harus ada ksemacam itu x^k == 1 mod y, karena x, yada koprime, dan untuk itu kharus kita miliki a == b mod k. Jadi kita dapat menemukan logaritma diskret dari 1 mod y, dan untuk langkah pertama kita dapatkan

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

Jadi sekarang kita ingin mencari dua angka a, bsedemikian rupa a == b mod k. Untuk melakukan ini, kami menetapkan yuntuk menjadi kdan mencoba menemukan a, bitu x^a == x^b mod ylagi. Menggunakan logika yang sama, kita mengambil logaritma diskrit lagi dan dapatkan

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

Kita ulangi ini sampai kita mencapai yang kecil y, pada titik yang sepele untuk menemukan dua angka yang hash ke modulo hal yang sama y. Setelah 63 iterasi y = 4, pada titik mana pada dasarnya dua angka berfungsi.

Berikut kode Mathematica untuk menghasilkan rantai log diskrit:

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

Ini memberikan output berikut .

Sp3000
sumber
Versi yang sedikit lebih pendek adalah bahwa jika beberapa ratus digit pertama adalah sama, tidak mungkin bahwa sisa dari input sama sekali tidak penting. Sebenarnya melakukan matematika untuk memecahkan ini terlalu banyak.
aaaaaaaaaaaa
@ eBusiness Itu benar. Ternyata tidak terlalu penting di sini, tetapi pada awalnya saya khawatir akan melampaui 2^(2^30)batas, maka dari itu cek.
Sp3000
Sebenarnya, saya menduga bahwa tidak mungkin untuk membuat string di mana sesuatu di luar angka ke-512 penting. Anda berhasil menghasilkan skenario terburuk. Retakan termudah adalah memanfaatkan nol terkemuka internal: "100000001" "1000000001".
aaaaaaaaaaaa
7

Pyth, 8 byte oleh FryAmTheEggman

99999999999999999999999999

dan

99999999999999999999999998

Presisi titik apung tidak cukup besar untuk ini.

Sp3000
sumber
Saya sebenarnya mendapatkan hasil yang berbeda untuk ini, tetapi saya percaya bahwa strategi ini akan berhasil, jadi saya akan menandainya sudah retak. Kerja cepat: P
FryAmTheEggman
Hmm aneh. Saya dapatkan 437409784163148untuk keduanya. Saya ingin tahu mengapa ada perbedaan ...
Sp3000
Anda mungkin menggunakan python 3.5 bukan? Saya belum memperbarui, masih di 3,4 mungkin itu saja?
FryAmTheEggman
@FryAmTheEggman Saya menggunakan penerjemah online, sebenarnya ...
Sp3000
Sebenarnya ya saya dapatkan 437409784163148dan 37409784163148jadi saya kira itu baru saja kehilangan digit terakhir karena beberapa alasan, tetapi 99 ... 997 memberikan jawaban yang sama dengan 999 ... 98.
FryAmTheEggman
6

CJam, 44 byte, pengguna jimmy23013

Jumlahnya terlalu besar untuk dikirim, jadi di sini mereka berada di Pastebin: num 1 , num 2 .

Angka pertama adalah 600^2 = 360000yang. Angka kedua sama, kecuali untuk perubahan berikut:

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

Keduanya hash 271088937720654725553339294593617693056.

Penjelasan

Mari kita lihat pada bagian pertama dari kode:

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)

Jadi jika kita dapat menemukan dua angka input sehingga jumlah S[i][j]*13^i*19^jmodulo yang sama 16^20untuk array 600-lebar awal dan array zip, maka kita sudah selesai.

Untuk mempermudah, kami hanya akan mempertimbangkan 600^2 = 360000angka input -digit, sehingga array 600-lebar hanya 600 x 600 persegi digit. Ini membuat segalanya lebih mudah untuk divisualisasikan, dan valid sejak saat itu 10^360000 ~ 2^(2^20.19) < 2^(2^30). Untuk menyederhanakan hal-hal lebih jauh, kami hanya akan mempertimbangkan string input seperti itu yang digit perseginya simetris di sepanjang diagonal utama, sehingga array asli dan array zip sama. Ini juga memungkinkan kita untuk mengabaikan pembalikan string awal dan penomoran indeks kanan-ke-kiri, yang membatalkan satu sama lain.

Untuk memulai kita, kita bisa mengambil nomor pertama menjadi 360000yang pertama. Untuk mendapatkan angka kedua, kami ingin memodifikasi ini dengan mengubah beberapa digit sehingga jumlahnya adalah modulo yang sama 16^20, sambil mempertahankan simetri digit persegi. Kami menyelesaikan ini dengan menemukan daftar tiga kali lipat (i, j, k)sehingga

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

di mana 1 <= k <= 8jumlah untuk meningkatkan digit 1 oleh (yaitu mengubah ke digit dari 2 menjadi 9 - kita bisa memasukkan 0 tetapi kita tidak membutuhkannya) dan 0 <= i < j < 600merupakan pasangan indeks.

Setelah kita memiliki (i, j, k)kembar tiga, kita mengubah angka di (i, j)dan (j, i)untuk 1+kmendapatkan angka kedua. Si kembar tiga ditemukan menggunakan algoritma backtracking serakah, dan untuk angka kedua di atas digit persegi terlihat seperti:

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

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

Misalnya, (i, j, k) = (0, 1, 7)terkait dengan mengubah digit (0, 1)(posisi 600*0 + 1 = 1) dan (1, 0)(posisi 600*1 + 0 = 600) menjadi 1 + 7 = 8.


Inilah backtracker di Python 3, meskipun inspeksi lebih dekat mengungkapkan bahwa kami cukup beruntung, karena tidak ada backtracking yang sebenarnya terjadi:

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

Sebagai bonus, ini adalah port hash yang tidak terlalu efisien dalam Python 3. Itu tidak berguna.

Sp3000
sumber
5

PHP 4.1, 66 byte oleh 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;

Ditemukan menggunakan hashing berulang sederhana, mulai dari 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.
sumber
Yup, yang itu sudah retak. Berapa lama untuk sampai di sana?
Ismael Miguel
Percobaan kedua. Percobaan pertama adalah mencari nilai-nilai dari 100 hash pertama, percobaan kedua adalah membuat rantai hash (yaitu hash(hash(hash(...(hash(1)...)))). Rantai pertama menyatu menjadi lingkaran hampir seketika. Aku bahkan tidak perlu membuka cracker hash multithreaded saya.
Vi.
Terjemahan: hash yang cukup lemah?
Ismael Miguel
Ya.󠀠󠀠󠀠󠀠󠀠󠀠
Vi.
5

Python 3 (216) oleh Sp3000

Pesan saya adalah

5012053369354645637214643587103597313576086380250249302980438772005248488380915054746146050001036696049972235875591571028140916001206596142280971107479334216535925703480968283657357930602076844092875640359192729378384507238123245417656548512647301639542279794868512420586823155070914644206130805893968511673770843170450832829657206145931885656157628306896903719624729809643572222159364893644113710867223921580178741177106141068298067479650611992859787419779579962211254029169589775046869542029842374359998053713002047081002506346875804341770199884355810931652447801492691887376948615365487982834690942054717077615539311699691010938426302886867891090301248321702485904291177813145565144089044261424329155436660979948932491709511914065619715728353376578192548334780893602675684085757434059540582004872746967999949306946618036846307799677491651967418565531672392468089533111553281620101129322575737949904022139471688252420467041529301533363008476437812216585923822571793353317799365005036029476865
5012053369354645637214643587103103086948976188724715498910865650846170784131001427390927276355140411160919276493388206817700368694224128444524223814513348177926532982330730066315320819293979046126543806115318009892783577432467861426768883700930779409885418980853424256180864755881414774514084197887594253752179391098292488771920695965135791582218083012144604515253506370334133858904659263953147111654656123599460222236152128559750436960308887683690915261431659087040402402092795259541564130228515353133867041828417398395559815392177084002004583988047406317670433664624642858480970640416500369367395538257341309676777745698712896295462462064271676447460293684100001583256400774270688958051470568447233589146620275159126426142305307007744396679875427883384557759778766330566230012377845843842097372663092379922300568052486301863154557664156185573021849420011058607321977550938866119133331529852821217331665195832442542012455132139770813510559894254061471149750738447764616026512400623344132554752

Saya menggunakan kode Python 2 ini untuk menghasilkannya:

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)

Modulus besar adalah produk dari dua bilangan prima adan b. Saya kira harapannya adalah bahwa NP-tidak mungkin bagi kami untuk faktor semiprime, tapi saya kira 128 bit terlalu kecil karena beberapa halaman web memberi saya jawabannya segera.

Modulo kelompok multiplikatif abakan memiliki urutan (a - 1) (b - 1) yang berarti jika kita menaikkan angka berapa pun dari kekuatan itu maka harus menghasilkan 0 atau (biasanya) 1. Jadi saya meletakkan 1 bit di tempat yang menghasilkan 2 (a-1) (b-1) dikalikan ke dalam hash. Maka pesan lainnya pada dasarnya adalah 0, tetapi saya menetapkan satu bit lainnya di setiap nomor untuk membuat panjangnya sama.

Saya pikir itu akan lebih mengganggu jika hash kuadrat pada setiap bit, daripada hanya setelah menggunakan semua bilangan prima. Maka itu tidak akan begitu mudah untuk membangun eksponen yang sewenang-wenang untuk mereka.

feersum
sumber
Kerja bagus :) Ya kerentanan yang ada dalam pikiran saya pada dasarnya adalah bahwa semiprime terlihat dalam kode, dan saya menyadari Mathematica dapat memfaktorkannya secara instan.
Sp3000
+1 Kode Anda sulit dibaca, tetapi selain itu, celah yang bagus dan instruktif.
aaaaaaaaaaaa
5

C, 128 byte - oleh: osifrque melengking

Dua string berikut ini sama-sama hash untuk semua nol:

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

Fungsi hash dibangun sehingga bit orde tinggi tidak pernah mempengaruhi bit orde rendah, oleh karena itu saya dapat menghasilkan kumpulan string di mana semua xbit orde rendah adalah nol, maka saya dapat mencoba kombinasi gabungan dari string ini untuk menemukan beberapa di mana lebih dari bit yang lebih rendah adalah nol dll. Saya cukup yakin bahwa ada lebih banyak cara untuk memecahkan ini, dan juga cara yang menghasilkan string lebih pendek secara signifikan, tetapi dengan cara ini saya menghindari melakukan banyak matematika.

aaaaaaaaaaaa
sumber
Luar biasa! Mereka berdua hash to 0x0000000a0000000a0000000a0000000adi sistem saya, tapi itu masih cukup menakjubkan. ( echo -ne '\x0a' |./hashjuga memberikan hasil yang sama.)
r3mainer
1
@squeamishossifrage Anda memiliki garis baru pemerah setelah masing-masing string, tanpa itu adalah nol nol.
aaaaaaaaaaaa
Oh ya, kesalahan saya :-)
r3mainer
4

Python 3, 118 byte

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

dan

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

(yaitu: 9E400 dan 9E4000)

Keduanya menghasilkan

83909358607540647658718900164058931893

Menggali lebih dalam, tampaknya bilangan bulat mana saja yang diikuti oleh k angka berulang sehingga k> 128 dan (k% 4 == 0) akan mengembalikan hash yang sama. Misalnya, H("1"+"1"*32*4)dan H("1"+"1"*33*4)keduanya 13493430891393332689861502800964084413. Hmmm, 128 ...

tucuxi
sumber
4

Python 2, 161 byte, oleh Bingung

340282366920938463463374607431768211456 (decimal)
100000000000000000000000000000000 (hexadecimal)

dan

340282366920938468780317283222139437056 (decimal)
100000000000001203B66F94300000000 (hexadecimal)

Keduanya memiliki output:

83F172CC3D050D131F64FD04B8181DC2

Jumlahnya 2 ^ 128 dan 2 ^ 128 + (3 * 5 * 7 * 11 * 13 * 17) ^ 2 * 19 * 2 ^ 32.

jimmy23013
sumber
3

Java, 299 bytes oleh SuperJedi224

Pastebin untuk M. Dalam biner, Mmemiliki 65535 1s, diikuti oleh 2 0s.

Pastebin untuk N. Dalam biner, Nmemiliki 21845 1s, diikuti oleh 174766 0s.

Keduanya menghasilkan 0.

Perhatikan bahwa dasar dari algoritma ini adalah i.bitCount()*i.bitLength()+1dan pada akhirnya, kami mengambil hasilnya sesuai dengan kekuatan idan membawanya pada mod 2 128 . Jadi idenya adalah hanya untuk menemukan dua iyang dapat dibagi oleh empat, tetapi di mana ungkapan pertama memberi 2 32 . Itu mudah dilakukan dengan memfaktorkan 2 32 -1 dan memilih dua faktor untuk penghitungan 1s dan total lebar bit dari angka tersebut.

Sunting: Sebenarnya, ada sedikit lebih banyak alasan mengapa Mmenghasilkan nol, tetapi kita dapat dengan mudah menemukan lebih banyak angka yang menghasilkan nol karena penjelasan saya dengan menggunakan faktor-faktor lain dari 2 32 -1 sehingga setidaknya ada 64 nol pada akhirnya.

Martin Ender
sumber
3

C, 134 byte (oleh Barteks2x)

10

dan

20

keduanya hash

0xa609779942cb9ef1

karena algoritma hanya hash digit terakhir!

r3mainer
sumber
Itu adalah kesalahan bodoh ...
barteks2x
3

C, 87 byte

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

Ditemukan menggunakan bruteforcer tabrakan saya.

Vi.
sumber
Mungkin karena hanya 64-bit.
Vi.
Bagus :-) Berapa lama waktu yang dibutuhkan?
r3mainer
Sekitar 7 menit menjalankan program. Sekarang mulai lagi dengan pengukuran.
Vi.
1
Menemukan tabrakan lain: 473E0B6ED5AF2B92 7EC2BC9B5E9F5645 -> 0000000000000000 0EAC34C8A9F94389setelah 3525078917 panggilan fungsi hash dan real 14m24.970s user 48m42.410swaktu.
Vi.
3

Python 2, 115 byte, oleh ossifrage melengking

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

dan

2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Nilai hash tidak ada hubungannya dengan urutan blok.

jimmy23013
sumber
2

C ++, 239 bytes oleh SpelingMistake

Menggunakan program "utama" yang disediakan, dua input berikut menghasilkan hash yang sama:

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

dan

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

The 8 byte pertama dari masukan tidak pernah diproses , karena bug ini dalam kode:

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

karena --idievaluasi menjadi false when i==1, q[0](8 byte pertama: Iadalah an int64). Mengganti kondisi loop dengan for(I i=n;i--;)akan memperbaiki ini.

tucuxi
sumber
Sepertinya input 8 byte pertama diabaikan.
Vi.
Sepertinya ada bug dalam kode; perbaikannya adalah akhiran bukan awalan.
tucuxi
1
Ada juga tabrakan non-bug (lihat komentar untuk pertanyaan awal).
Vi.
2

Ruby, 90 Bytes, oleh MegaTom

4271974071841820164790043412339104229205409044713305539894083215644439451561281100045924173873152

dan

23495857395130010906345238767865073260629749745923180469417457686044416983587046050252582956302336

yaitu 2 dan 11 diikuti oleh 40 nol byte. Jadi mereka berdua memiliki 41 byte. Nilai hash ditambahkan oleh panjang input untuk setiap byte, dan kemudian dibalik dalam desimal. Panjang input yang diakhiri dengan 1dapat memastikan nilai hash akan berakhir dengan 0cukup cepat. Kemudian membalikkannya mengurangi panjang nilai hash sebesar 1.

Keduanya memiliki nilai hash 259.

jimmy23013
sumber
2

C # - 393 byte - oleh: Logan Dam

70776e65642062792031333337206861786f72dan 70776e65642062792031333337206861786f7200keduanya hash to 18E1C8E645F1BBD1.

aaaaaaaaaaaa
sumber
Keren! Bisakah Anda menjelaskan bagaimana Anda memecahkannya? Dan mungkin "bantalan yang salah"?
ldam
@LoganDam Itu semua kode yang beralih di sekitar input, Anda akhirnya memproses kelipatan 8 karakter, dan jika panjang input bukan kelipatan 8, Anda mengganti nol. Jika saya menambahkan beberapa nol di tempat yang tepat mereka hanya menggantikan bantalan, yang merupakan nol di tempat pertama.
aaaaaaaaaaaa