29) Криптосистема Рабина.

Используется RSA модуль (n = pq).

Числа p и q выбираются из условий:

p = 3 mod 4 и q = 3 mod 4

Процедура шифрования проста: y = x² mod n

Эта процедура осуществляется следующим способом:

Вычисляется:

x_p1 = mod p

x_p2 = p - mod p

x_q1 = mod q

x_q2 = q - mod q

p и q составляют секретный ключ

Формируются значения:

x₁ = x_p1∙a + x_q1∙b mod n

x₂ = x_p1∙a + x_q2∙b mod n

x₃ = x_p2∙a + x_q1∙b mod n

x₄ = x_p2∙a + x_q2∙b mod n

x n

a = q (q^-1 mod p)

b = p (p^-1 mod q)

КС Рабина не дает четкого расшифрования. Это главный недостаток. Достоинство: процедуры шифрования и расшифрования несложные.

30.Понятие эллиптической кривой. Свойства точек эллиптической кривой. Выбор параметров эллиптической кривой.

Эллиптическая кривая(Е) – множество точек (x,y), удовлетворяющие уравнению: .

Нужно найти корни уравнения:

1.D<0 3 корня

2.D>0 1 корень

3.D=0 2 корня (не исп в криптографии)

Первым условием выбора кривой, проверяется неравенство D=0.

Свойства точек элл. кривой: 1) P+Q=Q+P 2) (P+Q)+S=P+(Q+S) 3) P+0=P 4) P+(-P)=0 (существование обратной точки).

Композицию точек наз. сложением точек, а операцию P+P=[2]P - удвоением.

Выбор параметров элл. кривой :

1)Выбирается число p, т.е модуль. Длина битового числа должна быть такой. Что бы сделать невозможным применение метода вычисления логарифма на элл кривой.

2)выбираются параметры a и b, что бы D≠0.

3)Вычисляется количество точек на элл кривой (# (a,b))

4)определяется условие, если n простое число n=# (a,b). Подходит, если n=q или n=h*q (h – небольшое число). Если вып условие, то алгоритм продолжается. Стойкость определяется не только числом p, но и q. Если аглоритм не вып, то переходим к этапу 2.

5)проверка ( ; 0<k<32.

6)проверка p≠q.

Если проверки проходят, то кривая считается выбранной, выбирается точка генератора (G)

31.Криптосистема Эль-Гамаля на эллиптической кривой.

1)выбирается общая для пользователя элл кривая и точка G. Каждый пользователь генерирует закрытый ключ(число) и вычисляет точку: ]G= . (открытый ключ – точка). Параметры кривой и открыты публично. Если хотим передать сообщение x (x<p), то шифрование производится след образом:

2)генерируется k, 0<k<q

3)вычисляется точка R=[k]G; P=[k]

4)осущ передача инф: y=x* modp (y – число)

Передается <R,y>

5) на приемной стороне Q= ]R. Q и P одна и таже точка, тогда из Q берем ординату

32.Методы криптоанализа криптосистем с открытым ключом: метод криптоанализа «шаг младенца, шаг великана», метод исчисления порядка.

Шаг младенца, шаг великана(имеется уравнение )

1)выбираем 2 целых числа, которые удовлетворяют условию m*k=p

2)вычисляем 2 ряда чисел до тех пор, пока не будет совпадений в 1 и 2 ряду.

y ,ay, y, …, y modp – шаг младенца

, ,…, modp – шаг великана

3)находятся числа i,j для которых вып равенство: = y. I,j – степени шагов. (число I определяется по 2ому ряду, j определяется по 1ому ряду)

4)число x=im-j явл решением уравнения

Метод исчисления порядка ( )

Число n называется р-гладким если оно разлагается только на простые множители, меньшие либо равные р.