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

[Envelope]

Уверен, что не один я устал от метода "слепого перебора" зашифрованных пакетов.
Нет, идея, с перебором, конечно, классная, вот только реализация: типа клюквой пробить бетонный забор, короче, если все на форуме подключатся, то этот процесс (при условии обработки одного пакета в день одним пользователем) займет (грубо) 6*10^280 лет как вам такое положение вещей в пространстве?

Обладая, нашими сегодняшними технологиями, на дешифрацию 1024 битного ключа мы потратим энергию, равносильною появлению Сверхновой. Как думаете, есть у нас такие запасы на планете? <_<

Либы для клиента перебора написаны итак в большей степени на асме.
Но одного асма недостаточно. Нужен толковый алгоритм - это основное. Тогда, впринципе, хыть на Vb клиента напиши, все равно перебор быстрее идти будет.
Эта тема создана для поиска более эффективного алгоритма дешифрации, основанного на знаниях в области Высшей математики.

Я ПРОСТО НАСТАИВАЮ, ЧТОБЫ ВСЕ, КТО СЕЙЧАС ЗАНИМАЕТ СВОЮ ГОЛОВУ ТЕМ, КОГДА ЖЕ ЕГО МОНСТР-КОМП ОБРАБОТАЕТ ОЧЕРЕДНОЙ ПАКЕТ, ЗАНЯЛИ СЕБЯ ПОИСКОМ ИНФЫ В ИНЕТЕ И УЗУЧЕНИЕМ ВОПРОСА!!!

Народ, подключайте, всех, кого знаете, особенно, если у кого-то есть в знакомых преподы по Вышке. Объясните им, что вдруг заинтересовались криптографией - мол, прогу секьюрную пишете. Они только скакать от счастья будут - это именно то, о чем они мечтали всю свою преподавательскую деятельность - чтобы их трудами, наконец, кто-то заинтересовался, чтоб кому-то эта хрень стала интересна.

Короче, что я еще могу сказать... Дерзайте, тогда раскроем РСА!!! starwars_draka;

Зыы... Исходники клиента приложены в конце сообщения

[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 не должны быть слишком близки друг к другу
Возможно простые следует искать там итерируя в обе стороны от любой из указанных мной точек.
Поправьте меня, если я заблуждаюсь?