Меня давно мучил вопрос, как работают системы шифрования с открытым ключом. Казалось бы, информации навалом, а «человеческим языком» почитать про это негде. Но сегодня утром тов. diggya подкинул ссылочку на статью, в которой доступно описывается алгоритм шифрования RSA (за что ему большое спасибо).

Для желающих могу также предложить описание своих практических экспериментов с RSA. Требуется: программа bc (которая «arbitrary precision calculator language»), процессор пошустрее и несколько минут свободного времени.

Сначала я вкратце обрисую, что в той статье, — ну, просто для того, чтобы все формулы были под рукой, окей?

Генерация ключа

1. надо случайно выбрать два простых числа p и q (и ещё мы будем использовать число n, равное p×q)
2. надо выбрать число e, такое, чтобы 1 < e < (p-1)×(q-1), и чтобы это e было взаимно простым с (p-1)×(q-1)
3. надо найти число d таким образом, чтобы (e×d-1) делилось на (p-1)×(q–1)

Вот и вся морока. Что получается в итоге:

• пара (n, e) - это открытый (public) ключ
• пара (n, d) - это закрытый (private) ключ

Держится это, как известно, «на соплях» — то есть, на том, что число n размером где-то 2²⁰⁴⁸ разложить на два сомножителя (p и q) будет весьма проблематично. Даже для всяких КГБ, ЦРУ, СБУ и ФСБ. Даже на современных компах.

Шифрование и расшифровка

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

Соотношения очень простые:

C = M^e mod n
M = C^d mod n

Правда, всё просто?

¹) Обычно никто не пытается зашифровать этим алгоритмом всё сообщение в каком-нибудь ASCII; используется метод «цифрового конверта»: при шифровке создаётся случайный ключ для какого-нибудь традиционного симметричного алгоритма шифрования (например, DES), и сам ключ шифруется по RSA. Передаётся сообщение, зашифрованное DESом, и ключ, зашифрованный RSA. Получатель декодирует при помощи RSA DESовский ключ, а тем DESовским ключом декодирует само сообщение.

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

Surprise! Точно так же, как шифрование и расшифровка² — но e и d меняются местами. А в чём же разница? Да только в том, кто пользуется каким ключом - открытым или закрытым.

²) Такая «подпись» несёт в себе всё сообщение, что (обычно) нахрен не нужно (потому как она прикладывается к открытому сообщению); обычно подписывается только хэш сообщения (это md5, sha1 или более современные и стойкие функции).

Практические занятия

Следует обратить внимание, что даже в нашем простом примере будут применяться числа такого масштаба, что с ними работать очень неудобно. Итак, возьмём в руки замечательную прогу bc и скормим ей (обычным Ctrl-C Ctrl-V, или кому как удобно) три нужные нам функции:

define gcd(a,b) {
  while( b != 0 ) { c = a%b; a = b; b = c }
  if (a<0) return -a; return a
}

define find_min_e (p, q) {
  max_e = (p-1)*(q-1)
  for( e=2; e<max_e; e++ ) if (gcd(max_e, e)==1) return e
  print "Oops... :(\n"
}

define find_min_d (p, q, e) {
  i = (p-1)*(q-1)
  for( d=1; 1; d++ ) if( ! ((e*d-1)%i) ) return d 
}

Теперь нам надо придумать «случайные» p и q. Большие числа брать не стоит, я взял (с потолка) числа 127 и 401. Кстати, не любые числа подходят (по крайней мере, из «небольших»). Набираем в нашей bc такую фигню:

p=127
q=401
n=p*q                   # здесь n=50927
e=find_min_e(p, q)      # здесь e=11
d=find_min_d(p, q, e)   # здесь d=27491

Отлично. С данными значениями p и q (и данным алгоритмом нахождения e, который вовсе не обязан быть минимальным), получается пара ключей, состоящая из открытого (50927, 11) и закрытого (50927, 27491).

Определим в нашем сеансе bc ещё несколько функций с «говорящими» названиями:

define encrypt (n, e, message) { return (message^e) % n }
define decrypt (n, d, crypted) { return (crypted^d) % n }
define sign (n, d, message) { return (message^d) % n }
define verify (n, e, signatrue) { return signatrue^e % n }

…и попробуем «вручную» что-то эдакое зашифровать, а потом расшифровать (в этом примере нашим «сообщением» будет число 1234; зелёным цветом выделено то, что нам пишет bc):

encrypt (n, e, 1234)
49136
decrypt (n, d, 49136)
1234

…а ещё попробуем что-то подписать и проверить подпись:

sign (n, d, 1234)
39890
verify (n, e, 39890)
1234

Работает?

Несмотря на тривиальность примеров, мне было довольно-таки любопытно с этим всем возиться. Как же, настоящий RSA — и всё «на коленке» собирается и работает как часы! :) Конечно, для серьёзных применений стоит применять нормальный криптографический софт, но понимание происходящих «под капотом» процессов всегда может пригодиться.