Ақпараттық жүйелерді жасырын аспектілерді анықтау арқылы талдау

Кіріспе

Ақпараттық жүйелерді олардың жасырын жақтарын анықтау мақсатында талдауды зерттеу.

Криптоанализ (грек тілінен: kryptós – "жасырын", analýein – "талдау") – жүйенің жасырын жақтарын түсіну үшін ақпараттық жүйелерді талдау процесі. Криптоанализ криптографиялық қауіпсіздік жүйелерін бұзу және криптографиялық кілт белгісіз болған жағдайда да шифрланған хабарламалардың мазмұнына қол жеткізу үшін қолданылады. Криптографиялық алгоритмдерді математикалық талдаудан өзге, криптоанализ криптографиялық алгоритмдердің өзіндегі кемшіліктерге емес, олардың іске асырылуындағы әлсіздіктерді пайдаланатын жанама арна арқылы шабуылдарды зерттеуді де қамтиды. Мақсаты бір болғанымен, криптоанализдің әдістері мен техникалары криптография тарихы бойында күрт өзгеріп, криптографиялық күрделіліктің артуына бейімделіп келді. Бұл өзгерістер бұрынғы қалам мен қағазға негіделген әдістерден бастап, Екінші дүниежүзілік соғыстағы Блетчли Парктегі британдық "Бомбалар" мен "Колосс" компьютерлері сияқты машиналарға, содан кейін қазіргі заманғы математикалық тұрғыдан дамыған компьютерлік жүйелерге дейін жетті. Қазіргі криптожүйелерді бұзу әдістері көбінесе таза математикадағы мұқият құрастырылған мәселелерді шешуді қамтиды, олардың ең танымалсы – бүтін сандарды жіктеу.

Шолу

Шифрлау кезінде құпия ақпарат ("таза мәтін" деп аталады) жіберуші оны шифрлау алгоритмін қолдана отырып, ең алдымен оқылмайтын формаға ("шифрлық мәтін") түрлендіріп, алушыға қауіпсіз түрде жібереді. Шифрлық мәтін алушыға қауіпсіз емес арна арқылы жіберіледі. Алушы шифрлық мәтінді кері шифрлау алгоритмін қолдану арқылы шифрлайды, нәтижесінде таза мәтінді қалпына келтіреді. Шифрлық мәтінді шифрлау үшін алушыға жіберушіден құпия ақпарат қажет, әдетте әріптер, сандар немесе биттер тізбегі, ол криптографиялық кілт деп аталады. Егер рұқсатсыз адам таралу кезінде шифрлық мәтінге қол жеткізсе де, құпия кілтсіз оны таза мәтінге қайта түрлендіре алмайды деген принцип бар. Шифрлау тарих бойы маңызды әскери, дипломатиялық және коммерциялық хабарламаларды жіберу үшін қолданылып келді, ал қазіргі күні электрондық пошта мен интернет байланысын қорғау үшін компьютерлік желілерде кеңінен қолданылады. Криптоанализдің мақсаты үшінші тараптың, криптоаналитик, түпнұсқа ("таза мәтін") туралы мүмкіндігінше көп ақпарат алуы, шифрлық мәтінді оқу үшін шифрлауды "бұзуға" тырысып, құпия кілтті анықтау, соның арқасында болашақ хабарламаларды шифрлауға және оқуға болады. Мұны іске асыруға арналған математикалық техника криптографиялық шабуыл деп аталады. Криптографиялық шабуылдарды әртүрлі жолдармен сипаттауға болады:

Шабуылшы қолда бар ақпараттың мөлшері

Криптоаналитикалық шабуылдар шабуылшының қолда бар ақпарат түріне қарай жіктелуі мүмкін. Негізгі бастапқы нүкте ретінде, талдау мақсатында жалпы алгоритм белгілі деп есептеледі; бұл Шеннонның «жау жүйені біледі» максимісі, бұл өз кезегінде Керкгоффс принципімен тең. Бұл практикадағы орынды болжам – тарих бойында құпия алгоритмдердің тыңшылық, сатқындық және кері инженерия арқылы кеңінен танылуының көптеген мысалдары бар. (Кейде шифрлар таза дедукция арқылы бұзылады; мысалы, неміс Лоренц шифры және жапондық Purple коды, сондай-ақ әртүрлі классикалық схемалар):
Тек шифрмәтін: криптоаналитик тек шифрмәтіндердің немесе кодталған мәтіндердің жинағына қол жеткізе алады. Белгілі ашық мәтін: шабуылшыда сәйкес келетін ашық мәтінді білетін шифрмәтіндер жиынтығы бар. Таңдалған ашық мәтін (таңдалған шифрмәтін): шабуылшы өз таңдауы бойынша ашық мәтіндердің (шифрмәтіндердің) кез келген жиынтығына сәйкес шифрмәтіндерді (ашық мәтіндерді) алуға болады. Адаптивті таңдалған ашық мәтін: таңдалған ашық мәтіндік шабуыл сияқты, бірақ шабуылшы алдыңғы шифрлаудан алынған ақпаратқа негізделген кейінгі ашық мәтіндерді таңдай алады, бұл Адаптивті таңдалған шифрмәтіндік шабуылға ұқсас. Қатысты кілт шабуылы: таңдалған ашық мәтіндік шабуыл сияқты, бірақ шабуылшы екі түрлі кілтпен шифрланған шифрмәтіндерді алуға болады. Кілттер белгісіз, бірақ олардың арасындағы байланыс белгілі; мысалы, бір битпен ерекшеленетін екі кілт.

Қажетті есептеу ресурстары

Шабуылдарды оларға қажетті ресурстар арқылы да сипаттауға болады. Осы ресурстарға мыналар жатады:
Уақыт – орындалуы тиіс есептеу қадамдарының саны (мысалы, сынақ шифрлаулар). Жады – шабуылды жүзеге асыру үшін қажетті сақтау көлемі. Деректер – белгілі бір тәсіл үшін қажетті ашық мәтіндер мен шифрлы мәтіндердің мөлшері мен түрі. Кейде осы шамаларды дәл болжау қиын, әсіресе шабуылды іс жүзінде сынау үшін жүзеге асыру мүмкін болмағанда. Бірақ академиялық криптоаналитиктер шабуылдардың қиындығының шамамен ретін келтіруге тырысады, мысалы, «SHA 1 соқтығысулары қазір 252». Брюс Шнайер есептеу тұрғысынан жүзеге асырылуы қиын шабуылдарды да бұзу деп санауға болатынын айтады: «Шифрды бұзу дегеніміз шифрдағы әлсіздікті табу, оны күш қолданудан гөрі аз күрделілікпен пайдалануға болады. Күш қолдану 2128 шифрлауды қажет етуі мүмкін, бірақ 2110 шифрлауды қажет ететін шабуыл шифрдың бұзылуы болып есептеледі, қарапайым тілмен айтқанда, бұзу – шифр жарнамаланғандай жұмыс істемейтіндігінің куәлігі». Осылайша, толық криптожүйе күшті болуы мүмкін, тіпті айналымдар саны қысқартылған нұсқалары әлсіз болса да. Дегенмен, бастапқы криптожүйені бұзуға жақын жартылай бұзулар толық бұзудың алдын білдіруі мүмкін; DES, MD5 және SHA 1-ге жасалған сәтті шабуылдардың бәрі де әлсіретілген нұсқаларға жасалған шабуылдармен басталды. Академиялық криптографияда схеманың әлсіздігі немесе бұзылуы әдетте өте консервативті түрде анықталады: оған көп уақыт, жад немесе белгілі ашық мәтіндер қажет болуы мүмкін. Сондай-ақ, шабуылшыдан көптеген нақты шабуылшылардың істей алмайтын нәрселерді істеуі талап етілуі мүмкін: мысалы, шабуылшы шифрланатын нақты ашық мәтінді таңдауы керек немесе тіпті құпия кілтке байланысты бірнеше кілттерді қолдану арқылы шифрланатын ашық мәтінді сұрауы мүмкін. Бұдан әрі, ол криптожүйенің жетілмегендігін дәлелдеуге жеткілікті, бірақ нақты шабуылшыларға пайдалы болмайтын ақпараттың шағын бөлігін ғана ашуы мүмкін. Соңында, шабуыл криптографиялық құралдардың әлсіретілген нұсқасына, мысалы, айналымдар саны қысқартылған блок шифрына, толық жүйені бұзуға жасалған қадам ретінде ғана қолданылуы мүмкін.

Attacks can also be characterised by the resources they require. Those resources include:
Time – the number of computation steps (e. g., test encryptions) which must be performed. Memory – the amount of storage required to perform the attack. Data – the quantity and type of plaintexts and ciphertexts required for a particular approach. It is sometimes difficult to predict these quantities precisely, especially when the attack is not practical to actually implement for testing. But academic cryptanalysts tend to provide at least the estimated order of magnitude of their attacks' difficulty, saying, for example, "SHA 1 collisions now 252." Bruce Schneier notes that even computationally impractical attacks can be considered breaks: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute force might require 2128 encryptions; an attack requiring 2110 encryptions would be considered a break simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised." so it's possible for the full cryptosystem to be strong even though reduced round variants are weak. Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow; the successful attacks on DES, MD5, and SHA 1 were all preceded by attacks on weakened versions. In academic cryptography, a weakness or a break in a scheme is usually defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts. It also might require the attacker be able to do things many real world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or even to ask for plaintexts to be encrypted using several keys related to the secret key. Furthermore, it might only reveal a small amount of information, enough to prove the cryptosystem imperfect but too little to be useful to real world attackers. Finally, an attack might only apply to a weakened version of cryptographic tools, like a reduced round block cipher, as a step towards breaking the full system.

Тарих

Криптоанализ криптографиямен бірге дамып келді, және осы бәсекелестік криптография тарихында көрініс тапқан – ескі, бұзылған шифрларды жаңаларымен алмастыру, ал жақсартылған схемаларды бұзу үшін жаңа криптоаналитикалық әдістер ойлап табылды. Іс жүзінде, олар бір монетаның екі жағындай қарастырылады: қауіпсіз криптография болжамды криптоанализге қарсы тұратын дизайнды талап етеді.

Классикалық шифрлар

"Криптоанализ" деген сөз салыстырмалы түрде жаңа (ол Уильям Фридман 1920 жылы ойлап тапқан), бірақ кодтар мен шифрларды бұзу әдістері одан да ертерек кезеңге жатады. Дэвид Кан "Кодтарды бұзушылар" кітабында араб ғалымдары криптоаналитикалық әдістерді жүйелі түрде жазған алғашқы адамдар болғанын айтады. Криптоанализ туралы алғашқы жазбаша түсіндірме 9 ғасырдың араб ғалымы әл-Кинди (шамамен 801–873 жж., Еуропада "Алкиндус" деп те аталған) "Криптографиялық хабарламаларды шешу туралы трактат" (Рисалах фи Истихрадж әл Муамма) еңбегінде келтірілген. Бұл трактатта жиілік талдауы әдісінің алғашқы сипаттамасы бар. Сондықтан әл-Кинди тарихтағы алғашқы код бұзғыш деп есептеледі. Оның маңызды жұмысына әл-Халил (717–786) ықпал еткен, ол "Криптографиялық хабарламалар кітабын" жазды, онда пермутациялар мен комбинацияларды қолдану арқылы барлық мүмкін араб сөздерін дауысты және дауыссыз әріптерімен тізімдеудің алғашқы мысалы келтірілген. Жиілік талдауы – классикалық шифрларды бұзудың негізгі құралы. Табиғи тілдерде әліпбидің кейбір әріптері басқаларына қарағанда жиірек кездеседі; мысалы, ағылшын тілінде "E" әрпі кез келген мәтін үлгісінде ең көп кездесетін әріп болуы мүмкін. Сол сияқты, "TH" диграфы ағылшын тіліндегі ең жиі кездесетін әріптер жұбы және т.б. Жиілік талдауы осы статистиканы жасыра алмайтын шифрға негізделген. Мысалы, қарапайым алмастыру шифрында (әрбір әріп басқа әріппен алмастырылатын), шифрмәтіндегі ең жиі кездесетін әріп "E" әрпіне сәйкес болуы мүмкін. Сондықтан, егер шифрмәтін алфавит әріптерін жеткілікті түрде есептеу үшін жеткілікті ұзын болса, мұндай шифрды жиілік арқылы талдау салыстырмалы түрде оңай. Әл-Киндидің моноалфавиттік алмастыру шифрларын бұзу үшін жиілік талдауы әдісін ойлап табуы Екінші дүниежүзілік соғысқа дейінгі криптоанализ саласындағы ең маңызды жетістік болды. Әл-Киндидің "Рисалах фи Истихрадж әл Муамма" кітабында алғашқы криптоаналитикалық әдістер, соның ішінде полиалфавиттік шифрлар, шифрларды жіктеу, араб фонетикасы мен синтаксисі туралы сипаттамалар келтірілген. Бұдан өзге, ол шифрлау әдістерін, белгілі бір шифрларды криптоанализді және араб тіліндегі әріптер мен әріптер тіркесінің статистикалық талдауын қамтыды. Криптоанализдің табысы тарихқа күшті әсер еткені сөзсіз; басқалардың құпия ойлары мен жоспарларын оқу қабілеті шешуші артықшылықты қамтамасыз етеді. Мысалы, 1587 жылы Англияда Шотландияның Мэри патшайымы Англияның Елизавета I-ге қарсы үш қастандыққа қатысқандығы үшін мемлекеттік қасақаналық жасады деген айыппен сотталып, өлім жазасына кесілді. Оның заговоршылармен жазған шифрланған хаттары Томас Фелипс тарапынан бұзылғаннан кейін жоспарлар ашыққа шықты. Еуропада 15-16 ғасырларда француз дипломаты Блез де Вигенер (1523–96) және басқалар полиалфавиттік алмастыру шифры идеясын дамытты. Шамамен үш ғасыр бойы Вигенер шифры, түрлі шифрлау алфавиттерін таңдау үшін қайталанатын кілтті пайдаланатын, толыққанды қауіпсіз деп саналды ("дешифрлеуге болмайтын шифр"). Дегенмен, Чарльз Бэббидж (1791–1871) және кейін, тәуелсіз түрде, Фридрих Касиски (1805–81) осы шифрды бұзуға қол жеткізді. Бірінші дүниежүзілік соғыс кезінде бірнеше елдің өнертапқыштары Вигенер жүйесін бұзу үшін пайдаланылған қайталауды азайту мақсатында Артур Шербиустың "Энигма" сияқты роторлық шифрлау машиналарын жасады.

Although the actual word "cryptanalysis" is relatively recent (it was coined by William Friedman in 1920), methods for breaking codes and ciphers are much older. David Kahn notes in The Codebreakers that Arab scholars were the first people to systematically document cryptanalytic methods. The first known recorded explanation of cryptanalysis was given by Al Kindi (c. 801–873, also known as "Alkindus" in Europe), a 9th century Arab polymath, in Risalah fi Istikhraj al Mu'amma (A Manuscript on Deciphering Cryptographic Messages). This treatise contains the first description of the method of frequency analysis. Al Kindi is thus regarded as the first codebreaker in history. His breakthrough work was influenced by Al Khalil (717–786), who wrote the Book of Cryptographic Messages, which contains the first use of permutations and combinations to list all possible Arabic words with and without vowels. Frequency analysis is the basic tool for breaking most classical ciphers. In natural languages, certain letters of the alphabet appear more often than others; in English, "E" is likely to be the most common letter in any sample of plaintext. Similarly, the digraph "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide these statistics. For example, in a simple substitution cipher (where each letter is simply replaced with another), the most frequent letter in the ciphertext would be a likely candidate for "E". Frequency analysis of such a cipher is therefore relatively easy, provided that the ciphertext is long enough to give a reasonably representative count of the letters of the alphabet that it contains. Al Kindi's invention of the frequency analysis technique for breaking monoalphabetic substitution ciphers was the most significant cryptanalytic advance until World War II. Al Kindi's Risalah fi Istikhraj al Mu'amma described the first cryptanalytic techniques, including some for polyalphabetic ciphers, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis. He also covered methods of encipherments, cryptanalysis of certain encipherments, and statistical analysis of letters and letter combinations in Arabic. Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed secret thoughts and plans of others can be a decisive advantage. For example, in England in 1587, Mary, Queen of Scots was tried and executed for treason as a result of her involvement in three plots to assassinate Elizabeth I of England. The plans came to light after her coded correspondence with fellow conspirators was deciphered by Thomas Phelippes. In Europe during the 15th and 16th centuries, the idea of a polyalphabetic substitution cipher was developed, among others by the French diplomat Blaise de Vigenère (1523–96). For some three centuries, the Vigenère cipher, which uses a repeating key to select different encryption alphabets in rotation, was considered to be completely secure (le chiffre indéchiffrable—"the indecipherable cipher"). Nevertheless, Charles Babbage (1791–1871) and later, independently, Friedrich Kasiski (1805–81) succeeded in breaking this cipher. During World War I, inventors in several countries developed rotor cipher machines such as Arthur Scherbius' Enigma, in an attempt to minimise the repetition that had been exploited to break the Vigenère system.

Бірінші және Екінші дүниежүзілік соғыстағы шифрлар

Бірінші дүниежүзілік соғыста Циммерман телеграммасының ашылуы АҚШ-ты соғысқа тартуға елеулі үлес қосты. Екінші дүниежүзілік соғыста одақтастар Германия шифрларының, соның ішінде Энигма машинасы мен Лоренц шифрларының, сондай-ақ жапон шифрларының, әсіресе "Purple" және JN 25 шифрларының бірлескен криптоанализінен зор пайда көрді. "Ультра" барлау жүйесі Еуропа соғысының аяқталуын екі жылға дейін қысқартудан бастап, соғыстың нәтижесін анықтауға дейін барлық іске ықпал еткені айтылады. Тынық мұхитындағы соғысқа да "Magic" барлауы көмектесті. Жау хабарларының шифрларын талдау Екінші дүниежүзілік соғыста одақтастардың жеңісіне маңызды үлес қосты. Ф. В. Винтерботам соғыстың соңында батыс одақтастардың Жоғарғы қолбасшысы Дуайт Д. Эйзенхауэрдің "Ультра" барлауы одақтастардың жеңісіне "шешуші" болғанын айтқанын келтірді. Екінші дүниежүзілік соғыстағы британдық барлау қызметінің ресми тарихшысы сэр Гарри Хинсли де "Ультра" соғысты "екі жылдан кем емес, тіпті төрт жылға қысқартты" деген пікір білдірді; сонымен қатар, ол "Ультра" болмаған жағдайда соғыстың қалай аяқталатыны белгісіз болар еді деді. Іс жүзінде, жиілікті талдау статистикалық мәліметтерге де, тіл біліміне де бірдей мөлшерде сүйенеді, бірақ шифрлардың күрделілігі артқан сайын криптоанализде математиканың рөлі арта түсті. Бұл өзгеріс екінші дүниежүзілік соғысқа дейін және оның кезінде ерекше байқалды, онда Ось державаларының шифрларын бұзу үшін математикалық білімнің жаңа деңгейлері қажет болды. Бұдан өзге, автоматтандыру алғаш рет осы кезеңде криптоанализде қолданылды – польшалық Bomba құрылғысы, британдық Bombe, перфокарталық жабдықтар және Colossus компьютерлері арқылы, яғни бағдарламамен басқарылатын алғашқы электрондық цифрлық компьютерлер.

Көрсеткіш

Лоренц шифры және Екінші дүниежүзілік соғыс кезінде нацистік Германия қолданған Энигма машинасы сияқты өзара шифрлау машиналарында әрбір хабарламаның өз кілті болды. Әдетте, хабар жіберуші оператор шифрланған хабарламадан бұрын белгілі бір ашық мәтінді және/немесе шифрланған мәтінді жіберу арқылы хабарлама кілті туралы хабар қабылдаушы операторға хабардар ететін. Бұл индикатор деп аталады, себебі ол хабар қабылдаушы операторға хабарды шешу үшін машинаны қалай орнату керектігін көрсетеді. Дұрыс жобаланбаған және іске асырылмаған индикатор жүйелері алдымен поляк криптографтарына, содан кейін Блетчли Парктегі британ криптографтарына Энигма шифрлау жүйесін бұзуға мүмкіндік берді. Ұқсас дұрыс емес индикатор жүйелері британдықтарға Лоренц SZ40/42 шифрлау жүйесін анықтауға және криптоанализшілер шифрлау машинасының өзін көрмей-ақ оның хабарламаларын толыққанды бұзуға әкелген жағдайларды анықтауға мүмкіндік берді.

Асимметриялық шифрлар

Асимметриялық криптография (немесе ашық кілт криптографиясы) – екі (математикалық тұрғыдан байланысты) кілтті пайдалануға негізделген криптография; біреуі жеке, екіншісі – қоғамдық. Мұндай шифрлардың қауіпсіздігі міндетті түрде «қиын» математикалық есептерге негізделгендіктен, шабуыл жасаудың айқын жолы – сол есепті шешу әдістерін жасау болып табылады. Екі кілтті криптографияның қауіпсіздігі математикалық сұрақтарға байланысты, ал бір кілтті криптографияда мұндай байланыс көбінесе болмайды. Сонымен қатар, криптоанализ математикалық зерттеулермен жаңаша байланыстырылады. Асимметриялық схемалар әртүрлі математикалық есептерді шешудегі (болжамды) қиындықтарға сүйенеді. Егер есепті шешуге жаңа, тиімді алгоритм табылса, жүйе әлсірейді. Мысалы, Diffie–Hellman кілт алмасу схемасының қауіпсіздігі дискретті логарифмді есептеудің қиындығына байланысты. 1983 жылы Дон Копперсмит дискретті логарифмдерді (кейбір топтарда) табудың жылдамдатылған әдісін тапты, соның салдарынан криптографтар үлкенірек топтарды (немесе басқа типтегі топтарды) пайдалануға көшті. RSA қауіпсіздігі (ішінара) бүтін сандарды жіктеудің қиындығына байланысты – жіктеудегі жаңа жетістіктер RSA қауіпсіздігіне әсер етеді. 1980 жылы күрделі 50 таңбалы санды 10¹² қарапайым компьютерлік операциямен жіктеуге болады еді. 1984 жылға қарай жіктеу алгоритмдерінің жетістіктері 75 таңбалы санды 10¹² операцияда жіктеуге мүмкіндік берді. Есептеу технологиясының дамуы операцияларды әлдеқайда жылдам орындауға мүмкіндік берді. Мур заңы компьютерлердің жылдамдығы арта беретінін болжайды. Жіктеу әдістері де осылай дамуы мүмкін, бірақ олар математикалық түсінік пен шығармашылыққа көбірек тәуелді болады, ал оларды болжау мүмкін емес. RSA-да бұрын қолданылған 150 таңбалы сандар жіктелді. Бұл жоғарыда айтылғаннан гөрі көп күш-жігерді қажет етті, бірақ қазіргі заманғы жылдам компьютерлерде орынсыз емес. 21 ғасырдың басында 150 таңбалы сандар RSA үшін жеткілікті үлкен кілт өлшемі деп есептелмейтін болды. 2005 жылы бірнеше жүз таңбалы сандарды жіктеу әлі де қиын болып саналды, бірақ әдістер уақыт өте келе жақсара түсуі мүмкін, сондықтан кілт өлшемін үнемі жаңарту немесе эллипстік қисық криптографиясы сияқты басқа әдістерді пайдалану қажет. Асимметриялық схемалардың тағы бір ерекшелігі – симметриялық криптожүйелерге жасалған шабуылдардан айырмашылығы, кез келген криптоанализ ашық кілттен алынған білімді пайдалану мүмкіндігіне ие.

Asymmetric cryptography (or public key cryptography) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard" mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two key cryptography depends on mathematical questions in a way that single key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way. Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the Diffie–Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. In 1983, Don Coppersmith found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). RSA's security depends (in part) upon the difficulty of integer factorization – a breakthrough in factoring would impact the security of RSA. In 1980, one could factor a difficult 50 digit number at an expense of 1012 elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75 digit number could be factored in 1012 operations. Advances in computing technology also meant that the operations could be performed much faster. Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150 digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150 digit numbers were no longer considered a large enough key size for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such as elliptic curve cryptography to be used. Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from the public key.

Кванттық есептеуді криптоанализде қолдану

Кванттық компьютерлер, әлі де зерттеудің бастапқы сатыларында болғанымен, криптоанализде қолданылуы мүмкін. Мысалы, Шор алгоритмі үлкен сандарды полиномдық уақытта көбейткіштерге жіктеуге қабілетті, нәтижесінде, кеңінен қолданылатын ашық кілтті шифрлеудің кейбір түрлерін бұзуға болады. Кванттық компьютерде Гровер алгоритмін қолдану арқылы, күшпен кілтті табу процесін шаршылай жылдамдатуға болады. Дегенмен, мұны кілттің ұзындығын екі есеге арттыру арқылы болдырмауға болады.