Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика 2015

10.4. Криптографическая система с открытым ключом

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

Дэн Браун

Алгоритмы шифрования с открытым ключом (асимметричные шифры) используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента X относительно просто вычислить значение функции f(x). Однако если известно значение функции у = f(x), то нет простого пути для вычисления значения аргумента X.

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

  • 1. Разложение больших чисел на простые множители (алгоритм RSA, авторы — Райвест, Шамир и Адлеман — Rivest, Shamir, Adleman).
  • 2. Вычисление логарифма или возведение в степень (алгоритм DH) авторы — Диффи и Хелман).
  • 3. Вычисление корней алгебраических уравнений.
  • 4. Эллиптические кривые.

Рассмотрим простейший пример «необратимых» функций. Легко в уме найти произведение двух простых чисел 11 и 13. Но попробуйте быстро в уме найти два простых числа, произведение которых равно 437. Подобные трудности возникают и при использовании вычислительной техники для отыскания двух простых сомножителей для очень большого числа: найти сомножители можно, но потребуется много времени.

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

Заметим, что операцию разложения числа на множители называют факторизацией.

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

В 40-х г одах XX в. американский инженер и математик Клод Шеннон предложил разрабатывать шифр таким образом, чтобы его раскрытие было эквивалентно решению сложной математической задачи. Причём, сложность задачи должна быть такой, чтобы объем необходимых вычислений превосходил бы возможности современных ЭВМ.

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

Алгоритм шифрования RSA разработали Rivest, Shamir, Adleman.

Опишем пример использования такой системы (см. таблицу).

Пусть абонент А (например, банкир) и абонент В (например, вкладчик) решили организовать между собой секретную передачу информации.

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

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

Действия

Абонент А (банкир)

Абонент В (вкладчик)

1. Выбор двух простых чисел р и q

р=7; q = 13

р = 11; q = 23

2. Вычисление произведения г = p-Q

г — 7-13 = 91

г = 11-23 = 253

3. Расчет функции Эйлера <р(г) = r-p-q+1

К

в

ИГ

(р{г) = 220

4. Выбор случайного числа S, взаимно простого с <р(г) из интервала 0 < s < <р(г)

s = 5

s = 31

5. Расчет секретного

ключа t с помощью соотношения s-t = l(mod

5-t= 1 (mod (72)) t = 29

3U=l(mod(220)) t= 71

6. Публикация открытых ключей S, г

s = 5, г = 91

s = 31, г = 253

Порядок создания ключей иллюстрируется с помощью таблицы. Для наглядности числа выбраны малой величины. Фактически эти числа имеют около 100 десятичных разрядов.

Использованная в таблице запись а - /%mod(y)) означает, что при целочисленном делении числа а на число у остаток равен Д

Например, 7 = l(mod(3)).

Функция Эйлера — арифметическая функция <р(г), значение которой равно количеству положительных чисел, не превосходящих г и взаимно простых с г.

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

Абонент А шифрует число 2 открытым (опубликованным) ключом абонен та В. Для шифрования передаваемое число 2 возводится в степень S = 31, т. е.

Затем находит остаток от деления числа т на величину г = 253, в результате которою получается число 167, то есть:

Напомним, что числа S и г являются открытым ключом абонента В.

В линию передается число 167, которое является шифром исходного числа 2.

Получив шифрограмму (167), абонент В использует свой секретный ключ t = 71. Для дешифрации он возводит полученное число 167 в степень 71 и находит остаток от деления на число 253. Математически это записывается так:

В данном случае остаток от деления равен 2, значит, шифрация и дешифрирование произошли правильно. Было передано число 2, и это же число было принято после всех преобразований.

Предположим, что абонент В решил ответить абоненту А и направить ему букву, зашифрованную числом 3.

Абонент В использует открытый (опубликованный) ключ абонента А (s = 5, г = 91) и выполняет шифрующее преобразование числа 3. Математически это записывается так:

В линию отправляется число 61. Получив это число, абонент А восстанавливает (дешифрирует) исходный текст с помощью своего секретного ключа t = 29:

В результате дешифрации на приемной стороне получено число 3, которое отправил абонент В.

Процесс обмена буквами между абонентами иллюстрирует следующая таблица.

Передача

Число

В

линии

Прием

Бу-

ква

Число

Шифрование

Дешифрование

Число

Бу-

ква

м

2

2Ji = 167(mod(253))

167

167'‘ = 2(mod(253))

2

м

L

3

33=61(mod(91))

61

61/a=3(mod(91))

3

L

Первая строка приведенной таблицы поясняет процесс передачи буквы М от абонента А к абоненту В. Вторая строка показывает, как передается буква L от абонента В к абоненту А. В данном случае считается, что буква М кодируется числом 2, а буква L - числом 3.

В приведенных примерах был рассмотрен порядок передачи одного символа с каждой стороны. Понятно, что таким образом последовательно передается целое сообщение, но преобразование над каждым символом происходит по рассмотренной схеме. Заметим, что для использования этого метода необходимо сообщение предварительно преобразовать в набор чисел, например, с помощью кодовой таблицы.

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

Однако у этого метода есть существенный недостаток. Используя опубликованный ключ, сообщение может прислать любой абонент, выдавая себя за другого абонента.

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

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

Рассмотрим пример.

Предположим, что абонент В (вкладчик) решил послать сообщение, состоящее из числа 41, абоненту А (банкиру). Вначале вкладчик шифрует сообщение открытым ключом банкира:

В результате шифрования получено число 6.

Дальше вкладчик повторно шифрует эго сообщение своим секретным ключом 71:

Шифрограмма 94 отправляется банкиру.

Банкир, получив секретное сообщение, использует вначале открытый ключ вкладчика:

Затем банкир использует свой секретный ключ:

В результате абонент А (банкир) получает сообщение, состоящее из числа 41.

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

Цифровая подпись используется не только для заверения текстовых или финансовых документов. Эта же информационная технология применяется для указания авторства разработанной программы. Активные элементы ActiveX, оживляющие Web-сграницы, заверяются цифровой подписью. Этим повышается безопасность использования новых программных продуктов (уменьшается вероятность несанкционированной установки троянских программ).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы