S-blok (datalogi)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. marts 2015; checks kræver 30 redigeringer .

S-boks (eller substitutionsblok , eng. s-box fra substitution-box ) - en funktion i programkoden eller et hardwaresystem, der tager n bit ved indgangen , konverterer dem i henhold til en bestemt algoritme og returnerer m bit ved den output . n og m er ikke nødvendigvis ens [1] .

S-bokse bruges i blokcifre .

I elektronik kan du direkte anvende kredsløbet vist på figuren . I programmering oprettes substitutionstabeller ( substitutionstabeller , substitutionstabeller). Begge disse tilgange er ækvivalente, dvs. data krypteret på en computer kan dekrypteres på en elektronisk enhed og omvendt.

En S-boks kaldes perfekt ( perfekt s-boks ) [2], hvis værdierne af outputbittene beregnes af den bøjede funktion baseret på værdierne af inputbittene, og enhver lineær kombination af outputbits er en bøjet funktion af input bits.

Softwareimplementering

Softwareimplementeringen af s-blokken fungerer som følger:

værdien ved indgangen læses ( funktionsargument ) ;
den aflæste værdi søges i tabellen ;
ifølge en bestemt regel vælges en tabelcelle; outputværdien læses fra cellen; outputværdien returneres fra funktionen.

Den anvendte tabel kaldes "erstatningstabellen" eller "erstatningstabellen". Bordet kan:

være uforanderlig (fast) ( eng. static );
genereres baseret på nøglen ( dynamisk ) .

For eksempel bruges en fast tabel til DES -chifferen (algoritmen) , mens for Blowfish- og Twofish -chifferne oprettes tabellen baseret på nøglen.

Eksempel [3] . Overvej at arbejde med tabellen i den femte s-blok ( ) i DES -chifferet . Den femte s-boks tager 6 bit ( ) som input og returnerer 4 bit ( ) som output . Vi nummererer inputbittene fra venstre mod højre fra 1 til 6. Substitutionstabellen har følgende form: $S_5$ $n=6$ $m=4$

S5 _		Værdier af 2., 3., 4. og 5. bit ved input
S5 _		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
Værdier af 1. og 6. bit ved indgangen	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
	ti	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	elleve	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

Lad input bits " 0 1101 1 ". Lad os finde output bits .

1. og 6. bit ved indgangen er lig med "01".
2., 3., 4. og 5. bit ved indgangen er lig med "1101".
I skæringspunktet mellem række "01" og kolonne "1101" finder vi cellen "1001" - bitværdierne ved udgangen.

Hardwareimplementering

Hardwareimplementeringen af s-blokken (se fig. ) består af følgende enheder:

dekoder ;
skifte system;
encoder .

En dekoder er en enhed, der konverterer et n - bit binært signal til et en-bit basissignal . $2^{n}$

For eksempel, for s-boksen vist i figuren , konverterer dekoderen et tre-bit signal ( ) til et otte-bit et ( ). $n=3$ $2^{3}=8$

Skift systeminterne forbindelser, der udfører bitbytning . Hvis m=n , er antallet af forbindelser . Hver inputbit er knyttet til en outputbit placeret i den samme bit eller en anden bit . Hvis antallet af indgange n og udgange m ikke er ens, kan hver dekoderudgang have nul, en, to eller flere forbindelser. Det samme gælder for encoder-indgangene. $2^{n}$

For s-blokken vist på figuren er antallet af forbindelser . $n=m=3$ $2^{n}=2^{3}=8$

En encoder er en enhed, der konverterer et signal fra en enkelt-bit-ær til en n -bit binær. $2^{n}$

For s-blokken vist i figuren kan følgende substitutionstabel (substitutionstabel) kompileres.

	0	en	2	3	fire	5	6	7
Indgangsværdi for dekoder	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
Nummeret på dekoderudgangen (ifølge figuren ), hvor værdien er sat til 1 (på andre udgange er værdien sat til 0)	0	en	2	3	fire	5	6	7
Nummeret på encoder-indgangen (ifølge figuren ), hvor værdien er sat til 1 (på andre indgange er værdien sat til 0)	3	0	en	fire	6	7	2	5
Værdien ved udgangen af encoderen	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

Eksempel . Lad tallet 110 2 føres til indgangene på encoderen vist på figuren (se figur ). Da decimalrepræsentationen af det binære tal 110 2 er 6 10 , vil den 6. udgang af indkoderen have værdien 1, og de andre udgange vil have værdien 0 (se figur ). Ved hjælp af et system af switches vil værdien 1 blive overført til 2. indgang på dekoderen (bit swap). Da den binære repræsentation af decimaltallet 2 10 er 010 2 , vil udgangene fra dekoderen være tallet 010 2 ( se figur ).

Ansøgning

S-bokse bruges i blokcifre , når der udføres symmetrisk kryptering for at skjule det statistiske forhold mellem almindelig tekst og chiffertekst .

Analyse af en n -bit s-blok for stor n er ekstremt vanskelig, men det er meget vanskeligt at implementere en sådan blok i praksis, da antallet af mulige forbindelser er stort ( ). I praksis bruges "substitutionsblokken" som et element i mere komplekse systemer. $2^{n}$

S-bokse bruges i følgende cifre:

AES ( engelsk a dvanced e ncryption s tandard ) er en chiffer, der er standard i USA ;
GOST 28147-89 - indenlandsk datakrypteringsstandard;
DES ( eng. data encryption s tandard ) er en chiffer, der var standard i USA før vedtagelsen af AES ;
Blowfish ;
To fisk .

Sikkerhed

Når man designer en s-box, skal man være særlig opmærksom på udarbejdelsen af en "substitutionstabel". I mange år har forskere ledt efter bogmærker (sårbarheder, der kun er kendt af skaberne) i substitutionstabellerne i de otte s-blokke i DES -chifferet . Forfatterne af DES fortalte [4] om, hvad de blev styret af, når de kompilerede substitutionstabeller. Resultaterne af differentiel kryptoanalyse af DES-chifferet viste, at tallene i substitutionstabellerne var nøje udvalgt for at øge DES's modstand mod visse typer angreb. Biham og Shamir fandt ud af, at selv små ændringer i tabeller kan svække DES markant [5] .

Noter

↑ Chandrasekaran, J. et al. En kaosbaseret tilgang til forbedring af ikke-linearitet i s-box-designet af symmetriske nøglekryptosystemer // Fremskridt i netværk og kommunikation: første internationale konference om datalogi og informationsteknologi, CCSIT 2011, Bangalore , Indien , 2.-4. januar 2011 . Proceedings, del 2. - Springer, 2011. - S. 516. - ISBN 978-3-642-17877-1 .
↑ RFC 4086 . Afsnit 5.3 "Brug af s-bokse til blanding"
↑ Buchmann Johannes A. 5. DES // Introduktion til kryptografi. — Korr. 2. print.. - New York, NY [ua]: Springer, 2001. - S. 119-120. — ISBN 0-387-95034-6 .
↑ Kobbersmed, Don Data Encryption Standard (DES) og dens styrke mod angreb // IBM Journal of Research and Development : journal. - 1994. - Bd. 38 , nr. 3 . - S. 243-250 . - doi : 10.1147/rd.383.0243 .
↑ Gargiulos "S-Box-modifikationer og deres effekt i DES-lignende krypteringssystemer" Arkiveret 20. maj 2012 på Wayback Machine . S. 9.

Litteratur

Kaisa Nyberg (engelsk) (1991). "Perfekte ikke-lineære s-bokse" ( PDF ) . Fremskridt inden for kryptologi - Eurocrypt (engelsk) 1991 . Brighton . pp. 378-386 . Hentet 2007-02-20 . (utilgængeligt link)

S. Mister og C. Adams (engelsk) (1996). "Praktisk s-box design" ( PostScript ) . Workshop om udvalgte områder i kryptografi (engelsk) (SAC 1996). værkstedsrekord . Queens University . pp. 61-76 . Hentet 2007-02-20 .

Schneier, Bruce . Anvendt kryptografi. Anden udgave (neopr.) . - John Wiley & Sons , 1996. - S. 296 -298, 349. - ISBN 0-471-11709-9 .

Easttom, ChuckEn guideline til at skabe kryptografiske s-bokse (neopr.) . — https://www.academia.edu/9192148/CREATING_CRYPTOGRAPHIC_S-BOXES_A_Guideline_for_Designing_Cryptographic_S-Boxes_by_Chuck_Easttom , 2014.

Se også

Rijndael s- box
Bijektion
boolesk funktion
Ikke noget i ærmet
Erstatningscifre
Permutationsboks (engelsk) ( engelsk p-boks )