Криптосистема Голдвассера-Микали
Генерирование ключей
1)генерируем два больших простых числа р и q, состоящих из β бит,
2)вычисляем N = pq ,
|
|
y |
|
|
|
3) Выбираем |
y QN и |
|
|
=1 |
, |
|
|||||
|
N |
|
|||
то есть, y |
является псевдоквадратом по модулю N), |
||||
4) Открытый ключ (N,y) , закрытый (p,q).
шифрование
Для того , чтобы отправить сообщение корреспонденту. А корреспондент. В выполняет:
1.Получает от А открытый ключ (N,y),
2.Представляет сообщение m вc виде битовой строки
|
m = m1,m2, ,mk, |
длиной k, |
|
|
|
|
|
|
|
||
3. Для i от 1 до k выполняет: |
|
|
|
, |
N |
{ |
N |
} |
|||
- |
выбирает случайным образом xi ( ZN ) |
||||||||||
|
|
|
|
|
|
• |
Z |
= a Z |
|
: НОД(a,N)=1 |
|
мультипликативная группа, |
|
|
|
|
|
|
|
|
|||
- |
вычисляет |
2 |
mod |
N , если mi |
= 0, |
|
, |
|
|
|
|
xi |
|
|
|
|
|||||||
|
|
ci = |
|
|
|
=1 |
|
|
|
|
|
|
|
yx2 mod N , если m |
i |
|
|
|
|
|
|||
|
|
|
i |
|
|
|
|
|
|
|
|
в первом случае получаем квадрат, а во втором псевдоквадрат по модулю N,
4. Посылает c = c1,c2, ,ck, корр. А. (Размер криптограммы
k( 2β )
Расшифрование
Корр. А выполняет следующие действия: |
ei′ = ci , |
|||||||||
1. |
Для i от 1 до k вычисляет символ Лежандра: |
|||||||||
2. |
Вычисляет |
mi |
|
|
|
|
|
p |
||
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
' |
|
|
|
|
|
m |
|
|
|
|
0, если ei =1 |
|
||
|
|
i |
= |
|
|
|
|
|||
|
|
|
|
|
|
|||||
|
|
|
|
1, в противном случае |
|
|||||
то есть, mi = 0 |
если |
|
|
(вычет) , mi =1 в противном случае, |
||||||
ci |
QN |
|||||||||
|
|
|
|
|
|
|
|
|||
3. Выводит расшифрованное сообщение m = m1,m2, ,mk,
Криптостойкость КС Голдвассера-Микали
•Данный алгоритм использует при шифровании псевдослучайные числа и основывается на вычислительной неразрешимости задачи о квадратичном вычете.
•Данный алгоритм вероятностного шифрования обеспечивает семантическую безопасность.
•Недостаток – существенное увеличение длины криптограммы
• ( в 2β раз, где β - количество разрядов в числах p и q).
Таким образом, для КС Диффи–Хеллмана, так же как и для всех КС ОК, необходимо обеспечивать подлинность открытых данных (т. е. обеспечитьрешениезадачаутентификации).
КСЭль-Гамаля
Это некоторая модификация КС РША, стойкость которой не связана непосредственно с проблемой факторизации. Она широко используется в стандартах цифровой подписи и допускает естественное обобщение на случайКС, построенныхнаосновеиспользованияэллиптическихкривых, чтобудетрассмотренодалее.
Генерированиеключей
Пользователь А проделываетследующиеоперациидлягенерирования ключей:
1) генерируетпростоечисло p ипримитивныйэлемент α GF(p);
2)выбираетслучайноечисло a такое, что 1 ≤ a ≤ p −2 , ивычисляетчисло
αa;
3)вкачествеоткрытогоключавыбираетнабор: (p, α, αa mod p), ав качествезакрытогоключа – число a.
Шифрование
Пользователь В выполняет следующие шаги для шифрования сообщения M, предназначенногопользователю А:
1)получаетоткрытыйключ A;
2)представляетсообщение M ввидецепочкичисел Mi , каждоеиз которыхнепревосходит p −1 ;
3)выбираетслучайноечисло k такое, что 1 ≤ k ≤ p −2;
4) вычисляет |
γ = αk mod p |
, |
δ = |
Mi |
αa |
) |
k |
mod p ; |
|
|
( |
|
5) посылаеткриптограмму C = (γ,δ) пользователю А.
Дешифрование
Пользователь A выполняет следующие шаги для дешифрования сообщения, полученногоотпользователя B:
1)используясвойзакрытыйключ, вычисляет γ−a mod p ;
2)восстанавливаетсообщение Mi = γ−aδmod p .
Действительно γ−aδ = α−ak Miαak = Mi mod p .
Особенностью схемы Эль-Гамаля является то, что она относится к такназываемымсхемам рандомизационногошифрования, посколькупри шифровании в ней используется дополнительная случайность в виде числа k.
(Считается, что рандомизационное шифрование более стойко по отношению к некоторым методам криптоанализа, например к таким как статистическиеатаки [3].)