Начну с предыстории.
В те давние времена, когда 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.csvn');
fprintf('Odd results have been saved to sinusoid_odd_results.csvn');Результаты анализа графиков оказались удивительными. Ожидалось увидеть хаотичную картину, однако полученные данные показали чётко структурированные зависимости.
Ниже ссылки на результаты полученных данных в desmos.
Подобных графиков раньше нигде не встречал и, честно говоря, был удивлён, как числовые значения чисел хорошо укладываются в границы. Теперь не надо в лоб перебирать все значения от 1 и корня из N. Нарисовал график для числа и ясно, где искать. Могу ошибаться, ведь как-то слишком просто это получается.
После краткого предварительного анализа, я так думаю (покажет дальнейшее исследование), что можно задать границы для поиска множителей справа относительно первого образованного овала — тот, что слева, и левее правого овала — тот, что справа.
Между ними это и будет область для поиска множителей чисел RSA, естественно, что область центрального горба тоже убирается из области для поиска.
Второй вывод, который я сделал (надеюсь, кто-то подтвердит или опровергнет мою версию) — это то, что вычислять каждое число не надо, достаточно идти от квадрата Т0 вниз по числовой оси, по пути прореживая числовые данные.
Например, мы можем взять корень RSA-100Т0=1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
SQRT_T0= 39020571855401265512289573339484371018905006900194.7844 => 39020571855401265512289573339484371018905006900195
И пройти вниз по числовому ряду, взять первую тысячу точек, т. е. от 39020571855401265512289573339484371018905006900195 до 39020571855401265512289573339484371018905006899195
Потом перескакиваем через 3 разряда влево, опять берём 1000 точек вниз-вверх и т. д. пока не дойдём до второго разряда слева нашего числа.
Стандартным методом быстро такие числовые расстояния не пройти, а этим методом можно. На выходе получим картину аналогичную.
Мнится мне, что точек будет гораздо больше на больших числах, и такое разряжение не окажет сильного влияния на общую картину графика.
Ещё раз прошу извинить за мой любительский вариант описания, я далёк от профессионального математика, но я старался как мог.
Это что касается определения границ поиска множителей конкретно для RSA.
В дальнейшем есть планы по изучению свойств числового ряда, которые мне неожиданно открылись. Узнать, есть ли зависимость при распределении на множителях, которые уже известны, есть ли паттерны малых чисел (до 10 разрядов), которые согласуются со сверхбольшими числами, почему горбы переворачиваются, от чего это зависит, изучить формирование первых десяти старших разрядов цифр множителей и много ещё чего интересного.
Буду благодарен за любые комментарии и указание на допущенные мной неточности или ошибки.
P.S. Я не профессиональный математик, я любитель математики. Не судите слишком строго.
Автор: Alexey Nickolaevich Zolotarev
