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

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

Основы

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

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

Голдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Изобретенная ими схема называется криптосистемой GM. Она шифрует все сообщение бит за битом, причем вся сложность, связанная с поиском отдельного зашифрованного бита в тексте c, заключается в проверке, принадлежит число c множеству $~QR_N$ или множеству $~J=\{x\in \Z^\ast_N , \left ( \frac{x}{N} \right )\}$

Описание алгоритма

Генерация ключа

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

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

Шифрование

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

{

$x \leftarrow _U \Z^\ast_N ;$
$if(b_i==0)c_i \leftarrow x^2(mod N);$
$else \ c_i \leftarrow yx^2(mod N);$

}

Боб посылает Алисе сообщение $E_N(m) \leftarrow (c_1,c_2 \dots ,c_l).$

Дешифрование

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

{

$if(c_i \in QR_N) b_i \leftarrow 0;$
$b_i \leftarrow 1 ;$

}

$set \ m \leftarrow (b_1,b_2,\dots,b_l).$

Временная сложность алгоритма

Для шифрования сообщения, состоящего из l бит, необходимо выполнить O(l(log ₂N)²) побитовых операций.Это выражение представляет собой оценку временной сложности алгоритма.Степень расширения этого алгоритма равна log ₂N:одному биту исходного текста соответствуют log ₂N бит зашифрованного текста.
Поскольку для вычисления символа Лежандра по модулю p и по модулю q при условии, что | p | = | q | = k необходимо выполнить O_B(k²) побитовых операций, для расшифровки кортежа $(c_1,c_2,\dots c_k)$ требуются O_B((log ₂N)²) побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.

Стойкость криптосистемы GM

Алгоритм шифрования в криптосистемы GM можно рассматривать как безошибочный рандомизированный алгоритм: случайные операции в алгоритме шифрования не могут исказить зашифрованный текст и обладают при этом следующими важными свойством.
Нулевые биты в исходном тексте равномерно распределяются по множеству QR_N, а единичные - по множеству $J_N(1)\backslash QR_N$.
Оба распределения являются равномерными, поскольку для нулевого бита, содержащегося в исходном тексте, возведение в квадрат означает отображение группы $\Z_N^\ast$ на множестве QR_N, а для единичного бита умножение элемента множества QR_N на число y является отоброжением из множества QR_N на множество $J_N(1)\backslash QR_N$.

Список литературы

• Вэнбо Мао Современная Криптография. Теория и Практика. — Спб.: Вильямс, 2005.