РТУ МИРЭА
Кафедра КБ-1 «Защита информации»
ЛАБОРАТОРНАЯ РАБОТА № 3
по дисциплине «Криптографические методы защиты информации»
(шифр и наименование учебной дисциплины)
ТЕМА Шифрование с открытым ключом
(наименование темы лабораторного занятия)
РТУ МИРЭА – 2018 г.
Главная проблема использования одноключевых (симметричных) криптосистем заключается в распределении ключей. Для того, чтобы был возможен обмен информацией между двумя сторонами, ключ должен быть сгенерирован одной из них, а затем в конфиденциальном порядке передан другой. Особую остроту данная проблема приобрела в наши дни, когда криптография стала общедоступной, вследствие чего количество пользователей больших криптосистем может исчисляться сотнями и тысячами.
Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркле (Ralph Merkle) о распространении открытого ключа, они предложили метод получения секретных ключей для симметричного шифрования, используя открытый канал. В 2002 году Хеллман предложил называть данный алгоритм «Диффи - Хеллмана - Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом.
Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов - Рон Ривест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского Технологического Института (MIT)).
Справедливости ради следует отметить, что в декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал систему, аналогичную RSA, в 1973 году, а несколькими месяцами позже в 1974 году Малькольм Вильямсон изобрел математический алгоритм, аналогичный алгоритму Диффи – Хеллмана - Меркле.
Суть шифрования с открытым ключом заключается в том, что для шифрования данных используется один ключ, а для расшифрования другой (поэтому такие системы часто называют ассиметричными).
Основная предпосылка, которая привела к появлению шифрования с открытым ключом, заключалось в том, что отправитель сообщения (тот, кто зашифровывает сообщение), не обязательно должен быть способен его расшифровывать. Т.е. даже имея исходное сообщение, ключ, с помощью которого оно шифровалось, и зная алгоритм шифрования, он не может расшифровать закрытое сообщение без знания ключа расшифрования.
Первый ключ, которым шифруется исходное сообщение, называется открытым и может быть опубликован для использования всеми пользователями системы. Расшифрование с помощью этого ключа невозможно. Второй ключ, с помощью которого дешифруется сообщение, называется секретным (закрытым) и должен быть известен только законному получателю закрытого сообщения.
Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции (x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x. Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = p, тогда SIN(p) = 0). Однако, если SIN(x) = 0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i * p, где i – целое число.
Однако не всякая необратимая функция годится для использования в реальных криптосистемах. В их числе и функция SIN. Следует также отметить, что в самом определении необратимости функции присутствует неопределенность. Под необратимостью понимается не теоретическая необратимость, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства за обозримый интервал времени.
Поэтому чтобы гарантировать надежную защиту информации, к криптосистемам с открытым ключом предъявляются два важных и очевидных требования.
1. Преобразование исходного текста должно быть условно необратимым и исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа, на основе открытого также должно быть невозможным на современном технологическом уровне.
Все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из следующих типов односторонних преобразований.
1. Разложение больших чисел на простые множители (алгоритм RSA).
2. Вычисление дискретного логарифма или дискретное возведение в степень (алгоритм Диффи-Хелмана-Меркле, схема Эль-Гамаля).
3. Задача об укладке рюкзака (ранца) (авторы Хелман и Меркл).
4. Вычисление корней алгебраических уравнений.
5. Использование конечных автоматов (автор Тао Ренжи).
6. Использование кодовых конструкций.
7. Использование свойств эллиптических кривых.
Алгоритм RSA. Стойкость RSA основывается на большой вычислительной сложности известных алгоритмов разложения произведения простых чисел на сомножители. Например, легко найти произведение двух простых чисел 7 и 13 даже в уме – 91. Попробуйте в уме найти два простых числа, произведение которых равно 323 (числа 17 и 19). Конечно, для современной вычислительной техники найти два простых числа, произведение которых равно 323, не проблема. Поэтому для надежного шифрования алгоритмом RSA, как правило, выбираются простые числа, количество двоичных разрядов которых равно нескольким сотням.
Описание RSA было опубликовано в августе 1977 года в журнале «Scientific American». Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда. Например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках.
Первым этапом любого асимметричного алгоритма является создание получателем шифрограмм пары ключей: открытого и секретного. Для алгоритма RSA этап создания ключей состоит из следующих операций.
Таблица 1. Процедура создания ключей
Примечания:
· Простое число – натуральное число, большее единицы и не имеющее других делителей, кроме самого себя и единицы.
· Функция Эйлера - j(n) = (p-1)*(q-1).
· Вычисление d производится алгоритмом Евклида таким образом, что (e*d – 1) делится на j(n).
· Взаимно простые числа – числа, не имеющие общих делителей, кроме 1 (например, p=3, q=5, n=15, j(n)=8 – взаимно простые с 15 – 1, 2, 4, 7, 8, 11, 13, 14).
Процедуры шифрования и дешифрования выполняются по следующим формулам
C = Тe mod n,
Т = Cd mod n.
где Т, C – блоки исходного и зашифрованного сообщения. В нашем случае представим их в виде числовых эквивалентов символов открытого и шифрованного сообщения.
Пример шифрования по алгоритму RSA приведен в следующей таблице. Коды букв соответствуют их положению в русском алфавите (начиная с 1).
Таблица 2. Пример шифрования по алгоритму RSA
Следует отметить, что p и q выбираются таким образом, чтобы n было больше кода любого символа открытого сообщения. В автоматизированных системах исходное сообщение переводиться в двоичное представление, после чего шифрование выполняется над блоками бит, равной длины. При этом длина блока должна быть меньше, чем длина двоичного представления n.
В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи размером 2048 битов.
Алгоритм на основе задачи об укладке ранца. В 1978 г. Меркль и Хеллман предложили использовать задача об укладке ранца (рюкзака) для асимметричного шифрования. Она относится к классу NP-полных задач и формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M1, M2,..., Мn и суммарное значение S; требуется вычислить значения bi такие что
S = b1М1 + b2М2 +... + bnМn,
где n – количество предметов; bi - бинарный множитель.
Значение bi = 1 означает, что предмет i кладут в рюкзак, bi = 0 - не кладут.
Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.
В основе алгоритма, предложенного Мерклом и Хеллманом, лежит идея шифрования сообщения на основе решения серии задач укладки ранца. Предметы из кучи выбираются с помощью блока открытого текста, длина которого (в битах) равна количеству предметов в куче. При этом биты открытого текста соответствуют значениям b, a текст является полученным суммарным весом. Пример шифрограммы, полученной с помощью задачи об укладке ранца, показан в следующей таблице.
Таблица 3. Пример шифрования на основе задачи об укладке ранца
Суть использования данного подхода для шифрования состоит в том, что на самом деле существуют две различные задачи укладки ранца - одна из них решается легко и характеризуется линейным ростом трудоемкости, а другая, как принято считать, нет. Легкий для укладки ранец можно превратить в трудный. Раз так, то можно применить в качестве открытого ключа трудный для укладки ранец, который легко использовать для шифрования, но невозможно - для дешифрования. А в качестве закрытого ключа применить легкий для укладки ранец, который предоставляет простой способ дешифрования сообщения.
В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность {2, 3, 6, 13, 27, 52, 105, 210} является сверхвозрастающей, а {1, 3, 4, 9, 15, 25, 48, 76} - нет.
Решение для сверхвозрастающего ранца найти легко. В качестве текущего выбирается полный вес, который надо получить, и сравнивается с весом самого тяжелого предмета в ранце. Если текущий вес меньше веса данного предмета, то его в рюкзак не кладут, в противном случае его укладывают в рюкзак. Уменьшают текущий вес на вес положенного предмета и переходят к следующему по весу предмету в последовательности. Шаги повторяются до тех пор, пока процесс не закончится. Если текущий вес уменьшится до нуля, то решение найдено. В противном случае, нет.
Например, пусть полный вес рюкзака равен 270, а последовательность весов предметов равна {2, 3, 6, 13, 27, 52, 105, 210}. Самый большой вес – 210. Он меньше 270, поэтому предмет весом 210 кладут в рюкзак. Вычитают 210 из 270 и получают 60. Следующий наибольший вес последовательности равен 105. Он больше 60, поэтому предмет весом 105 в рюкзак не кладут. Следующий самый тяжелый предмет имеет вес 52. Он меньше 60, поэтому предмет весом 52 также кладут в рюкзак. Аналогично проходят процедуру укладки в рюкзак предметы весом 6 и 2. В результате полный вес уменьшится до 0. Если бы этот рюкзак был бы использован для дешифрования, то открытый текст, полученный из значения шифртекста 270, был бы равен 10100101.
Открытый ключ представляет собой не сверхвозрастающую (нормальную) последовательность. Он формируется на основе закрытого ключа и, как принято считать, не позволяет легко решить задачу об укладке ранца. Для его получения все значения закрытого ключа умножаются на число n по модулю m. Значение модуля m должно быть больше суммы всех чисел последовательности, например, 420 (2+3+6+13+27+52+105+210=418). Множитель n должен быть взаимно простым числом с модулем m, например, 31. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.
Таблица 4. Пример получения открытого ключа
Для шифрования сообщение сначала разбивается на блоки, по размерам равные числу элементов последовательности в рюкзаке. Затем, считая, что единица указывает на присутствие элемента последовательности в рюкзаке, а ноль — на его отсутствие, вычисляются полные веса рюкзаков – по одному рюкзаку для каждого блока сообщения.
В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с таблицей кодов символов Windows 1251. Результат шифрования с помощью открытого ключа {62, 93, 186, 403, 417, 352, 315, 210} представлен в следующей таблице.
Таблица 5. Пример шифрования
Для расшифрования сообщения получатель должен сначала определить обратное число n-1, такое что (n * n-1) mod m = 1. В математике обратное число n-1 (обратное значение, обратная величина) - число, на которое надо умножить данное число n, чтобы получить единицу (n * n-1 = 1). Пара чисел, произведение которых равно единице, называются взаимно обратными. Например: 5 и 1/5, -6/7 и -7/6. Обратными числами по модулю m называются такие числа n и n-1, для которых справедливо выражение (n * n-1) mod m = 1. Для вычисления обратных чисел по модулю обычно используется расширенный алгоритм Евклида. После определения обратного числа каждое значение шифрограммы умножается на n-1 по модулю m и с помощью закрытого ключа определяются биты открытого текста.
В нашем примере сверхвозрастающая последовательность равна {2, 3, 6, 13, 27, 52, 105, 210}, m = 420, n = 31. Значение n-1 равно 271 (31*271 mod 420 = 1).
Таблица 6. Пример расшифрования
В своей работе авторы рекомендовали брать длину ключа, равную 100 (количество элементов последовательности). В заключении следует отметить, что задача вскрытия данного способа шифрования успешно решена Шамиром и Циппелом в 1982 г.
Алгоритм шифрования Эль-Гамаля. Схема была предложена Тахером Эль-Гамалем в 1984 году. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и обеспечения аутентификации. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.
Суть задачи заключается в следующем. Имеется уравнение
gx mod p = y
Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм).
Порядок создания ключей приводится в следующей таблице.
Таблица 7. Процедура создания ключей
Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 < k < p – 1). После чего шифрограмма генерируется по следующим формулам
a = gk mod p,
b = (yk Т) mod p,
где Т – исходное сообщение;
(a, b) – зашифрованное сообщение.
Дешифрование сообщения выполняется по следующей формуле
T = (b (ax)-1) mod p
или
T = (b ap-1-x) mod p,
где (ax)-1 – обратное значение числа ax по модулю p.
Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.
Первая часть шифрованного сообщения – a = 57 mod 23 = 17.
ax = 173 = 4917, (ax)-1 = 5 (4913 * 5 mod 23 = 1) или ap-1-x = 1723-1-3 = 239072435685151324847153.
Таблица 8. Пример шифрования по алгоритму Эль-Гамаля (при k = const)
Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т’. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a’, b’) выполняется соотношение b (b’)-1 = Т (Т’)-1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т’.