Реализация алгоритма шифрования RSA

Сегодня мы рассмотрим алгоритм шифрования RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman).  Данный алгоритм обладает высокой криптостойкостью, а так же очень прост в реализации.

В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования за разумное время (обратной операции) необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложения числа на простые множители.

Взлом данного алгоритма займёт много времени и потребует больших вычислительных мощностей. Рассмотрим пример. Был объявлен конкурс на расшифровку строки, зашифрованной данным алгоритмом. Строка была расшифрована за 6 месяцев с применением 1600 компьютеров. Очень впечатляющие результаты надёжности алгоритма. Конечно, когда наконец-то разработают хорошие квантовые компьютеры, то подобные алгоритмы будут взламываться очень быстро, но пока мы можем спокойно использовать RSA.

Алгоритм RSA является алгоритмом ассиметричного шифрования. Любое ассиметричное шифрование предполагает наличие пары ключей, а именно открытого и закрытого. С помощью открытого ключа мы кодируем строку, с помощью закрытого производим декодирование.

Теперь рассмотрим как создаются данные ключи:

1.      Сначала мы выбираем два простых числа p и q.

2.      Затем вычисляем произведение p и q, которое называется модулем. N = p*q.

3.      Вычисляется значение функции Эйлера от числа n: 

4.      Выбирается целое число , взаимно простое со значением функции и .

5.      Выбирается число d удовлетворяющее условию e*d mod f(p,q)=1

Получаем {e,n} – открытый ключ шифрования, {d, n} – закрытый.

Рассмотрим пример реализации алгоритма на python.

Сначала определим начальные данные:

p = 3557

q = 2579

N = p*q

f = (p-1)*(q-1)

d = 6111579

e = 3

Теперь перейдём к шифрованию и дешифровке. Формула шифрования выглядит следующим образом:

y = x^e mod n, где х – цифровой код символа.

Для дешифровки применим другую формулу:

х = y^d mod n.

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

Напишем функцию шифрования:

def encode_RSA(word,e,N):

    ret = []

    for v in word:

        n = ord(v)

        ret.append(int(n**e%N))

И функцию декодирования:

def decode_RSA(word,d,N):

    ret = []

    for v in word:

        sim = v**d%N

        ret.append(unichr(sim))

    return ret

Применяется это так:

l = encode_RSA(u'cat',e,n)

print l

print decode_RSA(l ,d,n)

Результат:

[970299, 912673, 1560896]

 [u'c', u'a', u't']

В данной статье мы рассмотрели алгоритм шифрования RSA. На данный момент он обладает высокой криптоскойстью и, если вы будете обновлять ключи хотя бы раз в месяц, то можете не волноваться, что его взломают. Не стоит шифровать этим алгоритмом большие тексты, потому что время шифрования велико (особенно на python). Надеюсь, материалы этой статьи будут вам полезны.

Оригинал статьи читаем тут, а так же другие интересные и полезные статьи на моём блоге.