Комплексная безопасность информационных систем. Асимметричные алгоритмы шифрования. (Лекция 8)

1. КОМПЛЕКСНАЯ БЕЗОПАСНОСТЬ ИНФОРМАЦИОННЫХ СИСТЕМ

ЛЕКЦИЯ 8. АСИММЕТРИЧНЫЕ АЛГОРИТМЫ
ШИФРОВАНИЯ
Профессор кафедры
доктор технических наук, старший научный сотрудник
ТУКЕЕВ Дмитрий Леонидович

2.

УЧЕБНЫЕ ВОПРОСЫ
1

3.

ЛИТЕРАТУРА
1. А.А. ВАРФОЛОМЕЕВ ОСНОВЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
Учебное пособие. Российский университет дружбы народов. – М.: 2008 С.
2

4.

1. ОБОБЩЕННАЯ СХЕМА АСИММЕТРИЧНЫХ АЛГОРИТМОВ ШИФРОВАНИЯ
сообщение
асимметричное
зашифрование
зашифрованное
сообщение
асимметричное
расшифрование
открытый ключ
получателя
закрытый ключ
получателя
сообщение
генератор ключей
Криптографическая система с открытым ключом – система шифрования
и/или электронной цифровой подписи (ЭЦП), при которой для проверки ЭЦП и для
шифрования сообщения используется открытый ключ, передаваемый по
незащищенному каналу, а для генерации ЭЦП и для расшифровки сообщения
используется секретный ключ. Открытый и закрытый ключи различны и не могут
быть получены один из другого.
Криптографические системы с открытым ключом широко применяются в
различных сетевых протоколах:
TLS и его предшественнике SSL (лежащих в основе HTTPS),
SSH, PGP, S/MIME.
3

5.

1. ОБОБЩЕННАЯ СХЕМА АСИММЕТРИЧНЫХ АЛГОРИТМОВ ШИФРОВАНИЯ
Односторонние функции
- такие f(x), что по известному x просто найти значение f(x), тогда как
вычислить x из f(x) очень сложно. Т.е. ею можно зашифровать сообщение, но
расшифровать нельзя!
Криптография с открытым ключом использует односторонние функции с
«лазейкой». Лазейка (y) — это некий секрет, который помогает расшифровать. То
есть существует такой y, что зная f(x) и y, можно вычислить x.
1.
2.
3.
Пример использования односторонних функций с «лазейкой»
Для шифрования текста можно взять телефонный справочник (по нему очень легко найти
номер любого жителя города, но очень сложно по известному номеру найти абонента).
Для каждой буквы из шифруемого сообщения выбирается имя, начинающееся на ту же букву.
Таким образом букве ставится в соответствие номер телефона абонента.
Сообщение
П
О
Б
Е
Д
А
Выбранное имя Криптотекст
Попов
5643452
Орехов
3572651
Богданова
4673956
Ефимов
3517289
Дмитриев
7755628
Арсеньева
8492746
Чтобы расшифровать текст, надо иметь
справочник,
составленный
согласно
возрастанию номеров.
Этот справочник является лазейкой
(секретом, который помогает получить
начальный
текст),
известной
только
легальным пользователям.
3

6.

1. ОБОБЩЕННАЯ СХЕМА АСИММЕТРИЧНЫХ АЛГОРИТМОВ ШИФРОВАНИЯ
Односторонние функции
Пример односторонней функции – целочисленное умножение.
Прямая задача – вычисление произведения двух очень больших чисел P и Q
(N=P*Q) – относительно несложная задача,
Обратная задача – разложение на множители целого числа N является
практически неразрешимой при достаточно больших N.
Два типа задач теории чисел, используемых в ассиметр. шифровании:
1. Факторизация целого числа:
f = x·y, найти x и y, зная f.
На настоящий момент неизвестны алгоритмы факторизации чисел, хотя и не
доказано, что таких алгоритмов не существует.
2. Задача дискретного логарифмирования
Для заданных g и a решение x уравнения gx = a называется дискретным
логарифмом элемента a по основанию g.
Задача дискретного логарифмирования состоит в нахождении некоторого
целого неотрицательного числа x, удовлетворяющего уравнению
gx=a.
3

7.

1. ОБОБЩЕННАЯ СХЕМА АСИММЕТРИЧНЫХ АЛГОРИТМОВ ШИФРОВАНИЯ
Схема обмена информацией при шифровании данных
1. Получатель A вычисляет открытый в и секретный d ключи, секретный ключ
хранит в тайне, открытый же делает доступным (сообщает отправителю, группе
пользователей сети, публикует);
2. Отправитель B, используя открытый ключ получателя в, зашифровывает
сообщение m c помощью ключа в, и пересылается зашифрованное сообщение С
получателю A;
3. Получатель A получает сообщение С и расшифровывает его, используя свой
секретный ключ d.
3

8.

1. АЛГОРИТМ ДИФФИ — ХЕЛЛМАНА
ОПИСАНИЕ АЛГОРИТМА
Предположим, существует два абонента: А и Б. Обоим абонентам известны
некоторые два числа g и p, которые не являются секретными. Для того, чтобы создать
неизвестный более никому секретный ключ, оба абонента генерируют большие
случайные числа: А — число a, Б — число b. Затем А вычисляет значение A
A = ga mod p
(1)
и пересылает его Б, а Б вычисляет:
B = gb mod p
(1)
и передаёт А. Предполагается, что злоумышленник может получить оба этих
значения, но не модифицировать их (то есть у него нет возможности вмешаться в
процесс передачи).
На втором этапе А на основе имеющегося у нее a и полученного по сети B
вычисляет значение:
Ba mod p = gab mod p.
(3)
Б на основе имеющегося у него b и полученного по сети A вычисляет значение
Ab mod p = gab mod p.
(4)
Его они и могут использовать в качестве секретного ключа, поскольку здесь
злоумышленник встретится с практически неразрешимой (за разумное время)
проблемой вычисления (3) или (4) по перехваченным ga mod p и gb mod p, если числа
p, a, b выбраны достаточно большими.
3

9.

1. КРИПТОСИСТЕМА
RSA
Криптоалгоритм RSA разработан в 1978 году тремя
авторами – Р.Ривестом, А.Шамиром и А.Адлеманом.
• В RSA каждый ключ состоит из пары целых чисел.
• Каждый участник создает свои открытый и закрытый
ключи самостоятельно.
• Закрытый ключ каждый из них держит в секрете, а
открытые ключи можно сообщать кому угодно или даже
публиковать их.
Открытый и закрытый ключи каждого участника обмена
сообщениями образуют «согласованную пару» в том смысле, что они являются взаимно обратными.
Создание открытого и секретного ключей при использовании алгоритма RSA
1. выбор простых чисел p и q;
2. вычисление n=p·q;
3. вычисление числа m=(p-1)(q-1);
4. выбор открытой экспоненты e , такой, что 1<e<m и является взаимно простым числом (не имеет
общих делителей, кроме 1, с m;
5. выбор секретной экспоненты d такой, что
d·e=1 +к· m;
6. пара чисел P=(e,n) публикуется в качестве открытого ключа;
7. пара S=(d,n) является закрытым (секретным) ключом и держится в секрете.
3

10.

1. КРИПТОСИСТЕМА
зашифрование
M
C M e (mod n)
RSA
дешифрование
C
M C d (mod n)
M
ПРИМЕР Зашифровать и расшифровать сообщение "САВ" по алгоритму RSA.
РЕШЕНИЕ
Для простоты возьмем небольшие числа - это сократит наши расчеты.
1. Выберем p=3 and q=11.
2. Определим n= 3*11=33.
3. Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
4. Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно,
например, 7: (e=7).
5. Представим шифруемое сообщение как последовательность чисел в диапазоне
от 0 до 32 (не забывайте, что кончается на n-1). Буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9; C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С); M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);
3

11.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,
основанная на трудности вычисления дискретных логарифмов в конечном поле.
Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой
подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной
цифровой подписи в США(DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1984 году.[1] Эль-Гамаль
разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал
систему Диффи-Хеллмана и получил два алгоритма, которые использовались для
шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм ЭльГамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так
как не требовалась оплата взносов за лицензию. Считается, что алгоритм
попадает под действие патента Диффи-Хеллмана.
Генерация ключей
1.Генерируется случайное простое число p длины n битов.
2.Выбирается случайный примитивный элемент g поля Zp.
3.Выбирается случайное целое число x такое, что 1<x<p-1.
4.Вычисляется y = gxmod p.
5.Открытым ключом является тройка (p,g,y), закрытым ключом
— число x.

12.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Работа в режиме шифрования
Шифросистема Эль-Гамаля является фактически одним из способов
выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме ЭльГамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
Шифрование
Сообщение шифруется следующим образом:
Выбирается сессионный ключ — случайное целое число k такое, что
1<k<p-1
Вычисляются числа a = gkmod p и b = ykmod p.
Пара чисел (a,b) является шифротекстом.
Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее
исходного сообщения вдвое.
Расшифрование
Зная закрытый ключ x, исходное сообщение можно вычислить
шифротекста (a,b) по формуле:
M = b(ax)-1 mod p.
При этом нетрудно проверить, что
(ax)-1 ≡ g – kx (mod p)
и поэтому b(ax)-1 ≡ (yk M)g – kx ≡ (g kx M) g – kx ≡ M(mod p).
Для практических вычислений больше подходит следующая формула:
M = b(ax)-1 mod p = ba(p-1-x) mod p.
из

13.

2. СХЕМА ЭЛЬ-ГАМАЛЯ

14.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Пример
Шифрование
Допустим что нужно зашифровать сообщение M = 5.
1.Произведем генерацию ключей: пусть p = 11, g = 2.
Выберем x = 8 - случайное целое число x такое, что 1<x<p-1.
Вычислим y = g^x mod p = 2^8 mod 11 = 3.
Итак, открытым является тройка (p,g,y) = (11,2,3), а закрытым ключом
является число x = 8.
2.Выбираем случайное целое число k такое, что 1 < k < (p − 1). Пусть k = 9.
3.Вычисляем число A = gk mod p = 29 mod 11 = 512 mod 11 = 6.
4.Вычисляем число B = ykM mod p = 39*5 mod 11 = 19683*5 mod 11 = 9
Полученная пара (a,b) = (6,9) является шифротекстом.
Расшифрование
Необходимо получить сообщение M = 5 по известному шифротексту
(a,b) = (6,9) и закрытому ключу x = 8.
Вычисляем M по формуле
M = b(ax)-1 mod p = 9*(68)-1 mod 11 = 5.
Получили исходное сообщение M = 5.

15.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Так как в схему Эль-Гамаля вводится случайная величина k,то шифр ЭльГамаля можно назвать шифром многозначной замены. Из-за случайности выбора
числа k такую схему еще называют схемой вероятностного шифрования.
Вероятностный характер шифрования является преимуществом для схемы ЭльГамаля, так как у схем вероятностного шифрования наблюдается большая
стойкость по сравнению со схемами с определенным процессом шифрования.
Недостатком схемы шифрования Эль-Гамаля является удвоение длины
зашифрованного текста по сравнению с начальным текстом.
Для схемы вероятностного шифрования само сообщение M и ключ не
определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо
использовать различные значения случайной величины k для шифровки
различных сообщений M1 и M2.
Если
использовать
одинаковые
k,
то
для
соответствующих
шифротекстов (a1,b1) и (a2, b2) выполняется соотношение
b1*(b2)-1 = M1*(M2)-1.
Из этого выражения можно легко вычислить M2, если известно M1.

16.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Главным преимуществом схемы цифровой подписи Эль-Гамаля является
возможность вырабатывать цифровые подписи для большого числа сообщений с
использованием только одного секретного ключа. Чтобы злоумышленнику
подделать подпись, ему нужно решить сложные математические задачи с
нахождением логарифма в поле Zp. Следует сделать несколько комментариев:
Случайное число k должно сразу после вычисления подписи уничтожаться, так
как если злоумышленник знает случайное число k и саму подпись, то он легко
может найти секретный ключ по формуле: x = (m-ks)r-1 mod(p-1) и полностью
подделать подпись.
Число k должно быть случайным и не должно дублироваться для различных
подписей, полученных при одинаковом значении секретного ключа.
Использование свертки m = h(M) объясняется тем, что это защищает подпись
от перебора сообщений по известным злоумышленнику значениям подписи.
Пример: если выбрать случайные числа i,j,удовлетворяющие условиям 0<i<p1, 0<j<p-1, НОД(j,p-1)=1 и предположить, что
r = gi y-1 mod p;
s = r j-1 mod (p-1);
m = r I j-1 mod (p-1),
то легко удостовериться в том, что пара (r,s) является верной цифровой
подписью для сообщения x = M.

17.

2. СХЕМА ЭЛЬ-ГАМАЛЯ
Цифровая подпись Эль-Гамаля стала примером построения других подписей,
схожих по своим свойствам. В их основе лежит выполнение сравнения: yA rB = gC
mod p, в котором тройка (A,B,C) принимает значения одной из перестановок ±r, ±s
и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля
получается при A = r, B = s, C = m.На таком принципе построения подписи сделаны
стандарты цифровой подписи США и России. В американском стандарте DSS
(Digital Signature Standard), используется значения A = r, B = - s, C = m, а в
Российском стандарте: A = - x, B = - m, C = s.
Еще одним из преимуществ является возможность уменьшения длины
подписи с помощью замены пары чисел (s,m) на пару чисел (s mod q,m mod q),
где q является каким-то простым делителем числа (p-1). При этом сравнение для
проверки подписи по модулю p нужно заменить на новое сравнение по
модулю q: (yA rB) mod p = gC mod q. Так сделано в американском стандарте DSS
(Digital Signature Standard).