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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Основы[править | править вики-текст]

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

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

Гольдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Она шифрует всё сообщение бит за битом, причём вся сложность, связанная с поиском отдельного зашифрованного бита в тексте 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_2N)^2) побитовых операций. Это выражение представляет собой оценку временной сложности алгоритма. Степень расширения этого алгоритма равна \log_2N:одному биту исходного текста соответствуют \log_2N бит зашифрованного текста.
Поскольку для вычисления символа Лежандра по модулю p и по модулю q при условии, что |p|=|q|=k необходимо выполнить O_B(k^2) побитовых операций, для расшифровки кортежа (c_1,c_2,\dots c_k) требуются O_B((\log_2N)^2) побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.

Стойкость криптосистемы 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.