В очередной работе из цикла статей о натуральном ряде чисел (НРЧ) используются понятия и обозначения Г2± – модели НРЧ в форме дискретной (из клеток с координатами (х1, хо)) бесконечной плоскости (см.здесь), в которой составное четное или нечетное натуральное число (СННЧ) в каждой клетке модели описывается соотношением N =x1 2 ± xо 2. Рассматривается очередное важное для решения задачи факторизации больших чисел (ЗФБЧ) свойство Натурального ряда чисел — кратность клеток модели модулю шифра RSA.
Об алгебраических кольцах и шифре RSA
Шифр RSA и ему подобные в своей основе имеет строгую математическую конструкцию – конечное числовое кольцо вычетов (КЧКВ) по модулю составного числа N = dмdб, где dм – меньший простой делитель, dб – больший делитель.
Требованием к ключу (в частности к модулю N) шифра является то, чтобы оба делителя были простыми числами очень большой разрядности (до 300 десятичных цифр). см.здесь
Другим важным требованием к ключу шифра является требование для разности делителей
|dб – dм| = Δ. Она должна иметь столь же высокую разрядность как сами делители. Простым примером КЧКВ может служить начальный фрагмент натурального ряда чисел с добавлением нулевого элемента. Кольцо образуют все числа подряд от 0 до N – 1. Более подробно о кольцах можно прочитать в учебниках по высшей алгебре.
Стойкость шифра RSA к раскрытию ключа оценивается как очень высокая и все усилия криптоаналитиков мира по взлому шифра с момента его публикации (1978 год) успеха до сих пор не имели. Можно назвать ряд причин такого положения.
Публикуемые алгоритмы для реализации атак на шифр базируются в своей основе на концепции числового решета, предложенного Эратосфеном еще до новой эры. С каждой новой публикацией мы видим несколько улучшенную, усовершенствованную версию алгоритма, но, по-видимому, эти усовершенствования недостаточны для достижения успеха. Идея решета Эратосфена [1] была прогрессивной в его время, но сейчас это не срабатывает.
В сети Интернет имеется список RSA-чисел, которые фирма предлагается факторизовать. Список опубликован в 1991 году, и он пока далек от завершения. Анализ результатов мультипликативного разложения чисел из списка доступен, как и сами числа, открыт для всех.
Из анализа следует, чем больше цифр в описании числа, тем большее время требовалось для его разложения. Напрашивается вывод о том, что для разложения модуля N используются алгоритмы весьма чувствительные к разрядности чисел, т. е. алгоритмы используют свойства чисел, сильно зависящие от их разрядности. Я же имею в виду свойства подобные «признакам делимости» чисел. Они практически от разрядности факторизуемого числа не зависят (см.здесь).
Публикуемые работы ограничиваются, как правило, обработкой непосредственно самого числа, игнорируя его окружение, свойства ближних и дальних соседей в рамках конкретной системы счисления. Очень большие надежды авторов и ожидания возлагаются на новые вычислительные средства: квантовые, фотонные, молекулярные и тому подобные вычислители.
Авторы публикаций и владельцы фирмы, т.е. алгоритмов шифрования не отрицают других новых подходов, и не исключают возможности создания новых алгоритмов на новых идеях, перед которыми задача факторизации больших чисел не устоит и ее решение будет успешным. Меня как автора настоящей публикации привлекают как раз новые оригинальные разработки в области решения ЗФБЧ.
Большинство моих публикаций посвящены как раз новым подходам, начиная с синтеза моделей натурального ряда чисел, изучения их свойств и использования таких свойств при разработке новых оригинальных алгоритмов решения ЗФБЧ. Двигаясь в этом направлении удалось установить (открыть) Закон распределения делителей (ЗРД) числа N в НРЧ ЗРД.
Вертикали (столбцы) Г2± – модели НРЧ
Примером такого нового подхода может служить использование сумм пар квадратов чисел. Эти числа берутся из НРЧ и должны удовлетворять требованиям: два числа смежные и их сумма равна составному числу N, которое хотим факторизовать, еще два числа квадраты, удовлетворяющие уравнению N + x1 2 = xо 2.
Еще одно требование: суммы квадратов смежных чисел аддитивного разложения с найденными двумя квадратами должны иметь равные (совпадающие) значения (см.здесь). Если удается выполнить перечисленные требования, то факторизация N гарантирована. Пример 1 ниже по тексту иллюстрирует эту возможность.
Рассмотренная схема оригинальная, отличается от предложенной Л. Эйлером и другими математиками более простым и прозрачным для понимания содержанием.
Пример 1. (Сумма квадратов). Задано составное число N = dмdб = 209723. Требуется найти его мультипликативное разложение, т. е. значения множителей dм и dб.
Решение. Воспользуемся свойствами сумм квадратов в Г2+ – гиперболо-круговой модели.
Извлекаем квадратный корень из N, √209723 = 457,955 = 458 и округляем до большего целого.
Далее находим разности последующих квадратов и числа N с проверкой равенства этой разности полному квадрату: 458 2 – 209723 = 41 ≠ ▢, 459 2 – 209723 = 958 ≠ ▢, 460 2 – N ≠ ▢,
461 2 – N ≠ ▢,
462 2 – 209723 = 3721 = 61 2 = ▢. На 5-м шаге искомая разность равна полному квадрату. Находим аддитивное разложение N = 209723 = sм + sб = 104861 + 104862 на смежные слагаемые. Проверяем равенство сумм квадратов в клетках модели
N (х11, хо) = N (х11, sм), N (х12, хо2) = N (х12, sб),
где sм, sб – номера столбцов, а х11 и х12 – номера строк, модели. Эти номера определяются из соотношений равенства сумм квадратов.
sм2 + 462 2 = 104861 2 + 213444 = 10995829321 + 213444 = 10996042765;
sб 2 + 61 2 = 104862 2 + 3721 = 10996039044 + 3721 = 10996042765. Суммы в клетках, как и ожидалось, оказались равными между собой.
Для таких сумм записываем равенство sм2 + 462 2 = sб 2 + 61 2 и преобразуем его в равенство разностей квадратов 462 2 – 61 2 = sб 2 – sм2. Справа разность квадратов всегда равна N, а левая разность преобразуется в произведение
462 2 – 61 2 = (462 – 61)(462 + 61) = 401·523 = 209723 = N.
Оба множителя – простые числа, т.е. факторизация числа N успешно завершена. Недостаток такого подхода состоит в необходимости отыскивать в смежных столбцах модели суммы квадратов с совпадающими значениями. При больших числах это достаточно трудоемкая операция. По существу эта задача сводится к подбору такого квадрата, который при суммировании с числом N дает больший квадрат.
Горизонтали (строки) Г2- – модели НРЧ
Работа с числами, решение актуальных задач типа ЗФБЧ или дискретного логарифма предполагает, что исследователь каким-то образом упорядочил и классифицировал числа (здесь) и работает не вслепую, не наугад, а прогнозирует ожидаемый результат, на основе выдвинутых гипотез о результате.
Одним из свойств строк (горизонталей) Г 2- – модели НРЧ является линейная зависимость значений каждой клетки последующей строки модели от значений в клетках предыдущей, что выражается простым суммированием значений из клеток верхней из двух смежных строк с постоянным значением из последней клетки нижней строки, то есть
N(х1, хо) = N(х1-1, хо) + N(х1, х1 — 1), хо пробегает при этом всю нижнюю строку (Табл.1)
Кликабельно
Рисунок 1-Значения кратные составным нечетным числам в первой 100 (выделены заливкой)
На рисунке выделены заливкой клетки с числами равными произведению номеров диагоналей.
Особенностью этих чисел является то, что номера диагоналей в КЧКВ по модулю N, рассматриваемые как элементы кольца, при отображении их (возведении в квадрат) и приведении результата по модулю кольца остаются самими собой (неподвижные элементы).
Первое число в качестве модуля N =15. Для него кратная клетка содержит произведение номеров диагоналей 10·6 = 60 = 15·4 кратное модулю с коэффициентом k = 4. Для номеров диагоналей выполняется: 6 2 ≡ 6(mod15);10 2 ≡ 10(mod15).
Возьмем второе число в качестве модуля N =35. Для него кратная клетка содержит произведение номеров диагоналей 21·15 = 315 = 35·9 кратное модулю с коэффициентом k = 9. Для номеров диагоналей выполняется: 15 2 ≡ 15(mod35);
21 2 ≡ 21(mod35). Так будет для всех чисел N, принадлежащих длинной диагонали Д1, в строке которых указана заливкой кратная N клетка.
Пример 2.(Вычисление кратной клетки). Задан составной модуль КЧКВ N =77. по свойствам 1,2 значение в клетке N(х1 = 39, хо = 17) вычисляется как сумма значений в клетке сверху над заданной и в последней клетке строки х1 = 39 равная модулю КЧКВ.
N(х1, хо) = N(х1 = 39, хо = 17) = N(38, 17) + N(39, 39 – 1) => 1232 = 1155 +77.
N(х1, хо)=N(х1 = 39, хо = 17)=N(38, 17)+ N(39, 39 –1) = 38 2 – 17 2 + 39 2–38 2 => 1232 = 1155 +77.
С другой стороны, значение в каждой клетке произвольной строки вычисляется как разность квадратов координат клетки или как произведение разности координат клетки на их сумму
N(х1, хо) = N(х1 = 39, хо = 17) = 39 2 — 17 2 = (39 – 17)(39 + 17) = 22·56 = 1232 =16·77.
Существуют и другие менее наглядные способы вычислений значения в клетке.
Рассмотренный пример замечателен тем, что устанавливает формализованную связь рассматриваемой модели с конечным числовым кольцом вычетов по составному модулю.
Известно, что длинная первая диагональ Г2± – модели НРЧ. содержит в своих клетках все нечетные подряд следующие числа, которые могут рассматриваться как модули приведения алгебраических структур. Сами структуры образованы из элементов – натуральных чисел. Здесь не будем углубляться в понятия высшей алгебры, а укажем только факты интересные с позиций их отображения в Г2 - – модели НРЧ.
Среди всех элементов структуры КЧКВ по модулю N имеется множество И= {x}, которые называются идемпотентами, и квадраты которых после редукции (приведения их по модулю) сохраняют свои значения х 2≡ х(mod N). Такие элементы называются в теории отображений – неподвижными. Далее будем обозначать идемпотенты символами И1, И2,…
Другой класс элементов множество Н = {x} КЧКВ, называемых инволюциями, обладает следующим свойством х 2≡ 1(mod N). Далее будем обозначать инволюции символами Н1, Н2,…
Роль таких элементов колец весьма велика при решении прикладных задач и здесь мы рассмотрим отдельные интересные и полезные для решения ЗФБЧ факты. Дело в том, что теория колец не отвечает на вопрос, какие конкретно из элементов кольца являются идемпотентами, какие инволюциями. Как установить эти элементы, как определить их значения, при заданном модуле N кольца.
Оказывается, идемпотенты являются, к тому же, элементами кратными разным делителям модуля N. Их произведение по модулю равно нулю, так как кратно N, но сумма двух идемпотентов равна N + 1. Располагая значением идемпотента, можно решить задачу нахождения наибольшего общего делителя (общего как для модуля, так и для идемпотента).
А отсюда недалеко и до решения задачи факторизации модуля кольца, которая обеспечит нахождение личного ключа асимметричного шифра и успешность атаки на такой шифр.
Рассмотренный пример с клеткой, имеющей значение кратное значению в крайней правой клетке строки (кратной клеткой) имеет особенность, состоящую в том, что произведение диагоналей в кратной клетке – это произведение идемпотентов кольца.
Факторизация N с использованием идемпотентов конечного числового кольца
Схемы факторизации СННЧ N. Использование идемпотентов КЧКВ
Все (х1, хо) клетки Г2 - – модели уникальны и объединяются в линии: горизонтали с номерами х1 (они содержат число х1 клеток), вертикали с номерами хо, диагонали: короткие (K) с номерами х1 + хо и длинные (Д) с номерами х1 – хо.
В каждой клетке (х1, хо) модели пересекаются линии названных типов, номера которых определены координатами клетки. В клетках модели могут находиться не любые числа, а только представимые разностями квадратов других чисел (координат).
Горизонталь модели может быть задана ее номером х1, а вертикаль соответственно номером хо. В каждую клетку вписано число N (х1, хо) = х1 2 – хо 2. Последние клетки горизонталей образуют длинную диагональ Д1 и содержат значения
N(х1, х1 – 1) = х1 2– х1 2 + 2х1– 1= 2х1 – 1,
зависящие от номера горизонтали. В клетках этой диагонали содержатся все следующие подряд нечетные числа. Для диапазона чисел [d1min, d1max], d1min, d1max ∊ Д1, сумма их значений задает аддитивную форму числа N.
Пример 3 (Вычисление значения kN кратной клетки как суммы элементов фрагмента диагонали Д1 )
= 77+75+ 73+ …+ 37+35 = 1232 = 16·77= 22·56,,где i= 1(1)22.
Последнее означает, что количество слагаемых (22) в сумме равно меньшему делителю
N (х1, хо), а среднее слагаемое (56) – большему делителю N (х1, хо).
Если клетки главной До диагонали Г2 ± – модели с уравнением х1 = хо включить в Г2 - — модель, то значение в них будет равно нулю. Тогда при порождении значений в клетках строки с номером х1 в ее последней клетке получим значение 2х1–1, так как оно суммируется со значением из клетки строки с номером х1–1, находящейся сверху над ней и это значение равно 0. Важными свойствами Г2 - — модели и ее клеток являются следующие.
Свойство 1. Все числа в клетках текущей горизонтали х1 могут быть получены из чисел в соответствующих клетках предшествующей (верхней) горизонтали с номером х1 – 1 путем суммирования их значений с постоянным значением 2х1 – 1.
Таблица 1 – Фрагмент Г2 - — модели из 2-х строк 38-й и 39-й, N = 77
Действительно, N (х1, хо) = N (х1 –1, хо) + 2х1 – 1 = х1 2 – 2х1 + 1+ 2х1 – 1– хо 2 = х1 2 – хо 2.
Свойство 2. Второе свойство вытекает из первого. Любое число N (х1, хо) в клетке горизонтали с номером х1 может быть получено как сумма значений в клетках фрагмента длинной диагонали Д1, из которых большее d1max – число в последней клетке горизонтали х1, а меньшее d1min – число лежит в клетке пересечения диагонали Д1 с вертикалью хо.
Свойство 3. Для бесквадратного СННЧ N, помещенного в крайнюю правую клетку горизонтали х1, в этой горизонтали найдется клетка, в которой будет помещено число кратное N, т. е. число kN, k > 1. Поиск такой клетки нетривиальная трудно решаемая задача.
Иллюстрацией этого свойства являются данные таблицы 2. Для чисел первой сотни, которые бесквадратные и составные N, размещенные в клетках d1∊ Д1 со значением 2х1 – 1 указывается другая клетка (х1, хо), содержащая значение N (х1, xо) = kd1 кратное d1.
Таблица 2.
К·Д — произведение диагоналей, пересекающихся в клетке со значением kN.
Свойство 4. Все числа N (х1, хо) в клетках текущей горизонтали х1 могут быть получены как произведения номеров диагоналей а = х1+хо короткой и b = х1 – хо длинной, пересекающихся в этих клетках.
Иллюстрацию свойств удобно выполнить на числовом примере
Пример 4. Будем рассматривать Г2 - – модель. Зададим для факторизации СННЧ N = pq = 7·11 = 77. Это нечетное число и для него в длинной диагонали Д1 имеется клетка, которая лежит в горизонтали с номером х1 = ½ (N + 1) = 39.
Само число 77 помещено в последней клетке этой горизонтали, содержащей, как и все другие клетки, разность квадратов координат х1 2 – хо 2.
Первая клетка этой горизонтали в вертикали хо = 0 занята числом
х1 2 = 39 2 = 1521. Значение числа в любой промежуточной клетке горизонтали х1 равно, с одной стороны, произведению номеров b = х1 – хо длинной и короткой a = х1 + хо диагоналей, пересекающихся в ней ab = (х1 + хо)( х1 – хо).
С другой стороны – равно разности квадратов номеров горизонтали (для всех клеток горизонтали этот квадрат х1 2 одинаков) и вертикали хо 2, также пересекающихся в этой промежуточной клетке, т.е.
N(х1, хо) = х1 2– хо 2.
Кроме этого, все значения в клетках горизонтали х1 (по свойству 1) равны сумме значений N(х1, хо) = N(х1 – 1, хо) + 77 из соответствующих клеток горизонтали с номером х1 – 1, т.е. из верхней над ней и константы, равной N = 77.
Допустим, что в качестве номеров диагоналей выбраны у короткой значение х1 + хо = И1= 56 и для длинной значение х1 – хо = И2 = 22, т.е. значения нетривиальных идемпотентов кольца вычетов по модулю N.
При перемножении нетривиальных идемпотентов в роли диагоналей Г2 - – модели получаем в некоторой клетке горизонтали (с номером х1 = 39) в качестве их произведения число, кратное модулю (77) кольца вычетов, который размещается в последней клетке этой горизонтали, т. е. И1·И2 = 56·22 = kN = 16·77 = 1232.
Также из теории колец известно, что сумма нетривиальных идемпотентов равна И1+ И2 = N+1. Таким образом, относительно неизвестных идемпотентов получаем алгебраическую систему уравнений, которая кроме двух неизвестных идемпотентов содержит еще и третью неизвестную – коэффициент кратности k>1.
К счастью коэффициент k может быть определен вне системы алгебраических уравнений. Допустим, что коэффициент k нами уже определен k = 16.Тогда решаем систему уравнений.
Последнее слагаемое в квадратном уравнении необходимо сделать квадратом числа 39. Для этого добавим в левую и правую части уравнения число 289 = 17 2. Тогда получаем
(И2 — 39) 2 = 17 2 или И2 – 39 = ±17 и окончательно, И2 = 17 + 39 = 56 или И2 = 39 – 17 = 22.
Ответ: Идемпотенты равны И2 = 22; И1 = 56 или наоборот: И2 = 56 и И1 = 22.
Теперь вернемся к вопросу определения значения коэффициента кратности k.
Рассмотрим следующий алгоритм определения коэффициента кратности модуля N.
Алгоритм
1. Задано составное число N = 77 – модуль кольца вычетов;
2. Определяем по N значение номера горизонтали x1 = ½ (77+ 1) = 39, в первую клетку
которой помещаем квадрат 39 2 = 1521, а в ее последнюю клетку помещаем N = 77;
3. Произведение идемпотентов появляется в промежуточной клетке горизонтали x1 = 39; для этой клетки выполняется то условие, что число в ней равно kN, и оно представимо разностью квадратов натуральных чисел.
4. Следовательно, вычитая многократно из квадрата числа первой клетки горизонтали 39 2 = 1521 последовательно значения хо = 1,2,3,..., определяем каждый раз значение k, и является ли оно целым числом? Как только разность становится кратной N, задача решена: найдено kN.
Рассмотрим также другой алгоритм определения коэффициента кратности модуля N.
1. Задано составное число N = 77 – модуль кольца вычетов;
2. Определяем по N значение номера горизонтали x1 = ½ (77+ 1) = 39, в первую клетку
которой помещаем квадрат 39 2 = 1521, а в ее последнюю клетку помещаем N = 77;
3. Произведение идемпотентов появляется в промежуточной клетке горизонтали x1; для этой клетки выполняется то условие, что число в ней равно kN, и оно представимо разностью квадратов натуральных чисел.
Используя свойство 2, число kN можно находить указанным там путем, а именно, суммированием монотонно убывающих нечетных чисел из фрагмента диагонали Д1, начинающегося числом d1max = 77, и завершающегося числом d1min, значение которого априори неизвестно, d1min, d1max ∊ Д1.
4. Для установления последнего слагаемого после каждого шага суммирования проверяется делимость полученной суммы на N = 77. Решением будет сумма, делящаяся нацело на 77.
Таблица 3 – Числа N кратные 3 на осевой линии (заливкой выделен прогноз)
В этой таблице составные числа (кратные трем) следуют с чередующимися пропусками величиной 6 и 12. Действительно, в строке N имеем 21 – 15 = 6, а 33 – 21 = 12 и далее в таком же порядке. Предположительно пропуски между табличными значениями N вызваны тем, что в шестерке смежных чисел встречаются простые числа-близнецы, например, 16, 17, 18, 19, 20.
Следующее число кратное трем 21 как раз шестое по счету после 15. Либо в 12 подряд следующих чисел возможны пары простых чисел-близнецов, например, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, либо к простым близнецам подмешиваются квадраты 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50. В общем, выбор осуществляется с гарантией не cтолкнуться на не составное число в позиции, соответствующей числу кратному трем.
Именно, такое условие обеспечивает надежность прогноза далеко вперед. Пропущенные числа при этом оказываются кратными не только трем, но и большим простым числам, что позволяет их рассматривать с других позиций.
Список публикаций
1.Стечкин Б.С., Матиясевич Ю.В. Сито Эратосфена // Труды международной школы С.Б. Стечкина по теории функций. — Екатеринбург, 1999. – с. 148.
