Алгоритм шифрования 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

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

      1. я тоже не понял.
        Определяем закрытую экспоненту dd : d∗e=1(modϕ(N))d∗e=1(modϕ(N)) =>=> d=3

        Что из чего следует непонятно.

        n то большая, то маленькая в статье и видимо перепутано.

        1. Поправили, где N маленькая 🙂 Везде теперь обозначается одинаково, спасибо!

          Для того, чтобы понять как находить d, стоит обратить внимание на расширенный алгоритма Евклида. Для вычисления используется формула d=e^(-1)mod(phi(n)), не забывайте что e^(-1) - не дробь, а обратный элемент по модулю. Найти обратный элемент можно как раз с помощью расширенного алгоритма Евклида

        2. Fi(n) = 20 - функция Эйлера от простых p=3, q=11.
          Далее выбрали открытую эксп e=7 (простое)
          d*e = 1(mod(20))
          d*7= 1 (mod(20)) => d=3. Так как 3*7=1 mod(20)

  1. Объясните мне вот что.
    А Алисы есть ЗАКРЫТЫЙ+ОТКРЫТЫЙ ключи.
    А у боба есть только ОТКРЫТЫЙ который так же принадлежит Алисе.
    Это говорит о том что зашифрованные сообщения может слать Боб -> Алисе!
    А если Алисе надо будет послать сообщения, то теперь боб делает свой закрытый ключ и открытый ключ. И посылает Алисе открытый, верно?

    Как интересно это работает в https. Там что и сервер и клиент генерирует каждый свой закрытый и открытый ключ?

    1. Да, все верно.

      В HTTPS используются протокол SSL/TLS и дело обстоит немного иначе, там используется асимметричная и симметричная криптография. Для выработки общего секрета используется алгоритма Диффи-Хеллмана. Может необходимо описать подробнее этот вопрос?

    2. У меня вопрос такой. Для выполнения Условия 1 к сообщению Да добавляется случайная строка "А1В2". Это сообщение отправляется Алисой Бобу. Но как Боб узнает, что эта строка не является осмысленной и ее нужно отбросить? У них в распоряжении ведь только публичные ключи друг друга, следовательно эта строка является информацией, которую должны знать они оба, причем только они. А в текущих условиях они владеют той же информацией друг о друге, что и Ева.

      1. Это лишь пример, он был описан для подготовки читателя к RSA-OAEP 🙂

        Конечно такой пример не стоит использовать на практике. Однако можно заранее договориться добавлять к сообщению количество бит/байт, которые необходимо отбрасывать, например (count||M||random), но опять возникают проблемы (Что если о.т - число?). Поэтому используйте RSA-OAEP 🙂

  2. Однозначно нужно!) Статья очень интересная, хотелось бы более развернутого продолжения.

  3. Добрый день!
    Вопрос такой: как на стадии дешифрования отличить одну последовательность от другой. В разобранном примере (6131) были дешифрованы 6, 13, 1. Как отличить эту последовательность, скажем, от 6, 1, 3, 1 или от 6, 1, 31?
    Спасибо.

  4. Добрый день!
    Вопрос о дешифровании. В разобранном примере последовательность 6131 мы разбили на 6, 13, 1. Почему не на 6, 1, 3, 1 или 6, 1, 31? Как в этом разобраться?
    Спасибо.

  5. При расшифровке, откуда мы знаем что надо брать 6 13 1, а не, например, 61 3 1 или 6 1 31.

    1. Передача производится в hex:
      >>> hex(6), hex(13), hex(1)
      ('0x6', '0xd', '0x1')

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

      >>> int("0x6", 16), int("0xd", 16), int("0x1", 16)
      (6, 13, 1).

      Спасибо за замечание, добавили в статью 🙂

      1. Здравствуйте! Статья замечательная, но я все же не могу понять один аспект, касающийся передачи в hex..

        Как мы можем передавать именно "0x6 0xd 0x1" (те как Вы говорите, если я правильно понял: 6 13 1) - но ведь это же ненадежно так делать передачу. Почему мы не передали одно число, которое нужно дешифровать: 6131.(последовательность чисел) И как в этом случае быть тогда, как понять что это не 6131, и не 613 1 , а 6 13 1? Можно на почту ответить, буду очень благодарен! Спасибо!!:)

  6. Спасибо большое за статью.
    Ответьте пожалуйста на вопрос. Вы написали:

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

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

    Тут открытый и закрытый ключ состоят из двух чисел. Почему, когда я генерирую например приватный ключ с помощью openssl, получается огромная последовательность символов? Это и есть те самые два числа? А почему символами? И где разделитель между ними?

    Заранее спасибо 🙂

    1. Вы все верно заметили, openssl генерирует ключи в pem формате.
      Огромная последовательность символов - кодировка base64 (таков pem формат).
      Попробуйте выполнить следующие команды:

      #Тут генерируем открытый ключ 1024 бит
      $ openssl genrsa -out private_key.pem 1024

      #Читаем ключ, получим обертку base64
      $ cat public_key.pem
      -----BEGIN PUBLIC KEY-----
      MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDrzdvq2s8PlDscnJ7+irJfXjTT
      y17XREZXDOUu1w9RvZWxyoJFjjXctybTI+mr7gnSX5FPHVGCtZ9GADuMdakMHM4B
      jWBsShtaOY02YCO0KKGjEDBoBzNmM8LbZnxwknWNNILOaiasxBthWwmwL1O6eh1s
      t1L8bIZ2ZQtdV9wPUQIDAQAB
      -----END PUBLIC KEY-----

      #Читаем модуль N (в hex формате) и e
      $ openssl rsa -pubin -inform PEM -text -noout < public_key.pem Public-Key: (1024 bit) Modulus: 00:eb:cd:db:ea:da:cf:0f:94:3b:1c:9c:9e:fe:8a: b2:5f:5e:34:d3:cb:5e:d7:44:46:57:0c:e5:2e:d7: 0f:51:bd:95:b1:ca:82:45:8e:35:dc:b7:26:d3:23: e9:ab:ee:09:d2:5f:91:4f:1d:51:82:b5:9f:46:00: 3b:8c:75:a9:0c:1c:ce:01:8d:60:6c:4a:1b:5a:39: 8d:36:60:23:b4:28:a1:a3:10:30:68:07:33:66:33: c2:db:66:7c:70:92:75:8d:34:82:ce:6a:26:ac:c4: 1b:61:5b:09:b0:2f:53:ba:7a:1d:6c:b7:52:fc:6c: 86:76:65:0b:5d:57:dc:0f:51 Exponent: 65537 (0x10001)

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *