Материал: Щерба В.В. Криптографическая защита информации

66

Рис. 6.6. Система шифрования А5

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

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

γмi=(γмi-1+Cм)mod32, где Cм=01010101 (в шестнадцатеричной системе счисления);

γсi=(γсi-1+Cс-1)mod(32-1)+1, где Cс=01010104 (в шестнадцатеричной системе счисления).

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

Как обычно, начальный вектор инициализации процедуры в составе γм0 и γс0 выступает секретным параметром.

67

Ле к ц и я 7. СИСТЕМЫ ШИФРОВАНИЯ

СОТКРЫТЫМИ КЛЮЧАМИ

Системы шифрования с открытыми ключами или асимметричные системы шифрования появились относительно недавно. Их основу образуют так называемые однонаправленные (или односторонние) функции. Однонаправленной называется функция F: X→Y, для которой по x€X достаточно просто вычислить значение y=F(x), но обратное значение х по y€Y определить практически невозможно из-за вычислительной сложности задачи.

Криптографическая система RSA

Криптографическая система RSA была разработана в 1978 г. и в настоящее время является одной из самых распространенных систем шифрования с открытыми ключами. Свое название шифр получил в соответствии с первыми буквами фамилий авторов – Rivest, Shamir и Adleman. Напомним формальное описание шифра.

Пусть n=p·q – целое число, представленное в виде произведения двух простых чисел p и q. Пусть также М и С – блоки открытого и зашифрованого текстов, являются элементами множества натураль-

где φ(n)=(p-1)·(q-1) – значение функции Эйлера от числа n. Пусть e – открытый ключ зашифрования, d – секретный ключ

расшифрования, а n – модуль системы; секретными параметрами шифра являются: p, q, d.

Тогда правила зашифрования и расшифрования определяются

Предварительно заметим (без вывода), что для любого целого числа М и любого простого p справедливо сравнение: Мp≡M(mod p) [4] (заметим, что сравнение [4] равносильно сравнению Мp–М≡0(mod p) или М·(Мp-1-1)≡0(mod p) [5]. Поскольку p – простое число, то

справедливы следующие рассуждения. Если наибольший общий делитель (M, p)=p, то p делит М, и поэтому М≡0 (mod p), откуда сле-

68

дует [5]. Если же наибольший общий делитель (M, p)=1, то согласно малой теореме Ферма Мp-1≡1(mod p), откуда также следует [5]).

Поскольку в [2] С есть остаток от деления Me на n, перепишем выражение [2] в виде соответствующего сравнения: С≡Me(mod n).

Поскольку любое целое число сравнимо с самим собой по любому модулю, в частности: q≡q(mod n), на основании свойств сравнений

(если a≡b(mod n) и c≡d(mod n), то ac≡bd(mod n)) имеем: q·С≡q·Me(mod n) или, учитывая, что n=p·q: q·С≡q·Me(mod q·p).

На основании свойств сравнений (если ac≡bc (mod nc), то a≡b (mod n)) это сравнение можно представить в виде: С≡Me(mod p).

Вновь, на основании свойств сравнений (если a≡b (mod n), то и ak≡bk (mod n)), запишем: Сd≡Med(mod p).

Аналогично можно показать, что Сd≡Med(mod q).

Итак: Сd≡Med(mod p) и Сd≡Med(mod q) [6]

В соответствии с [1] существует такое целое r, что e·d=r(p-1)·(q-

1)+1; отсюда:

Med=Mr(p-1)•(q-1)+1=M(rp-r)(q-1)+1=(Mp)r(q-1)·M-r(q-1)+1=(Mp)r(q-1)·M-r(q-1)·M.

Поскольку любое целое число сравнимо с самим собой по любому

модулю, а Мp≡M(mod p) (см. [4]) из последнего выражения следует:

Med=(Mp)r(q-1)·M-r(q-1)·M≡Mr(q-1)·M-r(q-1)·M(mod p) =M(mod p).

И окончательно: Med≡M(mod p); аналогично можно показать, что

Med≡M(mod q).

На основании свойств сравнений (если a≡b(mod n) и c≡d(mod n), то (a+c)≡(b+d)(mod n)) эти сравнения можно записать в виде:

0≡(-Med+ M)(mod p) и 0≡(-Med+M)(mod q) [7]

На основании свойств сравнений (если a≡b(mod n) и c≡d(mod n), то (a+c)≡(b+d)(mod n)), складывая левые и правые части сравнений

[6] и [7], имеем: Cd≡M(mod p) и Cd≡M(mod q).

Отсюда следует, что p и q являются множителями числа (Cd-М). Поскольку p и q – различные простые числа, это означает, что p·q также является множителем (Cd-М). Учитывая это и то, что n=p·q, можно записать: Cd≡M(mod n). Как известно, эта запись означает, что остатки от деления Cd и M на целое n одинаковы. Но по условию M<n, т. е. само М является остатком. Отсюда, окончательно, следует, что M=Cd(mod n), что и требовалось доказать.

Можно показать, что сложность нахождения секретного ключа системы RSA определяется сложностью разложения модуля n на простые множители. В настоящее время самые большие числа вида n=p·q,

69

которые удается разложить на множители известными методами, содержат в своей записи 140 десятичных знаков. В связи с этим рекомендуется выбирать p и q в размере 100 десятичных знаков каждое.

Криптографическая система Эль-Гамаля

Криптографическая система Эль-Гамаля была предложена в 1985 г. Приведем описание шифра.

Пусть р – простое число; α – специальная константа. Пусть также М и С – блоки открытого и зашифрованного текстов, являются элементами множества натуральных чисел (0, 1,..., (р-1)).

Параметр шифра ß определяется исходя из условия:

ß=αа (mod p), [1],

где a – целое число из интервала 1<а≤(р-2), выбираемое владельцем секретного ключа.

Пусть k=(α, ß, p, a) – выбранный ключ, который состоит из открытого ключа зашифрования kз=(α, ß, p) и секретного ключа расшифрования kр=a.

Правило зашифрования на ключе kз определяется формулой:

r – случайное число (рандомизатор) из интервала 1≤r≤(р-2), выбираемое пользователем, который выполняет зашифрование открытого текста.

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

Покажем, что М=Dk(C1, C2). Для этого в выражение [4] подставим

Учитывая, что M<p (т. е. само М в выражении [5] является остат-

ком) из [5], имеем: M=C1- a·C2 (mod p)=Dk(C1, C2).

Криптографическая стойкость системы шифрования Эль-Гамаля определяется сложностью решения задачи дискретного логарифмирования элементов конечного поля (логарифмирования в пространстве модулей). Утверждается, что в настоящее время эта задача практически нереализуема для простых чисел, содержащих не менее 150 десятичных знаков. Шифр Эль-Гамаля относят к шифрам с вероятност-

70

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

Схемы применения асимметричных криптографических систем

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

пример А, получает в свое распоряжение два именных ключа: kоткрА и kзакрА. Один из ключей (kоткр) не составляет секрета, он выступает в

качестве публичного и называется открытым; второй ключ (kзакр) традиционно является секретным. Знание одного ключа практически не позволяет определить значение второго.

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

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

1. Схема отсылки пользователем А пользователю В секретного сообщения и расшифрования полученного сообщения:

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

3. Схема отсылки пользователем А пользователю В секретного сообщения с подтверждением авторства:

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