Ақпаратты шифрлау және ашып шығару алгоритмі

Кіріспе

Ақпаратты шифрлау және оны шешу алгоритмі

Криптографияда шифр (немесе шифрлау) – ақпаратты шифрлау немесе оны шешу алгоритмі, яғни процедура ретінде орындалатын нақты қадамдар тізбегі. Шифрлау – бұл сирек қолданылатын термин. Шифрлау немесе кодтау – ақпаратты шифрға немесе кодқа түрлендіру. Көне тілде «шифр» мен «код» сөздерінің мағынасы бірдей, себебі екеуі де хабарды шифрлейді; алайда, криптографияда, әсіресе классикалық криптографияда, бұл ұғымдар ерекшеленеді. Кодтар көбінесе шығыстағы әртүрлі ұзындықтағы символдар тізбесін алмастырады, ал шифрлар әдетте кіретін символдардың санымен бірдей символдарды алмастырады. Код бір ұғымды екінші ұғыммен байланыстырады. Сөздер мен сөз тіркестері әріптермен немесе сандармен кодталуы мүмкін. Кодтар әдетте кірістен кілтке дейін тікелей мағынаны сақтайды. Кодтардың негізгі функциясы – уақытты үнемдеу. Шифрлар алгоритмдік болып табылады. Берілген кіріс шифрдың шешілу процесін орындауы тиіс. Шифрлар көбінесе жазбаша ақпаратты шифрлеу үшін қолданылады. Кодтар үлкен код кітабы арқылы жұмыс істейді, ол символдардың немесе сандардың кездейсоқ тізбегін сөзбен немесе сөз тіркесімен байланыстырады. Мысалы, «UQJHSE» дегені «Келесі координаттарға өтіңіз» деген код болуы мүмкін. Шифр қолданғанда бастапқы ақпарат – ашық мәтін, ал шифрланған түрі – шифрланған мәтін деп аталады. Шифрланған мәтінде ашық мәтіннің барлық ақпараты сақталады, бірақ оны тиісті механизмсіз адам немесе компьютер оқи алмайды. Шифрдің жұмысы көбінесе кілт деп аталатын қосымша ақпаратқа (немесе NSA терминологиясында криптоайнымалы) тәуелді болады. Шифрлеу процедурасы кілтке байланысты өзгереді, бұл алгоритмнің жұмысын өзгертеді. Шифрды қолдану алдында кілтті таңдау қажет. Кілтті білмесе, шифрланған мәтінді оқылатын ашық мәтінге шешу өте қиын, тіпті мүмкін емес. Қазіргі шифрларды бірнеше түрге бөлуге болады:

In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography. Codes generally substitute different length strings of characters in the output, while ciphers generally substitute the same number of characters as are input. A code maps one meaning with another. Words and phrases can be coded as letters or numbers. Codes typically have direct meaning from input to key. Codes primarily function to save time. Ciphers are algorithmic. The given input must follow the cipher's process to be solved. Ciphers are commonly used to encrypt written information. Codes operated by substituting according to a large codebook which linked a random string of characters or numbers to a word or phrase. For example, "UQJHSE" could be the code for "Proceed to the following coordinates." When using a cipher the original information is known as plaintext, and the encrypted form as ciphertext. The ciphertext message contains all the information of the plaintext message, but is not in a format readable by a human or computer without the proper mechanism to decrypt it. The operation of a cipher usually depends on a piece of auxiliary information, called a key (or, in traditional NSA parlance, a cryptovariable). The encrypting procedure is varied depending on the key, which changes the detailed operation of the algorithm. A key must be selected before using a cipher to encrypt a message. Without knowledge of the key, it should be extremely difficult, if not impossible, to decrypt the resulting ciphertext into readable plaintext. Most modern ciphers can be categorized in several ways:

Олар белгілі бір мөлшердегі символдар блогында (блок шифрлары) немесе үздіксіз символдар ағынында (ағын шифрлары) жұмыс істейді. Шифрлеу және оны шешу үшін бірдей кілт қолданыла ма (симметриялық кілт алгоритмдері), әлде әрқайсысы үшін әртүрлі кілт қолданыла ма (асимметриялық кілт алгоритмдері). Алгоритм симметриялық болса, кілт алушы мен жіберушіге ғана белгілі болуы керек. Алгоритм асимметриялық болса, шифрлеу кілті оны шешу кілтінен өзгеше, бірақ оған тығыз байланысты. Егер бір кілтті екіншісінен анықтау мүмкін болмаса, асимметриялық кілт алгоритмінде ашық/жеке кілт қасиеттері болады және кілттердің бірін құпиялылықты бұзбай жариялауға болады.

Этимология

Араб тіліндегі нөлді білдіретін "صفر" (sifr) сөзінен пайда болған "сифр" сөзі, орта ғасырларда араб сандары жүйесінің бір бөлігі ретінде Еуропаға тарады. Римдік сандар жүйесінде нөл ұғымы болмағандықтан, математиканың дамуы шектелді. Осы кезеңде сөз ортағасырлық латын тілінде "cifra", ал кейін орта француз тілінде "cifre" деп қабылданды. Содан кейін ол ағылшын тілінде "cipher" (кейде "cypher" деп те жазылады) сөзіне айналды. Терминнің шифрлаумен байланыстыруына қатысты бір теория бар: нөл ұғымы еуропалықтарға түсініксіз болғандықтан, бұл термин оңай түсінілмейтін хабарламаны немесе қатынасты білдірген. Кейін "cipher" термині кез келген араб цифрын немесе оларды қолдана отырып есептеуді білдіру үшін де қолданылды. Сондықтан, мәтінді араб цифрларымен шифрлау – мәтінді сөзбе-сөз "цифрға" айналдыру болып табылады.

Кодтармен салыстырғанда

Кездейсоқ жағдайларда "код" және "шифр" сөздерін көбінесе бір-бірінің орнына қолдануға болады; алайда, бұл сөздердің техникалық мағыналары әртүрлі ұғымдарды білдіреді. Кодтар мағынаны сақтайды; сөздер мен тіркестер сандарға немесе символдарға сәйкес келеді, нәтижесінде хабар қысқарады. Мысалы, коммерциялық телеграф кодын қарастырайық, ол телеграммалар арқылы коммерциялық келісімдер жасаудан туындаған ұзақ телеграммалық хабарламаларды қысқарту үшін қолданылған. Тағы бір мысал – бүкіл сөзді шифрлеу, ол пайдаланушыға толық сөзді символмен немесе таңбамен алмастыруға мүмкіндік береді, дәл сол сияқты жапон тіліндегі жазу жүйесіндегі Канжи (яғон тілінде қытай таңбаларын білдіреді) таңбалары, дыбырлық япон жазуын толықтырады. Мысалы, ағылшын тілінде "The quick brown fox jumps over the lazy dog" фразасын "The quick brown 狐 jumps 上 the lazy 犬" деп ауыстыруға болады. Стенографтар кейде бүкіл сөздерді қысқарту үшін арнайы символдарды қолданады. Шифрлар, керісінше, төменгі деңгейде жұмыс істейді: жеке әріптер, әріптердің шағын топтары немесе, қазіргі жүйелерде, жеке биттер мен биттер блогы деңгейінде. Кейбір жүйелерде кодтар мен шифрлар бірдей жүйеде қолданылады, қауіпсіздікті арттыру үшін супершифрлеу қолданылады. Кейбір жағдайларда "код" және "шифр" терминдері тиісінше "ауыстыру" және "транспозиция" сөздерімен синоним ретінде қолданылады. Тарихи тұрғыдан криптография кодтар мен шифрлардың екіге бөлінуіне негізделген, ал кодтаудың шифрларға ұқсас терминологиясы болды: "кодтау, кодталған мәтін, декодтау" және т.б. Алайда, кодтардың бірнеше кемшіліктері бар, оның ішінде криптоанализге осалдығы және ауыр кодтар кітабын басқарудың қиындығы. Осы себепті, кодтар қазіргі заманғы криптографияда қолданылымнан шығып, шифрлар басым техникаға айналды.

Түрлері

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

Тарихи

Цезарь шифры – ең ежелгі криптографиялық жүйелердің бірі. Юлий Цезарь шамамен б.з.б. 50 жылы Маркус Туллий Цицеронға хат жазу үшін алфавиттегі әріптерді үш позицияға жылдырып, қалған әріптерді басына ораған шифрды қолданды. [11] Бұрын қолданылған тарихи қалам мен қағаз шифрлары кейде классикалық шифрлар деп аталады. Оларға қарапайым ауыстыру шифрлары (мысалы, ROT13) және транспозиция шифрлары (мысалы, теміржол қоршауы шифры) кіреді. Мысалы, "GOOD DOG" сөзі "PLLX XLP" деп шифрлануы мүмкін, онда "L" әрпі "O" әрпін, "P" әрпі "G" әрпін, ал "X" әрпі "D" әрпін алмастырады. "GOOD DOG" сөзінің әріптерін транспозициялау "DGOGDOO" нәтижесін береді. Бұл қарапайым шифрларды және мысалдарды, тіпті ашық мәтін мен шифрленген мәтін жұптары болмаса да, бұзу оңай. 1640 жылдары парламенттік қолбасшы, Манчестердің 2-ші графы Эдвард Монтегю, Англия азаматтық соғысы кезінде өзінің одақтастарына кодталған хабарлар жіберу үшін шифрлар жасады. Қарапайым шифрлар полиалфавиттік ауыстыру шифрларымен (мысалы, Виженер шифры) алмастырылды, олар әр әріп үшін ауыстыру алфавитін өзгертеді. Мысалы, "GOOD DOG" сөзі "PLSX TWF" деп шифрлануы мүмкін, онда "L", "S" және "W" әріптері "O" әрпін алмастырады. Белгілі немесе шамаланған ашық мәтіннің аз ғана мөлшері болғанда да, қарапайым полиалфавиттік ауыстыру шифрларын және қалам мен қағаз шифрлау үшін жасалған әріптерді транспозициялау шифрларын бұзу оңай. Бір реттік блокнотқа негізделген қауіпсіз қалам мен қағаз шифрын жасау мүмкін, бірақ олардың басқа кемшіліктері де бар. 20-шы ғасырдың басында шифрлау мен дешифрлеуді жүзеге асыру үшін транспозиция, полиалфавиттік ауыстыру және "қосымша" ауыстыру түрлерін пайдаланатын электромеханикалық машиналар ойлап табылды. Роторлық машиналарда бірнеше роторлық дискілер полиалфавиттік ауыстыруды қамтамасыз етті, ал қосымша тақталар басқа ауыстыруды қамтамасыз етті. Роторлық дискілер мен қосымша тақтадағы сымдарды ауыстыру арқылы кілттерді оңай өзгертуге болады. Бұл шифрлау әдістері бұрынғы схемаларға қарағанда күрделірек болған және шифрлау мен дешифрлеу үшін машиналар қажет болғанмен, осы шифрлау әдістерін бұзу үшін британдық Bombe сияқты басқа машиналар да ойлап табылды.

The Caesar Cipher is one of the earliest known cryptographic systems. Julius Caesar used a cipher that shifts the letters in the alphabet in place by three and wrapping the remaining letters to the front to write to Marcus Tullius Cicero in approximately 50 BC. [11]

Historical pen and paper ciphers used in the past are sometimes known as classical ciphers. They include simple substitution ciphers (such as ROT13) and transposition ciphers (such as a Rail Fence Cipher). For example, "GOOD DOG" can be encrypted as "PLLX XLP" where "L" substitutes for "O", "P" for "G", and "X" for "D" in the message. Transposition of the letters "GOOD DOG" can result in "DGOGDOO". These simple ciphers and examples are easy to crack, even without plaintext ciphertext pairs. In the 1640s, the Parliamentarian commander, Edward Montagu, 2nd Earl of Manchester, developed ciphers to send coded messages to his allies during the English Civil War. Simple ciphers were replaced by polyalphabetic substitution ciphers (such as the Vigenère) which changed the substitution alphabet for every letter. For example, "GOOD DOG" can be encrypted as "PLSX TWF" where "L", "S", and "W" substitute for "O". With even a small amount of known or estimated plaintext, simple polyalphabetic substitution ciphers and letter transposition ciphers designed for pen and paper encryption are easy to crack. It is possible to create a secure pen and paper cipher based on a one time pad, but these have other disadvantages. During the early twentieth century, electro mechanical machines were invented to do encryption and decryption using transposition, polyalphabetic substitution, and a kind of "additive" substitution. In rotor machines, several rotor disks provided polyalphabetic substitution, while plug boards provided another substitution. Keys were easily changed by changing the rotor disks and the plugboard wires. Although these encryption methods were more complex than previous schemes and required machines to encrypt and decrypt, other machines such as the British Bombe were invented to crack these encryption methods.

Кілттің көлемі мен осалдық

Таза математикалық шабуылда (яғни шифрды бұзуға көмектесетін басқа ақпараттың болмауы) ең басты екі фактор қарастырылады:

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