Криптосистема без передачи ключей
Пусть абоненты A,B,C, . . . условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно большое простое число p такое, что p − 1 хорошо разлагается на не очень большие простые множители. Затем каждый из абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с p − 1. Пусть число абонента A — a, абонента B — b и т.д.
Числа a, b, . . . составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи (α для A, для B и т. д.) находятся из уравнений: для A из aα ≡ 1 (mod φ(p)), 0 < α < p−1; для B — из b ≡ 1 (mod φ(p)), 0 < β < p − 1 и т.д. Пересылаемые сообщения, коды-числа, должны быть меньше p−1. В случае, когда сообщение больше или равно p−1, оно разбивается на части таким образом, чтобы каждая часть была числом, меньшим p − 1.
Предположим абонент A решил отправить сообщение m (m < p−1) B. Для этого он сначала зашифровывает свое сообщение ключом a, получая по формуле m1 ≡ ma (mod p) шифрованное сообщение m1, которое отправляется B. B, получив m1, зашифровывает его своим ключом b, получая по формуле m2 ≡ mb 1 (mod p) шифрованное сообщение m2, которое отправляется обратно к A. A шифрует полученное сообщение ключом a по формуле m3 ≡ m2α (mod p) и окончательно отправляет m3 к B. B, используя ключ , сможет теперь расшифровать исходное сообщение m. Действительно, m4 ≡ m 3 ≡ maαb β ≡ m (mod p), т. к. aαb β ≡ 1 (mod φ(p)), следовательно, aαb β = kφ(p) + 1 для некоторого целого k и mkφ(p)+1 ≡ (mφ(p))km ≡ m (mod p), т. к. mφ(p) ≡ 1(mod p) по теореме Эйлера-Ферма.
Пример. Абоненты A и B вместе выбрали p = 23 (φ(23) = 22), A выбрал a = 5, а B — b = 7. Затем из уравнения 5α ≡ 1 (mod φ(23)) A находит α = 9, а B из подобного уравнения находит = 19. При передаче сообщения m = 17 от A к B сначала A отправляет к B m1 ≡ 175 ≡ 21 (mod 23), из m1 = 21 B вычисляет m2 ≡ 217 ≡ 10 (mod 23) и отправляет его обратно A, из m2 = 10 A вычисляет для B m3 ≡ 109≡ 20 (mod 23), наконец, B может прочитать посланное ему сообщение 2019 ≡ 17 (mod 23).
Криптосистема с открытым ключом
Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA.
Пусть абоненты A и B решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа (pA1 , pA2 и pB1 , pB2 ), находит их произведение (rA и rB), функцию Эйлера от этого произведения (φ(rA) и φ(rB)) и случайное число (a и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, A из уравнения aα≡ 1 (mod φ(rA)) находит α (0 < α < φ(rA)), а B из уравнения bβ ≡ 1 (mod φ(rB)) находит (0 < β < φ(rB)). Затем A и B печатают доступную всем книгу паролей вида:
A: rA, a
B: rB, b
Теперь кто-угодно может отправлять конфиденциальные сообщения A или B. Например, если пользователь книги паролей хочет отправить сообщение m для B (m должно быть меньшим rB, или делиться на куски, меньшие rB), то он использует ключ b из книги паролей для получения шифрованного сообщения m1 по формуле m1 ≡ mb(mod rB), которое и отправляется B. B для дешифровки m1 использует ключ в формуле m 1 ≡ mb ≡ m (mod rB), т. к. b ≡ 1(mod φ(rB)), следовательно, b = kφ(rB)+1 для некоторого целого k и mkφ(rB)+1 ≡ (m'(rB))km ≡ m (mod rB), т.к. mφ(rB) ≡ 1 (mod rB) по теореме Эйлера-Ферма. Доказано, что задача нахождения секретного ключа по данным из книги паролей имеет ту же сложность, что и задача разложения числа rB на простые множители.
Пример. Пусть для A pA1 = 7 и pA2 = 23, тогда rA = pA1pA2 = 161, φ(161) = 6 * 22 = 132, α = 7, α = 19 (из уравнения 7α ≡ 1 (mod 132)).
Следовательно, запись в книге паролей для A будет иметь вид A: 161, 7. Если кто-то захочет отправить A секретное сообщение m = 3, то он должен сначала превратить его в шифровку m1 по формуле m1 ≡ 37 ≡94 (mod 161). Когда A получит m1 = 94 он дешифрует его по формуле m ≡ 9419 ≡ 3 (mod 161).
Электронная подпись
Криптосистема с открытым ключом открыта для посылки сообщений для абонентов из книги паролей для любого желающего. В системе с электронной подписью сообщение необходимо “подписывать”, т.е. явно указывать на отправителя из книги паролей.
Пусть W1,W2, . . . ,Wn — абоненты системы с электронной подписью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно так же как и в системе с открытым ключом. Пусть i-ый абонент (1 ≠ i ≤ n) выбирает два больших простых числа pi1 и pi2, затем вычисляет их произведение — ri = pi1pi2 и функцию Эйлера от него — φ(ri), затем выбирает первый ключ ai из условий 0 < ai < φ(ri), НОД (ai, φ(ri)) = 1 и, наконец, вычисляет второй ключ αi из уравнения aiαi ≡ 1 (mod φ(ri)). Записи в книге паролей будут иметь вид:
W1: r1, a1
W2: r2, a2
· · ·
Wn: rn, an
Если абонент W1 решает отправить секретное письмо m W2, то ему следует проделать следующую последовательность операций:
1) Если m > min(r1, r2), то m разбивается на части, каждая из которых меньше меньшего из чисел r1 и r2;
2) Если r1 < r2, то сообщение m сначала шифруется ключом α1 (m1 ≡ mα1 (mod r1)), а затем — ключом a2 (m2 ≡ maα22 (mod r2)), если же r1 > r2, то сообщение m сначала шифруется ключом a2 (m1 ≡ mα2 (mod r2)), а затем — ключом α1 (m2 ≡ mα11 (mod r1));
3) Шифрованное сообщение m2 отправляется W2.
W2 для дешифровки сообщения m2 должен знать, кто его отправил, поэтому к m2 должна быть добавлена электронная подпись, указывающая на W1. Если r1 < r2, то для расшифровки m2 сначала применяется ключ α2, а затем — a1, если же r1 > r2, то для расшифровки m2 сначала применяется ключ a1, а затем — α2. Рассмотрим случай r1 < r2 : mα22 ≡ mα2a21 ≡ m1 (mod r2) и mα11 ≡ mα1a11 ≡ m (mod r1) по теореме Эйлера-Ферма.
Пример. Пусть W1 выбрал и вычислил следующие числа p11 =7, p12 = 13, r1 = p11p12 = 91, φ(91) = 72, a1 = 5, α1 = 29, а W2 — следующие p21 = 11, p22 = 23, r2 = 253, φ(253) = 220, a2 = 31, α2 = 71. После занесения записей о W1 и W2 в открытую книгу паролей, W2 решает послать сообщение m = 41 для W1. Т.к. r2 > r1, то сообщение сначала шифруется ключом a1, а затем ключом α2 : m1 ≡ 415 ≡ 6 (mod 91), m2 ≡ 671 ≡ 94 (mod 253). Сообщение m2 отправляется W1. Получив m2 = 94, W1, зная, что оно пришло от W2, дешифрует его сначала ключом a2, а затем ключом a1 : 9431 (mod 253) ≡ 6, 629 (mod 91) ≡ 41.
Если подписать сообщение открытым образом, например, именем отправителя, то такая “подпись” будет ничем не защищена от подделки. Защита электронной подписи обычно реализуется с использованием таких же методов, что в криптосистеме с открытым ключом.
Электронная подпись генерируется отправителем по передаваемому сообщению и секретному ключу. Получатель сообщения может проверить его аутентичность по прилагаемой к нему электронной подписи и открытому ключу отправителя.
Стандартные системы электронной подписи считаются настолько надежными, что электронная подпись юридически приравнена к рукописной. Электронная подпись часто используется с открытыми, незашифрованными электронными документами.