Ключ

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

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

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

Продолжая тему о блочном шифре победителе конкурса, проводимого Национальным институтом стандартов и технологий США (1997 2000), будем рассматривать его функционирование, работу. Агентство национальной безопасности США не являлось участником конкурса, поэтому шансы стать победителем у разработчиков были велики.

Конкурсной комиссией были предварительно отобраны 15 заявок от разных стран. Выступать могли как организации, так и частные лица. В итоге победил RIJNDAEL(Бельгия) авторы Винсент Рюмен (Vincent Rijmen) и Ион Дэмен (Joan Daemen). Структуру шифра считают классической SP-сетью.

Ранее уже приводились основные технические характеристики и повторяться не будем.

Шифрование сообщений

Разработчиками создан шедевр, впервые идеология и реализация симметричного блочного шифра стала до конца понятной, так как шифр полностью основан на элементах классической (прозрачной) алгебраической структуры (поле), с достаточно скромными для обозрения количественными характеристиками. Конечное расширенное поле (поле многочленов) характеристики 2 имеет степень расширения n=8 и число элементов (порядок поля 2⁸ = 256), отсюда обозначение поля GF(2⁸).

Выбор неприводимого многочлена поля и примитивного элемента поля = 00000011₂ = 3₁₀, также не является загадочным. Одним словом, это не DES и не отечественный ГОСТ 28147.89.
Исходные тексты подготавливаются на устройствах с клавиатурой, используя
Таблицу Символы кода ASCII

Раунды и операции шифрования АЕS

Число раундов шифра обозначается Nr и зависит от длины ключа (Nr = 10 для ключа 128 битов, Nr= 12 для ключа 192 бита и Nr = 14 для ключа 256 битов).
Цикл (один раунд) шифрования AES состоит (в изменении состояния State шифруемого сообщения) из четырех основных операций:
1. AddRoundKey S + Ki; суммирование состояния (исходного текста с ключом)
2. SubBytes ax^-1 + b; замена результатов суммирования другими байтами
3. ShiftRows; Sp(x); циклические сдвиги строк на разное число позиций
4. MixColumns A0S. перемешивание столбцов квадрата.

Покажем, как это происходит на числовом примере для текущего состояния в каждой операции, начиная с верхней (нулевой) строки. Результаты 2-й и 3-й операций не требуют числовых преобразований, но MixColumns связана с умножением 2-х матриц и определение элементов результирующей матрицы требует конкретных вычислений в поле GF(2⁸). Алгоритм выработки ключа (Kеу Schedule) формирует 32-разрядные слова, число которых равно длине блока Nb.

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

Существует анимация, поясняющая функционирование алгоритм шифра AES, весьма наглядно демонстрируются раундовые операции. Автор не ставил перед собой цели показать все детали процесса зашифрования, но даже этот упрощенный вариант (на уровне байтов), что почти совпадает с элементами поля GF(2⁸), удачно демонстрирует работу шифра AES. Детальное изложение для уяснения математических основ работы с элементами поля и конкретная реализация в различных представлениях элементов поля здесь.

Операция AddRoundKey для i-го раунда

Суммирование столбцов State с раундовым ключом (Add Round Key).

Раундовый ключ, предварительно вычисленный и выбранный, представляется в форме (квадрат) State (Key). Суммирование выполняется для одноименных столбцов. Пара столбцов State (Data) и State (Key) операцией XOR поразрядно складывается.

Таким образом, преобразование AddRoundKey состоит из суммирования матрицы S блока (квадрата 44) сообщения в M4(GF(2⁸)) с частичным Ki ключом i-го раунда (также с квадратом 44 ). Результат суммирования обозначается SiA, т е. состояние после i-го AddRoundKey M4(GF (2⁸)) M4(GF (2⁸)), S SiA = S + Ki.
В начальном раунде (r = 0) выполняется только Add RoundKey суммирование по mod2 (XOR) байтов блока данных и блока ключа. Результат этого раунда используется как исходное (State) состояние для первого раунда (r=1) и представляется в формате квадрат.
Шифрование сообщений AES

Пример 1. Сообщение (исходный текст = ИТ) в 16-ричном представлении
имеет вид 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34,
а ключ шифра 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 0f 4f 3c.
Операция AddRoundKey S + Ki для всех 16 байтов квадрата State
Предварительный раунд зашифрования подготавливает сумму ИТ с ключом.

Их Сумма, представленная байтами в формате квадрат при Nb = Nk = 4 и Nr = 10 имеет вид:


Рисунок Результат предварительного раунда (до первого)

Ключ и исходный текст (это может быть и звук и картинка и др.) представлены в 16-ричном виде. Это не самое удобное представление, поэтому преобразуем его к двоичным векторам и выполняем сложение по модулю 2.



Для удобства ручного счета 16-ричное представление байтов преобразуется в двоичное, а после суммирования обратный переход от двоичного к 16-ричному представлению.

Операция SubByte для i-го раунда

Замена байтов (Sub Bytes ( ) )

Первый раунд. Операция AddRoundKey уже выполнена. Все байты суммарного квадрата (исходного состояния обозначим их точками (х, y) на некоторой плоскости) преобразуются функцией S (x, y) в новые значения табличка "Замена байтов".

Заменяем угловой (левый верхний) байт State = Сумма, (равный 19), на байт d4 из таблицы замен S-блока и следующий (3D) на 27 (они выделены заливкой). Так преобразуются все 16 байтов квадрата "Сумма".

Так для первого байта {19} = {x, y}, x = 1, y = 9, S(19) = d4. Все такие значения также представляются квадратом с замещениями.

Функция S (x, y) табулирована, т. е. задана таблицей с двумя входами строка (х) и столбец (у). Поскольку все многообразие байтов исчерпывается числом 256, то таблица имеет размер 1616 = 256, а ее строки и столбцы пронумерованы x, y = 0(1)15 цифрами 16-ричной системы счисления. Вид таблицы S (x, y) приведен ниже.



Покажем, как получены значения этой таблицы S (x, y). Вначале каждый байт исходного состояния {x, y} преобразуется в инвертированный {x, y}^-1, в мультипликативный обратный в поле GF(2⁸). Затем байт умножается на матрицу А. Нулевой байт переходит в себя {0, 0}^-1 = {0, 0}.

Каждая строка матрицы аффинного преобразования А содержит лишь пять единиц.

Затем к инвертированному (обращенному) байту применяют аффинное преобразование, которое в векторно-матричной форме записывается так



Аффинная матрица

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного состояния подвергается такому преобразованию, и их значения вписаны в квадратную таблицу S (x, y).

Скалярное представление аффинного преобразования имеет следующий вид (общий вид i -го элемента результата):


где ; , ^' соответственно исходное и преобразованное значение i-го разряда байтов, i = 0(1)7.

Выражение для ^' содержит 6 слагаемых, так как каждая строка циклической матрицы аффинного преобразования имеет лишь 5 ненулевых элементов; шестое слагаемое берется из вектора сдвига ci.

Для ускорения вычислений используется квадратная таблица фиксированных значений (S (x, y) блок). Значение b =63 16 ричное число принадлежит GF(2⁸) и матрица а имеет вид, показанный ранее. В сущности, операция реализует подстановку (замену) байт из S квадрата 1616.

Преобразование SubByte состоит в применении к каждому элементу матрицы S элементарного преобразования s. Результат этой операции обозначается SiSu, т. е. это состояние блока текста после операции SubByte i-го раунда. Не путать буквы S и s (большую и малую).

В сущности, здесь выполняется аффинное преобразование с постоянным вектором сдвига, обозначаемым символом b
M4 (GF(2⁸)) M4 (GF(2⁸)).

Запись векторов сверху (младший разряд) вниз. Вектор сдвига c = {63}₁₆, что в таблице S (x, y) отражено для байта {00}. Каждый байт исходного текста (состояния) подвергается такому преобразованию, и их значения вписаны в таблицу S (x, y).

Пример 2. Первый байт исходного состояния первого раунда равен {19}. Мультипликативный обратный для него (см. Табл. П1) равен 3f = {19}^-1= 0011 1111₂ =¹¹³. Это значение легко находится по таблице элементов поля GF(2⁸). При отсутствии таблицы элементов поля можно выполнить и непосредственные вычисления.

Пусть байт {x, y} = 09 = ¹⁹⁹ и {09} ^-1 = 4f, тогда
b0 = (1+0+1)mod2 = 0, b4 = (1+1+0)mod2 = 0,
b1 = (1+0+1)mod2 = 0, b5 = (0+1+1)mod2 = 0,
b2 = (1+0+0)mod2 = 1, b6 = (0+1+1)mod2 = 0,
b3 = (1+1+0)mod2 = 0, b7 = (0+1+0)mod2 = 1.
Результирующий вектор ( 0, 1, 2, 3, 4, 5, 6, 7) =1000 0100₂ = 84.

Следовательно, байт 4f S-блоком преобразуется в байт 84, что можно увидеть в таблице замен S (x, y) = S (4, f) = 84. Этот результата лежит на пересечении строки с номером 4 и столбца с номером f. Геометрическое представление замены байтов (SubBytes) изображено на рисунке 4, где s нелинейное преобразование, определяемое соотношениями:
GF(2⁸) GF(2⁸),

Операция ShiftRows для i-го раунда

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

Выбор величин сдвигов подчинен следующим условиям:
Каждая строка должна иметь индивидуальное смещение элементов;
Реализация операции должна быть простой;

Совокупность сдвигов наилучшим образом должна препятствовать проведению атак:

А) атак, использующих сокращенные дифференциалы
В) атак типа Square.


Рисунок 5 Состояние после сдвига строк

ShiftRows преобразование перемещения байтов строки в матрице состояния S, которое циклически сдвигает строки матрицы состояния на различные по величине смещения. Результат операции обозначается SiSh, т. е. это состояние после операции ShiftRows
i-го раунда. Такие перемещения могут быть описаны Р(х) перестановкой байт из квадрата S, которая имеет вид:


Из всех вариантов сдвигов, обеспечивающих наилучшее противостояние атакам, был выбран самый простой циклический сдвиг и c0 = 0.

Геометрическое представление преобразования замены байтов изображено на рисунке 4, где приведены квадраты числового примера для первого раунда.

Сдвиг строк в массиве State выполняется влево. Строка с номером нуль остается неподвижной (не сдвигается). Остальные строки RIJNDAEL сдвигаются на число байтов c1, c2, c3, указанное в квадрате на рисунке 5), в зависимости от числа Nb байтов в блоке данных. Строка 1 сдвигается на c1 байтов, строка 2 на c2 байтов и строка 3 на с3 байтов.

В стандарте AES величина Nb = 128 постоянная, поэтому всегда c1 = 1, c2 = 2 и c3 = 3.

Таблица Величины сдвигов

Операция MixColumns для i-го раунда

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

• Обратимость получаемого результата.
• Линейность в поле GF(2⁸); выполнение этого требования создает условия для применения алгоритма прямого расшифрования.
• Достаточно сильное рассеивание данных.
• Высокую скорость реализации на 8-разрядных процессорах; единообразие обработки любых блоков данных, т. е. симметричность.
• Простой вид для описания и реализации.

Все названные требования удовлетворены в стандарте АES. Из возможных линейных преобразований 4 bytes 4 bytes выбрана операция умножения многочленов (элементов поля) по модулю (x) = x⁴ + 1. Выбор коэффициентов сомножителей обусловлен требованиями 1, 3 и 4. Коэффициенты {00}, {01}, {02}, {03}, соответствуют: {00} отсутствию преобразования; {01} не требуется умножения; {02} умножение при использовании функции x time ( ) и {03} при использовании x time и последующего сложения по mod2 промежуточных результатов.

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

Сущность преобразования Mix Columns ( ) состоит в следующем. Столбцы State
S = < S0c, S1c, S2c, S3c>, с = 0(1)3, после сдвига строк рассматриваются как элементы поля GF(2⁸) и умножаются по mod(x⁴ + 1) на фиксированный многочлен g(x):
g(x) = {03}x³+{0,1}x²+{01}x+{02}.


где с номер столбца State, c = 0(1)3.

где А циркулянтная матрица, т. е. линейное инвертируемое (обратимое) отображение на GF (2⁸), А принадлежит M8(GF (2⁸)),
обозначает умножение матрицы из GF (2⁸) и вектора
х -1 = {b0 b1b7 }b, который рассматривается как элемент над полем GF(2) векторного пространства, эквивалентный транспонированному в вектор {b0 b1b7 }b.

Развернем это выражение в скалярную форму
S0C = ({02} S0C) ({03} S1C) S2C S3C;
S1C = S0C ({02} S1C) ({03} S2C) S3C;
S2C = S0C S1C ({02}S2C) ({03} S3C);
S3C = ({03} S0C) S1C S2C ({02} S3C).
В результате выполнения указанных действий байты вектора
SC = <S0c, S1c, S2c, S3c> будут заменены байтами S0C, S1C, S2C, S3C.

MixColumns преобразование состоит из умножения двух матриц. Матрицы S промежуточного состояния текста и фиксированной матрицы A0 обе из введенного ранее множества M4 (GF (2⁸)). Результат операции обозначается символом SiM, это по существу состояние S после операции MixColumns i-го раунда.

M4 (GF (2⁸)) M4 (GF (2⁸)),
S Si, М = АS,
где матрицы А и А^-1 (циркулянтные матрицы) определяются как:

.
Операция MixColumns произведение специальной цикловой А0 матрицы на матрицу State, по правилу строка на столбец

.
Два пустых столбца в результирующей матрице оставлены для самостоятельного заполнения.
Начинаем с левого углового элемента нулевой строки квадрата. Его значение определяется суммой произведений пар элементов: {02}D4{03}BF {01}5D {01}30. Элементы обеих матриц это элементы поля GF(2⁸) с одной стороны и информационные байты в 16-ричном представлении с другой. Умножение элементов в поле удобно выполнять в степенном представлении примитивного элемента.

Пользуясь таблицей поля, выполним замену 16-ричного представления на степенное для левой цикловой матрицы элементы {01} = a⁰, {02} = a²⁵, {03} = a¹. Для правой матрицы в произведении получим


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

1-й элемент нулевой строки определяется в виде:

{02}D4 {03}BF {01}5D {01}30 = a²⁵а⁶⁵ a¹а¹⁵⁷ a⁰а¹³⁶ a⁰а¹⁰¹ = а⁹⁰ a¹⁵⁸а¹³⁶а¹⁰¹,

2-й элемент нулевой строки определяется аналогичным соотношением (поменялся столбец)

{02}Е0{03}B4 {01}52 {01}АЕ = a²⁵а⁶⁸ a¹а²⁵¹ a⁰а²⁵³ a⁰а¹²³ = а⁹³ a²⁵² а²⁵³а¹²³,

3-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}B8{03}41 {01}11 {01}F1 = a²⁵а⁵⁹ a¹а¹⁴³ a⁰а⁴ a⁰а⁷⁴ = а⁸⁴ a¹⁴⁴ а⁴ а⁷⁴,

4-й элемент нулевой строки определяется аналогичным соотношением поменялся столбец

{02}1Е{03}27 {01}98 {01}Е5 = a²⁵а²⁸ a¹а¹⁰⁶ a⁰а⁸⁹ a⁰а³² = а⁵³a¹⁰⁷ а⁸⁹а³².

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



Перейдем к вычислению элементов 1-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 0-й строки.

1-й элемент 1-й строки матрицы перемешанных столбцов определяется соотношением.


Перейдем к вычислению элементов 2-й строки матрицы (изменяется номер строки циклической матрицы). Элементы в парах произведений изменяются относительно 1-й строки.

1-й элемент 2-й строки матрицы перемешанных столбцов определяется соотношением



Перейдем к вычислению элементов 3-й строки матрицы (изменяется номер строки циклической матрицы) Элементы в парах произведений изменяются относительно 2-й строки.

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

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

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

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

1. Атака на ключ шифра AES

Сначала, описывается атака на AES в простом случае, и после этого становится видно, как можно обобщить такую атаку. Цель рассматриваемой атаки состоит в том, чтобы восстановить ключ K(Nr) шифра. Как только определяется частичный (раундовый) ключ K(Nr), становится просто получить ключ K.

1.1 Принцип атаки

Предполагается, что есть возможность изменять путем внесения ошибки "" в отдельный байт матрицы S состояния (один из 16) после операции ShiftRows (Nr 1), т. е. предпоследнего раунда, и известен индекс (#клетки) искаженного байта (элемента) состояния. Эта последняя гипотеза может быть опущена, она введена для того, чтобы более доступно объяснить механизм атаки. Новое значение элемента состояния предполагается неизвестным.

Ошибка "" распространяется на не более чем четыре байта состояния выхода процесса. Для всех 4-х изменяемых элементов состояния выхода, находится множество значений (набор) векторов возможной ошибки " " п. 1.4. Кроме того, появляется возможность пересекать множества возможных значений "" (определение 1) для этих четырех элементов. При пересечении таких множеств получается меньший набор, и таким образом, сокращается количество требуемых зашифрованных текстов для полного анализа.

Наконец, для каждой ошибки, мы выводим некоторые возможные искаженные значения четырех элементов предшествующего раундового ключа. Формируя другие зашифрованные тексты, мы находим четыре байта раундового ключа К(10). Эта атака остается успешной даже с большим количеством общих предположений о местоположении ошибки. Таких как отсутствие сведений о местоположении ошибки перед 9-м MixColumns() преобразованием. Разность матрицы шифрованного текста с искажениями и без них выявит искажения и их положение (в примере это позиции 0,7,10,13).

Предполагается также, что ошибки " ", вводимые в раунде 8 (до 8-го MixColumns() преобразования), могли бы быть полезными для анализа. Но при этом возрастает количество требуемых зашифрованных текстов для более полного анализа. Для рассматриваемого числового примера, необходимо около десяти зашифрованных текстов, чтобы получить четыре байта раундового ключа К(10), в условиях, когда не рассматривается гипотеза относительно местоположений ошибки.

1.2 Числовой пример воздействия ошибки на сообщение

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

Вход = 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34;
Ключ шифра = 2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C;
Выход = 39 25 84 1D 02 DC 09 FB DC 11 85 97 19 6A 0B 32;
Ошибка " " = 1Е 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00.

Следующая диаграмма показывает значения, содержащиеся в массивах состояний, в соответствии с длиной шифрблока и длиной ключа шифра по 16 байтов каждый (то есть, Nb = 4 и Nk = 4).

Распространение ошибки показывается жирным шрифтом и в шестнадцатеричном представлении. Ниже представлены квадраты состояния State в разных ситуациях


Ошибка " " = 1E, введенная в 0-й байт состояния 9-го раунда, приводит к изменениям в четырех байтах конечного состояния. Примеры вычислений для угловых клеток главной диагонали квадрата состояния:

в левую верхнюю (угловую) клетку квадрата State 9-го раунда вводится ошибка " " = 1Е

87 1Е = 1000 0111 0001 1110 = 1001 1001 = 99
нижний правый угол State 9-го раунда после MixColum9 суммируется с байтом ключа К(9):

BC 6E = 1011 1100 0110 1110 = 1101 0010 = d2.
вычисления значений результирующей ошибки.

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

Например, в 16-ричном виде находим значения ошибок:
Таблица 7 вычисление значений ошибок

Получили в итоге разностные ошибки $inline$ _0=E7, _1=51, _2=47, _3=99$inline$. Дадим пример вычисления последнего байта ошибки:

62 FB = 01100010 11111011 = 1001 1001 = 99.
Положения измененных ошибкой байтов состояния
$inline$ _0=E7, _1=51, _2=47, _3=99$inline$.указывают на индексы для элементов раундового ключа (последнего раунда), как К[0], K[7], K[10], K[13]. Здесь 0, 7, 10, 13 номера клеток матрицы состояния, а матрица Ао это матрица преобразования перемешивания столбцов процесса зашифрования, первый столбец которой имеет вид: 02, 01, 01, 03.

Как введенная ошибка действует на конечном заключительном состоянии

.

Анализ информации, получаемой при введении ошибки

Единственной операцией, которая может содержать информацию относительно ключа K(Nr) является последнее SubBytes( ) преобразование. Следовательно, мы имеем четыре уравнения, где x0, x1, x2, x3, являются неизвестными переменными.

Мы хотим получить решения следующих четырех уравнений:




Байты $inline$ _0, _1, _2, _3$inline$, измененные ошибкой, содержат информацию о неизвестном ключе, сформировавшем эти байты.

Все такие уравнения можно обобщить в единственном уравнении
s(x +c) + s(x) =, (1)
где постоянная величина с = 01, 02 или 03 и именно это уравнение будем далее решать и анализировать.

Определение 1. Множество решений уравнения (1) для ошибок обозначим символом B(c) и определим выражением:
B(c)=S(c)={ GF [2⁸]: x GF [2⁸],s(x +c) + s(x) =}, |B(c)| =127.

Это индивидуальная область ошибок, соответствующая конкретной ошибке . Для других области для ошибок будут другими.

Определение 2. Рассмотрим линейное преобразование над полем GF (2):
: GF [2⁸] GF [2⁸];
xx² + x.

Образ отображения Im() GF (2)-векторного пространства, т.е. множество элементов
(x² + x) из GF [2⁸] обозначим Е1 = Im() и его размерность dimGF(2)(E1) = 7. Если Е1, то существуют два различных решения x1, x2 GF [2⁸] уравнения x²+x=, и решения удовлетворяют соотношению x2 = x1 + 1 и x2x1 = (modd x,(2⁸-1) ) по теореме Виеты.
Переменная это свободный член квадратного уравнения

Проиллюстрируем примером рассмотренное линейное преобразование.
Пример Задано поле GF [2⁸], над его элементами выполняется преобразование xx² + x.

Таблица 8 начальный фрагмент поля GF [2⁸] и результаты преобразования элементов.


В таблице 8 показано как преобразование изменяет пары, рядом стоящих в упорядоченном по десятичным значениям элементов списке, в один и тот же элемент поля. Из этого следует, что результат преобразования (образ) в два раза меньше прообраза (поле как бы сжимается в 2 раза). Этот принцип сжатия размерности множеств положен в основание предлагаемой атаки.


Предложение 2. Следующее утверждение справедливо для 1, 2 GF [2⁸] {0}:

2. Обобщение и реализация

Первым делом при помощи специального программного приложения формируются 20-ть шифртекстов с ошибкой. Для этого вводятся в модель (программу) исходный текст, ключ, ошибка и задается номер позиции, в которой ошибка помещается. Нажатием кнопки Пуск программа реализует алгоритм и выведет результаты 2-х последних раундов шифрования в развернутом виде для текста с ошибкой, текста без ошибки и разность между ними. После этого сохраняется шифртекст без ошибки и с ошибкой. Циклически изменяется значение ошибки и нажатием кнопки Пуск получают следующий шифртекст с ошибкой. На одном значении столбца формировалось по 5 шифртекстов с ошибкой.
Для реализации атаки необходимо при помощи программы открыть файл с шифртекстом без ошибки и шифртекстом с ошибкой (данные в файле представляются в 16-ричном виде), шифртексты и разность между ними отображаются в виде квадратного массива байтов (State). Нажатием кнопки Искать ключ запускается процедура поиска возможных байтов ключа. Текущее состояние процессов отображается в текстовом окне. После этого открывается шифртекст с другой ошибкой, и процедура повторяется. При получении байта ключа 10-го раунда он также отображается в соответствующем квадратном массиве байтов. При прогонке всех 20 сформированных на предыдущем этапе шифртекстов с ошибкой велика вероятность получения значений всех байтов ключа 10 раунда (иначе нужны ещё шифртексты с ошибками). После этого восстановить ключ шифрования по алгоритму Восстановление ключа шифра с использованием последнего подключа приведенному здесь.


Рисунок 11 Программный продукт построения шифртекста с ошибкой

Для ускорения процедуры перебора шифртекстов с ошибкой можно поставить галочку напротив кнопки Найти ключ


Рисунок 12 Программная реализация атаки

Пример работы программного продукта
Исходный текст 3243f6a8885a308d313198a2e0370734
Ключ 2b7e151628aed2a6abf7158809cf4f3c
Ошибка 1 1e000000000000000000000000000000
Шифртекст с ошибкой 1 de25841d02dc0962dc11c297193b0b32
Возможные байты ключа




Рисунок 13 Пример работы программы

Ключ 10 раунда d014f9a8c9ee2589e13f0cc8b6630ca6 ключ полностью восстановлен
Восстановленный ключ 2b7e151628aed2a6abf7158809cf4f3c, как и ожидалось он совпадает с заданным в сеансе шифрования ключом.

2.1. Ситуация, когда информация о местоположении ошибки отсутствует

В этом пункте, предполагается, что ошибка содержится в байте состояния, между последними двумя выполнениями операции MixColumns. Это тот же самый случай, когда предварительно за исключением того, что ошибка может быть заключена между байтов от 1 до 16. Ошибка при этом размножается операцией MixColumns и распространяется уже на 4 байта состояния.

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

2.2. Аппаратное устройство

Предположим, что имеется возможность физически воздействовать на аппаратное устройство AES. Сначала вычислим шифры для более чем десяти случайных открытых текстов при помощи AES устройства. Затем изменяем примером проект, вырезая строки и подключая их к земле (или Vcc) temporaly между двумя байтами в течение раунда, расположенного в двух раундах перед завершением. В конце концов, мы имеем байт в раунде Nк -2, всегда заменяемый 00 (или FF).

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

Литература
[1] FIPS PUB 197: Advanced Encryption Standard, csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[2] Boneh, DeMillo, and Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EU-ROCRYPT97, pp. 37-51, 1997.
[3] E. Biham & A.Shamir, Differential Fault Analysis of Secret Key Cryptosystems, CS 0910, Proceedings of Crypto97.
[4] Ross J. Anderson, Markus G. Kuhn: Tamper Resistance a Cautionary Note, The Second USENIX Workshop on Electronic Commerce Proceedings, Oakland, California, November 18-21, 1996, pp 1-11, ISBN 1-880446-83-9.

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

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

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

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

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

Предпосылки и возможности

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

Математической основой этих фактов и явлений служат:
односторонняя (однонаправленная) функция;
односторонняя функция с лазейкой (с секретом).

Определение. Функция f: X Y называется односторонней, если существует эффективный алгоритм ее вычисления при любом Х, но не существует такого алгоритма для вычисления обратной к ней функции.

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

Математикам давно знакома проблема факторизации и они ищут пути ее эффективного решения. К основным достижениям (результатам) математики в области факторизации чисел следует отнести следующее:
метод Евклида отыскания наибольшего общего делителя (НОД), в котором для пары чисел b и а, если они составные, но взаимно простые, НОД (а, b)=1. Но если эти числа имеют общий делитель, то алгоритм НОД находит больший из всех делитель d и НОД (а, b)=d.

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

метод факторизации П. Ферма известен с 1643 года. Он находит наибольший множитель d числа N, не превосходящий . Метод требует О() арифметических операций и работает наиболее быстро, если множители p и q имеют близкие значения, т.е. когда их разность мала.
решето Эратосфена.

Метод линейного решета (алгоритм LS)

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

На числовом интервале , где 0 < e 1/2 фиксированное действительное число, рассматриваются две функции двух целочисленных переменных , определенных в этом интервале I равенствами:


где $inline$ h = [N^], например,h =[15347^] = 124; a, b Z I.$inline$

В силу сравнимости этих функций по модулю N их можно использовать при построении требуемых соотношений. Фиксируется граница В > 0 для элементов факторной базы , которую образуют все простые числа, не превосходящие В, а также целое число 1. Далее рассматривается сравнение по модулю N

Допустим, что правая часть сравнения может быть представлена произведением и левая часть будет полным квадратом, если величины входят в произведение четное число раз $inline$П_{i,j}t(a_i, b_j)=(-1)_0^ П_{p_i}p_i^{_i}$inline$,
где рi простые числа из факторной базы S, а целое число, являющееся полным квадратом.

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

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

И сами величины (a, b) принимают небольшие значения. Значения ограничены и верна оценка:
Проверка делимости величины s (a, b) на простое число р для произвольных a, b I сводится к проверке делимости на р величины

Это легко показывается. Пусть простое число р S делит значение величины s (a, b) при некоторых а. Но из равенства


следует, что для произвольных целых значений k, l.

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

Квадратичное решето (QS)

Этот алгоритм (quadratic sieve-QS) предложен в 1981 году Карлом Померансом и почти 10 лет был лучшим (до предложенного в 1990 алгоритма SNFS (special number field sieve), обеспечившего разложение на множители 9-го числа П.Ферма (155 десятичных знаков)).
Возможности квадратичного решета ограничиваются разложением в сомножители чисел, с не более чем 110 десятичных цифр в их описании. Оценка сложности (эвристическая) алгоритма даже после многочисленных усовершенствований составляет арифметических операций.

При рассмотрении QS важными понятиями, которые желательно удерживать в уме, являются:
вектор показателей степеней чисел -<4 0 1 1>, где, например, для имеем
линейная зависимость векторов (см. пример 3 здесь);
факторная база S=(2,3,5,7) набор малых простых чисел, для которых N -квадратичный вычет;
гладкие числа вычеты, которые <N и раскладывается в простые числа из базы S;
процедура просеивания.

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

Делители p и q отыскиваются с помощью специальных чисел-значений многочлена вида $inline$q(x)=(j+[N^])^2-Nx(j)^2(mod N)$inline$, где $inline$x(j) =j+[N^] и j$inline$ пробегает значения в диапазоне -М<j<М. Значения q(x) в целых точках таблицы Д являются квадратами по (mod N).

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

Определение. Факторная база S набор малых простых чисел, включающий р =-1 и все простые числа рi, рiВ, такие, что символ Лежандра (N/pi)=+1, т.е. N является квадратичным вычетом для всех рi из факторной базы S.

Определение. Пара целых чисел называется гладкой относительно факторной базы S, если: выполняется сравнение и b раскладывается в произведение элементов из S.

В методе QS формируется множество аргументов х и чисел q(x), среди которых отыскиваются гладкие относительно факторной базы. Эти числа используются для построения соотношений, декларированных в цели метода. Ниже в примере приводится вариант такого формирования (таблица Д).

После формирования последовательности пар значений (х, q(x)) выполняем просеивание и находим значения хi, для которых , т. е. q(x) раскладывается на сомножители в нашей факторной базе S.

Если процесс формирования последовательности пар значений (х, q(x)) не является трудным для понимания, то процесс просеивания при чтении текста требует нашего внимания значительно больше. Раскроем его здесь в деталях. Пусть задан многочлен q(x) Z[x]. Будем отыскивать все целые числа K в отрезке [-М, М] такие, что некоторые значения q(x) раскладываются в произведение простых чисел из заданного множества S.

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

Алгоритм QS

Все теоретические положения QS удобно оформить в виде шагов алгоритма:
1. Выбираются границы P и A порядка . вид многочлена просеивания и диапазон значений.

2. Для аргумента $inline$x = [N^ ] +1, [N^ ] + 2, , [N^ ] +A$inline$, и многочлена q(x) выписываем в таблицу Д по порядку пары целых чисел .

3. Для каждого нечетного простого числа p P проверяем условие Лежандра (N/p)=1 и, если оно не выполняется, удаляем p из факторной базы. Однако, если мы разложим каждое значение q(x) по степеням простых чисел, то увидим, что некоторые числа из них не имеют множителей больше порога (в примере в разложении у 4-х чисел все факторы p11), а р = 5 не является
делителем ни одного из них, следовательно, факторную базу примера мы ограничим такими простыми числами S = (2,3,7,11):

$$display$$ 132 = 2^2 3 11 , 7623 = 3^2 7 11^2 , 8316 = 2^2 3^3 7 11 , 27783 = 3^4 7^3 .$$display$$

4. Предполагая, что p такое нечетное простое число, что N квадратичный вычет по модулю p; решаем сравнение $inline$x^2 N (mod p^) для = 1, 2,$inline$

Берем значения в порядке возрастания, пока не окажется, что уравнение не имеет решений x, сравнимых по модулю с каким-либо из чисел в области $inline$[(kN)^ ] +1 x [(kN)^ ] +A$inline$. Обозначим через наибольшее из таких чисел, для которых в указанной области найдется число x со свойством $inline$x^2 N (mod p^)$inline$.

Пусть два решения $inline$x^2 N (mod p^)$inline$ и $inline$x_2 N- x_1(mod p^)$inline$. Не требуется, чтобы принадлежали отрезку $inline$[(kN)^ ] +1 x [(kN)^ ] +A$inline$.

5. При том же значении p просматриваем список значений , полученный в пункте 2. В столбце, соответствующем p, ставим 1 против всех значений , для которых x отличается от x1 на некоторое кратное p. После этого заменяем 1 на 2 для всех таких значений , что x отличается от x1 на кратное .

Затем заменяем 2 на 3 у всех значений , для которых x отличается от x1 на кратное , и так далее до . Затем делаем то же самое с . Наибольшим числом, которое появляется в этом столбце, будет .

6. Каждый раз, когда в пункте 5 ставим 1 или заменяем 1 на 2, 2 на 3 и т.д., делим соответствующее число на p и сохраняем полученный результат в той же ячейке.

7. В столбце под p = 2 при N 1(mod 8) просто ставим 1 против с нечетным x и делим соответствующее на 2. При N 1(mod 8) решаем уравнение и продолжаем в точности также, как в случае нечетного p (за исключением того, что при 3 уравнение будет иметь 4 различных решения ).

8. Когда указанные действия будут проведены для всех простых чисел, не превосходящих P, отбросим все , кроме тех, которые обратились в 1 после деления на все степени p, не превосходящие P.

Тогда получится таблица того же вида, что в примере метода факторизации Ферма, в которой столбец bi будет содержать все такие значения x из интервала $inline$[(kN)^ ] +1, [(kN)^ ] +A$inline$, что есть B-число, а остальные столбцы будут соответствовать тем значениям p P, для которых N квадратичный вычет.

9. Оставшаяся часть процедуры в точности совпадает с процедурой из факторизации Ферма.

Пример. Будем применять последовательно положения теории алгоритма. Пусть задано составное число N =pq =112093, которое нужно разложить на множители. Следуя концепции квадратичного решета, извлекаем квадратный корень из N, $inline$m =[N^] =[112093^] =334,8 =335$inline$ и округляем его значение до большего целого.

Далее в методе необходимо сформировать для i =1(1)А таблицу Д пар чисел , возрастающих по i с шагом 1 значений аргументов (ограничимся для А = 40 значениями) и соответствующих им значений функции.

Таблица Д Множество, содержащее В-гладкие числа (значения q(x)) с целыми аргументами


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

Имеется возможность в процессе решения выбранное множество чисел изменять (уменьшать, увеличивать). В таблице Д среди значений q(х) нет полных квадратов. Теперь можно приступить к поиску чисел, которые обеспечат получение однородной системы линейных уравнений по модулю 2. Сама эта система нетривиальными решениями будет иметь переменные, произведения которых будут получать значения равные полному квадрату.

Просеивание

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

Уже сформирована 2-х строчная таблица Д пар чисел (х-верхняя строка, q(x) нижняя) Все подряд значения q(x) (нижней строки таблицы Д) последовательно делят на все рj простые числа (и их степени) из факторной базы S. Результаты деления вписывают в прежние позиции.

Те значения, которые не делятся на рj оставляют без изменений. Цель таких преобразований не вычеркнуть полностью разделившиеся числа из таблицы, а получить в результате деления в их ячейках единичные значения, что соответствует В-гладким числам, т.е. полному разложению числа в таких позициях на степени простых из S. Также для этих ячеек выявляется аргумент х.

Дальше будем обрабатывать (делить) числа из строки таблицы Д таблицы Д, которые соберем в одной новой Q таблице (41 позиция). Все числа этой новой таблицы делим на р = 2, = 1. Аргументы i в таблицу не пишем, так как это просто номера ячеек.

В результате получаем все четные числа, поделенные пополам в таблице Q, столбцы четных чисел чередуются с нечетными. Это закономерно. В исходной таблице четные чередовались с нечетными числами. Для любого целого d выполняется равенство, так что, если число из набора q(х) делится на d, то все числа отстоящие от него на расстоянии, кратном d также делятся на d


Изменившиеся числа выделены заливкой в ячейках, делим на (р = 2 =2), т.е. еще раз.

Теперь все числа в таблице Q нечетные. Деление на простое р =2 и его степени 22=4 завершилось. Начинаем делить на следующее простое число из факторной базы (р =3, = 1)


Если некоторое число разделилось на три, то каждое третье после него также делится на три. Таких цепочек чисел в таблице Q возникло две: 1-я цепочка начинается с первой ячейки; 2-я с третьей.

Это следствие того, что квадратичное сравнение по модулю р имеет два решения (если вообще имеет решение). Делим на тройку всего три раза (р =3, = 3), пока таблица при делении на нее не перестанет изменяться.


Следующее деление на 3 таблицу Q не меняет. Переходим к делению на (р =7, = 1) т.е. к следующему числу факторной базы. Опять возникли 2 цепочки с началом в 4-й и в 5-й ячейках.

Еще два прохода с делителем (р = 7, = 3) приводят к появлению первой единицы в таблице (предпоследнее число таблицы 49:7:7 =1).


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


В ячейках таблицы (с аргументами х=335, 346, 347, 374) появились новые единицы. В позициях последней таблицы, содержащих единицы в исходном заполнении уже размещались 11-гладкие числа, но мы узнали об этом только после просеивания. Вот эти числа: 132, 7623, 8316, 27783.

Система линейных алгебраических уравнений и ее решение

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

Выше показано, как эти четыре В-гладких числа найдены, без раскладывая всего списка чисел на множители. Соответствующая система линейных уравнений AX = 0(mod 2) имеет матрицу коэффициентов по модулю 2 следующего вида:


Верхняя строка матрицы гладкие числа, левый столбец- факторная база. Следующим шагом нами получена нетривиальная линейная комбинация по модулю 2, в которой коэффициенты 0 и 1, и дающую в результате нулевой вектор. Для этого полученные результаты (В-гладкие числа) используют для формирования системы линейных алгебраических уравнений (СЛАУ), АХ0(mod2) решения которой приводят к окончательному результату-факторизации N.

Формируется А матрица СЛАУ, в которой векторы показателей гладких чисел записываются в столбцах, а вектор Х определяемый неизвестный. Решением этой СЛАУ по модулю 2 получается вектор . При это решение нетривиально: (1110), что означает полным квадратом будет произведение первых трех чисел.


В предшествующих обозначениях получены зависимости
X = П xi = 335 346 347=40220770, y = 91476.
Здесь X y = 40220770 91476 = 40129294.
Находим НОД (X y, N) = НОД (40129294, 112093) = 112093.
К сожалению, найденный делитель числа N = 112093 тривиален. Заметим, что и
НОД (X + y, N) = НОД (40312246, 112093) = 1 тривиальный делитель.

Возьмем тогда другое решение системы АХ0(mod2), а именно решение (0101), получающееся при . Оно означает, что точным квадратом будет произведение второго и четвёртого чисел:


Имеем X = Пxi = 346 374 = 129404, y = 14553. Находим
НОД (X y, N) = НОД (114851, 112093) = 197.
Найден нетривиальный делитель 197 числа N = 112093. Теперь число N можно разложить на множители: N = 112093 = 569 197.

Заключение

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

Список, использованной литературы

1. Агафонова И.В. Факторизация больших целых чисел и криптография 2006.
2. Брассар Ж. Современная криптология. М.: ПОЛИМЕД, 1999.
3. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003
4. Нестеренко А.Ю. Теоретико-числовые алгоритмы в криптографии. Москва 2012
5. Rivest R. L., Shamir A., Adleman L. M. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. 1978. V. 21, P. 120126.
6. The RSA Challenge Numbers // RSA Laboratories. www.rsasecurity.com/rsalabs/node.asp?id=2093
7. Стренг Г. Линейная алгебра и её применения. М.: Мир, 1980.
8. Смарт Н. Криптография. М.: Техносфера, 2005.
9. Shanks D. Five number-theoretic algorithms // Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), Utilitas Math. 1973. P. 5170. Congressus Numerantium, No. VII.