Функция губки
![]() | Этой статье нужно больше ссылок на другие статьи для интеграции в энциклопедию. |
![Иллюстрация принципа работы функции губки](http://upload.wikimedia.org/wikipedia/commons/thumb/7/70/SpongeConstruction.svg/langru-300px-SpongeConstruction.svg.png)
В криптографии функция губки (или просто губка) (англ. sponge construction или sponge function) — это класс алгоритмов с конечным внутренним состоянием, на вход которых поступает двоичная строка произвольной длины, и которые возвращают двоичную строку также произвольной длины f:{0,1}n → {0,1}*. Функция губки может использоваться для создания хеш-функций, потоковых и блочных шифров, генераторов псевдослучайных чисел, имеющих произвольную длину входных данных.
Структура
[править | править код]Губка — это итеративная конструкция для создания функции с произвольной длиной на входе и произвольной длиной на выходе на основе преобразований f. Губка имеет внутреннее состояние S — с данными фиксированного размера b (бит). При этом данные разделены на 2 части — первая S1 размера r, а вторая S2 — размера c. Значение r называется битовой скоростью, а значение с — мощностью; b = r + c.
На фазе инициализации блок данных размера b заполняется нулями, а входные данные M разбиваются на блоки размера r. Дальнейшая работа губки производится в 2 этапа:
- В фазе «впитывания» (absorbing) выполняется операция XOR очередного блока исходного сообщения с первой частью состояния S1 размера r(бит), оставшаяся часть S2 состояния ёмкостью c остается незатронутой. Результат помещается в S1 , а затем состояние S обрабатывается функцией f — многораундовой бесключевой псевдослучайной перестановкой, и так повторяется до исчерпания блоков исходного сообщения.
- В фазе «выжимания» (squeezing) состояние S подаётся на функцию f, после чего часть S1 подаётся на выход. Эти действия повторяются, пока не будет получена последовательность нужной длины (например, длины хэша).
Последние биты c зависят от входных блоков лишь опосредованно и не выводятся в ходе фазы «выжимания» (squeezing).
Применение
[править | править код]![]() | В разделе не хватает ссылок на источники (см. рекомендации по поиску). |
Генератор псевдослучайных чисел, основанный на функции губки
[править | править код]Моделирование ГПСЧ с изменяемыми входными данными
[править | править код]Определим ГПСЧ с изменяемыми исходными данными как объект с состоянием, который поддерживает два типа запросов, в любом порядке:
- Запрос подачи, feed(σ) — подает исходное значение, состоящее из непустой строки σ ϵ , в состояние ГПСЧ;
- Запрос принятия, fetch(l) — поручает ГПСЧ вернуть l бит.
Тогда исходный материал (seeding material), подаваемый на вход генератора — это конкатенация σ, полученных во всех запросах подачи.
Неформально требования к ГПСЧ с изменяемыми исходными данными могут быть определены следующим образом:
Во-первых, его выход (то есть ответы на запросы подачи) должен зависеть от всех исходных материалов. Во-вторых, для злоумышленника, не знающего исходный материал, но наблюдавшего часть вывода, должно быть невозможно сделать вывод об оставшейся части выхода.
Определим идеальный ГПСЧ как конструкцию, использующую Случайный оракул
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/6e/%D0%9E%D1%82%D0%B2%D0%B5%D1%82_%D0%B8%D0%B4%D0%B5%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%93%D0%9F%D0%A1%D0%A7.jpeg/323px-%D0%9E%D1%82%D0%B2%D0%B5%D1%82_%D0%B8%D0%B4%D0%B5%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%93%D0%9F%D0%A1%D0%A7.jpeg)
Конструкцию, которую мы определили, можно описать следующим образом. Она сохраняет как состояние последовательность всех запросов подачи и принятия, которые она получила, составляя историю h. При получении запроса подачи feed(σ) она обновляет историю подсоединением этого запроса. При получении запроса принятия fetch(l), она подает случайному оракулу строку, который в свою очередь шифрует историю строкой и возвращает биты от z до z+l-1 своего ответа, где z — число запрашиваемых бит в запросе подачи. Следовательно, конкатенация ответов на запросы подачи — всего лишь ответ случайного оракула на единичный запрос. Это продемонстрировано на рисунке. Назовем эту конструкцию режимом, сохраняющим историю, с функцией шифрования e(h). Определение режима с сохранением истории, следовательно, сходится к определению этой функции шифрования.
Так как выход ГПСЧ должен зависеть от всего полученного исходного материала, шифрующая функция e(h) должна быть инъективна с исходным материалом. Другими словами, для любых двух последовательностей запросов с различным исходным материалом, два отображения e(h) должны быть различны. Мы называем это полнота исходного материала (seed-completeness). В функции шифрования с полным исходным материалом на запрос принятия будут выданы различные ответы на разные входные строки. Отсюда следует, что ГПСЧ возвращает независимые биты.
Таким образом, предлагается следующее определение идеального ГПСЧ с изменяемыми входными данными.
Идеальный ГПСЧ с изменяемыми входными данными — это режим, сохраняющий историю, называемый случайным оракулом, с функцией шифрования e(h) с полным исходным материалом.
Создание ГПСЧ с использованием функции губки
[править | править код]Кажется естественным включить запрос подачи в фазу «впитывания», а запрос принятия в фазу «выжимания». Однако исполнение функции губки имеет только одну фазу впитывания (один вход), за которой следует одна фаза «выжимания» (то есть один выход произвольной длины) и она не может быть использована для производства многократных фаз.
Очевидно, эту трудность легко обойти. Достаточно считать, что каждый раз как псевдослучайные биты приняты, другое исполнение функции губки запрашивается с другим входом.
При построении функции губки, входное сообщение m ϵ должно быть поделено на блоки из r битов и заполнено. Обозначим, как p(m) функцию, которая делает это, и предположим, что эта функция добавляет только биты после m. Предположим, что мы хотим повторно использовать состояние губки, для которой входной строкой было сообщение m1 и для которой выходные биты были «выжаты» при l>0. Состояние функции губки в этой точке таково, как если бы частичное сообщение m’1 = р(m1) || 0r(⌈l/r⌉-1) было «впитано». Обратите внимание, что нулевые блоки составляют дополнительные итерации из-за фазы сжатия. Перезапуск губки с этой точки означает, что входным будет сообщение m2, для которого m’1 является префиксным.
Чтобы определить ГПСЧ формально, мы должны указать функцию шифрования e(h) с полным исходным материалом, отображающую последовательность запросов подачи и принятия. Выход е(h) используется в качестве входа для функции губки.
На практике идея состоит в том, чтобы не вызвать функцию губки со всей е (h) каждый раз, как получаем запрос принятия. Вместо этого, конструкция использует функцию губки каскадным образом, повторно используя состояние, как описано в разделе 3.2.[где?] Чтобы разрешить повторное использование состояния функции губки е (h) должна быть такой, что если h’ = h || fetch(l) || feed(σ), то p(e(h)) || 0r(⌈l/r⌉-1) — префикс e(h’).
Чтобы связать конструкцию с практической реализацией, опишем для начала конструкцию с двумя ограничениями. Первое ограничение на длину запросов исходного значения. Для фиксированного целого k требуем, чтобы длина исходного материала σв любом запросе подачи feed(σ) была такова, что |p(σ)| = kr. Другими словами, после заполнения, исходный материал покрывает ровно k блоков по r бит. Второе ограничение в том, что первым запросом должен быть запрос подачи.
Конструкция является конструкцией с учетом состояний (stateful), если её состояние состоит из mϵ N бит, принятых с момента последнего запроса подачи. Начнем с нового исполнения функции губки, задаем m = 0. Обозначим как е строку, отображение е(h) запросов, добавленных к истории h.
- Если пришел запрос fetch(l):
Выполнение производит l выходных битов, «выжимая» их из функции губки. Формально е будет адаптирована во время следующего запроса подачи.
Значение m изменено: m = m + l.
- Если пришел запрос feed (σ):
Формально этот запрос подачи вызывает запрос к функции губки с е в качестве входных данных. Если это не первый запрос, то е обновлено только до последнего запроса подачи. Таким образом, результаты запросов получения с момента последнего запроса подачи должны быть включены в е, как если бы е ранее «впитывалась». Сначала е становится равной p(e), чтобы имитировать заполнение при переключении на фазу «выжимания» после предыдущего запроса подачи. Тогда ⌈m\r⌉ −1 блоков по r нулей добавляются к e для учета дополнительных вызовов функции f при последующих запросах подачи. Теперь m сбрасывается: m = 0. (Это часть влияет только на е — ничего не должно измениться в выполнении).
Затем «впитывается» σ. Формально это выражается путём добавления σ к е.
Наконец, выполнение переключает функцию губки на фазу «выжимания». Это означает, что «впитанные» данные должна быть заполнены и перестановка f применена к состоянию. (Формально, это не меняет е, так как заполнение по определению выполняется при переключении на фазу отжима).
Ограничение на фиксированный размер запросов подачи не является обязательным и может быть удалено. Для обеспечения переменной длины исходного материала и сохранения полноты исходного материала, должны быть введены некоторые формы заполнения внутри функции шифрования, чтобы убедиться, что границы исходного материала могут быть идентифицированы. Кроме того, придется добавить способ отличать блоки с нулевым исходным материалом от нулевых блоков. Это может быть сделано, например, постановкой 1 в каждый блок, содержащий исходный материал.
Ограничение первого запроса, являющегося запросом подачи, может быть удалено, так как не имеет смысла генерировать псевдослучайные биты без первой подачи исходного материала. Если первый запрос — это принятие, то выполнение сразу заполняет (пустой строкой) вход, переключает функции губки на фазу «выжимания» и производит выходные биты с помощью «выжимания». Формально в следующем запросе подачи, это должно быть учтено в е присваиванием е значения р (пустая строка) ||0r([m=r]-1).