Алгоритм Диффи-Хелмана.

57. (~1 задача)Алгоритмом Диффи-Хелмана использовав ,, закодировать и раскодировать. Использовать(для облегчения расчёта применять). Можно применять модуль, или больший.

АлгоритмRsa

58. (1 задача) (RSA-33)АлгоритмомRSAзашифровать и расшифровать первую букву фамилии в диапазоне от 2 до 31. Исключения 11, и 22. Если буква не подходит взять первую подходящую от начала фамилии, - сначала проверить вторую (и т.д.) Исключения 11, 22 и 21 и 12. (для облегчения расчёта применять).

59. (2 задачи)(RSA51) АлгоритмомRSAзашифровать и расшифровать первую букву фамилии в диапазоне от 2 и более. Если буква не подходит взять первую подходящую от начала фамилии, - сначала проверить вторую (и т.д.) Исключения 13 и . (для облегчения расчёта применять).

Ключ шифрования , ключ дешифрования находится алгоритмом Евклида

(32 – значение функции Эйлера от 3*17=51)002E

60. («RSA»997)(1-2 задачи) Имитируя алгоритмRSA(практически требуется составной модуль, мы используем простой) закодировать начальные буквы фамилии имени отчества разбить на два блока по три цифры (второй 10-ки, 1й - единицы), первый зашифровать и расшифровать. Зашифровать, возведя в 797 степень, ДЛЯ !ПРОВЕРКИ!! расшифровать, возведя в 5ю:(для облегчения расчёта применять). Например, Иванов Иван Николаевич, ИИН→101012→002+111→шифруем Т=002. Менделеев Дмитрий Иванович

М	1	4
Д	0	5
И	1	0

Шифруем текст Т=450.

61. Другой вариант выполнить то же с текстом Т=100a+10b+с (где все цифрыa,bиcвзяты в стандартном представлении - от 1 до 9). Если результат больше 994 - аннулировать цифруa, т.е. убрать - старший разряд.

62. Алгоритм Масси-Омуры для того же блока mod997,(mod996).

63. Алгоритм Масси-Омуры для того же блока первых букв фамилии и имени mod97,(mod96).

Лабораторная в Экселе: ВзломRsa: алгоритм квадратичного решета для факторизации составного модуляRsa.

Теория метода квадратичного решета.

Простейший алгоритм факторизации целых чисел подразумевает проверку делимости на все сомножители до

Сложность алгоритма

Пусть нам настолько повезло, что мы нашли число А, квадрат которого по модулю составного числа N=pq(а такие числа используются в системе шифрования с открытым ключомRSA) есть тоже некий (но другой) квадрат.

,

проводя эквивалентные преобразования

это возможно в трёх случаях

1) делится на

2) делится на

3) делится наиделится наили наоборот. 3-й случай - то, на что мы и рассчитываем пытаясь построить полный квадрат.

В этом случае алгоритмом Евклида за приблизительно линейное время ищется НОД одного из двух чисел

или

с модулем pq:

илирезультатом будет один из сомножителейили. ДелениемNна найденный сомножитель найдем второй сомножитель, что даст вычислить значение функции Эйлера,:

(для этого нам надо знать разложение на множители), что даст возможность обратив алгоритмом Евклида открытый ключ шифрования е, вычислить закрытый ключ dи позволит читать секретную переписку (рассекретит алгоритм).

Впрочем, надо иметь ввиду, что на этом пути нам может не повезти, и не повезёт, но у нас есть возможность ПОПЫТАТЬСЯ создать полный квадрат из некоторых чисел вида

,

На практике берут столбец чисел ,, где- постепенно увеличиваемый параметр.

,

Если .

То мы имеем ситуацию

и

, где

В общем случае может потребоваться более двух сомножителей

, причём понятно, что любое произведениеесть уже квадрат, нетривиальной проблемой остаётся создать комбинацию чисел вида..=.

Для решения этой проблемы малые в силу близостик корню изN:

числа разлагают на простые со-множители. Предполагают, что рассматриваются только М-гладкие числа, то есть те числа, которые имеют очень простое разложение – в котором есть простые сомножители размера не более М (М-гладкие). По вектору степеней можно понять какие степени нечётные – какие сомножители непарные.

Для этого используются вектора степеней взятые по модулю 2, из них составляются подбором коэффициентов суммы которые образуют четные вектора – полные квадраты.

64. Методом квадратичного решета разложить составной модуль алгоритма RSAсоставленный из двух простых чисел, отличающихся друг от друга на величину кратную 2 3 или 5 в некоторых степенях, разность должна быть четной не менее 16 или 20:,.

В ответе вычислить закрытый ключ, считая открытым ключом d=3 (для модулей кратных 3, 3ка не может быть ключом, поэтому взять 5). Для этого вычислить функцию Эйлера,(вспоминаем как считается функция Эйлера).

Например, 64, 32, 60

Устроят числа ,, или,

8. Разложить число на множители, подобрав полный квадрат, составленный из остатков квадратов в одиночку полный квадрат не составляющих.

Пример

Видимы два способа составить полный квадрат

1й

образуют полный квадрат

,

,составим

откудаи

Ищем наибольший общий сомножитель 69 и 46 алгоритмом Евклида:

откуда после деля 69 на 23 находим второй сомножитель 3, что позволяет рассчитать функцию Эйлера

(23-1)(3-1)=44 и

по открытому ключу вычислить закрытый ключ. Для иллюстрации возьмём открытый ключ шифрования e=5 и вычислимd=e^-1mod44

44=8*5+4

5=4+1

Обратный проход

1=5-4=5-(44-8*5)=9*5-44=5*9mod44

Отсюда ключ дешифрования d=9 (он позволяет читать всю секретную переписку).

Второй способ взять 5 6 и 9

Числа образуют полный квадрат

Перемножаем

9. Для выбора первого простого числа предлагается выбрать столбец по номеру d, строку поamod7. Второе число выбирается исходя из выше указанного требования

Таблица простых чисел

Первое число выбираем по номеру d

1 2 3 4 5 (dmod5)

3 5 7 11 13 число р

Число qполучается прибавлением числаxиз столбца к числу р:

q=x+p

1 2 3 4 5 (если результат не прост (циклический)сдвиг вправо)

16, 32, 64, 128, 144 (amod5) первое числоq

q1=x1+p,N1=pq1

24, 36, 48, 96, 72, (bmod5) второе числоq

q2=x2+p,N2=pq2

40, 80, 120, 100, 160(cmod5) третье числоq

q3=x3+p,N3=pq3

В лабораторной надо разложить три модуля

Вариант II

Первое число выбираем по номеру d(в числеdдо взятия модуля 10ка не откидывается)

1 2 3 4 5 6 7 8 9 (dmod9)

3 5 7 11 13 17 19 23 29 число р

q1=ab+min

q2=cd+min

q3=100+da+min

при этом нами предполагается, что в сочетаниях abcdиdaв первой цифре 10ка никогда не откидывается т.е., например, при а=13b=7 правильно писать 137, а не 37, но при а=13b=10=1 вы можете взятьq1=ab+min= 131+min=131

В данном случае числа q1=137 (как иq1=131)простые, но, как правило это не так: например, при а=9 иb=8 получилось бы числоq1=98 – оно явно нам не подходит в качестве простого, и тогда бы мы просмотрев числа 99 и 100 остановились бы на ближайшем простом, не меньшем данного - 101.

РЕШАЕТСЯ в ЭКСЕЛЕ:

Разложим число 77

Корень около 8

Строим арифметическую прогрессию +-1 от 8 (столбец А)

Строим рядом столбец А*А

Вычитаем раскладываем составной модуль N

	А	А2	АА-N=t	Разложение t	Не квадратичная часть разложения t
	3	9	-68
	4	16	-61
	5	25	-52	*-1*2*2*13	*-1*13
	6	36	-41
	7	49	-28		*-1*7
КОРЕНЬ!!!	8	64	-13	*-1*13
	9	81	4	*2*2	1
	10	100	23	23	23
	11	121	44		11
	12	144	67
	13	169	92	*2*2*23	23
	14	196	119
	15	225	148

Группы, образующие полные квадраты выделены одним цветом.

Вариант1
А=5*8=	40		А+В=	66	НОД(А+В,N)=	11
В=13*2	26		А-В=	14	НОД(А-В,N)=	7
				Алгоритм взломан:

Нам повезло мы получили разложения числа. (Вообще, вероятность 50%, что сомножители числа Nокажутся в разных компонентах (А-В)* (А+В))

Вариант2
А=10*13=	130		А+В=	176	НОД(А+В,N)=	11
В=23*2	46		А-В=	84	НОД(А-В,N)=	7
				Функция Эйлера (11-1)(7-1)= =10*6=60

Здесь мы тоже получили разложение.

Вариант III()

Берётся число из таблицы сумм квадратов (сумма квадратов всегда нетривиально разлагается методом квадратичного решета - это легко доказуемый аналитический факт).

ВНИМАНИЕ: для разложения берётся только число пригодное быть модулем в ассиметричной системе шифрования.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324
4								85
9				34		58							205		265
16						65						185			272	305
25													221				349
36						85		117				205		261
49			65		85								245		305
64								145		185
81	85				117		145										405
100										221
121							185		221		265				377		445
144		153				193				265
169			185		205								365				493
196		205		221		245						365				485
225					261						369				481		549
256		265				305				377				481		545
289	293	298	305	314	325	338	353	370	389	410	433	458	485	514	545	578	613
324	328	333	340	349	360	373	388	405	424	445	468	493	520	549	580	613	648
361	365	370	377	386	397	410	425	442	461	482	505	530	557	586	617	650	685
400	404	409	416	425	436	449	464	481	500	521	544	569	596	625	656	689	724
441	445	450	457	466	477	490	505	522	541	562	585	610	637	666	697	730	765
484	488	493	500	509	520	533	548	565	584	605	628	653	680	709	740	773	808
529	533	538	545	554	565	578	593	610	629	650	673	698	725	754	785	818	853
576	580	585	592	601	612	625	640	657	676	697	720	745	772	801	832	865	900
625	629	634	641	650	661	674	689	706	725	746	769	794	821	850	881	914	949
676	680	685	692	701	712	725	740	757	776	797	820	845	872	901	932	965	1000
729	733	738	745	754	765	778	793	810	829	850	873	898	925	954	985	1018	1053
784	788	793	800	809	820	833	848	865	884	905	928	953	980	1009	1040	1073	1108
841	845	850	857	866	877	890	905	922	941	962	985	1010	1037	1066	1097	1130	1165
900	904	909	916	925	936	949	964	981	1000	1021	1044	1069	1096	1125	1156	1189	1224
961	965	970	977	986	997	1010	1025	1042	1061	1082	1105	1130	1157	1186	1217	1250	1285
1024	1028	1033	1040	1049	1060	1073	1088	1105	1124	1145	1168	1193	1220	1249	1280	1313	1348
1089	1093	1098	1105	1114	1125	1138	1153	1170	1189	1210	1233	1258	1285	1314	1345	1378	1413
1156	1160	1165	1172	1181	1192	1205	1220	1237	1256	1277	1300	1325	1352	1381	1412	1445	1480
1225	1229	1234	1241	1250	1261	1274	1289	1306	1325	1346	1369	1394	1421	1450	1481	1514	1549
1296	1300	1305	1312	1321	1332	1345	1360	1377	1396	1417	1440	1465	1492	1521	1552	1585	1620
1369	1373	1378	1385	1394	1405	1418	1433	1450	1469	1490	1513	1538	1565	1594	1625	1658	1693
1444	1448	1453	1460	1469	1480	1493	1508	1525	1544	1565	1588	1613	1640	1669	1700	1733	1768
1521	1525	1530	1537	1546	1557	1570	1585	1602	1621	1642	1665	1690	1717	1746	1777	1810	1845
1600	1604	1609	1616	1625	1636	1649	1664	1681	1700	1721	1744	1769	1796	1825	1856	1889	1924
1681	1685	1690	1697	1706	1717	1730	1745	1762	1781	1802	1825	1850	1877	1906	1937	1970	2005
1764	1768	1773	1780	1789	1800	1813	1828	1845	1864	1885	1908	1933	1960	1989	2020	2053	2088
1849	1853	1858	1865	1874	1885	1898	1913	1930	1949	1970	1993	2018	2045	2074	2105	2138	2173
1936	1940	1945	1952	1961	1972	1985	2000	2017	2036	2057	2080	2105	2132	2161	2192	2225	2260
2025	2029	2034	2041	2050	2061	2074	2089	2106	2125	2146	2169	2194	2221	2250	2281	2314	2349
2116	2120	2125	2132	2141	2152	2165	2180	2197	2216	2237	2260	2285	2312	2341	2372	2405	2440

10. Например, человек с номером 7135берёт 7 строку 5 столбец число 389 из него вычитает 89 получает 300 которое удовлетворяет условию. Т.е. его задача разложить

11. Пример 3*43=129 рядом стоящие квадраты 121=-8~-2,144=15mod129, 169=40mod129~10, 196=67mod129, 225=96mod129~6, 100=-29,81=-48~-3, 64=-55mod129,

Из чисел -2,-3 и 6 получается полный квадрат:36 точнее ,,,,

,

1. Пример 167*967=161489 квадратный корень