Предположим, у вас есть хеш-функция которая принимает строки длиной и возвращает строки длины и имеет приятное свойство - она устойчива к столкновениям , то есть трудно найти две разные строки с одинаковым хешем .
Теперь вы хотели бы создать новую хеш-функцию которая принимает строки произвольной длины и отображает их в строки длины , в то же время сохраняя устойчивость к столкновениям.
К счастью для вас, уже в 1979 году был опубликован метод, теперь известный как конструкция Меркля-Дамгарда, который достигает именно этого.
Задача этой задачи будет заключаться в реализации этого алгоритма, поэтому сначала мы рассмотрим формальное описание конструкции Меркля – Дамгарда, прежде чем перейти к пошаговому примеру, который должен показать, что подход проще, чем это может появиться сначала.
Учитывая некоторое целое число , хеш-функцию как описано выше, и входную строку произвольной длины, новая хеш-функция выполняет следующие действия:
- Установите, длина и разбиение на куски длины n , заполняя последний кусок завершающими нулями, если необходимо. Это дает m = ⌈ lмного кусков, которые помечены как.
- Добавьте начальный и конечный фрагменты и , где - строка, состоящая из нулей и - этодвоичное число , дополненноеначальныминулями до длины .
- Теперь итеративно применяем к текущему фрагменту добавленному к предыдущему результату : , где . (Этот шаг может быть более понятным после просмотра примера ниже.)
- Выход является конечным результатом .
Задание
Напишите программу или функцию, которая принимает в качестве входных данных положительное целое число , хеш-функцию качестве черного ящика и непустую строку и возвращает тот же результат, что и на тех же входах.
Это код-гольф , поэтому выигрывает самый короткий ответ на каждом языке.
пример
Допустим, , поэтому наша заданная хеш-функция принимает строки длиной 10 и возвращает строки длиной 5.
- Учитывая ввод , мы получаем следующие фрагменты: , , и . Обратите внимание, что необходимо дополнить до длины 5 с одним завершающим нулем.
- - это просто строка из пяти нулей, а - это пять в двоичном виде ( ), дополненная двумя ведущими нулями.
- Теперь куски объединяются с :
- is our output.
Let's have a look how this output would look depending on some choices1 for :
- If , i.e. just returns every second character, we get:
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!Ответы:
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источник
let
in a guard is shorter than usingwhere
: Try it online!mapM(\_->"01")a
можноmapM(:"1")a
.R ,
159154 байтПопробуйте онлайн!
Тьфу! Отвечать на вызовы строк в R никогда не бывает красиво, но это ужасно. Это поучительный ответ о том, как не писать "нормальный" R-код ...
Спасибо nwellnhof за исправление ошибки стоимостью 0 байт!
Спасибо Дж. Доу за замену псевдонимов операторов на изменение приоритета, хорошо для -4 байта.
Приведенное ниже объяснение относится к предыдущей версии кода, но принципы остаются теми же.
источник
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:
источник
Ruby, 78 bytes
Try it online!
How it works:
источник
Jelly, 23 bytes
Try it online!
AcceptsH at the line above it, s as its left argument, and n as its right argument.
источник
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
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.
источник
Perl 6,
7968 bytesTry it online!
Explanation
источник
Чисто , 143 байта
Попробуйте онлайн!
источник
Python 2 ,
126113 байтовПопробуйте онлайн!
-13 благодаря триггернометрии .
Да, это мерзость, почему я не могу просто использовать встроенный для разделения строки на куски ...? :-(
источник
while
петля является лучшей встроенным я мог надеяться. 104 байта'0'*~-n
instead of'0'*(len(s)%n)
is shorter (and actually correct for shorter inputs).Programming Puzz
(16 символов). Замена'0'*(len(s)%n)
с'0'*~-n
исправлениями , что и экономит 7 байт.Python 2 ,
106102 байтаНа этот раз функция превосходит лямбду. -4 байта для простого манипулирования синтаксисом, благодаря Джо Кингу.
Попробуйте онлайн!
источник
Japt , 27 байт
Попытайся!
Я не нашел возможности для Japt принимать функции непосредственно в качестве входных данных, поэтому он принимает строку, которая интерпретируется как код Japt, и ожидает, что она определит функцию. В частности,ЧАС это принимает символы с нечетными индексами, в то время как этот пример является "умножением кодов символов и возьмите 5 старших цифр" пример.
OvW
принимает третий ввод и интерпретирует его как Japt, а затемg
вызывает его. Заменив этоOxW
разрешением на ввод вместо функции Javascript, или, если функция (каким-то образом) уже была сохранена в W, она может простоW
сохранить 2 байта. Ссылка выше имеет рабочий примерБлагодаря тому, как Japt принимает входные данные,s будет N будет ЧАС будет
U
,V
иW
Объяснение:
источник
GolfScript , 47 байт
Попробуйте онлайн!
источник
ОК , 41 байт
Попробуйте онлайн!
источник