НОУ ИНТУИТ | Лекция | Криптосистемы
< Лекция 15 || Лекция 15: 1234567
Аннотация: В этой лекции рассматриваются несколько асимметрично-ключевых криптографических систем: Рабина (Rabin), Эль-Гамаля (ElGamal), криптосистемa на основе метода эллиптических кривых (ECC — Elliptic Curve Cryptosystem).
Ключевые слова: криптосистема, RSA, шифрование, дешифрование, открытый ключ, секретный ключ, кортеж, генерация ключей, интегральная схема, вычет, получатель сообщения, криптографическая система, дискретный логарифм, первообразный корень, инверсия, безопасность, curve, cryptosystem, ECC, эллиптические кривые, псевдокод, полином, симметричный ключ, математическая функция, односторонняя функция, коммутативность, первообразная
15.1. Криптосистема Рабина
Криптосистема Рабина (М. Rabin) является вариантом криптосистемы RSА. RSА базируется на возведении в степень сравнений. Криптосистема Рабина базируется на квадратичных сравнениях, и ее можно представить как криптографическую систему RSA, в которой значениям e и d присвоены значения e = 2 и d = 1/2.
Другими словами, шифрование — и дешифрование — P = C1/2 (mod n).
Открытый ключ доступа в криптосистеме Рабина — n, секретный ключ является кортежем (p, q). Каждый может зашифровать сообщение, используя n, но только Боб может расшифровать сообщение, используя p и q. Дешифрование сообщения неосуществимо для Евы, потому что она не знает значения p и q. Рисунок 15.1 показывает шифрование и дешифрование.
Рис. 15.1. Шифрование, дешифрование и генерация ключей в криптосистеме Рабина
Мы должны подчеркнуть, что если Боб использует RSA, он может сохранить d и n и отказаться после генерации ключей от p, q и . Если Боб использует криптосистему Рабина, он должен сохранить p и q.
Процедура
Генерация ключей, шифрование и дешифрование показаны ниже.
Генерация ключей
Боб использует шаги, показанные в алгоритме 15.1, чтобы создать свой открытый ключ доступа и секретный ключ.
15.1. Генерации ключей для криптосистемы Рабина
Хотя два простых числа, p и q, могут быть в форме 4k + 1 или 4k + 3, процесс дешифрования становится более трудным, если используется первая форма. Рекомендуют применять вторую форму, 4k + 3, для того чтобы сделать дешифрование для Алисы намного проще.
Шифрование
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан алгоритмом 15.2.
Rabin_Encryption (n, P) // n — открытый ключ доступа;
P — зашифрованный текст Z*n
{
C <- P2 mod n // C — зашифрованный текст
return C
} 15.
2.
Шифрование в криптографической системе Рабина
Хотя исходный текст P может быть выбран из множества Zn, но чтобы сделать дешифрование более простым, мы определили множество, которое находится в Zn*.
Шифрование в криптосистеме Рабина очень простое. Операция нуждается только в одном умножении, что может быть сделано быстро. Это выгодно, когда ресурсы ограничены: например, при использовании карт с интегральной схемой, содержащей микропроцессор с ограниченной памятью, и при необходимости задействовать центральный процессор на короткое время.
Дешифрование
Боб может использовать алгоритм 15.3, чтобы расшифровать полученный зашифрованный текст.
Rabin_Decryption (p, q, C) // C — зашифрованный текст; p и q — секретные ключи a1 <- + (C(p+1)/4) mod p a2 <- - (C(p+1)/4) mod p b1 <- + (C(q+1)/4) mod q b2 <- - (C(q+1)/4) mod q // Алгоритм китайской теоремы об остатках вызывается четыре раза.P1 <- Китайский_остаток (a1, b1, p, q) P2 <- Китайский_остаток (a1, b2, p, q) P3 <- Китайский_остаток (a2, b1, p, q) P4 <- Китайский_остаток (a 2, b2, p, q) return P1, P2, P3 и P4
P1 <- Китайский_остаток (a1, b1, p, q)
P2 <- Китайский_остаток (a1, b2, p, q)
P3 <- Китайский_остаток (a2, b1, p, q)
P4 <- Китайский_остаток (a 2, b2, p, q)
return P1, P2, P3 и P415.3. Дешифрование в криптосистеме Рабина
Мы должны подчеркнуть здесь несколько моментов. Дешифрация базируется на решении квадратичного сравнения, которое рассмотрено в лекциях 12-13. Поскольку полученный зашифрованный текст — квадрат исходного текста, это гарантирует, что C имеет корни (квадратичные вычеты) в Zn*. Алгоритм китайской теоремы об остатке используется, чтобы найти четыре квадратных корня.
Самый важный пункт в криптосистеме Рабина — это то, что она недетерминирована.
Дешифрование имеет четыре ответа. Задача получателя сообщения — точно выбрать один из четырех ответов как конечный ответ. Однако во многих ситуациях получатель может легко выбрать правильный ответ.
Криптосистема Рабина не детерминирована — дешифрование создает четыре одинаково вероятных исходных текста.
Пример 15.1
Вот очень тривиальный пример, чтобы проиллюстрировать идею.
1. Боб выбирает p = 23 и q = 7. Обратите внимание, что оба являются сравнениями 3 mod 4.
2. Боб вычисляет .
3. Боб объявляет n открытым и сохраняет p и q в секрете.
4. Алиса хочет передать исходный текст P = 24. Обратите внимание, что 161 и 24 являются взаимно простыми; 24 находится в Z161*. Она вычисляет C = от 242 = 93 mod 161 и передает зашифрованный текст 93 Бобу.
5. Боб получает 93 и вычисляет четыре значения:
а. a1 = + (93 (23+1)/4) mod 23 = 1 mod 23
b. a2 = – (93 (23+1)/4) mod 23 = 22 mod 23
с. b 1 = + (93 (7+1)/4) mod 7 = 4 mod 7
d. b2 = – (93 (7+l)/4) mod 7 = 3 mod 7
- Боб имеет четыре возможных ответа — (a1, b 1), (a1, b2),
- (a2, b 1), (a2, b2) и использует китайскую теорему об остатках, чтобы найти четыре возможных исходных текста: 116, 24, 137 и 45 (все из них взаимно простые к 161 ). Обратите внимание, что только второй ответ — исходный текст Алисы.
