Начну с предыстории.
В те давние времена, когда Pentium 4 считался верхом технологической мысли, среди обычных людей того времени было развлечение на сайте bugtraq. Там оценивали стойкость хешей и шифров. Поначалу это была как игра, какая команда обработает больше блоков. Потом случились поступление в университет и работа. Но страсть к шифрам осталась и даже не собиралась уходить. С тех самых пор ваш покорный слуга «заболел» шифрами и всем, что с ними связано. Основную работу, как и увлечение разработкой электроники, при этом никто не отменял.
Шли годы, и чтобы поддерживать себя в форме, я занялся изучением свойств сверхбольших чисел. Это как хобби, даже день отдельное название получил — «RSA-день». Этот день я полностью и целиком посвящал опробованию новых теорий, написанию скриптов, изучению статей, новостей в интересующей меня области.
В один из таких дней мне попалась статья о разложении — факторизации с помощью квантовых компьютеров, знаменитый алгоритм Шора. Кому интересно, вот ссылка на Wiki. Суть алгоритма сводилась к нахождению периода, через который и находились множители сверхбольшого числа. В процессе размышлений над этой статьёй мне пришла в голову идея попробовать использовать синусоиду — основу и родоначальницу всех волн (связь во всех её видах, передача сигналов по проводам, по воздуху и под водой). Но было препятствие: частоты, которые имеют 100, 4000 десятичных знаков на современном уровне недоступны, и попытка получить резонанс не пошла дальше теории. Затем в один из вечеров мелькнула мысль: а не попробовать ли использовать периоды вместо частоты — они связаны, и единицы измерения не будут играть значение.
В своём хобби по изучению свойств сверхбольших чисел я наткнулся на интересный подход, связанный с использованием синусоид в контексте факторизации чисел RSA (получение границ поиска делителей).
Основное, что меня поначалу смущало, это огромные числа. Но к этому быстро привык в силу своей непрофессиональной недальновидности. Если система работает, то она работает и на малых числах. Изучал приближение периодов Т1 и Т2 для множителей по отношению к большому периоду синусоиды Т0. Сначала увидел, что система работает, в том плане, что если взять синусоиды с периодами Т1 и Т2 и отложить их на всю длину одиночной синусоиды с периодом Т0, то мы точно укладываемся в период Т0. Это и есть показательный график работы ключей RSA без всякой математики.
Вот пример, который я сделал для теста на матлабе — вы можете его использовать для проверки моих выводов.
% Задание периодов
% T1 * T2 = 5641 * 8429 = 47548189
T0 = 4757; % 4-значное число
T1 = 67; % 2-значное число
T2 = 71; % 2-значное число
% 6895 SQRT
% Создание массива значений по оси x
x = 0:0.1:T0;
% Вычисление значений синусоид
y0 = sin(2*pi*x/T0);
y1 = sin(2*pi*x/T1);
y2 = sin(2*pi*x/T2);
% Нахождение середины, пересечения с осью X, окончания графика, максимума и минимума для T0
mid_T0 = T0/2; % Середина графика
crossing_T0 = find(y0 == 0, 1); % Пересечение с осью X
end_T0 = length(x); % Окончание графика
[max_y0, max_idx] = max(y0); % Максимум на одном периоде
[min_y0, min_idx] = min(y0); % Минимум на одном периоде
half_period_end = find(y0(1:end-1).*y0(2:end) <= 0, 1); % Окончание полупериода
% Построение графиков
figure;
plot(x, y0, 'b-', x, y1, 'r--', x(1:end_T0), y1(1:end_T0), 'r--', x(1:end_T0), y2(1:end_T0), 'g:');
hold on;
% Отметка середины, пересечения с осью X и окончания графика для T0
plot(mid_T0, sin(2*pi*mid_T0/T0), 'bo', 'MarkerSize', 8);
plot(x(crossing_T0), 0, 'bx', 'MarkerSize', 8);
plot(x(end_T0), sin(2*pi*x(end_T0)/T0), 'b*', 'MarkerSize', 8);
% Добавление вертикальных линий для максимума и минимума на одном периоде T0
plot([x(max_idx), x(max_idx)], [min_y0, max_y0], 'b--');
plot([x(min_idx), x(min_idx)], [min_y0, max_y0], 'b--');
plot([x(half_period_end), x(half_period_end)], [min_y0, max_y0], 'b--');
legend('T0', 'T1', 'T2', 'Середина T0', 'Пересечение с осью X для T0', 'Окончание графика T0', ...
'Максимум T0', 'Минимум T0', 'Окончание полупериода T0');
xlabel('x');
ylabel('y');
title('Три синусоиды с отметками для T0');
grid on;В итоге получился вот такой график:
Два множителя точно укладываются на период их произведения.
Второй вопрос, который меня волновал при факторизации применительно к RSA, это с какого значения начинать и до какого числа идти.
Перебор в лоб меня не интересовал. Я искал более изящный метод. И вот наконец я его нашёл. Им оказалась всё та же синусоида.
Если построить график для значений синусоид, которые получаются при пересечении синусоид, то получается просто красота, всё встаёт на свои места. Если простыми словами, результат произведения мы знаем (по RSA) P*Q = N, ставим ограничение именно на это число N, берём корень от N и начинаем генерировать синусоиды с периодами от корня N вниз и вверх, не пропуская чётные числа. В итоге собираем данные для построения 2 графиков — с чётными значениями и нечётными. Объяснения выше понять трудновато, поэтому прошу проверить на матлабе.
Вот пример, который я использовал для вычисления координат.
% Заданные значения
T0 = 473717;%555817;%314791;
T1_start = 377;%477;%361;
T1_end = 1021;%877;%761;
% Создаём массивы для хранения результатов
even_results = [];
odd_results = [];
% Цикл по значениям T1 от 361 до 761
for T1 = T1_start:T1_end
% Вычисление значения синусоиды при x = T0
y = sin((2 * pi / T1) * T0);
% Добавление результата в соответствующий массив
if mod(T1, 2) == 0
even_results = [even_results; T1, y];
else
odd_results = [odd_results; T1, y];
end
end
% Сохранение результатов в файлы CSV
csvwrite('sinusoid_chetn_even_results.csv', even_results);
csvwrite('sinusoid_nechetn_odd_results.csv', odd_results);
% Вывод сообщения о завершении
fprintf('Even results have been saved to sinusoid_even_results.csv\n');
fprintf('Odd results have been saved to sinusoid_odd_results.csv\n');Результаты анализа графиков оказались удивительными. Ожидалось увидеть хаотичную картину, однако полученные данные показали чётко структурированные зависимости.
Ниже ссылки на результаты полученных данных в desmos.
Это для одних чисел.
Это для других чисел.
Подобных графиков раньше нигде не встречал и, честно говоря, был удивлён, как числовые значения чисел хорошо укладываются в границы. Теперь не надо в лоб перебирать все значения от 1 и корня из N. Нарисовал график для числа и ясно, где искать. Могу ошибаться, ведь как-то слишком просто это получается.
После краткого предварительного анализа, я так думаю (покажет дальнейшее исследование), что можно задать границы для поиска множителей справа относительно первого образованного овала — тот, что слева, и левее правого овала — тот, что справа.
Между ними это и будет область для поиска множителей чисел RSA, естественно, что область центрального горба тоже убирается из области для поиска.
Второй вывод, который я сделал (надеюсь, кто-то подтвердит или опровергнет мою версию) — это то, что вычислять каждое число не надо, достаточно идти от квадрата Т0 вниз по числовой оси, по пути прореживая числовые данные.
Например, мы можем взять корень RSA-100Т0=1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
SQRT_T0= 39020571855401265512289573339484371018905006900194.7844 => 39020571855401265512289573339484371018905006900195
И пройти вниз по числовому ряду, взять первую тысячу точек, т. е. от 39020571855401265512289573339484371018905006900195 до 39020571855401265512289573339484371018905006899195
Потом перескакиваем через 3 разряда влево, опять берём 1000 точек вниз-вверх и т. д. пока не дойдём до второго разряда слева нашего числа.
Стандартным методом быстро такие числовые расстояния не пройти, а этим методом можно. На выходе получим картину аналогичную.
Мнится мне, что точек будет гораздо больше на больших числах, и такое разряжение не окажет сильного влияния на общую картину графика.
Ещё раз прошу извинить за мой любительский вариант описания, я далёк от профессионального математика, но я старался как мог.
Это что касается определения границ поиска множителей конкретно для RSA.
В дальнейшем есть планы по изучению свойств числового ряда, которые мне неожиданно открылись. Узнать, есть ли зависимость при распределении на множителях, которые уже известны, есть ли паттерны малых чисел (до 10 разрядов), которые согласуются со сверхбольшими числами, почему горбы переворачиваются, от чего это зависит, изучить формирование первых десяти старших разрядов цифр множителей и много ещё чего интересного.
Буду благодарен за любые комментарии и указание на допущенные мной неточности или ошибки.
P.S. Я не профессиональный математик, я любитель математики. Не судите слишком строго.
Telegram-канал со скидками, розыгрышами призов и новостями IT ?
Комментарии (23)
uchitel
04.07.2024 14:10+4Любопытно, причем, не мне одному - уверен.
Попробуйте в следующий раз хоть немного формул и примеров с разъяснениями сделать, что бы тем кто не особо в теме было легче вникнуть. Код лучше на питоне делать, там и длинная арифметика и простой синтаксис. Для синусоид и больших чисел можно воспользоваться gmpy2 - удобный и простой пакетик.
А вообще, вы молодец, правильными вещами увлекаетесь. Человек, который берется за "нерешаемые" задачи так, словно они решаемы обладает незаурядными качествами.
wataru
04.07.2024 14:10Человек, который берется за "нерешаемые" задачи так, словно они решаемы обладает незаурядными качествами
При условии, что задачи не решенные, а "нерешаемые". Если про задачу доказано, что решения нет, то это просто трата времени себя и тех, кому непосчастливится читать "статьи" от таких людей. Вроде бедных сотрудников патентного бюро, читающих про очередной вечный вдигатель. Или вот недавно на хабре был кадр, который вообще любые данные научился сжимать.
alansbor Автор
04.07.2024 14:10+1Про задачу факторизации доказано только то, что она не решаема современными методами и тратить на нее время бесполезно. Вот и все что доказано. Но это же говорили и о шифре знаменитой Энигмы. Не правда ли ? В своих исследованиях и поисках, я пытаюсь найти решение более элегантное чем прямой перебор множителей пусть даже и ускоренный, но недостаточно.
wataru
04.07.2024 14:10Безусловно, я не спорил с вашей статьей, а лишь придрался к словам uchitel'я.
Если вам интересно, то есть метод основанный на эллиптических кривых. Он весьма быстрее тупого перебора. Кажется, смотря на небольшой набор весьма хаотичных графиков и чуствуя какие-то закономерности там, этот способ не переплюнуть.
alansbor Автор
04.07.2024 14:10+1Метод поиска на ЕС, не достаточно быстр, нельзя найти множители для 2048 битного RSA числа в течении часа хотя бы. Я и не стремлюсь его переплюнуть, ни в этом задача моих поисков и исследования. Моя задача попробовать найти решение этой давно застоявшийся проблемы. Это не смысл моей жизни, а хобби. :)
wataru
04.07.2024 14:10не достаточно быстр, нельзя найти множители для 2048 битного RSA числа в течении часа хотя бы
Ха, тут разговор о десятилетиях или веках должен идти, а не о часах. И это один из самых быстрых придуманных на сегодня методов. Все таки в этом суть шифрования и есть - взламывать его должно быть сложно. И смотрите, какая там вырвиглазная математика. Наивно думать, что смотря на графики у вас получится хотя бы так.
Я и не стремлюсь его переплюнуть, ни в этом задача моих поисков и исследования. Моя задача попробовать найти решение этой давно застоявшийся проблемы
Какой задачи? Если вы не хотите переплюнуть этот метод, то вы предложите худшее решение. Если вы хотите найти лечшее решение, то как вы при этом не хотите его переплюнуть?
uchitel
04.07.2024 14:10Главным качеством в некоторых отраслях является склонность к поиску идей. Когда к тебе приходит бизнес и говорит: хочу быстрее, больше и шоколаднее, то есть всего два ответа:
У вас и так топовый солвер и самые навороченные модели
Хорошо, сейчас подумаю
Что касается доказательств, то конечно есть вероятность, что бизнес купится на красивую, но полностью лживую презентацию. Но скорее всего, сразу попросят привести пример, подтверждающий наличие профита. За голые слова никто не заплатит (как правило). А платят порой слишком дохрена и прокачивание такого навыка стоит свеч.
wataru
04.07.2024 14:10Не понял, как графики синусов позволяют сократить перебор возможных делителей. Можно про это поподробнее рассказать?
То, что синус для "делителя" уложится в первые 2 горба синуса для делимого - интересный факт, но с свычислительной точки зрения, поделить нацело и посмотреть остаток гораздо проще.
alansbor Автор
04.07.2024 14:10Подсказка: я отметил в названиях графиков числа множителей и их произведение, они (множители) расположены все до описанного овала слева, если идти по числовой прямой в сторону обычной единицы. Добавьте точки множителей на ось абсцисс. Я пробовал с разными множителями, но все они были до овала слева. Чем не ограничение для поиска множителей.
wataru
04.07.2024 14:10До какого овала? То что вы пробовали на каких-то множителях, еще не является никаким доказательством. Эти точки вообще довольно хаотично разбросаны. Вы попробуйте множители не очень близкими к корню брать, там овалов может быть несколько, вообще не быть, да и расположены они могут быть много где.
Например, если вы овалом называете сине-зеленую, относительно пустую внутри область, то на последней картинке в статье его вообще нет.
alansbor Автор
04.07.2024 14:10+1Вы наверно не знакомы с полным перечнем требований при формировании ключей для RSA. Поэтому и говорите, что может быть где угодно. Но это не совсем так. Я поищу у себя полный перечень требований для формирования безопасных ключей RSA, если вы сами его раньше не найдете. Может быть тогда всё встанет на свои места.
wataru
04.07.2024 14:10Там точно есть требование "делители не должны быть очень маленькие или очень близко к корню.
ValeriyPushkarev
04.07.2024 14:10Тут, видимо, хотели прийти к тому, что если вы выполняете операцию N mod k1, и получаете какое-то значение, вы можете выполнить N mod k1-1 (и посмотреть, не сделали ли вы "оборот" при вычислении mod, если нет - пропустить до k1 значений при переборе, т.к. зависимость остатка от деления - линейная функция).
Из минусов - примерно та же сложность, что и просто перебрать SQRT(N) значений.
Вот пример вычисления множителей для 21 за 2 действия (в классическом переборе - 3):
ValeriyPushkarev
04.07.2024 14:10Лучшее, что вы можете сделать - посчитать количество получающихся значений в каждой группе (и даже попробовать соорудить двоичный поиск - если количество цифр в группе больше 1 - уменьшаем значение, если <=1 - увеличиваем)
wataru
04.07.2024 14:10N mod k1, и получаете какое-то значение, вы можете выполнить N mod k1-1 (и посмотреть, не сделали ли вы "оборот" при вычислении mod, если нет - пропустить до k1 значений при переборе, т.к. зависимость остатка от деления - линейная функция).
Можно по-подробнее?
Что значит, не сделали "оборот"? Что не изменилась целая часть в частном? И как это позволяет пропускать числа?
ValeriyPushkarev
04.07.2024 14:10Давайте представим:
вы получаете остаток от деления на N, затем на N-1. вы все еще движетесь по воображаемому циферблату c N (N-1) цифрами (на котором обычно и обьясняют концепцию mod).
вы прошли M цифр, и до сих пор не сделали шаг через 0 (выше на картинке N с 11 до 10).
Пока вы не перешли этот воображаемый 0 - вы движетесь с постоянной скоростью V, где V - количество раз, когда вы пересекли воображаемый 0.
Поэтому цифры во втором ряду имеют линейную зависимость (остаток от деления). Сначала остаток от деления растет на 1 при изменении делителя на 1, затем - на 2.
Интереснее второй концепт:
Двоичный поиск. Дело в том, что множитель похоже совпадает с местом перехода от нескольких ходов без пересечения 0 до нескольких пересечений нуля за 1 ход.
Оба этих состояния легко проверить за конечное время.
wataru
04.07.2024 14:10Ясно, тут рассматривается значение частного. При фиксированном частом k, если N=d*k+r, то r=N-d*k. Поэтому при увеличении делителя d, имеем линейную зависимость остатка k. "Пересечение нуля" тут - это уменьшение частного.
Т.е фактически, вместо перебора делитея d, вы перебираете оставшийся делитель N/d, значений у которого ровно столько же - sqrt(N).
Т.е. ничего это не изменило вообще.
Что касается бин поиска, то вам надо найти точку, где "переход через 0" даст остаток 0. Но во время проверки произвольного числа вы никак не можете определить, был ли этот переход раньше или его не было, так что бин поиск тут не работает.
Arastas
04.07.2024 14:10+1Это как хобби, даже день отдельное название получил — «RSA-день»
Скажите, а что вы делаете, если не удалось за день уложиться, или какая-то хорошая идея пришла под конец дня? Откладываете мысль в долгий ящик, до следующего дня хобби?
heavy87
04.07.2024 14:10+1Я как-то заморачивался по поводу фазового АЛУ, принцип действия которого основан на интерференции синусоидальных сигналов, источником которых являлся один единственный генератор, но которые сдвинуты относительно друг друга на N градусов. Вроде как создание такого АЛУ возможно в области ВЧ на полосковых линиях, которые можно разместить керамике. Такое АЛУ можно, как я полагаю, использовать как вспомогательный вычислительный модуль, подключаемый к обычному компьютеру.
inetstar
04.07.2024 14:10Знали бы вы, что дальше планирую на счет эллиптических кривых после RSA
Вы имеете ввиду факторизацию на основе эллиптических кривых или взлом самих эллиптических кривых?
MAXH0
Вот у меня всегда было подозрение. Все расчеты устойчивости шифра даются на обычные компьютеры. НО за скобками остается возможность, что возможен некий аналоговый процессор резко сужающий перебор...
Это подозрение ни на чем не основано. Точнее моё подозрение - это интерференция истории "Энигмы", которой долго торговали с явной уязвимостью, и истории PGP.
alansbor Автор
Да, аналоговые компьютеры были заброшены в России, а зря. Знали бы вы, что дальше планирую на счет эллиптических кривых после RSA, там тоже аналоговые схемы.