Криптосистемы с открытым ключом

Системы с открытым ключом названы так потому, что ключ, используемый при зашифровании данных, не является секретным и может быть, например, опубликован в средствах массовой информации. Также несекретным является алгоритм зашифрования. Защита данных обеспечивается тем, что для расшифрования необходим другой (секретный) ключ, причем он не может быть определен по открытому ключу зашифрования. Алгоритмы шифрования с открытым ключом называют поэтому несимметричными алгоритмами [20]. Наиболее известен метод шифрования с открытым ключом RSA.

Согласно методу RSA, для генерирования ключей необходимо выполнить следующие действия [18].

1. Выбрать два больших простых числа p и q.

2. Определить их произведение n = pq.

3. Выбрать число d, взаимно простое с числом (p - 1)(q - 1).

4. Определить число e, для которого выполняется условие

ed mod[(p - 1)(q - 1)] = 1.

5. Назвать открытым ключом числа e и n, а секретным ключом числа d и n.

Для применения полученных ключей открытое сообщение необходимо закодировать числами от 0 до n - 1. Каждое такое число M (i) зашифровывается при помощи открытого ключа по формуле

C (i) = [ M (i)] ^e mod(n). (23.4)

Для расшифрования используется формула с секретным ключом

M (i) = [ C (i)] ^d mod(n). (23.5)

Пример 23.1. Рассмотрим в качестве простого примера алгоритм RSA, основанный на очень малых числах p и q. Предположим, что шифрованию подлежит сообщение на русском языке [18]. Буквы сообщения можно представить числами от 0 до 32 (см. разд. 23.2).

Тогда за n можно принять число 33, а за простые числа p и q соответственно 3 и 11. Итак, согласно описанному алгоритму:

1) выберем два простых числа p = 3 и q = 11;

2) найдем n = 3 × 11 = 33;

3) за число d взаимно простое с числом (p - 1)(q - 1) = 20, примем число 3;

4) соотношению e ×3 mod(20) = 1 удовлетворяют числа 7, 27, 47,…, выберем e = 7.

Итак, открытым ключом для зашифрования является пара чисел e = 7 и n = 33, а закрытым (секретным) ключом для расшифрования – пара чисел d = 3 и n = 33.

Зашифруем слово ДОМ. Буквам Д, О и М соответствуют числа 5, 15 и 13. Используя открытый ключ, получим на основании (23.4) криптограмму, состоящую из чисел:

C ₁ = 5⁷ mod(33) = 78125 mod(33) = 14;

C ₂ = 15⁷ mod(33) = 170859375 mod(33) = 27;

C ₃ = 13⁷ mod(33) = 62748517 mod(33) = 7.

Для расшифрования криптограммы {14, 27, 7} воспользуемся формулой (23.5) и секретным ключом:

M ₁ = 14³ mod(33) = 2744 mod(33) = 5;

M ₂ = 27³ mod(33) = 19683 mod(33) = 15;

M ₃ = 7³ mod(33) = 343 mod(33) = 13.

Легко видеть, что в результате расшифрования получилось исходное открытое сообщение ДОМ. Следует отметить, что на практике применяются настолько большие числа p и q, что, зная e и n (открытый ключ), невозможно найти d за приемлемое время, так как в настоящее время не только не известен достаточно эффективный (полиномиальный) алгоритм разложения большого числа на простые множители, но и сам вопрос о существовании таких алгоритмов (а следовательно, о возможности взлома систем с открытым ключом в будущем) остается открытым [18, 21]. Тем не менее нельзя исключить открытие в будущем эффективных алгоритмов определения делителей целых чисел (факторизации), вследствие чего метод шифрования с открытым ключом станет абсолютно бесполезным. Пока этого не произошло, метод RSA имеет важные преимущества перед другими криптосистемами, такие как очень высокая криптостойкость и простота аппаратной и программной реализации.

Дата добавления: 2015-10-28