Практическая стойкость шифров.

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

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

Более надежный способ используется в военном протоколе аутентификации, принятом в США. Отправитель и получатель сообщения имеют опечатанный пакет со случайной последовательностью символов, вырабатываемой компетентным органом. Каждый из участников связи отвечает за защиту своего опечатанного пакета и имеет инструкцию не вскрывать его, пока не потребуется аутентификация сообщения. Кроме того, отправитель и получатель имеют общий секретный ключ. При аутентификации сообщения отправитель вскрывает пакет, дополняет сообщение символами этой секретной последовательности, а затем шифрует полученное сообщение, используя секретный ключ. Для шифрования обычно используется симметричный шифр. Получатель, после расшифрования сообщения (с помощью своей копии ключа) вскрывает пакет и производит аутентификацию. Сообщение интерпретируется как аутентичное только тогда, когда при расшифровании будут получены символы секретной последовательности. Если используется стойкое шифрование, то оппоненту (который не знает ключа) при осуществлении активной атаки не остается ничего другого, как случайным образом выбирать шифртекст в надежде, что он будет принят получателем как аутентичный. Если секретная последовательность состоит, например, из r битов, то вероятность того, что при расшифровании случайно выбранный оппонентом “шифрованный текст” даст со общение, заканчивающееся неизвестной ему, но правильной последовательностью, будет составлять величину 2^–r.

Другой метод нашел распространение при аутентификации электронной передачи фондов в Федеральной резервной системе США. Подобные передачи должны быть аутентифицированы с использованием процедуры, которая фактически реализована в криптографическом алгоритме, определенном в стандарте шифрования данных США (ранее DES, теперь — AES). Аутентификатор генерируется в режиме, называемом шифрованием со сцеплением блоков. В этом режиме сообщение разбивается на 64 битные блоки – М = M₁M₂…М_n, которые последовательно шифруются следующим образом. Блоки шифртекста С₁,С₂,… вырабатываются по рекуррентной формуле

С_i = Е_k (C_i-1 Å М,),

при этом вектор С₀ полагается равным начальному вектору IV (Initial Vector). Начальный вектор меняется ежедневно и хранится в секрете. Схематично этот режим изображается следующим образом:

Рис.11. Режим выработки имитовставки.

Процедура повторяется до тех пор, пока не будут обработаны все блоки текста. Последний блок шифртекста — С_n является функцией секретного ключа, начального вектора и каждого бита текста, независимо от его длины. Этот блок называют кодом аутентичности сообщения (КАС), и добавляют к сообщению в качестве аутентификатора. Само расширенное аутентификатором сообщение передается обычно открытым, хотя может быть и зашифрованным, если требуется секретность. Любой владелец секретного ключа и начального вектора может проверить правильность такого аутентификатора. Нужно лишь повторить ту же процедуру шифрования. Оппонент, однако, не может ни осуществить генерацию аутентификатора, который бы воспринимался получателем как подлинный, для добавления его к ложному сообщению, ни отделить аутентификатор от истинного сообщения для использования его с измененным или ложным сообщением. В обоих случаях вероятность того, что ложное сообщение будет интерпретироваться как подлинное, равна вероятности “угадывания” аутентифкатора, то есть 2^-64. Подчеркнем, что предложенный способ делает аутентификатор сложной функцией информации, которую он аутентифицирует. В таком случае подмножество допустимых сообщений состоит из тех пар текст-КАС, которые могут успешно пройти проверку на соответствие аутентификатора тексту с использованием ключа.

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

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

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

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

1. Замена знаков знаками того же алфавита.

2. Потеря знаков или появление дополнительных знаков того же алфавита.

Шифры, не распространяющие искажений типа “замена знаков”.

Будем рассматривать шифры, описываемые алгебраической моделью

S_A = (X, K, Y, E, D),

в которой причем для любых x Î X и k Î K длина y = E_k(x) совпадает с длиной x.

Мерой значительности последствий искажений типа “замена знаков” является метрика на множестве сообщений X = Y. Простейшей является метрика Хэмминга m,определяемая формулой

Так как для эндоморфного шифра каждое правило зашифрования E_k представляет собой биекцию E_k : X ® X, то будем пользоваться подстановочной моделью шифра – S_П = (X, E),в которой множество E ={e_k : k Î K} рассматривается как множество подстановок e : X ® X, e Î E.

Шифр S_П = (X, E)не распространяет искажений типа замены знаков и являются помехостойкими если для любых x, y Î A^l и любого e Î E выполняется неравенство

m(e^-1x, e^-1y) £ m(x, y).

Подстановки e Î E, удовлетворяющие предыдущему равенству, называются изометриями на X.

Теорема А. А. Маркова. Биекция eÎE является изометрией на X тогда и только тогда, когда для подходящих преобразований множества X:

где (j₁,…,j_l) – перестановка чисел 1, 2, …, l; R_i Î S(A) – некоторые фиксированные подстановки множества A, a_i Î A,

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

Шифры, не распространяющие искажений типа “пропуск-вставка знаков”.

Приведем теорему, рассматривающую подстановочную модель шифра.

Теорема. Если S_П = (X, E)– шифр не распространяющий искажений типа пропуск-вставка, то для любого e Î E, либо e = p_L, либо у = p_L· f (при подходящем p Î S(A)), где p_L отображение множества X в себя, определенное для любого a = (a₁,…,a_l) Î X формулой

(p – некоторая подстановка множества A), а f – отображение множества X в себя, меняющее порядок следования букв любого слова на противоположный:

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

Следовательно, все сложные шифры распространяют искажения типа “пропуск-вставка” и в данном случае борьба с такими искажениями криптографическими методами невозможна и, следовательно, необходимо применять иные способы повышения помехоустойчивости (например, введением избыточности – контрольные суммы и пр.).

Практические вопросы повышения надежности.

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

· Криптоанализ опирается на избыточность шифртекста, а сжатие файла перед шифрованием эту избыточность снижает;

· Шифрование занимает много времени, а потому сжатие файла до шифрования ускоряет весь процесс.

Важно запомнить, что сжатие должно выполняться именно до шифрования. (Сжимаемость шифртекста можно использовать как неплохой тест алгоритма шифрования. Если шифртекст можно сжать, значит алгоритм не сишком надежен.)

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

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

Последовательность применения имитовставки и кодирования приведена на рис.12.

Рис. 12. Практическое применение имитовставки в сочетании со сжимающим и помехоустойчивым кодированием.

Контрольные вопросы

1. Назовите основные составляющие алгебраической модели шифра.

2. Для чего применяются вероятностные модели шифров?

3. Для чего применяются модели открытых текстов?

4. Назовите критерии на открытый текст.

5. В чем различие между теоретической и практической криптостойкостью шифров?

6. В чем различие между имитацией и подменой сообщения?

7. Назовите основные способы обеспечения имитостойкости.

8. Какие бывают виды искажений при передаче сообщения?

Алфавитом, на котором действует блочный шифр, является множество двоичных векторов-блоков открытого текста одинаковой длины (64, 128 и т.д.). Так как с увеличением мощности алфавита энтропия на один знак также увеличивается, криптографическая стойкость алгоритма возрастает. Блочные шифры реализуются путем многократного применения к блокам открытого текста некоторых базовых преобразований.

Требования к базовым преобразованиям :

· возможность простой реализации (как аппаратной, так и программной);

· способность давать при небольшом числе итераций аналитически сложные преобразования;

· соответствие критериям рассеивания и перемешивания;

· соотвествие критерию лавинного эффекта.

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

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

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

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

Рассеивающие преобразования – простые преобразования, переставляющие между собой части блоков текста.

Применяемые математические преобразования (операции):

· Перестановки –смена местами битовых значений разрядов подблоков на основе фиксированных подстановок.

· Битовые сдвиги – (X >>Y) сдвиг вправо и (X<<Y) сдвиг влево битовых значений разрядов подблока X (соответствует умножению на 2 и целочисленному делению на 2 ) на величину, определяемую значением подблока Y.

· Циклические битовые сдвиги – (X>>>Y) циклический сдвиг вправо и (X<<<Y) циклический сдвиг влево битовых значений разрядов подблока X (ключа, шифртекста) на величину, определяемую значением подблока Y.

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

· Побитовая инверсия – (~X) инверсия всех битовых регистров блока X.

· Побитовое сложение по модулю 2 – (XÅY) операция XOR над всеми битовыми регистрами подблоков X и Y.

· Сложение по модулю 2ⁿ (n – длина блока в битах) – (XY) двоичное сложение подблоков с отбрасыванием значений старших регистров переноса.

· Умножение по модулю 2^{n 1} – (XY) двоичное умножение с отбрасыванием значений старших регистров переноса, причем нулевое значение подблока принимается равным 0 = 2ⁿ.

· Сложные операции (нелинейние подстановки , логарифмирование и экспоненцирование в конечном поле и пр.).

Сеть Файстеля.

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

Действие, состоящее из однократного вычисления образующей функции и последующего наложения ее результата на другую ветвь с обменом их местами, называется циклом или раундом (англ. round) сети Файстеля. Оптимальное число раундов N – от 8 до 32. Важно то, что увеличение количества раундов значительно увеличивает криптостойстость любого блочного шифра к криптоанализу.

Классическая схема одного раунда сети Файстеля имеет следующую структуру:

Зашифрование:

Расшифрование:

Рис.13. Сеть Файстеля

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

Данная схема является обратимой. Сеть Файстеля обладает тем свойством, что даже если в качестве образующей функции f будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Файстеля не нужно вычислять функцию f^-1.

Благодаря применению финального преобразования (перестановка левой и правой частей блока) сеть Файстеля симметрична. Использование операции XOR, обратимой своим же повтором, и инверсия последнего обмена ветвей делают возможным раскодирование блока той же сетью Файстеля, но с инверсным порядком применения подключей k_i. Заметим, что для обратимости сети Файстеля не имеет значение является ли число раундов четным или нечетным числом. В большинстве реализаций схемы, в которых оба вышеперечисленные условия (операция XOR и уничтожение последнего обмена) сохранены, прямое и обратное преобразования производятся одной и той же процедурой.

В настоящее время чаще применяют модификацию сети Фейстеля для большего числа ветвей. Это в первую очередь связано с тем, что при больших размерах кодируемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно, основные единицы информации обрабатываемые процессорами на сегодняшний день – это байт и двойное машинное слово 32 бита. Поэтому все чаще и чаще в блочных криптоалгоритмах встречается сеть Фейштеля с 4-мя ветвями. Самый простой принцип ее модификации изображен на рисунке а). Для более быстрого перемешивания информации между ветвями (а это основная проблема сети Фейштеля с большим количеством ветвей) применяются две модифицированные схемы, называемые “type-2” и “type-3”. Они изображены на рис.14.

Рис.14. Сеть Файстеля на четыре ветви.

Основные параметры блочных криптоалгоритмов.

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

Таблица 6. Основные параметры распространенных блочных криптоалгоритмов.

Ниже рассмотрим подробнее некоторые современные блочные криптоалгоритмы

Алгоритм DES.

DES представляет собой 64-битовый блочный алгоритм с 56-битовым ключом. Как и ГОСТ он построен на классической сети Файстеля и выполняется в течение 16 раундовсм рис.15, кроме того, он имеет начальную и завершающую перестановки.

При подстановке через S-блок на вход подается 48-битовый блок, разбитый восемь 6-битовых подблока, соответствующие каждый своей S-матрице. Первый и последний биты подблока объединяются в 2-битовое число, определяющее строку S-матрицы, а средние 4 бита объединяются в 4-битовое число, определяющее столбец. На выход подается 4-битовое значение соответствующего элемента S-матрицы.

Рис.15. Раунд шифрования DES

Алгоритм DES являлся коммерческим стандартом шифрования США до 2000 года, когда ему на смену пришел AES. В настоящее время алгоритм применяется в варианте 3DES – каждый блок шифруется трижды на разных ключах. Фактическая длина ключа составила 168 бит.

Блочный шифр TEA

Один из самых простых в реализации, но признанно стойких криптоалгоритмов – TEA (Tiny Encryption Algorithm).

Параметры алгоритма:

Размер блока – 64 бита.

Длина ключа – 128 бит.

В алгоритме использована сеть Фейстеля с двумя ветвями в 32 бита каждая.

Образующая функция F обратима.

Сеть Файстеля несимметрична из-за использования в качестве операции наложения не исключающего “ИЛИ”, а арифметического сложения.

Ниже приведен код криптоалгоритма на языке программирования PASCAL.

type TLong2=array[0.. 1] of longint; TLong2x2=array[0.. 1] of TLong2;const Delta=$9E3779B9;var key:TLong2x2;procedure EnCryptRouting(var data);var y,z,sum:longint; a:byte;beginy:=TLong2(data)[0];z:=TLong2(data)[1];sum:=0;for a:=0 to 31 do begin inc(sum,Delta); inc(y,((z shl 4) key[0,0]) xor (z sum) xor ((z shr 5) key[0,1])); inc(z,((y shl 4) key[1,0]) xor (y sum) xor ((y shr 5) key[1,1])); end;TLong2(data)[0]:=y;TLong2(data)[1]:=zend;

Рис.16. Алгоритм TEA

Отличительной чертой криптоалгоритма TEA является его размер. Простота операций, отсутствие табличных подстановок и оптимизация под 32-разрядную архитектуру процессоров позволяет реализовать его на языке ASSEMBLER в предельно малом объеме кода. Недостатком алгоритма является некоторая медлительность, вызванная необходимостью повторять цикл Фейштеля 32 раза (это необходимо для тщательного “перемешивания данных” из-за отсутствия табличных подстановок).

Схема работы алгоритма приведена на рис. 15.

Данный алгоритм получает на входе 64-битовый блок открытого текста (в процессе шифрования он разбивается на четыре 16-битовых подблока) и 128-битовый ключ, из которого генерируется пятьдесят два 16-битовых подключа шифрования Z₁..Z₅₂ по шесть подключей на каждый из восьми раундов и четыре подключа для выходного преобразования. На выходе генерируется 64-битовый блок шифрованного текста. Алгоритм расшифрования IDEA полностью повторяет структуру алгоритма шифрования: в качестве входных данных использует 64-битовый блок шифрованного текста, и тот-же 128-битовый ключ, из которого генерируются пятьдесят два 16-битовых подключей расшифрования U₁..U₅₂. В результате работы алгоритм расшифрования должен генерировать 64-битовый блок открытого текста.

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

Побитовое исключающее “ИЛИ” (XOR, сумма по модулю 2), обозначаемое символом Å.

Сложение целых чисел по модулю 2¹⁶ (по модулю 65536) с входными и выходными значениями, рассматриваемыми как 16-битовые целые числа без знака. Эта операция обозначается символом .

Умножение целых чисел по модулю 2¹⁶ 1 (по модулю 65537) с входными и выходными значениями, рассматриваемыми как 2-битовые целые числа без знака, за исключением блока состоящего из одних нулей, который интерпретируется как 2¹⁶. Эта операция обозначается символом .

Упрощенно операция реализуется следующим отображением:

Обратите внимание, что (ab mod 2¹⁶) соответствует 16 наименее значимым битам ab, а (ab div 2¹⁶) является простым сдвигом ab вправо на 16 битов. Особенность данной операции в том, что она образует группу (т. е. каждый элемент обратим, включая 0 º 2¹⁶). Эти операции являются несогласованными: 1) Никакие две из этих трех операций не подчиняются дистрибутивному закону. 2) Никакие две из этих трех операций не подчиняются ассоциативному закону.

Вычисление подключей IDEA.

В алгоритме IDEA используется 128-битовый ключ Z, который должен быть как у отправителя, так и у получателя сообщения. Из этого до начала шифрования или расшифрования генерируются пятьдесят два 16-битовых подключа. При этом применяется следующая схема. Первые восемь подключей, обозначенные Z₁..Z₈, образуются непосредственно из ключа: Z₁ равен первым 16 битам ключа, Z₂ – следующим 16 и т.д.

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

Подключи расшифрования U₁..U₅₂ получаются из ключей шифрования по схеме, приведенной в таблице. Где

Z_i^-1 – мультипликативное обращение Z_i по модулю 2¹⁶ 1 (простое число) то есть

Z_i Z_i^-1 = 0000000000000001.

-Z_i – аддитивное обращение Z_i по модулю 2¹⁶ то есть

Z_i(-Z_i) = 0000000000000000.

1. Первых четыре подключa для i-го раунда дешифрования получаются из первых четырех подключей (10 – i)-гo раунда шифрования, если 9-м раундом считать выходное преобразование. Первый и четвертый подключи дешифрования равны мультипликативным обращениям по модулю 2¹⁶ 1 первого и четвертого подключей шифрования соответственно. Для раундов со 2-го по 8-й второй и третий подключи дешифрования равны аддитивным обращениям по модулю 2¹⁶ третьего и второго подключей шифрования соответственно. Для раундов 1 и 9 второй и третий подключи дешифрования равны аддитивным обращениям по модулю 2¹⁶ второго и третьего подключей шифрования соответственно.

2. Для первых восьми раундов два последних подключа i-го раунда дешифрования равны двум последним подключай (9 – i)-го раунда шифрования.

Процесс шифрования предполагает два раунда и выходное преобразование. Один раунд состоит из преобразования входных блоков и субшифрования см рис. 17. Основой субшифрования является основной строительный блок алгоритма – мультипликативно-аддитивная (МА) структура.

Рис.17. Раунд шифрования IDEA

Раунд начинается с преобразования, которое с помощью операции сложения и умножения связывает четыре входных подблока с четырьмя подключами. Это преобразование представлено серым прямоугольником вверху рисунка. Четыре выходных блока этого преобразования связываются операцией XOR с целью получения двух 2-битовых блоков, которые затем подаются на вход структуры МА, представленной на рисунке нижним серым прямоугольником. Кроме того, структура МА получает на входе два подключа, а в результате обработки всех полученных данных на выходе этой структуры генерируется два 2-битовых значения.

Наконец, четыре блока, полученных на выходе первого преобразования связываются с помощью операции XOR с двумя блоками, полученными на выходе структуры МА, и в результате имеется четыре выходных блока (W₁₁..W₁₄) данного раунда см. рис.18

Рис.18. Выходное преобразование IDEA.

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

Подробно рассмотрим работу алгоритма. Выходы первого раунда расшифрования обозначим как (V₁₁..V₁₄). Промежуточные выходы первого раунда зашифрования и расшифрования обозначим соответственно как (I₁₁..I₁₄) и (J₁₁..J₁₄).

При шифровании на выходе функции выходного преобразования имеем

Y₁ = W₈₁Z₄₉, Y₂ = W₈₃Z₅₀, Y₁ = W₈₂Z₅₁, Y₄ = W₈₄Z₅₂.

При расшифровании на выходе первой подстадии первого раунда получаем

J₁₁ = Y₁U₁, J₁₂ = Y₂U₂, J₁₃ = Y₃U₃, J₁₄ = Y₄U₄.

Заменив соответствующие значения эквивалентными получим

J₁₁ = Y₁Z₄₉^-1 = W₈₁ Z₄₉Z₄₉^-1= W₈₁,

J₁₂ = Y₂ -Z₅₀ = W₈₃ Z₅₀ -Z₅₀ = W₈₃,

J₁₃ = Y₃ -Z₅₁ = W₈₂ Z₅₁ -Z₅₁ = W₈₂,

J₁₄ = Y₄Z₅₂^-1 = W₈₄ Z₅₂Z₅₂^-1= W₈₄.

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

W₈₁ = I₈₁ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄),

W₈₂ = I₈₃ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄),

W₈₃ = I₈₂ÅMA_L(I₈₁ÅI₈₃, I₈₂ÅI₈₄),

W₈₄ = I₈₄ÅMA_L(I₈₁ÅI₈₃, I₈₂ÅI₈₄),

Где MA_R(X, Y) обозначает правое выходное значение структуры МА для входных значений X и Y, а MA_L(X, Y) соответственно левое выходное значение. Тогда

V₁₁ = J₁₁ÅMA_R(J₁₁ÅJ₁₃, J₁₂ÅJ₁₄) =

= W₈₁ÅMA_R(W₈₁ÅW₈₂, W₈₃ÅW₈₄) =

= I₈₁ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄) Å MA_R [I₈₁ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄) Å I₈₃ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄),

I₈₂ÅMA_L(I₈₁ÅI₈₃, I₈₂ÅI₈₄) Å I₈₄ÅMA_L(I₈₁ÅI₈₃, I₈₂ÅI₈₄)] =

= I₈₁ÅMA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄) Å MA_R(I₈₁ÅI₈₃, I₈₂ÅI₈₄) =

= I₈₁.

Точно так же получаем V₁₁ = I₈₁, V₁₂ = I₈₃, V₁₃ = I₈₂, V₁₄ = I₈₄. Таким образом, выходные данные второй подстадии процесса расшифрования совпадают с входными значениями предпоследней стадии процесса шифрования за исключением перестановки второго и третьего блоков. Далее можно показать, что соотношение сохраняется для всех последующих подстадий вплоть до V₈₁ = I₁₁, V₈₂ = I₁₃, V₈₃ = I₁₂, V₈₄ = I₁₄. Наконец входное преобразование процесса расшифрования эквивалентно преобразованию первой подстадии шифрования за исключением перестановки 2-3 блоков и результаты зашифрования/расшифрования совпадут.

Алгоритм – победитель конкурса AES, объявленный в 2000 году, был разработан двумя бельгийскими криптографами Дименом (Daemen) и Рийменом (Rijmen). Эта криптосистема не является обобщением шифра Фейстеля. В основе алгоритма – повторяющиеся раунды, каждый из которых состоит из замен, перестановок и прибавления ключа. Кроме того, AES использует сильную математическую структуру: большинство его операций основано на арифметике поля . Однако в отличие от DES зашифрование и расшифрование в этом алгоритме – процедуры разные. Элементы поля хранятся в памяти компьютера в виде 8-битовых векторов (байтов). Например последовательность ‘1000 0011b’ соответствует многочлену X ⁷ X 1 над полем F₂ или шестнадцатиричному числу ‘83h’.

Арифметические операции в поле соответствуют операциям над двоичными многочленами из F₂[X] по модулю неприводимого многочлена

m(X) = X ⁸ X ⁴ X ³ X 1.

В алгоритме AES 32-битовые слова отождествляются с многочленами степени 3 из [X]. Отождествление делается в формате «перевертыш», то есть сташий бит соответствует младшему коэффициенту многочлена. Так, например, слово

a₀||a₁||a₂||a₃

соответствует многочлену

a₃X ³ a₂X ² a₁X a₀.

Арифметика в алгоритме совпадает с арифметическими действиями в кольце многочленов [X] по модулю многочлена M(X) = X ⁴ 1. Заметим, что многочлен M(X) = (X 1)⁴ приводим, и, следовательно, арифметические действия в алгоритме отличны от операций поля, в частности, бывают пары ненулевых элементов, произведение которых равно 0.

AES – настраиваемый блочный алгоритм, который может работать с блоками из 128, 192 или 256 битов. Для каждой комбинации размера блока и размера ключа определено свое количество раундов. Здесь рассматривается самый простой вариант алгоритма, при котором блоки, как и ключ, состоят из 128 битов. В этом случае в алгоритме выполняется 10 раундов.

Алгоритм оперирует с внутренней байтовой матрицей размера 4 на 4, называемой матрицей состояний:

,

которую обычно записывают как вектор 32-битовых слов. Каждое слово в векторе представляет собой столбец матрицы. Подключи также хранятся в виде матрицы 4 на 4:

.

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

SubBytes. В алгоритме есть два типа S-блоков. Один применяется при зашифровании, а другой – при расшифровании. S-блоки имеют прозрачную математическую структуру. Они поочередно обрабатывают строки матрицы состояний s = [s₇, …, s₀], воспринимая их как элементы поля . Их работа состоит из двух шагов.

1. Вычисляется мультипликативный обратный к элементу и записывается как новый байт x = [x₇, …, x₀]. По соглашению, элемент [0, …, 0], не имеющий обратного, остается неизменным.

2. Битовый вектор x при помощи линейного преобразования над полем F₂ переводится в вектор y:

,

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

ShiftRows. Операция осуществляет циклический сдвиг матрицы состояний. Каждая из ее строк сдвигается на свое число позиций. В рассматриваемой версии шифра это преобразование имеет вид:

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

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

Каждый столбец матрицы представляется в виде многочлена степени 3 с коэффициентами из :

a(X) = a₀ a₁X a₂X² a₃X³.

Новый столбец получается умножением многочлена a(X) на фиксированный многочлен

с(x) = ‘02h’ ‘01h’· X ‘01h’· X² ‘03h’· X³.

по модулю многочлена M(X) = X ⁴ 1. Так как умножение на многочлен линейная операция, ее можно представить в виде действия матрицы:

.

Матрица коэффициентов невырождена над , поэтому операция обратима, а обратимое к ней действие реализуется матрицей, обратной к выписанной.

AddRoundKey. Сложение с подключом осуществляется побайтово по модулю 2 для каждого байта матрицы состояний с соответствующим элементом матрицы подключа. обратная операция, очевидно, совпадает с исходной.

Структура раундов.

Шифрование в алгоритме AES запишется в псевдокоде следующим образом:

AddRoundKey(S,K[0]);

For i:= 1 to 9 do Begin SubBytes(S); ShiftRows(S); MixColumns(S); AddRoundKey(S,K[i]) End;

SubBytes(S);

ShiftRows(S);

AddRoundKey(S,K[10])

Блок открытого текста, предназначенный для шифрования, записывается в виде матрицы состояний S. Полученный в результате алгоритма шифротекст представляется той же матрицей. В последнем раунде операция MixColumns не осуществляется.

Процедура расшифрования в псевдокоде:

AddRoundKey(S,K[10]);

Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи.

Рис 19. Регистр сдвига с обратной связью.

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

Простейший тип регистров сдвига – регистр сдвига с линейной обратной связью (РСЛОС или ЛРС). Обратная связь – простая операция XOR над некоторыми битами регистра. Перечень этих битов определяется характеристическим многочленом и называется последовательностью отводов. Иногда такую схему называют конфигурацией Фибоначчи.

Рис.20. РСЛОС конфигурации Фибоначчи.

При программной реализации РСЛОС пользуются модифицированной схемой: для генерации нового значащего бита вместо использования битов последовательности отводов над каждым ее битом выполняется операция XOR с выходом генератора, заменяя старый бит последовательности отводов. Такую модификацию иногда называют конфигурацией Галуа.

Рис.21. РСЛОС конфигурации Галуа.

n-битовый РСЛОС может находиться в одном из 2ⁿ – 1 внутренних состояний. Это значит, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2ⁿ – 1 битов (заполнение нулями совершенно бесполезно). Прохождение всех 2ⁿ – 1 внутренних состояний возможно только при определенных последовательностях отводов. Такие регистры называют РСЛОС с максимальным периодом. Для обеспечения максимального периода РСЛОС необходимо, чтобы его характеристический многочлен был примитивным по модулю 2. Степень многочлена является длиной регистра сдвига. Примитивный многочлен степени n – это такой неприводимый многочлен, который является делителем , но не является делителем x^d 1 для всех d, являющихся делителями 2ⁿ – 1. (При обсуждении многочленов термин простое число заменяется термином неприводимый многочлен). Характеристический многочлен приведенных на рисунках РСЛОС:

x³² x⁷ x⁵ x³ x² x 1

примитивен по модулю 2. Период такого регистра будет максимальным, циклически проходя все 2³² – 1 значений до их повторения. Наиболее часто используются прореженные многочлены, т.е. у которых есть только некоторые коэффициенты. наиболее популярны трехчлены.

Важным параметром генератора на базе РСЛОС, является линейная сложность. Она определяется как длина n самого короткого РСЛОС, который может имитировать выход генератора. Линейная сложность важна, поскольку при помощи простого алгоритма Берленкемпа-Мэсси можно воссоздать такой РСЛОС, проверив всего 2n битов гаммы. С определением нужного РСЛОС поточный шифр фактически взламывается.

Помимо РСЛОС применяются и регистры сдвига с нелинейной обратной связью, обратной связью по переносу и пр.

Ряд генераторов разработан на основе теоретико-числового подхода (генераторы Блюма-Микали, RSA, BBS, сжимающие, аддитивные генераторы и пр.).

Математическое обеспечение синтеза поточных криптографических алгоритмов разработано более полно и подробно по сравнению с блочными криптоалгоритмами. Тем не менее для создания поточных шифров зачастую используют блочные криптоалгоритмы в режимах OFB или CFB.

Пусть P – некоторое поле, e – единица поля P. Обозначим через начальный отрезок произвольной последовательности u элементов поля P. Будем говорить, что многочлен

вырабатывает отрезок , если

,

то есть данный отрезок последовательности является отрезком некоторой линейной рекуррентной последовательности с характеристическим многочленом G(x). Алгоритм Берленкемпа-Месси строит многочлен G(x) наименьшей степени, вырабатывающий отрезок .

Определим функцию умножения последовательности на многочлен. Для произвольного многочлена и последовательности v положим H(x) · v = w, где

Многочлен G(x) вырабатывает l ³ m знаков последовательности u, если выполняется равенство

то есть если первые l – m знаков последовательности v равны нулю, а следующий за ними отличен от нуля.

Для многочлена G(x) Î P[x] степени m и последовательности u введем параметры l_u(G) и k_u(G) = l_u(G) – m Î N È {0, ¥}, где l_u(G) – число знаков последовательности u, вырабатываемых многочленом G(x). Ясно, что k_u(G) – максимальное число первых подряд идущих нулей в последовательности G(x) · u (либо ¥).

Будем индуктивно строить последовательность многочленов G₀(x), G₁(x), … неубывающих степеней 0 = m₀ < m₁ £ m₂ £ … .

Начальные условия: G₀(x) = e, m₀ = 0.

Этап 1. Если

то полагаем

Если G₁(x)·u = 0, то есть если k_u(G₁) = ¥, то G₁(x) – искомый минимальный многочлен ЛРП u. В противном случае строим G₂(x).

Этап t 1. пусть многочлены G₀(x), …, G_t(x) уже построены, и степень многочлена G_j(x) равна m_j, причем 0 = m₀ < m₁ £ m₂ £ … m_t. Пусть выполняются соотношения

Определим число s = s(t) так, чтобы выполнялись условия m_t = m_t – 1 = … = m_s 1 > m_s (такое s найдется, так как m₁ > m₀). Положим

Если G_{t 1}(x)·u = 0, то нужный многочлен построен. В противном случае строим G_{t 2}(x).

Теорема:Если u – линейная рекуррентная последовательность над полем P с минимальным многочленом степени m, то F(x) = G_t(x) для некоторого подходящего значения t £ 2m – 1 – k₀.

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

Основной подход, применяемый при проектировании генератора гаммы на базе РСЛОС прост. Сначала берется один или несколько РСЛОС, обычно с различными длинами и различными характеристическими многочленами. (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у сконструированного генератора будет максимальный период). Ключ является начальным состоянием регистров. Выходной бит представляет собой функцию, желательно нелинейную, некоторых битов РСЛОС.

Если выходной бит является функцией единственного РСЛОС, то генератор называется фильтрующим генератором.

Рис.22. Фильтрующий генератор.

Если выходной бит является функцией нескольких РСЛОС, то генератор называется комбинирующим генератором.

Рис.23. Комбинирующий генератор.

Еще один тип генераторов представляет собой композицию РСЛОС. В данной схеме выход одного из регистров подается на вход другого регистра.

Рис.24. Генератор на основе композиции регистров сдвига..

Кроме перечисленных схем усложнения применяются и другие схемы (с динамическим изменением закона рекурсии с элементами памяти и пр.).

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

Алгоритм DES может использоваться в следующих четырех режимах:

—режим электронной кодовой книги (ЕСВ — Electronic Code Book);

—режим сцепления блоков (СВС — Cipher Block Chaining);

— режим обратной связи по шифртексту (CFB — Cipher Feed Back);

—режим обратной связи по выходу (OFB — Output Feed Back).

Режим электронной кодовой книги (ЕСВ) отвечает обычному использованию DES как блочного шифра, осуществляющего некоторую простую замену блоков открытого текста. В режиме сцепления блоков (СВС) каждый блок C_i, i>1, шифртекста перед очередным зашифрованием складывается по модулю 2 со следующим блоком открытого текста М_i . При этом вектор С₀ полагается равным начальному вектору IV (Initial Vector). Начальный вектор меняется ежедневно и хранится в секрете. Блоки С,,С₂,… вырабатываются по рекуррентной формуле

С_i = DES_k(C_i-1 Å M_i).

Рис.27. Режим CBC.

В режимах CFB и OFB алгоритм DES функционирует по аналогии с “шифром Вернама”, в режиме OFB — как синхронный шифр, в режиме CFB — как шифр с самосинхронизацией.

В режиме CFB вырабатывается блочная “гамма” Z₀,Z₁,…, причем Z₀ полагается равным начальному вектору IV, а при i ≥ 1 блоки гаммы удовлетворяют соотношению Z_i = DES_k(C_i-1). Блоки открытого текста шифруются по правилу C_i = M_iÅ Z_i, i ≥ 1.

Рис.28. Режим CFB.

В режиме OFB вырабатывается блочная “гамма” Z₀,Z₁, …, причем Z₀ полагается равным начальному вектору IV, а при i ≥ 1 блоки гаммы удовлетворяют соотношению Z_i = DES_k(Z_i-1). Блоки открытого текста шифруются по правилу Ci=M_i Å Z_i, i ≥ 1.

Рис.29. Рис.29. Режим OFB.

Кроме перечисленных режимов, DES имеет также “режим т-битовой обратной связи”, 1 ≤ т ≤ 64 . Этот режим оперирует с m-битовыми блоками. Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации IV, “выровненный по правому краю”.

Рис.30. Режим m-битовой обратной связи.

Блоки открытого текста шифруются по правилу С_i= M_iÅ P_i, где P_i— вектор, состоящий из т старших битов блока DES_k(С_i-1). Обновление заполнения регистра сдвига осуществляется путем отбрасывания старших т битов и дописывания справа вектора P_i.

Указанные режимы имеют свои достоинства и недостатки. Основное достоинство режима ЕСВ — простота реализации. Недостаток — в возможности проведения криптоанализа “со словарем “. Дело в том что вследствие большой избыточности в открытом тексте вполне возможны повторения 64-битовых блоков. Это приводит к тому, что одинаковые блоки открытого текста будут представлены идентичными блоками шифртекста, что дает криптоаналитику возможность при наличии достаточно большого числа пар открытого и шифрованного текста восстанавливать с большой вероятностью блоки открытого текста по шифртексту.

В режимах ЕСВ и OFB искажение при передаче одного 64-битового блока шифртекста С, приводит к искажению после расшифрования соответствующего блока M_iоткрытого текста, но не влияет на следующие блоки. Это свойство используется для шифрования информации, предназначенной для передачи по каналам связи с большим числом искажений. Вместе с тем при использовании режима OFB остается открытым вопрос о периоде получаемой выходной гаммы, который в некоторых предположениях может составлять величину порядка 2³².

В режимах СВС и CFB искажение при передаче одного блока шифртекста С_i приводит к искажению на приеме не более двух блоков открытого текста — М_i, M_{j 1}. В то же время изменение блока M_iприводит к тому, что C_iи все последующие блоки шифртекста будут искажены. Это свойство оказывается полезным для целей аутентификации. Такие режимы применяются для выработки кода аутентификации сообщения. Так, в режиме СВС берется вектор инициализации, состоящий из одних нулей. Затем с помощью ключа k вырабатываются блоки C_i,…,C_nшифртекста. Кодом аутентификации сообщения (КАС) служит блок С_п.

Если требуется обеспечить лишь целостность сообщения, отправитель передает блоки М₁,…,М_пвместе с С_п. Тогда противнику, желающему изменить сообщение, нужно соответствующим образом изменить и блок С_п. Возможность этого маловероятна, если только противник не располагает секретным ключом k.

Если же нужно обеспечить шифрование и аутентификацию, то отправитель сначала использует ключ k₁для выработки КАС, затем шифрует последовательность блоков М₁,…,М_п, М_{п 1} = КАС на втором ключе k₂, и получает последовательность блоков С₁,…,С_n,С_{n 1}. Получатель должен сначала расшифровать С₁,…,С_п,С_{п 1}на ключе k₂, а затем проверить (с помощью k ), что М_{п 1}— это КАС для М₀, … , М_n.

Можно поступить и иначе: сначала использовать k для зашифрования М₁,…, Мn, получая С₁,…, С_n, а затем k₂— для получения КАС. Получатель же будет использовать k₂ для проверки КАС, а затем k — для расшифрования C₁, .. ,C_n.

Во всех перечисленных режимах вместо алгоритма DES может быть использован любой алгоритм блочного шифрования, в частности российский стандарт ГОСТ 28147-89.

В российском стандарте также предусмотрено несколько режимов использования: режим простой замены, режим шифрования с обратной связью и режим гаммирования с обратной связью, которые являются аналогами соответственно режимов ЕСВ, СВС и CFB. Для того чтобы избавиться от указанной выше проблемы неопределенности длины периода гаммы в режиме OFB, в российском стандарте введен режим гаммирования, при котором блочный шифр используется в качестве узла усложнения некоторой последовательности гарантированного периода. Для выработки этой последовательности обычно применяются линейные регистры сдвига или счетчики по некоторому модулю.

Рис.31. Режим гаммирования.

Уравнение шифрования имеет вид

C_i = M_i.Å F(γ_i), i = 1,2,…,

где F — преобразование, осуществляемое блочным шифром, γ_i– блоки, сформированные узлом выработки исходной гаммы из начального вектора γ₁, который передается в начале сообщения в открытом или зашифрованном виде.

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

Контрольные вопросы

1. В чем различие между поточными и блочными шифрами?

2. Какие шифры удобнее в программной, а какие в аппаратной реализации?

3. Какие требования предъявляются к шифрующим преобразованиям блочных шифров?

4. В чем суть рассеивающих и перемешивающих преобразований при блочном шифровании?

5. Назовите основные параметры блочных шифров.

6. Какие виды поточных шифров могут быть эффективно реализованы программно?

7. Какие требования предъявляются к генераторам псевдослучайной последовательности?

8. Какие требования предъявляются к функции шифрования поточного шифра?

9. Какие режимы шифрования не распространяют искажений?

4.1. Математические основы асимметричной криптографии.

4.1.1. Свойства операций, определенных на некотором множестве

4.1.2. Функция Эйлера. Поле. Теоремы Эйлера – Лагранжа и Ферма.

4.1.3. Конечные поля.

4.1.4. Основные алгоритмы.

4.1.5. Алгоритмы нахождения НОД и мультипликативного обратного по модулю.

4.1.6. Китайская теорема об остатках.

4.1.7. Символы Лежандра и Якоби. Извлечение корней.

4.2. Примеры современных асимметричных шифров.

4.2.1. Криптосистема RSA.

4.2.2. Взаимосвязь компонентов RSA.

4.2.3. Криптосистема Эль-Гамаля.

4.2.4. Криптосистема Рабина.

4.2.5. Рюкзачные криптосистемы.

4.2.6. Шифрсистема Мак-Элиса.

Математические основы асимметричной криптографии.

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

Системы шифрования с открытым ключом осуществляют блочное шифрование, поэтому открытый текст перед шифрованием разбивается на блоки.

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

Для понимания принципов построения асимметричных криптосистем необходимо повторить некоторые понятия алгебры и алгоритмы теории чисел.

Свойства операций.

Рассмотрим основные свойства арифметических операций определенных на некотором множестве А.

*, – обозначение операций.

Замкнутость:

Ассоциативность:

Наличие нейтрального элемента Q Î A:

Существование обратного элемента Î A:

Коммутативность:

Дистрибутивность операции относительно операции *:

Группы, кольца.

Определение. Группа – множество G с операцией, которая: замкнута, обладает нейтральным элементом, ассоциативна, относительно нее каждый элемент обладает обратным. Группу с коммутативной операцией называют коммутативной или абелевой.

Практически все группы в криптографии – абелевы. Обозначение группы: (G, знак операции).

Мультипликативная группа (G, · ):

Групповая операция – умножение · ;

Нейтральный элемент – единица 1 ;

Обратный элемент – a^-1;

Многократное применение операции – возведение в степень

a⁵ = a · a · a · a · a.

Аддитивная группа (G, ):

Групповая операция – сложение ;

Нейтральный элемент – ноль 0 ;

Обратный элемент – – a;

Многократное применение операции – умножение

5 · a = a a a a a.

Образующая g – такой элемент группы, что любой другой элемент может быть получен путем многократного применения к нему групповой операции. Запись .

В мультипликативной группе:

В аддитивной группе:

Определение. Кольцо – множество R с двумя операциями: сложением и умножением, в котором обе операции замкнуты, ассоциативны, обладают нейтральным элементом, связаны законом дистрибутивности, а сложение коммутативно и для каждого элемента есть обратный по сложению. Обозначение кольца (R, ·, ).

В коммутативном кольце операция умножения дополнительно обладает свойством коммутативности.

Основное кольцо, важное для криптологии – коммутативное кольцо остатков от деления на натуральное число n, большее 1, которое также называют кольцом вычетов по модулю n и обозначают Z_n или Z/nZ.

Одна из центральных задач арифметики остатков – решение сравнения:

a · x º b (mod n)

– Если НОД (a, n) = 1, то существует ровно одно решение, и оно находится с помощью a^-1: так как

a · a^-1 º 1 (mod n),

то, домножив обе части сравнения на a^-1, получим

x º b · a^-1 (mod n).

– Если НОД (a, n) = g ¹ 1 и g | b, то сравнение имеет g решений. Чтобы их найти нужно разделить исходное сравнение на g:

a’ · x’ º b’ (mod n’),

где a’ = a / g, b’ = b / g, n’ = n / g. Если x’ – решение полученного сравнения, то решение исходного сравнения – любое число вида

x = x’ i · n’,

где i = 0, 1, …, g – 1.

– В других случаях решений нет.

Пример:

7 · x º 3 (mod 143) – одно решение,

11 · x º 3 (mod 143) – решений нет,

11 · x º 22 (mod 143) – 11 решений.

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

,

где p_i – различные простые числа, то

Функция Эйлера для любого n > 2 имеет четное значение.

– наибольшее подмножество элементов, образующих группу по умножению # = j(n). (количество элементов мультипликативной группы кольца вычетов по модулю n равно j(n)).

Особый интерес представляют частные случаи:

1. Если p простое, то j(p) = p – 1.

2. Если p и q – простые и p ¹ q, то j(p · q) = (p – 1)(q – 1).

Если p – простое число, то любой элемент в Z_p(или Z/pZ) обладает мультипликативным обратным. Кольца с такими свойствами называются полями.

Определение. Полем называется множество (F, ·, ) с двумя операциями, обладающее свойствами:

– (F, ) – абелева группа с нейтральным элементом 0,

– (F {0}, ·) – абелева группа с нейтральным элементом 1,

– (F, ·, ) удовлетворяет закону дистрибутивности (умножение дистрибутивно относительно сложения).

Поле – коммутативное кольцо, в котором каждый ненулевой элемент обратим. Каждый ненулевой элемент кольца Z_p взаимно прост с p, так как p простое и, следовательно, обратим. Значит Z_p – конечное поле, которое обычно называют полем вычетов по модулю p и обозначают F_p = {0, 1, …, p – 1}. Мультипликативная группа = {1, …, p – 1} поля вычетов содержит все ненулевые элементы F_p.

Теорема Лагранжа. .

Обобщение Эйлера для малой теоремы Ферма. , при НОД(x, n) = 1.

Малая теорема Ферма. .

Конечные поля.

Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосистем, на основе эллиптических кривых.

Рассмотрим множество многочленов от переменной x с коэффициентами из F_p. Это множество обозначается через F_p[x] и образует кольцо относительно естественных операций суммы и умножения многочленов. Особый интерес представляет случай p = 2.

Пример. В кольце F₂[x] выполнены равенства:

Зафиксируем многочлен f(x) и будем рассматривать остальные элементы кольца F_p[x] по модулю f(x). Как и натуральные числа по модулю n, возможные остатки от деления на многочлен f(x), будут образовывать кольцо. Оно обозначается через F_p[x]/f(x)F_p[x] (по аналогии с Z/nZ).

Пример.f(x) = x⁴ 1 и p = 2. Тогда

так как

По аналогии с целыми числами по модулю n, где рассматривалось сравнение

a · x º b (mod n)

можно поставить аналогичный вопрос и для многочленов. Пусть a, b и f – многочлены из F_p[x]. Существование решения уравнения

a · a º b (mod f)

также зависит от НОД (a, f) и также возможны три ситуации. Наиболее интересна ситуация, когда НОД (a, f) = 1.

Многочлен называется неприводимым, если у него нет делителей, отличных от него самого и констант. Неприводимость многочленов – то же самое, что и простота целых чисел. Кольцо F_p[x]/f(x)F_p[x] является конечным полем тогда и только тогда, когда многочлен f(x) неприводим.

Рассмотрим два неприводимых многочлена над полем F₂

и .

Возникают два конечных поля

F₁ = F_p[x]/f₁(x)F_p[x] и F₂ = F_p[x]/f₂(x)F_p[x],

каждое состоит из 2⁷ двоичных многочленов (каждый имеет ровно 7 коэффициентов равных 1 или 0), степень которых не превосходит 6. Сложение в обоих полях выглядит одинаково, поскольку при вычислении суммы складываются коэффициенты многочленов по модулю 2. А вот умножаются элементы этих полей по разному:

Действительно ли различны поля F₁ и F₂ или это только кажущееся различие?

Изоморфны ли поля F₁ и F₂?

Изоморфизм: отображение j: F₁ ® F₂, удовлетворяющее двум требованиям:

Для построения изоморфизма между F₁ и F₂ достаточно показать как выражается корень f₂(x) в виде многочлена от корня f₁(x).

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

Теорема. Существует единственное (с точностью до изоморфизма) конечное поле с числом элементов равным степени простого числа.

Конечное поле из q = p^d элементов обозначается символом F_q или GF(q) (поле Галуа из q элементов).

Любое конечное поле K содержит в себе экземпляр поля целых чисел по некоторому простому модулю p, который называется простым подполем поля K. Число элементов простого подполя называется характеристикой поля и обозначается через char K. В частности char F_p = p. На конечном поле характеристики p можно определить отображение Фробениуса:

Ф: F_q®F_q, Ф(a) = (a^p)

которое является автоморфизмом (изоморфизмом поля с самим собой). Множество элементов из F_q, остающихся неподвижными при действии Ф, совпадает с его простым подполем:

{a Î F_q| a^p = a} = F_p.

Это утверждение – обобщение малой теоремы Ферма на случай любых конечных полей.

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

a = g^x

при некотором целом показателе x.

Пример. В поле из восьми многочленов

.

В нем существует 7 ненулевых элементов, а именно

1, a, a 1, a², a² 1, a² a, a² a 1,

где a – корень многочлена x³ x 1 (искусственно введенный элемент, удовлетворяющий соотношению a³ a 1 = 0, в котором все действия выполняются по модулю 2).

Тогда:

a¹ = a,

a² = a²,

a³ = a 1,

a⁴ = a² a,

a⁵ = a² 1,

a⁶ = a² a 1,

a⁷ = 1

и a – примитивный элемент поля . Целые числа по модулю p также имеют примитивный элемент, так как F_p – конечное поле.

Алгоритм А (Разложение на простые множители путем деления). По данному положительному целому числу N этот алгоритм находит простые множители p₁ ≤ р₂ ≤ … ≤ p_t числа N. В этом методе используется вспомогательная последовательность пробных делителей

d = d₀ < d₁ < d₂ < d₃ < …,

которая включает в себя все простые числа < (и, если это удобно, может содержать числа, не являющиеся простыми). Последовательность чисел d_i должна также содержать по крайней мере одно значение, такое, что d_k > .

А1. [Начальная установка.] Присвоить t ← 0, k ← 0, n ← N. (В ходе выполнения алгоритма переменные t, k, n подчинены следующим условиям: “n = N/p₁…p_t и n не имеет простых множителей, меньших d_k“.)

А2. [n = 1?] Если n = 1, алгоритм заканчивается.

A3. [Разделить.] Присвоить q ← , r ← n mod d_k. (Здесь q и r – соответственно частное и остаток от деления числа n на d_k.)

А4. [Остаток равен нулю?] Если r ≠ 0, то перейти к шагу А6.

А5. [Множитель найден.] Увеличить t на 1 и присвоить p_t ← d_k, n ← q. Возвратиться к шагу А2.

А6. [Частное мало?] Если q > d_k, увеличить k на 1 и возвратиться к шагу A3.

А7. [n — простое число.] Увеличить t на 1, присвоить p_t ← n и завершить выполнение алгоритма.

Рис.32. Алгоритм разложения числа на простые множители.

Пример.

Разложение на простые множители числа N = 25852. Сразу же находим, что N = 2 · 12926; следовательно, р₁ = 2. Далее, 12926 = 2 · 6463, так что р₂ = 1. Но теперь число n = 6463 не делится на числа 2, 3, 5, …, 19; находим, что n = 23 · 281; значит, р₃ — 23. В итоге имеем 281 = 12 · 23 5 и 12 ≤ 23, т. е. р₄ = 281.

Алгоритм Евклида.

Разделить целое число a на число b с остатком – это значит найти такие числа q и r c 0 £ r < |b|, при которых выполняется равенство

a = q · b r.

Разделить многочлен f на многочлен g с остатком – это значит найти такие многочлены q и r c 0 £ deg r < deg g, при которых выполняется равенство

f = q · g r.

Для вычисления НОД(r₀ = a, r₁ = b) производится деление с остатком по следующей схеме:

a = r₀ = q₁r₁ r₂,

b = r₁ = q₂r₂ r₃,

…..

r_m-2 = q_m-1b_m-1 r_m,

r_m-1 = q_mr_m.

Работа алгоритма Евклида основана на том, что отображение сохраняет наибольший общий делитель.

Отображение работает до a = НОД, b = 0.

Пример.

НОД(21, 12) = НОД (21 (mod 12), 12) =

= НОД(12, 9) = НОД (12 (mod 9), 9) =

= НОД(9, 3) = НОД (9 (mod 3), 3) =

= НОД(3, 0) = 3

Работа бинарного алгоритма нахождения НОД основана на следующем ряде отображений, также сохраняющих НОД:

Отображения работают до (a – b) /2 = 0. НОД = b.

Пример.

НОД(21, 12) = НОД (21, 12 / 2) =

= НОД(21, 6) = НОД (21, 6 / 2) =

= НОД(21, 3) = НОД ((21 – 3) / 2, 3) =

= НОД(9, 3) = НОД ((9 – 3) / 2, 3) =

= НОД(3, 3) = НОД ((3 – 3) / 2, 3) =

= НОД(0, 3) = 3

Во всех вышеперечисленных рассуждениях принимается a ³ b.

Алгоритм Евклида.

Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель.

A1. [v = 0?] Если v = 0, то выполнение алгоритма заканчивается, а в качестве результата возвращается число u.

A2. [Взять u mod v.] Присвоить r u mod v, u v, v r и вернуться к шагу A1. (В результате выполняемых на этом шаге операций значение v уменьшается, значение НОД(u, v) остается неизменным.)

Бинарный алгоритм НОД.

Алгоритм B. (Бинарный алгоритм нахождения наибольшего общего делителя). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель. (Использует знаковое представление чисел).

B1. [Найти степень 2.] Присвоить k 0, затем повторно присваивать kk 1, u u / 2, v v / 2 нуль или более раз до тех пор, пока одно или оба числа u и v станут нечетными.

B2. [Начальная установка.] (Исходные значения чисел u и v уже разделены на 2^k, и по крайней мере одно из текущих значений нечетно.) Если нечетно u, то присвоить t – v и перейти к шагу B4. В противном случае присвоить tu.

B3. [Уменьшить t наполовину.] (Здесь t четно и не нуль.) Присвоить tt / 2.

B4. [t четно?] Если t четно, то вернуться к шагу B3.

В5. [Установить max(u, v) заново.] Если t > 0, то присвоить u t, в противном случае присвоить v – t. (Большее из чисел u и v заменяется на |t| за исключением, возможно, первого выполнения этого шага.)

B6. [Вычесть.] Присвоить t u – v. Если t ¹ 0, то вернуться к шагу B3. В противном случае алгоритм останавливает выполнение, а на выходе будет u · 2^k.

Рис.33. Бинарный алгоритм НОД.

Расширенный алгоритм Евклида.

Алгоритм X. (Обобщенный алгоритм Евклида). Для заданных целых чисел u и v этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что uu₁ vu₂ = u₃ = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃); действия производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

ut₁ vt₂ = t₃ uu₁ vu₂ = u₃ uv₁ vv₂ = v₃.

X1. [Начальная установка.] Присвоить (u₁, u₂, u₃) (1, 0, u), (v₁, v₂, v₃) (0, 1, v).

X2. [v3 = 0?] Если v3 = 0, то выполнение алгоритма заканчивается.

X3. [Разделить и вычесть.] Присвоить , затем присвоить

(t₁, t₂, t₃) (u₁, u₂, u₃) – (v₁, v₂, v₃) · q,

(u₁, u₂, u₃) (v₁, v₂, v₃),

(v₁, v₂, v₃) (t₁, t₂, t₃).

Возвратиться к шагу X2.

Расширенный бинарный алгоритм НОД.

Алгоритм Y. Модификация алгоритма X с использованием принципов алгоритма B. Для заданных целых чисел u и v этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что uu₁ vu₂ = u₃ = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃); в течение всего процесса вычисления так же, как и в X выполняются соотношения

ut₁ vt₂ = t₃ uu₁ vu₂ = u₃ uv₁ vv₂ = v₃.

(Использует знаковое представление чисел).

Y1. [Найти степень 2.] То же, что в шаге B1.

Y2. [Начальная установка.] Присвоить (u₁, u₂, u₃) (1, 0, u), (v₁, v₂, v₃) (v, 1 – u, v). Если число u нечетно, присвоить (t₁, t₂, t₃) (0, –1, –v) и прейти к шагу Y4. В противном случае присвоить (t₁, t₂, t₃) (1, 0, u).

Y3. [Выполнить половинное деление t₃.] Если t₁ и t₂ четны, присвоить (t₁, t₂, t₃) (t₁, t₂, t₃)/2; иначе присвоить (t₁, t₂, t₃) (t₁ v, t₂ – u, t₃)/2. (В последнем случае t1 v и t2 – u будут оба четными.)

Y4. [t₃ четно?] Если t₃ четно, вернуться к шагу Y3.

Y5. [Переустановить max(u₃ v₃).] Если t₃ положительно, присвоить (u₁, u₂, u₃) (t₁, t₂, t₃); иначе присвоить (v₁, v₂, v₃) (v – t₁, – u – t₂, – t₃).

Y6. [Вычесть.] Присвоить (t₁, t₂, t₃) (u₁, u₂, u₃) – (v₁, v₂, v₃). Затем, если t₁ £ 0, присвоить (t₁, t₂) (t₁ v –, t₂ – u). Если t3 ¹ 0, вернуться к шагу Y3. В противном случае закончить выполнение алгоритма с результатом, равным (u₁, u₂, u₃ · 2^k).

Пусть p – простое число, большее 2. Рассмотрим отображение

,

сопоставляющее каждому элементу поля его квадрат. На множестве ненулевых элементов поля F_p это отображение в точности «два-в-один», то есть если из ненулевого элемента x Î F_p можно извлечь квадратный корень, то таких корней у него ровно 2 и, кроме того, ровно половина элементов из являются полными квадратами. Полные квадраты в называются квадратичными вычетами по модулю p. Множество всех квадратичных вычетов по модулю p является подгруппой порядка (p – 1)/2 в мультипликативной группе . Элементы мультипликативной группы из которых нельзя извлечь квадратный корень, называются квадратичными невычетами.

Для выявления полных квадратов по модулю p вводится символ Лежандра

Он равен 0, если a делится на p, 1, если a – квадратичный вычет по модулю p, и – 1, если a – квадратичный невычет.

Символ Лежандра легко вычисляется по формуле

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

Иначе говоря

При вычислении символа Лежандра большую помощь оказывают следующие дополнительные формулы:

Пример. С использованием разложения на множители вычислим символ Лежандра.

Извлечение квадратного корня из квадратичного вычета a по модулю p при помощи алгоритма Шенкса.

1. Выбрать наугад такое n, что

2. Пусть e, q – целые числа с нечетным q, удовлетворяющие соотношению p – 1 = 2^eq.

3. Положим y = n^q (mod p), r = e, x = a^{(q – 1)/2} (mod p).

4. Положим b = ax² (mod p), x = ax (mod p).

5. Пока b ¹ 1 (mod p) делать:

· найти наименьшее число m, такое, что

· положить

· положить

6. Вывести x.

Если p = 3 (mod 4), то для извлечения квадратного корня из a можно использовать формулу

формула дает правильный ответ потому, что

.

Символ Лежандра определен только в случае простого знаменателя. Если же знаменатель составной, то вводится символ Якоби, обобщающий символ Лежандра.

Пусть n – нечетное число, большее 2 и

.

Символ Якоби определяется через символы Лежандра простых делителей числа n следующим образом

Символ Якоби можно вычислять так же, как и символ Лежандра, опираясь на тождество, выведенное из закона квадратичной взаимности:

где a = 2^ea₁ и a₁ нечетно. Полезно помнить еще несколько формул, справедливых при нечетном n:

Это дает быстрый алгоритм вычисления символа Якоби и, соответственно, символа Лежандра, как его частный случай, без разложения на множители. Единственное, что нужно сделать – выделить максимальную степень двойки.

Пример.

Символ Лежандра сообщает нам, является ли a полным квадратом по модулю простого числа p. Символ Якоби ничего не утверждает о возможности извлечения квадратного корня из a по модулю составного числа n. Если a в действительности квадрат по модулю n, то символ Якоби будет равен 1. Однако из равенства нельзя сделать вывод о том, что a – полный квадрат. Не смотря на благоприятное равенство, квадратный корень из a может не извлекаться.

Извлечение корня из числа по модулю составного n = p · q в предположении, что разложение n на простые множители известно и a – полный квадрат по модулю n, то есть

Сначала извлекается корень из a по модулю p и обозначается через s_p (таких корней два, как будет показано позже). Затем извлекается квадратный корень из a по модулю q и обозначается s_q (таких корней также два). Наконец, для вычисления искомого корня применяем китайскую теорему об остатках к системе

Пример. Вычислим корень из a = 217 по модулю n = 221 = 13 · 17.

Квадратные корни из a по модулям 13 и 17 соответственно равны s₁₃ = 3 и s₁₇ = 8. Опираясь на китайскую теорему об остатках, получаем s = 42. Проверим правильность данного решения: s² = 42² ≡ 217 (mod 221).

Существуют еще три квадратных корня из a = 217 по модулю n = 221, поскольку n имеет два простых делителя. Для их отыскания применим КТО к трем системам с коэффициентами:

s₁₃ = 10, s₁₇ = 8;

s₁₃ = 3, s₁₇ = 9;

s₁₃ = 10, s₁₇ = 9

и получить полный ответ: 42, 94, 127, 179.

Криптосистема RSA.

Система построена на следующих функциях:

Односторонняя функция – умножение двух больших простых чисел:

N = p · q.

Обратная задача – задача факторизации, является сложной.

Односторонняя функция с секретом – потенцирование (возведение в степень) по модулю составного N = p · q сфиксированной степенью E:

C = m^E mod N.

Обратная задача – задача извлечения корня степени E по модулю N:

является сложной, если неизвестно разложение N на множители (секрет) и является простой при известном разложении N.

В дальнейшем секретные элементы криптосистем обозначаются строчными (p, q, m и пр.) открытые прописными (N, C, E и пр.) латинскими буквами.

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

N = p · q,

которое называют модулем алгоритма. Кроме того, выбирается шифрующая экспонента E, удовлетворяющая условию

НОД (E, (p – 1), (q – 1)) = 1.

Как правило E берут равным 3, 17 или 65537. Пара, доступная всем желающим, – это (N, E). Для выбора секретного ключа применяют расширенный алгоритм Евклида к паре чисел E и

(p – 1)(q – 1), получая при этом расшифровывающую экспоненту d. Найденная экспонента удовлетворяет соотношению

E · d = 1 (mod (p – 1)(q – 1)) = 1.

Секретным ключом является тройка (d, p, q). Фактически, можно было бы выбросить простые делители p и q из ключа и помнить лишь о d и всем числе N. Но, как будет рассмотрено позднее, это снизит скорость алгоритма.

Допустим теперь пользователь B намерен зашифровать сообщение, адресованное A. Он сверяется с открытым ключом и представляет сообщение в виде числа m, строго меньшего модуля N алгоритма. Шифртекст C получается из m по следующему правилу:

C = m^E (mod N).

A, получив шифрограмму, расшифровывает ее, возводя число C в степень d:

m = C^d (mod N).

Равенство имеет место в связи с тем, что порядок группы

#(Z/NZ)^* = φ(N) = (p – 1)(q – 1).

Потому по теореме Лагранжа (Эйлера-Ферма),

x^{(p – 1)(q – 1)} = 1 (mod N)

для любого числа x Î (Z/NZ)^*. Поскольку E и d взаимно обратны по модулю (p – 1)(q – 1), при некотором целом числе s получается равенство

Ed – s(p – 1)(q – 1) = 1.

Следовательно,

C^d = (m^E)^d = m^Ed = m^{1 s(p – 1)(q – 1)} = m · m ^{s(p – 1)(q – 1)} = m (mod N).

Пример. Пусть p = 7 и q = 11. Тогда N = 77, а (p – 1)(q – 1) = 6 · 10 = 60. В качестве открытой шифрующей экспоненты возьмем число E = 37, поскольку НОД(37, 60) = 1. Применяя расширенный алгоритм Евклида, найдем d = 13, так как

37 · 13 = 481 = 1 (mod 60).

Для зашифрования сообщения численное представление которого имеет вид m = 2:

C = m^E (mod N) = 237 (mod 77) = 51.

Расшифрование происходит аналогично:

m = C^d (mod N) = 5113 (mod 77) = 2.

Задача RSA: Даны числа C и E, последнее из которых удовлетворяет соотношению:

НОД(E, (p – 1)(q – 1)) = 1.

Требуется найти такое число m, что

m^E = C (mod N).

Лемма. Задача RSA не сложнее проблемы факторизации.

Доказательство. Применяя алгоритм факторизации, разложим число N на простые множители, вычислим значение функции Эйлера Ф = j(N) и найдем

D = 1/E (mod Ф).

Теперь, зная число D, легко восстановить m, поскольку

C^D = m^ED = m^{1 (mod Ф)} = m (mod N).

Отсюда следует, что при известных p и q легко находятся d и m.

Самые большие числа, которые к настоящему времени удается разложить на множители за разумное время, имеют 500 двоичных знаков. В связи с этим, для обеспечения стойкости систем среднего срока действия, рекомендуют брать модули шифрования порядка 1024 бит. Для систем большого срока действия следует выбирать модули, состоящие из 2048 бит.

Секретная экспонента и проблема факторизации:

Лемма. Если известна секретная экспонента d алгоритма RSA, соответствующая открытому ключу (N, E), то число N можно эффективно разложить на множители.

Доказательство. При некотором целом s имеет место равенство

Ed – s(p – 1)(q – 1) = 1.

Возьмем произвольное целое число X ¹ 0. Тогда

X^{Ed – 1}= 1(mod N).

Вычисляем квадратный корень Y₁ по модулю N:

что можно сделать, поскольку Ed – 1 известно и четно. Приходим к тождеству

которое можно использовать для определения делителей числа N с помощью вычисления НОД(Y₁ – 1, N). Однако это будет работать только если Y₁ ¹ ±1 (mod N).

Предположим, что нам не повезло и Y₁ = ±1 (mod N). Если Y₁ = –1 (mod N), вернемся к началу и выберем другое число X. Если Y₁ = 1 (mod N), то можно взять еще один квадратный корень

Опять получаем

откуда НОД(Y₂ – 1, N) – делитель числа N. К сожалению, здесь тоже может оказаться, что Y₂ = ±1 (mod N). Тогда придется повторить все снова.

Алгоритм необходимо повторять до тех пор, пока мы не разложим N на множители и не придем к числу (ED – 1)/2^t, которое уже не будет делиться на 2. В последнем случае придется вернуться к началу алгоритма, выбрать новое случайное значение X и все повторить.

Отсюда следует, что при известном d легко найти p и q.

Алгоритм, приведенный в доказательстве, – типичный пример алгоритма Лас-Вегаса, вероятностного по своей природе, которая проявляется в процессе работы. Но если уж ответ отыщется, то он будет обязательно верным.

Пример. Входные данные задачи RSA:

N = 1441499, E = 17 и d = 507905.

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

T₁ = (Ed – 1)/2 = 4317192,

X = 2.

Для вычисления Y₁, сделаем преобразования :

Поскольку Y1 оказался равным 1, нам нужно взять

T₂ = T₁/2 = (Ed – 1)/4 = 2158596 и .

Теперь

Снова нужно повторять предыдущие шаги, что приведет нас к

T₃ = (Ed – 1)/8 = 1079298

и

Отсюда

и мы можем найти простой делитель числа N, вычислив

НОД(Y₃ – 1, N) = 1423.

Значение функции Эйлера j(N) и проблема факторизации:

Лемма. Значение Ф = j(N) позволяет эффективно разложить число N на множители.

Доказательство. Имеем

Ф = (p – 1)(q – 1) = N – (p q) 1.

Следовательно, положив S = N 1 – Ф, мы получим

S = p q.

Нам нужно определить числа p или q, опираясь на их сумму S и произведение N. Рассмотрим многочлен

f(X) = (X – p)(X – q) = X² – SX N.

Теперь можно найти как p, так и q, решая квадратное уравнение f(X) = 0 стандартным образом:

Отсюда следует, что при известном j(N) легко найти p и q.

Пример. Открытый модуль N = 18923 криптосистемы RSA. Известно Ф = j(N) = 18648. Вычисляем

S = p q = N 1 – Ф = 276.

Соответствующий многочлен имеет вид:

f(X) = X² – SX N = X² – 276X 18923,

а его корни – p = 149, q = 127.

Разделенный модуль: Поскольку арифметика остатков – дорогое удовольствие с точки зрения компьютера, весьма заманчиво разработать систему шифрования, в которой пользователи разделяют общий модуль N, но применяют различные открытые и закрытые экспоненты (E_i, d_i).

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

Предположим, что нападающим является один из законных клиентов криптосистемы, скажем пользователь номер 1. Он может найти значение секретной экспоненты пользователя 2 – d₂. Сначала он вычисляет p и q по известному ему d₁. Затем злоумышленник находит

j(N) = (p – 1)(q – 1) и, наконец, при помощи расширенного алгоритма Евклида раскрывает значение d₂ по формуле

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

(N, E₁) и (N, E₂).

Противник, нападающий извне, видит зашифрованные сообщения С₁ и C₂, где

Он может вычислить

и восстановить сообщение m по следующей схеме:

Пример.N = N₁ = N₂ = 18923, E₁ = 11 и E₂ = 5.

Предположим, что перехвачены шифртексты

C₁ = 1514 и C₂ = 8189,

соответствующие одному открытому тексту m. Тогда противник вычисляет T₁ = 1 и T₂ = 2, после чего раскрывает исходную информацию:

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

Малые шифрующие экспоненты:

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

N₁, N₂ и N₃

и одинаковой шифрующей экспонентой E = 3. Пусть некто посылает им одно сообщение m, зашифрованное тремя разными открытыми ключами. Нападающий видит три криптограммы:

C₁ = m³ (mod N₁),

C₂ = m³ (mod N₂),

C₃ = m³ (mod N₃)

и с помощью китайской теоремы об остатках находит решение системы

{X = C_i (mod N_i)| i = 1, 2, 3}

в виде

X = m³ (mod N₁N₂N₃).

Но поскольку m³ < N₁N₂N₃, целые числа X и m³ должны совпадать. Поэтому, вычисляя обычный кубический корень из X, нападающий раскрывает сообщение m.

Пример.

N₁ = 323, N₂ = 299, N₃ = 341

и перехваченные сообщения

C₁ = 50, C₂ = 299, C₃ = 1,

Чтобы восстановить исходное сообщение m, находим решение системы

X = 300763 (mod N₁N₂N₃),

после чего извлекаем обычный кубический корень

m = X^1/3 = 67.

Вывод. При использовании малой шифрующей экспоненты E противник может восстановить циркулярное сообщение m для E пользователей.

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

При практической реализации RSA необходимо решить следующие задачи:

1. Генерация больших простых чисел p и q с проверкой выполнения соответствующих требований к ним.

2. Выбор экспонент e и d с соблюдением соответствующих требований.

3. Реализация операции вычисления x^y(mod n).

Генерация большого простого числа:

1) Сгенерировать случайное n-битовое число p.

2) Установить старший и младший бит равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший – обеспечивает его нечетность).

3) Убедиться, что p не делится на малые простые числа: 3, 5, 7, 11 и т.д. Во многих практических реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее надежна проверка делимости на все простые числа, меньшие 2000. Эти проверки можно выполнить на основе массива этих простых чисел.

4) Выполнить тест простоты Рабина-Миллера для некоторого случайного числа a. Если p проходит тест, сгенерировать другое случайное число a и повторить тест. Для ускорения проверки можно выбирать относительно небольшие значения a. Выполнить тест минимум пять раз. Если p не проходит один из тестов, то перейти к шагу 1).

Другой путь – не генерировать случайное число p в каждом тесте, а последовательно перебирать все нечетные числа, начиная со случайно выбранного числа, пока не найдется простое число.

Тест Рабина-Миллера:

Выбрать для тестирования число p. Вычислить b – число делений p – 1 на 2 (то есть 2^b – это наибольшая степень числа 2, на которую делится p – 1). Затем вычислить m, такое, что p = 1 2^b · m.

1) Выбрать случайное число a, меньшее p.

2) Установить j = 0 и z = a^m mod p.

3) Если z = 1 или если z = p – 1, то p проходит тест и может быть простым числом.

4) Если j > 0 и z = 1, то p не относится к простым числам.

5) Установить j = j 1. Если j < b и z ¹ (p – 1), установить z = z² mod p и вернуться к шагу 4). Если z = p – 1, то p проходит тестирование и может быть простым числом.

6) Если j = b и z ¹ (p – 1), то p не относится к простым числам.

Выбор экспонент e и d:

1) Так как единственное требование к e – отсутствие общих множителей с числом φ(n) = (p – 1) · (q – 1), то логично выбирать небольшое e легко разложимое на простые множители и осуществлять проверку делением φ(n) на множители e. Либо выбирать простое e. Неплохо также выбирать e с минимальным количеством единиц в двоичном представлении, что ускорит операцию возведения в степень, реализованную следующим алгоритмом.

2) Так как очевидно, что d = e^-1(mod p), то d находим при помощи расширенного алгоритма Евклида.

Алгоритм вычисления x^y(mod n).

1) Представим y в двоичной системе счисления y = y₀2^r … y_r-12 y_r, где y_i, цифры в двоичном представлении равные 0 или 1, y₀ = 1.

2) Положим x₀ = x и затем для i = 1,…, r вычислим

.

3) x_r есть искомый вычет x^y(mod n).

Односторонняя функция – возведение в степень с фиксированным модулем P и основанием G.

H = G^x (mod P)

Обратная задача – задача дискретного логарифмирования

x = ind _G,P H

является сложной.

Здесь опишем шифрование по Эль-Гамалю, использующее конечные поля. Существует и аналогичная система на эллиптических кривых.

В отличие от RSA, в алоритме Эль-Гамаля существуют некоторые открытые параметры, которые могут быть использованы большим числом пользователей. Они называются параметрами домена и выглядят следующим образом:

– P – «большое простое число», то есть число, насчитывающее около 1024 бит, такое, что P – 1 делится на другое, «среднее простое число» Q, лежащее неподалеку от 2¹⁶⁰.

– G – элемент мультипликативной группы поля , порядок которой, как мы знаем делится на Q, причем

G^{(P – 1)/Q} (mod P) ≠ 1.

Все параметры домена, то есть P, Q и G, выбираются таким образом, чтобы элемент G^{(P – 1)/Q} был образующей абелевой группы A порядка Q. Информация об этой группе открыта и используется большим числом пользователей.

После выбора параметров домена определяют открытый и закрытый ключи. Закрытым ключом может априори быть любое натуральное число x, а открытый ключ получается по следующей формуле:

H = G^x (mod P).

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

Сообщение в этой ситеме представляется ненулевым элементом поля . Для его шифрования поступают следующим образом:

– генерируют случайный эфемерный ключ k,

– вычисляют C₁ = G^k,

– находят C₂ = m · H^k,

– выдают получившийся шифртекст в виде пары С = (С₁, С₂).

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

Чтобы расшифровать пару данных С = (С₁, С₂), производят следующие преобразования:

Пример.Q = 101, P = 809 и G = 3.

Легко проверить, что Q действительно делит число P – 1, а порядок элемента G в группе делится на Q. Порядок элемента G равен 808, поскольку

3⁸⁰⁸ = 1 (mod P),

и ни при каких меньших степенях такого равенства не получается.

В качестве пары открытого и закрытого ключа выберем

x = 68 и H = G^x = 3⁶⁸ = 65 (mod P).

Допустим, нам нужно зашифровать сообщение, численное представление которого равно

m = 100. Поступаем следующим образом.

– Генерируем случайный эфемерный ключ k = 89.

– Находим С₁ = G^k = 3⁸⁹ = 345 (mod P).

– Получаем С₂ = m · H^k = 100 · 65⁸⁹ = 517 (mod P).

– Отправляем шифртекст C = (345, 517).

Адресат сможет восстановить текст, делая также вычисления:

Последнее равенство получается чуть более сложно, чем в вещественных числах: сначала число 345 возводится в степень 68 по модулю 809, вычисляется мультипликативный обратный к результату по этому же модулю, а затем найденный обратный умножается на 517.