Цели и задачи изучения темы
Целью данной темы является рассмотрение вопросов построения асимметричных криптосистем, хэш-функций и электронных цифровых подписей.
Алгоритмы шифрования с открытым ключом
Одной из основных проблем при практическом использовании рассмотренных симметричных систем шифрования является проблема распределения секретных ключей между абонентами и проблема хранения этих ключей.
Для решения этих проблемы на основе результатов, полученных классической и современной алгеброй, были предложены асимметричныекриптосистемы. Суть их состоит в том, что каждым адресатом информационного обмена генерируются два ключа, связанные между собой по определенному правилу. Один ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому, кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне.
Все асимметричные криптографические системы основаны на использовании односторонних функций с секретом.
Рассмотрим в общем виде принцип использования односторонних функций с секретом для шифрования сообщений. Каждый абонент криптосистемы выбирает некоторую одностороннюю функцию 
с секретом k. Функции всех абонентов заносятся в общедоступный справочник, но значение секрета k каждый абонент, как и следует из названия, держит в секрете. Если абонент B хочет переслать сообщение M абоненту A, он извлекает из справочника функцию абонента A и с ее помощью вычисляет C = Fk (M). Шифртекст C пересылается абоненту A, который по нему вычисляет исходное сообщение M, обратив функцию с помощью секрета k. Расшифровать сообщение может только абонент A, поскольку кроме него никто не знает секрет k.
Обычно функции шифрования для разных абонентов вычисляются по одному и тому же заранее установленному алгоритму, но в зависимости от некоторого параметра. У каждого абонента такой параметр свой. Этот параметр называется открытымключом данного абонента, поэтому асимметричные криптосистемы называют также криптосистемами с открытым ключом.
Наиболее известными криптосистемами с открытым ключом являются RSA, Диффи-Хеллмана, Эль Гамаля и криптосистема на основе эллиптических кривых.
Криптосистема RSA
Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.
Надежность алгоритма основывается на трудности факторизации больших чисел.
В криптосистеме RSA открытый ключ e, секретный ключ d открытый текст М и шифртекст С принадлежат множеству целых чисел
где N – модуль: 
. Здесь Р и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете.
Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.
Число e выбирают случайным образом так, чтобы выполнялись условия:
,
,
где 
– функция Эйлера, НОД (a,b) – наибольший общий делитель чисел a и b. Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N. Второе из указанных выше условий означает, что e и функция Эйлера должны быть взаимно простыми. Это гарантирует существование величины d, такой, что
или 
.
В RSA число e рассматривают как открытый ключ и используют для шифрования данных, а d – как секретный ключ для расшифрования.
Вычислить секретный ключ d по известным значениям e и можно с помощью расширенного алгоритма Евклида, который позволяет решить следующую задачу: даны целые неотрицательные числа a и b (
), найти целые x, y, c, такие, что ax + by = c, где c = НОД(a,b).
Приведем его описание.
НА ВХОДЕ: два неотрицательных числа a и b:
НА ВЫХОДЕ: c = НОД (a, b) и целые x, y: ax + by = c.
1. Положить x2:=1, x1:=0, y2:=0, y1:=1
2. Пока b > 0 выполнят шаги 2.1 и 2.2
2.1. q:= a div b, r:= a – qb, x:= x2 – qx1, y:= y2 – qy1
2.2. a:= b, b:= r, x2:= x1, x1:= x, y2:= y1, y1:= y
3. Положить c:= a, x:= x2, y:= y2 и возвратить (c, x, y). Конец.
Нахождение d сводится к выполнению указанного алгоритма при значениях входных параметров a = и b = e. В этом случае искомое значение d есть выходной параметр y.
В RSA преобразование шифрования определяет шифртекст С через пару (открытый ключ e, открытый текст М) в соответствии со следующей формулой:
.
В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.
Обращение функции 
, т.е. определение значения М по известным значениям С, e и N, практически не осуществимо при 
.
Однако обратную задачу можно решить, используя пару (секретный ключ d, шифртекст С) по следующей формуле:
.
Рассмотрим конкретный пример:
1) Выбрать два простых числа: P = 7, Q = 17;
2) Вычислить 
;
3) Вычислить 
;
4) Выбрать е так, чтобы е было взаимнопростым с 
и меньше, чем : пусть е = 5;
5) Определить d так, чтобы 
и d < 96: d = 77, т.к.
77×5 = 385 = 4×96 + 1;
6) Зашифровать сообщение М = 19:
;
7) Расшифровать C = 66: 
.
Общая процедура шифрования/расшифрования в криптосистеме RSA представляет собой следующую последовательность действий.
1. Получатель сообщения формирует значения , e и d, так, как было описано выше. Параметры N и e являются общедоступными, и могут быть распространенны по незащищенному каналу связи. Параметры P, Q и d являются секретными.
2. Отправитель сообщения, зная N и e, осуществляет шифрование сообщения. Если открытый текст представляет собой число 
, то он разбивается на блоки, каждый из которых может быть представлен в виде числа 
. Каждый такой блок подвергается преобразованию:
.
В итоге получается шифртекст 
, который отправляется получателю.
3. Получатель расшифровывает принятый шифртекст , используя секретный ключ d по формуле:
.
В результате получается последовательность чисел 
, которые представляют собой открытый текст M.
