Лабораторная в Экселе: Взлом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

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

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

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

Вариант III()

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

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

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 квадратный корень