S-block (informatica)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 22 martie 2015; verificările necesită 30 de modificări .

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

Implementarea software a blocului s funcționează după cum urmează:

valoarea la intrare este citită ( argumentul funcției );
valoarea citită este căutată în tabel ;
conform unei anumite reguli, este selectată o celulă de tabel; valoarea de ieșire este citită din celulă; valoarea de ieșire este returnată de la funcție.

Tabelul folosit se numește „tabel de înlocuire” sau „tabel de înlocuire”. Tabelul poate:

fi imuabil (fix) ( ing. static );
să fie generat pe baza cheii ( dinamice ) .

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ă: $S_5$ $n=6$ $m=4$

S5 _		Valorile biților 2, 3, 4 și 5 la intrare
S5 _		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 .

Biții 1 și 6 de la intrare sunt egali cu „01”.
Al 2-lea, al 3-lea, al 4-lea și al 5-lea biți de la intrare sunt egali cu „1101”.
La intersecția rândului „01” și coloanei „1101” găsim celula „1001” - valorile biților la ieșire.

Implementarea hardware

Implementarea hardware a blocului s (vezi Fig. ) constă din următoarele dispozitive:

decodor ;
sistem de comutare;
codificator .

Un decodor este un dispozitiv care convertește un semnal binar de n biți într -un semnal de bază de un bit . $2^{n}$

De exemplu, pentru cutia s prezentată în figură , decodorul convertește un semnal de trei biți ( ) într-unul de opt biți ( ). $n=3$ $2^{3}=8$

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. $2^{n}$

Pentru blocul s prezentat în figura , , numărul de conexiuni este . $n=m=3$ $2^{n}=2^{3}=8$

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. $2^{n}$

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 ).

Aplicație

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. $2^{n}$

S-box-urile sunt folosite în următoarele coduri:

AES ( Standard de criptare avansat în engleză ) este un cifr care este standard în Statele Unite ;
GOST 28147-89 - standard intern de criptare a datelor;
DES ( eng. data e ncryption standard ) este un cifr care era standard în Statele Unite înainte de adoptarea AES ;
Blowfish ;
Doi pești .

Securitate

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] .

Note

↑ Chandrasekaran, J. și colab. O abordare bazată pe haos pentru îmbunătățirea neliniarității în proiectarea s-box a criptosistemelor cu chei simetrice // Progrese în rețele și comunicații: prima conferință internațională despre informatică și tehnologia informației, CCSIT 2011, Bangalore , India , 2-4 ianuarie 2011 . Proceedings, part 2. - Springer, 2011. - P. 516. - ISBN 978-3-642-17877-1 .
↑ RFC 4086 . Secțiunea 5.3 „Folosirea s‑box-urilor pentru amestecare”
↑ Buchmann Johannes A. 5. DES // Introducere în criptografie. — Corr. 2. print.. - New York, NY [ua]: Springer, 2001. - P. 119-120. — ISBN 0-387-95034-6 .
↑ Calămarul, Don Standardul de criptare a datelor (DES) și puterea sa împotriva atacurilor // IBM Journal of Research and Development : jurnal. - 1994. - Vol. 38 , nr. 3 . - P. 243-250 . - doi : 10.1147/rd.383.0243 .
↑ „Modificările S-Box și efectul lor în sistemele de criptare asemănătoare DES” lui Gargiulo, arhivat pe 20 mai 2012 la Wayback Machine . S. 9.

Literatură

Kaisa Nyberg (engleză) (1991). „S-box neliniare perfecte” ( PDF ) . Progrese în criptologie - Eurocrypt (engleză) 1991 . Brighton . pp. 378-386 . Consultat 2007-02-20 . (link indisponibil)

S. Mister și C. Adams (engleză) (1996). „Design practic s-box” ( PostScript ) . Workshop on Selected areas in cryptography (engleză) (SAC 1996). fișa atelierului . Universitatea Queens . pp. 61-76 . Consultat 2007-02-20 .

Schneier, Bruce . Criptografia aplicată. Ediția a doua (neopr.) . - John Wiley & Sons , 1996. - S. 296 -298, 349. - ISBN 0-471-11709-9 .

Easttom, ChuckUn ghid pentru crearea s-box-urilor criptografice (neopr.) . — https://www.academia.edu/9192148/CREATING_CRYPTOGRAPHIC_S-BOXES_A_Guideline_for_Designing_Cryptographic_S-Boxes_by_Chuck_Easttom , 2014.

Vezi și

Rijndael s- cutie
Bijectie
funcţie booleană
Nimic din mânecă
Cifrul de substituție
Caseta de permutare (engleză) ( p-box în engleză )