RSA: шифрование и расшифровка

Не забыли, какое у нас есть ценное соотношение?

• A = B^e mod n
• B = A^d mod n

Здесь есть одна трудность — посчитать x^e mod n за приемлимое время. Может быть, нам подойдёт такая вот функция?

define modpow(x, e, n) { return x^e % n; }

Наш открытый ключ — (50927, 11). Если мы захотим зашифровать сообщение «1234» (сообщение — это число), то нам потребуется посчитать значение 1234¹¹ mod 50927. Если будем считать «в лоб», то сначала надо будет определить значение 1234¹¹ — а это 10103381606301936187653160695875584. Это всего лишь 11-я степень, а в настоящей криптографии e и d — числа с десятками знаков.

К счастью, есть алгоритм побыстрее, и он в RSA играет довольно важную роль.

define modpow(x, e, n) { r = 1; while( e>0 ) { if( (e%2)==1 ) { r = (r*x) % n } e = e/2; x = (x * x) % n; } return r; }

Вот теперь — другое дело. Поехали!

n = 50927 d = 27491 e = 11 define encrypt(msg) { return modpow(msg,e,n) } define decrypt(enc) { return modpow(enc,d,n) }

Получилось! При помощи открытого ключа наше число (1234) превращается в шифр (49136), которое, в свою очередь, при помощи закрытого ключа превращается обратно в 1234. Теперь попробуем разобраться с электронной подписью.

Разделы сайта

• Моя персона
• Веб-разработка
• Мой десктоп
• IRC-канал
• Криптография
  • Кое-что о GPG
  • RSA для чайников
    • Теория
    • Делаем ключи
    • Шифрование
    • ЭЦП
    • Эпилог
• Инструменты

Поиск