Задается N — большое составное нечетное натуральное число (СННЧ), которое требуется факторизовать. Математическая теория метода решета числового поля (NFS) строится на основе теории делимости в алгебраических числовых полях. Перед любым автором, как и передо мной, возникает трудность сжатого изложения весьма обширного материала, касающегося методов SNFS и GNFS. Так как 2-й возник из 1-го я не привожу их отличий, хотя об этом много сказано.

О методах написаны целые книги. Но, помня о собственных затруднениях в изучении методов и преодолении их, считаю, что даже «куцее» урезанное изложение будет способствовать ознакомлению читателей с методами и идеями, лежащими в их основе. Надеюсь, что понимание этих идей их ограниченности (что практика подтверждает многократно), позволит более трезво подойти к тому, что предлагается мной в проблеме факторизации.

Можно сказать читатели принудили меня доносить до них чужие идеи, которые я не разделяю, так как свои считаю более обоснованными и прогрессивными, более здравыми. Они пока не получили завершенного вида, но время еще есть. Хочу изменить у читателей отношение к своим идеям и получить поддержку, а не минусы в комментариях, не подкрепляемые доводами. Личную неприязнь или «ничего не понял» доводом для минусования публикации считать не могу.

Неоправданное усложнение (матрица СЛАУ для $$ имеет размер 6000000×6000000) задачи факторизации больших чисел (ЗФБЧ) подвигло меня серьезно заняться этой проблемой. Уже удалось вскрыть закон распределения делителей СННЧ в НРЧ, т.е. понять где и как прячутся делители в натуральном ряде чисел, что конечно же упростит их поиск и обнаружение.

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

Оценки сложности — эвристические опираются на рассуждения ограниченные авторским пониманием проблемы. Пора бы уже понять, что факторизация чисел в глубоком тупике, а математикам (не только им) пересмотреть свое отношение к проблеме и создать новые модели.

Простая идея факторизации целого нечетного числа N исторически — состоит в поиске пары квадратов чисел разной четности, разность которых кратна kN, при k =1 разложение успешно реализуется так как в этом случае сразу получаем произведение двух скобок $$ c сомножителями N. При k>1 случаются тривиальные разложения.

Таким образом, проблема факторизации преобразуется в проблему поиска подходящих квадратов чисел. Понимали эти факты многие математики, но П. Ферма первым в 1643 году реализовал идею поиска таких квадратов в алгоритме, названном его именем. Перепишем иначе приведенное соотношение $$.

Если разность слева от равенства не равна квадрату, то изменяя х, можно подобрать другой квадрат, чтобы и справа получался квадрат. Практически все нынешние алгоритмы используют эту идею (поиска пары квадратов), но судя по результатам, похоже, что идея себя исчерпала.

Теория отношений в математике и в ряде предметных областей (принятие решений, базы знаний и данных, математическая лингвистика, моделирование процессов, и др.) играет весьма заметную роль, но пока далека от завершения. Как и в других отраслях математического знания ее известные результаты в большей мере относятся к вопросам и задачам существования тех или иных ее объектов, чем к задачам их перечисления. Казалось бы любой исследователь в конкретной отрасли теории должен бы интересоваться общей и полной картиной, интересующих его объектов и их зависимостей, обозревать полную панораму. Но увы, сделать это весьма проблематично, так как такую панораму (картину) никто не создал и не предлагает. Даже предложенный в работе каталог отношений проблему не закрывает.

Продолжая тему скажу, что посмотрел публикации других авторов Хабра по этой теме. Интерес к проблемам имеется, но в теорию влезать никто не желает. Действуют как пионеры первооткрыватели. Это было бы прекрасно, при получении ими новых результатов, достижений, но к этому никто и не стремится.

А на деле получается хуже, чем уже известно, не учитывается масса факторов, результаты теории применяются там, где она это делать не рекомендует и вообще не очень серьезно все выглядит, хотя Хабр, как надо понимать к этому и не стремится. Читатели не могут и не должны играть роль фильтра.

Эта работа о безопасности информационных систем, в которых принимаются серьезные информационные решения и которые можно подразделить на три типа:

• во-первых, системы извлечения информации (информационно-поисковые системы (ИПС), информационно-измерительные системы (ИИС) и другие);
• во-вторых, приемопередающие системы (системы передачи данных (СПД), запросно-ответные системы (ЗОС) и другие);
• в-третьих, системы разрушения, уничтожения информации (постановки помех, подавления сигналов, радиоглушители и другие).

Во всех системах управление — важное явление, процесс, деятельность, которые включают в себя как компоненты организацию системы, распределение ресурсов (планирование), принятие решения и связь.

Трудно назвать область деятельности, в которой не принимались бы время от времени решения. Эта ситуация и явление имеет место всегда и раньше, и теперь, и в будущем.Человек пальцем не пошевелит, не приняв решения об этом. Не всегда это осознается, но это именно так.

Здесь (в работе) основное внимание уделим теории выбора и принятия решений, которая исследует математические модели принятия решений и их свойства. Наука о принятии решений долгое время развивалась, можно сказать, однобоко. Классическая схема охватывается статистической теорией, основывающейся на функции риска, на ошибках первого и второго рода.

Этот подход к принятию решений сыграл свою положительную роль и применимость его сегодня не отрицается, но ограничивается принципами рациональности. Подход не лишен и недостатков. Известно крылатое выражение, приписываемое классику (Госсету (псевдоним Стьюдент)) от статистической теории «о трех видах лжи: преднамеренной, непреднамеренной и статистике».

Важной задачей кодологии при обработке информационных потоков кодированных сообщений в каналах систем связи и компьютерных является разделение потоков и селектирование их по заданным признакам. Выделенный поток расчленяется на отдельные сообщения и для каждого из них выполняется углубленный анализ с целью установления кода и его характеристик с последующим декодированием и доступом к семантике сообщения.

Так, например, для определенного Рида-Соломона кода (РС-кода) необходимо установить:

• длину n кодового слова (блока);
• количество k информационных и N-k проверочных символов;
• неприводимый многочлен р(х), задающий конечное поле GF(2^r);
• примитивный элемент α конечного поля;
• порождающий многочлен g(x);
• параметр j кода;
• используемое перемежение;
• последовательность передачи кодовых слов или символов в канал и еще некоторые другие.

Здесь в работе рассматривается несколько другая частная задача — моделирование собственно РС-кода, являющаяся центральной основной частью названной выше задачи анализа кода.

В информационных системах обмен сообщениями в сетях связи или вычислительных сопровождается возмущающими воздействиями среды или нарушителя, что приводит к появлению искажений сигналов и к ошибкам в символах при цифровой передаче. Борьбу с этим явлением ведут, используя корректирующие коды. Ранее я описывал код Хемминга, и показал как исправляется одиночная ошибка в кодовом слове. Естественно возник вопрос и о ситуациях с большим количеством ошибок. Сегодня рассмотрим случай двух ошибок в кодовом слове (кратную ошибку). С одной стороны, все в теории более менее просто и понятно, но с другой — совершенно не очевидно. Изложение материала выполнено на основе работ Э. Берлекемпа.

Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические объекты и процессы их функционирования. Эта публикация является продолжением предшествующей, прочтение которой желательно, так как многие понятия и термины, используемые здесь, описываются там.

Предлагается изложение не в традиционном (стрелочном) стиле, а так, как мне самому пришлось всю эту кухню представлять и осваивать и по учебникам/пособиям, и по журнальным статьям. Особенно полезной вещью считаю созданный мной каталог, он позволяет выделить практически любое пространство и представить его элементы в удобном виде: матрицей, графом и др. Сразу видишь с чем имеешь дело и свойства (они уже выписаны) проверять часто не требуется.

Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД)). Не менее важной считаю область принятия решений, которая состоит из двух основных статистической и алгебраической, основанной целиком на теории отношений. Образовательный уровень специалистов в этой теории близок к нулю.

Откройте учебник по специализации и там увидите в лучшем случае об эквивалентностях, которые авторами трактуются весьма своеобразно. Одного защитившегося уже ДТН спрашиваю: Вы рассматриваете отношение эквивалентности на указывая ни носителя отношения, ни конкретного отношения, как оно у Вас выглядит в записи? Ответ: как выглядит — обыкновенно. Выясняется, что он обо всем этом имеет весьма смутное представление.

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

Операция деления как раз одна из самых «дорогих» операций. Дело в том, что в алгебраических полях, а соответственно и в группах операция деления вообще отсутствует и выход из положения (когда не делить нельзя) состоит в том, что операцию деления заменяют умножением, но умножают не на саму координату, а на обращенное ее значение. Из этого следует, что предварительно надо привлекать расширенный алгоритм Евклида НОД и кое что еще. Одним словом, не все так просто как изображают авторы большинства публикаций о ЕСС. Почти все, что по этой теме опубликовано и не только в Интернете мне знакомо. Мало того, что авторы не компетентны и занимаются профанацией, оценщики этих публикаций плюсуют авторов в комментариях, т. е. не видят ни пробелов, ни явных ошибок. Про нормальную же статью пишут, что она уже 100500-я и от нее нулевой эффект. Так все пока на Хабре устроено, анализ публикаций делается огромный, но не качества содержания. Здесь возразить нечего — реклама двигатель бизнеса.

Информационное взаимодействие абонентов в компьютерных и связных сетях подвергается возмущениям, которые приводят к возникновению ошибок и возмущений разного рода. Помимо возникновения ошибок в передаваемых сообщениях возможен несанкционированный доступ к содержанию сообщений нарушителя. Борьба с этими нежелательными явлениями ведется тысячелетиями, но с переменным успехом. Создатели Интернета задумывали его совсем не таким, каким он стал сейчас. О хакерах тогда и не думали.

Основные теоретические проблемы информационного противостояния, задачи по их решению возлагаются на теории кодологии, криптологии и стеганологии, в которых во всем мире интенсивно развиваются направления кодоанализа, криптоанализа и стегоанализа. Практические аспекты также не остаются в стороне, но замечу, что в РФ активность не очень-то высока, сказывается инертность молодых (сам я разменял уже 9-й десяток, но администрация Хабра ограничила возрастной ценз 1950 г). Мое мнение, конечно, ограничено наблюдением потомства (вплоть до правнуков) и общением в интернете, а также с обучаемыми и сотрудниками фирмы, где подрабатываю. СМИ тоже добавляют негатива. Кто из молодежи чуть поумнел, уходят за бугор. Поведение остальных видите сами.

Проблемы информационной безопасности требуют изучения и решения ряда теоретических и практических задач при информационном взаимодействии абонентов систем. В нашей доктрине информационной безопасности формулируется триединая задача обеспечения целостности, конфиденциальности и доступности информации. Представляемые здесь статьи посвящаются рассмотрению конкретных вопросов ее решения в рамках разных государственных систем и подсистем. Ранее автором были рассмотрены в 5 статьях вопросы обеспечения конфиденциальности сообщений средствами государственных стандартов. Общая концепция системы кодирования также приводилась мной ранее.

Сознание — рефлексия субъектом действительности, своей деятельности, самого себя. Оно порождается не природой, а самим человеком и окружающим миром, семьей, обществом.
В свое время Г. В. Ф. Гегелем были высказаны идеи о трех слоях в его учении о субъективном духе, который выделял три ступени в развитии субъективного духа: антропологию, феноменологию и психологию. Сегодня этот подход вполне применим к сознанию.

Развитие вычислительной техники движется по различным направлениям, не ограничиваясь явлениями классической физики, электроники, оптики и теперь уже квантовой механики.
Ознакомление с проблемой квантовой криптологии и смежными, близкими к ней (не только по публикациям), показало, что имеют место определенные недостатки и пробелы в ее описании и представлении. Описывая конкретику того или иного физического явления, объекта, автор игнорирует его окружение даже ближайшее, оказывающее на объект непосредственное воздействие (часто возмущающее влияние). Это не упрек авторам, их право излагать так как они излагают. Это скорее мой мотив включиться в общий поток сознания. Материальная вещественная сторона квантовых явлений так или иначе проявляет себя и неучет ее, может сказаться существенным негативом. Что имеется ввиду? Материальная реализация квантовых компьютеров (КК), регистров, отдельных кубитов — всего того из чего КК сделаны. Обмен пользователей полученными результатами через сети связи и, наконец, защита, целостность и доступность таких результатов от нарушителя — тоже проблемы.

После подробного изложения с деталями отдельных преобразований, с элементами конечного не отвлеченного (как во множестве публикаций, не исключая и Хабровских) алгебраического поля, а (конкретного), в рамках которого реализуется RIJNDAEL, AES-128 и (выполнения операций стандарта AES-128), можно перейти к рассмотрению возможных атак на шифр. Пока ограничимся одной атакой, по нашему мнению, наиболее доступной для понимания и прозрачно построенной (хотя, возможно, не всем читателям) Хабра.

К минусам-то я уже приучен, но с чем чёрт не шутит. Анализ возможных атак и ожидаемых результатов выполнялся многими авторами, но конкретных успешных примеров или просто впечатляющих замыслов явно недостаточно. Здесь будет рассмотрена с математических позиций атака с использованием вносимой нарушителем в шифртекст ошибки. Автор при выборе атаки для демонстрации старался не привлекать те, где используются слишком накрученые и заумные математические вещи, но сам рассматриваемый предмет достаточно серьёзный и не позволяет переходить к объяснениям на «пальцах».

В этой IV части завершаем описание шифра АЕS — 128. Для читателей не знакомых с предшествующими частями работы поясню, что материал излагается в учебных целях и это накладывает ряд особенностей (детализация, числовые примеры, математические основы и др.) Предполагается не просто ознакомление со стандартом, а использование излагаемого материала для разработки алгоритмов зашифрования и дешифрования (при отсутствии ключа). Авторы множества известных в сети (и вне её) публикаций не ставили перед собой таких целей, что делает эти публикации малопригодными для наших целей.

Процесс обратный зашифрованию называется расшифрованием сообщений. Для расшифрования (с ключом) шифрованных текстов (ШТ) создается инверсная таблица замен и раундовые ключи, которые используются в обратном порядке относительно схемы для шифрования, но подобно процессу зашифрования.

Мотивом к публикации столь подробных текстов об AES стандарте-предоставление возможности ознакомления с ним в деталях, достаточных не только для разработки самостоятельной программной реализации алгоритма зашифрования, но и для создания алгоритмов возможных криптоаналитических атак на шифр, т. е. для дешифрования шифрграмм без знания ключа.

Те публикации, которые имеются в сети, названным целям не отвечают, не могут быть мною использованы в процессе обучения специалистов.

Одно из основных старых (или даже старинных) требований к шифрам — это создавать открытый (доступный для изучения) алгоритм шифрования и накрутки вокруг него (режимы, протоколы и т. п.) всё, кроме ключа шифра. Ключ — это то, что должно сохраняться в строжайшей тайне от всех. При этом ключ не обязательно имеет гриф «Секретно». Предел такого условия — ключом владеет только получатель шифрграммы, он сам в принципе и должен его устанавливать.

Для симметричных систем шифрования это условие невыполнимо. И в этом принципиальное отличие асимметричных (двухключевых) систем от симметричных, в которых источник утечки информации о ключе может быть не единственным. Ранее отмечалось, что АЕS — упрощенная версия шифра RIJNDAEL, а здесь местами будем использовать полную версию.

Основные операции шифра

Рассматривая работу отдельных операций раунда, и повторяя раунды нужное число раз при этом иллюстрируя все промежуточные действия, а не только их конечные результаты, конкретным примером сообщения и ключа шифра мы в деталях наблюдаем все шаги процесса шифрования и можем анализировать, те условия при которых они реализуются, те результаты которые получаются и т.п. Помним при этом, что «дьявол кроется в деталях».

При слепом обращениях к имплементациям пользователь ничего этого не видит, не ощущает и главное — не понимает как шифрование происходит. Он задает только текст сообщения и ключ. Это все, что пользователю понятно. Пользователь целиком доверяет разработчику, на чем уже многократно попадались деятели от государственного уровня до рядовых пользователей. Это и прослушивание переговоров дипломатических представительств и отказ технических систем, когда чужое коммуникационное оборудование покупается и устанавливается без оглядки.
Как анализировать процесс шифрования, на что и как влияет внесение изменений не ясно.

Эта публикация вызвана необходимостью дать возможность обучаемым изучать и моделировать процессы шифрования/расшифрования и дешифрования последнего стандарта США. Ознакомление с имеющимися публикациями в сети не соответствуют программе обучения в силу их поверхностного подхода, неполноты изложения, и отсутствия должной строгости. Например, нигде не встречается выбор и задание примитивного элемента, формирующего поле, без чего работу и подготовку специалиста, особенно криптоаналитические явления и процессы, организовать и моделировать невозможно. В этой работе используется описание, несколько отличное от оригинала AES, представленного FIPS PUB 197. Здесь описывается шифр AES, с использованием матриц над GF(2⁸), но примечания работы сохраняются, т. е. шифр реализуется над конечным расширенным полем GF (2⁸). На русском языке достаточно полная и доступная версия шифра изложена Зензиным О.С. и Ивановым М.А.

Структура конечного кольца вычетов по составному модулю

Замысел работы. Создать такую математическую модель большого числа, которая позволила бы находить его делители, исключая схему перебора возможных их вариантов. При построении модели полагаем известными все ее элементы: значение N = dмdб, позицию его в контуре натурального ряда чисел (НРЧ), оба делителя, их свойства.

Определяемыми неизвестными характеристиками такой универсальной модели являются функциональные зависимости одних переменных модели от других. Эти зависимости должны иметь характер законов и выполняться всегда (для всех чисел) независимо от масштаба чисел. Формирование работоспособной модели числа оказалось достаточно сложным и объемным процессом, поэтому принято решение разбить его на 2 статьи (Часть I здесь).

В настоящее время ситуация с моделированием чисел и факторизацией как пишут Манин и Панчишкин близка к тупику или уже в тупике.

В этой статье на основе закона распределения делителей (ЗРД см.здесь ) числа рассматривается вопрос о структуре конечного числового кольца вычетов (КЧКВ) и о том, как неизвестные нам делители N управляют возникновением полных квадратов — квадратичных вычетов (КВВ) в списке квадратичных вычетов, которые доступны нашему наблюдению. Часть понятий и определений вводилась в части I и здесь повторяются не все из них.