Электронная подпись

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

Пусть \[ W_1, W_2, \ldots, W_n \] - абоненты системы с электронной подписью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно так же как и в системе с открытым ключом. Пусть \[ i \] -ый абонент ( \[ 1\ne i\le n \] ) выбирает два больших простых числа \[ p_{i1} \] и \[ p_{i2} \] , затем вычисляет их произведение - \[ r_i=p_{i1}p_{i2} \] и функцию Эйлера от него - \[ \varphi(r_i) \] , затем выбирает первый ключ \[ a_i \] из условий \[ 0<a_i<\varphi(r_i) \] , \[ \hbox{НОД}(a_i, \varphi(r_i))=1 \] и, наконец, вычисляет второй ключ \[ \alpha_i \] из уравнения \[ a_i\alpha_i\equiv 1\pmod{\varphi(r_i)} \] . Записи в книге паролей будут иметь вид:

Если абонент \[ W_1 \] решает отправить секретное письмо \[ m \] \[ W_2 \] , то ему следует проделать следующую последовательность операций:

1. Если \[ m>\min(r_1,r_2) \] , то \[ m \] разбивается на части, каждая из которых меньше меньшего из чисел \[ r_1 \] и \[ r_2 \] ;
2. Если \[ r_1<r_2 \] , то сообщение \[ m \] сначала шифруется ключом \[ \alpha_1 \] ( \[ m_1\equiv m^{\alpha_1}\pmod{r_1} \] ), а затем - ключом \[ a_2 \] ( \[ m_2\equiv m_1^{a_2}\pmod{r_2} \] ), если же \[ r_1>r_2 \] , то сообщение \[ m \] сначала шифруется ключом \[ a_2 \] ( \[ m_1\equiv m^{a_2}\pmod{r_2} \] ), а затем - ключом \[ \alpha_1 \] ( \[ m_2\equiv m_1^{\alpha_1}\pmod{r_1} \] );
3. Шифрованное сообщение \[ m_2 \] отправляется \[ W_2 \] .

\[ W_2 \] для дешифровки сообщения \[ m_2 \] должен знать, кто его отправил, поэтому к \[ m_2 \] должна быть добавлена электронная подпись, указывающая на \[ W_1 \] . Если \[ r_1<r_2 \] , то для расшифровки \[ m_2 \] сначала применяется ключ \[ \alpha_2 \] , а затем - \[ a_1 \] , если же \[ r_1>r_2 \] , то для расшифровки \[ m_2 \] сначала применяется ключ \[ a_1 \] , а затем - \[ \alpha_2 \] . Рассмотрим случай \[ r_1<r_2 \] : \[ m_2^{\alpha_2}\equiv m_1^{a_2\alpha_2}\equiv m_1\pmod{r_2} \] и \[ m_1^{a_1}\equiv m^{\alpha_1a_1}\equiv m\pmod{r_1} \] по теореме Эйлера-Ферма.

Пример. Пусть \[ W_1 \] выбрал и вычислил следующие числа \[ p_{11}=7, p_{12}=13, r_1=p_{11}p_{12}=91, \varphi(91)=72, a_1=5, \alpha_1=29 \] , а \[ W_2 \] - следующие \[ p_{21}=11, p_{22}=23, r_2=253, \varphi(253)=220, a_2=31, \alpha_2=71 \] . После занесения записей о \[ W_1 \] и \[ W_2 \] в открытую книгу паролей, \[ W_2 \] решает послать сообщение \[ m=41 \] для \[ W_1 \] . Т. к. \[ r_2>r_1 \] , то сообщение сначала шифруется ключом \[ a_1 \] , а затем ключом \[ \alpha_2 \] : \[ m_1\equiv 41^5\equiv 6\pmod{91} \] , \[ m_2\equiv 6^{71}\equiv 94\pmod{253} \] . Сообщение \[ m_2 \] отправляется \[ W_1 \] . Получив \[ m_2=94 \] , \[ W_1 \] , зная, что оно пришло от \[ W_2 \] , дешифрует его сначала ключом \[ a_2 \] , а затем ключом \[ \alpha_1 \] : \[ 94^{31}\pmod{253}\equiv 6 \] , \[ 6^{29}\pmod{91}\equiv 41 \] .

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

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

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

Стандарт шифрования данных

В 1977 году в США был предложен стандарт для шифрования данных - DES (Data Encryption Standard), разработанный в IBM. В 1980 он был одобрен ведущей мировой организацией по стандартам - ANSI. В настоящее время алгоритм DES широко используется для защиты коммерческой информации.

DES - это классическая криптосистема с открытым способом шифровки и дешифровки, секретность которой обеспечивается исключительно ключом. Основные достоинства DES:

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

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

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

Примером программы, реализующей алгоритм DES, является программа DISKREET из пакета Norton Utilities.