Аффинная система подстановок Цезаря

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

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

Определим в такой системе преобразование Еa,b: Zm > Zm:

Еa,b(x)= ax+b mod m,

где в качестве ключа k = (a, b) используется пара целых чисел, удовлетворяющих условиям 0 ??a,b < m, и НОД(а,m)=1.

В данном преобразовании буква, соответствующая числу x в открытом тексте, заменяется на букву шифртекста, соответствующую числовому значению y =(ax +b) mod m (например m=26 в латинском алфавите).

Следует заметить, что преобразование Еa,b(x) является взаимно однозначным отображением на множестве Zm только в том случае, если НОД(а,m)=1, т.е. а и m должны быть взаимно простыми числами.

Это условие взаимной простоты необходимо для обеспечения инъективности отображения Еa,b(x) = ax+b mod m. Если оно не выполняется, возможна ситуация, когда две разные буквы отображаются в одну (возникает неоднозначность расшифрования), а некоторые буквы отсутствуют в шифртексте, так как никакие буквы в них не отображаются.

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

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

Криптосистема Хилла и её частный случай шифр Плэйфеpа

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

Алгебраический метод, обобщающий аффинную подстановку Цезаря для шифрования n-грамм, был сформулирован Лестером С.Хиллом.

Шифрование ведется путем выполнения умножения вектора на матрицу. Матрица является ключом шифрования. Открытый текст разбивается на n-граммы - блоки длиной n, равной размерности матрицы и каждая n-грамма х = (х0, х1, х2, … , хn-1) рассматривается как вектор.

Ключевая матрица Т размером пЧп вида Т={ti,j}, i,j = 0,1, … ,n-1 задает отображение, являющееся линейным преобразованием:

Т: Zm,n > Zm,n, Т: х > у; у=Тх,

где .

Для расшифрования шифртекста необходимо выполнить обратное преобразование:

х = Т-1 у.

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

Т Т-1 = Т-1 Т = I, где I - единичная матрица.

Доказано, что для этого необходимо, чтобы определитель матрицы det Т, не делился на любое простое р, которое делит m.

Шифры гаммирования

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

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

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

Следует отметить, что при блочном шифровании открытые данные разбивают на блоки Т0(i) одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков гi аналогичной длины.

Уравнение зашифрования можно записать в виде

ci = гi ? mi , i=1,…,M,

где ci - i-ый блок шифртекста; гi - i-ый блок гаммы шифра; mi - i-ый блок открытого текста; М - количество блоков открытого текста.

Процесс дешифрования сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение расшифрования имеет вид

mi = гi? ? ci, i=1,…,M.

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

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

гi+1 = (агi + b) mod m,

где а и b - константы; г0 - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений а и b. Необходимо выбирать числа a и b такие, чтобы период был максимальным. Как показано Д. Кнутом, это возможно тогда и только тогда, когда b - нечетное и взаимно простое с m, и величина а mod 4 = 1. По другим рекомендациям b - взаимно простое с m, и а нечетное.

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

Ri = ( Si + G ) mod (k -1),

где Ri, Si, G -- символы соответственно зашифрованного, исходного текста и гаммы.

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

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

Таблица 8 - Пример шифрования гаммированием

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

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

Страницы: 1, 2, 3, 4, 5