Циклометр Реевски: польское устройство 1934-35гг для взлома шифров Enigma. Предшественник Bombe, помог расшифровать немецкие коды во Второй мировой войне.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Криптологиялық құрылғы
криптологиялық құрылғы
Cryptologic device
the cryptologic device
Циклометр – "шамамен 1934 немесе 1935 жылы" Польша шифрлау бюросының неміс бөлімінен (BS 4) Мариан Реевски жасаған, Enigma пермутацияларының циклдық құрылымын тізімдеуге арналған криптологиялық құрылғы. Осы арқылы неміс Enigma шифрмәтінің шифрлануын жеңілдетуге мүмкіндік берді. Реевскидің кейінгі криптологиялық бомбасымен бірге, оны Англиядағы Блетчли Паркте соғыс жылдарында Enigma шифрларын бұзуға көмектесетін Bombe құрылғысының алдағысы ретінде қарастыруға болады. 2019 жылы Кембридж университетінің Инженерлік факультетінің Хэл Эванс және Тим Флэк жасаған суреттер негізінде циклометрдің жұмыс істейтін үлгісі құрастырылды.
The cyclometer was a cryptologic device designed, "probably in 1934 or 1935," by Marian Rejewski of the Polish Cipher Bureau's German section (BS 4), to catalog the cycle structure of Enigma permutations, thereby facilitating the decryption of German Enigma ciphertext. With Rejewski's later cryptologic bomb, it can be viewed as a predecessor to the Bombe that was to help break Enigma ciphers later in the war at Bletchley Park in England. Using drawings made by Rejewski, Hal Evans and Tim Flack at the Department of Engineering, University of Cambridge, in 2019 constructed a working version of the cyclometer.
Мариан Реевски
Мариан Реевскийдің Познань университетінде математика оқуы кезінде Польша шифрлау бюросы оны және басқа математика студенттерін, соның ішінде Джерзи Рожицкий мен Генрик Зигальскиді криптология бойынша бюроның қаржылаған курсына қабылдады. Кейіннен Бюро кейбір студенттерді уақытша жергілікті бюро кеңсесінде жартылай жұмыс істеуге тартты. Познань университетін бітіргеннен кейін, Геттинген университетінде Реевски екі жылдық актуарлық статистика курсының бірінші жылын аяқтады, сосын Познаньға оралды. 1932 жылдың қыркүйегінде ол, Рожицкий және Зигальский Варшаваға Шифрлау бюросында толық уақыт жұмыс істеу үшін кетті. 1932 жылдың желтоқсанында Шифрлау бюросы Реевскиге неміс Enigma шифрлау машинасымен жұмыс істеуді тапсырды. Бюро оны бұзуға тырысып, бірақ сәтті болмады. Бірнеше апта ішінде Реевски машинаны қайта құруға қол жеткізді. Неміс Enigma хабарламаларының процедуралары жиі қолданылатын, құпия күнделікті машина параметрлерін пайдаланды, сонымен қатар шифрлаушыдан жеке үш әріптен тұратын хабарлама кілтін таңдауды қажет етті. Мысалы, шифрлаушы "ABL" дегенді хабарлама кілті ретінде таңдауы мүмкін. Хабарлама кілті хабарды шифрлау немесе шешу кезінде роторлардың бастапқы орнын белгілеу үшін қолданылды. Жеке хабарлама кілтін таңдау – қауіпсіздік шарасы болды: ол күні бойы барлық хабарламаларды бірдей полиалфавиттік кілтті пайдаланып жіберуден сақтады, бұл хабарламаларды полиалфавиттік шабуылға осал ететін еді. Дегенмен, хабарды жіберуші кілтті алушыға жеткізуі керек болды, сонда ғана ол хабарды шеше алатын еді. Хабарлама кілті алдымен сол күнгі Grundstellung (Enigma роторларының құпия бастапқы орны, мысалы, "FOL") арқылы шифрланды. Байланыс кейде бұрмаланып, егер хабарлама кілті бұрмаланса, алушы хабарламаны шеше алмайтын еді. Сондықтан немістер хабарлама кілтін екі рет жіберуді қадағалады; егер бұрмалану болса, алушы хабарлама кілтін таба алатын еді. Осы жерде немістер маңызды қателік жасады. Шифрланған хабарлама кілтін (мысалы, "PKP") "PKP PKP" алу үшін екі рет жіберудің орнына, олар хабарлама кілтін екі еселеді (мысалы, "ABL ABL"), екі еселенген кілтті шифрлап ("PKP JXI") алды және шифрланған екі еселенген кілтті жіберді. Бұл қателік Реевскиге Enigmaның алты тізбектік ауысуын анықтауға және олардың бірдей кілтпен шифрланғанын пайдалануға мүмкіндік берді. Коммерциялық Enigma машинасының көмегімен, француз тыңшысы Ханс Тило Шмидт алған неміс материалдары және нашар кілттерді таңдаған неміс шифрлаушыларының көмегімен Реевски Enigma роторлары мен рефлекторының сымдарын кері инженерлік жолмен анықтай алды. Шифрлау бюросы неміс хабарламаларын шешу үшін бірнеше поляк Enigma машиналарын жасады.
During Marian Rejewski's mathematics studies at Poznań University, the Polish Cipher Bureau recruited him and some other mathematics students, including Jerzy Różycki and Henryk Zygalski, to take a Bureau sponsored course on cryptology. The Bureau later hired some of the students to work part time at a temporary local Bureau office. After graduating from Poznań University, at the University of Göttingen Rejewski completed the first year of a two year actuarial statistics course, then returned to Poznań. In September 1932 he, Różycki, and Zygalski went to Warsaw to work full time for the Cipher Bureau. In December 1932 Rejewski was tasked by the Cipher Bureau to work on the German Enigma cipher machine. The Bureau had attempted, but had failed, to break it. Within a few weeks, Rejewski managed to reconstruct the machine. The German Enigma message procedures used common, secret daily machine settings, but also required a cipher clerk to choose an individual three letter message key. Thus, a clerk might choose "ABL" as the message key. The message key was used to set the initial position of the rotors when enciphering or deciphering the message. Choosing an individual message key was a security measure: it avoided having all the day's messages sent using the same polyalphabetic key, which would have made the messages vulnerable to a polyalphabetic attack. However, the sender needed to communicate the message key to the recipient in order for the latter to decipher the message. The message key was first encrypted using the day's Grundstellung (a secret initial position of the Enigma's rotors, e. g., "FOL"). Communications were sometimes garbled, and if the message key were garbled, the recipient would be unable to decrypt the message. Consequently the Germans took the precaution of sending the message key twice; if there was a garble, the recipient should be able to find the message key. Here the Germans committed a crucial error. Instead of sending the encrypted message key (e. g., "PKP") twice to get "PKP PKP", they doubled the message key (e. g., "ABL ABL"), encrypted the doubled key to get ("PKP JXI"), and sent the encrypted doubled key. That mistake allowed Rejewski to identify six sequential permutations of the Enigma and exploit the knowledge that they encrypted the same message key. With the help of a commercial Enigma machine, German materials obtained by French spy Hans Thilo Schmidt, and German cipher clerks who chose weak keys, Rejewski was able to reverse engineer the wiring of the Enigma's rotors and reflector. The Cipher Bureau then built several Polish Enigma doubles that could be used to decrypt German messages.
Грилл әдісі
Реевски бұл цикл ақпаратын және код жазушылардың шалаңдық әдеттерін пайдаланып, гриль әдісі арқылы жеке пермутацияларды – А, В, С, Д, Е, Ф табуға мүмкіндік алды, бірақ бұл әдіс еңбекке толы болды. Грильді қолданғаннан кейін поляктар оң жақ ротордың орнын, плагиндік қосылымдарды және Q (рефлектор мен қалған екі ротордың пермутациясын) біле алатын болды. Күнделікті кілтті алу үшін поляктарға әлі де көп жұмыс жасау қажет еді, және бұл жұмысқа екі сол жақ ротордың орнын және Грундстангты табу үшін барлық мүмкін комбинацияларды сынап қарау кіруі мүмкін. Поляктар гриль әдісінің бір бөлігін жеңілдету үшін Q каталогын қолдана бастады; бұл каталогта 4056 жазба болды (26 × 26 × 6). Сақиналардың орналасуын анықтау үшін гриль әдісі 17 576 мүмкіндікті сынап көруді қажет етеді. Гриль әдісі 1936 жылдың 1 қазанына дейін тиімді жұмыс істеді, сол күні немістер алты стекерді (плагиндік қосылымдарды) қолдануды тоқтатып, орнына бесеуден сегізге дейін стекер қолдана бастады. Көбірек стекерлер гриль әдісіне кедергі келтіруі мүмкін.
Rejewski could use this cycle information and some sloppy habits of code clerks to figure out the individual permutations A B C D E F using the grill method, but that method was tedious. After using the grill, the Poles would know the rightmost rotor and its position, the plugboard connections, and Q (the permutation of the reflector and other two rotors). In order to get the daily key, the Poles would still have a lot of work to do, and that work could entail trying all possible orders and positions for the two left rotors to find the position for the Grundstellung. The Poles started using a Q catalog to make part of the grill method easier; that catalog had 4,056 entries (26 × 26 × 6). To find the ring settings, the grill method could require trying 17,576 possibilities. The grill method worked well until 1 October 1936, the day the Germans stopped using six steckers (plugboard connections) and started using five to eight steckers. More steckers could frustrate the grill method.
Цикл ұзындығы
Каталогты нақты циклдар бойынша индекстеудің орнына, поляктар циклдардың ұзындығы бойынша индекстеуді ойлап тапты. Плагборд пермутациядағы әріптердің идентификациясын өзгерткенімен, циклдардың ұзындығын өзгертпеді. Көрініп тұрғанындай, индикаторлық пермутацияның цикл ұзындықтары үшін 101 мүмкін үлгі бар. Карактеристикадағы үш пермутацияны ескергенде, цикл ұзындығының шамамен бір миллион комбинациясы болуы мүмкін. Осының салдарынан цикл ұзындықтарын 105,456 мүмкін комбинациялардың хэш-кестесіне хэш-функция ретінде қолдануға болады. Поляктар күндізгі трафикті қарап, индикатордың карактеристикасын анықтап, содан кейін карта каталогында іздейтін. Ықтималдық жоғары, тек бір (немесе бірнеше) картада осы цикл ұзындықтары болар еді. Нәтижесінде, роторлардың дұрыс ретін және олардың барлық позицияларын көп еңбекті жұмсамай анықтауға болар еді. Бұл әдіс гриль әдісінен қарапайым болды және көптеген штекерлер болғанда да жұмыс істеді.
Instead of indexing the catalog by the actual cycles, the Poles hit upon indexing the catalog by the length of the cycles. Although the plugboard changed the identity of the letters in the permutation, the plugboard did not change the lengths of the cycles. It turns out there are 101 possible patterns for the cycle lengths of an indicator permutation. With the three permutations in the characteristic, there are about one million possible cycle length combinations Consequently, the cycle lengths could be used as a hash function into a hash table of the 105,456 possible combinations. The Poles would look at the day's traffic, recover the characteristic of the indicator, and then look in the card catalog. The odds would be good that only one (or maybe a few) cards had those cycle lengths. The result would be the appropriate rotor order and the positions of all the rotors without much work. The method was simpler than the grill method and would work when there were many steckers.
Каталогты құру
Циклометр роторлардың берілген тізбегі үшін роторлардың барлық 17 576 позициясы бойынша "сипаттамаларының" циклдерінің ұзындығы мен санын каталогтау үшін қолданылды. Мұндай алты мүмкін тізбек болғандықтан, алынған "сипаттамалар каталогы" немесе "карта каталогы" барлығы (6) (17 576) = 105 456 жазбадан тұрды. Реевски жазғандай, карта каталогының пайдалылығы немістердің Enigma машиналарын қолданатын плагтік қосылымдардың санына (және хабарлама кілттерін қалпына келтіруге) тәуелсіз болды. Каталогты дайындау "еңбекке толы және бір жылдан астам уақыт алды, бірақ ол дайын болғаннан кейін күнделікті кілттерді шамамен он бес минут ішінде алуға болады еді". Алайда, 1937 жылдың 1 қарашасында немістер "кері айналдыру барабанын" немесе "рефлекторды" өзгертті. Бұл Шифр бюросын жаңа карта каталогымен қайта бастауға мәжбүр етті, "бұл міндет", - деп жазады Реевски, "біздің үлкен тәжірибеміздің арқасында, шамамен бір жылдан кем уақыт алды". Бірақ 1938 жылдың 15 қыркүйегінде немістер хабарлама кілттерін шифрлеу процедурасын толығымен өзгертті, нәтижесінде карта каталогы әдісі толығымен қолданусыз болды.
The cyclometer was used to prepare a catalog of the length and number of cycles in the "characteristics" for all 17,576 positions of the rotors for a given sequence of rotors. Since there were six such possible sequences, the resulting "catalog of characteristics," or "card catalog," comprised a total of (6) (17,576) = 105,456 entries. The utility of the card catalog, writes Rejewski, was independent of the number of plug connections being used by the Germans on their Enigma machines (and of the reconstruction of message keys). Preparation of the catalog "was laborious and took over a year, but when it was ready daily keys [could be obtained] within about fifteen minutes." On November 1, 1937, however, the Germans changed the "reversing drum," or "reflector." This forced the Cipher Bureau to start anew with a new card catalog, "a task," writes Rejewski, "which consumed, on account of our greater experience, probably somewhat less than a year's time." But then, on September 15, 1938, the Germans changed entirely the procedure for enciphering message keys, and as a result the card catalog method became completely useless.