Обсуждение Алгоритмов Дешифрации Ключа, Нужны свежие идеи - нельзя долго копать Поделиться Опции

[santilo]

А можно ли подписать своим RSA ключом и переделать бут, чтоб он проверял мою RSA

[Vilko]

Osta,
Нет
santilo,
Нет

[DmT]

Как вы конечно знаете (а если не знаете, дак узнайте здесь) в алгоритме RSA используются публичный и секретный ключи.
Открытый ключ - это пара (e,n)
Секретный ключ - это пара (d,n)
где e - открытая экспонента, d - секретная, а n - это произведение двух простых чисел p и q
Очевидно, что для получения секретного ключа не хватает только d, поскольку n мы всегда знаем.

Код

e*d mod Phi(n) = 1

где Phi(n) - это функция Эйлера
Как вы понимаете для её вычисления необходимо искать простые сомножетели(те самые p и q). А это что называется "дофига делов" учитывая, что длинная аргумента - 1024 бита (Это 2^1024 значений)
Но недолго повтыкав повникав вместе с товарищем motoprogger'ом вот в эту картинку пришли к выводу, что видим линейные зависимости и отклонения от них.
Родилась идея:
статистически узнать характер отклонений
и расчитывать функцию эйлера полагая, что результат будет находиться в одной из дельта областей отклонений от линейно-зависящих значений (их количество надо уточнить, motoprogger утверждает, что видит 2+2, а я 3+3, а при большем исследовании вообще может отличаться результат)
Или проще говоря внутри кольца радиусом наибольшего среднего статистического отклонения от точек на каждом линейном луче на этом графике.
(+ еще можно эверистик натыкать)

Тогда алгоритм такой:
1. полагаем что нашли Phi(n)
2. вычисляем

Код

d = 1/(e mod Phi(n)) + N*Phi(n)

для целых N от 1 до ??? (предположительно до e) и учитывая рекомендации по выбору d (скорее всего это разумное время)
3. проверяем выполнение равенства

Код

a^(e*d)=1 (mod n)

Каждое a, для которого это равенство выполнено, даёт право считать вероятность ошибки вдвое меньшей
В то же время любое a, не равное нулю и взаимно простое с n, для которого это равенство не выполнено, прямо указывает на неправильное нахождение

Таким образом в какой-то то момент времени либо станет ясно, что надо выбрать другие d и Phi(n), либо текущее d - является секретной экспонентой.

У кого какие мысли есть по поводу этого метода?

Добавлено позже (14.1.2011, 2:07):
одну из тем надо снести (это я к модераторам обращаюсь)

[Osta]

может бритву Оккама проще?

[DmT]

Можно подробнее?

[Джуманджи]

«Бритва О́ккама» или «лезвие Оккама» — методологический принцип.

Некоторые из его примеров:
"Самое простое решение - наиболее часто верное, самое верное решение - наиболее часто простое."

"Всё следует упрощать до тех пор, пока это возможно, но не более того."

"Не следует привлекать новые сущности без самой крайней на то необходимости."

Сообщение отредактировал Джуманджи - 13.1.2011, 22:45

[DmT]

Преамбула: поскольку на мотофане много умных людей (я правда в это верю) я хочу кое-чем поделиться с вами, уважаемые форумчане.
В дополнение к моему сообщению 3 постами выше расскажу, что я сегодня понаразмышлял
1. Функция Эйлера
Как я уже говорил, на википедии есть картинка илюстрирующая распределение функции Эйлера.
И сначала мне показалось, что это распределение можно использовать для приближенного вычисления функции. В принципе это и так и не так.
Загвоздка в том что на википедии показано распределение для любых n, а нас интересуют только такие числа n, которые имеют следующие свойства: не простые, не имеют маленьких делителей, не имеют делителей близких к корню из n (об этом позже).
в результате построения графика по полученым результатам (отсеяв неподходящие числа) я увидел прямую(ну почти прямую).
В принципе внимательный читатель при чтении алгоритма RSA и функции эйлера сразу поймет почему получилась прямая. А вот до меня это доходило достаточно долго.
Суть в том, что при n = pq где p и q - простые
функция Эйлера Phi(n) = (p-1)(q-1), а при больших p и q
pq ~= (p-1)(q-1)
то есть разница то получается не большой.
Но тут как посмотреть...
Надо эту разницу формализовать. А точнее отношение.
T = n/Phi(n) = pq/((p-1)(q-1)) = 1/((p-1)(q-1)/pq) = 1/((pq - p - q - 1)/pq) = 1/(1 - 1/q - 1/p - 1/pq)
ну и как бы понятно, что чем ближе p и q к "большим" порядкам тем отклонение меньше.
Но вот какая интересная штука получается на практике.

Как вы видите существует множество различных ярковыраженных кривых отклонений.
Я заметил, что каждая из этих отдельных кривых соответствует уникальному делителю. То есть есть множество чисел, для которых делителем является например число 101, и все отклонения для этих чисел будут лежать на одной и той же гиперболе. А для множества чисел у которых минимальный делитель 107 - все отклонения будут лежать на другой гиперболе, но внутри своего множества все свойства сохраняются.
Ссылка на xls файл с таблицей и графиком, которые я анализировал. http://dl.dropbox.com/u/3506908/rsa/anls_1.xls
Дак вот, как видно по картинке полоса отклонений (то есть разности минимального и максимального отклонений для рассматриваемого подмножества чисел) для чисел порядка 500000 составляет 0,0102. Разумеется нужно расширенное исследование этой ширины, но если предположить, что полоса остается примерно такой достаточно долго (до наших лимитов в 2^1024), то самый худший перебор обойдется нам в 0.0102*n*e (e - открытая экспонента, читать выше), а это неприлично долго (хотя учитывая специфику вероятностной проверки такая сложность практически никогда не достижима, все равно порядки огромные).
Это заставляет меня обратиться к вам, форумчане, за помощью в прогнозировании отклонения T. Мне кажется есть наиболее простой, чем факторизация способ.
Вообщем как угадать как пойдет гипербола, или как уменьшить ширину полосы отклонений.

2. Маленький размышлизм на тему разложения на простые сомножители.
Я предполагаю, что оптимальная зона поиска простых сомножителей находится в окрестностях точек
корень_из(n)/2 и (n+корень_из(n))/2
Это предположение основано на двух тезисах из рекомендаций по выбору простых:
1) p и q не должны быть слишком маленькими
2) p и q не должны быть слишком близки друг к другу
Возможно простые следует искать там итерируя в обе стороны от любой из указанных мной точек.
Поправьте меня, если я заблуждаюсь?

[DmT]

UPD
В предыдущем сообщении изображен график отклонений n/Phi(n) для n не простых и с минимальным делителем >= 100
вот график отклонений для n, где
n = pq, где p и q - простые (исключительно такие n нас интересуют)

видите как сходится хорошо, монотонно)
Надо эту кривульку аппроксимировать. Какие идеи? Могу выложить таблицу значений если кто-то возьмется за аппроксимацию.

UPD
придумал я, что сделать

[19:51:41] <dmt021> продифференцировать функцию
[19:52:02] <dmt021> с некоторым шагом dn
[19:53:16] <dmt021> на ширине шага dn отсортировать все точки графика (результаты функции T)
[19:53:36] <dmt021> взять несколько максимальных и минимальных
[19:53:51] <dmt021> взять их среднее значение
[19:55:29] <dmt021> Построить два новых графика
[19:56:17] <dmt021> таким образом мы отфильтруем «лишние» значения T(n)

UPD
придумал новую эверистику
положи
p = корень_из(n)/2
q = 2*корень_из(n)
(так чтоб pq = n)
теперь посчитаем отношение: q/p = 2*корень_из(n)/корень_из(n)/2 = 4.
то есть отличаться p и q должны в 4 раза (в сферическом вакуме)
Но надо посмотреть что будет с графиком при таких распределениях сомножителей

Сообщение отредактировал DmT - 15.1.2011, 23:42

[DmT]

UPD
использовал новую эверистику для построения графика.
Получилось интересно.
Вот так выглядит график для малых n

Большая картинка

[close]

А вот так для больших.

Большая картинка

[close]

Правда похожи? отличаются они только плотностью заполнения (на втором графике смотрится совсем как непрерывная функция, в отличии от первого) и порядком дробной части значения функции.
Надо проверить стабильность для других вероятных областей расположения p и q и если все ок - надо аппроксимировать(а с такими графиками это легче и точнее, чем с теми, что наблюдались на картинках выше). А потом можно и тестовый алгоритм закодить и потестить для малых длинах ключей.

UPD
Кто знает, как проверить рекурсивно аппроксимируемую функцию?

UPD
На 19.01 исследования продвинулись в значительной степени. Приостановлены до 23.01.

Сообщение отредактировал DmT - 19.1.2011, 13:53

[DmT]

Пришла в голову вдруг идея:
Делаем таблицу чисел Y = P*Q, где P и Q - простые числа до некоторого размера.
Затем проверяем не совпадают ли младшие разряды числа n (если кто не знает что такое n - выше написано) с одним из чисел Y.
Если вдруг младшие разряды ВНЕЗАПНО совпадут - значит младшие разряды p равны P, а младшие q равны Q. Гарантировано.