Hash de longitud arbitraria

16

Considere que tiene una función hash que toma cadenas de longitud y devuelve cadenas de longitud y tiene la buena propiedad de que es resistente a colisiones , es decir, es difícil encontrar dos cadenas diferentes con el mismo hash .H2nnssH(s)=H(s)

Ahora le gustaría construir una nueva función hash que tome cadenas de longitud arbitraria y las asigne a cadenas de longitud , sin dejar de ser resistente a colisiones.Hn

Por suerte para ti, ya en 1979 se publicó un método ahora conocido como la construcción Merkle-Damgård que logra exactamente esto.

La tarea de este desafío será implementar este algoritmo, por lo que primero veremos una descripción formal de la construcción Merkle-Damgård, antes de pasar por un ejemplo paso a paso que debería mostrar que el enfoque es más simple que Puede aparecer al principio.

Dado un número entero , una función hash como se describió anteriormente y una cadena de entrada de longitud arbitraria, la nueva función hash hace lo siguiente:n>0HsH

  • Establecer, la longitud de , y divida en trozos de longitud , llenando el último fragmento con ceros finales si es necesario. Esto produce muchos trozos que están etiquetados como .l=|s|ssnm=lnc1,c2,,cm
  • Añadir un ataque y un trailing trozo y , donde es una cadena que consta de n ceros y c m + 1 es n en binario, rellenado con principales ceros a longitud n .c0cm+1c0ncm+1nn
  • Ahora aplique iterativamente H al fragmento actual ci adjuntado al resultado anterior ri1 : ri=H(ri1ci) , donde r0=c0 . (Este paso podría ser más claro después de ver el ejemplo a continuación).
  • La salida de H es el resultado final rm+1 .

La tarea

Escriba un programa o función que tome como entrada un número entero positivo n , una función hash H como cuadro negro y una cadena no vacía s devuelve el mismo resultado que H en las mismas entradas.

Este es el , por lo que gana la respuesta más corta en cada idioma.

Ejemplo

Digamos n=5 , por lo que nuestra función hash H toma cadenas de longitud 10 y devuelve cadenas de longitud 5.

  • Dada una entrada de s="Programming Puzzles" , obtenemos los siguientes fragmentos: s1="Progr" , s2="ammin" , s3="g Puz" y s4="zles0" . Tenga en cuenta que s4 necesita ser rellenado hasta la longitud 5 con un cero al final.
  • c0="00000" es solo una cadena de cinco ceros yc5="00101" es cinco en binario (101 ), rellenado con dos ceros a la izquierda.
  • Ahora los fragmentos se combinan con 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 es nuestra salida.

Veamos cómo se vería esta salida dependiendo de algunas opciones 1 para H :

  • Si H("0123456789")="13579" , es decir, H solo devuelve cada segundo carácter, obtenemos:
    r1=H("00000Progr")="00Por"
    r2=H("00Porammin")="0oamn"
    r3=H("0oamng Puz")="omgPz"
    r4=H("omgPzzles0")="mPze0"
    r5=H("mPze000101")="Pe011"
    Por lo tanto,"Pe011" debe ser la salida si dichaH se da como función de caja negra.
  • Si H simplemente devuelve los primeros 5 caracteres de su entrada, la salida de H es "00000" . Del mismo modo, si H devuelve los últimos 5 caracteres, la salida es "00101" .
  • Si H multiplica los códigos de caracteres de su entrada y devuelve los primeros cinco dígitos de este número, por ejemplo, H("PPCG123456")="56613" , entonces H("Programming Puzzles")="91579" .

1 Por simplicidad, esos H realidad no son resistentes a colisiones, aunque esto no importa para probar su envío.

Laikoni
fuente
I must say it's fun that the example given has the last 'full' hash be of "OMG Puzzles!" effectively omgPzzles0. Well chosen example input!
LambdaBeta
Can we assume some flexibility on the input format for H (e.g. it takes two strings of length n, or a longer string of which it only considers the first 2n characters)?
Delfad0r
Are space characters, e.g., between "g P" valid output?
guest271314
@guest271314 If the space is part of the resulting hash, it needs to be outputted. If the hash is actually "gP", you may not output a space inbetween.
Laikoni

Respuestas:

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?)

Try it online!

Explanation

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

Just assigns the string "00...0" ('0' n times) to a


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

The function ? implements the recursive application of h: c is the hash we have obtained so far (length n), z is the rest of the string. If z is empty then we simply return c, otherwise we take the first n characters of z (possibly padding with zeros from a), prepend c and apply h. This gives the new hash, and then we call ? recursively on this hash and the remaining characters of z.


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

The function ! is the one actually solving the challenge. It takes n, h and s (implicit) as inputs. We compute a?s, and all we have to do is append n in binary and apply h once more. mapM(:"1")a!!n returns the binary representation of n.

Delfad0r
fuente
1
let in a guard is shorter than using where: Try it online!
Laikoni
2
It looks like mapM(\_->"01")a can be mapM(:"1")a.
xnor
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)

Try it online!

Yuck! Answering challenges in R is never pretty, but this is horrible. This is an instructive answer on how not to write "normal" R code...

Thanks to nwellnhof for fixing a bug, at a cost of 0 bytes!

Thanks to J.Doe for swapping the operator aliasing to change the precedence, good for -4 bytes.

The explanation below is for the previous version of the code, but the principles remain the same.

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
fuente
I think 0*(n-(?s)%%n) doesn't work if n divides s evenly. But 0*-((?s)%%-n) should work.
nwellnhof
@nwellnhof ah, of course, thank you, fixed.
Giuseppe
Minor changes, 155 bytes
J.Doe
1
@J.Doe nice! I saved another byte since seq has 1 as its from argument by default.
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);}

Try it online!

Not as clean as the bash solution, and highly improvable.

The function is f taking H as a function that replaces its string input with that string's hash, n as in the description, and x the input string and output buffer.

Description:

#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
fuente
229 bytes
ceilingcat
I think: 227 bytes (going off of ceilingcat's comment)
Zacharý
3

Ruby, 78 bytes

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

Try it online!

How it works:

([?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
G B
fuente
2

Jelly, 23 bytes

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

Try it online!

Accepts H at the line above it, s as its left argument, and n as its right argument.

Erik the Outgolfer
fuente
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"`)

Try it online!

This works as a program/function/script/snippet. H must be resolveable to a program or function that will perform the hashing. N is the argument. Example call:

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

Description:

Z=`printf %0*d $1`

This creates a string of $1 zeroes. This works by calling printf and telling it to print an integer padded to extra argument width. That extra argument we pass is $1, the argument to the program/function/script which stores n.

R=$Z

This merely copies Z, our zero string, to R, our result string, in preparation for the hashing loop.

while IFS= read -rn$1 c; do

This loops over the input every $1 (n) characters loading the read characters into c. If the input ends then c merely ends up too short. The r option ensures that any special characters in the input don't get bash-interpreted. This is the in the title - that r isn't strictly necessary, but makes the function more accurately match the input.

R=$R$c$Z

This concatenates the n characters read from input to R along with zeroes for padding (too many zeroes for now).

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

This uses a here string as input to the hash function. The contents ${R::2*$1} are a somewhat esoteric bash parameter substitution which reads: R, starting from 0, only 2n characters.

Here the loop ends and we finish with:

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

Here the same format string trick is used to 0 pad the number. bc is used to convert it to binary by setting the output base (obase) to 2. The result is passed to the hash function/program whose output is not captured and thus is shown to the user.

LambdaBeta
fuente
Why "127-ε"? Why not just "127"?
Solomon Ucko
I don't know. I was on the fence about the necessity of the r flag. I figured 1 byte doesn't really matter, but if pushed I could shave it.
LambdaBeta
For the read command?
Solomon Ucko
Because without it a `` in the input will be interpreted instead of ignored, so they'd have to be escaped.
LambdaBeta
Maybe add a note about that?
Solomon Ucko
2

Pyth, 24 bytes

Since Pyth doesn't allow H to be used for a function name, I use y instead.

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

Try it online! Example is with the "every second character" version of H.

Steven H.
fuente
2

Perl 6, 79 68 bytes

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

Try it online!

Explanation

{
  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
fuente
1

Clean, 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]]])

Try it online!

Οurous
fuente
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

Try it online!

-13 thanks to Triggernometry.

Yeah, this is an abomination, why can't I just use a built-in to split a string into chunks...? :-(

Erik the Outgolfer
fuente
codegolf.stackexchange.com/a/173952/55696 A while loop is the best builtin I could hope for. 104 bytes
Steven H.
@StevenH. Yeah, especially if you're actually focusing on the golfing itself. >_>
Erik the Outgolfer
'0'*~-n instead of '0'*(len(s)%n) is shorter (and actually correct for shorter inputs).
nwellnhof
@nwellnhof Yeah, but it's definitely not the same thing.
Erik the Outgolfer
Maybe I wasn't clear enough. Your solution gives the wrong answer for strings like Programming Puzz (16 chars). Replacing '0'*(len(s)%n) with '0'*~-n fixes that and saves 7 bytes.
nwellnhof
1

Python 2, 106 102 bytes

For once, the function outgolfs the lambda. -4 bytes for simple syntax manipulation, thanks to 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

Try it online!

Steven H.
fuente
Shouldn't the result be 'Pe011', not 'e011'?
Triggernometry
That it should. Fixed!
Steven H.
Use semi-colons instead of newlines. -4 bytes
Jo King
I didn't realize that worked for while loops as well, thanks!
Steven H.
1

Japt, 27 bytes

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

Try it!

I haven't found any capability for Japt to take functions directly as an input, so this takes a string which is interpreted as Japt code and expects it to define a function. Specifically, OvW takes the third input and interprets it as Japt, then g calls it. Replacing that with OxW allows input as a Javascript function instead, or if the function were (somehow) already stored in W it could just be W and save 2 bytes. The link above has the worked example of H that takes characters at odd indexes, while this one is the "multiply char-codes and take the 5 highest digits" example.

Due to the way Japt takes inputs, s will be U, n will be V, and H will be W

Explanation:

ò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
fuente
0

oK, 41 bytes

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

Try it 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
fuente