(no subject)

[kastaneda]

Меня давно мучил вопрос, как работают системы шифрования с открытым ключом. Казалось бы, информации навалом, а «человеческим языком» почитать про это негде. Но сегодня утром тов. 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 — и всё «на коленке» собирается и работает как часы! :) Конечно, для серьёзных применений стоит применять нормальный криптографический софт, но понимание происходящих «под капотом» процессов всегда может пригодиться.

Comments

[fester-ua.livejournal.com]

Гм. А за ссылку действительно спасибо, вчитаемся повнимательнее.

[diggya.livejournal.com]

Грей, тут меня посетила мысль, будешь смеяться. Это переборный взлом, но очень уж избирательный - я не знаю, сколько места занимают простые числа до 2^2048, но алгоритм подбора не строится на переборке чисел в лоб.

[kastaneda]

2²⁰⁴⁸ =~ 10⁶¹⁶

[kastaneda]

Гоню.

Wikipedia: Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растет как n / ln(n).

[kastaneda]

Для 2048-битных ключей это ~10⁶¹³

оффтоп

[vadim-kataev.livejournal.com]

в каком ты редакторе html пишешь для журнала ?

Re: оффтоп

[kastaneda]

такое — только руками, увы…

[egorfine.livejournal.com]

Ты еще колупни на тему криптования по эллиптическим кривым (ECC) и тебе станет по-настоящему дурно. Я обещаю.

[mt6561.livejournal.com]

А где бы онное заботать? Дай ссылку чтоли...

[kastaneda]

Да хотя бы вот здесь, что ли. Но ECC — это шифрование; дайте мне понятное описание факторинга эллиптическими кривыми (ECM)!

[amirul.livejournal.com]

С учетом того, что описание алгоритмов на эллиптических кривых в принципе не может быть "понятным" (в смысле оно понятно только тем, кто хотя бы минимально "в теме"), то само изложение алгоритма можно найти здесь (http://en.wikipedia.org/wiki/Integer_factorization).

[kastaneda]

Спасибо.

(К сожалению, язык Шекспира я знаю на уровне «oh, shit» и «press any key», поэтому читать буду долго и нудно…)

[kastaneda]

Колупнул слегонца. Любопытно.

[mt6561.livejournal.com]

http://motofan.ru/board/index.php?showtopic=27405&st=0

Гыгыгы ;)

[kastaneda]

Ржач дикий. 2005-й год, а кто-то всерьёз решил усовершенствовать Pollard (p-1), видать, даже не посмотрев на Pollart (p+1).

[paul-z.livejournal.com]

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

Не-а... Это безусловно от того, что я тупой, но как-то не просто получается...

C = (M**e) mod n
M = (C**d) mod n

Почему это будет работать?
mod это деление по модулю? то есть выражаясь человеческим языком остаток от целочисленного деления?

А когда тогда будет работать вот это:
С**d=((M**e) mod n)**d
Что-то я не соображу как вообще возведение в степень работает для деления по модулю?

Извиняюсь за тупизну вопросов... но что-то в самом деле не могу сообразить... :-(

[kastaneda]

mod это деление по модулю? то есть выражаясь человеческим языком остаток от целочисленного деления?
Да.

Почему это будет работать?
Вот это как раз в моём посте не объясняется. У меня объясняется только практическое применение, без доказательств, что так будет работать.

Если очень вкратце: см. Малая теорема Ферма (для любого целого a и простого p будет выполняться a^p−1 mod p = 1) и то, что e×d mod (p-1)×(q–1) = 1.

[paul-z.livejournal.com]

Да... спасибо.

Хорошо, а то я уж думал, что уравнения связывающие M и C - очевидны. И никак не мог понять почему же я ничего в них не могу понять.


Теперь, с теоремой, вроде бы понятнее... Но не до конца.
Будем подумать... Какие-то идеи появляются, но пока неточные... с этими алгебраическими штучками так всегда... вроде вот оно кажется ты его уже видишь, но никак не ухватишь. :-/

[mikhailian.livejournal.com]

Если это перевести на английский, то получится классная статья для какого-нибудь крутейшего журнала. И пара сотен баксов в кошельке.

[trueblacker.livejournal.com]

Описания алгоритма RSA в той статье некорректно. Вместо Алисы и Боба должны быть Гвен и Пао-Чи.