к какому типу относится алгоритм эль гамаля

Эль-Гамаль Шифрование

Введение в шифрование Эль-Гамаля

Алгоритм шифрования Эль-Гамаля с примером

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

Это будет очень легко понять на простом примере. Предположим, что даже если такие значения, как g ^ a и g ^ b, являются значениями, известными злоумышленнику, злоумышленнику будет чрезвычайно трудно найти значение g ^ ab, которое является ничем иным, как взломанным значением.

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

Шаг 1: Генерация открытого и закрытого ключей.

Шаг 2: Пользователь2 зашифрует данные с помощью открытого ключа Пользователя1.

Шаг 3: Расшифровка сообщения на конце user1.

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

Рекомендуемые статьи

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

Источник

«Криптосистемы-протоколы»: Диффи—Хеллмана, Эль-Гамаля, MTI/A(0), STS

Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам. Предыдущие разделы главы «Криптографически протоколы»: 1, 2, 3

Как и создатели трёхпроходных протоколов из предыдущего раздела, авторы следующих алгоритмов считали их не просто математическими конструкциями, обеспечивающие некоторую элементарную операцию (например, шифрование с открытым ключом), но пытались вокруг одной-двух формул построить законченную систему распространения ключей. Некоторые из этих конструкций, преобразовавшись, используются до настоящего времени (например, протокол Диффи-Хеллмана), некоторые — остались только в истории криптографии и защиты информации.

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

Протокол Диффи—Хеллмана

Первый алгоритм с открытым ключом был предложен Диффи и Хеллманом в работе 1976 года «Новые направления в криптографии» (Bailey Whitfield Diffie, Martin Edward Hellman, «New directions in cryptography», [Diffie, Hellman 1976]). Данный протокол, который также можно назвать схемой Диффи—Хеллмана, стал первым, позволивший уменьшить требования к каналу связи для установления защищённого соединения без предварительного обмена ключами.

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

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

Протокол обмена состоит из следующих действий.

Протокол обеспечивает только генерацию новых сессионных ключей (цель G10). В отсутствие третей доверенной стороны он не обеспечивает ни аутентификацию сторон (цель G1), из-за отсутствия проходов с подтверждением владения ключом отсутствует аутентификация ключа (цель G8). Зато, так как протокол не использует длительные «мастер»-ключи, можно говорить о том, что он обладает свойством совершенной прямой секретности (цель G9).

Протокол можно использовать только с такими каналами связи, в которые не может вмешаться активный криптоаналитик. В противном случае протокол становится уязвим к простой «атаке посередине».

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

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

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

Протокол Эль-Гамаля

Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

Протокол не обеспечивает гарантию выбора нового сессионного ключа в каждом сеансе протокола (G10), а использование «мастер»-ключа для передачи сеансового ключа позволяет злоумышленнику вычислить все сессионные ключи из прошлых сеансов при компрометации закрытого ключа (цель G9).

Протокол MTI/A(0)

В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

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

Как и другие представители криптосистем-протоколов, MTI не разрабатывался с учётом возможности компрометации закрытых «мастер»-ключей и (цель G9).

Протокол Station-to-Station

Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Каждая из сторон и обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи и открытым ключом для шифрования и проверки подписи .

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

Протокол состоит из четырёх проходов, три из которых включают передачу сообщений ([Черёмушкин 2009]).

Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

Как и все остальные «криптосистемы-протоколы», протокол Station-to-Station основывается на некотором внешнем источнике информации об открытых ключах участников, не подвергая сомнению корректность и надёжность этого источника. Что, в общем случае, неверно. Если информация о ключах участников нужно получать извне при каждом сеансе протокола (например, если участников много, и запомнить ключи всех возможности нет), то канал получения открытых ключей будет основной целью активного криптоаналитика для рассмотренных протоколов. Как от этого защититься с использованием примитивов асимметричной криптографии — в следующем разделе.

Литература

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

Источник

К какому типу относится алгоритм эль гамаля

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стойкость 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 1978 г. Меркл и Хеллман для асимметричного шифрования предложили использовать задачу об укладке ранца (рюкзака) [8], которая относится к классу NP-полных задач.

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

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

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

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

В качестве закрытого ключа (легкого для укладки ранца) используется сверхвозрастающая последовательность. Сверхвозрастающей называется последовательность, в которой каждый последующий член больше суммы всех предыдущих. Например, последовательность <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 должно быть больше суммы всех чисел последовательности (например, m = 420 [2+3+6+13+27+52+105+210 = 418]). Множитель n должен быть взаимно простым числом с модулем m (например, n = 31). Результат построения нормальной последовательности (открытого ключа) представлен в следующей таблице.

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

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

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

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

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

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

Авторами идеи и первого алгоритма вероятностного шифрования являются Шафи Гольдвассер (Shafi Goldwasser) и Сильвио Микали (Silvio Micali). Для данного типа шифров при шифровании одного и того же исходного сообщения с помощью одного и того же открытого ключа k₁ можно получить разные шифртексты, которые при расшифровке закрытым ключом k₂ дают изначальное исходное сообщение.

Такая особенность вероятностного шифрования делает бессмысленными атаки на шифр «с известным открытым текстом» и «с выбором открытого текста».

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

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

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

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

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

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

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

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

g i mod p ≠ 1, для 1 ≤ i

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

2 36 mod 37 = 1;
2 1 mod 37 = 2 (≠ 1);
2 2 mod 37 = 4 (≠ 1);
2 3 mod 37 = 8 (≠ 1);
2 4 mod 37 = 16 (≠ 1);
. ;
2 34 mod 37 = 28 (≠ 1);
2 35 mod 37 = 19 (≠ 1).

Для шифрования каждого отдельного блока исходного сообщения должно выбираться случайное число k (1 k mod p, (9.7)

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

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

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

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

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

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

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

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

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

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

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

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

y 2 ≡ x 3 + Ax + B (mod p), (9.12)

Запись A ≡ B (mod p) означает, что остатки от деления на p левой (A) и правой (B) частей выражения равны. В таких случаях говорят, что правая и левая части выражения «сравнимы по модулю». Например, 7 2 ≡ 2 3 + 4 * 2 + 3 (mod 5) ⇒ (7 2 ) mod 5 = (2 3 + 4 * 2 + 3) mod 5 ⇒ 49 mod 5 = 19 mod 5 ⇒ 4 = 4.

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

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

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

Аналитически сложение точек P₁ и P₂ выполняется по формулам:

Если P₁ = P₂, то λ равен значению производной в точке P₁.

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

Способ 1. Выполнить k раз сложение точки P

Способ 2. С использование двоичного представления числа k = (b_L, …, b₂, b₁) и операции удвоения точки. Например, k = 94₁₀ = 1011110₂, тогда P_k = 64P + 16P + 8P + 4P + 2P.

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

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

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

Для k = 94 вместо 93 сложений будет 4 сложения и 6 удвоений (сложений).

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

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

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

y 2 ≡ x 3 + Ax + B (mod p) ⇒ y 2 ≡ x 3 + 3x + 7 (mod 41).

Примем x₁ = 7, тогда y₁ 2 mod 41 = (7 3 + 3 * 7 + 7) mod 41 = 2, откуда y₁ = 17.

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

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

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

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

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

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

t = (36 * 14) mod 41 = 123Определяется исходное сообщение по ее десятичному представлению.Буква «K»

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

Источник