Hashing de comprimento arbitrário

16

Considere que você possui uma função de hash H que pega cadeias de comprimento 2n e retorna cadeias de comprimento n e tem a propriedade agradável de que é resistente a colisões , ou seja, é difícil encontrar duas cadeias diferentes ss com o mesmo hash H(s)=H(s) .

Agora você deseja criar uma nova função de hash H que pega cadeias de comprimento arbitrário e as mapeia para cadeias de comprimento n , enquanto ainda é resistente a colisões.

Para sua sorte, já em 1979 foi publicado um método agora conhecido como a construção Merkle – Damgård que alcança exatamente isso.

A tarefa desse desafio será implementar esse algoritmo; portanto, primeiro examinaremos uma descrição formal da construção de Merkle – Damgård, antes de seguir um exemplo passo a passo que deve mostrar que a abordagem é mais simples do que pode aparecer a princípio.

Dado um número inteiro n>0 , uma função de hash H conforme descrito acima e uma sequência de entrada s de comprimento arbitrário, a nova função de hash H faz o seguinte:

  • Defina l=|s|, o comprimento de s e divida s em pedaços de comprimento n , preenchendo o último pedaço com zeros à direita, se necessário. Isso produz m=lnmuitos pedaços rotulados comoc1,c2,,cm.
  • Adicione um pedaço inicial e final c0 e cm+1 , em que c0 é uma string que consiste em n zeros cm+1 é n em binário, preenchido com zeros à esquerda no comprimento n .
  • Agora, iterativamente, aplique H ao bloco atual ci anexado ao resultado anterior ri1 : ri=H(ri1ci) , em que r0=c0 . (Esta etapa pode ficar mais clara depois de analisar o exemplo abaixo.)
  • A saída de H é o resultado final rm+1 .

A tarefa

Escreva um programa ou função que tenha como entrada um número inteiro positivo n , uma função de hash H como caixa preta e uma string não vazia s e retorne o mesmo resultado que H nas mesmas entradas.

Isso é , então a resposta mais curta em cada idioma vence.

Exemplo

Digamos n=5 , então nossa função hash dada H pega cadeias de comprimento 10 e retorna cadeias de comprimento 5.

  • Dada a entrada de s="Programming Puzzles" , obtemos os seguintes blocos: s1="Progr" , s2="ammin" , s3="g Puz" e s4="zles0" . Observe que s4 precisava ser preenchido com o comprimento 5 com um zero à direita.
  • c0="00000" é apenas uma sequência de cinco zerosc5="00101" é cinco em binário (101 ), preenchido com dois zeros à esquerda.
  • Agora os pedaços são combinados com H :
    r0=c0="00000"
    r1=H(r0c1)=H("00000Progr")
    r2=H(r1c2)=H(H("00000Progr")"ammin") r3=H(r2c3)=H(H(H("00000Progr")"ammin")"g Puz")
    r4=H(r3c4)=H(H(H(H("00000Progr")"ammin")"g Puz")"zles0")
    r5=H(r4c5)=H(H(H(H(H("00000Progr")"ammin")"g Puz")"zles0")"00101")
  • r5 é a nossa saída.

Vamos dar uma olhada na aparência dessa saída, dependendo de algumas opções 1 para H :

  • Se H("0123456789")="13579" , ou seja, H apenas retorna cada segundo caractere, obtemos:
    r1=H("00000Progr")="00Por"
    r2=H("00Porammin")="0oamn"
    r3=H("0oamng Puz")="omgPz"
    r4=H("omgPzzles0")="mPze0"
    r5=H("mPze000101")="Pe011"
    Portanto,"Pe011" precisa ser a saída se esseH for fornecido como função de caixa preta.
  • Se H simplesmente retornar os 5 primeiros caracteres de sua entrada, a saída de H será "00000" . Da mesma forma, se H retornar os últimos 5 caracteres, a saída será "00101" .
  • Se H multiplicar os códigos de caracteres de sua entrada e retornar os cinco primeiros dígitos desse número, por exemplo, H("PPCG123456")="56613" , então H("Programming Puzzles")="91579" .

1 Por simplicidade, os H não são realmente resistentes a colisões, embora isso não importe para testar sua submissão.

Laikoni
fonte
Sandbox (excluído)
Laikoni 10/10
Devo dizer que é divertido que o exemplo dado tenha o último hash 'completo' de "OMG Puzzles!" efetivamente omgPzzles0. Exemplo de entrada bem escolhido!
LambdaBeta
Podemos assumir alguma flexibilidade no formato de entrada para H (por exemplo, ele usa duas strings de comprimento n, ou uma string mais longa, da qual considera apenas os primeiros 2n caracteres)?
Delfad0r
Os caracteres de espaço, por exemplo, estão entre a saída "g P" válida?
guest271314
@ guest271314 Se o espaço fizer parte do hash resultante, ele precisará ser gerado. Se o hash for realmente "gP", você não poderá gerar um espaço entre eles.
Laikoni 11/11/19

Respostas:

7

Haskell , 91 90 86 bytes

n!h|let a='0'<$[1..n];c?""=c;c?z=h(c++take n(z++a))?drop n z=h.(++mapM(:"1")a!!n).(a?)

Experimente online!

Explicação

a='0'<$[1..n]

Apenas atribui a string "00...0"( '0' n vezes) aa


c?""=c
c?z=h(c++take n(z++a))?drop n z

A função ?implementa a aplicação recursiva de h: cé o hash que obtivemos até agora (comprimento n ), zé o restante da string. Se zestiver vazio, simplesmente retornamos c, caso contrário, pegamos os primeiros n caracteres de z(possivelmente preenchendo com zeros de a), acrescentamos ce aplicamos h. Isso fornece o novo hash e, em seguida, chamamos ?recursivamente esse hash e os caracteres restantes de z.


n!h=h.(++mapM(:"1")a!!n).(a?)

A função ! é a que realmente resolve o desafio. É preciso n, he s(implícita) como entradas. Nós computamos a?s, e tudo o que precisamos fazer é anexar nem binário e aplicar hnovamente. mapM(:"1")a!!nretorna a representação binária de n .

Delfad0r
fonte
1
letem um guarda é mais curto do que usar where: Experimente on-line!
Laikoni 10/10
2
Parece que mapM(\_->"01")apode ser mapM(:"1")a.
Xnor 10/10
7

R , 159 154 bytes

function(n,H,s,`?`=paste0,`*`=strrep,`/`=Reduce,`+`=nchar,S=0*n?s?0*-(+s%%-n)?"?"/n%/%2^(n:1-1)%%2)(function(x,y)H(x?y))/substring(S,s<-seq(,+S,n),s--n-1)

Experimente online!

Que nojo! Responder a desafios de em R nunca é bonito, mas isso é horrível. Esta é uma resposta instrutiva sobre como não escrever código R "normal" ...

Agradecimentos ao nwellnhof por corrigir um erro, a um custo de 0 bytes!

Agradecimentos a J.Doe por trocar o alias do operador para alterar a precedência, bom para -4 bytes.

A explicação abaixo é para a versão anterior do código, mas os princípios permanecem os mesmos.

function(n,H,s,               # harmless-looking function arguments with horrible default arguments 
                              # to prevent the use of {} and save two bytes
                              # then come the default arguments,
                              # replacing operators as aliases for commonly used functions:
 `+`=paste0,                  # paste0 with binary +
 `*`=strrep,                  # strrep for binary *
 `/`=Reduce,                  # Reduce with binary /
 `?`=nchar,                   # nchar with unary ?
 S=                           # final default argument S, the padded string:
  0*n+                        # rep 0 n times
  s+                          # the original string
  0*-((?s)%%-n)+              # 0 padding as a multiple of n
  "+"/n%/%2^(n:1-1)%%2)       # n as an n-bit number
                              # finally, the function body:
 (function(x,y)H(x+y)) /      # Reduce/Fold (/) by H operating on x + y
  substring(S,seq(1,?S,n),seq(n,?S,n))  # operating on the n-length substrings of S
Giuseppe
fonte
Eu acho 0*(n-(?s)%%n)que não funciona se n divide s uniformemente. Mas 0*-((?s)%%-n)deve funcionar.
Nwellnhof 14/10
@ Nwellnhof ah, é claro, obrigado, fixo.
Giuseppe
Alterações menores, 155 bytes
J.Doe 16/10
1
@ J.Doe bom! Salvei outro byte, pois seqtem 1como fromargumento por padrão.
Giuseppe
3

C (gcc) , 251 bytes

#define P sprintf(R,
b(_){_=_>1?10*b(_/2)+_%2:_;}f(H,n,x)void(*H)(char*);char*x;{char R[2*n+1],c[n+1],*X=x;P"%0*d",n,0);while(strlen(x)>n){strncpy(c,x,n);x+=n;strcat(R,c);H(R);}P"%s%s%0*d",R,x,n-strlen(x),0);H(R);P"%s%0*d",R,n,b(n));H(R);strcpy(X,R);}

Experimente online!

Não é tão limpo quanto a solução do bash e é altamente improvável.

A função está fassumindo Hcomo uma função que substitui sua entrada de string pelo hash da string, ncomo na descrição, e xna string de entrada e no buffer de saída.

Descrição:

#define P sprintf(R,     // Replace P with sprintf(R, leading to unbalanced parenthesis
                         // This is replaced and expanded for the rest of the description
b(_){                    // Define b(x). It will return the integer binary expansion of _
                         // e.g. 5 -> 101 (still as integer)
  _=_>1?                 // If _ is greater than 1
    10*b(_/2)+_%2        // return 10*binary expansion of _/2 + last binary digit
    :_;}                 // otherwise just _
f(H,n,x)                 // Define f(H,n,x)
  void(*H)(char*);       // H is a function taking a string
  char*x; {              // x is a string
  char R[2*n+1],c[n+1],  // Declare R as a 2n-length string and c as a n-length string
  *X=x;                  // save x so we can overwrite it later
  sprintf(R,"%0*d",n,0); // print 'n' 0's into R
  while(strlen(x)>n){    // while x has at least n characters
    strncpy(c,x,n);x+=n; // 'move' the first n characters of x into c
    strcat(R,c);         // concatenate c and R
    H(R);}               // Hash R
  sprintf(R,"%s%s%0*d"   // set R to two strings concatenated followed by some zeroes
    R,x,                 // the two strings being R and (what's left of) x
    n-strlen(x),0);      // and n-len(x) zeroes
  H(R);                  // Hash R
  sprintf(R,"%s%*d",R,n, // append to R the decimal number, 0 padded to width n
    b(n));               // The binary expansion of n as a decimal number
  H(R);strcpy(X,R);}     // Hash R and copy it into where x used to be
LambdaBeta
fonte
229 bytes
tetocat 30/10
Eu penso: 227 bytes (saindo do comentário de ceilingcat)
Zachary
3

Ruby , 78 bytes

->n,s,g{(([?0*n]*2*s).chop.scan(/.{#{n}}/)+["%0#{n}b"%n]).reduce{|s,x|g[s+x]}}

Experimente online!

Como funciona:

([?0*n]*2*s).chop    # Padding: add leading and trailing 
                     # zeros, then remove the last one
.scan(/.{#{n}}/)     # Split the string into chunks
                     # of length n
+["%0#{n}b"%n]       # Add the trailing block
.reduce{|s,x|g[s+x]} # Apply the hashing function
                     # repeatedly
GB
fonte
2

Gelatina , 23 bytes

0Ṿ;s;BṾ€ṚWƲ}z”0ZU0¦;Ç¥/

Experimente online!

Aceita H na linha acima, s como argumento à esquerda, e n como argumento correto.

Erik, o Outgolfer
fonte
2

Bash , 127-ε bytes

Z=`printf %0*d $1` R=$Z
while IFS= read -rn$1 c;do R=$R$c$Z;R=`H<<<${R::2*$1}`;done
H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

Experimente online!

Isso funciona como um programa / função / script / snippet. H deve ser resolvido por um programa ou função que executará o hash. N é o argumento. Chamada de exemplo:

$ H() {
>   sed 's/.\(.\)/\1/g'
> }
$ ./wherever_you_put_the_script.sh 5 <<< "Programming Puzzles"  # if you add a shebang
Pe011

Descrição:

Z=`printf %0*d $1`

Isso cria uma sequência de $1zeros. Isso funciona chamando printf e solicitando que imprima um número inteiro preenchido com uma largura extra de argumento . Esse argumento extra que passamos é $1o argumento para o programa / função / script que armazena n.

R=$Z

Isso apenas copia Z, nossa cadeia zero, para R, nossa cadeia resultante, em preparação para o loop de hash.

while IFS= read -rn$1 c; do

Isso faz um loop na entrada de cada $1(n) caractere que carrega os caracteres lidos em c. Se a entrada terminar, c simplesmente ficará muito curto. A ropção garante que quaisquer caracteres especiais na entrada não sejam interpretados por bash. Esse é o título - que rnão é estritamente necessário, mas faz com que a função corresponda com mais precisão à entrada.

R=$R$c$Z

Isso concatena os n caracteres lidos da entrada para R junto com os zeros para preenchimento (muitos zeros por enquanto).

R=`H<<<${R::2*$1}`;done

Isso usa uma string here como entrada para a função hash. O conteúdo${R::2*$1} é uma substituição de parâmetro do bash um tanto esotérica que lê: R, começando de 0, apenas 2n caracteres.

Aqui o loop termina e terminamos com:

H< <(printf $R%0*d $1 `bc <<<"obase=2;$1"`)

Aqui, o mesmo truque de seqüência de caracteres de formato é usado para preencher 0 o número. bcé usado para convertê-lo em binário, definindo a base de saída (obase) como 2. O resultado é passado para a função / programa de hash cuja saída não é capturada e, portanto, é mostrada ao usuário.

LambdaBeta
fonte
Por que "127-ε"? Por que não apenas "127"?
Solomon Ucko 11/11
Eu não sei. Eu estava em cima do muro sobre a necessidade da rbandeira. Achei que 1 byte realmente não importa, mas se pressionado eu poderia raspar.
LambdaBeta 11/10
Para o readcomando?
Solomon Ucko 11/11
Porque sem ele um `` na entrada será interpretado em vez de ignorado, então eles terão que ser escapados.
LambdaBeta
Talvez adicione uma observação sobre isso?
Solomon Ucko 11/11
2

Pitão , 24 bytes

Como Pyth não permite que H seja usado para um nome de função, eu o uso y.

uy+GH+c.[E=`ZQQ.[ZQ.BQ*Z

Experimente online! Exemplo é com a versão "cada segundo caractere" de H.

Steven H.
fonte
2

Perl 6 , 79 68 bytes

{reduce &^h o&[~],comb 0 x$^n~$^s~$n.fmt("%.{$n-$s.comb%-$n}b"): $n}

Experimente online!

Explicação

{
  reduce         # Reduce with
    &^h o&[~],   # composition of string concat and hash function
    comb         # Split string
      0 x$^n     # Zero repeated n times
      ~$^s       # Append input string s
      ~$n.fmt("  # Append n formatted
        %.       # with leading zeroes,
        {$n             # field width n for final chunk
         -$s.comb%-$n}  # -(len(s)%-n) for padding,
        b")      # as binary number
      :          # Method call with colon syntax
      $n         # Split into substrings of length n
}
Nwellnhof
fonte
1

Limpo , 143 bytes

import StdEnv
r=['0':r]
$n h s=foldl(\a b=h(a++b))(r%(1,n))([(s++r)%(i,i+n-1)\\i<-[0,n..length s]]++[['0'+toChar((n>>(n-p))rem 2)\\p<-[1..n]]])

Experimente online!

Furioso
fonte
1

Python 2 , 126 113 bytes

lambda n,H,s:reduce(lambda x,y:H(x+y),re.findall('.'*n,'0'*n+s+'0'*(n-len(s)%n))+[bin(n)[2:].zfill(n)])
import re

Experimente online!

13 graças à triggernometria .

Sim, isso é uma abominação, por que não posso simplesmente usar um built-in para dividir uma string em pedaços ...? :-(

Erik, o Outgolfer
fonte
codegolf.stackexchange.com/a/173952/55696 Um whileloop é o melhor componente que eu poderia esperar. 104 bytes
Steven H.
@StevenH. Sim, especialmente se você estiver realmente focado no próprio golfe. > _>
Erik the Outgolfer
'0'*~-nem vez de '0'*(len(s)%n)é mais curto (e realmente correto para entradas mais curtas).
Nwellnhof 14/10
@nwellnhof Sim, mas definitivamente não é a mesma coisa.
Erik the Outgolfer
Talvez eu não tenha sido claro o suficiente. Sua solução fornece a resposta errada para cadeias de caracteres como Programming Puzz(16 caracteres). Substituindo '0'*(len(s)%n)por '0'*~-ncorreções que salvam 7 bytes.
Nwellnhof 14/10/19
1

Python 2 , 106 102 bytes

Pela primeira vez, a função supera a lambda. -4 bytes para manipulação simples de sintaxe, graças a Jo King.

def f(n,H,s):
 x='0'*n;s+='0'*(n-len(s)%n)+bin(n)[2:].zfill(n)
 while s:x=H(x+s[:n]);s=s[n:]
 return x

Experimente online!

Steven H.
fonte
O resultado não deve ser 'Pe011', não 'e011'?
Triggernometry
Que deveria. Fixo!
Steven H.
Use ponto e vírgula em vez de novas linhas. -4 bytes
Jo King
Eu não percebi que funcionou por enquanto loops também, obrigado!
Steven H.
1

Japonês , 27 bytes

òV ú'0 pV¤ùTV)rÈ+Y gOvW}VçT

Tente!

Eu não encontrei nenhum recurso para o Japt assumir funções diretamente como entrada, portanto, isso pega uma string que é interpretada como código Japt e espera que ela defina uma função. Especificamente, OvWpega a terceira entrada e a interpreta como Japt e depois a gchama. Substituir isso por OxWpermite a entrada como uma função Javascript, ou se a função já estava (de alguma forma) armazenada em W, poderia ser apenas We salvar 2 bytes. O link acima tem o exemplo trabalhado deHque recebe caracteres em índices ímpares, enquanto este é o exemplo "multiplique os códigos de caracteres e use os 5 dígitos mais altos".

Devido à maneira como Japt recebe entradas, sserá U,nserá VeH será W

Explicação:

òV                             Split U into segments of length V
   ú'0                         Right-pad the short segment with "0" to the same length as the others
       p     )                 Add an extra element:
        V¤                       V as a base-2 string
          ùTV                    Left-pad with "0" until it is V digits long
              r                Reduce...
                        VçT          ...Starting with "0" repeated V times...
               È       }                                                  ...By applying:
                +Y               Combine with the previous result
                   gOvW          And run W as Japt code

Kamil Drakari
fonte
0

OK , 41 bytes

{(x#48)(y@,)/(0N,x)#z,,/$((x+x!-#z)#2)\x}

Experimente online!

{                                       } /x is n, y is H, z is s.
                          (x+x!-#z)       /number of padding 0's needed + x
                         (         #2)\x  /binary(x) with this length
                      ,/$                 /to string
                    z,                    /append to z
             (0N,x)#                      /split into groups of length x
       (y@,)/                             /foldl of y(concat(left, right))...
 (x#48)                                   /...with "0"*x as the first left string
zgrep
fonte