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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптосистема Голдвассера-Микали - Описание алгоритма

23 января 2011

Оглавление:
1. Криптосистема Голдвассера-Микали
2. Описание алгоритма
3. Стойкость криптосистемы GM

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

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

Выбрать два случайных числа $~p$ и $~q$ , удовлетворяющих условию $~|p| = |q|$ бит
Вычислить значение $~N = pq$
Извлечь случайное целое число y удовлетворяющее условию $\left = \left = -1$
\mathcal {n}QR_N" src="http://upload.wikimedia.org/math/8/d/4/8d4f1b7b6f5bbca37fb4989580856db2.png" />.*)
Описать пару $~$ в качестве открытого ключа, а пару $~$ сохранить в тайне как закрытый ключ.

Шифрование

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

{

$x \leftarrow _U \Z^\ast_N ;$
$ifc_i \leftarrow x^2;$
$else \ c_i \leftarrow yx^2;$

}

Боб посылает Алисе сообщение $E_N \leftarrow.$

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

Получив кортеж $\text{[math]}$ , Алиса выполняет следующие операции:
$for$

{

$if b_i \leftarrow 0;$
$b_i \leftarrow 1 ;$

}

$set \ m \leftarrow.$

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

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

<<< Закрытый ключ

Самозаверенный сертификат >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие