Golfe de hash criptográfico

34

Este concurso acabou.

Devido à natureza dos desafios de , o desafio de policiais se torna muito mais fácil quando o interesse no desafio associado a ladrões diminui. Portanto, embora você ainda possa postar funções de hash, sua resposta não será aceita ou fará parte da tabela de classificação.

Este desafio é a busca pelo menor implementação de uma função hash que é resistente ao choque , ou seja, deve ser impraticável encontrar duas mensagens diferentes com o mesmo hash.

Como policial, você tenta inventar e implementar uma função de hash, encontrando o melhor compromisso entre o tamanho do código e a resistência à colisão. Use muitos bytes e outro policial irá derrotar você!

Como ladrão, você tenta frustrar as tentativas dos policiais quebrando suas funções, provando que elas são inadequadas. Isso os forçará a usar mais bytes para fortalecer seus algoritmos!

Desafio da polícia

Tarefa

Implemente uma função hash criptográfica H: I -> O de sua escolha, onde I é o conjunto de todos os números inteiros não negativos abaixo de 2 2 30 e O é o conjunto de todos os números inteiros não negativos abaixo de 2 128 .

Você pode implementar H como uma função real que aceita e retorna um único número inteiro, uma representação de seqüência de caracteres de um número inteiro ou uma matriz de números inteiros ou um programa completo que lê STDIN e imprime em STDOUT na base 10 ou 16.

Pontuação

  • H que tem que resistir ao desafio dos ladrões definido abaixo.

    Se um ladrão derrotar seu envio nas primeiras 168 horas após a publicação, ele será considerado rachado .

  • A implementação de H deve ser o mais curta possível. A inscrição mais curta e sem rachaduras será a vencedora do desafio da polícia.

Regras adicionais

  • Se você implementar H como uma função, forneça um wrapper para executar a função a partir de um programa que se comporta conforme explicado acima.

  • Forneça pelo menos três vetores de teste para o seu programa ou wrapper (entradas de exemplo e suas saídas correspondentes).

  • H pode ser seu novo design (preferencial) ou um algoritmo conhecido, desde que você o implemente. É proibido usar qualquer tipo de função hash embutida, função de compactação, cifra, PRNG, etc.

    Qualquer built-in comumente usado para implementar funções de hash (por exemplo, conversão de base) é um jogo justo.

  • A saída do seu programa ou função deve ser determinística.

  • Deve haver um compilador / intérprete gratuito (como na cerveja) que possa ser executado em uma plataforma x86 ou x64 ou de um navegador da web.

  • Seu programa ou função deve ser razoavelmente eficiente e deve conter qualquer mensagem em I abaixo de 2 2 19 em menos de um segundo.

    Para casos extremos, o tempo (de parede) gasto na minha máquina (Intel Core i7-3770, 16 GiB de RAM) será decisivo.

  • Dada a natureza desse desafio, é proibido alterar o código da sua resposta de qualquer forma, independentemente de alterar ou não a saída.

    Se o seu envio foi quebrado (ou mesmo se não), você pode postar uma resposta adicional.

    Se sua resposta for inválida (por exemplo, ela não está de acordo com a especificação de E / S), exclua-a.

Exemplo

Python 2.7, 22 bytes

def H(M):
 return M%17

Embrulho

print H(int(input()))

Desafio de ladrões

Tarefa

Rachar qualquer das bobinas apresentações afixando o seguinte na ladrões rosca : 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 um envio de policial depende de um comportamento definido ou indefinido da implementação, você precisa 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

Envios seguros

  1. CJam, 21 bytes por eBusiness
  2. C ++, 148 bytes por tucuxi
  3. C ++, 233 (?) Bytes do Vi.

Envios sem rachaduras

Você pode usar esse snippet de pilha para obter uma lista de respostas ainda não quebradas.

function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>

Dennis
fonte
Se uma função hash retornar números errôneos maiores que 2 ^ 128-1, isso invalida a submissão ou simplesmente usaríamos o resultado módulo 2 ^ 128?
Martin Ender
@ MartinBüttner: Sim, você teria que pegar o resultado do módulo 2 ^ 128.
Dennis
1
@Scimonster não satisfaz os requisitos (até 2 ^ 30 bits de entrada, 128 bits de saída)
CodesInChaos
1
Policiais e ladrões geralmente não fazem o contrário?
precisa saber é o seguinte
2
Talvez pudéssemos ter uma regra na qual os envios devem incluir hashes de exemplo; é muito chato ter que executar a linguagem de programação escolhida pelos remetentes para obter um resultado para comparar os que estão implementando a instalação de cracking.
Aaaaaaaaaaaa

Respostas:

6

CJam, 21 bytes

1q3*{i+_E_#*^26_#)%}/

Toma uma sequência de bytes como entrada.

No pseudocódigo:

hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

Exemplos de hashes:

"" (cadeia vazia) -> 1
"Teste" -> 2607833638733409808360080023081587841
"teste" -> 363640467424586895504738713637444713

Pode ser um pouco simples, o intervalo de saída é apenas um pouco mais do que 122 bits, o reforço da iteração tripla já está um pouco quebrado, pois ele faz exatamente a mesma coisa todas as vezes, então insira um hash para 1 no primeiro a iteração será uma pausa completa. Mas é curto, e não há graça em ser muito seguro.

aaaaaaaaaaaa
fonte
Existe uma versão C em anexo, como no outro post do CJam?
Vi.
@Vi. Não, ainda não pelo menos. Eu nunca me envolvi com bigint em C, existe uma biblioteca padrão para isso?
Aaaaaaaaaaa
GMP ?
Vi.
3
Aqui: pastebin.com/SDzA3JK4
ossifrage melindroso
1
@ Agawa001 Você está confundindo sua terminologia. É um algoritmo de hash de função de esponja de passagem tripla. Uma cifra de César é um algoritmo de criptografia específico, sem estado interno.
Aaaaaaaaaaa
7

Python, 109 bytes [ rachado , e novamente ]

def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

Tentei implementar a função única de Jenkins como está, com a única diferença sendo a semente e o número de bits.

Curiosidade: aparentemente, Perl usou o hash dos Jenkins em algum momento .

Embrulho

print(f(int(input())))

Exemplos

>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167
Sp3000
fonte
6

C ++, 148 bytes

typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<<i)|(o>>(128-i));o*=p;o^=b[n];}}

__uint128_t é uma extensão do GCC e funciona conforme o esperado. O hash é baseado na iteração do hash FNV (eu emprestei o primo, embora asejam os primeiros dígitos do Pi em hexadecimal) com uma rotação do tipo sha1 no início de cada iteração. Compilar com o -O3hash de um arquivo de 10 MB leva menos de 2 segundos, então ainda há margem para melhorar as iterações no loop interno - mas estou me sentindo generoso hoje.

Não uglificado (nomes de variáveis ​​alterados, comentários adicionados, espaço em branco e um par de chaves) para o seu prazer em crack:

typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;    
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<<i)|(output>>(128-i)); // variable roll 
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];        
        }
    }
    // computed hash now available in output
}

Sugestões de golfe são bem-vindas (mesmo que eu não consiga melhorar o código com base nelas).

edit: erros de digitação corrigidos no código não uglificado (a versão em golf permanece inalterada).

tucuxi
fonte
oparece não inicializado. Onde outputé declarado? Ou talvez oseja output?
Vi.
O mesmo para n. Você realmente verificou o código "desglomerado" para executar?
Vi.
Começou o bruteforcer ...
Vi.
Mesmo a versão de três rodadas não é fácil.
Vi.
@Vi. Corrigida versão desglomerada - desculpe por não ter verificado melhor. Tenho orgulho desse laço interno; U i=81;i-=3poderia ter sido ainda mais vil, sem custos significativos de tempo de execução.
226156 Tucuxi
5

CJam, 44 bytes [ rachado ]

lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

A entrada está na base 10.

CJam é lento. Espero que seja executado em 1 segundo em algum computador ...

Explicações

lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

Bem, as coisas bidimensionais pareciam ser uma fraqueza ... Pretendia-se fazer alguns cálculos lentos mais rapidamente no início. Mas como ele não pode ser executado em um segundo, não importa o que eu faça, removi o código lento finalmente.

Também deve ser melhor se eu tiver usado bits binários e bases mais altas.

Versão C

__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}
jimmy23013
fonte
Você poderia adicionar uma descrição? Nem todo mundo conhece CJam.
orlp
@orlp Edited ...
jimmy23013
Isso leva 0,4 s no meu computador, portanto está dentro do intervalo permitido.
Dennis
O que é A, B, C e assim por diante? Algumas matrizes? Quais dimensões? Pode ser facilmente implementado em C?
Vi.
1
Rachado , eu acredito.
Sp3000
5

C ++, 182 caracteres (+ cerca de 51 caracteres de padrão)

h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

Boilerplate:

void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

Programa executável com uma função de golfe

#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}
Vi.
fonte
2
Eu acho que a declaração de função etc. conta para a contagem de caracteres.
Ypnypn
@Ypnypn, contou caracteres em uma declaração de função reduzida.
Vi.
Qual é o hash de saída? Estou assumindo que é ((h << 64) | j).
Tucuxi
Sim. Ou apenas um par de números de 64 bits. Eu descobri __uint128_tapenas depois de implementar isso.
Vi.
1
@Dennis, Done.󠀠
Vi.
4

Pitão, 8 Rachado

sv_`.lhQ

Experimente online

Uma resposta meio boba, vou explicar como funciona, porque a maioria das pessoas não consegue ler Pyth. Isso leva o log natural de um mais a entrada e depois o converte em uma string. Essa sequência é revertida e, em seguida, avaliada e convertida em um número inteiro.

Uma tradução em python se pareceria com:

import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))
FryAmTheEggman
fonte
Rachado ?
Sp3000
4

Python 3, 216 bytes [ rachado ]

def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

Devido a uma incompatibilidade com as especificações, posso pensar em pelo menos uma leve vulnerabilidade, mas, além disso, acho que isso é pelo menos uma prova de força bruta. Eu verifiquei os primeiros 10 milhões de hashes, entre outras coisas.

Em termos de golfe, isso seria mais curto no Python 2, mas sacrifiquei alguns bytes por eficiência (já que provavelmente não vai ganhar de qualquer maneira).

Edit: Esta foi a minha tentativa de implementar o Very Smooth Hash , mas infelizmente 128 bits era muito pequeno.

Embrulho

print(f(int(input())))

Exemplos

>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

Explicação do código

def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

Um exemplo do preenchimento para f(6):

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)
Sp3000
fonte
Cracked
feersum
4

C, 87 bytes [ rachado ]

Este é o programa completo; nenhum invólucro necessário. Aceita entrada binária via stdin e gera um hash hexadecimal para stdout.

c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

Isso calcula apenas um hash de 64 bits, então estou apostando um pouco aqui.

Caso alguém esteja se perguntando, as duas constantes 'foo+'e 'bar/'são os números primos 1718578987 e 1650553391.


Exemplos:

Ignora zeros à esquerda:

echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

Entradas de byte único:

echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

Entradas de vários bytes:

echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c
ossifrage melindroso
fonte
Como se comportaria com 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' e 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'?
Ismael Miguel
1
foo|(d5c9bef71d4f5d1b) e foo\(d5c9bef71d4f5d1b) produzem hashes MUITO semelhantes.
Ismael Miguel
1
Quebrou !!! \x00e \x00\x00!
Ismael Miguel
1
Com base nos comentários do chat, acredito que isso ainda não está quebrado ainda? Apenas verifique duas vezes, porque o comentário acima pode ser confuso para aqueles que estão procurando por hashes não rachados.
Sp3000
3

J - 39 bytes - quebrado

Função pegando uma string como entrada e retornando um número inteiro <2 128 . Suponho que tenhamos que nomear nossa função como válida, portanto, elimine mais 3 caracteres da contagem se pudermos enviar funções anônimas.

H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

Para aqueles que não lêem hieróglifos, aqui está um resumo do que estou fazendo.

  • a=.(2^128x)&|@^/@Essa é uma sub-rotina * que pega uma matriz de números e a trata como uma torre de energia, onde a exponenciação é feita no mod 2 128 . Por "torre de energia", quero dizer, se você desse a entrada 3 4 5 6, calcularia 3 ^ (4 ^ (5 ^ 6)).
  • (".p:@+5,9:)aEssa função pega uma string, converte-a para o número N e calcula os números primos ( n +5) -ésimo ( n +9) -ésimo e, em seguida, lança o ade antes nele. Ou seja, encontramos o p(n+5) ^ p(n+9)mod 2 128, onde p(k)está o k-ésimo primo.
  • H=:_8...\(a...)]Execute a função acima em sub-blocos de 8 caracteres da entrada e, em seguida, atodos os resultados juntos e chame a função hash resultante H. Eu uso 8 caracteres porque a função " k-ésimo prime" de J falha quando p(k)> 2 31 , ou seja, k=105097564é o maior cofre k.

Tenha algumas saídas de amostra. Você pode tentar isso online no tryj.tk , mas eu realmente recomendo fazer isso em casa baixando o intérprete da Jsoftware .

   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

* Tecnicamente, não é uma função em si mesma, ela se liga a outras funções e atua na saída delas. Mas essa é uma questão semântica de J, não uma diferença conceitual: o fluxo do programa é como eu o descrevi acima.

algoritmshark
fonte
Cracked
Sp3000
2

Python 3, 118 bytes [ rachado ]

def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

Recuo é uma única guia. Hash simples, ainda não o testei completamente.

Ligue da seguinte maneira:

print(H("123456789"))

resultado: 73117705077050518159191803746489514685

tomsmeding
fonte
Como o número inteiro de entrada deve ser convertido em uma string para uso em seu algoritmo?
feersum
@feersum base-10 string é o que eu testei. Ele não usa nada, mas ord(c)embora, por isso, realmente, qualquer seqüência fará :) (exceto coisas como caracteres nul, eu acho que essas colisões de hash make muito fácil para ficar com uma cadeia de 0-9..)
tomsmeding
1
Quebrou: codegolf.stackexchange.com/a/51160/41288 . Começou observando que strings como "10000" e "20000" produzem hashes muito próximos. Começou a brincar com mais e mais zeros e, depois de 128 ou mais, qualquer dígito + k * 4 zeros repetidos retorna o mesmo hash, independentemente de k.
tucuxi
@tucuxi Já pensei que não deveria ser difícil demais ; Ainda bem que isso não foi trivial, mas que alguém a quebrou de qualquer maneira. Bom trabalho.
tomsmeding
2

C ++, 239 bytes

Meu primeiro código de golfe! [ Por favor, seja gentil ]

#define r(a,b) ((a<<b)|(a>>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

Versão não destruída:

I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

Não é o melhor hash e, definitivamente, não é o código mais curto existente. Aceitando dicas de golfe e esperando melhorar!

Embrulho

Provavelmente não é o melhor do mundo, mas mesmo assim um invólucro

I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}
SpelingMistake
fonte
2
Parece sólido, mas com 64 bits, pode estar sujeito a força bruta. Há cerca de 50% de chance de encontrar uma colisão em ~ sqrt (n) testes (dentre n saídas totais); 2 ^ 32 tentativas não são muito para um PC moderno.
226156 Tucuxi
O invólucro não possui inclusões de cabeçalho e, em geral, leva a muitos hashes iguais.
Vi.
Forneça algumas amostras de hash. Para mim, "3" e "33" levam a 481c27f26cba06cf (usando este wrapper).
Vi.
Rachado: codegolf.stackexchange.com/a/51215/41288 . Eu suspeito logo antes da @Vi. descobriu por que tantos hashes eram iguais.
tucuxi
1
Colisão adequada (sem uso de bug): printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_-> a4baea17243177fd; printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_-> a4baea17243177fd. O bruteforcer encontra colisões aqui muito mais rapidamente em comparação com outros hash de 64 bits aqui.
Vi.
2

Java, 299 291 282 bytes, com falha.

import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

Faz algumas operações no BigIntegers e, em seguida, pega o módulo de resultado 2 128 .

SuperJedi224
fonte
Como eu executo isso? Ideone se recusa a compilá-lo.
Martin Ender
1
Você pode executá-lo no Ideone renomeando a classe para "Principal" ou removendo a primeira palavra-chave "pública" (mas NÃO a segunda). Qualquer um funcionará.
SuperJedi224
Rachado.
Martin Ender
1
@ SuperJedi224 Por que não remover o primeiro publicvocê mesmo, economizando 7 caracteres?
precisa saber é o seguinte
@immibis Porque então eu não acho que funcionaria bem no Eclipse. Eu vou tentar embora. EDIT: Eu acho que sim. Isso é uma surpresa.
SuperJedi224
2

C, 128 bytes [ rachado ]

p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

Este é mais ou menos o mesmo algoritmo que meu último esforço (quebrado pelo Vi.) , Mas agora tem rodas de hamster suficientes para gerar hashes de 128 bits adequados.

As quatro constantes principais no código são as seguintes:

'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

Como antes, este é um programa completo sem a necessidade de um wrapper. O inteiro I é inserido via stdin como dados binários brutos (big-endian) e o hash O é impresso em hexadecimal para stdout. Zeros à esquerda em I são ignorados.

Exemplos:

echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a
ossifrage melindroso
fonte
Seu exemplo não mostrou uma colisão ali (os dois primeiros)?
mbomb007
@ mbomb007 Não. A entrada é um número entre 0 e 2 ^ (2 ^ 30). 0x00 e 0x0000 são iguais a zero, portanto produzem a mesma saída.
Ossifrage melindroso
2

C, 122 bytes [ rachado ]

long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

Loops aninhados, LCGs de meia avaliação e troca variável. O que há para não amar?

Aqui está uma versão ungolf'd para brincar:

long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

Este é um programa totalmente independente que lê de STDIN e imprime em STDOUT.

Exemplo:

> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

Em alguns benchmarks simples, ele processa cerca de 3 MB / s de dados de texto. A velocidade do hash depende dos próprios dados de entrada, portanto, isso provavelmente deve ser levado em consideração.

Mr. Llama
fonte
1

PHP 4.1, 66 bytes [ rachado ]

Estou apenas me aquecendo.

Espero que você ache isso interessante.

<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

Eu tentei números tão grandes quanto 999999999999999999999999999.
A saída parecia estar dentro da faixa de 2 128 .


O PHP 4.1 é necessário devido ao register_globals diretiva.

Ele funciona criando automaticamente variáveis ​​locais da sessão, POST, GET, PEDIDO e cookies.

Ele usa a chave a. (EG: acesso porhttp://localhost/file.php?a=<number> ).

Se você quiser testá-lo com o PHP 4.2 e mais recente, tente o seguinte:

<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

Esta versão funciona apenas com POST e GET.


Exemplo de saída:

0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

(Garanto que existem números que produzem o mesmo hash).

Ismael Miguel
fonte
1

C, 134 bytes, Rachado

Este é o programa C completo.

long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

O que faz: A idéia é pegar a entrada como matriz de bytes e anexar bytes pseudo-aleatórios (mas determinísticos) no final para tornar o comprimento igual a 2 2 30 (um pouco mais). A implementação lê entrada byte a byte e começa a usar dados pseudo-aleatórios quando encontra o primeiro caractere que não é um dígito.

Como o PRNG embutido não é permitido, eu o implementei.

Há um comportamento indefinido / definido pela implementação que reduz o código (o valor final não deve ser assinado e eu devo usar tipos diferentes para valores diferentes). E eu não poderia usar valores de 128 bits em C. Versão menos ofuscada:

long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}
barteks2x
fonte
Cracked
ossifrage melindroso
1

Python 2.X - 139 bytes [[ Cracked ]]

Isso é bastante semelhante a todos os outros hashes (LOOP, XOR, SHIFT, ADD) aqui. Venha pegar seus ladrões de pontos;) Eu vou dificultar depois que este for resolvido.

M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

Wrapper (espera um argumento na base 16 também conhecido como hexadecimal):

import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()
Intrigado
fonte
1
Além disso, não tenho certeza de que essa entrada atenda às especificações do OP, pois na minha máquina a função leva vários segundos em entradas grandes. Por exemplo, H(2**(2**10))demorou cerca de 8 ou 9 segundos, enquanto H(2**(2**12))demorou cerca de 29 segundos e H(2**(2**14))levou mais de dois minutos.
mathmandan
Você está absolutamente certo, eu obviamente deveria ter testado o tempo para entradas maiores. Além disso, parece que esqueci de executar meu próprio teste depois que esse turno foi adicionado. A versão original estava sem turno (antes da postagem) e estava passando no meu teste "sem colisões nos primeiros 100000 números inteiros": /
Intrigado
1

Python 2.7 - 161 bytes [[ Cracked ]]

Bem, desde que eu consegui mudar minha primeira função de hash para uma versão inútil antes de publicá-la, acho que publicarei outra versão de uma estrutura semelhante. Desta vez, testei-o contra colisões triviais e testei a maioria das magnitudes de entrada possíveis quanto à velocidade.

A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

Wrapper (não contado no bytecount)

import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

Execute o exemplo (a entrada é sempre um número hexadecimal):

$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB
Intrigado
fonte
1
Rachado .
precisa saber é o seguinte
Bem feito jimmy :)
Intrigado
1

Ruby, 90 bytes

def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

Um algoritmo de hash altamente aleatório que criei sem olhar para nenhum hash real ... não faço ideia se é bom. é preciso uma string como entrada.

Embrulho:

def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end 
puts H buildString gets
MegaTom
fonte
Você poderia fornecer o invólucro que a pergunta requer?
Dennis
Qual é o formato de entrada? Eu tentei com um número, mas ele diz comparison of String with 255 failed (ArgumentError).
precisa saber é o seguinte
H pega uma string, Build string pega o número exigido pelo OP e o transforma em uma string.
MegaTom 4/06/15
Eu acho que você precisa de um gets.to_ino invólucro.
precisa saber é o seguinte
Rachado .
precisa saber é o seguinte
0

Mathematica, 89 bytes, quebrado

Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

Não é o mais curto.

LegionMammal978
fonte
3
Como você executa isso sem o Mathematica? "Deve haver um compilador / intérprete gratuito (como na cerveja) que possa ser executado em uma plataforma x86 ou x64 ou a partir de um navegador da web".
Martin Ender
2
@ MartinBüttner wolfram.com/mathematica/trial
LegionMammal978
Rachado.
Martin Ender
0

PHP, 79 bytes (quebrado. Com um comentário):

echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

Isso faz muitas coisas assustadoras através de conversões de tipo em php, o que dificulta a previsão;) (ou pelo menos espero que sim). Porém, não é a resposta mais curta ou mais ilegível.

Para executá-lo, você pode usar o PHP4 e registrar globais (com? I = 123) ou usar a linha de comando:

php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"
Sebb
fonte
5
O valor de saída do hash parece com ponto flutuante. E é o mesmo para 3000000000000000000000000000000000000000000001 e 3000000000000000000000000000000000000000000000.
Vi.
0

C # - 393 bytes decifrados

using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

Ungolfed:

using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

Eu nunca toquei em criptografia ou hash na minha vida, então seja gentil :)

É uma implementação simples de um FNV-1a hash com alguma matriz girando na entrada. Estou certo de que existe uma maneira melhor de fazer isso, mas é o melhor que posso fazer.

Pode usar um pouco de memória em entradas longas.

ldam
fonte
Rachado: codegolf.stackexchange.com/a/51277/101 Além de apresentar preenchimento defeituoso, esse não é um hash criptográfico; há muitas maneiras de quebrá-lo.
Aaaaaaaaaaa
0

Python 2, 115 bytes [ Rachado já! ]

OK, aqui está o meu último esforço. Apenas 115 bytes porque a nova linha final não é necessária.

h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

Este é um programa completo que insere um número inteiro decimal no stdin e imprime um valor de hash decimal no stdout. Zeros iniciais extras resultarão em diferentes valores de hash, então, assumirei que a entrada não possui nenhum.

Isso funciona preenchendo pedaços de 197 dígitos do número de entrada por meio de uma exponenciação modular. Ao contrário de alguns idiomas, a int()função sempre usa como padrão a base 10, portantoint('077') como 77, não 63.

Saídas de amostra:

$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s
ossifrage melindroso
fonte
1
Não usou a ordem dos blocos ... Rachado .
precisa saber é o seguinte
Ugh. Eu entrego :-(
ossifrage melindroso