Модели шифрованиядешифрования дискретных сообщений. P.S

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

,
,

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

Голландский криптограф А. Керкхофс (1835 – 1903) предположил, что секретность шифров должна основываться только на секретности ключа, а не на секретности алгоритма шифрования, который, в конце концов, может оказаться известным противнику.

Если ключ шифрования равен ключу дешифрования, т.е.

= =,

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

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

Существуют два основных класса стойкости криптосистем:

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

Вычислительно стойкие криптосистемы, у которых стойкость к криптоанализу зависит от мощности вычислительной системы оппонента.

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

Для шифрования выбирают целое число N =p q , гдеp иq – два больших простых числа. Сообщение M представляется одним из чисел

M {2,3,...,N –1}.

Формулы, описывающие шифрование/дешифрование, имеют следующий вид:

,
,

где K – открытый ключ шифрования,k – закрытый ключ дешифрования.

Из этих двух соотношений следует равенство

,

которое в обычной арифметике выполняется, если kK = 1, а в модульной арифметике и при

kK = 1 + l (N ), (*)

где l – целое. Действительно с помощью теоремы Эйлера проверяем

,

если M иN – взаимно простые числа.

Рассмотренные соотношения указывают путь формирования ключей. Вначале выбирают очень большие случайные простые числа p иq с мало отличающимся числом разрядов так, чтобы произведение N = pq имело не менее 768 бит (по данным 2001 года). Вычиcляют функцию Эйлера

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

Равенство (*) эквивалентно

K k = 1 mod (N ),

откуда следует, что оба ключа взаимно обратные по модулю (N ).

Открытый ключ K выбирают, соблюдая необходимые условия:

K < (N ), НОД(K , (N )) = 1.

Закрытый ключ k вычисляют

k = K – 1 mod (N ),

с помощью алгоритма Евклида. Завершив подготовительные работы, открытый ключ K и модульN помещают в открытый справочник, приняв меры, гарантирующие невозможность подмены. Числаp и q хранят в секрете.

Отметим, что условие взаимной простоты чисел M и N , невыполнение которого делает невозможным декодирование, не создает серьезных ограничений. Во-первых, среди чисел меньшихN доля чисел взаимно простых сN равна (p –1)(q –1)/(pq ), т.е. неотличима от единицы, а, во-вторых, условие легко обеспечивается несущественной модификацией сообщения. Также степеньM K не должна быть меньшеN . При невыполнении этого условия криптограмма имеет вид

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

Очевидно, что в рассмотренных соотношениях числа K иk равноправны, т.е. ключи можно поменять местами, и использоватьk как открытый ключ шифрования, аK как закрытый ключ дешифрования.

Таким образом, оба ключа RSA задаются парами целых чисел: (K , N ) и (k , N ).

Когда авторы R. Rivest,A.Shamir,L. Adleman(Ривест, Шамир, Адлеман) в 1977 году предложили криптосистемуRSA, они зашифровали фразу “ItsallGreektome”, представленную в цифровой форме. Были опубликованы значенияM , K , N с указанием, что 129 десятичных разрядовN получены при умножении 64- и 65-разрядных чиселp иq . ФакторизацияN и вскрытие криптограммы были выполнены примерно за 220 дней лишь в 1994 году после предварительной теоретической подготовки. В работе принимало участие 600 добровольцев и 1600 компьютеров, объединенных в сеть с помощью Интернет.

Стойкость системы с открытым ключом, и в частности RSA, зависит от выбора ее параметров. Если выбратьlog 2 N = 200 бит, то для факторизации потребуется примерно 2,710 11 операций, что на персональном компьютере займет несколько дней. Если выбратьlog 2 N = 664 бит, то для факторизации потребуется 1210 23 операций. При скорости выполнения 10 6 операций в секунду на факторизацию уйдет несколько миллиардов лет.

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

Реализация шифраRSAотработана как в программном, так и в аппаратном варианте. ИспользуетсяRSAи для шифрования в смарт-картах. В программном варианте скорость шифрования имеет порядок 1 кбит/с, в аппаратном – 1050 кбит/с.

Сравнительно низкая скорость шифрования и дешифрования по сравнению с симметричными, блоковыми или потоковыми системами, является недостатком всех асимметричных систем шифрования, в том числе RSA.

1. Цифровая подпись

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

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

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

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

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

каждый пользователь сети, законный или незаконный, может проверить истинность цифровой подписи;

подписавший не может отказаться от сообщения, заверенного его цифровой подписью;

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

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

Существуют различные виды цифровой подписи, основанные на криптосистемах с открытым ключом. Рассмотрим реализацию ЦП на основе криптосистемы RSA.

В этом случае пользователь A , подписывающий сообщениеM , генерирует пару ключейk A ,K A и сообщает пользователям сети значенияK A иN . Далее пользовательA создает контрольную группу

,

которая и будет цифровой подписью (рис. 17). Контрольная группа приписывается к сообщению и передается вместе с ним.

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

Однако рассмотренная система выработки цифровой подписи имеет два существенных недостатка:

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

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

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

С помощью открытого ключа шифрования пользователь 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.

10.3.1. Системы шифрования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Модели криптографических систем

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

Процесс применения операции шифрования к шифротексту называется перешифровкой.

Свойства шифротекста

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

· Свойство однозначности шифрования:

· Из цепных равенств следует

(из свойства однозначности расшифрования)

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

это равенство используется для вывода формулы расстояния единственности.

· Для абсолютно надёжной криптосистемы

То есть

Использование для криптоанализа

Шеннон в статье 1949 года «Теория связи в секретных системах» показал, что для некоторого случайного шифра теоретически возможно (используя неограниченные ресурсы) найти исходный открытый текст, если известно букв шифротекста, где - энтропия ключа шифра, r - избыточность открытого текста (в том числе с учётом контрольных сумм и т. д.), N - объём используемого алфавита.

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

В целом, шифрование состоит из двух составляющих - зашифрование и расшифрование.

С помощью шифрования обеспечиваются три состояния безопасности информации:

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

· Целостность: шифрование используется для предотвращения изменения информации при передаче или хранении.

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

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

Как было сказано, шифрование состоит из двух взаимно обратных процессов: зашифрование и расшифрование. Оба этих процесса на абстрактном уровне представимы математическими функциями, к которым предъявляются определенные требования. Математически данные, используемые в шифровании, представимы в виде множеств, над которыми построены данные функции. Иными словами, пусть существуют два множества, представляющее данные - M и C; и каждая из двух функций(шифрующая и расшифровывающая) является отображением одного из этих множеств в другое.

· Шифрующая функция:

· Расшифровывающая функция:

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

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

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

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

Криптостойкость шифра

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

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

Абсолютно стойкие системы

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

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

Требования к абсолютно стойким системам шифрования:

· Ключ генерируется для каждого сообщения (каждый ключ используется один раз).

· Ключ статистически надёжен (то есть вероятности появления каждого из возможных символов равны, символы в ключевой последовательности независимы и случайны).

· Длина ключа равна или больше длины сообщения.

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

· Шифрующая система должна создаваться с исключительно глубоким знанием структуры используемого языка передачи сообщений

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

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

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) - система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.

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

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

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

На следующем ниже рисунке 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 |

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

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

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