Сайт о телевидении

Сайт о телевидении

» » Шифрование и шифры. ENLiGHT Project. Криптографический анализ асимметричных систем шифрования

Шифрование и шифры. ENLiGHT Project. Криптографический анализ асимметричных систем шифрования

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

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

Среди асимметричных (открытых) криптосистем наиболее широкое распространение получила криптографическая система RSA. В этой системе получатель сообщения выбирает два больших простых числа p и q так, чтобы произведение n = pq находилось за пределами вычислительных возможностей. Исходное сообщение М может иметь произвольную длину в диапазоне 1

Исходный текст М восстанавливается из шифрованного C обратным преобразованием

Получатель выбирает e и d так, чтобы выполнялись условия:

где - функция Эйлера, равная (p - 1)(q - 1);

(a, b) - наибольший общий делитель двух чисел.

То есть e и d являются в мультипликативной группе обратными величинами в арифметике вычетов по mod .

Очевидно, что главной целью криптографического раскрытия является определение секретного ключа (показателя степени при C - значения d).

Известны три способа, которыми мог бы воспользоваться криптоаналитик, для раскрытия величины d по открытой информации о паре {e, n}.

Факторизация n

Разложение величины n на простые множители позволяет вычислить функцию и, следовательно, скрытое значение d, используя уравнение

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

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

Прямое вычисление

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

x = p + q = n + 1 - ,

y = (p - q) 2 = x 2 - 4n.

Зная, можно определить x и, следовательно, y, зная x и y, простые p и q можно определить из следующих соотношений:

Прямая оценка d

Третий способ криптоанализа состоит в непосредственном вычислении величины d. Аргументация этого способа основана на том, что, если d выбрано достаточно большим, чтобы простой перебор был неприемлем, вычисление d не проще факторизации n, поскольку, если d известно, то n легко факторизуется. Это можно показать следующим образом. Если d известно, то можно вычислить величину, кратную функции Эйлера, используя условие

где k - произвольное целое число.

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

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

пусть нам дано целое число n>0, и требуется, если это возможно, найти два числа a и b, таких, что ab = n. На самом деле имеются две различные задачи: первая, называемая тестом на простоту - это проверка того, существуют ли такие a и b; вторая, называемая разложением - это задача их нахождения. Рассмотрим обе эти задачи.

Первый детерминистический тест.

Этот тест основан на малой теореме Ферма, которая утверждает, что если p - простое число, то a p-1 1 (mod p) для всех a, 1

Таким образом, тест состоит в выборе числа а, меньшего b и проверке

b на принадлежность классу простых чисел согласно условию a b-1 1 (mod b) в соответствии с приведенным выражением. Практически требуется проверить только несколько значений a. Выбор а, равным 3, позволяет выявить все составные числа. Тем не менее известно, что этот тест пропускает составные числа Кармайкла (например число 561 =3 х 11 х 17).

Второй детерминистический тест.

Разделим число “b” последовательно на 2, 3, ..., . Если при каком-нибудь делении мы получим нулевой остаток, то число “b” составное, а делитель и частное являются его сомножителями; в противном случае b - простое.

Поскольку необходимо выполнить делений, то время проверки простоты числа “b” равно O().

Этот очень медленный экспоненциальный тест не только определяет является ли число простым, но и находит сомножители составного числа.

Третий детерминистический тест.

Число “b” просто тогда и только тогда, когда b | {(b-1)! + 1}. Факториал (b-1)! и проверка делимости (b-1)!+1 для больших “b” уничтожает всякий интерес к этому тесту. Если `b" имеет 100 десятичных цифр, то (b-1)! состоит примерно из 100 102 цифр.

Все приведенные выше тесты были детерминистическими. Это означает, что для заданного числа “b” мы всегда получаем ответ, является ли оно простым или составным. Если заменить слово «всегда» на «с некоторой вероятностью», то оказывается возможным построить вероятностные тесты, которые называют также тестами псевдопростоты.

Первый вероятностный тест.

Этот тест позволяет выявить все составные числа Кармайкла. Выбирается случайное число a в диапазоне от 1 до b-1 и проверяется выполнение условий.

(a, b) = 1, J(a, b) a (b-1)/2 (mod b),

где J(a, b) символ Якоби.

Символ Якоби определяется следующими соотношениями:

J(a, p) = 1, если x 2 a (mod p) имеет решения в Z p ,

J(a, p) = -1, если x 2 a (mod p) не имеет решения в Z p ,

где Z p - кольцо вычетов по модулю p.

Если b - простое число, условия приведенные выше, всегда выполняются, а если b - составное, то они не выполняются с вероятностью. Поэтому выполнение k тестов гарантирует, что ответ неправилен с вероятностью 2 -k .

Второй вероятностный тест.

Поскольку число b, которое должно быть простым, всегда нечетное, то его можно представить в виде

где s - четное число. Затем в тесте выбирается случайным образом число a в диапазоне от 1 до b-1 и проверяется выполнение условий

1 (mod b) для 0 < j

Оба теста используются для проверки числа на принадлежность классу простых и требуют порядка О(log 2 b) операций над большими числами.

Третий вероятностный тест.

Для заданного b выбираем случайным образом m, 1

Вероятность того, что выдается ответ “b - составное число”, равна вероятности того, что m | b. Если d(b) число делителей b и m - случайно выбрано в пределах 1

Это очень слабый тест.

Четвертый вероятностный тест.

Для заданного “b” выбираем случайным образом m, 1

Если b составное число, то количество чисел m

Пятый вероятностный тест.

Это тест сильной псевдопростоты. Пусть заданы b и m. Пусть

где t - нечетное число и рассмотрим числа для (x r - наименьший по абсолютной величине остаток по модулю b).

Если либо x 0 = 1, либо найдется индекс i, i

Докажем это от противного. Предположим, что b - нечетное простое число. Покажем по индукции, что 1 (mod b) для, что будет противоречить условию теоремы.

Очевидно, что это справедливо для r = S по теореме Ферма. Предполагая справедливость утверждения для i, нетрудно видеть, что оно справедливо для i-1, потому что равенство

влечет за собой, что возводимое в квадрат число равно ±1. Но -1 не подходит по условию (иначе бы тест выдал ответ "не удалось определить").

Доказано, что если b - составное число, то вероятность того, что тест выдаст ответ "b - составное число" не меньше .

Разложение на множители больших целых чисел.

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

Метод основывается на идее Лежандра, если U 2 V 2 (mod b) 0

Пусть мы хотим разложить на множители число b. Пусть n = - максимальное число, не превосходящее, и вычислим числа a k = (n + k) 2 - b для небольших k (числа k могут быть и отрицательными).

Пусть {q i , i = 1, 2, …, j} - множество небольших простых чисел, которые могут делить выражение вида x 2 - b (т.е. b является квадратом по модулю q i). Такое множество обычно называется мультипликативной базой В. Запомним все числа a k , которые могут быть разложены по мультипликативной базе, т.е. записаны в виде

Такие ak называются В-числами. С каждым В-числом ak связывается вектор показателей

Если мы найдем достаточно много В-чисел, чтобы множество соответствующих векторов показателей было линейно зависимо по модулю 2

(любое множество из j+2 В-чисел обладает этим свойством), то можно будет представить нулевой вектор в виде суммы векторов показателей некоторого множества S, скажем

Определим целые числа

i = 0, 1, …, j,

Из сказанного выше следует, что U 2 V 2 (mod b) и (U-V, b) может быть нетривиальным делителем b.

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

Т. е. противник просто проводит j раз зашифрование на открытом ключе перехваченного шифротекста. Это выглядит следующим образом: (С e) e) e ..) e (mod n)=С e j(mod n)). Найдя такое j, противник вычисляет C e (j-1)(mod n) (т.е. j-1 раз повторяет операцию зашифрования) - это значение и есть открытый текст M. Это следует из того, что С e j(mod n)=(C e (j-1)(mod n))e=C. Т. е. некоторое число C e (j-1)(mod n) в степени e дает шифротекст С. А это открытый текст M.

Пример. p=983, q=563, e=49, M=123456.

C=M 49 (mod n)=1603, C497(mod n)=85978, C498(mod n)=123456, C499(mod n)=1603.

Стойкость системы шифрования, классификация систем шифрования по стойкости. Виды атак на систему шифрования.

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

Атаки нарушителя

1. Криптоанализ ведется, только на основе, перехваченных криптограмм;

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

3.Криптоанализ ведется на основе выбираемого противником открытого сообщения;

Классы систем шифрования

· Безусловно стойкие или идеальные, совершенные

· Вычислительностойкие

Безусловно стойкие (идеальные) системы шифрования

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

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

одного из возможных сообщений источника Математически условие АССШ можетбыть записано в виде:

Условная вероятность того, что сообщение M i было зашифровано криптограммой E j ;

– априорная (при неизвестной криптограмме) вероятность присутствия сообщения M i .

Вычислительно стойкие системы шифрования

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

Время криптоанализа определяется:

1. Сложностью алгоритма дешифрования;

2. Быстродействием вычислительных устройств,

осуществляющих дешифрование

Сложность алгоритмов криптоанализа должна соответствовать сложности решения сложной задачи.

Основные подходы к криптоанализу:

1. Тотальный перебор ключей

2. Анализ статистических особенностей криптограмм

3. Линейный криптоанализ

4. Дифференциальный криптоанализ

Быстродействие вычислительных устройств 10 10 - 10 12 операций/с

Быстродействие ЭВМ увеличивается в 4 раза каждые 3 года

Шифр замены, его свойства.

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

Шифром колонной замены называется шифр с алфавитом открытых сообщений Z m, совпадающим с алфавитом шифрованных сообщений и ключевым множеством K.

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

Свойства шифра замены.

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

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

3. При шифровании методом замены не происходит размножение ошибок, возникающих в канале связи из-за помех.

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

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

Согласно принципу Керхгоффа, алгоритмы шифрова­ния и дешифрования полностью известны криптоаналитику. Неизвестен лишь ключ, который используется как для шифрования, так и для дешифро­вания. Одинаковые блоки сообщений Мi и Мj всегда преобразуются в оди­наковые блоки криптограмм Ei и Ej . Если это свойство является нежела­тельным, то используют другую модификацию того же самого блокового алгоритма шифрования

Принципы построения блоковых шифров состоят в том, что в алгоритме блокового шифра необхо­димо использовать:

а) подстановки (нелинейные преобразования коротких частей (под­ блоков блокового шифра);

б) перестановки символов в блоках;

в) итерирование операций (а) и (б) (т. е. многократное повторение их с разными ключами).

Схема Файстеля.

Для упрощения процедур шифрования и дешифрования используется схема Файстеля, основанная на следующих принципах:

а) каждый текущий блок делится на две равные части - левую Li и правую Ri, где i - параметр итерации (раунда);

б) способ формирования следующих «половинок» блоков из предыду­щих, определяется, как показано на рис. 3.3, где ki - ключ i-гo раунда.

Представим это преобразование в аналитической форме:

L i = R i-1 , R i =L i-l + f(R i-1 , k i),

где f( ) - нелинейная функция от двух аргументов, в которой нелинейность определяется, например, таблицей.

Особености схемы Фейстеля:

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

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


Характеристики шифра АЕS

1.Может работать быстрее, чем обычный блочный шифр;

2.Может быть реализован на смарт-карте, используя небольшой РАМ и имея небольшое число циклов;

3. Преобразование раунда допускает параллельное выполнение;

4. Не использует арифметических операций, поэтому тип архитектуры процессора не имеет значения;

5. Может быть использован для вычисления МАС-кода и хэш-функции.

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

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

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

Следующее преобразование состоит в умножении каждой клетки квадрата, представленной в виде двоичного вектор-столбца ( , ) , на фиксированную матрицу и добавлении также фиксированного вектор-столбца, причем все операции здесь выполняются в поле GF{2}:

Используемая в этом преобразовании матрица и вектор-столбец сохраняются одинаковыми на всех раундах и не зависят от ключа.

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

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

Следующее преобразование называется перемешиванием столбцов. На этом шаге каждый С-й столбец квадратной матрицы представляется как 4-мерный вектор над полем GF(), и далее производится умножение в этом поле, заданном неприводимым полиномом + + + х +1, на определенную матрицу с элементами из этого же поля:

где элементы, показанные в этой матрице, задаются как элементы поля GF() (т. е. как двоичные последовательности длины 8), что иллюстрируется следующим примером:

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

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

Особенности шифра AES

1) AES ориентирован в основном на реализацию с 8-разрядными процессорами;

2) все раундовые преобразования выполняются в конечных полях, что допускает простую реализацию на различных платформах.

Стойкость шифра AES

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

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

Скорость шифрования AES

При программной реализации данный алгоритм наиболее эффективно реализуется на 8- и 32-разрядных платформах. Для типичных ПК скорость шифрования может составлять порядка 1 Мбайт/с - 500 кбайт/с. При аппаратной реализации высокие скорости шифрования (порядка 100 Мбайт/с и выше) потребуют увеличения аппаратных ресурсов и, следовательно, увеличения габаритов устройства.

Стойкость шифра A5/1

При разработке этого шифра предполагалось, что он будет иметь высокую

стойкость, так как количество его ключей достаточно велико, однако

дальнейшие исследования, проводившиеся независимыми криптографами

Показали, что у этого шифра есть слабые стороны. Одна из них состоит

в том, что ЛРР, входящие в состав шифратора, имеют малые длины, и поэтому

они подвержены некоторым модификациям статистических атак, а также

атакам на основе обменных соотношений между требуемым объемом памяти

и временем анализа.

В конечном итоге исследования, которые проводились начиная с

2000 г. (т. е. почти сразу после введения этого стандарта), показали, что данный

шифр может быть «взломан» с использованием обычного ПК в реальном

22.Возведение в степень, нахождение дискретного логарифма

Возведение в степень по модулю - это вычисление остатка от деления натурального числа b (основание), возведенного в степень e (показатель степени), на натуральное число m (модуль).
. Быстрый способ возведения Д.Кнута.

Представим показатель степени в двоичном виде;

Каждую единице заменим парой букв КУ (квадрат+умножение);

Каждый ноль заменим буквой К (квадрат);

В образовавшейся последовательности вычеркнем первую пару КУ;

Над основанием a проводим вычисления, согласно полученной последовательности.

Пример: 3 37 (mod7)

37 = 100101 = КУКККУККУ= КККУККУ

3®3 2 (mod7)=2®2 2 (mod7)=4®4 2 (mod7)=2®2×3(mod7)=6®6 2 (mod7)= 1®1 2 (mod7)= 1®1×3(mod7)=3

Сложность вычислений для операции возведения в степень: N@O(2logx).

Сложность вычислений для операции дискретного логарифмирования: N@O((n) 1/2).

Нахождение дискретного логарифма методом «встречи посредине»

Строим базу данных размера O((n) 1/2) вида a z (modn) для случайных чисел zÎ и сортируем ее.

Для случайных чисел b, таких что НОД(b,n-1)=1 вычисляем y b (modn) и сравниваем с числами базы данных.

С большой вероятностью после нескольких попыток получаем

a z (modn)= y b (modn)

4. Возводим обе части в степень b -1 , получим a z · b-1 (modn)= y (modn). Откуда следует

Этот метод имеет сложость N t @O((n) 1/2 logn), N v @O((n) 1/2)
Возвести в степень по модулю довольно легко, даже при больших входных значениях. А вот вычисление дискретного логарифма, то есть нахождение показателя степениe при заданных b , c и m , намного сложнее. Такое одностороннее поведение функции делает её кандидатом для использования в криптографических алгоритмах.

КС Эль-Гамаля.

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

Генерирование ключей .

Пользователь А проделывает следующие операции для генерирования ключей:

1)генерирует простое число p и примитивный элемент ɑ∈GF(p);

2) выбирает случайное число а такое, что 1<= a<= p-2, и вычисляет число ɑ^a;

3) в качестве открытого ключа выбирает набор: (p, ɑ, ɑ^amodp), а в качестве закрытого ключа – число а.

Шифрование .

Пользователь В выполняет следующие шаги для шифрования сообщения М, предназначенного пользователю А:

1) Получает открытый ключ А;

2) Представляет сообщение М в виде цепочки чисел Мi, каждое из которых не превосходит р-1;

3) Выбирает случайное число k такое, что 1<=k<=p-2;

4) Вычисляет ɣ=(ɑ^k)mod p, б=Мi((ɑ^a)^k) mod p;

5) Посылает криптограмму C=(ɣ,б) пользователю А.

Дешифрование

Пользователь А выполняет следующие шаги для дешифрования сообщения, полученного от пользователя В:

1) используя свой закрытый ключ, вычисляет (ɣ^(-a ))mod p

2) восстанавливает сообщение Mi=(ɣ^(-a))*б mod p

Действительно, ɣ^(-a )*б =(ɑ^(-a k))*Mi*(ɑ^(a k))=Mi mod p

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

Преимущество КС Эль-Гамаля состоит также и в том, что тогда все пользователи в сети могут выбирать одинаковые ɑ и р , что невозможно для КС РША. Кроме того, как будет показано далее, эта схема может быть естественным образом распространена на случай эллиптических кривых.

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

Стойкость КС Эль-Гамаля

Проблема восстановления сообщения М по заданным p , ɑ, ɑ^a, б , ɣ при неизвестном а эквивалентна решению задачи Диффи-Хеллман.

Ясно также, что если будет решена проблема нахождения дискретного логарифма, то криптосистема Эль-Гамаля будет вскрыта. При выборе р с разрядностью 768 бит (для повышенной стойкости-до 1024 бит), стойкость КС Эль-Гамаля будет такой же, как и у КС РША при выборе в последней тех же параметров для модуля.

Важно отметить, что для шифрования различных сообщений Мi, Мj необходимо использовать различные значения чисел k, поскольку в противоположном случае б1/б2=Мi/Мj, и тогда сообщение Мj может быть легко найдено, если известно сообщение Мi.


Генерирование ключей.

Случайно выбираются два простых числа p и q. Находится

модуль N=pq. Находится функция Эйлера φ (N)= (p-1)(q-1).

Выбираем число e такое, что НОД(e, φ (N))=1.

Находим d, как обратный элемент к e, de=1(mod φ (N)).

Объявляем d=SK, (e,N)=PK. PK сообщается всем

корреспондентам.

Шифрование .

Корр. А передает зашифрованное сообщение корр.В

(использует открытый ключ корр. В)

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

Корр. В расшифровывает принятую криптограмму от

корр.А,используя свой секретный ключ.

Атаки.

1. Система РША может быть вскрыта, если удастся найти p и q, т. е. факторизовать N.

Исходя из этого факта p и q должны выбираться такой большой разрядности, чтобы факторизация числа n потребовала необозримо большого времени, даже с использованием всех доступных и современных средств вычислительной техники.

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

Так, например ln n = 200, если, то число операций будет приблизительно равно 1,37 ∙ 10 14 .

При увеличении числа разрядов n до 1000 и более время факторизации становится совершенно необозримым.

2. Другой естественной атакой на КС РША является дискретное логарифмирование. Эта атака (при известном сообщении) выполняется следующим образом: d = log E M mod N. Однако задача дискретного логарифмирования по модулю многоразрядных чисел также относится к трудным в математике, и оказывается, что она имеет почти такую же сложность, как и задача факторизации.

3. Циклическая атака. Будем последовательно возводить полученную криптограмму в степень равную значению открытого ключа т.е. (((((E e) e)…..) e .

Если при некотором шаге окажется, что E i =E, то это означает,

что E i-1 =m. Доказывается, что данная атака не лучше атаки факторизации N.

4. Отсутствие шифрования. Этот случай возможен, если в результате шифрования получаем открытое сообщение, т. е. M e mod n = M. Такое условие должно выполниться хотя бы для одного из сообщений, например, для сообщений M = 0, 1, n – 1 . На самом деле таких сообщений, которые вообще! не шифруются, существует в точности . Их число всегда не менее 9. Однако при случайном выборе q и p доля таких сообщений будет ничтожно мала и они почти никогда не встретятся на практике.

5. Атака при малом объеме возможных сообщений

Предположим, что количество сообщений ограничено значениями M1 , M2 ,… , Mr , где r обозримо. (Это могут быть, например, различные команды – вперед, назад, влево, вправо и т. п.). Тогда сообщение может быть легко расшифровано.

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

Способ борьбы с такой атакой – это «подсаливание» сообщений (т. е. присоединение к ним небольших цепочек бит, полученных с использованием чисто случайного датчика).

ВИДЫ

Простая ЭП – подпись, которая путем использования кодов, паролей или иных средств подтверждает факт формирования ЭП определенным лицом.

· Неквалифицированная:
Получена в результате криптографического преобразования информации с использованием ключа ЭП;

Позволяет определить лицо, подписавшее документ;

Позволяет обнаружить факт внесения изменений в ЭД;

Создается с использованием средств ЭП;

· Квалифицированная:
Соответствует всем признакам неквалифицированной ЭП;

Ключ проверки ЭП указан в квалифицированном сертификате.

Для создания и проверки ЭП используются средства ЭП, получившие подтверждение соответствия в соответствии с законом об ЭП.

Схема ЭП РША.

Пусть имеется некоторое сообщение М и некоторым пользователем А сгенерирована пара открытый/закрытый ключ для системы РША, т. е. числа e A ,n A ; d A . Тогда сообщение М разбивается на блоки, каждый из которых может быть представлен целым числом, не превосходящим n А. Для каждого из таких сообщений-цифр М формируется ЦП S по следующему правилу: S = М dA mod(n A). Далее ЦП присоединяется к сообщению, образуя так называемое подписанное сообщение, т. е. пару M,S . Для верификации ЦП поль­зователь должен получить открытый ключ А, а также «подписанное» (но возможно фальсифицированное) сообщение М, S и вычислить Ṁ =S eA mod(e A). Далее он сравнивает Ṁ с М и при их совпадении полага­ет, что сообщение М действительно подписано А, в противном случае от­вергает его, как подделку или искажение.


Схема ЭП Эль-Гамаля.

ЭП - Электронная подпись (ЦП – Цифровая Подпись)

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

Генерирование ключей:

1) генерируется большое простое число р и примитивный элемент а над конечным полем GF(p);

2) генерируется число x : 1 ;

3) вычисляется у = а x mod(р) ;

4) выбирается открытый ключ верификации ЦП: (р, а, у ) и секретный ключ создания ЦП: x .

Формирование ЦП

Если пользователь А хочет подписать сообщение m, представленное в виде числа, принадлежащего Zp , то он выполняет следующие операции:

1) генерирует секретное число k : 1 ≤ k ≤ р – 2; gcd(k , р - l) = 1, где gcd – это НОД

2) вычисляет r = a k mod(р);

3) вычисляет k -1 mod(p - 1);

4) вычисляет s = k -l (m - xr )mod(p - l);

5) Формирует ЦП S к сообщению m как пару чисел S = (r, t).

Проверка (верификация) ЦП

Для того чтобы проверить подпись S, созданную А под сообщением M, любой пользователь выполняет следующие шаги:

1) получает открытый ключ А: (р, а, у) ;

2)проверяет, что 1 ≤ r ≤ р - 1 , и если это не выполняется, то отвер­гает ЦП;

3) рассчитывает V 1 = y r r s mod(р) ;

4) рассчитывает V 2 = а m mod(р);

5) принимает ЦП как правильную при условии, что V 1 = V 2

Стойкость ЦП на основе КС Эль-Гамаля

1) Злоумышленник может попытаться подделать подпись к своему сооб­щению М следующим образом: сгенерировать случайное число к, вычислить r = а k mod(р), а затем попытаться найти s = k - l (m - xr )mod(p - l).

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

3) Стоит отметить, что если не выполнен шаг 2 алгоритма ве­рификации ЦП , то злоумышленник может правильно подписать любое сооб­щение по своему выбору при условии, что в его распоряжении имеется какое-либо другое сообщение с правильной ЦП. Таким образом, при выборе модуля р , который в двоичном представлении имеет длину порядка 768 бит, обеспечивается хорошая стойкость ЦП, а для обеспечения долговременной стойкости целесообразно увеличить ее до 1024 бит.


Требования к криптографическим ХФ

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

2.Слабая коллизионная стойкость, когда для заданных x, h(x)=h вычислительно неосуществимо найти такое другое x’ значение, которое удовлетворяет уравнению h(x’)=h.

3.Сильная коллизионная стойкость, когда вычислительно неосуществимо найти такую пару аргументов x, x’ , для которых выполняется соотношение h(x)=h(x’).

Исправление уязвимости

Деннинг и Сакко предложили использовать метки времени в сообщениях для предотвращения атак, подобных рассмотренной выше. Обозначим такую метку буквой t. Рассмотрим вариант исправления уязвимости:

Компоненты PKI

· Сертификационный центр (Certificate Authority (CA)) - часть системы открытых ключей, которая выпускает сертификат для подтверждения прав пользователей или систем обратившихся с запросом. Она создает сертификат и подписывает его, используя частный ключ. Благодаря своей функции по созданию сертификатов, сертификационный центр является центральной частью PKI.

· Хранилище сертификатов (Certificate Repository) . Хранилище действующих сертификатов и списка аннулированных (Certificate Revocation Lists (CRLs)). Приложения проверяют пригодность сертификата и уровень доступа предоставляемый им, сверяя с образцом содержащимся в хранилище.

· Сервер восстановления ключей (Key Recovery Server) - сервер, осуществляющий автоматическое восстановление ключей, если данный сервис установлен.

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

· Регистрационный центр (Registration Authority) - модуль отвечающий за регистрацию пользователей и принятие запросов на сертификат.

· Сервер безопасности (Security Server) - сервер, который обеспечивает управление доступом пользователей, цифровыми сертификатами и надежными взаимосвязями в среде PKI. Сервер безопасности централизованно управляет всеми пользователями, сертификатами, связями с сертификационным центром, отчетами и проверяет список аннулированных сертификатов.

Функции PKI

· Регистрация (Registration) - процесс сбора информации о пользователе и проверки ее подлинности, которая затем используется при регистрации пользователя, в соответствии с правилами безопасности.

· Выдача сертификата (Certificate Issuance) . Как только CA подписал сертификат он выдается просителю и/или отправляется в хранилище сертификатов. СА проставляет на сертификатах срок действия, требуя таким образом периодического возобновления сертификата.

· Аннулирование сертификата (Certificate Revocation) . Сертификат может стать недействительным до окончания срока действия в силу различных причин: пользователь уволился из компании, сменил имя или если его частный ключ был скомпрометирован. При этих обстоятельствах СА аннулирует сертификат, занося его серийный номер в СRL.

· Восстановление ключа (Key Recovery) . Дополнительная функция PKI позволяет восстанавливать данные или сообщения в случае утери ключа.

· Управление работой (Lifecycle Management) - постоянная поддержка сертификатов в PKI, включающая обновление, восстановление и архивирование ключей. Эти функции выполняются периодически, а не в ответ на специальные запросы. Автоматизированное управление ключами наиболее важная функция для больших PKI. Ручное управление ключами может ограничить масштабируемость PKI.

Основные определения

· Certificate Revocation Lists (CRLs) - списоканнулированныхсертификатов. Аннулирование может быть вызвано сменой места работы, кражей частного ключа или другими причинами. Приложения, работающие с PKI, могут сверять сертификаты пользователей со списком CRL, прежде чем предоставить доступ в соответствии с этим сертификатом.

· Цифровойсертификат (Digital Certificate/X.509 Certificate) . Структура данных, применяющаяся для связывания определенного модуля с определенным открытым ключом. Цифровые сертификаты используются для подтверждения подлинности пользователей, приложений и сервисов, и для контроля доступа (авторизации). Цифровые сертификаты издаются и распределяются СА.

· Цифровой конверт (Digital Envelope) . Метод использования шифрования с открытым ключом для безопасного распространения секретных ключей использующихся при симметричном шифровании и для посылки зашифрованных сообщений. Значительно сокращается проблема распространения ключей связанная с симметричным шифрованием.

· Цифровая подпись (Digital Signature) . Метод использования шифрования с открытым ключом для обеспечения целостности данных и невозможности отказа от посылки. Зашифрованный блок информации после расшифровки получателем, идентифицирует отправителя и подтверждает сохранность данных. Например: документ "сжат", HASH зашифрован с помощью частного ключа отправителя и приложен к документу (по сути, это означает приложить "отпечаток пальца" этого документа). Получатель использует открытый ключ для расшифровки полученного сообщения до состояния "выжимки", которая затем сравнивается с "выжимкой" полученной после "сжатия" присланного документа. Если обе "выжимки" не совпали, то это означает, что документ был изменен или поврежден в процессе пересылки.

· Шифрование с открытым ключом (Public Key Cryptography) . Есть два основных типа шифрования: с открытым ключом и с секретным (симметричным) ключом. При шифровании с открытым ключом используется пара ключей: открытый, т.е. свободно доступный, и соответствующий ему частный ключ, известный только конкретному пользователю, приложению или сервису, которые владеют этим ключом. Эта пара ключей связана таким образом, что зашифрованное частным ключом, может быть расшифровано только открытым ключом и наоборот.

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

· Алгоритм RSA - первая шифровальная система с открытым ключом, названная в честь ее изобретателей: Ronald Rivest, Adi Shamir и Leonard Adleman.

· Смарт-карта. Устройство похожее на кредитную карточку со встроенной памятью и процессором, используемое для защищенного хранения ключей и сертификатов пользователя а также другой информации (как правило, социального и медицинского назначения).

· Digital Credentials. В рамках технологии PKI, стандарт ISO/TS 17090-1 определяет этот термин как криптографически защищенный объект, который может содержать индивидуальные ключи пользователя, сертификаты индивидуальных ключей, сертификаты Центров Сертификации PKI-структуры пользователя, список доверенных ЦС, а также другие параметры, относящиеся к домену пользователя - идентификатор пользователя, наименования применяемых криптографических алгоритмов, значения стартовых величин и т.д.. Credentials могут размещаться на аппаратных или программных носителях.

Принцип работы

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

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

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

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

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

Так за 400 лет до н. э. в Спарте использовалось шифрование на круговом цилиндре. На него наматывался свиток, после чего по свитку параллельно оси цилиндра записывался текст - строка за строкой. В результате на развернутом свитке буквы располагались без видимого порядка. Для прочтения послания получатель должен был намотать свиток на точно такой же цилиндр.

За 300 лет до н. э. в Греции был написан труд «Тактикус» о скрытых сообщениях. За 200 лет до н. э. изобретен полибианский квадрат, содержавший 5x5=25 клеток для двадцати четырех букв греческого алфавита и пробела, вписанных в произвольном порядке. При шифровании текста нужная буква отыскивалась в квадрате и заменялась на другую букву из того же столбца, но вписанную строкою ниже. Буква, которая находилась в нижней строке квадрата, заменялась на букву из верхней строки того же столбца. Получатель, имевший точно такой же квадрат, производил расшифровку сообщения, выполняя указанные операции в обратном порядке.

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

п=(К + I) mod m,

где п - номер буквы, полученной в результате шифрования буквы с номером I Здесь использована операция вычисления по модулю т, при выполнении которой записывается не сама сумма К+ I , а остаток от деления этой суммы на т.

Обобщение шифра Цезаря называется шифром простой замены. Его суть заключается в том, что все буквы алфавита заменяются другими буквами того же алфавита по правилу, которое является ключом. Например, а заменяется на в, б-на с, в - на в ,..., я - на г. Количество возможных при таком шифровании перестановок, соответствующих алфавиту с объемом т = 32, составляет m ! =32! = 2, 63 10 35 . Если в одну секунду при дешифровании методом простого перебора перебирать миллион ключей, то общее время на дешифровку составит 8,3-10 21 лет.



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

Криптографией занимались многие известные математики, такие как Виет, Кардано, Лейбниц и, наконец, Френсис Бэкон. Последний предложил двоичное кодирование латинского алфавита.

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

Промышленная революция в развитых странах привела к созданию шифровальных машин. В конце XVIII века Джефферсоном (будущим третьим президентом США) были изобретены шифрующие колеса. Первую практически работающую шифровальную машину предложил в 1917 г. Вернам. В том же году была изобретена роторная шифровальная машина, впоследствии выпускавшаяся фирмой Сименс под названием «Энигма» (загадка), - основной противник криптографов Союзных держав в годы Второй мировой войны.

Неоценимый вклад в криптографию внес К. Шеннон, особенно своей работой «Секретность и скрытность», написанной в 1948 г. В 1976 г. Диффи и Хеллман предложили криптосистемы с открытым ключом. В 1977 г. в США был введен открытый Федеральный стандарт шифрования для несекретных сообщений (DES). В 1989 году вводится открытая отечественная система шифрования ГОСТ 28147-89.

Рис. 1. Основные этапы развития криптографических систем

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

Широкое использование математических методов для доказательства стойкости шифров или для проведения криптоанализа,

Использование средств быстродействующей вычислительной техники,

Открытие нового вида криптографии с более «прозрачными» методами криптоанализа (криптография с общедоступным ключом),

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

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

2. Математическая модель системы шифрования/дешифрования дискрет-ных сообщений

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

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

, (1)

, (2)

которые преобразуют сообщение М в криптограмму Е при помощи ключа шифрования К Ш и, наоборот, криптограмму Е в сообщение М при помощи ключа дешифрования К ДШ. Обе функции, задающие криптосистему, должны удовлетворять следующим требованиям:

Функции f (,) и g(,) при известных аргументах вычисляются просто,

Функция g(E, К ДШ ) при неизвестном ключе К ДШ вычисляется сложно.

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

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

Если К Ш = К ДШ, то система шифрования называется несимметричной {двухключевой). В этом случае ключ К Ш доставляется в пункт шифрования, а ключ К ДШ - в пункт дешифрования. Оба ключа очевидно должны быть связаны функциональной зависимостью К ДШ = φ(К Ш) но такой, что по известному ключу шифрования К Ш нельзя было бы восстановить ключ дешифрования К ДШ Это означает, что для несимметричной системы шифрования φ(.) должна быть трудно вычислимой функцией. В такой системе имеется возможность распределять секретным образом среди законных пользователей только их ключи дешифрования, а ключи шифрования сделать открытыми и опубликовать, например, в общедоступном справочнике. Поэтому рассматриваемая криптосистема называется системой с открытым {общедоступным) ключом. Криптосистема с общедоступным ключом (Public key cryptosystem) была впервые предложена Диффи и Хелманом в 1976 году. Следует различать три основных вида нападения (атак) оппонентов на криптосистему:

Только при известной криптограмме Е ,

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

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

Современные криптосистемы считаются стойкими, если они стойки относительно всех трех видов атак.

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

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

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

Местоположение и величина ошибок в принятой криптограмме определяются вектором канальных ошибок е . При двоичной системе передачи принятая криптограмма будет иметь вид Е - Е ® ё , где знак ® означает побитное сложение по модулю 2, а общее число ошибок t равно норме вектора ошибок |е|,т.е. t= |е|. Число ошибок е" в расшифрованном сообщении М подсчитывается как t"= |f |, где 1= Й8А/. Ошибки не размножаются при условии, что f = t.

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

Перед отправлением данных по линии связи или перед помещением на хранение они подвергаются зашифрованию;
- для восстановления исходных данных из зашифрованных к ним применяется процедура расшифрования.

На следующем ниже рисунке 1 приведена схема преобразования данных при шифровании:

Рис.1. Схема преобразования данных при шифровании.

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

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

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

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

T = D(E(T))

Второе условие, которому должен удовлетворять шифр, следующее: он должен... шифровать данные, то есть делать их непонятными для непосвященного.

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

Отправленное сообщение до поступления к получателю является для него и, естественно, для злоумышленника неопределенным - если это было бы не так, тогда не было бы вообще никакого смысла его посылать. Пусть возможна отправка сообщений T1,T2,...,Tn с вероятностью p1, p2,..., pn соответственно. Тогда мерой неопределенности сообщения для всех, кто обладает этой априорной информацией, может служить величина математического ожидания логарифма вероятности одного сообщения, взятая со знаком "минус"; по некоторым соображениям в качестве основания логарифма удобно выбрать 2:

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

H(T ) = -2 N ·2 -N ·log 2 (2 -N ) = N = | T |,

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

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

,

где через p (T i | T") обозначена вероятность того, что исходное сообщение есть T i при условии, что результат его зашифрования есть T" .

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

I = H (T ) - H (T | T " ).

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

В наилучшем для разработчиков шифра случае обе эти неопределенности равны:

H(T | T " ) = H (T ),

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

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

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

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

1 0 0 1 0 1 1 1 0 1 0 1

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

маска исходный текст 0000 100101110101 0001 100001100100 0010 101101010110 ..... 1111 011010001010

Таким образом, теперь вероятность правильно угадать исходный текст равна 1/16 - знание особенности использованного способа шифрования повысило ее в 256 раз. Отсюда следует интересный вывод: чем больше неопределенность в шифрующем преобразовании для постороннего лица, тем дальше оно стоит от разгадки шифра, тем шифр надежнее. Шифр, полностью неопределенный для злоумышленника

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

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

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

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

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

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

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

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

T" = E (T ) = E K (T ),

здесь K - ключ шифра.

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

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

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

Появляется возможность для точной оценки "степени неопределенности" алгоритма шифрования - она просто равна неопределенности используемого ключа:

H (E K ) = H (K ).

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

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

H(T ) = | T |.

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

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

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

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

Примером абсолютно стойкого шифра может служить одноразовая гамма Вернама - наложение на открытые данные ( T ) ключа (K ) такого же размера, составленного из статистически независимых битов, принимающих возможные значения с одинаковой вероятностью, с помощью некоторой бинарной операции °:

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

Требует для своей реализации минимальной по сложности логики из всех возможных операций;

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

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

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

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

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

Если ключ равен 0, инвертируются нечетные по номеру биты исходного текста, нумерация слева направо;

Если ключ равен 1, инвертируются четные по номеру биты исходного текста;

Таким образом, E 0 (01) = 11, E 1 (01) = 00. Очевидно, что наш шифр не обладает абсолютной стойкостью. Предположим, что перехвачена шифровка "10". Каков исходный текст? Понятно, что он может быть как 00 так и 11 в зависимости от значения ключа, и однозначно определить это невозможно, что и требовалось доказать. Для более серьезных шифров у криптоаналитика будет просто больше "вариантов выбора" открытого текста, и никаких указаний на то, какой из них предпочесть.

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

1. Функция ненадежности ключа - неопределенность ключа при известных n битах шифротекста:

f (n ) = H (K | T " ), где | T " | = n .

Понятно, что f (n) может быть определена не для всех n .

2. Расстояние единственности шифра - такое значение n , при котором функция ненадежности, то есть неопределенность ключа становится близкой к 0 .

U(E) = n , где n -минимальное из тех, для которых

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

,

где избыточность исходного текста R определяется следующим соотношением:

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

H(T ) = H (K ) = | K |

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

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

(Продолжение следует )

Сергей Панасенко ,
начальник отдела разработки программного обеспечения фирмы «Анкад»,
[email protected]

Основные понятия

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

С = Ek1(M)

M" = Dk2(C),

где M (message) - открытая информация (в литературе по защите информации часто носит название "исходный текст");
C (cipher text) - полученный в результате зашифрования шифртекст (или криптограмма);
E (encryption) - функция зашифрования, выполняющая криптографические преобразования над исходным текстом;
k1 (key) - параметр функции E, называемый ключом зашифрования;
M" - информация, полученная в результате расшифрования;
D (decryption) - функция расшифрования, выполняющая обратные зашифрованию криптографические преобразования над шифртекстом;
k2 - ключ, с помощью которого выполняется расшифрование информации.

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

Для того, чтобы результат расшифрования совпал с исходным сообщением (т. е. чтобы M" = M), необходимо одновременное выполнение двух условий. Во-первых, функция расшифрования D должна соответствовать функции зашифрования E. Во-вторых, ключ расшифрования k2 должен соответствовать ключу зашифрования k1.

Если для зашифрования использовался криптостойкий алгоритм шифрования, то при отсутствии правильного ключа k2 получить M" = M невозможно. Криптостойкость - основная характеристика алгоритмов шифрования и указывает прежде всего на степень сложности получения исходного текста из зашифрованного без ключа k2.

Алгоритмы шифрования можно разделить на две категории: симметричного и асимметричного шифрования. Для первых соотношение ключей зашифрования и расшифрования определяется как k1 = k2 = k (т. е. функции E и D используют один и тот же ключ шифрования). При асимметричном шифровании ключ зашифрования k1 вычисляется по ключу k2 таким образом, что обратное преобразование невозможно, например, по формуле k1 = ak2 mod p (a и p - параметры используемого алгоритма).

Симметричное шифрование

Свою историю алгоритмы симметричного шифрования ведут с древности: именно этим способом сокрытия информации пользовался римский император Гай Юлий Цезарь в I веке до н. э., а изобретенный им алгоритм известен как "криптосистема Цезаря".

В настоящее время наиболее известен алгоритм симметричного шифрования DES (Data Encryption Standard), разработанный в 1977 г. До недавнего времени он был "стандартом США", поскольку правительство этой страны рекомендовало применять его для реализации различных систем шифрования данных. Несмотря на то, что изначально DES планировалось использовать не более 10-15 лет, попытки его замены начались только в 1997 г.

Мы не будем рассматривать DES подробно (почти во всех книгах из списка дополнительных материалов есть его подробнейшее описание), а обратимся к более современным алгоритмам шифрования. Стоит только отметить, что основная причина изменения стандарта шифрования - его относительно слабая криптостойкость, причина которой в том, что длина ключа DES составляет всего 56 значащих бит. Известно, что любой криптостойкий алгоритм можно взломать, перебрав все возможные варианты ключей шифрования (так называемый метод грубой силы - brute force attack). Легко подсчитать, что кластер из 1 млн процессоров, каждый из которых вычисляет 1 млн ключей в секунду, проверит 256 вариантов ключей DES почти за 20 ч. А поскольку по нынешним меркам такие вычислительные мощности вполне реальны, ясно, что 56-бит ключ слишком короток и алгоритм DES необходимо заменить на более "сильный".

Сегодня все шире используются два современных криптостойких алгоритма шифрования: отечественный стандарт ГОСТ 28147-89 и новый криптостандарт США - AES (Advanced Encryption Standard).

Стандарт ГОСТ 28147-89

Алгоритм, определяемый ГОСТ 28147-89 (рис. 1), имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - "исключающее или"), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз ("раундов"): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.

Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.

Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.

Табличные замены (Substitution box - S-box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция. В таблицу записываются выходные значения блоков. Блок данных определенной размерности (в нашем случае - 4-бит) имеет свое числовое представление, которое определяет номер выходного значения. Например, если S-box имеет вид 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 и на вход пришел 4-бит блок "0100" (значение 4), то, согласно таблице, выходное значение будет равно 15, т. е. "1111" (0 а 4, 1 а 11, 2 а 2 ...).

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

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

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;

K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.

Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:

K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.

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

В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 (см. рис. 1).

1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.

2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.

3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.

4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.

5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).

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

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

Зашифрование и расшифрование в режиме гаммирования

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

В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка - такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.

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

Рис. 2. Выработка гаммы шифра в режиме гаммирования с обратной связью.

Рассматривая режим генерации имитоприставок , следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-бит блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.

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

Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод "грубой силы". Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).

Стандарт AES

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

Конкурс на замену DES был объявлен в 1997 г. Национальным институтом стандартов и технологий США (NIST - National Institute of Standards and Technology). На конкурс было представлено 15 алгоритмов-претендентов, разработанных как известными в области криптографии организациями (RSA Security, Counterpane и т. д.), так и частными лицами. Итоги конкурса были подведены в октябре 2000 г.: победителем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen).

Алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, структура которых носит название "сеть Фейстеля" и аналогична российскому ГОСТ 28147-89. Особенность сети Фейстеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (см. рис. 1).

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

Алгоритм Rijndael выполняет четыре преобразования: BS (ByteSub) - табличная замена каждого байта массива (рис. 3); SR (ShiftRow) - сдвиг строк массива (рис. 4). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта. Далее идет MC (MixColumn) - операция над независимыми столбцами массива (рис. 5), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x). И, наконец, AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 6).
Рис. 3. Операция BS.

Рис. 4. Операция SR.

Рис. 5. Операция MC.

Количество раундов шифрования (R) в алгоритме Rijndael переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Расшифрование выполняется с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для MC - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию: c(x) * d(x) = 1. Добавление ключа AK является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.

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

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

Асимметричное шифрование

Алгоритмы асимметричного шифрования, как уже отмечалось, используют два ключа: k1 - ключ зашифрования, или открытый, и k2 - ключ расшифрования, или секретный. Открытый ключ вычисляется из секретного: k1 = f(k2).

Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению, функция y = f(x) является однонаправленной, если: ее легко вычислить для всех возможных вариантов x и для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x).

Примером однонаправленной функции может служить умножение двух больших чисел: N = P*Q. Само по себе такое умножение - простая операция. Однако обратная функция (разложение N на два больших множителя), называемая факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу. Например, разложение на множители N размерностью 664 бит при P ? Q потребует выполнения примерно 1023 операций, а для обратного вычисления х для модульной экспоненты y = ax mod p при известных a, p и y (при такой же размерности a и p) нужно выполнить примерно 1026 операций. Последний из приведенных примеров носит название - "Проблема дискретного логарифма" (DLP - Discrete Logarithm Problem), и такого рода функции часто используются в алгоритмах асимметричного шифрования, а также в алгоритмах, используемых для создания электронной цифровой подписи.

Еще один важный класс функций, используемых в асимметричном шифровании, - однонаправленные функции с потайным ходом. Их определение гласит, что функция является однонаправленной с потайным ходом, если она является однонаправленной и существует возможность эффективного вычисления обратной функции x = f-1(y), т. е. если известен "потайной ход" (некое секретное число, в применении к алгоритмам асимметричного шифрования - значение секретного ключа).

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

Алгоритм RSA

Разработанный в 1978 г. тремя авторами (Rivest, Shamir, Adleman), он получил свое название по первым буквам фамилий разработчиков. Надежность алгоритма основывается на сложности факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA - модуль системы N, по которому проводятся все вычисления в системе, а N = P*Q (P и Q - секретные случайные простые большие числа, обычно одинаковой размерности).

Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям:

1

где НОД - наибольший общий делитель, т. е. k1 должен быть взаимно простым со значением функции Эйлера F(N), причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (P - 1)*(Q - 1) .

Открытый ключ k1 вычисляется из соотношения (k2*k1) = 1 mod F(N) , и для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифрование блока данных M по алгоритму RSA выполняется следующим образом: C = M[в степени k1] mod N . Заметим, что, поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление M[в степени k1] нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов.

Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и k1. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров P и Q. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.

Какое шифрование лучше?

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

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

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

Дополнительные источники информации

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

  1. Брассар Ж. "Современная криптология".
  2. Петров А. А. "Компьютерная безопасность: криптографические методы защиты".
  3. Романец Ю. В., Тимофеев П. А., Шаньгин В. Ф. "Защита информации в современных компьютерных системах".
  4. Соколов А. В., Шаньгин В. Ф. "Защита информации в распределенных корпоративных сетях и системах".

Полное описание алгоритмов шифрования можно найти в следующих документах:

  1. ГОСТ 28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. - М.: Госстандарт СССР, 1989.
  2. Алгоритм AES: http://www.nist.gov/ae .
  3. Алгоритм RSA: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1 .


 
Статьи по теме:
Создание MIDI мелодии в программе Anvil Studio Hover-эффекты для изображений на чистом CSS3 Выезжающая иконка как на CoolWebMasters Варианты переноса строк Как перейти на строчку ниже на клавиатуре Надоела стандартная раскладка клавиш? Приложения для Android: обучающие программы для детей
Новое:
Power bi отчет с 1с. BI - системы. Критерии для...
Почему не работают USB порты на компьютере?
Как Zello рация для Андроид помогает водителям
Рейтинг производительности процессоров от «Интел
Что такое Информационные технологии (IT или ИТ)?
Панорама Джексон (Вайоминг)
Популярное:
Battle Carnival не запускается
Телефон Lenovo не включается
 Лучшие бесплатные программы для чтения PDF...
Номера телефонов сотовых операторов россии по...
Гугл плюс — регистрация, вход в аккаунт Google...
Делаем качественное охлаждение процессора Кулер...