Для расшифрования шифртекста необходимо выполнить обратное преобразование:
х = Т-1 у.
Для того, чтобы линейное преобразование Т, заданное своей матрицей, могло быть криптографическим преобразованием необходимо чтобы оно было обратимым (или невырожденным), то есть должна существовать обратная матрица Т-1: такая, что:
Т Т-1 = Т-1Т = I, где I - единичная матрица.
Доказано, что для этого необходимо, чтобы определитель матрицы det Т, не делился на любое простое р , которое делит m.
2.6. Шифры гаммирования.
Гамма шифра - это псевдослучайная последовательность, выработанная по заданному алгоритму для шифрования открытых данных и дешифрования зашифрованных данных. Под гаммированием понимают процесс наложения по определенному закону гаммы шифра на открытые данные, он может выполняться как в режиме блочного, так и потоковового шифрования. Он является типичным и наиболее простым примером реализации абсолютно стойкого шифра (при использовании бесконечного ключа п=¥).
Процесс шифрования заключается в генерации гаммы шифра и наложении полученной гаммы на исходный открытый текст обратимым образом, например с использованием операции сложения по модулю 2.
Следует отметить, что при блочном шифровании открытые данные разбивают на блоки Т0(i) одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков γi аналогичной длины.
Уравнение зашифрования можно записать в виде
ci = γi Å mi , i=1,…,M,
где ci - i-ый блок шифртекста; γi - i-ый блок гаммы шифра; mi - i-ый блок открытого текста; М - количество блоков открытого текста.
Процесс дешифрования сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение расшифрования имеет вид
mi = γi Å ci, i=1,…,M,
Полученный зашифрованный текст является достаточно трудным для раскрытия в том случае, если гамма шифра не содержит повторяющихся битовых последовательностей. Кpиптостойкость определяется размером ключа и методом генерации гаммы.
Чтобы получить линейные последовательности элементов гаммы, длина которых превышает размер шифруемых данных, используются датчики псевдослучайных чисел (ПСЧ). Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайных чисел γi, описываемые соотношением
γi+1 = (аγi + b) mod m,
где а и b - константы, γ0 - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.
Такой датчик генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений а и b. Необходимо выбирать числа a и b такие, чтобы период был максимальным. Как показано Д. Кнутом, это возможно тогда и только тогда, когда b - нечетное и взаимно простое с m, и величина а mod 4 = 1. По другим рекомендациям b - взаимно простое с m, и а нечетное.
Шифр Вернама является частным случаем шифрования гаммированием для двоичного алфавита (при значении модуля m=2).
Конкретная версия этого шифра, предложенная в 1926 году сотрудником фирмы AT&T Вернамом, использует двоичное представление символов исходного текста. Каждая буква исходного текста в алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием телеграфного кода Бодо в пятибитовый символ. То есть алфавит криптосистемы представляет собой множество Z32 всех пятибитовых последовательностей.
Ключ k=(k0 ,k1 ,...,kк-1), где "ki Î Z32 записывался на бумажной ленте. При шифровании ключ добавлялся к исходному тексту суммированием по модулю 2.
В общем случае система шифрования Вернама осуществляет побитовое сложение п -битового открытого текста и п-битового ключа:
yi = xiÅ ki, i=1,…,n
Здесь х1 х2 ... xп - открытый текст, k1 k2 ... kп - ключ, y1 y2 ... yп - шифрованный текст.
Расшифрование состоит в сложении по модулю 2 символов у шифртекста с той же последовательностью ключей k:
y Å k=x Å k Å k = x.
Метод Вернама использует длинную случайную ключевую последовательность и при его реализации возникают проблемы, связанные с необходимостью передачи ключа.
2.7. Анализ стойкости криптосистем
Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Понятие стойкости шифра является центральным для криптографии. Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Но абсолютно стойкий шифр на практике, как правило, неприменим, поэтому для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты, то есть противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр. Вопрос только в том, хватит ли у него сил, средств и времени для разработки и реализации соответствующих алгоритмов.
В этой ситуации желательно, получить теоретическую оценку стойкости, то есть, например, доказать, что никакой противник не сможет вскрыть выбранный шифр, скажем, за 10. К сожалению, математическая теория еще не дает нужных теорем — они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.
Поэтому у пользователя остается единственный путь — получение практических оценок стойкости. Этот путь состоит в том, чтобы определить от какого противника мы собираемся защищать информацию, а также какие силы и средства он сможет применить для его вскрытия. Затем, мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра, а наилучший из этих алгоритмов использовать для практической оценки стойкости шифра. В общем случае все оценки стойкости системы должны вестись в предположении, что криптоаналитику известен алгоритм шифрования, но он незнает ключа на котором зашифровано конкретное сообщение. Противник также может знать некоторые характеристики открытых текстов, например, общую тематику сообщений, некоторые стандарты, форматы и т. д.
Итак, стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру иногда называют проверкой стойкости. Имеется несколько показателей криптостойкости, среди которых основные:
- количество всех возможных ключей;
- среднее время, необходимое для кpиптоанализа.
В данной работе мы будем защищатся от пассивной атаки с известной шифрограммой, когда противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов. Задача криптоаналитика заключается с том, чтобы раскрыть исходные тексты и вычислить ключ.
Для этого рекомендуется использовать один из двух простейших методов вскрытия шифра
1. Статистическую атаку.
2. Силовую атаку.
Рассмотрим в чем они состоят.
Криптоаналитическая статистическая атака
Криптоаналитическая статистическая атака применима только против систем одноалфавитной замены, главным недостатком которых является возможность взлома шифртекста на основе анализа частот появления букв. Такая атака начинается с подсчета частот появления символов:
- определяется число появлений каждой буквы в шифртексте.
- полученное распределение частот букв в шифртексте сравнивается с распределением частот букв в алфавите исходных сообщений, например в английском.
- буква с наивысшей частотой появления в шифртексте заменяется на букву с наивысшей частотой появления в английском языке и т.д.
По закону больших чисел вероятность успешного вскрытия системы шифрования повышается с увеличением длины шифртекста.
Силовая атака
Силовая атака заключается в подборе ключа шифрования путем перебора подряд всех возможных ключей вплоть до нахождения истинного. В отличие от всех других методов эта атака применима для всех типов шифров, но она имеет максимальную сложность реализации и, соответственно, требует максимальных затрат времени и средств.
Алгоритм криптоанализа заключается в следующем: определяется множество всех возможных ключей шифрования для данной криптосистемы и для каждого ключа выполняются шаги:
- Дешифрование известного шифртекста на этом ключе;
- Анализ «осмысленности» полученного предполагаемого открытого текста, например путем поиска соответствующих слов в словаре возможных сообщений;
- Принятие решения об истинности найденного ключа на основе результатов предыдущих шагов дешифрования.
Данный метод работает тем медленнее, чем больше длина шифртекста, используемого для криптоанализа.
3. Задания
3.1. Лабораторная работа №1
Тема: симметричные криптосистемы.
Цель работы: Разработать криптографическую защиту информации, содержащейся в файле данных, с помощью алгоритма шифрования, указанного в варианте. Для этого:
1. Разработать алгоритмы шифрования и дешифрования блока (потока) открытого текста заданной длины из алфавита Zn на заданном ключе с помощью метода, указанного в варианте(Если это позволяет алгоритм, длину блока взять кратной 8 бит).