Comments 31
Вот у меня всегда было подозрение. Все расчеты устойчивости шифра даются на обычные компьютеры. НО за скобками остается возможность, что возможен некий аналоговый процессор резко сужающий перебор...
Это подозрение ни на чем не основано. Точнее моё подозрение - это интерференция истории "Энигмы", которой долго торговали с явной уязвимостью, и истории PGP.
Любопытно, причем, не мне одному - уверен.
Попробуйте в следующий раз хоть немного формул и примеров с разъяснениями сделать, что бы тем кто не особо в теме было легче вникнуть. Код лучше на питоне делать, там и длинная арифметика и простой синтаксис. Для синусоид и больших чисел можно воспользоваться gmpy2 - удобный и простой пакетик.
А вообще, вы молодец, правильными вещами увлекаетесь. Человек, который берется за "нерешаемые" задачи так, словно они решаемы обладает незаурядными качествами.
Спасибо, учту в дальнейших статьях.
Человек, который берется за "нерешаемые" задачи так, словно они решаемы обладает незаурядными качествами
При условии, что задачи не решенные, а "нерешаемые". Если про задачу доказано, что решения нет, то это просто трата времени себя и тех, кому непосчастливится читать "статьи" от таких людей. Вроде бедных сотрудников патентного бюро, читающих про очередной вечный вдигатель. Или вот недавно на хабре был кадр, который вообще любые данные научился сжимать.
Про задачу факторизации доказано только то, что она не решаема современными методами и тратить на нее время бесполезно. Вот и все что доказано. Но это же говорили и о шифре знаменитой Энигмы. Не правда ли ? В своих исследованиях и поисках, я пытаюсь найти решение более элегантное чем прямой перебор множителей пусть даже и ускоренный, но недостаточно.
Безусловно, я не спорил с вашей статьей, а лишь придрался к словам uchitel'я.
Если вам интересно, то есть метод основанный на эллиптических кривых. Он весьма быстрее тупого перебора. Кажется, смотря на небольшой набор весьма хаотичных графиков и чуствуя какие-то закономерности там, этот способ не переплюнуть.
Метод поиска на ЕС, не достаточно быстр, нельзя найти множители для 2048 битного RSA числа в течении часа хотя бы. Я и не стремлюсь его переплюнуть, ни в этом задача моих поисков и исследования. Моя задача попробовать найти решение этой давно застоявшийся проблемы. Это не смысл моей жизни, а хобби. :)
не достаточно быстр, нельзя найти множители для 2048 битного RSA числа в течении часа хотя бы
Ха, тут разговор о десятилетиях или веках должен идти, а не о часах. И это один из самых быстрых придуманных на сегодня методов. Все таки в этом суть шифрования и есть - взламывать его должно быть сложно. И смотрите, какая там вырвиглазная математика. Наивно думать, что смотря на графики у вас получится хотя бы так.
Я и не стремлюсь его переплюнуть, ни в этом задача моих поисков и исследования. Моя задача попробовать найти решение этой давно застоявшийся проблемы
Какой задачи? Если вы не хотите переплюнуть этот метод, то вы предложите худшее решение. Если вы хотите найти лечшее решение, то как вы при этом не хотите его переплюнуть?
Главным качеством в некоторых отраслях является склонность к поиску идей. Когда к тебе приходит бизнес и говорит: хочу быстрее, больше и шоколаднее, то есть всего два ответа:
У вас и так топовый солвер и самые навороченные модели
Хорошо, сейчас подумаю
Что касается доказательств, то конечно есть вероятность, что бизнес купится на красивую, но полностью лживую презентацию. Но скорее всего, сразу попросят привести пример, подтверждающий наличие профита. За голые слова никто не заплатит (как правило). А платят порой слишком дохрена и прокачивание такого навыка стоит свеч.
Не понял, как графики синусов позволяют сократить перебор возможных делителей. Можно про это поподробнее рассказать?
То, что синус для "делителя" уложится в первые 2 горба синуса для делимого - интересный факт, но с свычислительной точки зрения, поделить нацело и посмотреть остаток гораздо проще.
Подсказка: я отметил в названиях графиков числа множителей и их произведение, они (множители) расположены все до описанного овала слева, если идти по числовой прямой в сторону обычной единицы. Добавьте точки множителей на ось абсцисс. Я пробовал с разными множителями, но все они были до овала слева. Чем не ограничение для поиска множителей.
До какого овала? То что вы пробовали на каких-то множителях, еще не является никаким доказательством. Эти точки вообще довольно хаотично разбросаны. Вы попробуйте множители не очень близкими к корню брать, там овалов может быть несколько, вообще не быть, да и расположены они могут быть много где.
Например, если вы овалом называете сине-зеленую, относительно пустую внутри область, то на последней картинке в статье его вообще нет.
Вы наверно не знакомы с полным перечнем требований при формировании ключей для RSA. Поэтому и говорите, что может быть где угодно. Но это не совсем так. Я поищу у себя полный перечень требований для формирования безопасных ключей RSA, если вы сами его раньше не найдете. Может быть тогда всё встанет на свои места.
Тут, видимо, хотели прийти к тому, что если вы выполняете операцию N mod k1, и получаете какое-то значение, вы можете выполнить N mod k1-1 (и посмотреть, не сделали ли вы "оборот" при вычислении mod, если нет - пропустить до k1 значений при переборе, т.к. зависимость остатка от деления - линейная функция).
Из минусов - примерно та же сложность, что и просто перебрать SQRT(N) значений.
Вот пример вычисления множителей для 21 за 2 действия (в классическом переборе - 3):
Лучшее, что вы можете сделать - посчитать количество получающихся значений в каждой группе (и даже попробовать соорудить двоичный поиск - если количество цифр в группе больше 1 - уменьшаем значение, если <=1 - увеличиваем)
N mod k1, и получаете какое-то значение, вы можете выполнить N mod k1-1 (и посмотреть, не сделали ли вы "оборот" при вычислении mod, если нет - пропустить до k1 значений при переборе, т.к. зависимость остатка от деления - линейная функция).
Можно по-подробнее?
Что значит, не сделали "оборот"? Что не изменилась целая часть в частном? И как это позволяет пропускать числа?
Давайте представим:
вы получаете остаток от деления на N, затем на N-1. вы все еще движетесь по воображаемому циферблату c N (N-1) цифрами (на котором обычно и обьясняют концепцию mod).
вы прошли M цифр, и до сих пор не сделали шаг через 0 (выше на картинке N с 11 до 10).
Пока вы не перешли этот воображаемый 0 - вы движетесь с постоянной скоростью V, где V - количество раз, когда вы пересекли воображаемый 0.
Поэтому цифры во втором ряду имеют линейную зависимость (остаток от деления). Сначала остаток от деления растет на 1 при изменении делителя на 1, затем - на 2.
Интереснее второй концепт:
Двоичный поиск. Дело в том, что множитель похоже совпадает с местом перехода от нескольких ходов без пересечения 0 до нескольких пересечений нуля за 1 ход.
Оба этих состояния легко проверить за конечное время.
Ясно, тут рассматривается значение частного. При фиксированном частом k, если N=d*k+r, то r=N-d*k. Поэтому при увеличении делителя d, имеем линейную зависимость остатка k. "Пересечение нуля" тут - это уменьшение частного.
Т.е фактически, вместо перебора делитея d, вы перебираете оставшийся делитель N/d, значений у которого ровно столько же - sqrt(N).
Т.е. ничего это не изменило вообще.
Что касается бин поиска, то вам надо найти точку, где "переход через 0" даст остаток 0. Но во время проверки произвольного числа вы никак не можете определить, был ли этот переход раньше или его не было, так что бин поиск тут не работает.
Это как хобби, даже день отдельное название получил — «RSA-день»
Скажите, а что вы делаете, если не удалось за день уложиться, или какая-то хорошая идея пришла под конец дня? Откладываете мысль в долгий ящик, до следующего дня хобби?
Я как-то заморачивался по поводу фазового АЛУ, принцип действия которого основан на интерференции синусоидальных сигналов, источником которых являлся один единственный генератор, но которые сдвинуты относительно друг друга на N градусов. Вроде как создание такого АЛУ возможно в области ВЧ на полосковых линиях, которые можно разместить керамике. Такое АЛУ можно, как я полагаю, использовать как вспомогательный вычислительный модуль, подключаемый к обычному компьютеру.
Знали бы вы, что дальше планирую на счет эллиптических кривых после RSA
Вы имеете ввиду факторизацию на основе эллиптических кривых или взлом самих эллиптических кривых?
Всем добрый вечер.
Переписал свой скрипт под большие числа и все стало синусоидально. Как так ?
Куда все пропало ?
Я проверил переписанный скрипт на старых данных, все работает как и было.
Что я не так делаю ?
T0 = '1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139';%'473717';
T1_u = '37975227936943673922808872755445627854565536638199'; %'377';
%37975227936943673922808872755445627854565536638199
T1_start =vpa(T1_u,200);
T1_start_start= vpa(T1_start-1000,200);
T1_end = vpa(T1_u,200);
T1_end_end = vpa(T1_end+1000,200);
% Создаем массивы для хранения результатов
even_results = {};
odd_results = {};
% Цикл по значениям T1 в диапазоне от T1_start - 500 до T1_start + 1200
%for T1_offset = T1_range_down:1:T1_range_up
for T1 = T1_start_start:T1_end_end
% Преобразуем T1 в число произвольной точности
T1_offset = vpa(T1,200);
T0_nil = vpa(T0,200);
% Вычисление значения синусоиды при x = T0 с использованием произвольной точности
%y = sin((2 * pi / T1) * T0);
%y = vpa(sin(2 * pi * T0 / T1), 100);
%y = vpa(sin((2 * pi / T1)*T0), 100);
y = vpa(sin((2 * pi / T1_offset)*T0_nil), 200);
%y = vpa(sin(2 * pi * (mod(T0_nil, T1) / T1)), 100);
%%disp(['y: ' char(y)]);
% Преобразование значений в строки для сохранения в CSV
T1_str = char(T1);
y_str = char(y);
% Форматирование чисел в строку без экспоненциальной формы
%T1_str = sprintf('%.200f', T1);
%y_str = sprintf('%.200f', y);
% Добавление результата в соответствующий массив
if mod(T1_offset, 2) == 0
even_results = [even_results; {T1_str, y_str}];
else
odd_results = [odd_results; {T1_str, y_str}];
end
end
% Сохранение результатов в файлы CSV
even_table = cell2table(even_results, 'VariableNames', {'T1', 'Y'});
odd_table = cell2table(odd_results, 'VariableNames', {'T1', 'Y'});
writetable(even_table, 'sinusoid_even_results_large_numbers.csv');
writetable(odd_table, 'sinusoid_odd_results_large_numbers.csv');
% Вывод сообщения о завершении
fprintf('Even results have been saved to sinusoid_even_results_large_numbers.csv\n');
fprintf('Odd results have been saved to sinusoid_odd_results_large_numbers.csv\n');
Куда все пропало ?
А оно было-то? Это как "Я решил простые числа. Формула 2k+1. Я проверил: 3, 5, 7 - все работает. Потом: Ой, а что-то 111 не простое, где ошибка?"
Ваши закономерности в графиках оказались лишь случайностью.
Хотя, может быть, тут и есть ошибка в скрипте. Это какой язык вообще? Может там большие числа приводятся к формату с плавающей точкой и больше 18 знаков точности на самом-то деле не хранят.
Синусоида и начальные условия факторизации едины