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

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

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

Шифр – совокупность заранее оговоренных способов преобразования исходного секретного сообщения с целью его защиты.

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

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

Алфавит - конечное множество используемых для кодирования информации символов. Например, русский алфавит содержит 33 буквы от А до Я. Однако этих тридцати трех знаков обычно бывает недостаточно для записи сообщений, поэтому их дополняют символом пробела, точкой, запятой и другими знаками. Алфавит арабских цифр – это символы 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 . Этот алфавит содержит 10 знаков и с его помощью можно записать любое натуральное число. Любое сообщение может быть записано также с помощью двоичного алфавита, то есть с использованием только нулей и единиц.

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

Преобразование открытого текста в криптограмму называется зашифрованием . Обратное действие называется расшифрованием . В англоязычной литературе терминам "зашифрование/ расшифрование" соответствуют термины "enciphering/deciphering" .

Ключ – информация, необходимая для шифрования и расшифрования сообщений.

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

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

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

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

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

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

3.5.3 Модели и методы шифрования\дешифрования дискретных сообщений

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

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

E = f(M,K ш), M = g(E,K д),

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

· функции f(М, К ш) и g(Е, К д) при известных аргументах вычисляются просто;

· функция g(E,?) при неизвестном ключе К д вычисляется сложно.

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

Следует различать три основных вида атак на криптосистему:

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

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

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

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

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

К ш = К д = К

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

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

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

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

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

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

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

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

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

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

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

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

,
,

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

Голландский криптограф А. Керкхофс (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выбран достаточно стойким.

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

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

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

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

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

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

Так за 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.

Сергей Панасенко ,
начальник отдела разработки программного обеспечения фирмы «Анкад»,
[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.

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

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

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

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