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

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

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

Асимметричная ключевая криптография использует два отдельных ключа: один секретный (частный) и один открытый (общедоступный); шифрование и дешифрование представляют процесс запирания и отпирания замков ключами. В этом случае замок, запертый открытым ключом доступа, можно отпереть только с соответствующим секретным ключом. Рис.1 показывает, что если Алиса запирает замок открытым ключом доступа Боба, то только секретный ключ Боба может отпереть его.

Рис. 1.  Закрытие и открытие в асимметрично - ключевой криптосистеме

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

Рис. 2.  Общая идея асимметрично-ключевой криптосистемы

Первый ключ работает обычно со строкой символов (например, биты), второй - с числами или множеством чисел. Рис. 2 иллюстрирует несколько важных фактов.

Первый: подчеркивает асимметричный характер криптографической системы. Ответственность за обеспечение безопасности находится, главным образом, на плечах приемника (в данном случае это Боб). Боб должен создать два ключа: один секретный (частный) и один открытый (общедоступный). Боб не несет ответственность за распределение открытого ключа доступа всему сообществу. Это может быть сделано через канал распределения открытого ключа доступа. Хотя этот канал не обязан обеспечивать секретность, он должен обеспечить установление подлинности и целостность информации о ключе. Ева не должна иметь возможности распространять свой открытый ключ сообществу, представляя его как открытый ключ доступа Боба. На данный момент мы принимаем, что такой канал существует.

Второй факт: асимметрично-ключевая криптография означает, что Боб и Алиса не могут использовать одно и то же множество ключей для двухсторонней связи. Каждый объект в сообществе создает свой собственный секретный и открытый ключи доступа. Рис. 2 показывает, как Алиса может использовать открытый ключ доступа Боба, чтобы передать Бобу зашифрованные сообщения. Если Боб хочет ответить, Алиса устанавливает свои собственные секретный и открытый ключи доступа.

Третий: асимметрично-ключевая криптография означает, что Боб нуждается только в одном секретном ключе, чтобы получать всю корреспонденцию от любого участника сообщества. Алиса нуждается в ключах, чтобы связаться с n объектами в сообществе - один ключ доступа для каждого. Другими словами, Алиса нуждается в кольце ключей доступа.

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

Шифрование и дешифрование в асимметрично-ключевой криптографии - математические функции, которые применяются к числам, представляющим исходный текст и зашифрованный текст. Зашифрованный текст можно представлять себе как C = f (K public, P). Исходный текст можно представлять себе как P = g (K private, С). Функция f шифрования используется только для шифрования; функция дешифрования g используется для дешифрования. Далее мы покажем, что функция f нуждается в «лазейке» односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.

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

5. «Лазейка» в односторонней функции

Главная идея асимметрично-ключевой криптографии - понятие «лазейки» в односторонней функции.

Хотя понятие функции знакомо из математики, мы дадим неофициальное определение здесь. Функция - правило, по которому связывают (отображают) один элемент во множестве A, называемый доменом, и один элемент во множестве B, называемый диапазоном, как показано на рис.3.

Рис. 3.  Функция отображения домена в диапазон

Обратимая функция - функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.

Односторонняя функция - функция, которая обладает следующими двумя свойствами:

1. f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).

2. f -1 вычисляется трудно. Другими словами, при данном y, вычислить x= f ~1 (y) неосуществимо.

«Лазейка» в односторонней функции - односторонняя функция с третьим свойством:

3. При данном y и ловушке (секретной) x может быть легко вычислен.

Пример 1

Когда n является большим, - односторонняя функция. Обратите внимание, что в этой функции x - кортеж (p, q) двух простых чисел, а y в данном случае- это n. При заданных p и q всегда просто вычислить n. При данном n очень трудно вычислить p и q. Это - проблема разложения на множители. В этом случае для нахождения функции f -1 нет решения с полиномиальным временем.

Пример 2

Когда n является большим, функция y = xk mod n - «лазейка» в односторонней функции. При заданных x, k и n просто вычислить y, используя алгоритм быстрого возведения в степень. При заданных y, k и n очень трудно вычислить y. Это - проблема дискретного логарифма. В этом случае нет решения с полиномиальным временем для функции f -1. Однако если мы знаем «лазейку» и k' , такое, что , мы можем использовать x = yk mod n, чтобы найти x. Это - известный алгоритм (RSA - Riverst-Shamir-Adelman), который будет рассмотрен позже.

6. Криптографическая система RSA

Самый общий алгоритм открытого ключа доступа - криптографическая система RSА, названная по имени его изобретателей Ривеста, Шамира, Эделмана (Rivest, Shamir и Adelman).

RSА использует два типа ключей - e и d, где e - открытый, a d - секретный. Предположим, что P - исходный текст и C - зашифрованный текст. Алиса использует C = Pe mod n, чтобы создать зашифрованный текст C из исходного текста P; Боб использует P = Cd mod n, чтобы извлечь исходный текст (файл), переданный Алисой. Модулей n создается очень большое количество с помощью процесса генерации ключей, который мы обсудим позже.

Для шифрования и дешифрования применяют возведение в степень по модулю. При использовании быстрого алгоритма возведение в степень по модулю выполнимо в полиномиальное время. Однако нахождение модульного логарифма так же сложно, как и разложение числа по модулю. Для него нет алгоритма с полиномиальным временем. Это означает, что Алиса может зашифровать сообщение общедоступным ключом (e) в полиномиальное время. Боб также может расшифровать его в полиномиальное время (потому что он знает d). Но Ева не может расшифровать это сообщение, потому что она должна была бы вычислить корень e-той степени из C с использованием модульной арифметики. Рис. 4 показывает идею RSA.

Рис. 4 Сложность операций в RSA

Другими словами, Алиса использует одностороннюю функцию (возведение в степень по модулю) с лазейкой, известной только Бобу. Ева не знает лазейку, поэтому не может расшифровать сообщение. Если когда-нибудь найдут полиномиальный алгоритм для модуля вычисления корня e-той степени из n, то возведение в степень по модулю n не будет больше односторонней функцией.

Рис. 5 показывает общую идею процедуры, используемой в RSA.

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

Рис. 5  Шифрование, дешифрование и генерация ключей в RSA

RSA использует две алгебраических структуры: кольцо и группу.

Кольца шифрования/дешифрования. Шифрование и дешифрование сделаны с использованием коммутативного кольца с двумя арифметическими операциями: сложение и умножение. В RSA это кольцо общедоступно, потому что модуль n общедоступен. Любой может послать сообщение Бобу, используя это кольцо для шифрования.

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

RSA использует две алгебраических структуры: открытое кольцо R = < Zn, +, ? > и секретную группу G = < Z(n)*, ? >.

Алгоритм создания открытого и секретного ключей.

• Выбираются два случайных простых числа p и q

• Вычисляется их произведение n=p*q, которое называется модулем.

• Вычисляется значение функции Эйлера от числа n:

ц(n)=(p-1)(q-1)

• Выбирается открытый ключ е с учетом условий:

1<e<ц(n), НОД(е,ц(n))=1

• Определяется секретный ключ d, удовлетворяющего условию:

e*d?1 (mod ц(n)), где d<n

• Пара P=(e,n) публикуется в качестве открытого ключа RSA

• Пара S=(d,n) играет роль секретного ключа RSA и держится в секрете

Боб использует шаги, показанные в данном алгоритме, чтобы создать свои открытый и секретный ключи. После генерации ключей Боб объявляет кортеж (e, n) как свой открытый ключ доступа: Боб сохраняет d как свой секретный ключ. Боб может отказаться от p, q и ; они не могут изменить его секретный ключ, не изменяя модуль. Для безопасности рекомендуется размер для каждого простого p или q - 512 бит (почти 154 десятичные цифры). Это определяет размер модуля, n 1024 бита (309 цифр).

В RSA кортеж (e, n) - открытый ключ доступа; целое число d - секретный ключ.

Алгоритм шифрования сообщения P

· Разбиваем исходный текст на блоки P1, P2, …, Pm

· Шифруем текст сообщения в виде последовательности блоков

Cj= Pjе mod n( j =1,n)

Алгоритм расшифрования

Чтобы расшифровать эти данные, используя секретный ключ (d,n), необходимо выполнить следующие вычисления: Pj= Cjd mod n ( j =1,n) В результате будет получено множество чисел P(j), которые представляют собой исходный текст.

В RSA p и q должны быть по крайней мере 512 битов; n должны быть по крайней мере 1024 бит.

Пример 3

Боб выбирает 7 и 11 как p и q и вычисляет . Значение или 60. Теперь он выбирает два ключа, e и d, из Z60*. Если он выбирает e = 13, то d = 37. Обратите внимание, что (они инверсны друг другу). Теперь предположим, что Алиса хочет передать исходный текст 5 Бобу. Она использует общедоступный ключ 13, чтобы зашифровать 5.

Исходный текст:5

Страницы: 1, 2, 3, 4