Эллиптическая криптография. Ильичев Д.О._МОп-1601б. Д. О. Ильичев (И. О. Фамилия)
 Скачать 1.03 Mb.
|
|
Глава 2. Эллиптические кривые в криптографии 2.1 Алгоритмы на эллиптических кривых 2.1.1 Эллиптические кривые над полем GF( ) В основном криптография использует кривые над нечетным полем, но часто используются кривые над полем GF( ). Ниже на рисунке 2.1 показан алгоритм сложения и удвоения эллиптических кривых Рисунок 2.1 - Алгоритм сложения и удвоения точек на кривых Суперсингулярные кривые. Основной отличительной особенностью этих кривых в сравнении с несуперсингулярными, это легкость вычисления порядка кривой. Чтобы использовать эти кривые не обязательно использовать сложный алгоритм вычисления порядка кривой. Суперсингулярную кривую можно описать следующим уравнением ( ) (2.1) С помощью замены переменных уравнение можно привести к виду ( ) (2.2) Если из этого уравнения извлекается корень третьей степени, то заменив переменную ( ) уравнение переписывается следующим образом 17 ( ) (2.3) Несуперсингулярные кривые. Уравнение таких кривых представляется в следующем виде (2.4) С заменой переменных , где приводит эту кривую к виду (2.5) 2.1.2 Скалярное умножение на суперсингулярных кривых Скалярное умножение точки - это основа в арифметике эллиптических кривых. Лучше всего использовать балансные системы счисления. Алгоритмической особенностью этих кривых является более быстрая работа с удвоением точки чем с умножением. Оценка сложности складывается за счет операций сложения точек. В аддитивных цепочках можно ускорить вычисления, когда точка P не задается заранее. Если же P известна заранее придется использовать другие алгоритмы, однако в них использование суперсингулярных кривых не принесет особой пользы. Проективные координаты. При увеличении количества умножений в четыре с половиной раза можно получить более быстрые вычисления, не смотря на то что время преобразования будет в пять раз больше. После этого можно переходить к проективным координатам. Подстановкой в уравнения эллиптических кривых Ep1, Ep2, Ep3 получим однородные уравнения относительно X, Y (2.6) (2.7) 18 (2.8) Проективные координаты (X, Y, Y) и (X, Y, Z) эквивалентны при условии что существует такое число t множества K при котором выполняется условие . Класс равного соотношения обозначим (X: Y: Z). Все классы этих трех координат и является проективными координатами. Эллиптическая кривая теперь является множеством проективных точек на плоскости. Точка которая лежит на прямой будет единственной нулевой точкой с координатами х = 0, y = 1, z = 0. Пусть ( ) и ( ) . Представим, что . Для точки ( ) необходимо применить формулу сложения, после применения которых, учитывая что получим ( ) (2.9) Где . Из этого следует находим ( ), где ( ) (2.10) 2.1.3 Скалярное умножение на несуперсингулярных кривых Заменив алгоритмы для сложения и удвоения точек можно использовать предыдущие алгоритмы на суперсингулярных кривых для несуперсингулярных. Метод Монтгомери для несуперсингулярных кривых. Криптографы Лопес и Дахаб создатели этого метода. Для рассмотрения используется кривая . Вычисления производятся после каждого шага где . По формулам сложения 19 и удвоения точек используемые для несуперсингулярных кривых, находим обновленные координаты точек ( ) ( ) .(2.11) ( ) (2.12) При =0 результатом удвоения точек получается бесконечно удаленная точка. Метод Монтгомери в проективных координатах. Этот метод использует координаты точек представляя их ⁄ . Вычисление точки 2Pi происходит по формуле ( ) ( ) (2.13) где Нахождение координат точки происходит по формуле. ( ) ( ) ( ) (2.14) где ( )( ), ( ) Метод Лопеса-Дохаба использования проективных координат. Чтобы уменьшить количество операций для проективных координат нашлось решение приравнивать координатным переменным (X:Y:Z) аффинную точку ( ). Тогда в проективных координатах кривая представляется в виде (2.15) Смешанное проективно-аффинское сложение точек выполняется с помощью девяти умножений, девяти сложений и пяти возведений в квадрат. 20 Как и в суперсингулярных кривых, этот метод можно использовать с любой вариацией метода аддитивных цепочек при которых строятся линейные цепочки. P сразу вычисляется в аффинных координатах, потому что в конце придется переводить в афиинные координты, затрачивая по два деления на точку. При k содержащей u(k) удвоений и s(k) сложений, трудность вычислений равна ( ) ( ) ( ), а в алгоритме Коблица (если b=1) ( ) ( ) ( ). 2.2 Протоколы на эллиптических кривых 2.2.1 Выбор точки и размещение данных Криптография использует точки эллиптической кривой для особенных точек. Криптографическая задача решает выбирать случайную точку или брать точку на координатах которой находятся данные. Значение x можно получить как часть бинарного вектора, значение y координаты определяется с помощью уравнения кривой. Это связано с тем что нужно решить квадратное уравнение. Сперва нужно выбрать точку на эллиптической кривой. Для суперсингулярных кривых алгоритм показан на рисунке 2.2. Рисунок 2.2 – Алгоритм суперсингулярных кривых Алгоритм для несуперсингулярной кривой показан на рисунке 2.3 21 Рисунок 2.2 - Алгоритм несуперсингулярных кривых 2.2.2 Распределение ключей Для примера используем несколько протоколов. Криптостойкость данных алгоритмов складывается за счет сложности вычисления дискретного логарифма и алгоритма Диффи-Хеллмана. Проблемы вычисления логарифма появляется когда известна группа циклов, известна определенного элемента и необходимо определить показатель x. Для групп точек эллиптической кривой проблема с использованием дискретного логарифма является определением числа k по известной точке P и точке Q, которая равна произведению этих чисел. Для эллиптических кривых не придумано полиномиальных алгоритмов решения, но существует решение для суперсингулярных кривых, который переводит эту проблему к DLP. Классической проблемой Диффи-Хеллмана является использование его алгоритма в мультипликативной группе поля. Суть этой проблемы в вычислении по элементам , и Протокол Диффи-Хеллмана. Вместо ключа классической криптосистемы можно взять случайную точку (x, y), Рассмотрим пример. E – это эллиптическая кривая и P – это точка этой кривой. Абонент А выбирает случайное число , вычисляет координаты точки и отправляет абоненту В. Абонент В делает тоже самое и отправляет абоненту А. Точка является общим ключом. Абонент 22 А вычисляет эту точку, умножая свой ключ на ключ полученный от абонента В, а В вычисляет, умножая свой ключ на полученный ключ абонента A. Благодаря тому что группа точек является абелевой, Результат не зависит от того в каком порядке буду происходить вычисления, тогда абоненты получат одинаковую точку (x,y) и могут использовать координату x как ключ одинаковой криптосистемы. Проблемой для сторонних людей будет в вычислении секретной точки, так как они не будут знать секретные ключи абонентов. В этом и заключается проблема Диффи-Хеллмана. Протокол Месси-Омуры. Это протокол, позволяющий передавать информацию по открытым каналам связи без передачи информации. Мультипликативный вариант. Протокол был описан к мультипликативной группе , где p это простое число. Абонент А прикрепляет к ящику свой ключ и отсылает его абоненту В. Абонент B получает посылку и прикрепляет к ящику свой ключ и отсылает его абоненту А. После этого абонент А открепляет свой ключ от ящика и снова отсылает его абоненту В. Абонент В, получив посылку открепляет свой ключ от ящика. Иногда вместо механических замков можно использовать электронные. Для этого необходимо выбрать большое простое число p. Абоненты А и В выбирают случайные числа и и вычисляют числа и , обратные по модулю ( ) ( -функция Эйлера) ( ( )) ( ( )) (2.16) Числа ( ), ( ) это секретные ключи. Для m при 0 ( ) ( ) . Первый множитель равен 1 по теореме Эйлера. Аддитивный вариант. На эллиптической кривой находятся постоянные переменные, переменные перемножаются с точками кривой, по модулю ее порядка. Применив алгоритм преобразования вычислим 23 ( ). (2.17) Благодаря теореме сравнимости по модулю получаем Для всех точек этой кривой с порядком N выполняется свойство ( ) Можно вычислить Q=eP и R=dQ, используя e и d из формулы (2.17) и точку эллиптической кривой. В алгоритме, который использует алгебру эллиптических кривых, параметрами для системы используют уравнение кривой и поле, над которым она построена. По этому протоколу абонент А выбирает число и вычисляет по формуле (2.15) число . Абонент B выбирает свое число и вычисляет число Абонент А зашифровывает информацию в точку M и умножает на свое число и получает точку . Далее он отсылает ее B. Абонент В производит вычисления точки . Далее А расшифровывает свой замок и вычисляет точку и пересылает ее абоненту В. Абоненту B нужно снять шифровку с сообщения. Умножая точку А на свой ключ и найти . Сообщение m может выступать в качестве ключа симметричной криптосистемы. Протокол Менезеса-Кью-Венстоуна (MQV – протокол). Протоколы, которые рассматривались ранее имеют проблему, что посторонний человек сможет перехватить информацией при перехвате сообщение. Например, в протоколе Диффи-Хеллмана злоумышленник, назовем его абонентом С, сможет завладеть информацией, которую абоненту B посылает абонент А и заполучить закрытый ключ абонента B. Абонент B и абонент C владеют одинаковыми закрытыми ключами. Далее C сделает тоже самое для абонента А, после чего А и С имеют общий закрытый ключ. При осторожных действиях третьего абонента А и В не будут знать, что у них есть посредник. Для того чтобы этого не случилось необходима авторизация кратковременных ключей, для этого используются закрытые ключи. В алгоритме одноразовые ключи привязываются к многоразовым из-за этого 24 злоумышленник не может перехватить информацию или сообщение. При использовании одноразового ключа становится невозможно использовать многоразовые ключи при передаче сообщения. ( ) (2.18) Константу k можно вычислять в модульной арифметике кольца так и Z. Поэтому существует два варианта решения этой задачи. Первый вариант реализует модульную арифметику целых чисел. Второй вариант реализует циклические свойства подгруппы точек эллиптической кривой. Если реализовывается модульная арифметика, то с числами можно выполнить некоторые математические действия, например, сложение или умножение, а если реализовывать арифметику эллиптической кривой, то числа можно умножать на точки эллиптической кривой. Оба варианта предопределяют что абоненты знают точку Р кривой порядка N, с которой происходят все вычисления. Открытые ключи абонента B известны абоненту А ( ) ( ) (2.19) Открытые ключи абонента А известны абоненту B ( ) ( ) (2.20) 2.2.3 Криптосистемы Эль-Гамаля Протокол Диффи-Хеллмана можно рассмотреть в криптосистеме Эль - Гамаля на эллиптической кривой. Рассмотрим пример, при котором пользователь один хочет отправить сообщение пользователю два. Поэтому строим криптосистему Эль-Гамаля с математическими свойствами эллиптических кривых. Параметрами являются эллиптическая кривая и точка высшего порядка. 25 Пользователь А выбирает никому неизвестное число , вычисляет свой общедоступный ключ (E,P,Y), где Абонент B для передачи секретного сообщения m получает копию открытого ключа (E, N, P, Y); прикладывает сообщение в точку ( ); задает случайное число ; вычисляет временный ключ ; вычисляет криптограмму; пересылает криптосистему абоненту А. Для того чтобы расшифровать сообщение пользователь А, применяет свой закрытый ключ ,вычисляя , далее то что получилось он прибавляет к , и получает точку M (2.21) Аналитик теперь знает чем является общедоступный ключ (E, P, Y) и криптосистема ( ), чтобы найти точку М необходимо вычислить точку . Теперь необходимо перейти к решению алгоритма Диффи-Хеллмана, или проще говоря решить логарифмическую задачу. Использовать тот же рандомизатор не получится. При условии, что у аналитика получилось дешифровать криптосистему или вычислить значение точки M, аналитик может узнать и другие сообщения или информацию, которая была зашифрована с этим рандомизатором. 2.2.4 Протоколы цифровой подписи Электронная цифровая подпись. Подпись в электронном документе – это некий цифровой код, который в зависимости от информации в сообщении, использованного ключа и задающегося рандомизатора меняется. Обозначим M, K, R, S – это группа сообщений, которые можно использовать, группа ключей для определенного шага, рандомизаторов и электронных подписей. 26 Ее можно записать в следующем виде ( ) (2.22) При такой записи она является электронной подписью пары точек (m, h(m)), эти пары точек являются сообщением, которое готовится быть подписанным. Множество пар этих точек имеет некоторые криптографические свойства. Группа точек H имеет не такую большую мощностью, в сравнении с множеством : | | | | | |. Все элементы h группы точек H имеет огромное количество прообразов | | | ( )| |{ ( ) }| (2.23) Если задать первую координату, то можно узнать элемент множества. Чтобы это сделать нужно узнать, чему равно h(m) первой координаты по вычислению числа хеш – функции. Вычислять первую координату по второй считается невозможным так как хеш-функция имеет свойство односторонности. При условии что задается элемент ( ( )) , считается практически недосягаемым выбрать такой элемент ( ( )) ( ( )) , т.е. элемент отличается от того, который задали только первой координатой. Считается невозможным взять две группы чисел ( ) и ( ), у которых координаты второго элемента совпадали бы. Электронная подпись сообщения h(m) с ключом подписи k осуществляет проверку возможности использования ключа проверки Проверяется расчеты предиката проверки ( ), в нем - это группы ключей для проверки. Проверочный предикат для подписи с учетом возврата сообщения можно описать следующим образом 27 ( ) {( ( )) } (2.24) В нем m’ – это информация для проведения подлинности подписи, а h’(m) хеш-функция информации. Отображение Sign (M, K, R) имеет несколько свойств, которые обеспечивают подлинность подписи. Отображение в одну сторону Sign(h(m), K, R) считается невозможным в плане вычисления ключа. Значение отображения s = Sign (h(m), k, r), такое что P (s, k’). Для цифровой подписи с известным заранее сообщением производим вычисления s = Sign(h(m), k, r), Р(s, k’), считается невозможным фальсифицировать сообщение m’ чтобы оно имело такое же цифровое значение. Одним словом, подделать подпись не получится. Считается невозможным подобрать два сообщения m и m’ с одинаковой электронной подписью т.е предикат проверки с заданным ключом будет удовлетворено k. При отсутствии информации о цифровой подписи нельзя узнать сообщение и ее значение под этим сообщением Признаки, описанные выше подкрепляются стойкой хеш-фукнцией, в которой имеются раннее упомянутые признаки и биективные преобразования. 2.2.5 Электронная подпись Эль-Гамаля с возвратом сообщения – схема Nyberg-Rueppel. Этот алгоритм построен на проверке можно ли изъять «отпечаток» какого-то сообщения с помощью проверки подписи s, которую абонент получает при подписке документа используя ключ подписи k, рандомизатор r и главная задача проверить условие ( ) ( ) (2.25) где m’ это сообщение, а h’(m) – это хеш-значение сообщения, которое берется из подписи на определенном ключе. 28 Рассмотрим пример. Y(F) сгруппированные точки кривой Y, P – стандартная точка общедоступного ключа, N – порядок этой точки, k – закрытый ключ того кто подписывает документ. Общедоступным ключом пользователя будет точка (2.26) e=h(m) – это хеш-функция h в сообщении. Последовательность вычислений электронной подписи такой. Берется случайная точка r, 0 (2.27) Используем x координату точки R как целое число и вычисляем ( ) (2.28) ( ) (2.29) Если c равно нулю или d равно нулю, то мы возвращаемся к шагу с формулой 2.25. В этом случае точки c и d являются подписью документа m, такого что h(m)=e. Для проверки не фальсифицирована ли хеш-функция h(m) выполняется следующее. Проверяется что Вычисляем (2.30) Используя x координату точки R’ в виде двоичной записи числа, вычисляем ( ) (2.31) 29 При совпадении значения точки e’ со значением хеш-функции последнее удостоверяется. 30 Глава 3. Реализация и тестирование алгоритма 3.1 Протокол Дифии-Хеллмана Передача информации с помощью открытых каналов была большой проблемой. Для этой проблемы нашлось решение после того как появился алгоритм Диффи-Хеллмана. Этот алгоритм дал возможность пересылать сообщения без отправки каких-либо полезных сведений для расшифровки. Сам алгоритм позволяет пользователям обмениваться ключами без опасности перехвата информации. Криптографию с открытыми ключами предложили использовать Уитфилд Диффи и Мартин Хеллман. Они привнесли в криптографию понятие что можно использовать ключи шифрования и расшифрования — исключая возможность утечки информации закрытого ключа с помощью открытого ключа. Впервые этот алгоритм был представлен на Национальной компьютерной конференции 1976 года. Ниже мы опишем его числовую реализацию. |