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

Системы с открытым ключом названы так потому, что ключ, используемый при зашифровании данных, не является секретным и может быть, например, опубликован в средствах массовой информации. Также несекретным является алгоритм зашифрования. Защита данных обеспечивается тем, что для расшифрования необходим другой (секретный) ключ, причем он не может быть определен по открытому ключу зашифрования. Алгоритмы шифрования с открытым ключом называют поэтому несимметричными алгоритмами [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)

Пример. Рассмотрим в качестве простого примера алгоритм 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 имеет важные преимущества перед другими криптосистемами, такие как очень высокая криптостойкость и простота аппаратной и программной реализации.

Цифровая подпись

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

При передаче секретных документов (военного или дипломатического содержания) весьма вероятным является перехват документа противником, который может либо создать и переслать вместо него подложный документ, либо изменить содержимое документа законного источника. Чтобы обнаружить подмену, в зашифрованное сообщение встраивается так называемая имитовставка, которая представляет собой последовательность, полученную по определенному алгоритму на основе всего текста открытого сообщения. Получатель после расшифрования криптограммы подвергает полученный открытый текст повторной обработке тем же алгоритмом и сравнивает полученную имитовставку с принятой. Если совпадения нет, принятое сообщение считается ложным.

Совершенно другая ситуация может иметь место при обмене информацией коммерческого характера. Здесь возможна ситуация, когда партнеры по информационному обмену не доверяют друг другу и являются в каком-то смысле противниками. Один из партнеров может изготовить документ, зашифровать его и заявить, что получил его от партнера.

Для такого случая необходимо применять схему шифрования следующего вида. Передающий абонент зашифровывает подпись с помощью своего секретного ключа, а получатель расшифровывает ее своим несекретным ключом. Несекретный ключ может представлять собой набор проверочных соотношений, позволяющих установить подлинность подписи, но не восстановить секретный ключ. Таким образом, никто, кроме законного автора документа, не в состоянии сгенерировать правильную подпись.

ЛИТЕРАТУРА

1. Котельников В. А. О пропускной способности «эфира» и проволоки в электросвязи [Текст] / в кн. Материалы по радиосвязи к I Всесоюзному съезду по вопросам технической реконструкции связи [Текст]. – М.: Всесоюзный энергетический комитет, 1933.

2. Теория электрической связи [Текст] / Зюко А. Г., Кловский Д. Д., Коржик В. И. Назаров М.В.; под ред. Д. Д. Кловского. – М.: Радио и связь, 1999. – 432 с.

3. Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся втузов [Текст]: 13-е изд., исправленное. – М..: Наука, Гл. ред. физ.-мат. лит., 1986. – 544 с.

4. Борисов В. А., Калмыков В. В., Ковальчук Я. М. Радиотехнические системы передачи информации [Текст]; под ред. В. В. Калмыкова. – М.: Радио и связи, 1990. – 304 с.

5. Панфилов И. П., Дырда В. Е. Теория электрической связи [Текст]. – М.: Радио и связь, 1991. – 344 с.

6. Теплов Н. Л. Теория передачи сигналов по электрическим каналам связи [Текст]. – М.: МО СССР, 1976. – 424 с.

7. Оппенгейм А. В., Шафер Р. В. Цифровая обработка сигналов [Текст] – М.: Связь, 1979. – 416 с.

8. Баскаков С. И. Радиотехнические цепи и сигналы [Текст]. – М.: Высш. шк., 2002. – 448 с.

9. Кловский Д. Д., Конторович В. Я., Широков С. М. Модели непрерывных каналов связи на основе стохастических дифференциальных уравнений [Текст]. – М.: Радио и связь, 1984. – 248 с.

10. Волков Л. Н., Немировский М. С., Шинаков Ю. С. Системы цифровой радиосвязи: базовые методы и характеристики [Текст]: учебное пособие. – М.: Эко-Трендз, 2005. – 392 с.

11. Голяницкий, И. А., Громакова Ю. А. Математические модели и методы в радиосвязи [Текст] / под ред. Громакова Ю. А. – М.: Эко-Трендз, 2005. – 440 с.

12. Тихонов В. И., Миронов М. А. Марковские процессы [Текст]. – М.: Советское радио, 1977. – 488 с.

13. Котельников В.А. Теория потенциальной помехоустойчивости [Текст]. – М.: Госэнергоиздат, 1956. – 152 с.

14. Уидроу Б.,Стринз С. Адаптивная обработка сигналов [Текст]: пер. с англ. – М.: Радио и связь, 1989. – 440 с.

15. Васюков В.Н. Теория электрической связи: учебник [Текст]. – Новосибирск.: Изд-во НГТУ, 2005. – 392 с.

16. Черенкова Е.Л., Чернышев О.В. Распространение радиоволн [Текст]. – М.: Радио и связь, 1984. – 271 с.

17. Ященко В.В. Основные понятия криптографии [Текст]: Математическое просвещение: сер. 3: вып. 2. – 1998. – С. 53–70.

18. Петраков А.В. Основы практической защиты информации [Текст]. – М.: Радио и связь, 2000. – 368 с.

19. Шеннон К. Теория связи в секретных системах [Текст] / Работы по теории информации и кибернетике. – М.: ИЛ, 1963. – 830 с.

20. Брассар Ж. Современная криптология [Текст]. – М.: Изд. полиграф. фирма ПОЛИМЕД, 1999. – 176 с.

21. Введение в криптографию / Под общ. ред. В. В. Ященко [Текст]. – М.: МЦНМО, 2000. – 272 с.