2й RSA: Шифр c подписью

na 11 3 33

(33 na ) (3 1)(11 1) 2 10 20

T c d a

da 2d 1 ...: нод(da ; (nA )) 1

da 1

Eb 3b 2 . : нод(Eb ; (Nb )) 1

Потеря секретных данных

n p q

n открытоp q

секретно

(n) ( p 1)(q 1)

(n)

тогда

Пусть	открыто
( p 1)(q 1)	pq	p q 1
n (n) p q 1
Что вместе с
n p q				известно
					t	p q
				q t		p
n p				n p (t p)
								n p t p2
	Квадратное уравнение Над R
	p	2	tp		n		o
					pq		Теорема ВИЕТА

p q	p и q
Корнями являются

ПРОтокол ФИАТА-Шамира

Доверяют ВсеЦентрЮзеры С

			о
		т
		ры
	к
т
о

	с
разложение
n p q	е
	е
	к
	р
	т
	н
	о

	Юзер А	S
	выбирает
		секретно

: нод(s, n) 1

vто s

2

n

откр

mod

ы

A регистрирует в Центре С

как открытые данные

идентификация

x r2 mod n

* A вычисляет

e 0

или

e 1

y r se mod n

* A выбирает с. r

* B случайным обр. выбирает

Передаёт его В

Передаёт его A

и передаёт его В

проверка

к

10100 00

если

* B проверяет y2 x ve mod n

repeat

1

y 0

until

если

p

y 0

2

10100

Отвергает без проверки

26-ричная a 0

b 1 c2 d3 e4 f5 g6 h7 I8 j9 k10 l11 m12 n13 o14 p15 q16 r17 s18 t19 u20 v21 w22 x23 y24 z25

А1

б2

в3

г4

д5

е6

ё7

ж8

з9

и10

й11

к12

л13

м14

н15

о16

п17

р18

с19

т20

у21

ф22

х23

ц24

ч25

ш26

щ27

ъ28

ы29

ь30

э31

ю32

я33

А1

б2

в3

г4

д5

е6

ё7

ж8

з9

и10

й11

к12

л13

м14

н15

о16

п17

р18

с19

т20

у21

ф22

х23

ц24

ч25

ш26

щ27

ъ28

ы29

ь30

э31

ю32

я33

а0

б1

в2

г3

д4

е5

ё6

ж7

з8

ий9

к10

л11

м12

н13

о14

п15

р16

с17

т18

у19

ф20

х21

ц22

ч23

ш24

щ25

ъ26

ы27

ь28

э29

ю30

я31

32-ричная	А0	30-ричная
	б1		А0
	в2		б1
	е5 Алфавит		г3
	г3		в2
	д4
	ё6		д4
			её5
	ж7
	з8	Ф.И.О. инициалы	ж6
	и9	Б.С.С. 1, 16, 16	з7
	к11		к9
	й10		ий8
	л12	30o	л10
	о15	1 16 30 16 30 ..
			н12
	м13	2	м11
	н14
	п16		о13
	р17		п14
	с18		р15
	т19
		Ф.И. инициалы	с16
	у20
	ф21		т17
	х22	Б.С. 1, 16, 16	у18
	ц23		ф19
	ч24	текст	х20
	ш25	T 1 16 30 ..	ч22
	щ26		ц21
	ъ27	n 997	ш23
	ы28
	ь29	n 997	щ24
	э30		ъь25
	ю31		ы26
	я32		э27

	e ближК a b c : нод(e, (n))	ю28
		я29

Зашифровать алгоритмом Масси-Омуры

p 31

g3

x a y с

T a b d

p, g опубликованы g 65537 простое n на порядки больше

Алгоритм

Диффи-Хелмана

A		A,	Б		Б
		поле F	Открытое
			общее
			знание
секретно		g порождающий Эл.т		придумать z
придумать x
g x передать					секретно
				g z передать
открыто			использ z		открыто
использ x
для ux g z x g zx	общий ключ		для yz g x z		g zx общий ключ
секретно					секретно
	w g zx	общий Секретный ключ			Дешифровка
	шифровка				(обратно)
Сообщение					M С w
	С	M w
M
		или			С w 1
	С M w

Зашифровать алгоритмом Диффи-Хелмана

p 31

g3

x a y с

T a b d

2x 3 (3x 1) 6x2

11x 3

2x 3

(3x 1)

1 mod

x

2

x 2

1x2 1 x 3 1 x2 x 2 1

Взять

Эллиптические кривые

ОбратитьпоMod(x2 x 2)

(a b c) F

2

строим

5

Теорема: существует неприводимый многочлен любой

F r

1

1

1

1

-

p

требуется

-

степени n

-

-

-

1

p

p

p

p

p

f (x)

≤

r

≤

r

1

≤

2

≤

1

≤ 0

ar x

ar 1x

a2 x

a1x a0 x

неразложимый

≤

≤

≤

≤

0

≤

неразложимость

0

0

0

0

1

состоит из

f (x) g(x) h(x)

F

=

0≤ ai ≤ p-1

52

ar 1

0,1, ...

Многочленов степени n

a

x2

a x1 a

1

h(x) a

r 1

xr

1 a

r

2

xr 2

x, x 1, x 2,... x 4

pr

2

1

0

2x, 2x 1,2x 2,... ,2x 4

пусть В

2точности

пример

F52

3x, 3x 1,3x 2,... ,3x 4

f

(x) x

x 2

неразложим

проверка

4x, 4x 1,4x 2,... ,4x 4

a,b : f (x) (x a) (x b)

обратим

f( x 0) 2

3 x 1

f( x 1) 4

x2 x 2

3 2

1

(3x

1)2x

4 x 2

f( x 2) 3

2

6 x

x 2 4 x 2

3x 1 (4x 2) 2

2 x

2

3 1

f

( x 3)

4 f( x 4) 2

3x 4

3 2

2 3x 1 2(4 x 2)

1 2 3 3 (3x 1)

6(4x 2)

3 (3x

1)

(4x 2)

откуда

4 x 2 ( x 2 x 2) (3x 1) 2 x

3 (3x 1)

(x

2

x 2) (3x 1) 2x

x2 x 2

2x 3 (3x 1)

x 2

2x 3 (3x 1) 1

1

x2

2x 3 (3x 1) 1 mod .

2x 3 (3x 1) 6x2 5x 3

3 (3x 1)

1

mod x2 x 2

1 x2

5x 3 1 x2 x 2 1 2x

Алгоритм ЕВКЛИДА в Fpr

строим F 2

5

обратим

x2 x 2

3 2 1

(3x 1)2x 4 x 2

3 x 1

2

6 x

2 x

x 2

4 x 2

Проверка

3x 1 (4x 2) 2

неразложимости

f( x 0)

2

3x 4

2

3

f( x 1)

4

f( x 2)

3

2 3 1

f( x 3)

4

f( x 4)

2

2 3x 1 2(4 x 2)

1 2 3 3 (3x 1) 6(4x 2) 3 (3x 1) (4x 2)

откуда

4 x 2 ( x 2 x 2) (3x 1) 2 x

3 (3x 1) (x

2

x 2) (3x 1) 2x

2x 3 (3x 1) 1 x2 x 2 1

2x 3 (3x 1)

x 2

x2

* F52

25 1 24 элемента

2x 3 (3x 1) 1 mod ..

ЗАДАЧА:

Обратить элемент а+b+d

x1 x

элемент

x

x x 2 4x 3

не порождающий

(оцифровка α1х+α0) в

2

2

порядок элемента

x3 x(4x 3) 4x2 3x

8 4x

2

3 x 3

x

4

поле F 2

x4 x(4x 2) 4x

2 2x

(4x2

4x

8) x

2

x 3

2 x 2

3

2

2

4x 8) 2 x 8

(4x

5

x x(2x 2) 2x 2x (2x 2x 4) 4 4

1

x4 1

Полином

непрриводим

g(x) x7 x4 x3 x1 1

Оцифровать f(x)←(а+b+c+d) и Обратить по mod g

найти

? : f 1 mod g(x)