Алгоритм шифрования RSA

Алгоритм шифрования RSA на пальцах.

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

Криптосистема с открытым ключом.

В криптосистеме с открытым ключом, в отличие от симметричной, используются два ключа: открытый и закрытый (закрытый хранится в секрете). Открытый ключ используется для проверки ЭЦП и для шифрования сообщений. Закрытый ключ – для генерации ЭЦП и для расшифрования сообщений.

Для тех, кто забыл, напомним:
ЭЦП – (Электронная цифровая подпись) – атрибут электронного документа, который получается в результате некоторого криптографического преобразования данных. ЭЦП позволяет проверить целостность документов, конфиденциальность документов, а так же идентифицировать владельца документа. Аналог обычной подписи.

Алгоритм шифрования RSA

Стоит отметить, в основе криптографических систем с открытым ключом лежат односторонние функции – такие функции, которые обладают следующими свойствами:

    1. Пусть известно значение x, тогда вычислить F(x) относительно просто.
    2. Пусть известно y=F(x), однако вычислить x сложно.

Не стоит понимать под этим определением теоретическую однонаправленность, здесь имеется ввиду, что практически невозможно вычислить обратное значение функции за разумное время.
Необходимо понимать, что криптосистемы с открытым ключом не заменяют симметричные криптосистемы, это связано с тем, что:

    1. Скорость работы алгоритмов с открытым ключом намного ниже, чем скорость работы симметричных алгоритмов. Поэтому ассиметричные шифры используются для шифрования небольших по размеру данных, например, ключей.
    2. Длина ключей значительно больше, чем в симметричных криптосистемах.

Конечно, есть и плюсы, например:

    1. Удобное распределение открытых ключей, не требует секретности.
    2. В больших сетях число ключей значительно меньше, чем в симметричной криптосистеме.

А теперь перейдем к конкретному примеру ассиметричного шифрования – RSA.

Описание алгоритма RSA.

Описание может быть не очень понятным и нудным, наберитесь терпения, когда мы дойдем до примера, все встанет на свои места 🙂

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

В RSA открытый и закрытый ключ состоит из пары целых чисел. Закрытый ключ хранится в секрете, а открытый ключ сообщается другому участнику, либо где-то публикуется.

На словах понять тяжело, поэтому предлагаю разобрать все по частям.

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

Всё начинается с генерации ключевой пары (открытый, закрытый ключ). Генерация ключей в RSA осуществляется следующим образом:

    1. Выбираются два простых числа p и q (такие что p неравно q).
    2. Вычисляется модуль N=p*q.
    3. Вычисляется значение функции Эйлера от модуля N: \phi(N) = (p-1)(q-1).
    4. Выбирается число e, называемое открытой экспонентой, число e должно лежать в интервале
    1<e<\phi(N), а так же быть взаимно простым со значением функции \phi(N). 5. Вычисляется число d, называемое секретной экспонентой, такое, что d*e=1(mod\phi(N)), то есть является мультипликативно обратное к числу e по модулю \phi(N).

Итак, мы получили пару ключей:

    Пара (e,N) - открытый ключ.
    Пара (d,N) - закрытый ключ.

Если вам нужно сгенерировать пару, используйте OpenSSL:

А теперь переходим к шифрованию и расшифрованию.

Шифрование и расшифровывание в RSA

Есть следующий сценарий: Боб и Алиса переписываются в интернете, но хотят использовать шифрование, чтобы поддерживать переписку в секрете :). Алиса заранее сгенерировала закрытый и открытый ключ, а затем отправила открытый ключ Бобу. Боб хочет послать зашифрованное сообщение Алисе:

Шифрование: Боб шифрует сообщение m, используя открытый ключ Алисы (e,N) : C=E(M)=M^e mod(N), и отправляет с Алисе.

Расшифровывание: Алиса принимает зашифрованное сообщение c. Используя закрытый ключ (d,N), расшифровывает сообщение M=D(C)=C^d mod(N)

Проиллюстрируем то, что описано выше:

Алгоритм шифрования RSA

Безопасность схемы RSA

От каких параметров зависит стойкость алгоритма RSA? Представим себе, что к Бобу и Алисе присоединяется Ева, которая хочет узнать, какое сообщение послал Боб. Допустим, что у Евы есть открытый ключ Алисы (e,N), для того, чтобы расшифровать сообщение c, необходимо знать закрытый ключ (d,N). Мы знаем, что d*e=1(mod\phi(N)), однако Ева не знает \phi(N)=(p-1)*(q-1), т.е задача сводится к нахождению простых чисел p и q (хотя это не всегда так), которые связаны с известным N следующим образом N=p*q.

Делаем выводы. Чтобы алгоритм был стойким, необходимо:

    1. Выбрать два больших простых случайных числа p и q (к примеру, >= 1024 бита каждое), должны быть не слишком различными и быть не слишком близкими
    2. Наибольший общий делитель (p-1) и (q-1) должен быть небольшим, в лучшем случае равен двум.
    3. Выбрать большое значение открытой экспоненты e, как правило, выбирают простые числа Ферма: 17, 257, 65537...
    4. Сохранение в секрете закрытого ключа.

Ниже («Почему RSA не так прост?») я покажу, что эти условия необходимые, но не достаточные. Для стойкости шифра RSA необходимы еще некоторые условия.

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

Пример шифрования RSA

Поехали!

    1. Выбираем простые числа (небольшие, чтобы упростить вычисления) : p=3 и q=11
    2. Вычисляем модуль n=p*q=3*11=33
    3. Вычисляем функцию Эйлера от модуля N : \phi(N)=(p-1)*(q-1)=2*10=20.
    4. Выбираем открытую экспоненту e = 7
    5. Определяем закрытую экспоненту d : d*e?1(mod\phi(N)) => d=3

Будем шифровать сообщение RSA, пусть букве A соответствует цифра 1, B - 2, C - 3 и т.д (Подобное соответствие вносим для простоты), тогда :

R = 18; S = 19; A = 1;

Открытый ключ : (e,N)=(7,33)

C_1 = (18^7)mod33 = 6
C_2 = (19^7)mod33 = 13
C_3 = (1^7)mod33 = 1

C(

Передача шифртекста происходит в формате hex:

То есть передается строка вида "0x6 0xd 0x1"

Иллюстрация примера:

Алгоритм шифрования RSA

Пример расшифрования RSA

На стороне получателя строка "0x6 0xd 0x1" декодируется:

Используем закрытый ключ : (d,N)=(3,33)

M_1 = (6^3)mod33 = 18
M_2 = (13^3)mod33 = 19
M_3 = (1^3)mod33 = 1

18 = R; 19 = S; 1 = A;

Получаем исходное сообщение - RSA. Иллюстрировать не будем, и так все понятно 🙂

Почему RSA не так прост?

В статье я описал наиболее простую форму RSA, вроде все просто, однако использовать такой алгоритм нельзя. Почему нельзя? Необходимо проверить, удовлетворяет ли данный алгоритм требованиям к ассиметричным криптосистемам.

Условие 1.
Ассиметричный алгоритм шифрования является стойким, если атакующий имеет два открытых текста M_1 и M_2, а так же зашифрованный текст C_i, не может с вероятностью большей, чем \frac{1}{2} определить к какому из сообщений M_1 или M_2 относится C_i

Проверка условия 1.
Перейдем к RSA и проверим условие 1. Вспомним ситуацию с Алисой и Бобом, допустим, канал связи прослушивает Ева. Боб спрашивает у Алисы: «Алиса, мы идем сегодня в кино», причем сообщение не шифруется. Алиса отвечает Бобу, но не хочет, чтобы кто-то знал, поэтому шифрует свой ответ на открытом ключе Боба и отправляет шифротекст Бобу. (Предполагается, что Алиса отвечает Бобу монотонно). Ева перехватывает зашифрованное сообщение и знает, что Алиса ответила либо «Да», либо «Нет». Ева располагает открытым ключом Боба, поэтому последовательно шифрует сообщение «Да» и «Нет», соответственно одно из них совпадет с зашифрованным сообщением Алисы и Ева узнает, пойдет ли Алиса сегодня в кино или нет 🙂

Алгоритм шифрования RSA

Из этого видно, что упрощенное описание алгоритма RSA не годится для практического использования. Как решается данная проблема на практике? Решается эта проблема достаточно просто: к сообщению добавляется некоторая случайная величина, а затем полученный текст шифруется. Таким образом, если Ева перехватывает сообщение C_1=E(ДаA1B2, то зашифровав «Да» и «Нет»: C_2=E(Нет, C_3=E(Да, будет видно, что C_1, C_2 и C_3 не совпадут.

Алгоритм шифрования RSA

Итак, в алгоритме RSA перед тем как зашифровать сообщение, к тексту добавляется некоторая случайная величина, а затем текст проходит процедуру шифрования. Поэтому функция шифрования принимает вид :

C=(M||random)^e mod (N), вместо C=M^e mod(N)

Условие 2.

Допустим, у Евы есть две функции, одна F_1 шифрует сообщения, вторая F_2 расшифровывает шифротекст. Затем Ева генерирует два сообщения M_1 и M_2. Затем наугад одно из сообщений шифруется функцией F_1, на выходе функции - шифротекст C_i. C_i возвращается Еве, её задача угадать с вероятностью большей, чем \frac{1}{2} к какому из сообщений M_1 или M_2 принадлежит C_i. При этом Ева может расшифровать любое сообщение, кроме C_i (иначе задача лишена смысла). Считается, что криптосистема с открытым ключом стойкая, если злоумышленник не может с вероятностью большей, чем \frac{1}{2} сказать какому из сообщений соответствует шифротекст.

Алгоритм шифрования RSA

Проверка условия 2.

Перейдем к RSA и проверим условие 2. Пусть у Евы есть два открытых сообщения M_1 и M_2 и один шифротекст C_i=M_1^e mod(N). Что делает Ева? Она создает сообщение, используя открытый ключ (e,N) : C^*=2^e C_i mod(N), затем используя функцию F_2 расшифровыает это сообщение, таким образом M^*=C^{*d} mod(N) = 2^{ed}*M_1^{ed}mod(N) = 2 M_1 mod(N), вычисляя \frac{M^*}{2} Ева получит сообщение M_1.

Вышесказанное еще раз показывает, что использовать на практике упрощенный алгоритм RSA нельзя. Решается это проблема почти так же как и в случае с условием1, напомню, что в условии1 мы добавляли к сообщению абсолютно случайную и непрогнозируемую информацию, а затем шифровали текст. Теперь накладывам еще одно требование: необходимо, чтобы дополнительные блоки помогали определить, был ли шифротекст получен в результате шифрующей функции или он смоделирован злоумышленником. Для проверки расшифрованных данных на подлинность используются всем известные хеш-функции.

Такая схема в шифровании RSA называется RSA-OAEP(Optimal asymmetric encryption padding), рассмотрим подробнее OAEP на примере.

RSA-OAEP

Шифрование:
Для того чтобы зашифровать текст в RSA-OAEP делается следующее:

    1. Выбираются две хеш-функции H(x) и G(x), такие, что суммарная длина результаов хеш-функии не была больше длины ключа RSA.
    2. Генерируется строка битов L. Причем последовательность должна быть случайной, а длина не должна превышать длину результата хеш-функции H(x).
    3. Открытый текст M разбивается на блоки по k-бит. Каждому блоку mi дописывается (p-k) нулей, где число p - длина хеш- функции G(x).
    4. Определяется набор бит (m||0^{(p-k)} \oplus G(L))||(L \oplus H(p||0^{(p-k)} \oplus G(L))
    5. Биты, полученные на шаге 4, представляются в виде целого числа M_1
    6. Определяется шифротектс : C=M_1^e mod(N)

Расшифрование:

Для того, что бы расшифровать сообщение делается следующее:

    1. Определяется M_1 : M_1=C^d mod(N)
    2. В полученной последовательности бит отсекают левую часть (p левых бит числа M_1, p - длина хеш функции G(x). Пусть эти биты T : T=(m||0^{(N-k)} \oplus G(L))
    3. Определяется H(T)=H(m||0^{(N-k)} \oplus G(L))
    4. Исходя из того, что известно H(T), т.к. знаем L \oplus H(T) (правая часть блока), получаем L.
    5. Находим m, из условия, что T \oplus G(L), а T в свою очередь : T=(m||0^{(N-k)} \oplus G(L))
    6. На этом шаге необходимо проверить полученное m, если оно заканчивается (p-k)-нулями, то сообщение зашифровано верно, иначе шифротекст некорректен, то есть оно подделано злоумышленником

Выводы

Если вы дочитали эту статью до конца, то вы большой молодец :). Что мы вынесли из всего этого.

  • Познакомились с криптосистемой с открытым ключом.
  • Узнали что такое ЭЦП.
  • Познакомились с алгоритмом RSA.
  • Узнали, как генерируются ключи в RSA.
  • Как происходит шифрование в RSA.
  • Разобрали конкретные примеры.
  • Узнали о «подводных камнях» упрощенного алгоритма RSA.

Я надеюсь, что данный материал был не только полезен, но и интересен :). А чтобы прокачать свой скилл еще больше предлагаю ознакомиться с материалом, который представлен ниже.

Литература и источники

  • «Методы дискретной математики в криптологии» - В.М. Фомичев.
  • «Прикладная криптография» - Б. Шнайер.
  • «Основы криптографии» - А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин
  • «Optimal asymmetric encryption» M. Bellare and P. Rogaway
  • «Digital signatures with RSA and other public-key cryptosystems» D. E. Denning