Алгоритм шифрования с открытым ключом RSA: история и принципы работы

Введение

Алгоритм криптографии с открытым ключом – это криптосистема. В криптосистеме с открытым ключом ключ шифрования является общедоступным и отличается от ключа дешифрования, который хранится в секрете (приватный). Пользователь RSA создает и публикует открытый ключ, основанный на двух больших простых числах, а также дополнительное значение. Сами простые числа остаются секретными. Любой может зашифровать сообщение с помощью открытого ключа, но расшифровать его может только тот, кто знает приватный ключ. Безопасность RSA основана на практической сложности факторизации произведения двух больших простых чисел – так называемой "задаче факторизации". Взлом шифрования RSA известен как "задача RSA". Вопрос о том, насколько эта задача сложна по сравнению с задачей факторизации, остаётся открытым. Нет опубликованных методов для взлома системы при использовании достаточно длинного ключа. RSA – относительно медленный алгоритм. Поэтому он редко используется для непосредственного шифрования пользовательских данных. Чаще RSA применяется для передачи сессионных ключей для симметричного шифрования, которые затем используются для массового шифрования и дешифрования.

История

Идея асимметричной криптосистемы с открытым и закрытым ключом приписывается Уитфилду Диффи и Мартину Хеллману, которые опубликовали эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. Их формулировка использовала общий секретный ключ, созданный путем возведения числа в степень по модулю простого числа. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому, что сложность факторизации в то время еще недостаточно изучалась. Более того, как и алгоритм Диффи-Хеллмана, RSA основана на модульном возведении в степень. Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предпринимали несколько попыток создать функцию, которую было бы трудно обратить. Ривест и Шамир, как специалисты в области компьютерных наук, предлагали множество потенциальных функций, а Адлеман, как математик, отвечал за выявление их уязвимостей. Они испробовали различные подходы, включая методы, основанные на задаче о рюкзаке и пермутационных полиномах. В течение некоторого времени они считали, что достижение желаемого результата невозможно из-за противоречивых требований. В апреле 1977 года они провели Пасху в доме студента и выпили значительное количество вина, после чего вернулись домой около полуночи. Ривест, не сумев заснуть, лежал на диване с учебником математики и начал размышлять об их односторонней функции. Он провел остаток ночи, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA – по первым буквам их фамилий в том же порядке, что и в их публикации. Клиффорд Кокс, английский математик, работавший в британской разведывательной организации Government Communications Headquarters (GCHQ), описал аналогичную систему во внутреннем документе в 1973 году. Однако, учитывая высокую стоимость компьютеров, необходимых для ее реализации в то время, она рассматривалась скорее как курьез, и, насколько известно, никогда не была внедрена. Его идеи и концепции оставались нераскрытыми до 1997 года из-за присвоенного им высшего уровня секретности. Kid RSA (KRSA) – это упрощенный, небезопасный шифр с открытым ключом, опубликованный в 1997 году и предназначенный для образовательных целей. Некоторые считают, что изучение Kid RSA дает понимание принципов работы RSA и других шифров с открытым ключом, подобно упрощенному DES.

The idea of an asymmetric public private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published this concept in 1976. They also introduced digital signatures and attempted to apply number theory. Their formulation used a shared secret key created from exponentiation of some number, modulo a prime number. However, they left open the problem of realizing a one way function, possibly because the difficulty of factoring was not well studied at the time. Moreover, like Diffie Hellman, RSA is based on modular exponentiation. Ron Rivest, Adi Shamir, and Leonard Adleman at the Massachusetts Institute of Technology made several attempts over the course of a year to create a function that was hard to invert. Rivest and Shamir, as computer scientists, proposed many potential functions, while Adleman, as a mathematician, was responsible for finding their weaknesses. They tried many approaches, including "knapsack based" and "permutation polynomials". For a time, they thought what they wanted to achieve was impossible due to contradictory requirements. In April 1977, they spent Passover at the house of a student and drank a good deal of wine before returning to their homes at around midnight. Rivest, unable to sleep, lay on the couch with a math textbook and started thinking about their one way function. He spent the rest of the night formalizing his idea, and he had much of the paper ready by daybreak. The algorithm is now known as RSA the initials of their surnames in same order as their paper. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), described a similar system in an internal document in 1973. However, given the relatively expensive computers needed to implement it at the time, it was considered to be mostly a curiosity and, as far as is publicly known, was never deployed. His ideas and concepts, were not revealed until 1997 due to its top secret classification. Kid RSA (KRSA) is a simplified, insecure public key cipher published in 1997, designed for educational purposes. Some people feel that learning Kid RSA gives insight into RSA and other public key ciphers, analogous to simplified DES.

Патент

20 сентября 1983 года институту MIT был выдан патент, описывающий алгоритм RSA: «Система и способ криптографической связи». Согласно аннотации к патенту, представленной DWPI: Система включает в себя канал связи, подключенный как минимум к одному терминалу с устройством кодирования, и как минимум к одному терминалу с устройством декодирования. Сообщение, подлежащее передаче, шифруется в шифротекст на кодирующем терминале путем представления сообщения в виде числа M из заранее определенного множества. Затем это число возводится в заранее определенную степень (связанную с предполагаемым получателем) и вычисляется. Остаток C получается при делении полученного числа на произведение двух заранее определенных простых чисел (связанных с предполагаемым получателем). Подробное описание алгоритма было опубликовано в августе 1977 года в колонке «Математические игры» журнала Scientific American.

Операция

Алгоритм RSA включает в себя четыре шага: генерация ключа, распространение ключа, шифрование и расшифрование. Основной принцип, лежащий в основе RSA, заключается в том, что практически возможно найти три очень больших положительных целых числа e, d и n, таких, что для всех целых чисел m (0 ≤ m < n) выражения и дают одинаковый остаток при делении на n (они сравнимы по модулю n). Однако, имея в распоряжении только e и n, найти d крайне сложно.

Целые числа n и e составляют открытый ключ, d представляет собой закрытый ключ, а m – сообщение. Возведение в степень по модулю с использованием e и d соответствует шифрованию и расшифрованию соответственно. Кроме того, поскольку эти два показателя степени могут быть поменены местами, открытый и закрытый ключи также могут быть поменены местами, что позволяет подписывать сообщения и проверять их подлинность с использованием одного и того же алгоритма.

Распределение ключей

Предположим, что Боб хочет отправить информацию Алисе. Если они решат использовать RSA, Бобу необходимо знать открытый ключ Алисы для шифрования сообщения, а Алисе – использовать свой закрытый ключ для расшифровки сообщения. Чтобы Боб мог отправлять зашифрованные сообщения, Алиса передает свой открытый ключ (n, e) Бобу по надежному, но необязательно секретному каналу. Закрытый ключ Алисы (d) никогда не передается.

Шифрование

После того, как Боб получит открытый ключ Элис, он может отправить сообщение M Элис. Для этого он сначала преобразует M (в точности, незаполненный открытый текст) в целое число m (в точности, заполненный открытый текст) такое, что 0 ≤ m < n, используя согласованный обратимый протокол, известный как схема заполнения. Затем он вычисляет шифротекст c, используя открытый ключ Элис e, в соответствии с формулой:

Это можно сделать достаточно быстро, даже для очень больших чисел, используя возведение в степень по модулю. Затем Боб передает c Алисе. Следует отметить, что по крайней мере девять значений m могут привести к одному и тому же шифротексту c, равным m, но это крайне маловероятно на практике.

Доказательство теоремы Эйлера

Хотя в оригинальной статье Ривеста, Шамира и Адлемана использовалась малая теорема Ферма для объяснения принципа работы RSA, часто встречаются доказательства, основанные на теореме Эйлера. Мы хотим показать, что m^(ed) ≡ m (mod n), где n = pq – произведение двух различных простых чисел, а e и d – положительные целые числа, удовлетворяющие условию ed ≡ 1 (mod φ(n)). Поскольку e и d положительны, мы можем записать ed = 1 + hφ(n) для некоторого неотрицательного целого числа h. Предполагая, что m и n взаимно просты, имеем

где предпоследняя конгруенция следует из теоремы Эйлера. В более общем случае, для любых e и d, удовлетворяющих ed ≡ 1 (mod λ(n)), тот же вывод следует из обобщения теоремы Эйлера, данного Кармайлом, которое утверждает, что m^(λ(n)) ≡ 1 (mod n) для всех m, взаимно простых с n.

Если m не взаимно просто с n, приведенный выше аргумент недействителен. Это маловероятно (только доля чисел 1/p + 1/q − 1/(pq) обладает этим свойством), но даже в этом случае требуемая конгруенция все равно верна. Либо m ≡ 0 (mod p), либо m ≡ 0 (mod q), и эти случаи можно рассмотреть, используя предыдущее доказательство.

Атаки на обычную RSA

Существует ряд атак на RSA с использованием простых методов, описанных ниже. При шифровании с малыми степенями шифрования (например, если e = 3) и небольшими значениями m (то есть, m < n^(1/e)), результат m^e будет строго меньше модуля n. В этом случае шифротексты можно легко расшифровать, извлекая корень e-й степени из шифротекста в целых числах. Если одно и то же открытое сообщение отправляется e или более получателям в зашифрованном виде, и получатели используют один и тот же показатель степени e, но разные p, q и, следовательно, n, то исходное открытое сообщение можно легко расшифровать с помощью китайской теоремы об остатках. Йохан Хастад заметил, что эта атака возможна даже в том случае, если открытые тексты не равны, но злоумышленник знает линейную зависимость между ними. Позже эту атаку улучшил Дон Копперсмит (см. Атаку Копперсмита). Поскольку шифрование RSA является детерминированным алгоритмом (то есть не имеет случайного компонента), злоумышленник может успешно провести атаку с выбранным открытым текстом, зашифровав вероятные открытые тексты с использованием открытого ключа и проверяя, равны ли они шифротексту. Криптосистема называется семантически безопасной, если злоумышленник не может отличить два шифротекста друг от друга, даже если он знает (или выбрал) соответствующие открытые тексты. RSA без дополнения не является семантически безопасным. RSA обладает свойством, что произведение двух шифротекстов равно шифрованию произведения соответствующих открытых текстов, то есть m1^e * m2^e ≡ (m1 * m2)^e (mod n). Из-за этого мультипликативного свойства возможна атака с выбранным шифротекстом. Например, злоумышленник, желающий узнать расшифровку шифротекста c ≡ m^e (mod n), может попросить владельца секретного ключа d расшифровать подозрительно выглядящий шифротекст c′ ≡ c * r^e (mod n) для некоторого значения r, выбранного злоумышленником. Благодаря мультипликативному свойству, c′ является шифрованием mr (mod n). Следовательно, если злоумышленнику удастся провести атаку, он узнает mr (mod n), из которого он сможет получить сообщение m, умножив mr на модульный обратный элемент r по модулю n. Зная секретный показатель степени d, можно эффективно разложить модуль n = pq на множители. И, имея разложение модуля n = pq на множители, можно получить любой секретный ключ (d′, n), сгенерированный для соответствующего открытого ключа (e′, n). Было показано, что для некоторых типов сообщений данное дополнение не обеспечивает достаточного уровня безопасности. Более поздние версии стандарта включают в себя Optimal Asymmetric Encryption Padding (OAEP), который предотвращает эти атаки. Таким образом, OAEP следует использовать во всех новых приложениях, а дополнение PKCS#1 v1.5 следует заменять везде, где это возможно. Стандарт PKCS#1 также включает схемы обработки, предназначенные для обеспечения дополнительной безопасности для цифровых подписей RSA, например, Probabilistic Signature Scheme for RSA (RSA PSS). Безопасные схемы дополнения, такие как RSA PSS, так же важны для безопасности подписи сообщений, как и для шифрования сообщений. Два патента США на PSS были выданы ( и ); однако срок действия этих патентов истек 24 июля 2009 года и 25 апреля 2010 года соответственно. Использование PSS больше не связано с патентными ограничениями. Следует отметить, что использование разных пар ключей RSA для шифрования и подписи потенциально более безопасно.

There are a number of attacks against plain RSA as described below. When encrypting with low encryption exponents (e. g., 1=e = 3) and small values of the m (i. e., m < n^(1/e)), the result of m^(e) is strictly less than the modulus n. In this case, ciphertexts can be decrypted easily by taking the eth root of the ciphertext over the integers. If the same clear text message is sent to e or more recipients in an encrypted way, and the receivers share the same exponent e, but different p, q, and therefore n, then it is easy to decrypt the original clear text message via the Chinese remainder theorem. Johan Håstad noticed that this attack is possible even if the clear texts are not equal, but the attacker knows a linear relation between them. This attack was later improved by Don Coppersmith (see Coppersmith's attack). Because RSA encryption is a deterministic encryption algorithm (i. e., has no random component) an attacker can successfully launch a chosen plaintext attack against the cryptosystem, by encrypting likely plaintexts under the public key and test whether they are equal to the ciphertext. A cryptosystem is called semantically secure if an attacker cannot distinguish two encryptions from each other, even if the attacker knows (or has chosen) the corresponding plaintexts. RSA without padding is not semantically secure. RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is, m1^(e)m2^(e) ≡ (m1m2)^(e) (mod n). Because of this multiplicative property, a chosen ciphertext attack is possible. E. g., an attacker who wants to know the decryption of a ciphertext c ≡ m^(e) (mod n) may ask the holder of the private key d to decrypt an unsuspicious looking ciphertext c′ ≡ cr^(e) (mod n) for some value r chosen by the attacker. Because of the multiplicative property, c' is the encryption of mr (mod n). Hence, if the attacker is successful with the attack, they will learn mr (mod n), from which they can derive the message m by multiplying mr with the modular inverse of r modulo n.
Given the private exponent d, one can efficiently factor the modulus 1=n = pq. And given factorization of the modulus 1=n = pq, one can obtain any private key (d', n) generated against a public key (e', n). showed that for some types of messages, this padding does not provide a high enough level of security. Later versions of the standard include Optimal Asymmetric Encryption Padding (OAEP), which prevents these attacks. As such, OAEP should be used in any new application, and PKCS#1 v1.5 padding should be replaced wherever possible. The PKCS#1 standard also incorporates processing schemes designed to provide additional security for RSA signatures, e. g. the Probabilistic Signature Scheme for RSA (RSA PSS). Secure padding schemes such as RSA PSS are as essential for the security of message signing as they are for message encryption. Two USA patents on PSS were granted ( and ); however, these patents expired on 24 July 2009 and 25 April 2010 respectively. Use of PSS no longer seems to be encumbered by patents. Note that using different RSA key pairs for encryption and signing is potentially more secure.

Факторизация целых чисел и проблема RSA

Безопасность криптосистемы RSA основана на двух математических задачах: задаче факторизации больших чисел и задаче RSA. Полное расшифрование шифротекста RSA считается невозможным при условии, что обе эти задачи являются сложными, то есть для их решения не существует эффективного алгоритма. Для обеспечения безопасности от частичного расшифрования может потребоваться добавление надежной схемы дополнения. Задача RSA определяется как задача нахождения корня e-й степени по модулю составного числа n: восстановления значения m, такого что c ≡ m^(e) (mod n), где (n, e) является открытым ключом RSA, а c – шифротекстом RSA. В настоящее время наиболее перспективным подходом к решению задачи RSA является факторизация модуля n. В случае возможности восстановления простых множителей, злоумышленник может вычислить секретный показатель d из открытого ключа (n, e), а затем расшифровать c, используя стандартную процедуру. Для этого злоумышленник раскладывает n на p и q и вычисляет НОК(p − 1, q − 1), что позволяет определить d по e. На данный момент не найден метод полиномиального времени для факторизации больших целых чисел на классическом компьютере, но и не доказано, что такого метода не существует; подробнее об этой проблеме – в разделе факторизация целых чисел. Для факторизации публичного модуля n можно использовать метод квадратичного решета с использованием нескольких полиномов (MPQS). Первая факторизация RSA-512 в 1999 году потребовала использования сотен компьютеров и эквивалента 8400 MIPS-лет, за период времени около семи месяцев. К 2009 году Бенджамин Муди смог факторизовать 512-битный ключ RSA за 73 дня, используя только общедоступное программное обеспечение (GGNFS) и свой настольный компьютер (двухъядерный Athlon64 с процессором 1900 МГц). Для процесса просеивания потребовалось менее 5 ГБ дискового пространства и около 2,5 ГБ оперативной памяти. Ривест, Шамир и Адлеман отметили, что им не удалось найти доказательство того, что инверсия RSA столь же сложна, как факторизация. По состоянию на 2020 год наибольшее общеизвестное факторизованное число RSA имело 829 бит (250 десятичных цифр, RSA-250). Его факторизация с использованием современной распределенной реализации заняла около 2700 CPU-лет. На практике ключи RSA обычно имеют длину от 1024 до 4096 бит. В 2003 году RSA Security оценила, что 1024-битные ключи, вероятно, станут уязвимыми к 2010 году. По состоянию на 2020 год неизвестно, можно ли взломать такие ключи, но минимальные рекомендации были повышены как минимум до 2048 бит. Обычно предполагается, что RSA безопасен, если n достаточно велико, за исключением случаев, связанных с квантовыми вычислениями. Если n имеет длину 300 бит или меньше, его можно факторизовать за несколько часов на персональном компьютере, используя уже доступное бесплатное программное обеспечение. Ключи длиной 512 бит были практически взломаны в 1999 году, когда RSA-155 был факторизован с использованием нескольких сотен компьютеров, и теперь их можно факторизовать за несколько недель с использованием стандартного оборудования. В 2011 году были зафиксированы случаи эксплуатации, связанные с использованием сертификатов подписи кода длиной 512 бит, которые могли быть факторизованы. Теоретическое аппаратное устройство под названием TWIRL, описанное Шамиром и Тромером в 2003 году, поставило под сомнение безопасность 1024-битных ключей. Неизвестны атаки на небольшие открытые показатели, такие как e = 3, при условии использования надлежащего дополнения. Атака Копперсмита имеет множество применений при атаке на RSA, особенно если открытый показатель e мал и зашифрованное сообщение короткое и не имеет дополнения. 65537 – часто используемое значение для e; это значение можно рассматривать как компромисс между избежанием потенциальных атак с использованием малых показателей и сохранением эффективности шифрования (или проверки подписи). В специальной публикации NIST по компьютерной безопасности (SP 800-78 Rev. 1 от августа 2007 г.) не допускаются открытые показатели e меньше 65537, но причина этого ограничения не указана. В октябре 2017 года группа исследователей из Масарикова университета объявила об уязвимости ROCA, которая затрагивает ключи RSA, генерируемые алгоритмом, реализованным в библиотеке Infineon под названием RSALib. Было показано, что большое количество смарт-карт и модулей доверенной платформы (TPM) подвержены этой уязвимости. Уязвимые ключи RSA можно легко идентифицировать с помощью тестовой программы, выпущенной командой.

The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i. e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme. The RSA problem is defined as the task of taking eth roots modulo a composite n: recovering a value m such that c ≡ m^(e) (mod n), where (n, e) is an RSA public key, and c is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus n. With the ability to recover prime factors, an attacker can compute the secret exponent d from a public key (n, e), then decrypt c using the standard procedure. To accomplish this, an attacker factors n into p and q, and computes lcm(p − 1, q − 1) that allows the determination of d from e. No polynomial time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists; see integer factorization for a discussion of this problem. Multiple polynomial quadratic sieve (MPQS) can be used to factor the public modulus n.

The first RSA 512 factorization in 1999 used hundreds of computers and required the equivalent of 8,400 MIPS years, over an elapsed time of about seven months. By 2009, Benjamin Moody could factor an 512 bit RSA key in 73 days using only public software (GGNFS) and his desktop computer (a dual core Athlon64 with a 1,900 MHz CPU). Just less than 5 gigabytes of disk storage was required and about 2.5 gigabytes of RAM for the sieving process. Rivest, Shamir, and Adleman noted However, Rivest, Shamir, and Adleman noted, in section IX/D of their paper, that they had not found a proof that inverting RSA is as hard as factoring. as of 2020, the largest publicly known factored RSA number had 829 bits (250 decimal digits, RSA 250). Its factorization, by a state of the art distributed implementation, took about 2,700 CPU years. In practice, RSA keys are typically 1024 to 4096 bits long. In 2003, RSA Security estimated that 1024 bit keys were likely to become crackable by 2010. As of 2020, it is not known whether such keys can be cracked, but minimum recommendations have moved to at least 2048 bits. It is generally presumed that RSA is secure if n is sufficiently large, outside of quantum computing. If n is 300 bits or shorter, it can be factored in a few hours in a personal computer, using software already freely available. Keys of 512 bits have been shown to be practically breakable in 1999, when RSA 155 was factored by using several hundred computers, and these are now factored in a few weeks using common hardware. Exploits using 512 bit code signing certificates that may have been factored were reported in 2011. A theoretical hardware device named TWIRL, described by Shamir and Tromer in 2003, called into question the security of 1024 bit keys. There is no known attack against small public exponents such as 1=e = 3, provided that the proper padding is used. Coppersmith's attack has many applications in attacking RSA specifically if the public exponent e is small and if the encrypted message is short and not padded. 65537 is a commonly used value for e; this value can be regarded as a compromise between avoiding potential small exponent attacks and still allowing efficient encryptions (or signature verification). The NIST Special Publication on Computer Security (SP 800 78 Rev. 1 of August 2007) does not allow public exponents e smaller than 65537, but does not state a reason for this restriction. In October 2017, a team of researchers from Masaryk University announced the ROCA vulnerability, which affects RSA keys generated by an algorithm embodied in a library from Infineon known as RSALib. A large number of smart cards and trusted platform modules (TPM) were shown to be affected. Vulnerable RSA keys are easily identified using a test program the team released.

Важность генерирования сильных случайных чисел

Для генерации простых чисел p и q необходимо использовать криптографически стойкий генератор случайных чисел, который был правильно инициализирован достаточным количеством энтропии. Анализ, сравнивающий миллионы открытых ключей, собранных из Интернета, был проведен в начале 2012 года Арьеном К. Ленстрой, Джеймсом П. Хьюзом, Максимом Ожье, Джоппе В. Босом, Торстеном Кляйнюнгом и Кристофом Вахтером. Им удалось разложить на множители 0,2% ключей, используя только алгоритм Евклида. Они использовали уязвимость, свойственную криптосистемам, основанным на факторизации целых чисел. Если 1=n = pq – один открытый ключ, а 1=n′ = p′q′ – другой, то если случайно 1=p = p′ (но q не равно q'), то простое вычисление 1=gcd(n, n′) = p раскладывает на множители как n, так и n', полностью скомпрометировав оба ключа. Ленстра и др. отмечают, что эту проблему можно минимизировать, используя стойкий случайный источник начальных данных длиной в два раза больше предполагаемого уровня безопасности, или применяя детерминированную функцию для выбора q при заданном p, вместо выбора p и q независимо друг от друга. Надя Хенингер участвовала в группе, которая провела аналогичный эксперимент. Они использовали идею Дэниела Дж. Бернштейна для вычисления НОД каждого ключа RSA n по отношению к произведению всех остальных ключей n', которые они обнаружили (число, состоящее из 729 миллионов цифр), вместо вычисления каждого gcd(n, n′) по отдельности, тем самым достигнув значительного ускорения, поскольку после одного крупного деления задача вычисления НОД становится стандартной. Хенингер сообщает в своем блоге, что проблемные ключи почти исключительно встречались во встраиваемых приложениях, включая "файрволы, маршрутизаторы, VPN-устройства, устройства удаленного администрирования серверов, принтеры, проекторы и VOIP-телефоны" от более чем 30 производителей. Хенингер объясняет, что проблема с одним общим простым числом, выявленная обеими группами, возникает в ситуациях, когда генератор псевдослучайных чисел изначально плохо инициализирован, а затем повторно инициализируется между генерацией первого и второго простых чисел. Использование источников начальных данных с достаточной энтропией, полученных из времени нажатия клавиш, шума электронных диодов или атмосферного шума от радиоприемника, настроенного между станциями, должно решить эту проблему. Стойкая генерация случайных чисел важна на каждом этапе криптографии с открытым ключом. Например, если для симметричных ключей, распространяемых RSA, используется слабый генератор, то злоумышленник может обойти RSA и угадать симметричные ключи напрямую.

A cryptographically strong random number generator, which has been properly seeded with adequate entropy, must be used to generate the primes p and q. An analysis comparing millions of public keys gathered from the Internet was carried out in early 2012 by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter. They were able to factor 0.2% of the keys using only Euclid's algorithm. They exploited a weakness unique to cryptosystems based on integer factorization. If 1=n = pq is one public key, and 1=n′ = p′q′ is another, then if by chance 1=p = p′ (but q is not equal to q'), then a simple computation of 1=gcd(n, n′) = p factors both n and n', totally compromising both keys. Lenstra et al. note that this problem can be minimized by using a strong random seed of bit length twice the intended security level, or by employing a deterministic function to choose q given p, instead of choosing p and q independently. Nadia Heninger was part of a group that did a similar experiment. They used an idea of Daniel J. Bernstein to compute the GCD of each RSA key n against the product of all the other keys n' they had found (a 729 million digit number), instead of computing each gcd(n, n′) separately, thereby achieving a very significant speedup, since after one large division, the GCD problem is of normal size. Heninger says in her blog that the bad keys occurred almost entirely in embedded applications, including "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from more than 30 manufacturers. Heninger explains that the one shared prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially, and then is reseeded between the generation of the first and second primes. Using seeds of sufficiently high entropy obtained from key stroke timings or electronic diode noise or atmospheric noise from a radio receiver tuned between stations should solve the problem. Strong random number generation is important throughout every phase of public key cryptography. For instance, if a weak generator is used for the symmetric keys that are being distributed by RSA, then an eavesdropper could bypass RSA and guess the symmetric keys directly.

Время атак

Кохер описал новую атаку на RSA в 1995 году: если злоумышленник Ева знает аппаратное обеспечение Алисы достаточно подробно и может измерить время расшифровки для нескольких известных шифротекстов, Ева может быстро вычислить секретный ключ d. Эта атака также применима к схеме цифровой подписи RSA. В 2003 году Бонэ и Брамли продемонстрировали более практичную атаку, способную восстановить разложение RSA на простые множители через сетевое соединение (например, с веб-сервера, использующего Secure Sockets Layer (SSL)). Эта атака использует информацию, утекающую при оптимизации, основанной на китайской теореме об остатках, применяемой во многих реализациях RSA. Один из способов противодействия этим атакам — обеспечить, чтобы операция расшифровки занимала фиксированное время для любого шифротекста. Однако этот подход может существенно снизить производительность. Вместо этого большинство реализаций RSA используют альтернативную технику, известную как криптографическое маскирование. Криптографическое маскирование RSA использует мультипликативное свойство RSA. Вместо вычисления c^(d) (mod n), Алиса сначала выбирает секретное случайное число r и вычисляет (r^(e)c)^(d) (mod n). Результат этого вычисления, после применения теоремы Эйлера, равен rc^(d) (mod n), и эффект r можно устранить, умножив на его мультипликативный обратный. Новое значение r выбирается для каждого шифротекста. При использовании маскирования время расшифровки перестает зависеть от значения входного шифротекста, и, следовательно, атака по времени терпит неудачу.

Адаптивные атаки с использованием выбранного шифровального текста

В 1998 году Дэниел Блейхенбахер описал первую практическую адаптивную атаку с выбором открытого текста против зашифрованных сообщений RSA, использующих схему дополнения PKCS #1 v1 (схема дополнения рандомизирует и добавляет структуру в зашифрованное сообщение RSA, что позволяет определить, является ли расшифрованное сообщение допустимым). Из-за уязвимостей схемы PKCS #1, Блейхенбахеру удалось осуществить практическую атаку на реализации RSA протокола Secure Sockets Layer и восстановить ключи сеанса. В результате этой работы криптографы теперь рекомендуют использовать схемы дополнения с доказанной безопасностью, такие как Optimal Asymmetric Encryption Padding, а RSA Laboratories выпустила новые версии PKCS #1, не подверженные этим атакам. Вариант этой атаки, получивший название "BERserk", вновь появился в 2014 году и затронул криптобиблиотеку Mozilla NSS, которая использовалась, в частности, в Firefox и Chrome.

Атаки на анализ боковых каналов

Была описана атака по стороннему каналу с использованием анализа предсказания ветвлений (BPA). Многие процессоры используют предсказатель ветвлений для определения вероятности выполнения условного перехода в потоке инструкций программы. Часто эти процессоры также реализуют технологию одновременной многопоточности (SMT). Атаки, основанные на анализе предсказания ветвлений, используют вспомогательный процесс для статистического определения секретного ключа при его обработке на этих процессорах. Простой анализ предсказания ветвлений (SBPA) заявляет об улучшении BPA не статистическим методом. В своей статье "О силе простого анализа предсказания ветвлений" авторы SBPA (Онур Ачичмез и Четин Кая Кок) утверждают, что смогли восстановить 508 из 512 бит ключа RSA за 10 итераций. Атака на основе сбоев питания на реализации RSA была описана в 2010 году. Автор восстановил ключ, изменяя напряжение питания процессора за пределами допустимых значений, что приводило к множественным сбоям питания на сервере.

Сложная реализация

Для безопасной реализации RSA необходимо учитывать множество деталей (надежный ГСЧ, приемлемая степень публичного ключа и т. д.). Это делает реализацию сложной, вплоть до того, что в книге "Практическая криптография с Go" рекомендуется избегать использования RSA, если это возможно.