Geum.ru

«Информатика»

Вид материалаУчебное пособие

Содержание


Криптографические средства защиты
F(N) и взаимно простое с ним, например, k=3
Подобный материал:
1   ...   21   22   23   24   25   26   27   28   ...   39

Криптографические средства защиты


Необходимы идентификация (определение «кто это» – группы и, возможно, имени для выяснения на какие действия он имеет право) и аутентификация (проверка подлинности, действительно ли «он это он») пользователя.

Например, при входе в систему пользователь вводит свое имя (идентификация) и пароль (аутентификация). В банкоматах: идентификация – ввод карточки, аутентификация – набор PIN (PersonaI Identification Number) кода. Могут использоваться токены – физические ключи или магнитные карты, которые пользователь вставляет в считывающее устройство (token – опознавательный знак).

Для шифрования используются методы криптографии, для вскрытия (взлома) зашифрованных данных – методы криптоанализа.

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

Традиционные методы шифрования (симметричное шифрование, шифрование с одним ключом, шифрование с закрытым ключом) – составитель и получатель сообщения знают секретный ключ (большое двоичное число), который используют для шифровки и расшифровки текста.

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

Наиболее распространен стандарт (алгоритм) симметричного шифрования DES (Data Encryption Standard), использующий 56-битовый закрытый ключ (реальная длина ключа 64 бита за счет информации для контроля) и опубликованный в 1977 году. При шифровании используются 16 проходов текста так, что каждый бит блока зашифрованного текста зависит от каждого бита блока исходного текста и каждого бита ключа.

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

Ассиметричные системы шифрования (нетрадиционные системы, шифрование с двумя ключами, шифрование с открытым ключом) – будущий получатель сообщения создает два ключа: закрытый (секретный), который сохраняет только у себя и открытый, который по любому каналу, не скрывая, передает будущему отправителю. Зашифрованное отправителем с помощью открытого ключа сообщение нельзя расшифровать, не зная закрытый ключ.

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

Наиболее широко применяется для шифрования с открытым ключом алгоритм (система) RSA (по фамилиям авторов – Rivest, Shamir, Adleman), предложенный в 1978 году.

Алгоритмы ассиметричного шифрования требуют значительно больших затрат машинного времени. Поэтому используются комбинированное (гибридное) шифрование с созданием электронного цифрового конверта RSA (RSA digital envelope) – пользователь создает секретный ключ, шифрует им все большое сообщение по DES, сам (относительно короткий) секретный ключ шифрует своим открытым ключом по RSA и отправляет адресату в одном пакете. Получатель своим секретным ключом по RSA расшифровывает секретный ключ отправителя, а с его помощью по DES основное сообщение. При использовании открытого ключа (в том числе цифровых конвертов), доступного посторонним, имеется опасность фальсификации – отправки сообщения третьим лицом от имени пользователя.

Упрощенная иллюстрация ассиметричного шифрования алгоритмом RSA.

1)Задаемся двумя простыми числами, например, a=2, b=5*.

2)Находим их произведение N=2*5=10.

3)Находим функцию Эйлера F(N), равную количеству положительных чисел, не превосходящих N и взаимно простых с N (то есть не имеющих общих простых делителей с N). Оказывается, что при получении N по использованному правилу, F(N)= (a-1)*(b-1)=(2-1)*(5-1)=4.

4)Выбираем любое целое положительное число k, меньшее F(N) и взаимно простое с ним, например, k=3.

5)Числа N и k образуют открытый ключ и могут быть опубликованы.

6)Секретный ключ определяем как любое целое положительное число s, отвечающее условию (k*s)mod F(N) =1. В нашем примере требуется (3*s)mod 4 =1 и можно взять s=7.

7)Пусть теперь нужно зашифровать текст, представленный числом t=8.** Код этого числа c определяется по правилу c=(tk)mod N.

У нас c=(83)mod 10=(512)mod 10=2.

8)Оказывается, что, зная код c и секретный ключ s, легко восстановить исходный текст по правилу t=(cs)mod N. У нас t=(27)mod 10 = (128)mod 10 = 8, что соответствует действительности.

Лицо, не знающее секретный ключ s, может расшифровать его только рассчитав функцию Эйлера F(N), а затем решив уравнение (k*s)mod F(N) =1. Мы легко нашли F(N) по известной формуле, так как заранее знали простые числа a и b, образовавшие N. По современным представлениям, зная только N, восстановить a и b можно лишь алгоритмом перебора, требующем, при большом N, нереально больших затрат машинного времени.