Este concurso acabou.

Não há resposta remanescente para o desafio da polícia.

Segmento complementar de golfe hash criptográfico

Como lembrete, aqui estão as regras para ladrões do principal desafio:

Tarefa

Rachar qualquer das bobinas apresentações afixando o seguinte na linha ladrões: duas mensagens M e N em I de tal modo que H (H) = H (N) e H ≠ N .

Pontuação

Quebrar cada envio de policial ganha um ponto. O ladrão com mais pontos ganha.

No caso de empate, o ladrão empatado que quebrou a finalização mais longa vence.

Regras adicionais

• Todo envio de policial só pode ser quebrado uma vez.

• Se o envio de um policial se basear em um comportamento definido ou não definido pela implementação, você precisará encontrar apenas uma falha que funcione (verificável) na sua máquina.

• Cada rachadura pertence a uma resposta separada no tópico dos ladrões.

• A publicação de uma tentativa de crack inválida o impede de quebrar esse envio específico por 30 minutos.

• Você não pode quebrar sua própria submissão.

Exemplo

Python 2.7, 22 bytes por user8675309

1

e

18

Entre os melhores

1. eBusiness: 3 rachaduras, 393 bytes
2. Martin Büttner: 3 rachaduras, 299 bytes
3. jimmy23013: 3 rachaduras, 161 bytes
4. Sp3000: 3 rachaduras, 44 bytes
5. tucuxi: 2 rachaduras, 239 bytes
6. Vi .: 2 rachaduras, 87 bytes
7. feersum: 1 crack, 216 bytes
8. mathmandan: 1 crack, 139 bytes
9. ossifrage melindroso: 1 crack, 134 bytes

C, 122 bytes - por: Mr. Llama

bmaj8PCosFLAJjeHaevvvchnJedmg2iujpePOPivI2x2asw0yKa2eA15xvFJMFe82RGIcdlvxyaAPRuDuJhFjbh78BFsnCufJkarwEyKa0azHxccw5qegpcP9yaO0FKoohanxgiAfK1Lqwba51bKtjacbvdjMmcBkiv8kd62sBd98c4twa98sgj3iPh7nkP4
rlaejTPrua1DhBdg0jrIoDBi8fc1GIJAigivIGaxs1OmfPcctNadK3HErvzPLCeDPD8fkMNPCBcIwuoGfEHegOfk9k9pwktslqaBenaati1uNthMiyk9ndpy7gdIz88iot6A09cbNeIMheyjBvbeegL7aGp7mCb91hCxnvgV5abfImrPfLbrbraAsN6loJgh

Ambas as strings para bb66000000000000d698000000000000

Assim como "C, 128 bytes - por: ossifrage squeamish", os bits de ordem superior nunca influenciam os bits de ordem inferior; isso pode ser explorado.

Código

Visual C ++, usa operações de seqüência de caracteres " inseguras "

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

long long x, y;

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

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

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

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

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

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

Python, 109 bytes por Sp3000

Observe que Martin rachou primeiro, então não tenho certeza se isso merece pontos. Por outro lado, fiz um ataque de pré-imagem em vez de uma simples colisão - um resultado muito mais forte. Isso significa que você pode atribuir um valor de hash arbitrário e criará uma entrada que gera esse valor de hash.

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

E para mostrar que funciona:

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

E para fornecer um conjunto específico de números que colidem:

N: 2**128
M: 43617

Python, 109 bytes por Sp3000

340282366920938463463374607431768211414

e

113982837842983129870077688367927159293402923522160868689804433865221255200726

ambos produzem

132946164914354994014709093261515948032

O algoritmo divide a entrada em pedaços de 128 bits e modifica repetidamente o hash (semeado para 42) com cada pedaço, antes de fazer um hash extra no final. Para encontrar uma colisão, nosso objetivo é encontrar dois números que produzam o mesmo resultado depois de executar o seguinte pseudo-código em cada parte:

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

Como o hash é obtido no mod 2 ¹²⁸ , queremos procurar números que mudem todas as coisas interessantes fora desse intervalo de bits. Mas o hash é semeado para 42ter alguns bits não tão significativos definidos para começar:

000000000000000000000000 ... 000000000000000000101010

Minha idéia era livrar-se desses bits ao adicionar o primeiro pedaço. Então, vamos tentar 2 ¹²⁸ -42:

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

Isso é bastante simples, então vamos tentar usá-lo como um dos dois números. (Com efeito, o primeiro número da colisão I utilizada é de 2 ¹²⁸ -42.

Agora, como encontramos outro número com o mesmo resultado? Bem, após uma iteração, o hash não é 42mais, mas 2**122como acabamos de mostrar. Agora, adicionando um segundo pedaço ao nosso número de entrada, podemos executar outra iteração. Podemos escolher o segundo pedaço pelo mesmo argumento que este, ou seja, queremos 2 ¹²⁸ -2 ¹²² . Então o resultado intermediário depois hash += chunkserá idêntico e terminamos com o mesmo resultado no final.

Assim, podemos calcular os dois números da colisão:

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

Podemos facilmente gerar muito mais colisões como essa.

Mathematica, 89 bytes por LegionMammal978

0

e

16

Ambos produzem 0.

O princípio desse policial é desenvolver um autômato celular 1-D binário "aleatório" a partir de uma condição inicial "aleatória" para um número "aleatório" de etapas e, em seguida, interpretar as primeiras 128 células do resultado como um número inteiro.

O problema é que a regra é determinada simplesmente por Mod[#^2,256], de modo que qualquer múltiplo de 16 dê a regra 0, que é a regra trivial em que todas as células são sempre zero. Se a entrada não for divisível por 99, evoluiremos pelo menos 1 passo, para que a saída seja sempre zero. Portanto, quaisquer dois múltiplos que não sejam múltiplos de 99 definitivamente colidem. No entanto, a entrada 0 também fornece 0 (apesar de nunca usar a regra), porque a condição inicial é apenas a representação binária da entrada (que é todos os zeros neste caso).

Como um aparte, podemos encontrar outras colisões que são completamente independentes da regra. Como observado acima, qualquer múltiplo de 99 significa que o autômato celular não evoluiu de modo algum, então o resultado são simplesmente os primeiros (mais significativos) 128 bits da condição inicial ... que é apenas o número de entrada. Portanto, se pegarmos dois múltiplos que não diferem nos primeiros 128 bits (preenchidos à direita com zeros), também teremos uma colisão. O exemplo mais simples disso é M = 99, N = 99*2 = 198.

J, 39 bytes

O primeiro número é:

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000

Ou seja, 10000000repetido 64 vezes. O segundo número é aquele mais um, ou seja,

10000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000000100000001000000010000001

Ambos produzem

322124197561777885386414076216564234267

Explicação

Vamos começar com x := H 10000000 = 146018215378200688979555343618839610915, e y := 2^128. Em vez de acharmos a, bisso a == b mod y, procuraremos a, bque x^a == x^b mod y, usando as torres de energia do algoritmo.

Mas deve haver alguns kque x^k == 1 mod y, desde que x, ysão coprimes, e para isso kdevemos ter a == b mod k. Assim, podemos encontrar o logaritmo discreto de 1 mod ye, na primeira etapa, obtemos

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

Então agora queremos encontrar dois números a, bcomo esse a == b mod k. Para fazer isso, definimos o yque é ke tentamos encontrar de novo a, bisso x^a == x^b mod y. Usando a mesma lógica, pegamos o logaritmo discreto novamente e obtemos

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

Repetimos isso até chegarmos a um valor pequeno y, e nesse ponto é trivial encontrar dois números que misturam com o mesmo módulo y. Após 63 iterações y = 4, nesse ponto basicamente dois números funcionam.

Aqui está o código do Mathematica para gerar a cadeia de log discreta:

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

Isso fornece a seguinte saída .

Pyth, 8 bytes por FryAmTheEggman

99999999999999999999999999

e

99999999999999999999999998

A precisão do ponto flutuante não é grande o suficiente para isso.

CJam, 44 bytes, usuário jimmy23013

Os números são grandes demais para serem publicados, então aqui estão eles no Pastebin: num 1 , num 2 .

O primeiro número é um 600^2 = 360000. O segundo número é o mesmo, exceto para as seguintes alterações:

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

Ambos hash para 271088937720654725553339294593617693056.

Explicação

Vamos dar uma olhada na primeira metade do código:

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)

Portanto, se pudermos encontrar dois números de entrada para que as somas de S[i][j]*13^i*19^jsejam o mesmo módulo 16^20para a matriz inicial de 600 e a matriz compactada, então terminamos.

Para tornar as coisas um pouco mais fáceis, consideraremos apenas 600^2 = 360000números de entrada com dois dígitos, para que a matriz de 600 caracteres tenha apenas 600 por 600 quadrados de dígitos. Isso facilita a visualização das coisas e é válido desde então 10^360000 ~ 2^(2^20.19) < 2^(2^30). Para simplificar ainda mais as coisas, consideraremos apenas as cadeias de entrada cujo quadrado de dígitos é simétrico ao longo da diagonal principal, para que a matriz original e a matriz compactada sejam iguais. Isso também nos permite ignorar a reversão inicial da string e a numeração do índice da direita para a esquerda, que se cancelam.

Para começar, podemos considerar o primeiro número como um 360000. Para obter o segundo número, queremos modificar isso alterando alguns dígitos, para que as somas sejam o mesmo módulo 16^20, preservando a simetria do quadrado do dígito. Conseguimos isso encontrando uma lista de triplos (i, j, k)para que

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

onde 1 <= k <= 8é o valor para aumentar o dígito 1 (alterando para um dígito de 2 para 9 - poderíamos ter incluído 0, mas não precisamos dele) e 0 <= i < j < 600somos pares de índices.

Uma vez que temos os (i, j, k)trigêmeos, mudamos os dígitos no (i, j)e (j, i)para 1+kobter o segundo número. Os trigêmeos foram encontrados usando um algoritmo ganancioso de retorno, e para o segundo número acima do dígito quadrado se parece com:

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

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

Por exemplo, (i, j, k) = (0, 1, 7)corresponde à alteração dos dígitos (0, 1)(posição 600*0 + 1 = 1) e (1, 0)(posição 600*1 + 0 = 600) para 1 + 7 = 8.

Aqui está o backtracker no Python 3, embora uma inspeção mais detalhada tenha revelado que tivemos muita sorte, pois nenhum backtracking realmente aconteceu:

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

Para um bônus, aqui está uma porta não tão eficiente do hash no Python 3. Era inútil.

PHP 4.1, 66 bytes por 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;

Encontrado usando hash iterado simples, começando em 1:

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

Python 3 (216) por Sp3000

Minhas mensagens são

5012053369354645637214643587103597313576086380250249302980438772005248488380915054746146050001036696049972235875591571028140916001206596142280971107479334216535925703480968283657357930602076844092875640359192729378384507238123245417656548512647301639542279794868512420586823155070914644206130805893968511673770843170450832829657206145931885656157628306896903719624729809643572222159364893644113710867223921580178741177106141068298067479650611992859787419779579962211254029169589775046869542029842374359998053713002047081002506346875804341770199884355810931652447801492691887376948615365487982834690942054717077615539311699691010938426302886867891090301248321702485904291177813145565144089044261424329155436660979948932491709511914065619715728353376578192548334780893602675684085757434059540582004872746967999949306946618036846307799677491651967418565531672392468089533111553281620101129322575737949904022139471688252420467041529301533363008476437812216585923822571793353317799365005036029476865
5012053369354645637214643587103103086948976188724715498910865650846170784131001427390927276355140411160919276493388206817700368694224128444524223814513348177926532982330730066315320819293979046126543806115318009892783577432467861426768883700930779409885418980853424256180864755881414774514084197887594253752179391098292488771920695965135791582218083012144604515253506370334133858904659263953147111654656123599460222236152128559750436960308887683690915261431659087040402402092795259541564130228515353133867041828417398395559815392177084002004583988047406317670433664624642858480970640416500369367395538257341309676777745698712896295462462064271676447460293684100001583256400774270688958051470568447233589146620275159126426142305307007744396679875427883384557759778766330566230012377845843842097372663092379922300568052486301863154557664156185573021849420011058607321977550938866119133331529852821217331665195832442542012455132139770813510559894254061471149750738447764616026512400623344132554752

Eu usei esse código Python 2 para gerá-los:

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)

O grande módulo era um produto de dois primos ae b. Acho que a esperança era que seria impossível para o NP fatorar o semiprime, mas acho que 128 bits é muito pequeno, já que algumas páginas da web me deram a resposta imediatamente.

O módulo do grupo multiplicativo abterá ordem (a - 1) (b - 1), o que significa que, se elevarmos qualquer número a esse poder, ele terá que resultar em 0 ou (geralmente) 1. Então, eu coloquei 1 bits em locais que resultaram em 2 ^{(a-1) (b-1)} sendo multiplicado no hash. Em seguida, a outra mensagem é basicamente 0, mas defino outro bit em cada número para tornar os comprimentos iguais.

Eu acho que teria sido mais irritante se o hash ao quadrado fosse melhor do que depois de usar todos os números primos. Então não seria tão simples construir expoentes arbitrários para eles.

C, 128 bytes - por: ossifrage squeamish

As duas seqüências a seguir ambos hash para todos os zeros:

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

A função hash é criada para que os bits de ordem superior nunca influenciem os bits de ordem inferior; portanto, eu posso gerar uma coleção de strings em que todos os xbits de ordem inferior são zero; em seguida, posso tentar combinações concatenadas dessas strings para encontrar algumas onde mais os bits mais baixos são zero etc. Tenho certeza de que há mais maneiras de quebrar isso, e também maneiras que produzem seqüências significativamente mais curtas, mas dessa maneira evitei fazer muitas contas.

Python 3, 118 bytes

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

e

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

(ou seja: 9E400 e 9E4000)

Ambos produzem

83909358607540647658718900164058931893

Indo um pouco mais fundo, parece que qualquer número inteiro seguido por k dígitos repetidos, de forma que k> 128 e (k% 4 == 0) retornem o mesmo hash. Por exemplo, H("1"+"1"*32*4)e H("1"+"1"*33*4)são ambos 13493430891393332689861502800964084413. Hmmm, 128 ...

Python 2, 161 bytes, por Intrigado

340282366920938463463374607431768211456 (decimal)
100000000000000000000000000000000 (hexadecimal)

e

340282366920938468780317283222139437056 (decimal)
100000000000001203B66F94300000000 (hexadecimal)

Ambos têm a saída:

83F172CC3D050D131F64FD04B8181DC2

Os números são 2 ^ 128 e 2 ^ 128 + (3 * 5 * 7 * 11 * 13 * 17) ^ 2 * 19 * 2 ^ 32.

Java, 299 bytes por SuperJedi224

Pastebin for M. Em binário, Mpossui 65535 1s, seguidos por 2 0s.

Pastebin for N. Em binário, Npossui 21845 1s, seguido por 174766 0s.

Ambos produzem 0.

Observe que a base do algoritmo é i.bitCount()*i.bitLength()+1e, finalmente, levamos o resultado ao poder ie o mod 2 ¹²⁸ . Portanto, a idéia era apenas encontrar dois ique são divisíveis por quatro, mas onde a primeira expressão dá 2 ³² . Isso foi feito facilmente, fatorando 2 ³² -1 e escolhendo dois fatores para a contagem de 1s e a largura total de bits do número.

Edit: Na verdade, há um pouco mais sobre o porquê de Mproduzir zero, mas podemos facilmente encontrar mais números que produzem zero por causa da minha explicação, usando outros fatores de 2 ³² -1, de modo que haja pelo menos 64 zeros no final.

C, 134 bytes (por Barteks2x)

10

e

20

ambos hash para

0xa609779942cb9ef1

porque o algoritmo hashes apenas o último dígito!

C, 87 bytes

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

Encontrado usando meu bruteforcer de colisão.

Python 2, 115 bytes, por ossifrage melindroso

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111122222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222

e

2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

O valor do hash não tinha nada a ver com a ordem dos blocos.

Python 2.x, 139 bytes por Intrigado

H(2)

e

H(128)

ambos retornam

16645614427504350476847004633262883518.

C ++, 239 bytes por SpelingMistake

Usando o programa "principal" fornecido, as duas entradas a seguir produzem o mesmo hash:

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

e

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

Os primeiros 8 bytes de entrada nunca são processados , devido a este erro no código:

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

porque --iavalia como false quando i==1, q[0](os primeiros 8 bytes: Ié um int64). Substituir a condição do loop por for(I i=n;i--;)teria corrigido isso.

Ruby, 90 bytes, da MegaTom

4271974071841820164790043412339104229205409044713305539894083215644439451561281100045924173873152

e

23495857395130010906345238767865073260629749745923180469417457686044416983587046050252582956302336

que são 2 e 11 seguidos por 40 bytes zero. Então, ambos têm 41 bytes. O valor do hash é adicionado pelo comprimento da entrada para cada byte e, em seguida, é revertido em decimal. Um comprimento de entrada que termina com 1pode garantir que o valor do hash termine 0rapidamente. A reversão reduz o comprimento do valor do hash em 1.

Ambos têm o valor de hash 259.

C # - 393 bytes - por: Logan Dam

70776e65642062792031333337206861786f72e 70776e65642062792031333337206861786f7200ambos hash para 18E1C8E645F1BBD1.