Ашық кілтті криптография алгоритмі және RSA жүйесі

Кіріспе

Қоғамдық кілттің криптография алгоритмі – криптожүйе. Қоғамдық кілт криптожүйесінде шифрлау кілті ашық болады және құпия сақталатын шифрлау кілтінен (жеке кілттен) ерекшеленеді. RSA пайдаланушысы екі үлкен жай санға негізделген ашық кілтті құрастырып, жариялайды, сонымен қатар қосымша мәнді де жариялайды. Жай сандар құпия сақталады. Кез келген адам ашық кілт арқылы хабарды шифрлей алады, бірақ жеке кілтті білетін адам ғана оны шеше алады. RSA қауіпсіздігі екі үлкен жай санның көбейтіндісін есепке бөлудің практикалық қиындығына негізделген, бұл "есепке бөлу мәселесі" деп аталады. RSA шифрлауын бұзу – RSA мәселесі деп аталады. Бұл мәселенің есепке бөлу мәселесінен гөрі қиындығы ашық мәселе болып қалады. Егер жеткілікті үлкен кілт қолданылса, жүйені жеңуге арналған жарияланбаған әдістер жоқ. RSA салыстырмалы түрде баяу алгоритм. Осы себепті, ол пайдаланушы деректерін тікелей шифрлеу үшін жиі қолданылмайды. Көбінесе RSA симметриялық кілтті криптография үшін ортақ кілттерді беру үшін қолданылады, содан кейін олар көп көлемді шифрлеу-дешифрлеу үшін пайдаланылады.

Тарих

Асимметриялық ашық кілт криптожүйесінің идеясы 1976 жылы осы тұжырымдаманы жариялаған Уитфилд Диффи мен Мартин Хеллманға тиесілі. Олар сонымен қатар сандық қолтаңбаларды енгізді және сандар теориясын қолдануға тырысты. Олардың құрастыруындағы негіз – модуль бойынша белгілі бір санның дәрежесінен жасалған ортақ құпия кілт. Алайда, олар бір бағытты функцияны іске асыру мәселесін ашық қалдырды, мүмкін сол кезде санды түйіндеудің қиындығы жеткілікті зерттелмегендіктен. Сонымен қатар, Диффи-Хеллман сияқты, RSA да модульдік дәрежелеуге негізделген. Рон Ривест, Ади Шамир және Массачусетс технология институтының Леонард Адлеман бір жыл бойы кері қайтаруы қиын функция жасауға бірнеше рет әрекеттенді. Ривест пен Шамир, компьютер ғалымдары ретінде, көптеген мүмкін функцияларды ұсынды, ал математик Адлеман олардың кемшіліктерін табуға жауапты болды. Олар «қапшыққа негізделген» және «пермутациялық көпмүшелер» сияқты көптеген тәсілдерді сынап көрді. Бір кезде олар өзара қайшы талаптарға байланысты мұндай функция жасау мүмкін емес деп ойлады. 1977 жылдың сәуір айында олар бір студенттің үйінде Паска (құтқарылу) мерекесін тойлады және түн ортасында үйлеріне қайтқанға дейін көп шарап ішті. Ұйықтамаған Ривест диванда математика оқулығымен жатып, олардың бір бағытты функциясы туралы ойлана бастады. Ол түнің қалған бөлігін идеясын қалыптастыруға жұмсады және таңертең қағаздың көп бөлігі дайын болды. Алгоритм қазір RSA деп аталады, олардың тегінің әріптері қағаздағы тізімдегідей ретпен берілген. Британдық барлау қызметі – Үкіметтік байланыс штабында (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.

Патент

RSA алгоритмін сипаттайтын патент 1983 жылдың 20 қыркүйегінде MIT-ге берілді: "Криптографиялық байланыс жүйесі және әдісі". DWPI патентінің аннотациясынан: Жүйеде кодтау құрылғысы бар кемінде бір терминалға және декодтау құрылғысы бар кемінде бір терминалға қосылған байланыс арнасы бар. Жіберілмекші хабар кодтау терминалында алдын ала белгіленген жиынтықтағы М саны ретінде шифрланып, шифрмәтінге түрлендіріледі. Бұл сан содан кейін бірінші алдын ала белгіленген дәрежеге (көрсетілген қабылдаушымен байланысты) көтеріліп, есептеледі. Экспоненталанған сан екі алдын ала белгіленген жай санның көбейтіндісіне (көрсетілген қабылдаушымен байланысты) бөлінгенде қалдық немесе қалдық, C есептеледі. Алгоритмнің толыққанды сипаттамасы 1977 жылдың тамызында Scientific American журналының "Математикалық ойындар" рубрикасында жарияланды.

Операция

RSA алгоритмі төрт қадамнан тұрады: кілт жасау, кілт тарату, шифрлау және шифрлауды кері қайтару. RSA-ның негізгі принципі – барлық бүтін сандар үшін m (0 ≤ m < n) екі өте үлкен оң бүтін сан e, d және n табу мүмкіндігі, олардың екеуі де n-ге бөлгенде бірдей қалдық береді (яғни, модуль бойынша конгруэнтті): алайда, тек e және n белгілі болғанда, d табу өте қиын. n және e бүтін сандары ашық кілтті құрайды, d жеке кілтті білдіреді, ал m – хабарламаны. e және d бойынша модульдік дәрежелеу сәйкесінше шифрлау мен шифрлауды кері қайтаруға сәйкес келеді. Бұған қоса, екі дәрежелі өрнекті ауыстыруға болатындықтан, жеке және ашық кілтті де ауыстыруға болады, бұл бірдей алгоритмді пайдаланып хабарламаға қол қоюға және оны тексеруге мүмкіндік береді.

Кілттерді бөлу

Мысалы, Боб Алисаға ақпарат жібергісі келеді делік. Егер олар RSA-ны пайдалануды шешсе, Боб хабарды шифрлау үшін Алисаның ашық кілтін білуі керек, ал Алиса хабарды ашу үшін өзінің жеке кілтін пайдалануы керек. Бобтың шифрланған хабарламаларын жіберуіне мүмкіндік беру үшін Алиса өзінің ашық кілтін (n, e) Бобқа сенімді, бірақ міндетті түрде құпия емес арна арқылы жібереді. Алисаның жеке кілті (d) ешқашан таралмайды.

Шифрлау

Боб Алисаның ашық кілтін алғаннан кейін, ол Алисаға M хабарламасын жібере алады. Ол үшін ол алдымен M (нақтырақ айтқанда, толтырылмаған қара мәтін) санын 0 ≤ m < n шартына сәйкес келетін толық санға (нақтырақ айтқанда, толтырылған қара мәтін) айналдырады, бұл үшін екеуі келіскен қайтымды протокол, яғни толтыру схемасы қолданылады. Содан кейін ол Алисаның e ашық кілтін пайдаланып, c шифрланған мәтінін есептейді. Бұл модульдік дәрежелеу арқылы, тіпті өте үлкен сандар үшін де, оңай және жылдам орындалуы мүмкін. Боб содан кейін c-ні Алисаға жібереді. m-нің кем дегенде тоғыз мәні c шифрланған мәтініне тең нәтиже береді, бірақ бұл практикада өте сирек кездеседі.

Ойлер теоремасын қолдану арқылы дәлелдеу

Ривест, Шамир және Адлеманның түпнұсқалық мақаласында Ферманың кішкентай теоремасы RSA-ның неге жұмыс істейтінін түсіндіру үшін қолданылса да, көбінесе Эйлер теоремасына сүйенетін дәлелдемелер кездеседі. Біз m^(ed) ≡ m (mod n) екенін көрсеткіміз, мұнда n = pq екі әртүрлі жай санның көбейтіндісі, ал e және d – ed ≡ 1 (mod φ(n)) шартын қанағаттандыратын оң бүтін сандар. e және d оң сандар болғандықтан, 1 = ed = 1 + hφ(n) деп жаза аламыз, мұнда h – нөл емес бүтін сан. m саны n-ге өзіндік жай сан болған жағдайда, Эйлер теоремасынан екінші соңғы тепе-теңдік мынадай болады. Кез келген e және d сандары ed ≡ 1 (mod λ(n)) шартын қанағаттандырса, дәл осындай қорытынды Эйлер теоремасының Кармайкл тарапынан алынған жалпылама түрінен шығады, яғни m^(λ(n)) ≡ 1 (mod n) барлық 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′ ≡ cr^e (mod n) шифрлауын сұрауы мүмкін, мұндағы r шабуылшы таңдаған мән. Көбейту қасиетіне сәйкес, c′ mr (mod n) шифрлау болып табылады. Сондықтан, егер шабуылшы шабуылда табысқа жетсе, ол mr (mod n) мәнін біледі, одан m хабарламасын r-дің n модуль бойынша кері шамасын mr-ге көбейту арқылы алуға болады. Жеке көрсеткіш d берілгенде, модуль n = pq тиімді түрде көйтілуі мүмкін. Ал модуль n = pq көйтілгенін ескере отырып, кез келген жеке кілт (d', n) ашық кілтке (e', n) қарсы жасалуы мүмкін. Кейбір хабарламалар үшін бұл паддинг жеткілікті деңгейде қауіпсіздік қамтамасыз етпейтіні көрсетілді. Стандарттың кейінгі нұсқаларына осы шабуылдарды болдырмайтын Оптималды Асимметриялық Шифрлау Паддингі (OAEP) кіреді. Осылайша, OAEP кез келген жаңа қолданбада қолданылуы керек, ал PKCS#1 v1.5 паддингі мүмкіндігінше ауыстырылуы керек. PKCS#1 стандартында RSA қолтаңбаларына қосымша қауіпсіздік беруге арналған өңдеу схемалары да бар, мысалы, RSA үшін Ықтималдық Қолтаңба Схемасы (RSA PSS). RSA PSS сияқты қауіпсіз паддинг схемалары хабарламаны шифрлау үшін де, қол қою үшін де қауіпсіздік үшін маңызды. PSS-ке екі АҚШ патені берілді ( және ); алайда бұл патенттердің мерзімі 2009 жылдың 24 шілдесінде және 2010 жылдың 25 сәуірінде аяқталды. 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 шифрмәтінiң толық шифрлауын мүмкiн емес деп есептеуге болады, егер осы екі мәселе де қиын болса, яғни оларды шешуге тиімді алгоритм болмаса. Жарым-жартылай шифрлаудан қорғану үшін қауіпсіз толтыру схемасын қосу қажет болуы мүмкін. RSA мәселесі – құрама n санының e-ші түбiн модуль бойынша табу мiндетi: c ≡ m^(e) (mod n) шартын қанағаттандыратын m мәнiн қалпына келтіру, мұнда (n, e) – RSA ашық кілті, ал c – RSA шифрмәтіні. Қазіргі уақытта RSA мәселесін шешудің ең перспективалы тәсілі – n модулін факторлау. Басты факторларды қалпына келтіру мүмкiндiгiмен шабуылшы ашық кілт (n, e) арқылы құпия көрсеткiш d-ны есептей алады, содан кейін стандартты процедураны қолдана отырып c-ны шифрлайды. Бұл үшін шабуылшы n-дi p және q-ға көбейтіп, lcm(p − 1, q − 1) есептейді, бұл d-ны e-ден анықтауға мүмкiндiк береді. Классикалық компьютерде үлкен бүтін сандарды факторлауға арналған полиномиалды уақыт әдісі әлі табылған жоқ, бірақ мұндай әдіс жоқ екені дәлелденбеген; осы мәселені талқылау үшін бүтін сандарды факторлау қараңыз. Көптік полиномиалды квадраттық елеуіш (MPQS) n жалпы модулін факторлау үшін пайдаланылуы мүмкiн. 1999 жылы алғашқы RSA 512 факторлау жүздеген компьютерлерді пайдаланды және шамамен жеті ай өткен уақыт ішінде 8,400 MIPS жылға тең болды. 2009 жылы Бенджамин Муди тек ашық бағдарламалық қамтамасыз етуді (GGNFS) және өзінің үстел компьютерін (1,900 МГц процессоры бар екі ядролы Athlon64) пайдаланып, 73 күнде 512 биттік RSA кілтін факторлай алды. Тек 5 гигабайттан аз дискілік жад және 2,5 гигабайт RAM қажет болды. Алайда, Rivest, Shamir және Adleman өздерінің IX/D бөлімінде RSA-н кері қайтарудың факторлау сияқты қиын екеніне дәлел таппағанын атап өтті. 2020 жылға қарай жалпыға белгілі ең үлкен факторланған RSA саны 829 биттен (250 ондық сан, RSA 250) тұрды. Оның факторлық бөлінісі, технологияның алдыңғы қатарлы үлестірілген іске асырылуы арқылы, шамамен 2,700 CPU жылды алды. Іс жүзінде RSA кілттерінің ұзындығы әдетте 1024-тен 4096 битке дейін болады. 2003 жылы RSA Security 1024 биттік кілттерді 2010 жылға қарай бұзуға болатындығын болжады. 2020 жылға қарай мұндай кілттерді бұзу мүмкiндiгi белгісіз, бірақ ең аз ұсыныстар кем дегенде 2048 битке ауыстырылды. Жалпы алғанда, егер n жеткілікті үлкен болса, кванттық есептеуден тыс RSA қауіпсіз деп есептеледі. Егер n 300 бит немесе одан аз болса, оны бірнеше сағат ішінде дербес компьютерде, қазірдің өзінде еркін қол жетімді бағдарламалық қамтамасыз етуді пайдалана отырып, факторлауға болады. 512 биттік кілттер 1999 жылы RSA 155 бірнеше жүз компьютерлерді пайдалану арқылы факторландырылған кезде практикалық түрде бұзуға болатындығы дәлелденді, ал қазір олар бірнеше аптада жалпы аппаратты пайдалану арқылы факторландырылады. 2011 жылы 512 биттік кодты қол қою сертификаттарын пайдаланатын, факторланған болуы мүмкiн пайдаланулар туралы хабарланды. 2003 жылы Шамир мен Тромер сипаттаған TWIRL деп аталатын теориялық аппараттық құрылғы 1024 биттік кілттердің қауіпсіздігін күмән тудырды. Дұрыс толтыру қолданылса, 1=e = 3 сияқты шағын көпшілік көрсеткіштеріне қарсы белгілі шабуыл жоқ. Coppersmith шабуылы RSA-ға шабуыл жасау үшін көптеген қолданбалар бар, әсіресе егер e ашық көрсеткіші кіші болса және шифрланған хабарлама қысқа және толтырылмаған болса. 65537 – e үшін жиі қолданылатын мән; бұл мәнді ықтимал кіші көрсеткіштік шабуылдардан аулақ болу және тиімді шифрлауды (немесе қолтаңбаны тексеруді) рұқсат ету арасындағы келісім ретінде қарастыруға болады. NIST Компьютерлік қауіпсіздік туралы арнайы басылымы (SP 800 78 Rev. 1, 2007 жылғы тамыз) 65537-ден кіші e жалпыға ортақ көрсеткішіне рұқсат бермейді, бірақ бұл шектеудің себебін көрсетпейді. 2017 жылдың қазан айында Масарик университетінің зерттеушілер тобы RSALib деп аталатын Infineon кітапханасында жинақталған алгоритммен құрылған RSA кілттеріне әсер ететін ROCA осаллығын жариялады. Көптеген смарт-карталар мен сенімді платформа модульдері (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' екеуін де жіктеуге мүмкіндік береді, осылайша екі кілтті де толығымен құлатып жібереді. Ленстра және авторлар бұл мәселені бит ұзындығы қажетті қауіпсіздік деңгейінен екі есе ұзын болған күшті кездейсоқ инициализацияны қолдану арқылы немесе p және q-ны тәуелсіз таңдаудың орнына, p берілгенде q-ны таңдау үшін детерминистік функцияны қолдану арқылы азайтуға болатынын атап өтеді. Надя Хенингер осыған ұқсас эксперимент жасаған топтың құрамында болды. Олар Дэниел Дж. Бернштейннің идеясын пайдаланып, әр RSA кілтінің GCD-ін n-нің барлық басқа кілттерінің көбейтіндісіне қарсы есептеді (729 миллион цифрдан тұратын сан), әр gcd(n, n′) есептеуінен гөрі, осылайша айтарлықтай жылдамдыққа қол жеткізді, себебі бір үлкен бөлуден кейін GCD мәселесі қалыпты көлемде болады. Хенингер өзінің блогында бұзылған кілттер негізінен «өрт қабырғалары, маршрутизаторлар, 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.

Уақытша шабуылдар

Кохер 1995 жылы RSA-ға жаңа шабуылды сипаттады: егер шабуылшы Ева Алисаның аппараттық құралдарын жеткілікті детальды білетін болса және бірнеше белгілі шифрмәтіндердің шифрлау уақытын өлшесе алса, Ева шифрлау кілтін d тез анықтай алады. Бұл шабуыл RSA қолтаңба схемасына да қолданылуы мүмкін. 2003 жылы Бонэ мен Брамли желілік қосылым арқылы (мысалы, Secure Sockets Layer (SSL) қосылған веб-серверден) RSA факторларын қалпына келтіре алатын практикалық шабуылды көрсетті. Бұл шабуыл көптеген RSA жүзеге асырулары қолданатын қытайлық қалдық теоремасының оңтайландыруынан ақпараттың таралуын пайдаланады. Бұл шабуылдарды болдырмаудың бір жолы – шифрмәтіннің әрқайсысы үшін шифрлау операциясы тұрақты уақытқа созылатынын қамтамасыз ету. Алайда, бұл тәсіл өнімділікті айтарлықтай төмендетуі мүмкін. Оның орнына, көптеген RSA жүзеге асырулары криптографиялық жасыру деп аталатын баламалы әдісті қолданады. RSA жасыру RSA-ның көбейту қасиетін пайдаланады. c^(d) (mod n) есептеудің орнына, Алиса алдымен құпия кездейсоқ r мәнін таңдайды және (r^(e)c)^(d) (mod n) есептейді. Бұл есептеудің нәтижесі Эйлер теоремасын қолданғаннан кейін rc^(d) (mod n) болады, сондықтан r әсерін оның кері көбейту арқылы жоюға болады. Әр шифрмәтін үшін r-дің жаңа мәні таңдалады. Жасыру қолданылған кезде, шифрлау уақыты енді кіріс шифрмәтіннің мәнімен байланысты емес, сондықтан уақыт шабуылы сәтсіз аяқталады.

Адаптациялық таңдалған шифрлық мәтіндік шабуылдар

1998 жылы Дэниел Блейхенбахер PKCS #1 v1 толтыру схемасын пайдалана отырып, RSA шифрланған хабарламаларға қарсы бірінші практикалық бейімделмелі таңдалған шифрмәтіндік шабуылды сипаттады (бұл толтыру схемасы RSA шифрланған хабарламаға кездейсоқ және құрылымдық элементтер қосады, соның арқасында шифрланған хабарламаның дұрыс екендігін анықтауға болады). PKCS #1 схемасындағы қателерге байланысты, Блейхенбахер Secure Sockets Layer протоколының RSA нұсқаларына қарсы шабуыл жасап, сессия кілттерін қалпына келтіре алды. Осы жұмыстың нәтижесінде криптографтар қазір дәлелді түрде қауіпсіз толтыру схемаларын, мысалы, Оңтайлы Асимметриялық Шифрлау Толтыруын (Optimal Asymmetric Encryption Padding) пайдалануды ұсынады, ал RSA Laboratories PKCS #1-дің осы шабуылдарға осал емес жаңа нұсқаларын шығарды. Осы шабуылдың "BERserk" деп аталған түрі 2014 жылы қайта пайда болды. Ол Firefox және Chrome қолданған Mozilla NSS Crypto Library-ге әсер етті.

Бүйірлік арналар талдау шабуылдары

Браншты болжау талдауын (BPA) қолданатын жанама арналық шабуыл сипатталды. Көптеген процессорлар бағдарламаның нұсқау ағынындағы шартты тармақтың орындалу ықтималдығын анықтау үшін тармақ болжаушысын пайдаланады. Көбінесе бұл процессорлар бір мезгілде көп өрістік (SMT) технологиясын қолдайды. Бранч болжау талдау шабуылдары осы процессорларда өңделгенде жеке кілтті (статистикалық) анықтау үшін бақылау процесін пайдаланады. Қарапайым тармақты болжау талдауы (SBPA) BPA-ны статистикалық емес тәсілмен жақсартады деп мәлімдейді. "Қарапайым тармақты болжау талдауының күші туралы" мақаласында SBPA авторлары (Онур Ачичмез және Сетин Кая Кок) 10 итерацияда RSA кілтінің 512 битінен 508-ін анықтағанын мәлімдейді. 2010 жылы RSA іске асырылымдарына қарсы қуат ақаулары шабуылдары сипатталды. Автор кілтті CPU қуат кернеуін шектен тыс өзгерту арқылы қалпына келтірді, бұл серверде бірнеше қуат ақауларына әкелді.

Қиын іске асыру

RSA-ны қауіпсіз түрде іске асыру үшін ескеру керек көптеген ерекшеліктер бар (күшті PRNG, қабылданатын ашық кілттік көрсеткіш және т.б.). Бұл оны іске асыруды қиын етеді, тіпті "Practical Cryptography With Go" кітабы мүмкіндігі болса RSA-ны қолданудан қашуды ұсынады.