Криптографические методы защиты информации

Лекции

9. ШИФРОВАНИЕ С ОТКРЫТЫМ КЛЮЧОМ

 

9.1. Основы шифрования.

9.2. Алгоритм RSA.

9.3. Алгоритм на основе задачи об укладке ранца.

9.4. Вероятностное шифрование.

9.5. Алгоритм шифрования Эль-Гамаля.

9.6. Алгоритм на основе эллиптических кривых.

Вопросы для самопроверки.

 

9.1. Основы шифрования

 

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

Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 г. Находясь под влиянием работы Ральфа Меркла (Ralph Merkle) о распространении открытого ключа, они предложили метод получения секретных ключей для симметричного шифрования, используя открытый канал. В 2002 г. Хеллман предложил называть данный алгоритм «Диффи - Хеллмана - Меркла», признавая вклад Меркла в изобретение криптографии с открытым ключом [17].

Хотя работа Диффи-Хеллмана создала большой теоретический задел для открытой криптографии, первой реальной криптосистемой с открытым ключом считают алгоритм RSA (названный по имени авторов - Рон Ривест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman)).

Справедливости ради следует отметить, что в декабре 1997 г. была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал систему, аналогичную RSA, в 1973 г., а несколькими месяцами позже в 1974 г. Малькольм Вильямсон изобрел математический алгоритм, аналогичный алгоритму Диффи – Хеллмана - Меркла.

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

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

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

Алгоритмы шифрования с открытым ключом используют так называемые необратимые или односторонние функции. Эти функции обладают следующим свойством: при заданном значении аргумента х относительно просто вычислить значение функции f(x), однако, если известно значение функции y = f(x), то нет простого пути для вычисления значения аргумента x. Например, функция SIN. Зная x, легко найти значение SIN(x) (например, x = π, тогда SIN(π) = 0). Однако, если SIN(x) = 0, однозначно определить х нельзя, т.к. в этом случае х может быть любым числом, определяемым по формуле i * π, где i – целое число.

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

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

1. Преобразование исходного текста должно быть условно необратимым и исключать его восстановление на основе открытого ключа.

2. Определение закрытого ключа на основе открытого также должно быть невозможным на современном технологическом уровне.

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

1. Разложение больших чисел на простые множители (алгоритм RSA).

2. Вычисление дискретного логарифма или дискретное возведение в степень (алгоритм Диффи-Хелмана-Меркла, схема Эль-Гамаля).

3. Задача об укладке рюкзака (ранца) (авторы Хелман и Меркл).

4. Вычисление корней алгебраических уравнений.

5. Использование конечных автоматов (автор Тао Ренжи).

6. Использование кодовых конструкций.

7. Использование свойств эллиптических кривых.

 

9.2. Алгоритм RSA

 

Стойкость RSA основывается на большой вычислительной сложности известных алгоритмов разложения числа на простые сомножители (делители). Например, легко найти произведение двух простых чисел 7 и 13 даже в уме – 91. Попробуйте в уме найти два простых числа, произведение которых равно 323 (числа 17 и 19). Конечно, для современной вычислительной техники найти два простых числа, произведение которых равно 323, не проблема. Поэтому для надежного шифрования алгоритмом RSA, как правило, выбираются простые числа, количество двоичных разрядов которых равно нескольким сотням.

[44] В августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:

N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541.

Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители р и q. Более того, Гарднер назначил приз в размере $100 (приличная сумма на тот момент) тому, кто первым получит правильный ответ. Каждый, кто захочет побольше узнать о шифре, писал Гарднер, может обратиться к создателям шифра — Рону Ривесту, Ади Шамиру и Леонарду Адлеману из Лаборатории информации Массачусетского технологического института.

Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более чем 600 человек. Ключами оказались р = 32 769 132 993 266 709 549 961 988 190 834 461 413 177 642 967 992 942 539 798 288 533 и q = 3 490 529 510 847 650 949 147 849 619 903 898 133 417 764 638 493 387 843 990 820 577, а зашифрованная фраза звучала так: «Волшебные слова — это брезгливый ягнятник».

Авторы RSA поддерживали идею её активного распространения. В свою очередь, Агентство национальной безопасности (США), опасаясь использования этого алгоритма в негосударственных структурах, на протяжении нескольких лет безуспешно требовало прекращения распространения системы. Ситуация порой доходила до абсурда. Например, когда программист Адам Бек (Adam Back) описал на языке Perl алгоритм RSA, состоящий из пяти строк, правительство США запретило распространение этой программы за пределами страны. Люди, недовольные подобным ограничением, в знак протеста напечатали текст этой программы на своих футболках [17].

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

Таблица 9.1. Процедура создания ключей

№ п/пОписание операцииПример
1Выбираются два простых числа1 p и q.p=7, q=13
2Вычисляется произведение n = p * q.n=91
3Вычисляется функция Эйлера2 φ(n).φ(n) = (7-1)(13-1) = 91-7-13+1 = 72
4Выбирается открытый ключ e, как произвольное число (0 < e < n), взаимно простое3 с результатом функции Эйлера (e φ(n)).e=5
5Вычисляется закрытый ключ d, как обратное число4 к e по модулю φ(n), из соотношения (d*e) mod φ(n) = 1.(d*5) mod 72 = 1, d = 29
6Публикуются открытый ключ (e, n) в специальном хранилище, где исключается возможность его подмены (общедоступном сертифицированном справочнике).

Примечания.

1) Простое число — натуральное число, большее единицы и не имеющее других натуральных делителей, кроме самого себя и единицы.

2) Результат расчета функция Эйлера φ(n) равен количеству положительных чисел, не превосходящих n и взаимно простым с n. Некоторые случаи и способы расчета функции Эйлера приведены в следующей таблице.

Таблица 9.2. Способы расчета функции Эйлера

Расчетный случайФормулаПример
(число / расчетная формула /
список взаимно простых чисел)
n
простое число
φ(n) = n - 1n = 7
φ(7) = 7 – 1 = 6
{1, 2, 3, 4, 5, 6}
n = p q
произведение двух простых чисел
φ(n) = φ(p) φ(q) =
= (p - 1) (q - 1) = n – p – q + 1
(за исключением случая p = q = 2)
n = 15 = 3 * 5
φ(15) = φ(3) φ(5) = (3 - 1) (5 - 1) = 15 - 3 - 5 + 1 = 8
{1, 2, 4, 7, 8, 11, 13, 14}
n = pq
простое число в степени
φ(n) = pq – pq-1n = 9 = 32
φ(9) = 32 - 32-1 = 9 - 3 = 6
{1, 2, 4, 5, 7, 8}
n = p1q1 p2q1 … pkqk
разложение числа согласно
основной теоремы арифметики
(общий случай)
n = 84 = 22 31 71

{1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83}

3) Взаимно простые числа – числа, не имеющие общих делителей, кроме 1, т.е. наибольший общий делитель которых равен 1.

4) Обратными числами по модулю m называются такие числа n и n-1, для которых справедливо выражение (n * n-1) mod m = 1. Для вычисления обратных чисел по модулю обычно используется расширенный алгоритм Евклида. В безмодульной математике обратное число n-1 (обратное значение, обратная величина) - число, на которое надо умножить данное число n, чтобы получить единицу (n * n-1 = 1). Пара чисел, произведение которых равно единице, называются взаимно обратными. Например: 5 и 1/5, -6/7 и -7/6.

 

Процедуры шифрования и дешифрования выполняются по следующим формулам

C = Тe mod n,          (9.1)

Т = Cd mod n.          (9.2)

где Т, C - числовые эквиваленты символов открытого и шифрованного сообщения.

Пример шифрования по алгоритму RSA приведен в следующей таблице. Коды букв соответствуют их положению в русском алфавите (начиная с 1).

Таблица 9.3. Пример шифрования по алгоритму RSA

Открытое сообщение, ТСимволАБРАМОВ
Код1218114163
Шифрограмма, С = Т5 mod 91132441147461
Открытое сообщение, Т = С29 mod 911218114163

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

[44] Алгоритм RSA требует много машинного времени и очень мощных процессоров. До 1980-х гг. только правительства, армия и крупные предприятия имели достаточно мощные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (англ. Pretty Good Privacy — «достаточно хорошая степень конфиденциальности»), алгоритм которой мог работать на домашних компьютерах. PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.

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

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

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

Спецслужбы обладают лучшими криптографическими технологиями. Как и торговцы оружием и наркотиками. Как и военные подрядчики, нефтяные компании и другие корпорации-гиганты. Но обычные люди и общественные организации практически не имеют недорогих защитных криптографических технологий с открытым ключом. До сих пор не имели.

PGP дает людям возможность самим защищать свою конфиденциальность. Сегодня существует растущая социальная потребность в этом. Вот почему я написал PGP.

В заключении следует отметить стойкость данного алгоритма. В 2003 г. Ади Шамир и Эран Тромер разработали схему устройства TWIRL, которое при стоимости $ 10 000 может дешифровать 512-битный ключ за 10 минут, а при стоимости $ 10 000 000 – 1024-битный ключ меньше, чем за год. В настоящее время Лаборатория RSA рекомендует использовать ключи (параметр n) размером 2048 битов.

 

9.3. Алгоритм на основе задачи об укладке ранца

 

В 1978 г. Меркл и Хеллман предложили использовать задача об укладке ранца (рюкзака) для асимметричного шифрования [8]. Она относится к классу NP-полных задач и формулируется следующим образом. Дано множество предметов различного веса. Спрашивается, можно ли положить некоторые из этих предметов в ранец так, чтобы его вес стал равен определенному значению? Более формально задача формулируется так: дан набор значений M1, M2, ..., Мn и суммарное значение S; требуется вычислить значения bi такие что

S = b1М1 + b2М2 + ... + bnМn,          (9.3)

где n – количество предметов;
bi - бинарный множитель. Значение bi = 1 означает, что предмет i кладут в рюкзак, bi = 0 - не кладут.

Например, веса предметов имеют значения 1, 5, 6, 11, 14, 20, 32 и 43. При этом можно упаковать рюкзак так, чтобы его вес стал равен 22, использовав предметы весом 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его вес стал равен 24.

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

Таблица 9.4. Пример шифрования на основе задачи об укладке ранца

Открытый текст111001000101100100000000
Рюкзак (ключ)156111420324315611142032431561114203243
Шифрограмма32 (1+5+6+20)73 (5+11+14+43)0

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность {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. Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

Таблица 9.5. Пример получения открытого ключа

Закрытый ключ, ki236132752105210
Открытый ключ,
(ki*n) mod m = (ki*31) mod 420
6293186403417352315210

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

В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с таблицей кодов символов Windows 1251. Результат шифрования с помощью открытого ключа {62, 93, 186, 403, 417, 352, 315, 210} представлен в следующей таблице.

Таблица 9.6. Пример шифрования

Открытое сообщениеСумма весовШифрограмма
(рюкзак), ci
СимволBin-код
А1100 000062+93155
Б1100 000162+93+210365
Р1101 000062+93+403558
А1100 000062+93155
М1100 110062+93+417+352924
О1100 111062+93+417+352+3151239
В1100 001062+93+315470

Для расшифрования сообщения получатель должен сначала определить обратное число 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).

Таблица 9.7. Пример расшифрования

Шифрограмма
(рюкзак), ci
(ci*n-1) mod m =
(ci*271) mod 420
Сумма весовОткрытое сообщение
СимволBin-код
15552+31100 0000А
3652152+3+2101100 0001Б
558182+3+131101 0000Р
15552+31100 0000А
924842+3+27+521100 1100М
12391892+3+27+52+1051100 1110О
4701102+3+1051100 0010В

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

 

9.4. Вероятностное шифрование

 

Вероятностное шифрование является разновидностью криптосистем с открытым ключом (авторы - Шафи Гольдвассер (Shafi Goldwasser) и Сильвио Микали (Silvio Micali)). Данный вид шифрования относят к допускающим неоднозначное вскрытие. Основной целью вероятностного шифрования является устранение утечки информации в криптографии с открытым ключом. Поскольку криптоаналитик всегда может зашифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифртекст С (С = Еk1(T)) и он пытается получить открытый текст T, он может выбрать случайное сообщение T' и зашифровать: С' = Еk1(T'). Если С' = С, то он угадал правильный открытый текст. В противном случае он делает следующую попытку.

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

С1 = Еk1(T), С2 = Еk1(T), С3 = Еk1(T), ..., СN = Еk1(T),          (9.4)

T = Dk2(C1) = Dk2(C2) = Dk2(C3) = ... = Dk2(CN).          (9.5)

В результате, даже если у криптоаналитика имеется шифртекст Ci и он угадает T, то в результате операции шифрования получиться Сj = Еk1(T). Вероятность того, что Ci = Сj крайне низка. Таким образом, криптоаналитик даже не узнает, была ли правильной его догадка относительно T или нет.

Ниже рассматриваются два алгоритма вероятностного шифрования:

- алгоритм шифрования Эль-Гамаля;

- алгоритм на основе эллиптических кривых.

 

9.5. Алгоритм шифрования Эль-Гамаля

 

Схема была предложена Тахером Эль-Гамалем в 1984 г. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и обеспечения аутентификации. Стойкость данного алгоритма базируется на сложности решения задачи дискретного логарифмирования.

Суть задачи заключается в следующем. Имеется уравнение

gx mod p = y.          (9.6)

Требуется по известным g, y и p найти целое неотрицательное число x (дискретный логарифм).

Порядок создания ключей приводится в следующей таблице.

Таблица 9.8. Процедура создания ключей

№ п/пОписание операцииПример
1Выбирается простое число p.p = 37
2Выбирается число g, являющееся первообразным корнем по модулю p и меньшее р.g = 2
3Выбираются произвольное число x, меньшее p.x = 5
4Вычисляется y = gx mod py = 25 mod 37 = 32 mod 37 = 32
5Открытый ключ - y, g и p. Причем g и p можно сделать общими для группы пользователей.
Закрытый ключ - x.

Примечание. Первообразный (примитивный) корень по модулю p – наименьшее положительное число g такое, что

gφ(p) mod p = 1

и

gi mod p ≠ 1,     для 1 ≤ i < φ(p)

где φ(p) – функция Эйлера (т.к. р – простое число, то φ(p) = p - 1).

Проверка. При g = 2 и p = 37, φ(37) = 37 – 1 = 36.

236 mod 37 = 1;
21 mod 37 = 2 (≠ 1);
22 mod 37 = 4 (≠ 1);
23 mod 37 = 8 (≠ 1);
24 mod 37 = 16 (≠ 1);
...;
234 mod 37 = 28 (≠ 1);
235 mod 37 = 19 (≠ 1).

Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 < k < p – 1). После чего шифрограмма генерируется по следующим формулам

a = gk mod p,          (9.7)

b = (yk Т) mod p,          (9.8)

где Т – исходное сообщение;
(a, b) – зашифрованное сообщение.

Дешифрование сообщения выполняется по следующей формуле

T = (b (ax)-1) mod p          (9.9)

или

T = (b ap-1-x) mod p,          (9.10)

где (ax)-1 – обратное значение числа ax по модулю p.

Пример шифрования и дешифрования по алгоритму Эль-Гамаля при k = 7 приведен в таблице, хотя для шифрования каждого блока (в нашем случае буквы) исходного сообщения надо использовать свое случайное число k.

Первая часть шифрованного сообщения – a = 27 mod 37 = 17.

ax = 175 = 1419857, (ax)-1 = 2 (1419857 * 2 mod 37 = 1) или ap-1-x = 1737-1-5 ≈ 1.3928892 * 1038.

Таблица 9.9. Пример шифрования по алгоритму Эль-Гамаля (при k = const)

Открытое сообщение, ТСимволАБРАМОВ
Код1218114163
Вторая часть шифрограммы, b = (327 * T) mod 371919197820
Открытое сообщение, T = (b * 2) mod 371218114163

Ввиду того, что число k является произвольным, то такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, т.к. у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение Т и ключ не определяют шифртекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений Т и Т’. Если использовать одинаковые k, то для соответствующих шифртекстов (a, b) и (a’, b’) выполняется соотношение b (b’)-1 = Т (Т’)-1 (mod p). Из этого выражения можно легко вычислить Т, если известно Т’.

Пример. Предположим злоумышленник перехватил зашифрованное сообщение С = ((a1, b1), (a2, b2), …, (an, bn)), для которого использовалось одно и тоже случайное число k. Он знает один из блоков Ti = Ek1(Ci) или при известном открытом ключе (y, g, p) ему удалось подобрать k’, которое совпало с используемым при шифровании k. Например по второму варианту, для шифрования символа Х (Т' = 22) злоумышленник использовал k’ = 7 (равное k). Тогда, b(X) = b’ = (327 * 22) mod 37 = 11, (b’)-1 = 27, (Т’)-1 = 32. Расшифрование перехваченного сообщения приведено в следующей таблице.

Таблица 9.10. Пример расшифрования перехваченного сообщения

Вторая часть перехваченной шифрограммы, b1919197820
L = (b * (b’)-1) mod p = (b * 27) mod 373227213243122
Вскрытое
открытое
сообщение,
Т
Код, определяемый по уравнению
(T * (T’)-1) mod p = L
(Т * 32) mod 37 = L
1218114163
СимволАБРАМОВ

 

9.6. Алгоритм на основе эллиптических кривых

 

Использование эллиптических кривых для создания криптосистем было независимо предложено Нилом Коблицем (Neal Koblitz) и Виктором Миллером (Victor Miller) в 1985 г. [8, 17]. При использовании алгоритмов на эллиптических кривых полагается, что не существует быстрых алгоритмов для решения задачи дискретного логарифмирования в группах их точек. В настоящий момент известны лишь экспоненциальные алгоритмы вычисления обратных функций для эллиптических кривых. По сравнению с субэкспоненциальными алгоритмами разложения числа на простые сомножители (см. криптосистему RSA), это позволяет при одинаковом уровне стойкости уменьшить размерность ключа в несколько раз, а, следовательно, упростить программную и аппаратную реализацию криптосистем.

Эллиптической кривой E называется множество точек (x, y), удовлетворяющих однородному уравнению Вейерштрасса:

y2 + a1xy + a2y = x3 + a3x2 + a4x + a5,          (9.11)

где ai - коэффициенты уравнения.

а) y2 = x3 – x б) y2 = x3 – 3x + 2 в) y2 = x3 – x + 1

Рис.9.1. Примеры эллиптических кривых

В криптографии эллиптические кривые рассматриваются над двумя типами конечных полей: простыми полями нечётной характеристики (n, где n > 3 - простое число) и полями характеристики 2 (GF(2m)).

Эллиптические кривые над полями нечётной характеристики n можно привести к виду, называемому эллиптической кривой в короткой форме Вейерштрасса:

y2 = x3 + Ax + B (mod n),          (9.12)

где A, B n - коэффициенты эллиптической кривой, удовлетворяющие 4 A3 + 27 B2 ≠ 0 (mod n).

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

x3 + Ax + B = 0.          (9.13)

Это можно сделать с помощью известных формул Кардано. Дискриминант этого уравнения

.          (9.14)

Если ∆ > 0, то уравнение имеет три различных действительных корня (см. рис. 9.1а – x1, x2 и x3). Если ∆ = 0, то уравнение имеет три действительных корня, по крайней мере, два из которых равны (см. рис. 9.1б – x1 и x2). Если ∆ = 0, то уравнение имеет один действительный корень (см. рис. 9.1в – x1) и два комплексно сопряженных.

Используемые в криптографии кривые не должны иметь особых точек. Геометрически это значит, что график не должен иметь точек возврата и самопересечений (см. рис. 9.1б). Если кривая не имеет особых точек, то её график имеет две части при положительном дискриминанте (см. рис. 9.1а), и одну - при отрицательном (см. рис. 9.1в). Например, для графиков выше в первом случае дискриминант равен 64, а в третьем он равен -368.

Следует отметить, что в n у каждого ненулевого элемента есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой разбиваются на пары вида P = (x, y) и -P = (x, -y). Например, эллиптическая кривая y2 = x3 + 3x + 2 при x = 1 и n = 5 имеет две точки в качестве решения: P = (1, 1) и -P = (1, -1), т.к. 12 ≡ 13 + 3 * 1 + 2 (mod 5) и (-1)2 ≡ 13 + 3 * 1 + 2 (mod 5).

Введем две операции, которые можно выполнять над точками кривой.

Сложение точек P3(x3, y3) = P1(x1, y1) + P2(x2, y2).

а) y2 = x3 – x б) y2 = x3 – x + 1

Рис.9.2. Сложение точек

          (9.15)

          (9.16)

В формулах 9.15 и 9.16 λ - угловой коэффициент прямой, проходящей через точки P1 и P2. Если P1 = P2, то λ равен значению производной в точке P1.

Умножение точки на число Pk(xk, yk) = k * P(x, y).

а) y2 = x3 – x б) y2 = x3 – x + 1

Рис.9.3. Удвоение точки

А) вариант 1 – выполнить сложение точки P k раз

          (9.17)

B) вариант 2 – с использование двоичного представления числа k = (bL, …, b2, b1) и операции удвоения точки. Например, k = 11010 = 11011102, тогда Pk = 64P + 32P + 8P + 4P + 2P.

Алгоритм, вычисления Pk может выглядеть следующим образом.

1. Pk := null

2. Q := P

3. Цикл. Для i := 1 до L

3.1. Если bi = 1

     то Если Pk = null

        то Pk = Q

        иначе Pk = Pk + Q

3.2. Q = 2 * Q     // ≈ Q = Q + Q

Для k = 110 вместо 109 сложений будет 1 присваивание, 4 сложения и 6 удвоений (сложений).

Рассмотрим процедуру создания ключей.

Таблица 9.11. Процедура создания ключей

№ п/пОписание операцииПример
1Выбирается модуль эллиптической кривой - простое число n (n > 2255 - ГОСТ).n = 41
2Выбираются коэффициенты эллиптической кривой A и B.
Должно соблюдаться условие (4 A3 + 27 B2) mod n ≠ 0, в противном случае меняются параметры эллиптической кривой n, A или B.
A = 3, B = 7

(4 * 33 + 27 * 72) mod 41 = 37
3Определяется точка эллиптической кривой P(xp, yp) и порядок циклической подгруппы группы точек эллиптической кривой q*).
Принимается произвольное xp (0 < xp < n) и определяется yp из уравнения эллиптической кривой.
Должны соблюдаться условия:
- для xp должен существовать yp (не для всякого xp при данных параметрах кривой (A, B, n) может существовать yp);
- P ≠ O и q P = O, где O - нулевая точка эллиптической кривой (P + (-P) = O);
- q – простое число;
- nt mod q ≠ 1, для всех целых t = 1, 2, …, T, где T ≤ 31;
- 2254 < q < 2256 (ГОСТ)
в противном случае меняются либо параметры эллиптической кривой n, A или B либо выбирается другая точка P.
xp = 7 ((73+3*7+7) mod 41 = 2),
yp = 17 (172 mod 41 = 2)

q = 47
4Выбирается закрытый ключ d (0 < d < q).d = 10
5Определяется точка эллиптической кривой Q(xq, yq):
Q(xq, yq) = d * P(xp, yp).
xq = 36,
yq = 20
6Публикуется открытый ключ [(A, B), P(xp, yp), n, Q(xq, yq)] в специальном хранилище, где исключается возможность его подмены (общедоступном сертифицированном справочнике).
Для выработки и проверки электронной цифровой подписи q является частью открытого ключа вместо n.

*) Прямой способ вычисления порядка группы точек эллиптической кривой q.

1) Рассчитываются координаты первой точки из выражения

y2 = x3 + Ax + B (mod n) > y2 = x3 + 3x + 7 (mod 41).

Примем x1 = 7, тогда y12 mod 41 = (73 + 3 * 7 + 7) mod 41 = 2, откуда y1 = 17.

P(xp, yp) = P(x1, y1) = P(7, 17).

2) Находим координаты второй точки. Для этого вначале вычисляется коэффициент λ

Решая последнее уравнение, получаем λ = 2 (34 * 2 mod 41 = 27).

Координаты второй точки получаем путем удваивания первой из выражений

x2 = (λ2 – 2x1) mod n = (22 – 2 * 7) mod 41 = -10 mod 41 = 31,

y2 = (λ(x1 – x2) – y1) mod n = (2 (7 – 31) – 17) mod 41 = -65 mod 41 = 17.

3) Каждую следующую точку рассчитываем по формулам, пока в знаменателе первой формулы не будет получен 0:

          (9.18)

          (9.19)

Получаем:

- λ3 = 0, x3 = 3, y3 = 24;
- λ4 = 29, x4 = 11, y4 = 31;
- λ5 = 24, x5 = 25, y5 = 2;
- …;
- λ46 = 2, x46 = 7, y46 = 24.

К полученному числу точек добавляем точку О, в результате чего q = 46 + 1 = 47. Эта точка есть результат сложения любых двух точек P(xi, yi) и -P(xi, -yi) и представляет собой бесконечно удаленную точку, в которой гипотетически сходятся все вертикальные кривые.

Процедура шифрования отдельного блока выполняется следующим образом [25].

Таблица 9.12. Процедура шифрования отдельного блока (буквы)

№ п/пОписание операцииПример
1Определяется десятичное представление буквы t.Буква «K»
t = 12
2Выбирается случайное число k (0 < k < n).k = 5
3Определяется точка Pk(xpk, ypk) = k * P.Pk(25, 2)
4Определяется точка Qk(xqk, yqk) = k * Q.Qk(3, 24)
5Вычисляется с = (t * xqk) mod n.с = (12 * 3) mod 41 = 36
6Шифрограмма – пара [Pk, c].[Pk(25, 2), 36]

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

Таблица 9.13. Процедура расшифрования отдельного блока (буквы)

№ п/пОписание операцииПример
1Вычисляется точка D(xd, yd) = d * Pk.D(3, 24)
2Вычисляется десятичное представление зашифрованной буквы t = (с * xd-1) mod n,
где xd-1 – обратное число к xd по модулю n.
xd-1 = 14 [(3 * 14) mod 41 = 1]
t = (36 * 14) mod 41 = 12
3Определяется исходное сообщение по ее десятичному представлению.Буква «K»

Приведенный выше способ шифрования является вариацией шифрования Эль-Гамаля. Если стойкость алгоритма шифрования Эль-Гамаля базируется на сложности решения задачи дискретного логарифмирования, то стойкость шифрования с помощью эллиптических кривых базируется на сложности нахождения множителя k точки P по их произведению. Т.е. если Q = k P, то зная P и k довольно легко вычислить Q. Эффективное решение обратной задачи (найти k при известных P и Q) на текущий момент пока не опубликовано.

 

Вопросы для самопроверки

 

1. В чем заключается суть и основная предпосылка появления шифрования с открытым ключом?

2. Основные требования, предъявляемые к криптосистемам с открытым ключом.

3. Перечислите типы односторонних преобразований, применяемых при асиметричном шифровании.

4. Дайте краткую характеристику алгоритма RSA.

5. В чем отличие сверхвозрастающей последовательности от обыкновенной?

6. Что означает обратное число по модулю?

7. В чем отличие вероятностного шифрования с открытым ключом от детерминированного?

8. В чем суть задачи дискретного логарифмирования?

9. Приведите уравнение эллиптической кривой в короткой форме Вейерштрасса.