Cifrele clasice de permutare. Permutările rutei

Un tip de permutare a rutei - permutarea verticală - a devenit larg răspândit. Acest cifru folosește și un tabel dreptunghiular în care mesajul este scris în rânduri de la stânga la dreapta. Cifragrama este scrisă vertical, cu coloanele selectate în ordinea determinată de cheie.

TEXT CLEAR: exemplu de permutare a rutei

CHEIE: (3, 1, 4, 2, 5)

CRIPTOGRAMA: rmuptkmrnrnrnprrysviateaeshoeo

Nu este recomandabil să completați ultimul rând al tabelului cu litere „nefuncționale”, deoarece criptoanalistul care a primit această criptogramă primește informații despre lungimea cheii numerice.

Cifru cu permutare verticală. Este o variație a cifrului anterior. Caracteristicile cifrului includ următoarele:

Numărul de coloane din tabel este fix și determinat de lungimea cheii;

Calea de intrare este strict de la stânga la dreapta, de sus în jos;

Cifragrama este scrisă în coloane în conformitate cu numerotarea lor (cheia).

Fig.5.5. Un exemplu de utilizare a unui cifr cu permutare verticală

Puteți folosi un cuvânt sau o expresie ca cheie. Apoi, ordinea în care sunt scrise coloanele corespunde ordinii alfabetice a literelor din cheie. De exemplu, dacă cuvântul cheie este „UNCLE”, atunci litera prezentă în el O primește numărul 1, D– 2 etc. Dacă o literă apare de mai multe ori într-un cuvânt, aparițiile sale sunt numerotate succesiv de la stânga la dreapta. În exemplu, prima literă D primește numărul 2, al doilea D – 3.

La criptarea mesajului „ABRAMOV ILYA SERGEEVIC” rezultatul va fi „OYAE_AV_ERIEIALRCHMG_B_SV”.

Această metodă constă în faptul că caracterele textului criptat sunt rearanjate după anumite reguli în cadrul blocului de caractere criptat. Să ne uităm la unele dintre cele mai comune varietăți ale acestei metode care pot fi utilizate în sistemele automate.

Cea mai simplă permutare este să scrieți textul original înapoi și, în același timp, să despărțiți cifra cifrată în cinci litere. De exemplu, din fraza:

LĂSAȚI SĂ FIE CEL NE-AM DORIT

obțineți următorul text cifrat:

ILETO KHIMKA KKATT EDUB TSUP

Ultimul grup (cinci) îi lipsește o literă. Aceasta înseamnă că înainte de a cripta expresia originală, aceasta ar trebui completată cu o literă nesemnificativă (de exemplu, O) la un număr care este un multiplu de cinci:

LET-FI-TAKKA-KMYKHO-TELIO.

Apoi, cifra cifrată, în ciuda unei astfel de modificări minore, va arăta diferit:

OILET OKHYMK AKKAT TEDUB LTSUP

Nu pare nimic complicat, dar decriptarea va cauza neplăceri serioase.

În timpul războiului civil american, s-a folosit următorul cod: fraza originală a fost scrisă în mai multe rânduri. De exemplu, câte cincisprezece litere (completând ultima linie cu litere fără sens).

După aceasta, coloanele verticale au fost scrise în ordine într-o linie împărțită în cinci litere:

PKUMS YTHIO BTUED LEITK TLAMK NCOAP

O variantă a acestui cifrat: mai întâi scrieți fraza originală în coloane:

Apoi împărțiți rândurile în cinci litere:

PSYUE TKAMH TLAVD UTBDT AKKYO EIBGE

Dacă scurtăm liniile și le creștem numărul, obținem zăbrele dreptunghiulare,în care puteți scrie textul sursă. Dar aici sunt deja necesare acorduri preliminare între destinatar și expeditorul mesajelor, deoarece grila în sine poate fi de lungimi și înălțimi diferite, puteți scrie în ea în rânduri, în coloane, într-o spirală acolo sau într-o spirală înapoi, de asemenea, puteți scrie de-a lungul diagonalelor și, pentru criptare, puteți lua, de asemenea, diferite direcții. În general, există o mulțime de opțiuni.

De exemplu, să luăm o grilă de 6x6 (și numărul de linii poate crește sau descrește în funcție de lungimea mesajului original) și să o umplem linie cu linie:

Dacă criptați de-a lungul săgeților (diagonalelor) de sus în jos din colțul din stânga sus, veți ajunge cu următoarea cifrogramă:

P UU SDK TECH LTAOA BTKTBM AMEVL YLGK IDI EZ ZH

Pentru proiectarea finală, textul cifrat poate fi împărțit în grupuri de 6 caractere:

PUUSDK TEKKHT AOABTK TBMAME VLYLGK IDIEZZH

Permutările cu cheie sunt adesea folosite. Apoi regulile pentru completarea grilei și criptarea din aceasta sunt simplificate și devin standard. Singurul lucru pe care trebuie să-l amintești și să-l cunoști este cheia, care poate fi orice cuvânt, de exemplu, RADIATOR. În conformitate cu aranjarea literelor din alfabet, litera A primește numărul 1, a doua literă A - 2, următoarea literă D din alfabet - 3, apoi I - 4, O - 5; prima literă P este 6, a doua P este 7 și litera T este 8. Completați grila:

Notăm coloanele în conformitate cu numerele literelor cheie:

UTY BKT STH TAO UAL PEMO DKI BKE

Apoi, secvența este din nou împărțită în cinci:

UTYK TSTHT AOUAL PEMOD KIBKE

Acest cod simplu de rearanjare a coloanei a fost folosit de agenții secreti germani în timpul celui de-al Doilea Război Mondial. Ei au folosit primele litere ale rândurilor de pe o anumită pagină a unei cărți obișnuite ca cheie.

O dezvoltare a acestui cifr este un cifr pentru rearanjarea coloanelor cu goluri, care sunt situate în zăbrele, de asemenea, în conformitate cu cheia (în cazul nostru, după 6-1-3-4-2-8-5-7 ... personaje):

Criptarea va fi astfel:

UDC b SEHL TTOM AEP PKI UKLR BTTO

Din exemplele luate în considerare, este clar că toate procedurile de criptare și decriptare care utilizează metoda permutării sunt destul de formale și pot fi implementate algoritmic.

Aatbash, cifru Scital, zăbrele Cardano sunt modalități binecunoscute de a ascunde informațiile de privirile indiscrete. În sensul clasic, un cifr de permutare este o anagramă. Esența sa constă în faptul că literele textului simplu își schimbă pozițiile după o anumită regulă. Cu alte cuvinte, cheia de cifrare este de a schimba ordinea caracterelor din mesajul deschis. Totuși, dependența cheii de lungimea textului criptat a creat multe inconveniente pentru utilizarea acestui tip de cifră. Dar capetele inteligente au găsit soluții interesante, viclene, care sunt descrise în articol.

Grupuri inversate

Pentru a vă familiariza cu criptarea folosind metoda permutării, vom aminti unul dintre cele mai simple exemple. Algoritmul său constă în împărțirea unui mesaj în n blocuri, care sunt apoi întoarse înapoi și schimbate. Să ne uităm la un exemplu.

• „Ziua trecea și aerul era întunecat pe cer”.

Să împărțim acest mesaj în grupuri. În acest caz n = 6.

• „Denukh odili nebav ozd uhtemny”.

Acum să extindem grupurile, scriind fiecare de la sfârșit.

• „hunned vaben dzo methu yyn”.

Să le rearanjam într-un anumit fel.

• "ilido methu yyn huned vaben dzo."

Pentru o persoană ignorantă, în această formă mesajul nu este altceva decât un gunoi. Dar, desigur, cel căruia îi este adresat mesajul se ocupă de algoritmul de decriptare.

Inserție din mijloc

Algoritmul pentru această criptare este puțin mai complicat decât permutarea:

1. Împărțiți mesajul în grupuri cu un număr par de caractere.
2. Introduceți litere suplimentare în mijlocul fiecărui grup.

Să ne uităm la un exemplu.

„El a condus făpturile pământului să doarmă”.

„Zemn yetv ariu vodi lkosnu”.

"Zeamn yeabtv araiu voabdi lkoasnu."

În acest caz, literele alternative „a” și „ab” au fost introduse în mijlocul grupurilor. Inserțiile pot fi diferite, în cantități diferite și nu se repetă. În plus, puteți extinde fiecare grup, le puteți amesteca etc.

Cod cifrat „Sandwich”

Un alt exemplu distractiv și simplu de criptare prin permutare. Pentru a-l folosi, trebuie să împărțiți textul simplu în 2 jumătăți și să scrieți una dintre ele caracter cu caracter între literele celeilalte. Să o arătăm cu un exemplu.

• "Din munca lor; numai eu sunt singur, fara adapost."

Împărțiți în jumătăți cu un număr egal de litere.

• „Sunt singura persoană fără adăpost din munca lor”.

Acum să scriem prima jumătate a mesajului cu un spațiu mare între litere.

• „Despre t i h t u d o v l i s h ”.

Și în aceste spații vom plasa literele din a doua jumătate.

• „Oyatoidhitnrbuedzodvolminshy”.

În cele din urmă, să grupăm literele într-un fel de cuvinte (operație opțională).

• „Oyatoi dhi tnrbue dzodvol minshyy”.

Este foarte ușor să criptați text folosind această metodă. Linia de prostii rezultată va trebui să dureze ceva timp pentru ca cei neinițiați să se dezlege.

Rearanjamente de-a lungul „rutei”

Acest nume a fost dat cifrurilor care au fost utilizate pe scară largă în cele mai vechi timpuri. Traseul în construcția lor a fost o figură geometrică. Textul simplu a fost scris într-o astfel de figură după un anumit model și preluat conform inversului său. De exemplu, o opțiune ar putea fi să scrieți text simplu într-un tabel folosind schema: un șarpe se târăște în sensul acelor de ceasornic prin celule și un mesaj criptat este compus prin scrierea coloanelor într-un singur rând, de la primul la ultimul. Aceasta este, de asemenea, criptare prin permutare.

Să arătăm cu un exemplu cum să criptăm textul. Încercați să determinați singur ruta de înregistrare și ruta de criptare.

— Mă pregăteam să suport războiul.

Vom scrie mesajul într-un tabel cu dimensiuni de 3x9 celule. Mărimea tabelului poate fi determinată pe baza lungimii mesajului sau un tabel fix poate fi folosit de mai multe ori.

Vom compune codul începând din colțul din dreapta sus al tabelului.

• „Launlvosoyatovvygidtaerprzh”.

Inversarea pașilor descriși nu este dificilă. Este suficient să faci exact invers. Această metodă este extrem de convenabilă deoarece facilitează reținerea procedurii de criptare și decriptare. De asemenea, este interesant pentru că orice formă poate fi folosită pentru un cifr. De exemplu, o spirală.

Permutări verticale

Acest tip de cifru este, de asemenea, o variantă de permutare a rutei. Este interesant în primul rând din cauza prezenței cheii. Această metodă a fost răspândită în trecut și a folosit și tabele pentru criptare. Mesajul este scris în tabel în modul obișnuit - de sus în jos, iar cifra cifrată este scrisă vertical, păstrând ordinea specificată de cheie sau parolă. Să ne uităm la un exemplu de astfel de criptare.

„Atât cu o cale dureroasă, cât și cu compasiune”

Folosim un tabel cu dimensiuni de 4x8 celule și scriem mesajul nostru în el în mod obișnuit. Și pentru criptare folosim cheia 85241673.

Acum, folosind cheia ca indicație a ordinii, să scriem coloanele într-o linie.

• „Gusetmsntmayapoysaotmserinid”.

Este important de reținut că, cu această metodă de criptare, celulele goale din tabel nu ar trebui să fie umplute cu litere sau simboluri aleatorii, în speranța că acest lucru va complica cifrarea. De fapt, dimpotrivă, o astfel de acțiune le va oferi inamicilor un indiciu. Deoarece lungimea cheii va fi egală cu unul dintre divizorii de lungime a mesajului.

Decodificare inversă a permutației verticale

Permutarea verticală este interesantă, deoarece decriptarea unui mesaj nu înseamnă pur și simplu urmarea unui algoritm în sens invers. Oricine cunoaște cheia știe câte coloane sunt în tabel. Pentru a decripta un mesaj, trebuie să determinați numărul de linii lungi și scurte din tabel. Acest lucru vă va permite să determinați începutul de unde să începeți să scrieți cifra cifrogramei în tabel pentru a citi textul simplu. Pentru a face acest lucru, împărțiți lungimea mesajului la lungimea cheii și obțineți 30/8=3 și 6 ca rest.

Astfel, am aflat că tabelul are 6 coloane lungi și 2 scurte, nu complet umplute cu litere. Privind cheia, vedem că criptarea a început la a 5-a coloană și trebuie să fie lungă. Așa că constatăm că primele 4 litere ale cifrgramei corespund celei de-a cincea coloane a tabelului. Acum puteți nota toate literele la locul lor și puteți citi mesajul secret.

Acest tip aparține așa-numitelor cifruri stencil, dar la baza lui se află criptarea prin metoda permutării simbolului. Cheia este un șablon în formă de masă cu găuri tăiate în el. De fapt, șablonul poate avea orice formă, dar cel mai adesea se folosește un pătrat sau o masă.

Șablonul Cardano este realizat după următorul principiu: celulele tăiate, atunci când sunt rotite la 90°, nu trebuie să se suprapună. Adică, după 4 rotații ale șablonului în jurul axei sale, fantele din acesta nu ar trebui să coincidă nici măcar o dată.

Să folosim ca exemplu o rețea Cardano simplă (în figura de mai jos).

Folosind acest șablon, vom cripta expresia „O, muze, mă voi adresa cu un apel”.

Umplem celulele șablonului cu litere conform regulii: mai întâi de la dreapta la stânga și apoi de sus în jos. Când celulele se epuizează, rotiți șablonul cu 90° în sensul acelor de ceasornic. În acest fel obținem următorul tabel.

Și ultima tură.

După ce combinăm 4 tabele într-unul singur, primim mesajul final criptat.

Deși mesajul poate rămâne același, va fi mai convenabil să primiți o cifrgramă cu aspect familiar pentru transmitere. Pentru a face acest lucru, puteți umple celulele goale cu litere aleatorii și puteți scrie coloanele într-o singură linie:

• „YAVGVGM OOZGVS MUAKG MBZGN GOSCHAGE SRYUAG”

Pentru a decripta acest mesaj, destinatarul trebuie să aibă o copie exactă a șablonului care a fost folosit pentru criptare. Acest cifru a fost considerat destul de stabil pentru o lungă perioadă de timp. Are, de asemenea, multe variante. De exemplu, folosind 4 grile Cardano deodată, fiecare dintre ele rotindu-se în felul său.

Analiza cifrurilor de permutare

Toate cifrurile de permutare sunt vulnerabile la analiza frecvenței. Mai ales în cazurile în care lungimea mesajului este comparabilă cu lungimea cheii. Și acest fapt nu poate fi schimbat prin utilizarea repetată a permutărilor, oricât de complexe ar fi acestea. Prin urmare, în criptografie, numai acele cifruri care folosesc mai multe mecanisme simultan, pe lângă permutare, pot fi stabile.

Cifre de permutare

Această metodă constă în faptul că caracterele textului criptat sunt rearanjate după anumite reguli în cadrul blocului de caractere criptat, adică. transformările duc la o schimbare doar în ordinea caracterelor din mesajul original. Să ne uităm la unele dintre cele mai comune varietăți ale acestei metode - permutări simple, complicate de tabel și complexe de traseu.

Criptare rearanjare simplă (rearanjarea verticală) se realizează după cum urmează:

1) este selectat un cuvânt cheie cu caractere care nu se repetă;

2) textul criptat este scris în rânduri consecutive sub simbolurile cuvintelor cheie;

3) textul cifrat este scris în coloane în ordinea în care literele cheii sunt situate în alfabet (sau în ordinea numerelor dintr-o serie naturală, dacă cheia este digitală).

Ca o ilustrare, iată un exemplu de criptare folosind o simplă rearanjare a mesajului: „FIȚI ATENȚIE CU REPREZENTANTUL DVS. AL COMPANIEI PHOENIX”. În acest caz, folosim tasta digitală 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. În textul sursă, în loc de spații, se folosește litera O.

Scriind textul în coloane și grupând caracterele câte cinci, obținem textul criptat sub forma:

DO VF NOYSE LRP IIEZH EEMSB S TMF NDLY TOPT RKUTS A E .

Decriptarea se realizează în următoarea ordine:

1) numărați numărul de caractere din textul cifrat și împărțiți la numărul de caractere din cheie;

2) notați cuvântul cheie și sub semnele acestuia, în ordinea corespunzătoare, notați simbolurile criptate în cantitatea specificată mai sus;

3) citiți textul sursă în funcție de rândurile tabelului.

Numărul de chei nu este mai mare de m!, unde m este numărul de coloane din tabel.

Slăbiciunea criptării prin simpla permutare se datorează faptului că, cu o lungime mare a textului criptat, în textul cifrat pot apărea modele de simboluri cheie. Pentru a elimina acest dezavantaj, puteți schimba cheia după criptarea unui anumit număr de caractere. Schimbând cheia suficient de frecvent, puterea criptării poate fi crescută semnificativ. În același timp, însă, organizarea procesului de criptare și decriptare devine mai complicată.

Există diferite metode pentru obținerea și stocarea unei chei numerice. Una dintre cele mai frecvente este de a atribui numere literelor în conformitate cu ordinea alfabetică a literelor. Să luăm, de exemplu, cuvântul PERMANENT. Litera A prezentă în ea primește Nr. 1. Dacă o literă apare de mai multe ori, aparițiile ei sunt numerotate succesiv de la stânga la dreapta. Prin urmare, a doua apariție a literei A devine #2. Nu există litera B în acest cuvânt, apoi litera B primește nr. 3 etc.:

Făcând mai dificilă rearanjarea unei mese constă în faptul că pentru a înregistra caracterele textului criptat se folosește un tabel special, în care sunt introduse unele elemente complicate. Complicația este că un anumit număr de celule de tabel nu sunt utilizate (sunt goale în figură). Numărul și locația elementelor neutilizate reprezintă o cheie de criptare suplimentară. Text criptat în blocuri de m x n – s elemente (m x n– dimensiunile tabelului, s – numărul de elemente neutilizate) se consemnează în tabel. Criptarea ulterioară este similară cu permutarea simplă.

Textul criptat va arăta astfel: DOPR BSWIK RRTM OY N ENSEF UT I SS AF I HOE EE T ME TJ DL.

În timpul decriptării, caracterele ciphertext sunt scrise în coloane de tabel într-o secvență de caractere cheie, omitând elementele neutilizate. Textul sursă este citit rând cu rând. Variind dimensiunea tabelului, secvența caracterelor cheie și numărul și locația elementelor neutilizate, puteți obține puterea necesară a textului cifrat.

O altă opțiune este cifrarea „Grelă rotativă” . destinat mesajelor de lungime 4mk. Luați un șablon care măsoară 2m*2k celule, decupați m*k celule, astfel încât atunci când este aplicat pe o coală de hârtie de aceeași dimensiune în 4 moduri diferite (rotind 90°), decupările sale să acopere complet întreaga zonă a foii . Literele mesajului sunt introduse secvenţial în decupajele stencil pe rânduri, în fiecare rând de la stânga la dreapta, în fiecare dintre cele 4 poziţii posibile ale sale într-o ordine prestabilită. Numărul de șabloane posibile, de ex. numărul de chei din acest cifr este de 4 mk (cu o dimensiune a șablonului de 8*8, numărul de opțiuni depășește 4 miliarde).

Se poate obține o putere de criptare foarte mare complicând rearanjamentele de-a lungul rutelor precum cele hamiltoniene. În acest caz, vârfurile unui anumit hipercub sunt folosite pentru a înregistra caracterele textului cifrat, iar caracterele textului cifrat sunt citite de-a lungul rutelor Hamilton și sunt folosite mai multe rute diferite. De exemplu, luați în considerare criptarea folosind rute Hamilton cu n = 3. Structura și trei trasee sunt prezentate în Fig. 7, iar un exemplu de criptare este în Fig. 8. permutare volumetrică (multidimensională).. În 1992 - 94 Ideea utilizării permutării volumetrice pentru a cripta textul simplu a fost dezvoltată în continuare. O schemă de permutare îmbunătățită bazată pe principiul cubului Rubik, în care, împreună cu textul simplu, elementele funcționale ale algoritmului de criptare însuși sunt de asemenea permutate, a stat la baza sistemului Rubicon. Utilizează un cub tridimensional și un tetraedru ca prototipuri de structuri spațiale multidimensionale, bazate pe transformări volumetrice ale căror permutări sunt efectuate.