Rozważmy masz funkcji skrótu , który trwa ciągi długości i powrót ciągi o długości i ma tę właściwość, piękny, że jest odporna na zderzenia , czyli trudno jest znaleźć dwa różne ciągi z tego samego skrótu .
Chciałbyś teraz zbudować nową funkcję skrótu która pobiera ciągi o dowolnej długości i odwzorowuje je na ciągi o długości , zachowując jednocześnie odporność na kolizje.
Na szczęście już w 1979 r. Opublikowano metodę znaną obecnie jako konstrukcja Merkle – Damgård, która osiąga właśnie to.
Zadaniem tego wyzwania będzie wdrożenie tego algorytmu, dlatego najpierw przejrzymy formalny opis konstrukcji Merkle – Damgård, a następnie przejrzymy krok po kroku przykład, który powinien wykazać, że podejście jest prostsze niż może się na początku pojawić.
Biorąc pod uwagę liczbę całkowitą , funkcję skrótu jak opisano powyżej i ciąg wejściowy o dowolnej długości, nowa funkcja skrótu wykonuje następujące czynności:
- Ustaw , długość i podział na kawałki o długości , w razie potrzeby wypełniając ostatni fragment końcowymi zerami. Daje to wiele kawałków oznaczonych jako.
- Dodaj początkowy i końcowy fragment i , gdzie jest łańcuchem składającym się z zer, a jest binarnie, wypełnione zerami wiodącymi do długości .
- Teraz iteracyjnie zastosuj do bieżącego fragmentu dołączonego do poprzedniego wyniku : , gdzie . (Ten krok może być bardziej wyraźny po zapoznaniu się z poniższym przykładem).
- Wydajność jest wynikiem końcowym .
Zadanie
Napisz program lub funkcję, która przyjmuje na wejściu dodatnią liczbę całkowitą , funkcję skrótu jako czarną skrzynkę i niepuste ciągi i zwraca ten sam wynik co na tych samych wejściach.
To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w każdym języku.
Przykład
Powiedzmy, że , więc nasza podana funkcja skrótu przyjmuje łańcuchy o długości 10 i zwraca łańcuchy o długości 5.
- Biorąc pod uwagę , otrzymujemy następujące fragmenty: , , i . Zauważ, że trzeba było uzupełnić do długości 5 jednym końcowym zerem.
- to tylko ciąg pięciu zer, a to pięć cyfr binarnych ( ), wypełnionych dwoma zerami wiodącymi.
- Teraz fragmenty są łączone z :
- jest naszym wyjściem.
Zobaczmy, jak wyglądałoby to wyjście w zależności od niektórych opcji 1 dla :
- Jeśli , tj. zwraca tylko co drugi znak, otrzymujemy:
So needs to be the output if such a is given as black box function. - If simply returns the first 5 chars of its input, the output of is . Similarly if returns the last 5 chars, the output is .
- If multiplies the character codes of its input and returns the first five digits of this number, e.g. , then .
1 For simplicity, those are actually not collision resistant, though this does not matter for testing your submission.
omgPzzles0
. Well chosen example input!Odpowiedzi:
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 ofźródło
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.
źródło
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:
źródło
Ruby, 78 bytes
Try it online!
How it works:
źródło
Jelly, 23 bytes
Try it online!
AcceptsH at the line above it, s as its left argument, and n as its right argument.
źródło
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.źródło
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.
źródło
Perl 6,
7968 bytesTry it online!
Explanation
źródło
Clean, 143 bytes
Try it online!
źródło
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...? :-(
źródło
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!
źródło
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:
źródło
GolfScript, 47 bytes
Try it online!
źródło
oK, 41 bytes
Try it online!
źródło