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 .
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.
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:
- 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 .
- 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 .
- Ahora aplique iterativamente al fragmento actual adjuntado al resultado anterior : , donde . (Este paso podría ser más claro después de ver el ejemplo a continuación).
- La salida de es el resultado final .
La tarea
Escriba un programa o función que tome como entrada un número entero positivo , una función hash como cuadro negro y una cadena no vacía devuelve el mismo resultado que en las mismas entradas.
Este es el código de golf , por lo que gana la respuesta más corta en cada idioma.
Ejemplo
Digamos , por lo que nuestra función hash toma cadenas de longitud 10 y devuelve cadenas de longitud 5.
- Dada una entrada de , obtenemos los siguientes fragmentos: , , y . Tenga en cuenta que necesita ser rellenado hasta la longitud 5 con un cero al final.
- es solo una cadena de cinco ceros y es cinco en binario ( ), rellenado con dos ceros a la izquierda.
- Ahora los fragmentos se combinan con :
- es nuestra salida.
Veamos cómo se vería esta salida dependiendo de algunas opciones 1 para :
- Si , es decir, solo devuelve cada segundo carácter, obtenemos:
Por lo tanto, debe ser la salida si dicha se da como función de caja negra. - Si simplemente devuelve los primeros 5 caracteres de su entrada, la salida de es . Del mismo modo, si devuelve los últimos 5 caracteres, la salida es .
- Si multiplica los códigos de caracteres de su entrada y devuelve los primeros cinco dígitos de este número, por ejemplo, , entonces .
1 Por simplicidad, esos realidad no son resistentes a colisiones, aunque esto no importa para probar su envío.
omgPzzles0
. Well chosen example input!Respuestas:
Haskell,
919086 bytesTry it online!
Explanation
Just assigns the stringn times) to
"00...0"
('0'
a
The functionn ), n characters of
?
implements the recursive application ofh
:c
is the hash we have obtained so far (lengthz
is the rest of the string. Ifz
is empty then we simply returnc
, otherwise we take the firstz
(possibly padding with zeros froma
), prependc
and applyh
. This gives the new hash, and then we call?
recursively on this hash and the remaining characters ofz
.The functionn .
!
is the one actually solving the challenge. It takesn
,h
ands
(implicit) as inputs. We computea?s
, and all we have to do is appendn
in binary and applyh
once more.mapM(:"1")a!!n
returns the binary representation offuente
let
in a guard is shorter than usingwhere
: Try it online!mapM(\_->"01")a
can bemapM(:"1")a
.R,
159154 bytesTry it online!
Yuck! Answering string 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.
fuente
0*(n-(?s)%%n)
doesn't work if n divides s evenly. But0*-((?s)%%-n)
should work.seq
has1
as itsfrom
argument by default.C (gcc), 251 bytes
Try it online!
Not as clean as the bash solution, and highly improvable.
The function is
f
takingH
as a function that replaces its string input with that string's hash,n
as in the description, andx
the input string and output buffer.Description:
fuente
Ruby, 78 bytes
Try it online!
How it works:
fuente
Jelly, 23 bytes
Try it online!
AcceptsH at the line above it, s as its left argument, and n as its right argument.
fuente
Bash, 127-ε bytes
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:
Description:
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.This merely copies Z, our zero string, to R, our result string, in preparation for the hashing loop.
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. Ther
option ensures that any special characters in the input don't get bash-interpreted. This is the-ε
in the title - thatr
isn't strictly necessary, but makes the function more accurately match the input.This concatenates the n characters read from input to R along with zeroes for padding (too many zeroes for now).
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:
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.fuente
r
flag. I figured 1 byte doesn't really matter, but if pushed I could shave it.read
command?Pyth, 24 bytes
Since Pyth doesn't allow H to be used for a function name, I use
y
instead.Try it online! Example is with the "every second character" version of H.
fuente
Perl 6,
7968 bytesTry it online!
Explanation
fuente
Clean, 143 bytes
Try it online!
fuente
Python 2,
126113 bytesTry 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...? :-(
fuente
while
loop is the best builtin I could hope for. 104 bytes'0'*~-n
instead of'0'*(len(s)%n)
is shorter (and actually correct for shorter inputs).Programming Puzz
(16 chars). Replacing'0'*(len(s)%n)
with'0'*~-n
fixes that and saves 7 bytes.Python 2,
106102 bytesFor once, the function outgolfs the lambda. -4 bytes for simple syntax manipulation, thanks to Jo King.
Try it online!
fuente
Japt, 27 bytes
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,H that takes characters at odd indexes, while this one is the "multiply char-codes and take the 5 highest digits" example.
OvW
takes the third input and interprets it as Japt, theng
calls it. Replacing that withOxW
allows input as a Javascript function instead, or if the function were (somehow) already stored in W it could just beW
and save 2 bytes. The link above has the worked example ofDue to the way Japt takes inputs,s will be n will be H will be
U
,V
, andW
Explanation:
fuente
GolfScript, 47 bytes
Try it online!
fuente
oK, 41 bytes
Try it online!
fuente