У криптографії. функція губки (англ. sponge construction або sponge function) відноситься до класу алгоритмів з кінцевим внутрішнім станом, на вхід якої надходить двоичная рядок довільної довжини, і яка повертає двійкову рядок також довільної довжини f: ^ n → ^ *. Губка є узагальненням як хеш-функцій. так і потокових і блокових шифрів, генераторів псевдовипадкових чисел, що мають довільну довжину вхідних даних.
Губка - це ітеративна конструкція для створення функції з довільною довжиною на вході і довільної завдовжки на виході на основі перетворень 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).
5. Генератор псевдовипадкових чисел, заснований на функції губки 5.1. Моделювання ГПСЧ із змінними вхідними даними
Визначимо ГПСЧ із змінними вихідними даними як об'єкт зі станом, який підтримує два типи запитів, в будь-якому порядку:
- Запит подачі. feed (σ) - подає початкове значення, що складається з непорожній рядки σ ε Z 2 + ^>. в стан ГПСЧ;
- Запит прийняття, fetch (l) - доручає ГПСЧ повернути l біт.
Тоді вихідний матеріал (seeding material), що подається на вхід генератора - це конкатенація σ, отриманих у всіх запитах подачі.
Неформально, вимоги до ГПСЧ із змінними вихідними даними можуть бути визначені наступним чином:
По-перше, його вихід (тобто відповіді на запити подачі) повинен залежати від усіх вихідних матеріалів. По-друге, для зловмисника, який знає вихідний матеріал, але спостерігав частина виведення, має бути неможливо зробити висновок про решти виходу.
Визначимо ідеальний ГПСЧ як конструкцію, яка використовує випадковий оракул.
Відповідь ідеального ГПСЧ із змінними вхідними даними на запит прийняття
Конструкція, яку ми визначили, можна описати наступним чином. Вона зберігає як стан послідовність всіх запитів подачі і прийняття, які вона отримала, складаючи історію h. При отриманні запиту подачі feed (σ) вона оновлює історію підключенням цього запиту. При отриманні запиту прийняття fetch (l), вона подає випадковому оракула рядок, який в свою чергу шифрує історію рядком і повертає біти від z до z + l-1 своєї відповіді, де z - число запитуваних біт в запиті подачі. Отже, конкатенація відповідей на запити подачі - всього лише відповідь випадкового оракула на одноразовий запит. Це продемонстровано на малюнку. Назвемо цю конструкцію режимом, яке зберігає історію, з функцією шифрування e (h). Визначення режиму із збереженням історії, отже, сходиться до визначення цієї функції шифрування.
Оскільки вихід ГПСЧ повинен залежати від всього отриманого вихідного матеріалу, шифрующая функція e (h) повинна бути ін'єкційних з вихідним матеріалом. Іншими словами, для будь-яких двох послідовностей запитів з різним вихідним матеріалом, два відображення e (h) повинні бути різні. Ми називаємо це повнота вихідного матеріалу (seed-completeness). У функції шифрування з повним вихідним матеріалом на запит прийняття будуть видані різні відповіді на різні вхідні рядки. Звідси випливає, що ГПСЧ повертає незалежні біти.
Таким чином, пропонується наступне визначення ідеального ГПСЧ із змінними вхідними даними.
Ідеальний ГПСЧ із змінними вхідними даними - це режим, який зберігає історію, званий випадковим оракулом, з функцією шифрування e (h) з повним вихідним матеріалом.
5.2. Створення ГПСЧ з використанням функції губки
Здається природним включити запит подачі в фазу «вбирання», а запит прийняття в фазу «вичавлювання». Однак виконання функції губки має тільки одну фазу вбирання (один вхід), за якою слідує одна фаза «вичавлювання» (тобто один вихід довільної довжини) і вона не може бути використана для виробництва багаторазових фаз.
Очевидно, ці труднощі легко обійти. Досить вважати, що кожен раз як псевдовипадкові біти прийняті, інше виконання функції губки запитується з іншим входом.
При побудові функції губки, вхідний повідомлення m ε Z 2 * ^> має бути поділено на блоки з r бітів і заповнене. Позначимо, як p (m) функцію, яка робить це, і припустимо, що ця функція додає тільки біти після m. Припустимо, що ми хочемо повторно використовувати стан губки, для якої вхідний рядком було повідомлення m1 і для якої вихідні біти були «вичавлені» при l> 0. Стан функції губки в цій точці таке, як якщо б часткове повідомлення m'1 = р (m1) || 0 r (⌈l / r⌉-1) було «впитано». Зверніть увагу, що нульові блоки складають додаткові ітерації через фази стиснення. Перезапуск губки з цієї точки означає, що вхідним буде повідомлення m2, для якого m'1 є префіксним.
Щоб визначити ГПСЧ формально, ми повинні вказати функцію шифрування e (h) з повним вихідним матеріалом, що відображає послідовність запитів подачі і прийняття. Вихід е (h) використовується в якості входу для функції губки.
На практиці ідея полягає в тому, щоб не викликати функцію губки з усією е (h) кожен раз, як отримуємо запит прийняття. Замість цього, конструкція використовує функцію губки каскадним чином, повторно використовуючи стан, як описано в розділі 3.2. Щоб дозволити повторне використання стану функції губки е (h) повинна бути такою, що якщо h '= h || fetch (l) || feed (σ), то p (e (h)) || 0 r (⌈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 (σ):
Потім «всотується» σ. Формально це виражається шляхом додавання σ до е.
Нарешті, виконання перемикає функцію губки на фазу «вичавлювання». Це означає, що «ввібрані» дані повинна бути заповнені і перестановка f застосована до стану. (Формально, це не змінює е, так як заповнення за визначенням виконується при перемиканні на фазу віджимання).
Обмеження на фіксований розмір запитів подачі не є обов'язковим і може бути видалено. Для забезпечення змінної довжини вихідного матеріалу і збереження повноти вихідного матеріалу, повинні бути введені деякі форми заповнення всередині функції шифрування, щоб переконатися, що кордони вихідного матеріалу можуть бути ідентифіковані. Крім того, доведеться додати спосіб відрізняти блоки з нульовим початковим матеріалом від нульових блоків. Це може бути зроблено, наприклад, постановкою 1 в кожен блок, що містить вихідний матеріал.
Обмеження першого запиту, що є запитом подачі, може бути видалено, тому що не має сенсу генерувати псевдовипадкові біти без першої подачі вихідного матеріалу. Якщо перший запит - це прийняття, то виконання відразу заповнює (символом нового рядка) вхід, перемикає функції губки на фазу «вичавлювання» і виробляє вихідні біти за допомогою «вичавлювання». Формально в наступному запиті подачі, це повинно бути враховано в е привласненням е значення р (порожній рядок) || 0 r ([m = r] -1).