S-block (datavetenskap)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 mars 2015; kontroller kräver 30 redigeringar .

S-box (eller substitution block , eng. s-box from substitution-box ) - en funktion i programkoden eller ett hårdvarusystem som tar n bitar vid ingången , konverterar dem enligt en viss algoritm och returnerar m bitar vid utgång . n och m är inte nödvändigtvis lika [1] .

S-boxar används i blockchiffer .

Inom elektronik kan du direkt tillämpa kretsen som visas i figuren . I programmering skapas substitutionstabeller ( substitutionstabeller , substitutionstabeller). Båda dessa tillvägagångssätt är likvärdiga, dvs data krypterad på en dator kan dekrypteras på en elektronisk anordning och vice versa.

En S-box kallas perfekt ( perfekt s-box ) [2] om värdena för utbitarna beräknas av den böjda funktionen baserat på värdena för ingångsbitarna och varje linjär kombination av utbitar är en böjd funktion hos inmatningsbitarna.

Programvaruimplementering

Mjukvaruimplementeringen av s-blocket fungerar enligt följande:

värdet vid ingången läses (funktionsargument ) ;
det avlästa värdet söks i tabellen ;
enligt en viss regel väljs en tabellcell; utgångsvärdet läses från cellen; utgångsvärdet returneras från funktionen.

Tabellen som används kallas "ersättningstabellen" eller "ersättningstabellen". Bordet kan:

vara oföränderlig (fast) ( eng. statisk );
genereras baserat på nyckeln ( dynamisk ) .

Till exempel används en fast tabell för DES- chifferet (algoritm) , medan för Blowfish- och Twofish -chifferna skapas tabellen baserat på nyckeln.

Exempel [3] . Överväg att arbeta med tabellen i det femte s-blocket ( ) i DES - chifferet . Den femte s-boxen tar 6 bitar ( ) som indata och returnerar 4 bitar ( ) som utdata . Vi numrerar inmatningsbitarna från vänster till höger från 1 till 6. Substitutionstabellen har följande form: $S_5$ $n=6$ $m=4$

S5 _		Värden för den 2:a, 3:e, 4:e och 5:e biten vid ingången
S5 _		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Värden för den 1:a och 6:e biten vid ingången	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
	tio	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	elva	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

Låt inmatningsbitarna " 0 1101 1 ". Låt oss hitta utgångsbitarna .

Den 1:a och 6:e biten vid ingången är lika med "01".
De 2:a, 3:e, 4:e och 5:e bitarna vid ingången är lika med "1101".
I skärningspunkten mellan rad "01" och kolumn "1101" hittar vi cellen "1001" - bitvärdena vid utgången.

Hårdvaruimplementering

Hårdvaruimplementeringen av s-blocket (se fig. ) består av följande enheter:

avkodare ;
bytessystem;
kodare .

En avkodare är en enhet som omvandlar en n - bits binär signal till en enbits bassignal . $2^{n}$

Till exempel, för s-boxen som visas i figuren konverterar avkodaren en trebitarssignal ( ) till en åttabitarssignal ( ). $n=3$ $2^{3}=8$

Switch system - interna anslutningar som utför bitbyte . Om m=n är antalet anslutningar . Varje ingångsbit mappas till en utgångsbit som finns i samma bit eller en annan bit . Om antalet ingångar n och utgångar m inte är lika, kan varje dekoderutgång ha noll, en, två eller flera anslutningar. Detsamma gäller för kodaringångarna. $2^{n}$

För s-blocket som visas i figuren , , är antalet anslutningar . $n=m=3$ $2^{n}=2^{3}=8$

En kodare är en enhet som omvandlar en signal från enenbit -är till en n -bit binär. $2^{n}$

För s-blocket som visas i figuren kan följande substitutionstabell (substitutionstabell) sammanställas.

	0	ett	2	3	fyra	5	6	7
Dekoderns ingångsvärde	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
Numret på dekoderutgången (enligt figuren ) där värdet är satt till 1 (på andra utgångar är värdet satt till 0)	0	ett	2	3	fyra	5	6	7
Numret på kodaringången (enligt figuren ) där värdet är satt till 1 (på andra ingångar är värdet satt till 0)	3	0	ett	fyra	6	7	2	5
Värdet vid utgången av kodaren	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

Exempel . Låt siffran 110 2 matas till ingångarna på givaren som visas i figuren (se figur ). Eftersom decimalrepresentationen av det binära talet 110 2 är 6 10 kommer kodarens 6 :e utgång att ha värdet 1, och de andra utgångarna kommer att ha värdet 0 (se figur ). Med hjälp av ett system av switchar kommer värdet 1 att överföras till dekoderns 2: a ingång (bitswap). Eftersom den binära representationen av decimaltalet 2 10 är 010 2 , kommer utsignalerna från dekodern att vara talet 010 2 ( se figur ).

Applikation

S-boxar används i blockchiffer när man utför symmetrisk kryptering för att dölja det statistiska förhållandet mellan klartext och chiffertext .

Analys av ett n -bitars s-block för stort n är extremt svårt, men det är mycket svårt att implementera ett sådant block i praktiken, eftersom antalet möjliga anslutningar är stort ( ). I praktiken används "substitutionsblocket" som en del av mer komplexa system. $2^{n}$

S-boxar används i följande chiffer:

AES ( engelska a dvanced e ncryption s tandard ) är ett chiffer som är standard i USA ;
GOST 28147-89 - inhemsk datakrypteringsstandard;
DES ( eng. data e ncryption tandard ) är ett chiffer som var standard i USA innan AES infördes ;
Blowfish ;
Tvåfiskar .

Säkerhet

Vid design av en s-box bör särskild uppmärksamhet ägnas åt sammanställningen av en "ersättningstabell". I många år har forskare letat efter bokmärken (sårbarheter som endast är kända för skaparna) i substitutionstabellerna för de åtta s-blocken i DES - chifferet . Författarna till DES berättade [4] om vad de vägleddes av vid sammanställningen av substitutionstabeller. Resultaten av differentiell kryptoanalys av DES-chifferet visade att siffrorna i substitutionstabellerna var noggrant utvalda för att öka motståndet hos DES mot vissa typer av attacker. Biham och Shamir fann att även små ändringar av tabeller kan försvaga DES avsevärt [5] .

Anteckningar

↑ Chandrasekaran, J. et al. En kaosbaserad metod för att förbättra icke-linjäritet i s-box-designen av symmetriska nyckelkryptosystem // Framsteg inom nätverk och kommunikation: första internationella konferensen om datavetenskap och informationsteknologi, CCSIT 2011, Bangalore , Indien , 2-4 januari 2011 . Proceedings, del 2. - Springer, 2011. - P. 516. - ISBN 978-3-642-17877-1 .
↑ RFC 4086 . Avsnitt 5.3 "Använda s-boxar för blandning"
↑ Buchmann Johannes A. 5. DES // Introduktion till kryptografi. — Korr. 2. print.. - New York, NY [ua]: Springer, 2001. - P. 119-120. — ISBN 0-387-95034-6 .
↑ Kopparsmed, Don Data Encryption Standard (DES) och dess styrka mot attacker // IBM Journal of Research and Development : journal. - 1994. - Vol. 38 , nr. 3 . - S. 243-250 . - doi : 10.1147/rd.383.0243 .
↑ Gargiulos "S-Box-modifieringar och deras effekt i DES-liknande krypteringssystem" Arkiverad 20 maj 2012 på Wayback Machine . S. 9.

Litteratur

Kaisa Nyberg (engelska) (1991). "Perfekta olinjära s-boxar" ( PDF ) . Framsteg inom kryptologi - Eurocrypt (engelska) 1991 . Brighton . pp. 378-386 . Hämtad 2007-02-20 . (inte tillgänglig länk)

S. Mister och C. Adams (engelska) (1996). "Praktisk s-box design" ( PostScript ) . Workshop om utvalda områden inom kryptografi (engelska) (SAC 1996). verkstadsrekord . Queens University . pp. 61-76 . Hämtad 2007-02-20 .

Schneier, Bruce . Tillämpad kryptografi. Andra upplagan (neopr.) . - John Wiley & Sons , 1996. - S. 296 -298, 349. - ISBN 0-471-11709-9 .

Easttom, ChuckEn riktlinje för att skapa kryptografiska s-boxar (neopr.) . — https://www.academia.edu/9192148/CREATING_CRYPTOGRAPHIC_S-BOXES_A_Guideline_for_Designing_Cryptographic_S-Boxes_by_Chuck_Easttom , 2014.

Se även

Rijndael s- box
Bijection
boolesk funktion
Inget på min ärmnummer
Ersättnings-chiffer
Permutationsbox (engelska) ( engelska p-box )