Криптосистема Гольдвассер — Микали

Криптосистема Гольдвассер — Микали (GM) — криптографическая система с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое понятие семантической стойкости.

Гольдвассер и Микали стали лауреатами Премии Тьюринга за 2012 год, создание криптосистемы с вероятностным шифрованием отмечено в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию.

Понятие стойкости по отношению к атаке IND-CPA впервые было предложено Голдвассер и Микали. Они назвали это понятие семантической стойкостью. Оно заключается в том, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте (если не считать полезной информацией длину самого исходного текста) ни одному взломщику, обладающему полиномиально ограниченными вычислительными ресурсами. Голдвассер и Микали обнаружили, что во многих приложениях сообщения могут содержать априорную информацию, полезную для организации атак. Например, зашифрованный текст может содержать только одну простую инструкцию (например, «покупать» или «продавать», либо имя одного из нескольких кандидатов при голосовании). Голдвассер и Микали указали на то, что криптосистемы с открытым ключом, основанные на непосредственном применении односторонних функций с секретом, как правило, очень слабо скрывают содержание таких сообщений.

Свойство (семантическая стойкость). Все элементы открытого текста, которые можно эффективно вычислить по заданному зашифрованному тексту, можно эффективно вычислить и без него.

Гольдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Она шифрует всё сообщение бит за битом, причём вся сложность, связанная с поиском отдельного зашифрованного бита в тексте c, заключается в проверке, принадлежит число c множеству ${\displaystyle QR_{N}}$ или множеству ${\displaystyle J(N)=\left\{x\in \mathbb {Z} _{N}^{\ast },\left({\frac {x}{N}}\right)=1\right\}}$

Чтобы установить параметры ключа, Алиса должна выполнить следующие операции :

1. Выбрать два случайных числа ${\displaystyle p}$ и ${\displaystyle q}$, удовлетворяющих условию ${\displaystyle |p|=|q|}$ бит
2. Вычислить значение ${\displaystyle N=pq}$
3. Извлечь случайное целое число ${\displaystyle y}$, удовлетворяющее условию (символы Якоби) ${\displaystyle \left({\frac {y}{p}}\right)=\left({\frac {y}{q}}\right)=-1}$
   (Таким образом, ${\displaystyle y\in J(N)}$, но ${\displaystyle y\notin QR_{N}}$.)
4. Описать пару ${\displaystyle (N,y)}$ в качестве открытого ключа, а пару ${\displaystyle (p,q)}$ сохранить в тайне как закрытый ключ.

Чтобы послать Алисе строку ${\displaystyle m=b_{1}b_{2}\dots b_{l}}$, Боб выполняет следующие операции:
${\displaystyle for(i=1,2\dots ,l)}$

{
${\displaystyle \quad x\leftarrow _{U}\mathbb {Z} _{N}^{\ast };}$
${\displaystyle \quad if\,(b_{i}==0)\,\,c_{i}\leftarrow x^{2}(mod\,N);}$
${\displaystyle \quad else\ c_{i}\leftarrow yx^{2}(mod\,N);}$
}

Боб посылает Алисе сообщение ${\displaystyle E_{N}(m)\leftarrow (c_{1},c_{2}\dots ,c_{l}).}$

Получив кортеж ${\displaystyle (c_{1},c_{2},\dots ,c_{l})}$, Алиса выполняет следующие операции:
${\displaystyle for(i=1,2\dots ,l)}$

{

${\displaystyle \quad if\,(c_{i}\in QR_{N})\,\,b_{i}\leftarrow 0;}$
${\displaystyle \quad b_{i}\leftarrow 1;}$

}

${\displaystyle set\ m\leftarrow (b_{1},b_{2},\dots ,b_{l}).}$

Для шифрования сообщения, состоящего из ${\displaystyle l}$ бит, необходимо выполнить ${\displaystyle O(l(\log _{2}N)^{2})}$ побитовых операций. Это выражение представляет собой оценку временной сложности алгоритма. Степень расширения этого алгоритма равна ${\displaystyle \log _{2}N}$:одному биту исходного текста соответствуют ${\displaystyle \log _{2}N}$ бит зашифрованного текста.
Поскольку для вычисления символа Лежандра по модулю ${\displaystyle p}$ и по модулю ${\displaystyle q}$ при условии, что ${\displaystyle |p|=|q|=k}$ необходимо выполнить ${\displaystyle O_{B}(k^{2})}$ побитовых операций, для расшифровки кортежа ${\displaystyle (c_{1},c_{2},\dots c_{k})}$ требуются ${\displaystyle O_{B}((\log _{2}N)^{2})}$ побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.

Алгоритм шифрования в криптосистеме GM можно рассматривать как безошибочный рандомизированный алгоритм: случайные операции в алгоритме шифрования не могут исказить зашифрованный текст и обладают при этом следующими важными свойствами.

Нулевые биты в исходном тексте равномерно распределяются по множеству ${\displaystyle QR_{N}}$, а единичные — по множеству ${\displaystyle J_{N}\backslash QR_{N}}$.
Оба распределения являются равномерными, поскольку для нулевого бита, содержащегося в исходном тексте, возведение в квадрат означает отображение группы ${\displaystyle \mathbb {Z} _{N}^{\ast }}$ на множестве ${\displaystyle QR_{N}}$, а для единичного бита умножение элемента множества ${\displaystyle QR_{N}}$ на число ${\displaystyle y}$ является отображением из множества ${\displaystyle QR_{N}}$ на множество ${\displaystyle J_{N}\backslash QR_{N}}$.

• Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6