18.Криптоанализ системы rsa.

Алгоритм вероятностной атаки на криптосистему RSA Из алгоритма RSA следует, что число n определяется как произведение двух чисел (p⋅ q) и знание функции Эйлера ϕ(n) эквивалентно знанию сомножителей факторизации n. Предположим, что ставится задача «взломать» систему RSA, т.е. определить положительное число d, удовлетворяющее условию

для всех a простых к n. Это эквивалентно тому, что (ed - 1) становится кратным НОК чисел (p-1), (q-1). Предположим, что известно n (являющееся произведением двух простых чисел) и также некое целое число m, удовлетворяющее сравнению для всех a взаимно простых с n. Заметим, что в этом случае m должно быть четным числом, поэтому, не меняя существа задачи, можно вместо m в дальнейшем использовать число m/2. Отсюда следует, что выражение справедливо, по крайней мере, для 50% a из (Z/nZ). Таким образом, если осуществляется тестирование множества случайно выбранных {a_i} и определяется, что во всех случаях выполняется сравнение , тогда с большой степенью вероятности можно утверждать, что все a и n взаимно просты . При этом возможны следующие варианты:

• m/2 кратно одному из двух чисел (p-1) или (q-1) ( для определенности положим p), но не кратно обоим этим числам. В этом случае всегда выполняется сравнение , но в 50% попытки сравнения по модулю q будут приводить к (-1).

• m/2 не кратно любому из двух чисел (p-1) или (q-1). В этом случае сравнения или q (и следовательно, n) выполняются в 25% попыток; сравнение или q выполняется в 25% попыток и в оставшиеся 50% выполняются сравненияa по модулю других простых чисел.

19. Криптосистемы на эллиптических кривых (целые числа): структура и принципы защиты информации.

Кривая третьего порядка Е, задаваемая уравнением вида (6.1)

называется эллиптической.

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

(6.2) Дискриминант этого уравне­ния (6.3)

Если D < 0, то (6.2) имеет три различных действительных корня α, β, γ; если D = 0, то (6.2) имеет три действительных корня α, β, β, (по крайней мере два из которых равны); наконец, если D > 0 , уравнение (6.2) имеет один действительный корень α, и два комплексно сопряженных. Вид кривой во всех трех случаях представлен на рисун­ках 6.1-6.3.

К ривая, представленная на рис. 6.2, называется сингулярной. В ее точке сингулярности (b, 0) имеются две касательные. Сингулярные кривые мы будем исключать из нашего рассмотрения. Поэтому при за­дании кривой с помощью параметров a и b потребуем выполнения условия D≠0 , что эквивалентно условию 4а³ + 27b² ≠ 0. (6.4)

П усть эллиптическая кривая Е задана уравнением (6.1) с ограничением на коэффициенты (6.4). Определим операцию компози­ции точек на кривой. Возьмем какие-либо две точки Р = (x₁,y₁), Q = (x₂,y₂) и проведем через них наклонную прямую (рис. 6.4). Эта прямая обязательно пересечет кривую в третьей точке, которую обозначим через R'. (Третья точка обязательно существует. Т.к. кубическое уравнение, получаемое после подстановки уравне­ния прямой в (6.1), имеет два действительных корня, соответствующих точкам Р и Q , следовательно, его третий корень, соответствующий R', также действителен.) Точку R = (х3,у3) получим путем измене­ния знака ординаты точки R'. Будем обозначать описанную операцию композиции точек следующим образом: R = Р + Q .

Пусть точка Р € Е имеет координаты (x, у). Тогда точку с ко­ординатами(х,-у) будем обозначать -Р. Будем считать, что вер­тикальная прямая, проходящая через Р и -Р, пересекает кривую в бесконечно удаленной точке О,т.е.Р+(-Р)=О. По соглашению Р + О = О + Р = Р.

Композиция R = (х_з,у₃) = Р + Q = Р + Р получается в случае Р=Q=(x₁,y₁) ( в случае касательной в точке Р и отражения ее второго пересечения с кривой R' относительно оси абсцисс (рис. 6.5). обозначение: R = Р + Р = [2]Р.

ф ормулы для определения координат результирующей точки R = (х_з,у₃) на основе координат исходных точек Р = (x₁,y₁), Q = (x₂,y₂):

k – угловой коэф. прямой ДЛЯ R = [2]Р : , x и y определяются так же.

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

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

у=g^хmod р на У = [x]G mod р

Переход наиболее непосредствен, когда показатель степени х приводится по модулю q. На эл­липтической кривой с мощностью рабочего множества точек q то же самое происходит с множителем [х]. Отличие состоит в том, что у — это число, a Y — точка, и обычно требуется переходить от точки к чис­лу. Наиболее простой способ такого перехода — использовать абсциссу точки.

На эллиптических кривых можно построить и аналог системы RSA.