RSA, а так ли все просто?

    Прелюдия


    Доброго времени суток, уважаемые читатели.
    Скорее всего, большинству из вас известно, что из себя представляет асимметричный алгоритм шифрования RSA. В самом деле, этому вопросу по всему рунету и на этом ресурсе в частности посвящено столько статей, что сказать о нем что то новое практически невозможно.
    Ну что там, ей богу, можно еще придумать и так все давным-давно понятно. Рецепт приготовления прост:
    Два простых числа P и Q.
    Перемножить до получения числа N.
    Выбрать произвольное E.
    Найти D=E-1(mod(P-1)(Q-1)).
    Для шифрования сообщение M возводим в степень E по модулю N. Для дешифрования криптотекст C в степень D по все тому же модулю N. Все криптопримитив готов. Берем и пользуемся, так? На самом деле, не так. Дело все в том, что это и в самом деле не более чем криптопримитив и в реальном мире все самую чуточку сложнее.

    Немного теории


    Для того чтобы понять почему крайне не рекомендуется использовать RSA в его наиболее простой форме сперва отметим следующее требование, выдвигаемое к асимметричным криптосистемам.
    Требование 1:
    Современная асимметричная криптосистема может(но это еще не факт) считаться стойкой, если злоумышленник, имея два открытых текста M1 и M2, а также один шифротекст Cb не может с вероятностью большей, чем 0.5 определить какому из двух открытых текстов соответствует шифротекст Cb.
    Посмотрим, удовлетворяет ли RSA данному требованию. Итак, представим, злоумышленник Мэлори прослушивает переписку Алисы и Боба. В один чудесный для себя день он видит, что Боб в открытом виде задал Алисе очень важный вопрос, знание ответа на который обогатит, ну или, по крайней мере, безмерно потешит любопытство Мэлори. Алиса односложно отвечает Бобу на этот вопрос личного характера. Она шифрует свой ответ открытым ключом Боба и отправляет шифротекст. Далее Мэлори перехватывает шифротекст и подозревает, что в нем зашифровано либо «Да», либо «Нет». Всё, что ему теперь нужно сделать для того чтобы узнать ответ Алисы это зашифровать открытым ключом Боба слово «Да» и если полученный криптотекст совпадет с перехваченным, то это означает, что Алиса ответила «Да», в противном же случает злоумышленник поймет, что ответом было «Нет».

    Как видно из этого, пускай несколько надуманного, но все же не столь и утопичного примера, RSA не столь надежна как это принято считать. Да конечно, можно сказать, что Алиса сама дура и никто ее не просил отвечать на такой серьезный для нее вопрос односложно. Так что же теперь запретить использование односложных ответов в криптографии? Конечно, нет. Все не так плохо, достаточно чтобы алгоритм добавлял к тексту некоторую случайную информацию, которую бы невозможно было предугадать и коварный Мэлори будет бессилен. Ведь, в самом деле, не сможет же он предсказать, что ответ «Да» после обработки алгоритмом превратится, например, в «Да4FE6DA54», а следовательно и зашифровать это сообщение он не сможет и нечего ему будет сравнивать с перехваченным криптотекстом.

    Таким образом, уже сейчас можно сказать, что RSA во всех своих проявлениях будь то PGP или SSL не шифрует только отправленные на вход шифрующей функции данные. Алгоритм сперва добавляет к этим данным блоки содержащие случайный набор бит. И только после этого полученный результат шифруется. Т.е. вместо привычной всем
    C=ME(mod N)
    получаем более близкую к действительности
    C=(M||Rand)E(mod N),
    где Rand случайное число.
    Такую методику называют схемами дополнения. В настоящее время использование RSA без схем дополнения является не столько плохим тоном, сколько непосредственно нарушением стандартов.

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

    Требование 2:
    Пусть злоумышленник имеет доступ к расшифровывающему «черному ящику». Т.е. любой криптотекст по просьбе злоумышленника может быть расшифрован. Далее злоумышленник создает два открытых текста M1 и M2. Один из этих текстов шифруется и полученный в результате криптотекст Cb возвращается злоумышленнику. Задача злоумышленника угадать с вероятностью большей чем 0.5 какому из сообщений M1 и M2 соответсвует криптотекст Cb. При этом он может попросить расшифровать любое сообщение, кроме Cb(в противном случае игра не имеет смысла). Говорят что криптосистема стойкая, если злоумышленник, даже в таких прекрасных для себя условиях, не сможет указать какому исходному тексту соответствует Cb с вероятностью большей 0.5.

    В свете вышесказанного посмотрим как с этим обстоят дела в RSA.
    Итак, злоумышленник имеет два сообщения M1 и M2. А также криптотекст
    Cb=M1E(mod N).
    Ему необходимо указать какому конкретно из двух текстов соответствует Cb. Для этого он может предпринять следующее. Зная открытый ключ E, он может создать сообщение
    C'=2E*Cb(mod N).
    Далее он просит расшифровывающий «черный ящик» расшифровать сообщение C'. А затем несложная арифметика ему в помощь. Имеем:
    M'=C'D(mod N)=2ED*M1ED(mod N)=2*M1(mod N).
    Т.е. вычислив M'/2 злоумышленник увидит M1. А это означает, что он поймет что в нашем примере было зашифровано сообщение M1, а следовательно мы еще раз убедились в неприемлемости использования RSA в его наивном виде на практике.

    Устранить и эту неприятность помогают схемы дополнения. Только теперь к ним выдвигается требование не только о том, чтобы дополнительная информация была абсолютно случайной и непрогнозируемой. Но так же и том, чтобы дополнительные блоки помогали определить был ли шифротекст получен в результате работы шифрующей функции или он смоделирован злоумышленником. Причем в случае, если будет обнаружено, что шифротекст смоделирован вместо расшифрованных данных атакующему будет выдано сообщение о несоответствие данных реальному криптотексту.

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

    В RSA при подписи и при шифровании данных используют две различные схемы дополнений. Схема, реализуемая для подписания документов, называется RSA-PSS(probabilistic signature scheme) или вероятностная схема подписи. Схема, используемая при шифровании – RSA-OAEP(Optimal asymmetric encryption padding) или оптимизированное асимметричное дополнение шифрования, на примере OAEP и рассмотрим как на самом деле происходит шифрование сообщений в RSA.

    RSA-OAEP


    Итак чтобы зашифровать абсолютно любое сообщение в RSA-OAEP делается следующее:
    1. Выбираются две хеш-функции G(x) и H(x) таким образом, чтобы суммарная длина результатов хеш-функций не превышала длины ключа RSA.
    2. Генерируется случайная строка битов l. Длина строки должна быть равна длине результата хеш-функции H(x).
    3. Сообщение M разбивают на блоки по k-бит. Затем к каждому полученному блоку m дописывают (n-k) нулей. Где n-длина хеш-функции G(x).
    4. Определяют следующий набор бит: {m||0(n-k)⊕G(l)}||{l⊕H(m||0(n-k)⊕G(l))}
    5. Полученные биты представляют в виде целого числа M1
    6. Криптотекст получают по формуле: C=M1E(mod N)

    Процесс дешифрования выглядит следующим образом:
    1. Находят M1 по формуле M1=CD(mod N)
    2. В полученном наборе бит отсекают левую часть. В смысле: левой частью служат n левых бит числа M1 где n-длина хеш-функции G(x). Обозначим эти биты условно T. И заметим, что T={m||0(n-k)⊕G(l)}. Все остальные биты являются правой частью.
    3. Находим H(T)=H(m||0(n-k)⊕G(l))
    4. Зная H(T) получаем l, т.к. знаем l⊕H(T)-это правая часть блока.
    5. Вычислив l, находим m из T⊕G(l) т.к. T={m||0(n-k)⊕G(l)}
    6. Если m заканчивается (n-k)-нулями значит сообщение зашифровано правильно. Если нет то это значит, что шифротекст некорректен, а следовательно он скорее всего подделан злоумышленником.

    Заключение


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

    upd: перенес в блог криптография.
    upd2:
    Литература и ссылки:
    1. Н. Фергюссон, Б. Шнайер «Практическая криптография»
    2. Н. Смарт «Криптография»
    3. Спецификация RSA-OAEP(pdf)
    Поделиться публикацией
    Комментарии 21
      +27
      Спасибо, всегда приятно видеть на хабре статьи такого уровня, а то банальные новости уже мягко говоря достали.
        +2
        ИМХО: если бы это были свои мысли или исследования, а так перепечатка с учебника или статья с другого сайта. Хоть бы источник указывали
          +4
          Б.Я. Рябко А.Н. Фионов «Криптографические методы защиты информации»
            +13
            Ну и что? Факт что ИНТЕРЕСНАЯ статья теперь есть на хабре и на русском, а не очередная новость о каком то обновлении, или что еще больше бесит какая нибудь статья про то как мне управлять своим временем, когда читать почту и когда кофе пить.
          +4
          Мягко говоря вы вводите людей в заблуждение. Потому что:

          1. В чистом виде RSA нигде не применяется, это только лишь алгоритм.
          2. Самим RSA данные не шифруют из-за его медлительности. Из ситуации выходят примерно так: генерируется случайный ключ, который шифруется rsa и результат передаётся другой стороне, а потом и данные, шифрованные этим ключом.
            –1
            Вы говорите о частном случае. Ваше замечание к статье не имеет ни какого отношения.
              +1
              Как это никакого? Комментарий не про RSA? 1й пункт не вносит некоторую ясность (корректировку)? Статья тоже говорила о частных случаях, ну и что.
              Комментарий ценен, потому что статья рассматривает одну сторону, которая действительно несколько дезинформирует, то есть, некоторые могут подумать что RSA стоит избегать.
                0
                «В чистом виде RSA ни где не применяется» — это не бред по вашему? Какая ясность? Использование RSA для шифрования ключей симметричных алгоритмов — это частный случай использования RSA и применяется он там где действительно нужна высокая скорость, например при шифровании поточных данных. Там где скорость не критична, а надежность важна RSA используется на все 100%.
                  0
                  > Там где скорость не критична, а надежность важна RSA используется на все 100%.
                  В статье же объяснили что в чистом виде когда нужна надежность используются надстройки над RSA. Этот смысл и несет фраза «В чистом виде RSA ни где не применяется». Будьте внимательнее.
                  Не то что бы «нигде», но применяться не должно.
            0
            Возможно, кому-то будет интересен оригинальный патент :)
            www.google.com/patents?id=daEsAAAAEBAJ&printsec=abstract&zoom=4&source=gbs_overview_r&cad=0#v=onepage&q&f=false
              0
              Перенесите в криптографию, кармы у вас теперь хватает
                +2
                Статья по шифрованию в 01-30 ночи. Круто, реально круто.
                  –2
                  Ну, вобще-то OAEP это «Optimal Asymmetric Encryption Padding», а не «Optimized».
                  А вобще, сколько можно мусолить RSA, его на хабре уже до дыр протерли.
                    +12
                    Мне было интересно, на мой взгляд гораздо лучше почитать про RSA, чем про айфоновские антены.
                      –3
                      Про РСА написано уже гораздо больше чем про айфоновские антенны )
                      +1
                      Спасибо, исправил.
                      –6
                      Это тока у рса такие проблемы или у алгоритма на элептических кривых тоже? :)
                        0
                        По тексту производится впечатление, что Вы говорите о не состоятельности всеми любимого RSA, в то время как miolini прав, что то, что Вы так обкакали в чистом виде не применяется. Это алгоритмическая база, причем одна из самых первых в асимметричной криптографии. Или давайте докажем что Windows 95 не состоятелен?

                        И да, давайте если мы публикуем какой-то научный труд, то укажем источники. Потому что…

                        В целом спасибо за статью, интересно. Но надо учитывать выше сказанное.
                          +5
                          Ни в коем не пытался выставить RSA в плохом свете. Просто хотел показать, что в криптографии порой учитываются даже самые невероятные ситуации. И продумывается защита от их возникновения. А также то, что даже самые сильные алгоритмы в связи с развитием криптографии, как науки, нуждаются в доработках и усовершенствованиях.
                          PS добавил источники.
                          0
                          Хорошая статья, мне помогла внести ясность (почти) про специфику современного применения. Не совсем ясно про хэш функции, к примеру в PKCS#1 эти функции постоянны или задаются в параметрах ключа или в параметрах зашифрованного сообщения?
                            0
                            Вообще в спецификации рекомендуется использовать SHA-1 или RIPEMD-160. Я так понимаю что в случае увеличения размера ключа применяется какая-то хитрая схема наподобие:
                            H(x)=SHA(<1>||x)||SHA(<2>||x)…
                            где <1> и <2> части по, например, 32 бита исходного X.
                            Вот здесь(pdf) подробно написано.

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                          Самое читаемое