Русская Википедия:Криптосистема Гольдвассер — Микали
Криптосистема Гольдвассер — Микали (GM) — криптографическая система с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое понятие семантической стойкости.
Гольдвассер и Микали стали лауреатами Премии Тьюринга за 2012 год, создание криптосистемы с вероятностным шифрованием отмечено в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию.
Основы
Понятие стойкости по отношению к атаке IND-CPA впервые было предложено Голдвассер и Микали. Они назвали это понятие семантической стойкостью. Оно заключается в том, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте (если не считать полезной информацией длину самого исходного текста) ни одному взломщику, обладающему полиномиально ограниченными вычислительными ресурсами. Голдвассер и Микали обнаружили, что во многих приложениях сообщения могут содержать априорную информацию, полезную для организации атак. Например, зашифрованный текст может содержать только одну простую инструкцию (например, «покупать» или «продавать», либо имя одного из нескольких кандидатов при голосовании). Голдвассер и Микали указали на то, что криптосистемы с открытым ключом, основанные на непосредственном применении односторонних функций с секретом, как правило, очень слабо скрывают содержание таких сообщений.
Свойство (семантическая стойкость). Все элементы открытого текста, которые можно эффективно вычислить по заданному зашифрованному тексту, можно эффективно вычислить и без него.
Гольдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Она шифрует всё сообщение бит за битом, причём вся сложность, связанная с поиском отдельного зашифрованного бита в тексте c, заключается в проверке, принадлежит число c множеству <math>QR_N</math> или множеству <math>J(N)=\left\{x\in \Z^\ast_N , \left ( \frac{x}{N} \right )=1\right\}</math>
Описание алгоритма
Генерация ключа
Чтобы установить параметры ключа, Алиса должна выполнить следующие операции :
- Выбрать два случайных числа <math>p</math> и <math>q</math>, удовлетворяющих условию <math>|p| = |q|</math> бит
- Вычислить значение <math>N = pq</math>
- Извлечь случайное целое число <math>y</math>, удовлетворяющее условию (символы Якоби) <math>\left ( \frac{y}{p} \right ) = \left ( \frac{y}{q} \right ) = -1</math>
(Таким образом, <math>y\in J(N)</math>, но <math>y \notin QR_N</math>.) - Описать пару <math>(N,y)</math> в качестве открытого ключа, а пару <math>(p,q)</math> сохранить в тайне как закрытый ключ.
Шифрование
Чтобы послать Алисе строку <math>m=b_1b_2\dots b_l</math>, Боб выполняет следующие операции:
<math>for(i=1,2 \dots, l)</math>
{
<math> \quad x \leftarrow _U \Z^\ast_N ;</math>
<math> \quad if\,(b_i==0)\,\,c_i \leftarrow x^2(mod \,N);</math>
<math>\quad else \ c_i \leftarrow yx^2(mod\, N);</math>
}
Боб посылает Алисе сообщение <math>E_N(m) \leftarrow (c_1,c_2 \dots ,c_l).</math>
Расшифрование
Получив кортеж <math>(c_1,c_2,\dots,c_l)</math>, Алиса выполняет следующие операции:
<math>for(i=1,2 \dots, l)</math>
{
<math> \quad if\, (c_i \in QR_N)\,\, b_i \leftarrow 0;</math>
<math>\quad b_i \leftarrow 1 ;</math>
}
<math>set \ m \leftarrow (b_1,b_2,\dots,b_l).</math>
Временная сложность алгоритма
Для шифрования сообщения, состоящего из <math>l</math> бит, необходимо выполнить <math>O(l(\log_2N)^2)</math> побитовых операций. Это выражение представляет собой оценку временной сложности алгоритма. Степень расширения этого алгоритма равна <math>\log_2N</math>:одному биту исходного текста соответствуют <math>\log_2N</math> бит зашифрованного текста.
Поскольку для вычисления символа Лежандра по модулю <math>p</math> и по модулю <math>q</math> при условии, что <math>|p|=|q|=k</math> необходимо выполнить <math>O_B(k^2)</math> побитовых операций, для расшифровки кортежа <math>(c_1,c_2,\dots c_k)</math> требуются <math>O_B((\log_2N)^2)</math> побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.
Стойкость криптосистемы GM
Алгоритм шифрования в криптосистеме GM можно рассматривать как безошибочный рандомизированный алгоритм: случайные операции в алгоритме шифрования не могут исказить зашифрованный текст и обладают при этом следующими важными свойствами.
Нулевые биты в исходном тексте равномерно распределяются по множеству <math>QR_N</math>, а единичные — по множеству <math>J_N \backslash QR_N</math>.
Оба распределения являются равномерными, поскольку для нулевого бита, содержащегося в исходном тексте, возведение в квадрат означает отображение группы <math>\Z_N^\ast</math> на множестве <math>QR_N</math>, а для единичного бита умножение элемента множества <math>QR_N</math> на число <math>y</math> является отображением из множества <math>QR_N</math> на множество <math>J_N \backslash QR_N</math>.
Список литературы
Шаблон:Криптосистемы с открытым ключом
