Кармайкловы числа имеют по меньшей мере три простых положительных множителя.
Первые кармайкловы числа с четырьмя простыми множителями:
1			561,														Числа КАРМАЙКЛА
2			1105,
																		псевдопростое
3			1729,
4			2465,															bn 1	1mod n
5			2821,
																			b нод n, b 1
6			6601,
7																			число
			8911,
																			кармайкла
8			10585,
9			15841,														i		Первые числа Кармайкла из 4х чисел
10			29341,
11			41041,														1
12			46657,														2
13			52633,														3
14			62745,													а
															л		4
15														к
			63973,										й
												а					5
16											м
										р
			75361,а
17			…					а	К								6
							л
18						с
					и												7
19			е	ч
		ы															8
	в
20р
е																	9
П
21

k

3

4

5

6

7

8

9

	Технология ЭЛЕКТРОННЫХ
	платежей (Master card)
	x	случайное	RSA банк
	Aвыбирает
		x Zn число	открыт
	Aвычисляет f (x)		n p q
			(n) p 1 q 1
		Односторонняя функция
			секретно
			секретно
			e открытый Ключ d Закрытый Ключ

случайное

Aвыбирает r число

нод(r; n) 1

Aвычисляет«затемняющий» МНОЖИТЕЛЬ

y f (x) re(mod n)

y банк

банк

Введение в криптографию 2

Семейство алгоритмов над конечными полями (RSA)

m ( p q) 1 mod n

Криптосистема RSA

выбираются p, q простые	m	t ( p q)	1 mod n
сверхсекретны
вычисляется (n) ( p 1)(q 1) : секретно
вычисляется n pq : открыт

берётся e : нод(e; (n)) 1 : Ключ ШИФРОВАНИЯ (открытый)

открыт

вычисляется d : e d 1mod (n) : Ключ ДеШИФРОВАНИЯ( сверхСЕКРЕ ТЕН / ЗАКрыт)

работа	открыт
Шифрованный текст
Расшифровка	c me mod n
	m1 mod n
	(me )d mod n	e	)	d	mod n ed
	m cd mod n
	(m					mod n
	m1mt ( p q) mod n				m
m1 t
	( p q) mod n	m11t mod n m

Задачи

•Закодировать Отчество шифром цезаря

•Гаммировать Имя (+Отчество) Фамилией

•Гаммировать Фамилию Сл. Последовательностью (генерировать на калькуляторе (или в экселе)).

•*Провести частотный анализ текста в Экселе

2	3	5	7	11	13
17	19	23	29	31	37
41	43	47	53	59	61
67	71	73	79	83	89
97	101	103	107	109	113
127	131	137	139	149	151
157	163	167	173	179	181
191	193	197	199	211	223
227	229	233	239	241	251
257	263	269	271	277	281
283	293	307	311	313	317
331	337	347	349	353	359
367	373	379	383	389	397
401	409	419	421	431	433
439	443	449	457	461	463
467	479	487	491	499	503
509	521	523	541	547	557
563	569	571	577	587	593
599	601	607	613	617	619
631	641	643	647	653	659
661	673	677	683	691	701
709	719	727	733	739	743
751	757	761	769	773	787
797	809	811	821	823	827
829	839	853	857	859	863
877	881	883	887	907	911
919	929	937	941	947	953
967	971	977	983	991	997

Взять (по таблице простых чисел) число

простое число р № b+a+d (фио)

До 1000

Обратить по данному модулю число а+b+c+d

	Q/P	3		5		7		11	13 17 19			23	29	31	37	41
	2	6		10		14	0	22	26	34	38	46	58	62	74	82
	3	9		15		21	0	33	39	51	57	69	87	93	111	123
	5	15		10		14	0	55	65	85	95	115	145	155	185	205
				25		35
	3	21		15		21	0	77	91	119	133	161	203	217	259	287
	7			35		49
	11	33		55		77	0	121	143	187	209	253	319	341	407	451
	5	15		25		35	0 55		65	85	95	145		185		533
	13	39		65		91	0	143	169	221	247	299	377	403	481
	17	51		85	119		0	187	221	289	323	391	493	527	629	697
	7	21		35		49	0	253	299	9	437	529	667	713	851	943
	23	69	115		161					391
	29	87	145		203		0	319	377	493	551	667	841	899	107	1189
															3
	31	93	155		217		0	341	403	527	589	713	899	961	114	1271
															7
	13	39		65		91		3		1			107		136
	37	111	185		259		0	407	481	629	703	851		1147		1517
													3		9
	17	51		85119			0	7	611	9	893	1081	136	1457	173	1927
	47	141	235		329			517		799			3		9
	53	159	265		371		0	583	689	901	100	1219	153	1643	196	2173
											7		7		1
	59	177	295		413		0	649	767	100	112	1357	171	1829	218	2419
										3	1		1		3
	61	183	305		427		0	671	793	103	115	1403	176	1891	225	2501
										7	9		9		7
	67	201	335		469		0	737	871	113	127	1541	194	2077	247	2747
										9	3		3		9
	37									9	134		205		262
										120

Протокол Kerberos / Цербер

KAС

н

ы

й

й

р

о

ч

н

с

н

г

о

ё

л

л

о

е

д

Д

а з

Р

с

В

A

н

и

е

е

щ

б

о

ь

т

е

е

м

и

A

М

A, А

е

т

-

B, N

е

л

а

ж

к	л
	с

т	к	а

ч

С

Д

ю

сервер

а

т

Р

е

о

л

р

з

к

дг

л

е

о

KBС

ёр

е

с

н

о

н

ч

ын

й

ы

с

й

е

к к

р

л

я

е

ч

щ

тю

е

н

и

B

б

о

о

С

С

n

Mod 10

			Кратные 2
0	1	2	3	4	5	6	7	8	9
		остатки				Кратные 5
									модуль
		(n)		2 1 5 1					10
		(10) 4

10 2 5

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

y2 x3 ax b				дискриминант≠0
Где	x3 ax b			27a3 9b
Взаимно прост С
3x	2 a
своей Формальной
	производной
нод(x3 ax b;3x2			a) 1
y2	x3 2x 2		p 5	нод(x3 2x 2;3x2 2) 1
	A(0,2)	O
точки
A( )(0, 2)		B(1,0)
			=
	=	B( )(1,0)

A( )(0,3)

Пусть p=7,q=11

n 7 11 77

(n) (7 1)(11 1) 6 1060

возьмём	e 13	тогда	d 37 :	37 13 481	1
				370 111	480 1