Көп әріптік ауыстыру шифрінің тарихы

Кіріспе

Көп алмастыру жазу жүйесі шифры

Полиалфавиттік шифр – бірнеше алмастыру алфавиттерін қолданатын алмастыру шифры. Виженер шифры – полиалфавиттік шифрдың ең белгілі мысалы, бірақ ол қарапайымдатылған ерекше жағдай. Энигма машинасы күрделірек, бірақ ол негізінен полиалфавиттік алмастыру шифры болып табылады.

Тарих

Аль Калкашандидің (1355–1418) еңбегі, Ибн әл-Дурахимнің (1312–1359) бұрынғы еңбегіне негізделген, шифрларды ауыстыру және орналастыру туралы алғашқы жарияланған талқылауды, сондай-ақ әрбір қарапайым мәтін әрпіне бірнеше алмастыру белгілері тағайындалған полиалфавиттік шифрдың алғашқы сипаттамасын қамтиды. Дегенмен, полиалфавиттік шифрлар араб криптологы әл-Кинди (801–873) тарапынан ғасырлар бұрын жасалған болуы мүмкін деген пікір бар. Леон Баттиста Альбертидің шамамен 1467 жылы жасаған Альберти шифры – полиалфавиттік шифрдың ерте түрі. Альберти хабарды шифрлеу үшін аралас әліпбиді қолданды, бірақ қалауынша басқа әліпбиге ауысып, осы ауысуды үлкен әріп немесе сан енгізу арқылы көрсететін. Осы шифрлеу үшін Альберти декодер құрылғысын – шифрлеу дискісін пайдаланды, ол аралас әліпбилерді қолдана отырып полиалфавиттік алмастыруды жүзеге асырды. Иоганн Тритемий өзінің 1518 жылы қайтыс болғаннан кейін жарық көрген «Полиграфияның алты кітабы» (Polygraphiae libri sex) атты кітабында Тритемий шифры деп аталатын прогрессивті кілтті полиалфавиттік шифрды ойлап тапты. Альберти шифрынан айырмашылығы, ол әліпбилерді кездейсоқ интервалмен ауыстырды, ал Тритемий хабардың әр әрпі үшін әліпбиді ауыстырды. Ол 26 әріптен тұратын (латын тілінде жазғандықтан Тритемий 24 әріп қолданды) тіктөртбұрышты кестеден (tabula recta) бастады. Әрбір әліпби жоғарыдағыдан бір әріпке солға қарай жылдырылды және Z әрпіне жеткеннен кейін қайтадан A-дан басталды (кестеге қараңыз). Тритемийдің идеясы хабардың бірінші әрпін бірінші жылдырылған әліпби арқылы шифрлеу болды, сондықтан A-дан B, B-дан C және т.б. шықты. Хабардың екінші әрпі екінші жылдырылған әліпби арқылы шифрленді және т.б. Альбертидің шифрлеу дискісі де дәл осы схеманы қолданды. Онда екі әліпби болды: біреуі бекітілген сыртқы сақинада, екіншісі айналатын дискіде. Әріпті шифрлеу үшін сыртқы сақинадағы әріп ізделіп, дискідегі оның астындағы әріп ретінде кодталады. Диск A-дан B-ның астында басталып, пайдаланушы әр әріпті шифрлегеннен кейін дискіні бір әріпке бұрады. Шифрді бұзу оңай болды, ал Альбертидің машиналық іске асыруы одан да қиын емес. Екі жағдайда да кілттік прогрессия шабуылдаушылардан жақсы жасырылмады. Тіпті Альбертидің полиалфавиттік шифрын іске асыруы да оңай болды (үлкен әріп криптоаналитик үшін маңызды көрсеткіш). Келесі бірнеше жүз жыл бойы көптеген алмастыру әліпбилерін пайдаланудың маңыздылығына көбісі назар аударған жоқ. Полиалфавиттік алмастыру шифрын жасаушылар бірнеше әліпбиді таңдауды жасыруға (қажет болған жағдайда қайталау арқылы) көбірек назар бөлген сияқты, көптеген әліпбилерді пайдалану және ешқайсысын қайталамау арқылы мүмкін болатын қауіпсіздікті арттыруға емес. Бұл принцип (әсіресе Альбертидің шексіз қосымша алмастыру әліпбилері) – жиілік талдауы жасалғаннан бері бірнеше жүз жыл ішіндегі ең маңызды жетістік болды. Дұрыс іске асырылса (және, соңғы кезде жүзеге асырылғанда) бұзуы әлдеқайда қиын болар еді. Тек 19 ғасырдың ортасында (Крым соғысы кезінде Бэббидждің құпия жұмысы және Фридрих Касискидің бірнеше жылдан кейін жарияланған, оған теңдесетін ашық хабарламасы) жақсы іске асырылған полиалфавиттік шифрларды криптоанализ жасауға қол жеткізілді. Касискинің зерттеуін қараңыз.

The work of Al Qalqashandi (1355–1418), based on the earlier work of Ibn al Durayhim (1312–1359), contained the first published discussion of the substitution and transposition of ciphers, as well as the first description of a polyalphabetic cipher, in which each plaintext letter is assigned more than one substitute. However, it has been claimed that polyalphabetic ciphers may have been developed by the Arab cryptologist Al Kindi (801–873) centuries earlier. The Alberti cipher by Leon Battista Alberti around 1467 was an early polyalphabetic cipher. Alberti used a mixed alphabet to encrypt a message, but whenever he wanted to, he would switch to a different alphabet, indicating that he had done so by including an uppercase letter or a number in the cryptogram. For this encipherment Alberti used a decoder device, his cipher disk, which implemented a polyalphabetic substitution with mixed alphabets. Johannes Trithemius—in his book Polygraphiae libri sex (Six books of polygraphia), which was published in 1518 after his death—invented a progressive key polyalphabetic cipher called the Trithemius cipher. Unlike Alberti's cipher, which switched alphabets at random intervals, Trithemius switched alphabets for each letter of the message. He started with a tabula recta, a square with 26 letters in it (although Trithemius, writing in Latin, used 24 letters). Each alphabet was shifted one letter to the left from the one above it, and started again with A after reaching Z (see table). Trithemius's idea was to encipher the first letter of the message using the first shifted alphabet, so A became B, B became C, etc. The second letter of the message was enciphered using the second shifted alphabet, etc. Alberti's cipher disk implemented the same scheme. It had two alphabets, one on a fixed outer ring, and the other on the rotating disk. A letter is enciphered by looking for that letter on the outer ring, and encoding it as the letter underneath it on the disk. The disk started with A underneath B, and the user rotated the disk by one letter after encrypting each letter. The cipher was trivial to break, and Alberti's machine implementation not much more difficult. Key progression in both cases was poorly concealed from attackers. Even Alberti's implementation of his polyalphabetic cipher was rather easy to break (the capitalized letter is a major clue to the cryptanalyst). For most of the next several hundred years, the significance of using multiple substitution alphabets was missed by almost everyone. Polyalphabetic substitution cipher designers seem to have concentrated on obscuring the choice of a few such alphabets (repeating as needed), not on the increased security possible by using many and never repeating any. The principle (particularly Alberti's unlimited additional substitution alphabets) was a major advance—the most significant in the several hundred years since frequency analysis had been developed. A reasonable implementation would have been (and, when finally achieved, was) vastly harder to break. It was not until the mid 19th century (in Babbage's secret work during the Crimean War and Friedrich Kasiski's generally equivalent public disclosure some years later), that cryptanalysis of well implemented polyalphabetic ciphers got anywhere at all. See Kasiski examination.