S-box (sau bloc de substituție , ing. s-box din substitution-box ) - o funcție din codul programului sau un sistem hardware care ia n biți la intrare , îi convertește conform unui anumit algoritm și returnează m biți la ieșire . n și m nu sunt neapărat egali [1] .
S-box-urile sunt folosite în cifrurile bloc .
În electronică, puteți aplica direct circuitul prezentat în figură . În programare se creează tabele de înlocuire ( tabele de înlocuire, tabele de înlocuire). Ambele abordări sunt echivalente, adică datele criptate pe un computer pot fi decriptate pe un dispozitiv electronic și invers.
Un S-box se numește perfect ( perfect s-box ) [2] dacă valorile biților de ieșire sunt calculate de funcția îndoită pe baza valorilor biților de intrare și orice combinație liniară de biți de ieșire este o funcția îndoită a biților de intrare.
Implementarea software a blocului s funcționează după cum urmează:
Tabelul folosit se numește „tabel de înlocuire” sau „tabel de înlocuire”. Tabelul poate:
De exemplu, un tabel fix este folosit pentru cifrul DES (algoritm) , în timp ce pentru cifrurile Blowfish și Twofish , tabelul este creat pe baza cheii.
Exemplul [3] . Luați în considerare lucrul cu tabelul celui de-al cincilea bloc s ( ) al cifrului DES . A cincea s-box ia 6 biți ( ) ca intrare și returnează 4 biți ( ) ca ieșire . Numerotăm biții de intrare de la stânga la dreapta de la 1 la 6. Tabelul de înlocuire are următoarea formă:
S5 _ | Valorile biților 2, 3, 4 și 5 la intrare | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | ||
Valorile biților 1 și 6 la intrare | 00 | 0010 | 1100 | 0100 | 0001 | 0111 | 1010 | 1011 | 0110 | 1000 | 0101 | 0011 | 1111 | 1101 | 0000 | 1110 | 1001 |
01 | 1110 | 1011 | 0010 | 1100 | 0100 | 0111 | 1101 | 0001 | 0101 | 0000 | 1111 | 1010 | 0011 | 1001 | 1000 | 0110 | |
zece | 0100 | 0010 | 0001 | 1011 | 1010 | 1101 | 0111 | 1000 | 1111 | 1001 | 1100 | 0101 | 0110 | 0011 | 0000 | 1110 | |
unsprezece | 1011 | 1000 | 1100 | 0111 | 0001 | 1110 | 0010 | 1101 | 0110 | 1111 | 0000 | 1001 | 1010 | 0100 | 0101 | 0011 |
Lăsați biții de intrare „ 0 1101 1 ”. Să găsim biții de ieșire .
Implementarea hardware a blocului s (vezi Fig. ) constă din următoarele dispozitive:
Un decodor este un dispozitiv care convertește un semnal binar de n biți într -un semnal de bază de un bit .
De exemplu, pentru cutia s prezentată în figură , decodorul convertește un semnal de trei biți ( ) într-unul de opt biți ( ).
Comutare sistem - conexiuni interne care efectuează schimbarea de biți . Dacă m=n , numărul de conexiuni este . Fiecare bit de intrare se mapează la un bit de ieșire situat în același bit sau într-un bit diferit . Dacă numărul de intrări n și de ieșiri m nu este egal, fiecare ieșire de decodor poate avea zero, una, două sau mai multe conexiuni. Același lucru este valabil și pentru intrările codificatorului.
Pentru blocul s prezentat în figura , , numărul de conexiuni este .
Un encoder este un dispozitiv care convertește un semnal dintr-un binar de un singur bițiîntr-un binar de n biți.
Pentru blocul s prezentat în figură , următorul tabel de înlocuire (tabel de substituție) poate fi compilat.
0 | unu | 2 | 3 | patru | 5 | 6 | 7 | |
---|---|---|---|---|---|---|---|---|
Valoarea de intrare a decodorului | 000 2 =0 10 | 001 2 =1 10 | 010 2 =2 10 | 011 2 =3 10 | 100 2 =4 10 | 101 2 =5 10 | 110 2 =6 10 | 111 2 =7 10 |
Numărul ieșirii decodorului (conform figurii ) la care valoarea este setată la 1 (la alte ieșiri valoarea este setată la 0) | 0 | unu | 2 | 3 | patru | 5 | 6 | 7 |
Numărul intrării codificatorului (conform figurii ) la care valoarea este setată la 1 (la alte intrări valoarea este setată la 0) | 3 | 0 | unu | patru | 6 | 7 | 2 | 5 |
Valoarea la ieșirea codificatorului | 011 2 =3 10 | 000 2 =0 10 | 001 2 =1 10 | 100 2 =4 10 | 110 2 =6 10 | 111 2 =7 10 | 010 2 =2 10 | 101 2 =5 10 |
Exemplu . Lăsați numărul 110 2 să fie alimentat la intrările encoderului prezentat în figură (vezi figura ). Deoarece reprezentarea zecimală a numărului binar 110 2 este 6 10 , a șasea ieșire a codificatorului va avea valoarea 1, iar celelalte ieșiri vor avea valoarea 0 (vezi figura ). Cu ajutorul unui sistem de comutatoare, valoarea 1 va fi transferată la a doua intrare a decodorului (bit swap). Deoarece reprezentarea binară a numărului zecimal 2 10 este 010 2 , ieșirile decodorului vor fi numărul 010 2 (vezi figura ).
S-box-urile sunt folosite în criptările bloc atunci când se realizează criptarea simetrică pentru a ascunde relația statistică dintre textul simplu și textul cifrat .
Analiza unui bloc s de n biți pentru n mare este extrem de dificilă, dar este foarte dificil de implementat un astfel de bloc în practică, deoarece numărul de conexiuni posibile este mare ( ). În practică, „blocul de substituție” este folosit ca element al sistemelor mai complexe.
S-box-urile sunt folosite în următoarele coduri:
Atunci când proiectați o cutie s, trebuie acordată o atenție deosebită compilării unui „tabel de înlocuire”. De mulți ani, cercetătorii caută semne de carte (vulnerabilități cunoscute doar de creatori) în tabelele de înlocuire ale celor opt blocuri S ale cifrului DES . Autorii DES au povestit [4] despre ce s-au ghidat la compilarea tabelelor de substituție. Rezultatele criptoanalizei diferențiale a cifrului DES au arătat că numerele din tabelele de substituție au fost alese cu grijă pentru a crește rezistența DES la anumite tipuri de atacuri. Biham și Shamir au descoperit că chiar și modificările mici ale tabelelor pot slăbi semnificativ DES [5] .