Šifrēšanas algoritms GOST 28147-89. Vienkārša nomaiņas metode. - Arhīvs WASM.RU

“Kamēr esat dzīvs, nemirstiet, paskatieties uz šo pasauli.
Daudziem šeit ir mirusi dvēsele - viņi ir miruši iekšā.
Bet viņi staigā un smejas, nezinādami, ka tādi nav,
Nesteidzieties ar savu nāves stundu, ”viņa man teica.

Ārija, "Augsti tur augšā"

2.1 Feistel tīkli.
2.2 Bloķēt šifru GOST 28147-89

3.1 Galvenā informācija
3.2 Kriptogrāfijas pārveidošanas galvenais solis

3.3 Pamata cikli:“ 32.-Z” , “ 32-R” .

4.1 Šifrēšanas transformācijas galvenā posma īstenošana
4.2 Palielinot algoritma ātrumu
5. Galvenās informācijas prasības
6. Izmantotās literatūras saraksts
7. Pateicības.

Ievads.

Šis dokuments ir mans mēģinājums aprakstīt metodi, kā vienkārši aizstāt GOST 28147-89 šifrēšanas algoritmu ar vienkāršāko, bet tomēr tehniski kompetento valodu. Pēc pirmo sešu punktu izlasīšanas lasītājs izteiks savu viedokli par to, kā es to izdarīju.

Lai mans darbs sniegtu lielāku labumu, iesaku apbruņoties ar lietoto literatūras sarakstā norādīto autoru darbiem. Ir arī ieteicams, lai kalkulatoram būtu funkcija darbības aprēķināšanai. XOR kopš lasot rakstu, tiek pieņemts, ka lasītājs bija iecerējis izpētīt šo šifrēšanas algoritmu. Lai gan tas ir piemērots arī kā atsauce, es šo rakstu uzrakstīju tieši kā mācību rakstu.

Iepriekšēja informācija par bloku šifriem.

Pirms sākam aplūkot algoritmu, mums jāiepazīstas ar šāda veida šifru radīšanas vēsturi. Algoritms pieder bloku šifru kategorijai, kuras arhitektūrā informācija ir sadalīta ierobežotā skaitā bloku, galīgais, protams, var nebūt pilnīgs. Šifrēšanas process notiek pilnos blokos, kas veido šifru. Pēdējais bloks, ja tas ir nepilnīgs, tiek papildināts ar kaut ko (par tā aizpildīšanas niansēm teikšu tālāk) un tiek šifrēts tāpat kā pilni bloki. Ar šifru es domāju šifrēšanas funkcijas rezultātu, kas iedarbojas uz noteiktu datu apjomu, ko lietotājs iesniedza šifrēšanai. Citiem vārdiem sakot, šifrs ir šifrēšanas gala rezultāts.

Blokšifru attīstības vēsture ir saistīta ar 70. gadu sākumu, kad IBM, apzinoties nepieciešamību aizsargāt informāciju, pārsūtot datus, izmantojot datoru sakaru kanālus, uzsāka savu pētījumu programmu, kas veltīta informācijas aizsardzībai elektroniskajos tīklos, ieskaitot kriptogrāfiju.

Pētnieku grupu - izstrādātājus no IBM, kas sāka pētīt šifrēšanas sistēmas ar simetrisku atslēgu izmantošanas shēmu, vadīja Dr. Horsts Feistels.

2.1 Feistel tīkli

Feistela piedāvātās jaunās šifrēšanas metodes arhitektūra klasiskajā literatūrā tiek dēvēta par "The Feistel Architecture", bet šobrīd krievu un ārzemju literatūrā tiek lietots vairāk ieviests termins - "Feistel's network" jeb Feistel`s NetWork. Pēc tam uz šīs arhitektūras tika būvēts šifrs "Lucifers", kas vēlāk tika publicēts un izraisīja jaunu intereses vilni par kriptogrāfiju kopumā.

"Feistel tīkla" arhitektūras ideja ir šāda: informācijas ievades plūsma ir sadalīta n bitu lieluma blokos, kur n ir pāra skaitlis. Katrs bloks ir sadalīts divās daļās-L un R, tad šīs daļas tiek ievadītas iteratīvā bloka šifrā, kurā j-tā posma rezultātu nosaka iepriekšējā posma j-1 rezultāts! To var ilustrēt ar piemēru:

Rīsi. 1

Funkcija A ir bloka šifra galvenā darbība. Tā var būt vienkārša darbība, piemēram, XOR darbība, vai arī tai var būt sarežģītāka forma kā virkne vienkāršu darbību - moduļu pievienošana, nobīde pa kreisi, elementu nomaiņa utt., Kopā ņemot, šīs vienkāršās darbības veidlapa tā saucamais - šifrēšanas transformācijas galvenais solis.

Jāatzīmē, ka funkcijas darbības galvenie elementi ir galveno elementu piegāde un XOR darbība, un no tā, cik labi ir pārdomāts šo darbību darbs, tas runā par visa šifra kriptogrāfisko spēku.

Lai Feistel tīkla ideja beidzot būtu skaidra, apsveriet vienkāršāko gadījumu, kas parādīts rīsi. 1, kur funkcijā A - būs darbības “mod 2” (“xor”), bet šis vienkāršākais gadījums, nopietnākā situācijā, piemēram, valsts nozīmes informācijas slēpšana, funkcija A var būt sarežģītāka (cik esmu redzējis, funkcija A patiešām ir ļoti sarežģīta):

Sākotnējie dati:

L = 1110b, R = 0101, K = 1111b

Iegūstiet šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Paskaidrosim savas darbības:

1. Šī darbība ir papildināšanas mod 2 4. Praksē šāda darbība tiek samazināta līdz vienkāršai saskaitīšanai, kur mums jāpievieno divi skaitļi un jāignorē pārnešana uz 5. ciparu. Tā kā, ja mēs noliksim eksponentus virs skaitļa binārā attēlojuma cipariem, tad eksponents būs četri virs piektā cipara, apskatīsim zemāk redzamo attēlu, kas parāda mūsu darbības darbības:

Rīsi. 2

Šeit es norādīju uz eksponentiem ar bultiņu, kā redzat, rezultātam vajadzēja būt 10100, bet, tā kā pārsūtīšana tiek ignorēta mod 2 4 darbības laikā, mēs iegūstam 0100.

2. Šo darbību literatūrā sauc par mod 2, montāžas valodā to īsteno komanda XOR... Bet tā pareizākais nosaukums ir mod 2 1. Bez šīs unikālās darbības diez vai ir iespējams izveidot ātru, viegli īstenojamu šifrēšanas algoritmu un tajā pašā laikā, lai tas joprojām būtu diezgan kriptogrāfiski spēcīgs. Šīs operācijas unikalitāte slēpjas faktā, ka tā pati ir pretēja! Piemēram, ja skaitlis A ir XOR ar skaitli B, rezultātā mēs iegūsim B, nākotnē pietiek ar skaitļu B un C atkārtotu XOR savā starpā, lai iegūtu iepriekšējo vērtību A!

Šajā operācijā mēs saņēmām 1010 ar cipariem 1110 un 0100, lai atgūtu 1110, pietiek ar XOR skaitļu 0100 un 1010 atkārtotu XOR! Sīkāka informācija par šo darbību ir atrodama rakstā, kas pievienots vietnei. www.wasm.ru, « Elementāra rokasgrāmataCRC_ kļūdu noteikšanas algoritmi»Autors, kurš Ross N. Viljamss... Šajā darbā ir jēga - " 5. Binārā aritmētika bez defisēšanas". Šajā rakstā ir aprakstīta darbība. xor! Es izsaucos, jo šajā rakstā šī darbība ir tik ieplānota, ka lasītājs ne tikai saprot, kā šī operācija darbojas, bet pat sāk to redzēt, dzirdēt un sajust!

3. Šī darbība ir nepieciešama, lai atšifrēšanas laikā no šifrēšanas varētu iegūt sākotnējās vērtības.

2.2 Bloka šifrs GOST 28147-89

Šifrēšanas algoritms GOST 28147 - 89 pieder bloku šifru kategorijai, kas darbojas saskaņā ar līdzsvarotu Feistel tīklu arhitektūru, kur divas atlasītā informācijas bloka daļas ir vienāda izmēra. Algoritms tika izstrādāts VDK astotā departamenta dziļumā, tagad pārveidots par FAPSI un tika ierakstīts kā Krievijas Federācijas šifrēšanas standarts vēl 1989. gadā PSRS laikā.

Lai šī algoritma metode darbotos, informācija ir jāsadala 64 bitu lieluma blokos. Izveidojiet vai ievadiet šifrēšanas sistēmā šādu pamatinformāciju: atslēgu un aizstāšanas tabula. Atslēgu un aizvietošanas tabulas izvēle šifrēšanai ir jāuztver ļoti nopietni, jo tas ir jūsu informācijas drošības pamats. Par to, kādas prasības tiek izvirzītas atslēgai, un tabulu par aizstāšanu skatiet postenī "Prasības pamatinformācijai".

Apsverot metodi, mēs uz to nekoncentrēsimies, jo šis raksts, kā jau teicu iepriekš, tika uzrakstīts ar mērķi iemācīt lasītājam šifrēt datus ar vienkāršu šī šifrēšanas algoritma nomaiņas metodi, taču mēs noteikti skarsim šo jautājumu raksta beigās.

Teorētiskais minimums.

3.1. Pamatinformācija

Kā jau teicu iepriekš, datu šifrēšanā aktīvi iesaistās:

3.1.1. Atslēga ir astoņu elementu secība, katra 32 biti. Turpmāk mēs apzīmēsim ar simbolu K, un elementi, no kuriem tas sastāv, ir k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2. Aizstāšanas tabula - astoņu rindu un sešpadsmit kolonnu matrica, turpmāk - Hij. Katrs elements rindas i un kolonnas j krustojumā aizņem 4 bitus.

3.2. Kriptogrāfijas pārveidošanas pamata posms

Galvenais šifrēšanas procesa posms ir - šifrēšanas transformācijas galvenais solis. Tas ir nekas vairāk kā darbība, lai šifrētu datus saskaņā ar noteiktu algoritmu, tikai izstrādātāji ir ieviesuši nosaukumu pārāk apgrūtinošu.

Pirms sākat šifrēt, bloks ir sadalīts divās daļās L un R, katrā 32 biti. Galvenais elements tiek izvēlēts un tikai pēc tam šīs divas bloka daļas, galvenais elements, aizstāšanas tabula, tiek ievadītas galvenā soļa funkcijā, galvenā soļa rezultāts ir viena pamata cikla atkārtošana, kas tiks aplūkota sadaļā nākamo rindkopu. Galvenais solis sastāv no šādām darbībām:

1. Bloka R papildinājuma daļa tiek summēta ar atslēgas elementu K mod 2 32. Iepriekš es aprakstīju līdzīgu darbību, šeit tas pats tikai eksponents nav "4", bet "32" - šīs operācijas rezultāts turpmāk tiks apzīmēts ar Smod.
2. Sadaliet iepriekš iegūto rezultātu Smod četru bitu elementos s7, s6, s5, s4, s3, s2, s1, s0 un ievadiet to nomaiņas funkcijai. Aizstāšana ir šāda: tiek izvēlēts elements Smod - si, mēs sākam no sākuma ar zemāko elementu un aizstājam ar vērtību no aizstāšanas tabulas ar i - rindu un kolonnu, uz kuru norāda elementa s vērtība i. Mēs pārietam uz elementu s i +1 un turpinām tādā pašā veidā un turpinām, līdz mainām pēdējā elementa Smod vērtību - šīs darbības rezultāts tiks apzīmēts kā, Vienkāršs.
3. Šajā operācijā mēs cikliski pārvietojam Ssimple vērtību pa kreisi par 11 bitiem un iegūstam Srol.
4. Mēs izvēlamies L bloka otro daļu un pievienojam to mod 2 ar Srol, kā rezultātā mums ir Sxor.
5. Šajā posmā bloka L daļa kļūst vienāda ar daļas R vērtību, un daļa R, savukārt, tiek inicializēta ar Sxor rezultātu, un šajā brīdī galvenā soļa funkcija ir pabeigta!

3.3 Pamata cikli: "32-З", "32-Р".

Lai šifrētu informāciju, tā ir jāsadala 64 bitu lieluma blokos, protams, pēdējais bloks var būt mazāks par 64 bitiem. Šis fakts ir šīs "vieglās nomaiņas" metodes Ahileja papēdis. Tā kā tā pievienošana 64 bitiem ir ļoti svarīgs uzdevums, lai palielinātu šifrēšanas programmas un šīs jutīgās vietas kriptogrāfisko stiprību, ja tā ir informācijas masīvā, un tā var arī nebūt (piemēram, fails ar 512 baitiem!) ), Jāizturas ar lielu atbildību!

Kad informācija ir sadalīta blokos, atslēga jāsadala elementos:

K = k1, k2, k3, k4, k5, k6, k7, k8

Šifrēšana pati par sevi sastāv no tā saucamo pamata ciklu izmantošanas. Kas, savukārt, ietver kriptotransformācijas pamatsoļu n-to skaitu.

Pamata cikli ir marķēti, kā to ievietot: n - m. Kur n ir šifrēšanas transformācijas pamatsoļu skaits bāzes ciklā, un m ir bāzes cikla "tips", t.i. par ko mēs runājam, par "Z" šifrēšanu vai "R" datu šifrēšanu.

Pamata šifrēšanas cikls 32-З sastāv no 32 pamata šifrēšanas transformācijas posmiem. Bloks N un atslēgas K elements tiek ievadīti funkcijā, kas īsteno soļa darbības, un pirmais solis notiek ar k1, otrais pār rezultātu, kas iegūts ar elementu k2 utt. saskaņā ar šādu shēmu:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P atšifrēšanas process notiek līdzīgi, bet galvenie elementi ir norādīti apgrieztā secībā:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Prakse.

4.1 Šifrēšanas pārveidošanas galvenā posma īstenošana

Kad bijām iepazinušies ar informācijas šifrēšanas teoriju, bija pienācis laiks redzēt, kā šifrēšana darbojas praksē.

Sākotnējie dati:

Ņemiet informācijas bloku N = 0102030405060708h, šeit daļas L un R ir vienādas:

L = 01020304h, R = 05060708h, ņemsim atslēgu:

K = ‘ 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(tie ir ASCII kodi, lai skatītu heksadecimālo attēlojumu, varat atvērt šo failu skatīšanas režīmā Total Commander, nospiežot taustiņu F3"Un tad atslēga" 3 "). Šajā atslēgā elementu vērtības būs šādas:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Ņemiet arī šādu aizstāšanas tabulu:

Rīsi. 3

Šeit rindas ir numurētas no 0 līdz 7, kolonnas no 0 līdz F.

Brīdinājums: Visa informācija, ieskaitot atslēgu ar aizvietošanas tabulu, tiek ņemta par piemēru algoritma apsvēršanai!

Izmantojot "Sākotnējos datus", ir nepieciešams iegūt kriptogrāfijas transformācijas galvenā soļa darbības rezultātu.

1. Izvēlieties daļu R = 05060708h un atslēgas elementu k1 = 'as28', heksadecimālā formā galvenais elements izskatīsies šādi: 61733238h. Tagad mēs veicam summēšanas operāciju mod 2 32:

Rīsi. 4

Kā redzat attēlā, mums nebija pārsūtīšanas 33 bitos, kas atzīmēti ar sarkanu un ar eksponentu “ 32 ". Un, ja mums būtu citas R un galvenā elementa vērtības, tas varēja notikt, un tad mēs to būtu ignorējuši un turpmāk izmantotu tikai dzeltenā krāsā atzīmētos bitus.

Šo darbību veicu ar montētāja komandu pievienot:

; eax = R, ebx = 'as28'

Šīs operācijas rezultāts Smod = 66793940h

2. Tagad vissarežģītākā operācija, bet, ja paskatās cieši, tā vairs nav tik briesmīga, kā šķiet sākumā. Iedomāsimies Smodu šādi:

Rīsi. 5

Es mēģināju attēlā attēlot Smod elementus, bet es tomēr paskaidrošu:

s0 = 0, s1 = 4, s2 = 9 utt.

Tagad, sākot ar zemāko elementu s0, mēs veicam nomaiņu. Atceroties rindkopu " 3.2. Kriptogrāfijas pārveidošanas pamata posms»I - rinda, s i - kolonna, meklējiet vērtību nulles rindā un nulles kolonnā:

6. att

Tātad pašreizējā Smoda vērtība nav 6679394 0 h un 6679394 5 h.

Mēs turpinām nomainīt s1, t.i. četri. Izmantojot pirmo rindu un ceturto kolonnu (s1 = 4!). Mēs skatāmies uz attēlu:

Rīsi. 7

Tagad jau Smoda vērtība, nevis 667939 4 5h, 667939 2 5h. Es pieņemu, ka tagad aizstāšanas algoritms lasītājam ir skaidrs, un varu teikt, ka pēc Ssimple gala rezultāta būs šāda vērtība - 11e10325h.

Par to, kā to visvieglāk ieviest montētāja komandu veidā, es runāšu vēlāk nākamajā rindkopā, pēc tam, kad runāju par paplašināto tabulu.

1. Mums jāpārvieto iegūtā Ssimple vērtība 11 biti pa kreisi.

Rīsi. astoņi

Kā redzat, šī darbība ir diezgan vienkārša, un to īsteno viena montāžas valodas komanda - roll un šīs Srol operācijas rezultāts ir 0819288Fh.

4. Tagad mūsu informācijas bloka L daļa ir XOR ar Srol vērtību. Es ņemu kalkulatoru no w2k sp4 un saņemu Sxor = 091b2b8bh.

5. Šī darbība ir galīga, un mēs vienkārši piešķiram, notīrām R, L daļas vērtību un inicializējam L daļu ar Sxor vērtību.

Gala rezultāts:

L = 091b2b8bh, R = 01020304h

4.2 Algoritma ātruma palielināšana

Tagad parunāsim par algoritma optimizēšanu ātrumam. Projekta īstenošanas procesā jāņem vērā, ka programma, kas strādā ar reģistriem biežāk nekā ar atmiņu, darbojas visātrāk, un šeit arī šis spriedums ir ļoti svarīgs, jo vairāk nekā vienā informācijas blokā pat 32 šifrēšanas darbības!

Ieviešot šifrēšanas algoritmu savā programmā, es rīkojos šādi:

1. Atlasītā bloka daļa L uz eax reģistru un R uz edx.

2. Esi reģistrā, inicializēts ar paplašinātās atslēgas adresi, sīkāk par to zemāk.

3. Reģistrā ebx ir piešķirta paplašinātās aizstāšanas tabulas adreses vērtība, sīkāk par to zemāk

4. Pārnes 1., 2., 3. posteņa informāciju uz pamata cikla 32 - З vai 32 - Р funkciju atkarībā no situācijas.

Ja paskatās uz galveno elementu plūsmas diagrammu punktā " Pamata cikli: "32-З", "32-Р"", Tad mūsu pamata cikla 32 - 3 atslēgu var attēlot šādi:

K 32-Z =

“As28”, “zw37”, “q839”, “7342”, “ui23”, “8e2t”, “wqm2”, “ewp1”,

“As28”, “zw37”, “q839”, “7342”, “ui23”, “8e2t”, “wqm2”, “ewp1”,

“Ewp1”, “wqm2”, “8e2t”, “ui23”, “7342”, “q839”, “zw37”, “as28”

Tie. no sākuma ir k1, k2, k3, k4, k5, k6, k7, k8 - ‘ kā 28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 'šī secība tiek atkārtota trīs reizes. Tad elementi iet apgrieztā secībā, ti: k8, k7, k6, k5, k4, k3, k2, k1 - “Ewp1”, “wqm2”, “8e2t”, “ui23”, “7342”, “q839”, “zw37”, “as28”.

Es iepriekš sakārtoju masīva elementus tādā secībā, kādā tie jāievada 32. - Z. Tādējādi es palielināju nepieciešamo atmiņu pēc gatavības principa, bet izglābu sevi no dažiem domāšanas procesiem, kas man nebija vajadzīgi, un palielināju ātrumu no algoritma, samazinot piekļuves laiku atmiņai! Šeit es aprakstīju tikai 32 - З atslēgu, 32. ciklam - Р es darīju to pašu, bet, izmantojot citu elementu piegādes shēmu, ko es arī aprakstīju punktā " Pamata cikli: “32-Z”, “32-P».

Tagad ir pienācis laiks aprakstīt aizstāšanas funkcijas ieviešanu, kā es solīju iepriekš. Es nevarēju aprakstīt agrāk, jo tam nepieciešams ieviest jaunu koncepciju - paplašinātu aizvietošanas tabulu. Es nevaru jums izskaidrot, kas tas ir. Tā vietā es jums to parādīšu, un jūs pats sev formulējat, kas tas ir - paplašināta aizvietošanas tabula?

Tātad, lai saprastu, kas ir paplašināta aizvietošanas tabula, mums ir nepieciešama, piemēram, aizstāšanas tabula, es ņemšu to, kas parādīts attēlā. 3.

Piemēram, mums bija jāaizstāj numurs 66793940h. Es to pasniegšu šādi:

Rīsi. deviņi

Tagad, ja mēs ņemam elementus s1, s0, t.i. vismazāk nozīmīgais baits, aizstāšanas funkcijas rezultāts būs 25 stundas! Pēc Andreja Vinokurova raksta izlasīšanas, kuru es citēju rindkopā " Izmantotās literatūras saraksts", Jūs faktiski atklājat, ka, izvēloties divas rindas, jūs varat iegūt masīvu, kas ļauj ātri atrast aizvietojošos elementus, izmantojot komandu montētājs xlat. Viņi saka, ka to var izdarīt citā veidā ātrāk, bet Andrejs Vinokurovs apmēram četrus gadus pētīja ātrus algoritmus GOST ieviešanai! Es nedomāju, ka jums vajadzētu izgudrot riteni no jauna, kad jums tas jau ir.

Tātad, par masīvu:

Ņemsim pirmās divas rindas nulli un pirmo, izveidosim 256 baitu masīvu. Tagad mēs novērojam vienu īpatnību, ka, ja ir nepieciešams pārveidot 00h, tad rezultāts būs 75h (pamatojoties uz 3. attēlu) - mēs ievietojam šo vērtību masīvā nobīdē 00h. Mēs ņemam vērtību 01h, aizstāšanas funkcijas 79h rezultātu, ievietojam to masīvā pie nobīdes 01 un tā tālāk līdz 0FFh, kas mums dos 0FCh, ko mēs ievietosim masīvā nobīdē 0FFh. Tātad mēs ieguvām paplašinātu aizstāšanas tabulu pirmajai rindu grupai: pirmajai un nullei. Bet joprojām ir trīs grupas: otrā lapa 2, 3 lapa, trešā lapa 4, 5 lapa ceturtā lapa 6, lapa 7. Mēs ar šīm trim grupām rīkojamies tāpat kā ar pirmo. Rezultāts ir paplašināta aizvietošanas tabula!

Tagad mēs varam ieviest algoritmu, kas veiks nomaiņu. Lai to izdarītu, mēs ņemam vērā avota kodus, kurus Andrejs Vinokurovs ievietojis savā lapā, sk. Bibliogrāfija».

lea ebx, pagarināts_tabulas_vienkāršs

mov eax, [ievietojiet numuru, kas jāaizstāj]

pievienot ebx, 100h; pāriet uz nākamajiem diviem mezgliem

sub ebx, 300h; lai turpmāk ebx norādītu uz galdu

Tagad vēl viena iezīme, ar iepriekšējām darbībām mēs ne tikai nomainījām, bet arī mainījām numuru par 8 bitiem pa kreisi! Mums vienkārši jāpārvieto skaitlis vēl 3 biti pa kreisi:

un mēs iegūstam operācijas rol eax rezultātu, 11!

Es neko vairāk nevaru piebilst par optimizāciju, vienīgais, ko varu uzsvērt, ir tas, ko teicu iepriekš - biežāk lieto reģistrus, nevis piekļuvi atmiņai. Es domāju, ka šie vārdi ir tikai iesācējiem, pieredzējušiem un bez maniem vārdiem to lieliski saprot.

Prasības pamatinformācijai.

Kā teikts Andreja Vinokurova rakstā, atslēga tiek izvēlēta pēc diviem kritērijiem:

Kritērijs vienādam bitu sadalījumam starp vērtībām 1 un 0. Parasti bitu vienlīdzīga sadalījuma kritērijs ir Pīrsona kritērijs ("chi-square").

Tas nozīmē atslēgu, principā jebkurš skaitlis var. Tas ir, kad tiek veidots nākamais atslēgas bits, tā inicializācijas varbūtība par vienu vai nulli ir 50/50!

Lūdzu, ņemiet vērā, ka atslēga sastāv no astoņiem elementiem, katrs no 32 bitiem, tāpēc atslēgā ir 32 * 8 = 256 biti un iespējamo atslēgu skaits ir 2 256! Vai tas tevi nepārsteidz?

Sērijas kritērijs.

Ja paskatāmies uz mūsu atslēgu, ko es iedevu rindkopā " 4.1 Šifrēšanas pārveidošanas galvenā posma īstenošana», Tad pamanīsit, ka ir derīgs šāds apzīmējums:

Rīsi. desmit

Vienā frāzē k 1 vērtību nedrīkst atkārtot ne k 2, ne citā atslēgas elementā.

Tas ir, atslēga, kuru esam izvēlējušies kā šifrēšanas algoritma apsvērumu, pilnībā atbilst diviem iepriekš minētajiem kritērijiem.

Tagad par aizvietošanas tabulas izvēli:

Tagad parunāsim par to, kā izvēlēties pareizo aizstāšanas tabulu. Galvenā prasība, lai izvēlētos aizstāšanas tabulas, ir elementu “neatkārtojamības” fenomens, no kuriem katrs ir 4 bitu liels. Kā redzējāt iepriekš, katra aizstāšanas tabulas rinda sastāv no vērtībām 0h, 1h, 2h, 3h,…, 0fh. Tātad galvenā prasība ir tāda, ka katrā rindā ir vērtības 0h, 1h, 2h, ..., 0fh un katra šāda vērtība vienā eksemplārā. Piemēram, secība:

1 2 3 4 5 6 7 8 9 A B C D E F

Tas pilnībā atbilst šai prasībai, bet tomēr! Nav ieteicams atlasīt šo secību kā virkni. Tā kā, ja jūs ievadāt vērtību funkcijas ievadē, kas balstās uz šādu virkni, tad izvadē jūs saņemsiet tādu pašu vērtību! Netici man? Tad ņemiet skaitli 332DA43Fh un astoņas šādas rindas kā aizstāšanas tabulu. Veiciet nomaiņas darbību, un es jums apliecinu, ka izeja būs skaitlis 332DA43Fh! Tas ir, tas pats, ko jūs iesniedzāt operācijas ievadam! Un tas neliecina par labu šifrēšanas formu, un vai tā bija?

Tā bija viena prasība, nākamais kritērijs saka - katram izejas bloka bitam jābūt statistiski neatkarīgam no katra ievades bloka bita!

Kā tas izskatās vienkāršāk? Un, lūk, piemēram, no iepriekš minētā skaitļa mēs izvēlējāmies elementu s0 = 0Fh, 01111b. Varbūtība, ka mēs pirmo bitu aizstāsim ar vienu vai nulli, ir 0,5! Varbūtība aizstāt otro, trešo un ceturto bitu, katru bitu, mēs atsevišķi apsveram ar vieniem vai nullēm, ir arī 0, 5. Izvēloties s1 = 0Eh, varbūtība, ka mēs esam nulles bits, un tas ir "0" , tiks aizstāts ar nulli vai pārāk vienāds - 0,5! Tādējādi saskaņā ar šo kritēriju nepastāv regularitāte starp elementu s0, s1 nulles bitu nomaiņu! Jā, jūs varētu aizstāt tos, bet jūs varētu aizstāt arī nulles.

Lai novērtētu tabulu pēc šī kritērija, varat izveidot korelācijas koeficientu tabulu, kas aprēķināta pēc formulas:

Ja p = 1, tad bita j vērtība pie izejas ir vienāda ar bita vērtību ievadē jebkurai ievades bitu kombinācijai;

Ja p = -1, tad bita j vērtība pie izejas vienmēr ir apgrieztais ievades bita i;

Ja p = 0, tad izejas bits j ar vienādu varbūtību ņem vērtības 0 un 1 jebkurai ievades bita i fiksētajai vērtībai.

Ņemsim vienu rindas piemēru:

Sadalīsim to "komponentos":

Aprēķināsim vienu koeficientu saskaņā ar iepriekš minēto formulu. Lai būtu vieglāk saprast, kā tas tiek darīts, es paskaidrošu sīkāk:

Mēs ņemam 0. skaitļa (0) 0. Bitu pie ievades un 0. Skaitļa 0. Bitu pie izejas (1), veicam operāciju 0 XOR 1 = 1.

Mēs ņemam 1. skaitļa (1) 0. bitu pie ieejas un 1. skaitļa 0. bitu pie izejas (1), veicam operāciju 1 XOR 1 = 0.

Mēs ņemam 2. skaitļa (0) 0. Bitu pie ieejas un 2. Skaitļa 0. Bitu pie izejas (0), veicam operāciju 0 XOR 0 = 0.

Mēs ņemam 3. skaitļa (1) 0. bitu pie ieejas un 3. skaitļa 0. bitu pie izejas (1), veicam operāciju 1 XOR 1 = 0.

Veicot secīgi XOR operācijas šajā secībā, mēs saskaitām visu vērtību vērtību, kas nav nulle, iegūstam vērtību 6. Tādējādi P 00 = 1- (6/2 4-1) = 0,25. Tātad, izrādījās, ka bita 0 vērtība pie izejas ir vienāda ar bita 0 vērtību pie ievades 4 gadījumos no 16;

Galīgā izredžu tabula:

Kā redzams no korelācijas koeficientu tabulas, ievades ievades 3. bits ir apgriezts pret bitu pie izejas 14 gadījumos no 16, kas ir 87,5%. Parastajām šifrēšanas sistēmām tas vairs nav pieņemams. Izmaiņām ņemsim vēl vienu piemēru:

Koeficientu tabula būs šāda (kam nav slinkums pārrēķināties)

Šajā tabulā viss ir vēl sliktāk - grupas 1. un 2. bits paliek nemainīgs! Cryptanalyst ir kur griezties Ņemot vērā visas šīs prasības, tika atrasta vienkārša meklēšana ("head -on") norādītajai teorijai atbilstošās permutācijas tabulas (šodien - 1276 kombinācijas) Šeit ir dažas no tām:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Izmantotās literatūras saraksts.

1. Andreja Vinokurova raksts:

Šifrēšanas algoritms GOST 28147-89, tā izmantošana un ieviešana

Intel x86 platformas datoriem.

Ir arī avota kodi šifrēšanas algoritma ieviešanai.

1. Horsta Feistela raksts:

Kriptogrāfija un datoru drošība.

(var atrast tajā pašā adresē kā iepriekšējais raksts)

1. Ross N. Viljamss:

Elementārs ceļvedis CRC kļūdu noteikšanas algoritmiem

Publicēts vietnē www.wasm.ru.

Pateicības.

Vēlos izteikt pateicību visiem www.wasm.ru foruma apmeklētājiem. Bet es īpaši vēlos pateikties ChS, kurš šobrīd ir pazīstams kā SteelRat, viņš palīdzēja man saprast lietas, kuras es, iespējams, nekad nebūtu sapratis, kā arī palīdzēja rakstīt rindkopu: “ Galvenās informācijas prasības”, Šīs rindkopas galveno daļu ir uzrakstījis viņš. Es esmu arī ļoti pateicīgs KSTU darbiniekam, kas nosaukts vārdā A.N. Tupolevs Aņikins Igors Vjačeslavovičs un būtu grēks nepieminēt Krisu Kasperski par to, ka viņš ir, un Volodja / wasm.ru par viņa norādījumiem. Ak, un es to saņemu no viņa. Es arī gribu atzīmēt Sega-Zero / Callipso, bet tas man ienesa prātā dažus matemātiskus džungļus.

Iespējams, tas ir viss, ko es gribētu jums pateikt.

Es būtu pateicīgs par kritiku vai jautājumiem, kas saistīti ar šo rakstu vai vienkārši padomu. Mana kontaktinformācija: [pasts aizsargāts], ICQ - 337310594.

Ar cieņu, Evil`s Interrupt.

P.S .: Ar šo rakstu es necentos nevienu pārspēt. Tas tika uzrakstīts ar nolūku, lai atvieglotu GOST izpēti, un, ja jums rodas grūtības, tas nenozīmē, ka esmu vainīgs. Esiet saprātīgs un pacietīgs, visu to labāko jums!

“Kamēr esat dzīvs, nemirstiet, paskatieties uz šo pasauli.
Daudziem šeit ir mirusi dvēsele - viņi ir miruši iekšā.
Bet viņi staigā un smejas, nezinādami, ka tādi nav,
Nesteidzieties ar savu nāves stundu, ”viņa man teica.

Ārija, "Augsti tur augšā"

1. Ievads

1. Iepriekšēja informācija par bloku šifriem

2.1 Feistel tīkli.
2.2 Bloķēt šifru GOST 28147-89

1. Teorētiskais minimums

3.1 Galvenā informācija
3.2 Kriptogrāfijas pārveidošanas galvenais solis

3.3 Pamata cikli:“ 32.-Z” , “ 32-R” .

1. Prakse

4.1 Šifrēšanas transformācijas galvenā posma īstenošana
4.2 Palielinot algoritma ātrumu
5.
6. Izmantotās literatūras saraksts
7. Pateicības.

Ievads.

Šis dokuments ir mans mēģinājums aprakstīt metodi, kā vienkārši aizstāt GOST 28147-89 šifrēšanas algoritmu ar vienkāršāko, bet tomēr tehniski kompetento valodu. Pēc pirmo sešu punktu izlasīšanas lasītājs izteiks savu viedokli par to, kā es to izdarīju.

Lai mans darbs sniegtu lielāku labumu, iesaku apbruņoties ar lietoto literatūras sarakstā norādīto autoru darbiem. Ir arī ieteicams, lai kalkulatoram būtu funkcija darbības aprēķināšanai. XOR kopš lasot rakstu, tiek pieņemts, ka lasītājs bija iecerējis izpētīt šo šifrēšanas algoritmu. Lai gan tas ir piemērots arī kā atsauce, es šo rakstu uzrakstīju tieši kā mācību rakstu.

Iepriekšēja informācija par bloku šifriem.

Pirms sākam aplūkot algoritmu, mums jāiepazīstas ar šāda veida šifru radīšanas vēsturi. Algoritms pieder bloku šifru kategorijai, kuras arhitektūrā informācija ir sadalīta ierobežotā skaitā bloku, galīgais, protams, var nebūt pilnīgs. Šifrēšanas process notiek pilnos blokos, kas veido šifru. Pēdējais bloks, ja tas ir nepilnīgs, tiek papildināts ar kaut ko (par tā aizpildīšanas niansēm teikšu tālāk) un tiek šifrēts tāpat kā pilni bloki. Ar šifru es domāju šifrēšanas funkcijas rezultātu, kas iedarbojas uz noteiktu datu apjomu, ko lietotājs iesniedza šifrēšanai. Citiem vārdiem sakot, šifrs ir šifrēšanas gala rezultāts.

Blokšifru attīstības vēsture ir saistīta ar 70. gadu sākumu, kad IBM, apzinoties nepieciešamību aizsargāt informāciju, pārsūtot datus, izmantojot datoru sakaru kanālus, uzsāka savu pētījumu programmu, kas veltīta informācijas aizsardzībai elektroniskajos tīklos, ieskaitot kriptogrāfiju.

Pētnieku grupu - izstrādātājus no IBM, kas sāka pētīt šifrēšanas sistēmas ar simetrisku atslēgu izmantošanas shēmu, vadīja Dr. Horsts Feistels.

2.1 Feistel tīkli

Feistela piedāvātās jaunās šifrēšanas metodes arhitektūra klasiskajā literatūrā tika saukta par “The Feistel Architecture”, taču šobrīd krievu un ārvalstu literatūrā tiek izmantots vairāk ieviests termins - “Feistel's network” jeb Feistel’s NetWork. Pēc tam uz šīs arhitektūras tika būvēts šifrs "Lucifers", kas vēlāk tika publicēts un izraisīja jaunu intereses vilni par kriptogrāfiju kopumā.

"Feistel tīkla" arhitektūras ideja ir šāda: informācijas ievades plūsma ir sadalīta n bitu lieluma blokos, kur n ir pāra skaitlis. Katrs bloks ir sadalīts divās daļās-L un R, tad šīs daļas tiek ievadītas iteratīvā bloka šifrā, kurā j-tā posma rezultātu nosaka iepriekšējā posma j-1 rezultāts! To var ilustrēt ar piemēru:

Rīsi. 1

Funkcija A ir bloka šifra galvenā darbība. Tā var būt vienkārša darbība, piemēram, XOR darbība, vai arī tai var būt sarežģītāka forma kā virkne vienkāršu darbību - moduļu pievienošana, nobīde pa kreisi, elementu nomaiņa utt., Kopā ņemot, šīs vienkāršās darbības veidlapa tā saucamais - šifrēšanas transformācijas galvenais solis.

Jāatzīmē, ka funkcijas darbības galvenie elementi ir galveno elementu piegāde un XOR darbība, un no tā, cik labi ir pārdomāts šo darbību darbs, tas runā par visa šifra kriptogrāfisko spēku.

Lai Feistel tīkla ideja beidzot būtu skaidra, apsveriet vienkāršāko gadījumu, kas parādīts rīsi. 1, kur funkcijā A - būs darbības “mod 2” (“xor”), bet šis vienkāršākais gadījums, nopietnākā situācijā, piemēram, valsts nozīmes informācijas slēpšana, funkcija A var būt sarežģītāka (cik esmu redzējis, funkcija A patiešām ir ļoti sarežģīta):

Sākotnējie dati:

L = 1110b, R = 0101, K = 1111b

Iegūstiet šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Paskaidrosim savas darbības:

1. Šī darbība ir mod 2 4 papildinājums. Praksē šāda darbība tiek samazināta līdz vienkāršai saskaitīšanai, kur mums jāpievieno divi skaitļi un jāignorē pārnešana uz 5. ciparu. Tā kā, ja mēs noliksim eksponentus virs skaitļa binārā attēlojuma cipariem, tad eksponents būs četri virs piektā cipara, apskatīsim zemāk redzamo attēlu, kas parāda mūsu darbības darbības:

Rīsi. 2

Šeit es norādīju uz eksponentiem ar bultiņu, kā redzat, rezultātam vajadzēja būt 10100, bet, tā kā pārsūtīšana tiek ignorēta mod 2 4 darbības laikā, mēs iegūstam 0100.

1. Šo darbību literatūrā sauc par mod 2, montāžas valodā to īsteno komanda XOR... Bet tā pareizākais nosaukums ir mod 2 1. Bez šīs unikālās darbības diez vai ir iespējams izveidot ātru, viegli īstenojamu šifrēšanas algoritmu un tajā pašā laikā, lai tas joprojām būtu diezgan kriptogrāfiski spēcīgs. Šīs operācijas unikalitāte slēpjas faktā, ka tā pati ir pretēja! Piemēram, ja skaitlis A ir XOR ar skaitli B, rezultātā mēs iegūsim B, nākotnē pietiek ar skaitļu B un C atkārtotu XOR savā starpā, lai iegūtu iepriekšējo vērtību A!

Šajā operācijā mēs saņēmām 1010 ar cipariem 1110 un 0100, lai atgūtu 1110, pietiek ar XOR skaitļu 0100 un 1010 atkārtotu XOR! Sīkāka informācija par šo darbību ir atrodama rakstā, kas pievienots vietnei. www.wasm.ru, « Elementāra rokasgrāmataCRC_ kļūdu noteikšanas algoritmi»Autors, kurš Ross N. Viljamss... Šajā darbā ir jēga - " 5. Binārā aritmētika bez defisēšanas". Šajā rakstā ir aprakstīta darbība. xor! Es izsaucos, jo šajā rakstā šī darbība ir tik ieplānota, ka lasītājs ne tikai saprot, kā šī operācija darbojas, bet pat sāk to redzēt, dzirdēt un sajust!

1. Šī darbība ir nepieciešama, lai atšifrēšanas laikā sākotnējās vērtības varētu iegūt no šifra.

2.2 Bloka šifrs GOST 28147-89

Šifrēšanas algoritms GOST 28147 - 89 pieder bloku šifru kategorijai, kas darbojas saskaņā ar līdzsvarotu Feistel tīklu arhitektūru, kur divas atlasītā informācijas bloka daļas ir vienāda izmēra. Algoritms tika izstrādāts VDK astotā departamenta dziļumā, tagad pārveidots par FAPSI un tika ierakstīts kā Krievijas Federācijas šifrēšanas standarts vēl 1989. gadā PSRS laikā.

Lai šī algoritma metode darbotos, informācija ir jāsadala 64 bitu lieluma blokos. Izveidojiet vai ievadiet šifrēšanas sistēmā šādu pamatinformāciju: atslēgu un aizstāšanas tabula. Atslēgu un aizvietošanas tabulas izvēle šifrēšanai ir jāuztver ļoti nopietni, jo tas ir jūsu informācijas drošības pamats. Par to, kādas prasības tiek izvirzītas atslēgai, un tabulu par aizstāšanu skatiet postenī "Prasības pamatinformācijai".

Apsverot metodi, mēs uz to nekoncentrēsimies, jo šis raksts, kā jau teicu iepriekš, tika uzrakstīts ar mērķi iemācīt lasītājam šifrēt datus ar vienkāršu šī šifrēšanas algoritma nomaiņas metodi, taču mēs noteikti skarsim šo jautājumu raksta beigās.

Teorētiskais minimums.

3.1. Pamatinformācija

Kā jau teicu iepriekš, datu šifrēšanā aktīvi iesaistās:

3.1.1. Atslēga ir astoņu elementu secība, katra 32 biti. Turpmāk mēs apzīmēsim ar simbolu K, un elementi, no kuriem tas sastāv, ir k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2. Aizstāšanas tabula - astoņu rindu un sešpadsmit kolonnu matrica, turpmāk - Hij. Katrs elements rindas i un kolonnas j krustojumā aizņem 4 bitus.

Galvenais šifrēšanas procesa posms ir - šifrēšanas transformācijas galvenais solis. Tas ir nekas vairāk kā darbība datu šifrēšanai pēc noteikta algoritma, tikai izstrādātāji ieviesa pārāk apgrūtinošo nosaukumu :).

Pirms sākat šifrēt, bloks ir sadalīts divās daļās L un R, katrā 32 biti. Galvenais elements tiek izvēlēts un tikai pēc tam šīs divas bloka daļas, galvenais elements, aizstāšanas tabula, tiek ievadītas galvenā soļa funkcijā, galvenā soļa rezultāts ir viena pamata cikla atkārtošana, kas tiks aplūkota sadaļā nākamo rindkopu. Galvenais solis sastāv no šādām darbībām:

1. Bloka R papildinājuma daļa tiek summēta ar atslēgas elementu K mod 2 32. Iepriekš es aprakstīju līdzīgu darbību, šeit tas pats tikai eksponents nav "4", bet "32" - šīs operācijas rezultāts turpmāk tiks apzīmēts ar Smod.
2. Sadaliet iepriekš iegūto rezultātu Smod četru bitu elementos s7, s6, s5, s4, s3, s2, s1, s0 un ievadiet to nomaiņas funkcijai. Aizstāšana ir šāda: tiek izvēlēts elements Smod - si, mēs sākam no sākuma ar zemāko elementu un aizstājam ar vērtību no aizstāšanas tabulas ar i - rindu un kolonnu, uz kuru norāda elementa s vērtība i. Mēs pārietam uz elementu s i +1 un turpinām tādā pašā veidā un turpinām, līdz mainām pēdējā elementa Smod vērtību - šīs darbības rezultāts tiks apzīmēts kā, Vienkāršs.
3. Šajā operācijā mēs cikliski pārvietojam Ssimple vērtību pa kreisi par 11 bitiem un iegūstam Srol.
4. Mēs izvēlamies L bloka otro daļu un pievienojam to mod 2 ar Srol, kā rezultātā mums ir Sxor.
5. Šajā posmā bloka L daļa kļūst vienāda ar daļas R vērtību, un daļa R, savukārt, tiek inicializēta ar rezultātu Sxor, un šajā gadījumā galvenā soļa funkcija ir pabeigta!

3.3 Pamata cikli: "32-З", "32-Р".

Lai šifrētu informāciju, tā ir jāsadala 64 bitu lieluma blokos, protams, pēdējais bloks var būt mazāks par 64 bitiem. Šis fakts ir šīs "vieglās nomaiņas" metodes Ahileja papēdis. Tā kā tā pievienošana 64 bitiem ir ļoti svarīgs uzdevums, lai palielinātu šifrēšanas programmas un šīs jutīgās vietas kriptogrāfisko stiprību, ja tā ir informācijas masīvā, un tā var arī nebūt (piemēram, fails ar 512 baitiem!) ), Jāizturas ar lielu atbildību!

Kad informācija ir sadalīta blokos, atslēga jāsadala elementos:

K = k1, k2, k3, k4, k5, k6, k7, k8

Šifrēšana pati par sevi sastāv no tā saucamo pamata ciklu izmantošanas. Kas, savukārt, ietver kriptotransformācijas pamatsoļu n-to skaitu.

Pamata cikli ir marķēti, kā to ievietot: n - m. Kur n ir šifrēšanas transformācijas pamatsoļu skaits bāzes ciklā, un m ir bāzes cikla "tips", t.i. par ko mēs runājam, par "Z" šifrēšanu vai "R" datu šifrēšanu.

Pamata šifrēšanas cikls 32-З sastāv no 32 pamata šifrēšanas transformācijas posmiem. Bloks N un atslēgas K elements tiek ievadīti funkcijā, kas īsteno soļa darbības, un pirmais solis notiek ar k1, otrais pār rezultātu, kas iegūts ar elementu k2 utt. saskaņā ar šādu shēmu:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

32-P atšifrēšanas process notiek līdzīgi, bet galvenie elementi ir norādīti apgrieztā secībā:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Prakse.

Kad bijām iepazinušies ar informācijas šifrēšanas teoriju, bija pienācis laiks redzēt, kā šifrēšana darbojas praksē.

Sākotnējie dati:

Ņemiet informācijas bloku N = 0102030405060708h, šeit daļas L un R ir vienādas:

L = 01020304h, R = 05060708h, ņemsim atslēgu:

K = ‘ 28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(tie ir ASCII kodi, lai skatītu heksadecimālo attēlojumu, varat atvērt šo failu skatīšanas režīmā Total Commander, nospiežot taustiņu F3"Un tad atslēga" 3 "). Šajā atslēgā elementu vērtības būs šādas:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Ņemiet arī šādu aizstāšanas tabulu:

Rīsi. 3

Šeit rindas ir numurētas no 0 līdz 7, kolonnas no 0 līdz F.

Brīdinājums: Visa informācija, ieskaitot atslēgu ar aizvietošanas tabulu, tiek ņemta par piemēru algoritma apsvēršanai!

Izmantojot "Sākotnējos datus", ir nepieciešams iegūt kriptogrāfijas transformācijas galvenā soļa darbības rezultātu.

1. Mēs izvēlamies daļu R = 05060708h un atslēgas elementu k1 = 'as28', heksadecimālā formā galvenais elements izskatīsies šādi: 61733238h. Tagad mēs veicam summēšanas operāciju mod 2 32:

Rīsi. 4

Kā redzat attēlā, mums nebija pārsūtīšanas 33 bitos, kas atzīmēti ar sarkanu un ar eksponentu “ 32 ". Un, ja mums būtu citas R un galvenā elementa vērtības, tas varēja notikt, un tad mēs to būtu ignorējuši un turpmāk izmantotu tikai dzeltenā krāsā atzīmētos bitus.

Šo darbību veicu ar montētāja komandu pievienot:

; eax = R, ebx = 'as28'

Šīs operācijas rezultāts Smod = 66793940h

1. Tagad vissarežģītākā operācija, bet, ja paskatās uzmanīgi, tā vairs nav tik briesmīga, kā šķiet sākumā. Iedomāsimies Smodu šādi:

ATTĒLS nav saglabāts

Rīsi. 5

Es mēģināju attēlā attēlot Smod elementus, bet es tomēr paskaidrošu:

s0 = 0, s1 = 4, s2 = 9 utt.

Tagad, sākot ar zemāko elementu s0, mēs veicam nomaiņu. Atceroties rindkopu " 3.2. Kriptogrāfijas pārveidošanas pamata posms»I - rinda, s i - kolonna, meklējiet vērtību nulles rindā un nulles kolonnā:

6. att

Tātad pašreizējā Smoda vērtība nav 6679394 0 h un 6679394 5 h.

Mēs turpinām nomainīt s1, t.i. četri. Izmantojot pirmo rindu un ceturto kolonnu (s1 = 4!). Mēs skatāmies uz attēlu:

Rīsi. 7

Tagad jau Smoda vērtība, nevis 667939 4 5h, 667939 2 5h. Es pieņemu, ka tagad aizstāšanas algoritms lasītājam ir skaidrs, un varu teikt, ka pēc Ssimple gala rezultāta būs šāda vērtība - 11e10325h.

Par to, kā to visvieglāk ieviest montētāja komandu veidā, es runāšu vēlāk nākamajā rindkopā, pēc tam, kad runāju par paplašināto tabulu.

1. Mums jāpārvieto iegūtā Ssimple vērtība 11 biti pa kreisi.

Rīsi. astoņi

Kā redzat, šī darbība ir diezgan vienkārša, un to īsteno viena montāžas valodas komanda - roll un šīs Srol operācijas rezultāts ir 0819288Fh.

1. Tagad paliek mūsu informācijas bloka L daļa, kas jānosaka ar Srol vērtību. Es ņemu kalkulatoru no w2k sp4 un saņemu Sxor = 091b2b8bh.
2. Šī darbība ir galīga, un mēs vienkārši piešķiram, notīrām R, L daļas vērtību un inicializējam L daļu ar Sxor vērtību.

Gala rezultāts:

L = 091b2b8bh, R = 01020304h

4.2 Algoritma ātruma palielināšana

Tagad parunāsim par algoritma optimizēšanu ātrumam. Projekta īstenošanas procesā jāņem vērā, ka programma, kas strādā ar reģistriem biežāk nekā ar atmiņu, darbojas visātrāk, un šeit arī šis spriedums ir ļoti svarīgs, jo vairāk nekā vienā informācijas blokā pat 32 šifrēšanas darbības!

Ieviešot šifrēšanas algoritmu savā programmā, es rīkojos šādi:

1. Atlasītā bloka daļa L uz eax reģistru un R uz edx.
2. Esi reģistrā, inicializēts ar paplašinātās atslēgas adresi, vairāk par to zemāk.
3. Reģistrā ebx ir piešķirta paplašinātās aizstāšanas tabulas adreses vērtība, vairāk par to zemāk
4. Pārsūtīja 1., 2., 3. posteņa informāciju uz pamata cikla 32 - З vai 32 - Р funkciju atkarībā no situācijas.

Ja paskatās uz galveno elementu plūsmas diagrammu punktā " Pamata cikli: "32-З", "32-Р"", Tad mūsu pamata cikla 32 - 3 atslēgu var attēlot šādi:

K 32-Z =

“As28”, “zw37”, “q839”, “7342”, “ui23”, “8e2t”, “wqm2”, “ewp1”,

“As28”, “zw37”, “q839”, “7342”, “ui23”, “8e2t”, “wqm2”, “ewp1”,

“Ewp1”, “wqm2”, “8e2t”, “ui23”, “7342”, “q839”, “zw37”, “as28”

Tie. no sākuma ir k1, k2, k3, k4, k5, k6, k7, k8 - ‘ kā 28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 'šī secība tiek atkārtota trīs reizes. Tad elementi iet apgrieztā secībā, ti: k8, k7, k6, k5, k4, k3, k2, k1 - “Ewp1”, “wqm2”, “8e2t”, “ui23”, “7342”, “q839”, “zw37”, “as28”.

Es iepriekš sakārtoju masīva elementus tādā secībā, kādā tie jāievada 32. - Z. Tādējādi es palielināju nepieciešamo atmiņu pēc gatavības principa, bet izglābu sevi no dažiem domāšanas procesiem, kas man nebija vajadzīgi, un palielināju ātrumu no algoritma, samazinot piekļuves laiku atmiņai! Šeit es aprakstīju tikai 32 - З atslēgu, 32. ciklam - Р es darīju to pašu, bet, izmantojot citu elementu piegādes shēmu, ko es arī aprakstīju punktā " Pamata cikli: “32-Z”, “32-P».

Tagad ir pienācis laiks aprakstīt aizstāšanas funkcijas ieviešanu, kā es solīju iepriekš. Es nevarēju aprakstīt agrāk, jo tam nepieciešams ieviest jaunu koncepciju - paplašinātu aizvietošanas tabulu. Es nevaru jums izskaidrot, kas tas ir. Tā vietā es jums to parādīšu, un jūs pats sev formulējat, kas tas ir - paplašināta aizvietošanas tabula?

Tātad, lai saprastu, kas ir paplašināta aizvietošanas tabula, mums ir nepieciešama, piemēram, aizstāšanas tabula, es ņemšu to, kas parādīts attēlā. 3.

Piemēram, mums bija jāaizstāj numurs 66793940h. Es to pasniegšu šādi:

ATTĒLS nav saglabāts

Rīsi. deviņi

Tagad, ja mēs ņemam elementus s1, s0, t.i. vismazāk nozīmīgais baits, aizstāšanas funkcijas rezultāts būs 25 stundas! Pēc Andreja Vinokurova raksta izlasīšanas, kuru es citēju rindkopā " Izmantotās literatūras saraksts", Jūs faktiski atklājat, ka, izvēloties divas rindas, jūs varat iegūt masīvu, kas ļauj ātri atrast aizvietojošos elementus, izmantojot komandu montētājs xlat. Viņi saka, ka to var izdarīt citā veidā ātrāk, bet Andrejs Vinokurovs apmēram četrus gadus pētīja ātrus algoritmus GOST ieviešanai! Es nedomāju, ka jums vajadzētu izgudrot riteni no jauna, kad jums tas jau ir.

Tātad, par masīvu:

Ņemsim pirmās divas rindas nulli un pirmo, izveidosim 256 baitu masīvu. Tagad mēs novērojam vienu īpatnību, ka, ja ir nepieciešams pārveidot 00h, tad rezultāts būs 75h (pamatojoties uz 3. attēlu) - mēs ievietojam šo vērtību masīvā nobīdē 00h. Mēs ņemam vērtību 01h, aizstāšanas funkcijas 79h rezultātu, ievietojam to masīvā pie nobīdes 01 un tā tālāk līdz 0FFh, kas mums dos 0FCh, ko mēs ievietosim masīvā nobīdē 0FFh. Tātad mēs ieguvām paplašinātu aizstāšanas tabulu pirmajai rindu grupai: pirmajai un nullei. Bet joprojām ir trīs grupas: otrā lapa 2, 3 lapa, trešā lapa 4, 5 lapa ceturtā lapa 6, lapa 7. Mēs ar šīm trim grupām rīkojamies tāpat kā ar pirmo. Rezultāts ir paplašināta aizvietošanas tabula!

Tagad mēs varam ieviest algoritmu, kas veiks nomaiņu. Lai to izdarītu, mēs ņemam vērā avota kodus, kurus Andrejs Vinokurovs ievietojis savā lapā, sk. Bibliogrāfija».

lea ebx, pagarināts_tabulas_vienkāršs

mov eax, [ievietojiet numuru, kas jāaizstāj]

pievienot ebx, 100h; pāriet uz nākamajiem diviem mezgliem

sub ebx, 300h; lai turpmāk ebx norādītu uz galdu

Tagad vēl viena iezīme, ar iepriekšējām darbībām mēs ne tikai nomainījām, bet arī mainījām numuru par 8 bitiem pa kreisi! Mums vienkārši jāpārvieto skaitlis vēl 3 biti pa kreisi:

un mēs iegūstam operācijas rol eax rezultātu, 11!

Es neko vairāk nevaru piebilst par optimizāciju, vienīgais, ko varu uzsvērt, ir tas, ko teicu iepriekš - biežāk lieto reģistrus, nevis piekļuvi atmiņai. Es domāju, ka šie vārdi ir tikai iesācējiem, pieredzējušiem un bez maniem vārdiem to lieliski saprot :).

Prasības pamatinformācijai.

Kā teikts Andreja Vinokurova rakstā, atslēga tiek izvēlēta pēc diviem kritērijiem:

- kritērijs bitu vienādam sadalījumam starp vērtībām 1 un 0. Parasti bitu vienlīdzīgas sadalījuma kritērijs ir Pīrsona kritērijs ("hī-kvadrāts").

Tas nozīmē atslēgu, principā jebkurš skaitlis var. Tas ir, kad tiek veidots nākamais atslēgas bits, tā inicializācijas varbūtība par vienu vai nulli ir 50/50!

Lūdzu, ņemiet vērā, ka atslēga sastāv no astoņiem elementiem, katrs no 32 bitiem, tāpēc atslēgā ir 32 * 8 = 256 biti un iespējamo atslēgu skaits ir 2 256! Vai tas tevi nepārsteidz? 🙂

- sērijas kritērijs.

Ja paskatāmies uz mūsu atslēgu, ko es iedevu rindkopā " 4.1 Šifrēšanas pārveidošanas galvenā posma īstenošana», Tad pamanīsit, ka ir derīgs šāds apzīmējums:

Rīsi. desmit

Vienā frāzē k 1 vērtību nedrīkst atkārtot ne k 2, ne citā atslēgas elementā.

Tas ir, atslēga, kuru esam izvēlējušies kā šifrēšanas algoritma apsvērumu, pilnībā atbilst diviem iepriekš minētajiem kritērijiem.

Tagad par aizvietošanas tabulas izvēli:

Tagad parunāsim par to, kā izvēlēties pareizo aizstāšanas tabulu. Galvenā prasība, lai izvēlētos aizstāšanas tabulas, ir elementu “neatkārtojamības” fenomens, no kuriem katrs ir 4 bitu liels. Kā redzējāt iepriekš, katra aizstāšanas tabulas rinda sastāv no vērtībām 0h, 1h, 2h, 3h,…, 0fh. Tātad galvenā prasība ir tāda, ka katrā rindā ir vērtības 0h, 1h, 2h, ..., 0fh un katra šāda vērtība vienā eksemplārā. Piemēram, secība:

1 2 3 4 5 6 7 8 9 A B C D E F

Tas pilnībā atbilst šai prasībai, bet tomēr! Nav ieteicams atlasīt šo secību kā virkni. Tā kā, ja jūs ievadāt vērtību funkcijas ievadē, kas balstās uz šādu virkni, tad izvadē jūs saņemsiet tādu pašu vērtību! Netici man? Tad ņemiet skaitli 332DA43Fh un astoņas šādas rindas kā aizstāšanas tabulu. Veiciet nomaiņas darbību, un es jums apliecinu, ka izeja būs skaitlis 332DA43Fh! Tas ir, tas pats, ko jūs iesniedzāt operācijas ievadam! Un tas neliecina par labu šifrēšanas formu, un vai tā bija? 🙂

Tā bija viena prasība, nākamais kritērijs saka - katram izejas bloka bitam jābūt statistiski neatkarīgam no katra ievades bloka bita!

Kā tas izskatās vienkāršāk? Un, lūk, piemēram, no iepriekš minētā skaitļa mēs izvēlējāmies elementu s0 = 0Fh, 01111b. Varbūtība, ka mēs pirmo bitu aizstāsim ar vienu vai nulli, ir 0,5! Varbūtība aizstāt otro, trešo un ceturto bitu, katru bitu, mēs atsevišķi apsveram ar vieniem vai nullēm, ir arī 0, 5. Izvēloties s1 = 0Eh, varbūtība, ka mēs esam nulles bits, un tas ir "0" , tiks aizstāts ar nulli vai pārāk vienāds - 0,5! Tādējādi saskaņā ar šo kritēriju nepastāv regularitāte starp elementu s0, s1 nulles bitu nomaiņu! Jā, jūs varētu aizstāt tos, bet jūs varētu aizstāt arī nulles. 🙂

Lai novērtētu tabulu pēc šī kritērija, varat izveidot korelācijas koeficientu tabulu, kas aprēķināta pēc formulas:

- ja p = 1, tad bita j vērtība pie izejas ir vienāda ar bita vērtību ievadē jebkurai ievades bitu kombinācijai;

- ja p = -1, tad bita j vērtība pie izejas vienmēr ir ieejas bita i apgrieztais;

- ja p = 0, tad izejas bits j ar vienādu varbūtību ņem vērtības 0 un 1 jebkurai ievades bita i fiksētajai vērtībai.

Ņemsim vienu rindas piemēru:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Sadalīsim to "komponentos":

Aprēķināsim vienu koeficientu saskaņā ar iepriekš minēto formulu. Lai būtu vieglāk saprast, kā tas tiek darīts, es paskaidrošu sīkāk:

- mēs ņemam 0. skaitļa (0) 0. bitu pie ievades un 0. skaitļa 0. bitu pie izejas (1), veicam operāciju 0 XOR 1 = 1.

- mēs ieejā ņemam 1. skaitļa (1) 0. bitu un izejā (1) 1. skaitļa 0. bitu, veicam operāciju 1 XOR 1 = 0.

- mēs ieejā ņemam 2. skaitļa (0) 0. bitu un 2 (0) bitu pie izejas (0), veicam operāciju 0 XOR 0 = 0.

- mēs ieejā ņemam 3. skaitļa (1) 0. bitu un 3 (0) bitu pie izejas (1), veicam operāciju 1 XOR 1 = 0.

Veicot secīgi XOR operācijas šajā secībā, mēs saskaitām visu vērtību vērtību, kas nav nulle, iegūstam vērtību 6. Tādējādi P 00 = 1- (6/2 4-1) = 0,25. Tātad, izrādījās, ka bita 0 vērtība pie izejas ir vienāda ar bita 0 vērtību pie ievades 4 gadījumos no 16;

Galīgā izredžu tabula:

Koeficientu tabula būs šāda (kam nav slinkums pārrēķināties)

	ieeja
Izeja		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Šajā tabulā viss ir vēl sliktāk - grupas 1. un 2. bits paliek nemainīgs! Kriptoanalītiķim ir kur griezties 🙂 Ņemot vērā visas šīs prasības, ar vienkāršu meklēšanu ("head -on") tika atrastas norādītajai teorijai atbilstošas ​​permutācijas tabulas (šodien - 1276 kombinācijas) Šeit ir dažas no tām:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Izmantotās literatūras saraksts.

1. Andreja Vinokurova raksts:

Šifrēšanas algoritms GOST 28147-89, tā izmantošana un ieviešana

Intel x86 platformas datoriem.

(var atrast: http://www.enlight.ru/crypto/frame.htm).

Ir arī avota kodi šifrēšanas algoritma ieviešanai.

1. Horsta Feistela raksts:

Kriptogrāfija un datoru drošība.

(var atrast tajā pašā adresē kā iepriekšējais raksts)

1. Ross N. Viljamss:

Elementārs ceļvedis CRC kļūdu noteikšanas algoritmiem

Publicēts vietnē www.wasm.ru.

Pateicības.

Vēlos izteikt pateicību visiem foruma www.wasm.ru apmeklētājiem. Bet es īpaši vēlos pateikties ChS, kurš šobrīd ir pazīstams kā SteelRat, viņš palīdzēja man saprast lietas, kuras es, iespējams, nekad nebūtu sapratis, kā arī palīdzēja rakstīt rindkopu: “ Galvenās informācijas prasības”, Šīs rindkopas galveno daļu ir uzrakstījis viņš. Es esmu arī ļoti pateicīgs KSTU darbiniekam, kas nosaukts vārdā A.N. Tupolevs Aņikins Igors Vjačeslavovičs un būtu grēks nepieminēt Krisu Kasperski par to, ka viņš ir, un Volodja / wasm.ru par viņa norādījumiem. Ak, un es to saņemu no viņa :). Es arī gribu atzīmēt Sega-Zero / Callipso, bet tas man ienesa prātā dažus matemātiskus džungļus.

Iespējams, tas ir viss, ko es gribētu jums pateikt.

Es būtu pateicīgs par kritiku vai jautājumiem, kas saistīti ar šo rakstu vai vienkārši padomu. Mana kontaktinformācija: [pasts aizsargāts], ICQ - 337310594.

Ar cieņu, Evil`s Interrupt.

P.S .: Ar šo rakstu es necentos nevienu pārspēt. Tas tika uzrakstīts ar nolūku, lai atvieglotu GOST izpēti, un, ja jums rodas grūtības, tas nenozīmē, ka esmu vainīgs. Esiet saprātīgs un pacietīgs, visu to labāko jums!

Šis algoritms ir obligāts lietošanai kā šifrēšanas algoritms Krievijas Federācijas valsts organizācijās un vairākās komerciālajās.

Algoritma apraksts

Algoritma diagramma ir parādīta attēlā. 3.1. Kā redzat, šī algoritma shēma ir diezgan vienkārša, kas nepārprotami vienkāršo tā programmatūras vai aparatūras ieviešanu.

GOST 28147-89 algoritms šifrē informāciju 64 bitu blokos, kas ir sadalīti divos apakšbloķos pa 32 bitiem (N1 un N2). Apakšbloku N1 apstrādā noteiktā veidā, pēc tam tiek pievienota tā vērtība

ar apakšbloka vērtību N2 (pievienošana tiek veikta modulo 2), tad apakšbloki tiek apmainīti. Šāda pārveidošana tiek veikta noteiktam raundu skaitam: 16 vai 32, atkarībā no algoritma darbības režīma (aprakstīts zemāk). Katrā kārtā tiek veiktas šādas darbības:

1. Atslēgas pārklājums. Apakšbloku / VI saturs tiek pievienots modulo 2 32 ar daļu no Kx taustiņa.

GOST 28147-89 algoritma šifrēšanas atslēgas izmērs ir 256 biti, un Kx ir tā 32 bitu daļa, tas ir, 256 bitu šifrēšanas atslēga tiek attēlota kā 32 bitu apakšatslēgu savienojums (3.2. Att.) :

SH ATI, AG2, YU, AG4, K5, KB, K7.

Šifrēšanas procesā tiek izmantota viena no šīm apakšatslēgām, atkarībā no kārtas kārtas un algoritma darbības režīma.

Rīsi. 3.1. Algoritma shēma GOST 28147-

Rīsi. 3.2. Algoritma šifrēšanas atslēga GOST 28147-89

2. Tabulas nomaiņa. Pēc atslēgas uzlikšanas apakšbloks / VI tiek sadalīts 8 daļās no 4 bitiem, un katra no tiem vērtība tiek individuāli aizstāta saskaņā ar šīs apakšbloka daļas nomaiņas tabulu. Aizstāšanas kastes (S-box) bieži tiek izmantotas mūsdienu šifrēšanas algoritmos, tāpēc ir vērts tos sīkāk apsvērt.

Tabulas aizstāšana tiek izmantota šādā veidā: ievadē tiek ievadīts noteiktas dimensijas (šajā gadījumā 4 bitu) datu bloks, kura skaitliskais attēlojums nosaka izvades vērtības numuru. Piemēram, mums ir šādas formas S-lodziņš:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Ļaujiet 4 bitu blokam "0100" nonākt pie ieejas, tas ir, vērtības 4. Saskaņā ar tabulu, izvades vērtība būs 15, tas ir. "1111" (0 tiek aizstāts ar 4, 1 tiek aizstāts ar 11, vērtība 2 nemainās utt.).

Kā redzat, algoritma shēma ir ļoti vienkārša, kas nozīmē, ka lielākā datu šifrēšanas slodze attiecas uz aizstāšanas tabulām. Diemžēl algoritmam piemīt īpašība, ka pastāv “vājas” aizvietošanas tabulas, kuras lietojot, algoritmu var atklāt ar kriptoanalīzes metodēm. Vājās ir, piemēram, tabula, kurā izlaide ir vienāda ar ievadi:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitu cikliska kreisā nobīde par 11 bitiem.

Algoritma darbības režīmi

GOST 28147-89 algoritmam ir 4 darbības režīmi:

□ vienkāršs nomaiņas režīms;

□ gamma režīms;

P gamma režīms ar atgriezenisko saiti;

□ simulatoru ražošanas veids.

Šie režīmi nedaudz atšķiras no vispārpieņemtajiem (aprakstīti 1.4. Sadaļā), tāpēc ir vērts tos sīkāk apsvērt.

Šiem režīmiem ir dažādi mērķi, taču tie izmanto to pašu šifrēšanas transformāciju, kas aprakstīta iepriekš.

Vienkāršs nomaiņas režīms

Vienkāršās nomaiņas režīmā iepriekš aprakstītās 32 kārtas tiek vienkārši veiktas, lai šifrētu katru 64 bitu informācijas bloku. 32 bitu apakšatslēgas tiek izmantotas šādā secībā:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI utt. - 1. līdz 24. kārtā;

□ K1, Kb, K5, K4, KZ, K2, K \, KO - kārtās no 25. līdz 32. datumam.

Atšifrēšana vienkāršā nomaiņas režīmā tiek veikta tieši tādā pašā veidā, bet ar nedaudz atšķirīgu apakšatslēgu secību:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - kārtās no 1 līdz 8;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb u.c. - kārtās no 9. līdz 32. vietai.

Līdzīgi kā standarta ECB režīmā, atsevišķu bloku šifrēšanas dēļ vienkāršu nomaiņas režīmu stingri neiesaka šifrēt pašus datus; to vajadzētu izmantot tikai citu šifrēšanas atslēgu šifrēšanai vairāku atslēgu shēmās.

Gamma režīms

Gamma režīmā (3.3. Att.) Katram vienkāršā teksta blokam tiek pievienots bitu modulis 2 ar 64 bitu šifra gamma bloku. Šifra gamma ir īpaša secība, kas tiek ģenerēta, izmantojot iepriekš aprakstītās transformācijas šādi:

1. Reģistros N1 un N2 tiek ierakstīts to sākotnējais aizpildījums-64 bitu vērtība, ko sauc par "sinhronizētu pārrāvumu" (sinhronizētā pārrāvums praksē ir inicializācijas vektora analogs CBC, CFB un OFB režīmos).

2. Reģistru / VI un N2 satura šifrēšana (šajā gadījumā - sinhronizācijas ziņojumi) tiek veikta vienkāršā nomaiņas režīmā.

3. N1 saturs tiek pievienots modulo (2 32 - 1) ar konstantu CI = 2 24 + 2 16 + 2 8 + 4, pievienošanas rezultāts tiek ierakstīts / VI reģistrā.

4. N2 saturam pievieno modulo 2 ar konstanti C2 = 2 24 + 2 16 + 2 8 +1, pievienošanas rezultāts tiek ierakstīts N2 reģistrā.

5. Reģistru / VI un N2 saturs tiek izvadīts kā 64 bitu šifra gamma bloks (ti, šajā gadījumā / VI un N2 veido pirmo gamma bloku).

6. Ja ir nepieciešams nākamais gamma bloks (ti, jums jāturpina šifrēšana vai atšifrēšana), jūs atgriežaties 2. darbībā.

Atšifrēšanai gamma tiek ģenerēta līdzīgā veidā, pēc tam XOR darbība atkal tiek piemērota šifrētajam tekstam un gamma bitiem.

Lai ģenerētu tādu pašu šifra gammu, lietotājam, kurš atšifrē kriptogrammu, ir jābūt tai pašai atslēgai un vienai un tai pašai sinhronizācijas ziņojuma vērtībai, kas tika izmantota informācijas šifrēšanai. Pretējā gadījumā oriģinālo tekstu nevarēs iegūt no šifrētā teksta.

Lielākajā daļā GOST 28147-89 algoritma ieviešanas sinhronizācijas ziņojums nav slepens elements, tomēr sinhronizācijas ziņojums var būt tikpat slepens kā šifrēšanas atslēga. Šajā gadījumā mēs varam pieņemt, ka algoritma atslēgas faktiskais garums (256 biti) tiek palielināts par vēl 64 sinhronizācijas ziņojuma bitiem, ko var uzskatīt par papildu atslēgas elementu.

Gamma režīms ar atgriezenisko saiti

Gamma režīmā ar atgriezenisko saiti, aizpildot reģistrus / VI un L / 2, sākot ar 2. bloku, netiek izmantots iepriekšējais gamma bloks, bet gan iepriekšējā vienkāršā teksta bloka šifrēšanas rezultāts (3.4. Att.) . Pirmais bloks šajā režīmā tiek ģenerēts pilnīgi līdzīgi kā iepriekšējais.

Rīsi. 3.4. Šifra gamma ģenerēšana atgriezeniskās saites gamma režīmā

Simulatora ražošanas veids

Prefikss ir kriptogrāfijas kontrolsumma, kas aprēķināta, izmantojot šifrēšanas atslēgu, lai pārbaudītu ziņojumu integritāti. Lai to aprēķinātu, ir īpašs algoritma GOST 28147-89 režīms.

Simulatora ģenerēšana tiek veikta šādi:

1. Pirmais 64 bitu informācijas bloks, kuram tiek aprēķināts prefikss, tiek ierakstīts reģistros N1 un N2 un šifrēts vienkāršotās nomaiņas samazinātajā režīmā, kurā tiek veiktas pirmās 16 kārtas no 32.

2. Iegūtais rezultāts tiek summēts modulo 2 ar nākamo informācijas bloku, rezultātu saglabājot N1 un N2.

3. M un N2 atkal tiek šifrēti samazinātas vienkāršas nomaiņas režīmā un tā tālāk līdz pēdējam informācijas blokam.

Imitators ir 64 bitu iegūtais N1 un N2 reģistra saturs vai tā daļa. Tiek izmantots visbiežāk lietotais 32 bitu prefikss, tas ir, puse no reģistra satura. Ar to pietiek, jo, tāpat kā jebkura kontrolsumma, simulators galvenokārt ir paredzēts aizsardzībai pret nejaušu informācijas sagrozīšanu. Lai pasargātu no apzinātas datu pārveidošanas, tiek izmantotas citas kriptogrāfijas metodes - pirmkārt, elektroniskais ciparparaksts (sk. 1.1. Sadaļu).

Imitatoru izmanto šādi:

1. Šifrējot jebkādu informāciju, tiek aprēķināts vienkārša teksta prefikss un nosūtīts kopā ar šifrēto tekstu.

2. Pēc atšifrēšanas prefikss tiek vēlreiz aprēķināts un salīdzināts ar nosūtīto.

3. Ja aprēķinātie un nosūtītie prefiksi nesakrīt - pārraides laikā tika izkropļots šifra teksts vai atšifrēšanas laikā tika izmantotas nepareizas atslēgas.

Prefikss ir īpaši noderīgs, lai pārbaudītu pareizu galvenās informācijas atšifrēšanu, izmantojot vairāku taustiņu shēmas.

Imitators ir kāds MAC ziņojuma autentifikācijas koda analogs, kas aprēķināts CBC režīmā; atšķirība ir tāda, ka sinhronizācijas ziņojums netiek izmantots prefiksa aprēķināšanai, turpretī inicializācijas vektors tiek izmantots MAC aprēķināšanai.

Algoritma kriptogrāfijas spēks

1994. gadā GOST 28147-89 algoritma apraksts tika tulkots angļu valodā un publicēts; tieši pēc tam sāka parādīties viņa ārvalstu ekspertu veiktās analīzes rezultāti; tomēr ilgu laiku neviens uzbrukums netika atzīts par iespējamu.

□ liels atslēgas garums - 256 biti; kopā ar slepeno sinhronizācijas ziņojumu efektīvais atslēgas garums tiek palielināts līdz 320 bitiem;

□ 32 pārvērtību kārtas; pēc 8 kārtām tiek sasniegts pilns ievades datu izkliedes efekts: viena teksta bloka bita izmaiņas ietekmēs visus šifrētā teksta bloka bitus un otrādi, tas ir, ir vairākas drošības rezerves.

Apsveriet GOST 28147-89 algoritma kriptoanalīzes rezultātus.

Aizvietošanas tabulu analīze

Tā kā aizstāšanas tabulas nav iekļautas standartā, vairāki darbi (piemēram, c) liecina, ka "kompetenta organizācija" var izveidot gan "labas", gan "sliktas" aizstāšanas tabulas. Tomēr slavenais eksperts Brūss Šneiers šādus pieņēmumus sauc par "baumām". Ir skaidrs, ka algoritma kriptogrāfiskā stiprība lielā mērā ir atkarīga no izmantoto aizvietošanas tabulu īpašībām; attiecīgi ir vājas nomaiņas tabulas (skat. Piemēru iepriekš), kuru izmantošana var vienkāršot uzbrukumu algoritmam. Tomēr iespēja izmantot dažādas aizvietošanas tabulas šķiet ļoti cienīga ideja, par kuru var minēt divus faktus no DES šifrēšanas standarta vēstures (sīkāku informāciju skatīt 3.15. Sadaļā):

□ uzbrukumos, izmantojot gan lineāro, gan diferenciālo DES algoritma kriptoanalīzi, tiek izmantotas aizvietošanas tabulu īpatnības; izmantojot citas tabulas, kriptoanalīze būs jāsāk no jauna;

□ ir mēģināts nostiprināt DES pret lineāro un diferenciālo kriptoanalīzi, izmantojot stabilākas aizvietošanas tabulas; šādas tabulas, kas patiešām ir izturīgākas, tika piedāvātas, piemēram, s 5 DES algoritmā; bet, diemžēl, nebija iespējams aizstāt DES ar s 5 DES, jo aizstāšanas tabulas ir stingri definētas standartā, attiecīgi, algoritma ieviešana, iespējams, neatbalsta iespēju mainīt tabulas uz citām.

Vairākos darbos (piemēram, un) tiek kļūdaini secināts, ka algoritma GOST 28147-89 aizvietotāju slepenās tabulas var būt daļa no atslēgas un palielināt tā faktisko garumu (kas ir nenozīmīgi, jo algoritmam ir ļoti liela 256 bitu atslēga). Tomēr darbs pierādīja, ka slepenās aizstāšanas tabulas var aprēķināt, izmantojot šādu uzbrukumu, ko var izmantot praksē:

1. Tiek iestatīta nulles atslēga un tiek veikta “nulles vektora” meklēšana, tas ir, vērtības z = / (0), kur / () ir algoritma kārtas funkcija. Šis posms aizņem apmēram 2 šifrēšanas darbības.

2. Izmantojot nulles vektoru, tiek aprēķinātas aizvietošanas tabulu vērtības, kas prasa ne vairāk kā 2 11 operācijas.

Algoritmu modifikācijas un to analīze

Darbā tika veikta GOST 28147-89 algoritma modifikāciju kriptoanalīze:

□ GOST-H algoritms, kurā attiecībā pret sākotnējo algoritmu tiek mainīta apakšatslēgu izmantošanas secība, proti, 25. līdz 32. kārtā apakšatslēgas tiek izmantotas tiešā secībā, tas ir, tādā pašā veidā kā iepriekšējās algoritma kārtas;

□ 20 kārtu GOST® algoritms, kas izmanto XOR, lai lietotu atslēgu, nevis modulo 32 papildinājumu.

Pamatojoties uz analīzes rezultātiem, tika secināts, ka GOST-H un GOST © ir vājāki nekā sākotnējais GOST 28147-89 algoritms, jo abiem ir vāju atslēgu klases. Jāatzīmē, ka GOST © kriptoanalīzes daļā darbs vārdu pa vārdam atkārto sadaļu, kas veltīta algoritma GOST 28147-89 kriptoanalīzei, ko 2000. gadā publicēja labi zināms darbs (bez atsaucēm uz oriģinālu) . Tas liek apšaubīt darba autoru profesionalitāti un pārējos tā rezultātus.

Darbā tiek piedāvāta ļoti interesanta algoritma modifikācija: tabulām S \… Ss jābūt atšķirīgām; katrā algoritma kārtā tie ir jāpārkārto saskaņā ar noteiktu likumu. Šī permutācija var būt atkarīga no šifrēšanas atslēgas vai arī tā var būt slepena (tas ir, tā var būt daļa no šifrēšanas atslēgas, kas ir lielāka par sākotnējo 256 bitu atslēgu). Abas šīs iespējas, pēc to autoru domām, ievērojami palielina algoritma pretestību pret lineāro un diferenciālo kriptoanalīzi.

Un vēl viena modifikācija, kas saistīta ar aizstāšanas tabulām, ir dota darbā, kurā tiek analizēta viena no iespējamām metodēm aizstāšanas tabulu aprēķināšanai, pamatojoties uz šifrēšanas atslēgu. Darba autori secināja, ka šāda atkarība vājina algoritmu, jo tas noved pie vāju atslēgu klātbūtnes un dažām iespējamām algoritma ievainojamībām.

Pilnīga algoritma analīze

Ir uzbrukumi pilna apļa GOST 28147-89 bez jebkādām izmaiņām. Viens no pirmajiem atklātajiem dokumentiem, kas analizē algoritmu, labi pazīstams raksts, ir veltīts uzbrukumiem, kuros tiek izmantotas vairāku labi zināmu šifrēšanas algoritmu atslēgu paplašināšanas procedūras vājās vietas. Jo īpaši pilna apļa GOST 28147-89 algoritmu var salauzt, izmantojot diferencētu kriptoanalīzi saistītajās atslēgās, bet tikai tad, ja tiek izmantotas vājas aizstāšanas tabulas. Algoritma 24 raundu versija (kurai trūkst pirmo 8 raundu) tiek atvērta tādā pašā veidā visām maiņas tabulām, taču spēcīgas maiņas tabulas (piemēram, parādītas c) padara šādu uzbrukumu pilnīgi nepraktisku.

Pašmāju zinātnieki A. G. Rostovcevs un E. B. Makhovenko 2001. gadā savā darbā ierosināja principiāli jaunu kriptoanalīzes metodi (pēc autoru domām, daudz efektīvāku par lineāro un diferenciālo kriptoanalīzi), veidojot objektīvu funkciju no zināma vienkārša teksta, kas atbilst tam šifrētajam tekstam un vēlamajam atslēgas vērtību un atrast tās galējību, kas atbilst patiesajai atslēgas vērtībai. Viņi arī atrada lielu GOST 28147-89 algoritma vājo atslēgu klasi, kas ļauj salauzt algoritmu, izmantojot tikai 4 atlasītus vienkāršus tekstus un atbilstošus šifrētus tekstus ar diezgan zemu sarežģītību. Darbā tiek turpināta algoritma kriptoanalīze.

2004. gadā Korejas speciālistu grupa ierosināja uzbrukumu, ar kura palīdzību, izmantojot diferencētu kriptoanalīzi saistītajās atslēgās, ar 91,7% varbūtību iespējams iegūt 12 slepenās atslēgas bitus. Uzbrukumam nepieciešami 2 35 atlasīti vienkāršie teksti un 2 36 šifrēšanas operācijas. Kā redzat, šis uzbrukums ir praktiski bezjēdzīgs reālam uzbrukumam algoritmam.

Algoritms GOST 28147-89 un šifrs "Magma" (GOST R 34.12-2015)

Algoritma vispārējā shēma. Algoritms, kas aprakstīts GOST 28147-89 “Informācijas apstrādes sistēmas. Kriptogrāfiskā aizsardzība. Kriptogrāfijas pārveidošanas algoritms ", ir vietējais simetriskās šifrēšanas standarts (līdz 2016. gada 1. janvārim) un ir obligāts ieviešanai sertificētos kriptogrāfiskās informācijas aizsardzības rīkos, ko izmanto valsts informācijas sistēmās un dažos gadījumos arī komerciālās sistēmās. Informācijas kriptogrāfiskās aizsardzības līdzekļu sertifikācija ir nepieciešama, lai aizsargātu informāciju, kas ir Krievijas Federācijas valsts noslēpums, un informāciju, kuras konfidencialitāte ir jānodrošina saskaņā ar spēkā esošajiem tiesību aktiem. Arī Krievijas Federācijā banku informācijas sistēmu aizsardzībai ieteicams izmantot algoritmu GOST 28147-89.

GOST 28147-89 algoritms (2.21. Att.) Ir balstīts uz Feistela shēmu un šifrē informāciju 64 bitu blokos, kas ir sadalīti divos 32 bitu apakšblokos (I un R). Apakšbloks R, tiek apstrādāta ar apaļās transformācijas funkciju, pēc kuras tās vērtība tiek pievienota apakšbloka Lj vērtībai, pēc tam apakšbloki tiek apmainīti. Algoritmam ir 16 vai 32 kārtas, atkarībā no šifrēšanas režīma (imitācijas ievietošanas aprēķins vai citi šifrēšanas režīmi).

Rīsi. 2.21.

Katrā algoritma kārtā tiek veiktas šādas transformācijas.

1. Atslēgas pārklājums. Apakšbloķēt saturu R i pievienots modulo 2 32 ar apaļo atslēgu K. Kj ir sākotnējās atslēgas 32 bitu daļa, ko izmanto kā apaļo atslēgu. GOST 28147-89 ns algoritms izmanto atslēgu paplašināšanas procedūru, sākotnējā 256 bitu šifrēšanas atslēga tiek attēlota kā astoņu 32 bitu apakšatslēgu saplūšana (salikšana) (2.22. Att.): K 0, K (, K t K, K A, K 5, K 6, K 7.

Šifrēšanas procesā tiek izmantota viena no šīm apakšatslēgām. TO

No 1. līdz 24. kārtai - tiešā secībā:

No 25. līdz 32. kārtai - apgrieztā secībā:

Rīsi. 2.22. GOST 28147-89 algoritma šifrēšanas atslēgas struktūra

2. Tabulas nomaiņa. Pēc tam, kad atslēga ir piemērota, apakšbloks R i ir sadalīta astoņās daļās, bet 4 bitos, un katras no tām vērtība tiek atsevišķi nomainīta saskaņā ar tās nomaiņas tabulu (S-box). Kopumā tiek izmantotas astoņas S -kastes - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Katrs GOST 28147-89 algoritma S bloks ir vektors (viendimensiju masīvs) ar ^ elementiem, kas numurēti no 0 līdz 15. S bloka vērtības ir 4 bitu skaitļi; veseli skaitļi no 0 līdz 15.

No S-box tabulas tiek ņemts elements, kura kārtas numurs sakrīt ar vērtību, kas tika iegūta aizvietošanas ievadē.

Piemērs 2.6.

Lai ir šādas formas S-bloks:

Ļaujiet šīs S kastes ievadei piešķirt vērtību 0100 2 = 4. S kastes izeja būs aizstāšanas tabulas 4. elements, ti. 15 = 1111 2 (elementi ir numurēti, sākot no nulles).

aizstājējus standarts nenosaka, kā tas tiek darīts, piemēram, DES šifrā. Mainīgas aizvietošanas tabulu vērtības ievērojami sarežģī algoritma kriptoanalīzi. Tajā pašā laikā algoritma stabilitāte būtībā ir atkarīga no to pareizās izvēles.

Diemžēl algoritmam GOST 28147-89 ir “vājas” aizvietošanas tabulas, kuras izmantojot, algoritmu var diezgan viegli atklāt ar kriptoanalīzes metodēm. Starp "vājajiem" ir, piemēram, triviāla aizstāšanas tabula, kurā ievade ir vienāda ar rezultātu (2.16. Tabula).

2.16. Tabula

Vājas S kastes piemērs

Tiek uzskatīts, ka aizvietošanas tabulu īpašās vērtības ir jātur slepenībā un tās ir ilgtermiņa galvenais elements, t.i. ir derīgas daudz ilgāk nekā atsevišķas atslēgas. Tomēr aizvietošanas tabulu slepenās vērtības nav daļa no atslēgas un nevar palielināt tās faktisko garumu.

Patiešām, slepenās aizstāšanas tabulas var aprēķināt, izmantojot šādu uzbrukumu, ko var izmantot praksē:

• tiek iestatīta nulles atslēga un tiek veikta "nulles vektora" meklēšana, t.i. nozīme z = F ( 0), kur F - algoritma apaļās transformācijas funkcija. Tas prasa apmēram 2 32 testa šifrēšanas darbības;
• izmantojot nulles vektoru, tiek aprēķinātas aizvietošanas tabulu vērtības, kas prasa ne vairāk kā 2 11 operācijas.

Tomēr, pat ja tiek pārkāpta aizstāšanas tabulu konfidencialitāte, šifra stiprums joprojām ir ārkārtīgi augsts un nesasniedz zem pieļaujamās robežas.

Tiek arī pieņemts, ka aizvietošanas tabulas ir kopīgas visiem šifrēšanas mezgliem tajā pašā kriptogrāfijas aizsardzības sistēmā.

S-kastes struktūras uzlabošana ir viena no visintensīvāk pētītajām problēmām simetrisko bloku šifru jomā. Būtībā ir nepieciešams, lai visas izmaiņas S-kastes ieejās izplūst nejaušišķietami mainot izlaidi. No vienas puses, jo lielākas ir S kastes, jo algoritms ir izturīgāks pret lineārās un diferenciālās kriptoanalīzes metodēm. No otras puses, lielu nomaiņas galdu ir grūtāk noformēt.

Mūsdienu algoritmos S-kastes parasti ir vektors (viendimensiju masīvs) 2 "t- bitu elementi. Bloka ievade nosaka elementa numuru, kura vērtība kalpo kā S bloka izeja.

S-kastes projektēšanai ir izvirzīti vairāki kritēriji. Aizstāšanas tabulai jāatbilst:

• stingrs lavīnas kritērijs;
• bitu neatkarības kritērijs;
• nelinearitātes prasība no ievades vērtībām.

Lai izpildītu pēdējo prasību, tika ierosināts norādīt lineāru kombināciju i biti ( es = 1, ..., T) aizvietošanas tabulas vērtības saliektas funkcijas(eng, liekts - atkāpjoties, šajā gadījumā - no lineārajām funkcijām). Saliektas funkcijas veido īpašu Būla funkciju klasi, ko raksturo augstākā nelinearitātes klase un atbilstība stingrajam lavīnas kritērijam.

Dažos darbos S-kastēm tiek piedāvāts pārbaudīt y pasūtījuma garantētā lavīnas efekta īstenošanu-mainoties vienam ievades bitam, mainās vismaz S-box izejas biti. Garantētā lavīnas efekta īpašība, kas ir no y līdz 2 līdz 5, nodrošina pietiekami labas S-kastes izkliedes īpašības jebkuram šifrēšanas algoritmam.

Izstrādājot pietiekami lielas nomaiņas tabulas, var izmantot šādas pieejas:

• nejauša atlase (mazām S kastēm tas var novest pie vāju aizvietošanas tabulu izveidošanas);
• nejauša atlase, kam seko pārbaude par atbilstību dažādiem kritērijiem, un vāju S-lodziņu noraidīšana;
• manuāla izvēle (pārāk darbietilpīga lieliem S blokiem);
• matemātiska pieeja, piemēram, ģenerēšana, izmantojot liektas funkcijas (šī pieeja tiek izmantota CAST algoritmā).

Var piedāvāt šādu GOST 28147-89 algoritma atsevišķu S bloku izstrādes procedūru:

• katru S lodziņu var aprakstīt ar četrām loģiskām funkcijām, katrai no funkcijām jābūt četriem loģiskiem argumentiem;
• šīm funkcijām jābūt pietiekami sarežģītām. Šo sarežģītības prasību nevar formāli izteikt, tomēr kā nepieciešams nosacījums var pieprasīt, lai atbilstošās loģiskās funkcijas, kas uzrakstītas minimālā formā (ti, ar minimālo iespējamo izteiksmes garumu), izmantojot pamata loģiskās darbības, nebūtu īsākas par noteikta nepieciešamā vērtība;
• atsevišķām funkcijām, pat ja tās izmanto dažādās aizstāšanas tabulās, jābūt pietiekami atšķirīgām.

2011. gadā tika ierosināts jauns uzbrukums "refleksīva sanāksme vidū", kas nedaudz samazina GOST 28147-89 pretestību (no 2256 līdz 2225). Labākais algoritma kriptoanalīzes rezultāts no 2012. gada samazina tā spēku līdz 2192, kas prasa salīdzinoši lielu šifrētā teksta izmēru un iepriekš sagatavotu datu apjomu. Neskatoties uz ierosinātajiem uzbrukumiem, GOST 28147-89 pašreizējā datortehnoloģijas attīstības līmenī paliek praktiski stabils.

Kods "Magma" (GOST R 34.12-2015). GOST 28147-89 standarts Krievijā ir spēkā vairāk nekā 25 gadus. Šajā laikā tas ir parādījis pietiekamu programmatūras un aparatūras ieviešanas izturību un labu efektivitāti, ieskaitot ierīces, kurās ir maz resursu. Lai gan ir ierosināti kriptoanalītiskie uzbrukumi, kas samazina tās pretestības aprēķinus (labākais ir līdz 2192), tie nebūt nav iespējami. Tāpēc tika nolemts iekļaut GOST 28147-89 algoritmu jaunizveidotajā simetriskajā šifrēšanas standartā.

2015. gada veikalā tika pieņemti divi jauni valsts kriptogrāfijas standarti: GOST R 34.12-2015 “Informācijas tehnoloģijas. Kriptogrāfiskās informācijas aizsardzība. Bloķēt šifrus "un GOST R 34.13-2015" Informācijas tehnoloģijas. Kriptogrāfiskās informācijas aizsardzība. Bloku šifru darbības režīmi ", kas stājas spēkā 2016. gada 1. janvārī.

GOST R 34.12-2015 standarts satur divu bloku šifru aprakstu ar bloka garumu 128 un 64 biti. GOST 28147-89 šifrs ar fiksētiem nelineāriem aizvietošanas blokiem ir iekļauts jaunajā GOST R 34.12-2015 kā 64 bitu šifrs ar nosaukumu "Magma".

Zemāk ir standarta nomaiņas bloki:

Standartā norādītais S-box komplekts nodrošina labākās īpašības, kas nosaka kriptoalgoritma pretestību diferenciālajai un lineārajai kriptoanalīzei.

Saskaņā ar Standartizācijas tehniskās komitejas "Informācijas kriptogrāfiskā aizsardzība" (TC 26) datiem, nelineāru aizvietošanas bloku noteikšana padarīs GOST 28147-89 algoritmu vienotāku un palīdzēs novērst "vāju" nelineāru aizvietošanas bloku izmantošanu. Turklāt visu šifra ilgtermiņa parametru fiksācija standartā atbilst atzītajai starptautiskajai praksei. Jaunais standarts GOST R 34.12-2015 ir terminoloģiski un konceptuāli saistīts ar starptautiskajiem standartiem ISO / IEC 10116 “Informācijas tehnoloģijas. Drošības metodes. "Bitu bloku šifru" darbības režīmi (ISO / IEC 10116: 2006 Informācijas tehnoloģijas - Drošības metodes - N bitu bloku šifra darbības režīmi) un ISO / IEC 18033 sērija "Informācijas tehnoloģija. Drošības nodrošināšanas metodes un līdzekļi. Šifrēšanas algoritmi ": ISO / IEC 18033-1: 2005" 1. daļa. Vispārīgi "(ISO / IEC 18033-1: 2005 Informācijas tehnoloģijas - Drošības metodes - Šifrēšanas algoritmi - 1. daļa: Vispārīgi) un ISO / IEC 18033-3: 2010 "3. daļa. Bloķēt šifrus" (ISO / IEC 18033-3: 2010 (Informācijas tehnoloģijas - Drošības paņēmieni - Šifrēšanas algoritmi - 3. daļa: Bloķētie šifri)).

GOST P 34.12-2015 standarts ietver arī jaunu bloku šifru ("Grasshopper") ar bloka izmēru 128 biti. Paredzams, ka šis šifrs būs izturīgs pret visiem šodien zināmiem bloķētu šifru uzbrukumiem.

Bloku šifru darbības režīmi (vienkārša nomaiņa, gamma, gamma ar atgriezenisko saiti, gamma ar šifrētu tekstu, vienkārša nomaiņa ar ieslēgšanu un imitācijas ieliktņa izstrāde) ir iekļauti atsevišķā standartā GOST R 34.13-2015, kas atbilst pieņemto starptautisko praksi. Šie režīmi ir piemērojami gan Magma, gan jaunajam Grasshopper šifram.

• Tiek veikta apļveida kreisā nobīde par 11 bitiem. Atšifrēšana tiek veikta saskaņā ar to pašu shēmu, bet ar atšķirīgu atslēgu lietošanas grafiku: no 1. līdz 8. atšifrēšanas kārtai - tiešā secībā: no 9. līdz 32. atšifrēšanas kārtai - apgrieztā secībā: Salīdzinājumā ar DES šifram GOST 28147-89 ir šādas priekšrocības: ievērojami garāka atslēga (256 biti, salīdzinot ar 56 DES šifram), uzbrukums, kuram ar brutālu spēku uzskaitīt atslēgu komplektu šobrīd šķiet neiespējami; vienkāršs atslēgas lietošanas grafiks, kas vienkāršo algoritma ieviešanu un palielina aprēķinu ātrumu. S-bloku dizains GOST 28147-89. Ir skaidrs, ka algoritma GOST 28147-89 shēma ir ļoti vienkārša. Tas nozīmē, ka vislielākā šifrēšanas slodze attiecas uz aizstāšanas tabulām. Cilnes vērtības
• Panasepko S.P. Šifrēšanas algoritmi: īpaša uzziņu grāmata. SPb.: BHV-Peter-Burg, 2009.
• Kara O. Pārdomu uzbrukumi produktu šifriem. URL: http://eprint.iacr.org/2007/043.pdf
• Krievijas šifrēšanas standarts: samazināts spēks. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Acheksejevs E. K., Smyshlyaev S. V. GOST 28147-89: "Nesteidzieties viņu apglabāt."

Slavenais pētnieks, algebriskās kriptoanalīzes dibinātājs Nikolass Kortuāšs apgalvo, ka GOST bloka šifrs, kuram tuvākajā laikā bija jākļūst par starptautisku standartu, patiesībā ir salauzts un nākotnē gaida daudzas publikācijas, kurām vajadzētu attīstīt savas idejas par šī algoritma nestabilitāte.

Tālāk ir īsi fragmenti no šī darba, ko var uzskatīt par satraucošu uzbrukumu starptautiskās standartizācijas vidū (autors bija pazīstams ar līdzīgiem pārspīlējumiem saistībā ar AES, taču viņa darbam bija liela teorētiska ietekme uz kriptoanalīzi, bet neizraisīja praktiskus uzbrukumus pašam AES). Bet, iespējams, tas ir arī reāls brīdinājums par "lidmašīnas ieniršanas astes spraugā" posma sākumu, kas var beigties ar valsts šifrēšanas standarta sabrukumu, kā tas bija gadījumā ar sajaukšanas algoritmu SHA-1 un de facto MD5 jaukšanas algoritms.

GOST 28147-89 tika standartizēts 1989. gadā un pirmo reizi kļuva par oficiālu konfidenciālas informācijas aizsardzības standartu, taču šifra specifikācija palika slēgta. 1994. gadā standarts tika deklasificēts, publicēts un tulkots angļu valodā. Pēc analoģijas ar AES (un atšķirībā no DES) GOST ir atļauts bez ierobežojumiem aizsargāt klasificētu informāciju saskaņā ar Krievijas standartā noteikto veidu. Tas. GOST nav DES analogs, bet 3-DES konkurents ar trim neatkarīgām atslēgām vai AES-256. Acīmredzot GOST ir diezgan nopietns šifrs, kas atbilst militāriem kritērijiem, radīts, cerot uz visnopietnākajām lietojumprogrammām. Pamatojoties uz Krievijas banku izmantotajām lietojumprogrammām, ir identificēti vismaz divi GOST S-box komplekti. Šīm bankām ir jāveic slepena saziņa ar simtiem filiāļu un jāaizsargā miljardi dolāru no krāpnieciskām zādzībām.

GOST ir bloku šifrs ar vienkāršu Feistel struktūru, kura bloka izmērs ir 64 biti, 256 bitu atslēga un 32 kārtas. Katrā kārtā ir modulo 2 ^ 32 taustiņu papildinājums, astoņu 4 bitu S lodziņu komplekts un vienkārša 11 bitu cikliska nobīde. GOST iezīme ir iespēja slepeni uzglabāt S blokus, ko var attēlot kā otro atslēgu, kas palielina efektīvo atslēgas materiālu līdz 610 bitiem. Viens S-box komplekts tika publicēts 1994. gadā kā daļa no GOST-R 34.11-94 jaucējfunkcijas specifikācijas un, kā rakstīja Šneiers, to izmantoja Krievijas Federācijas Centrālā banka. Tas ir iekļauts arī RFC4357 standartā sadaļā "id-GostR3411-94-CryptoProParamSet". Šneiera grāmatas beigās (S-box secībā) bija kļūda avota kodā. Visprecīzāko krievu izcelsmes atsauces ieviešanu tagad var atrast OpenSSL bibliotēkā. Ja kaut kur tiek izmantotas slepenas S kastes, tad tās var iegūt no programmatūras ieviešanas un mikroshēmām, patiesībā tika publicēti attiecīgie darbi.

GOST ir nopietns konkurents

Papildus ļoti lielajam atslēgas izmēram GOST ir ievērojami zemākas izpildes izmaksas salīdzinājumā ar AES un citām līdzīgām šifrēšanas sistēmām. Faktiski tas maksā daudz mazāk nekā AES, kas prasa četras reizes vairāk aparatūras loģisko vārtu, lai nodrošinātu daudz zemāku drošības līmeni.

Nav pārsteidzoši, ka GOST ir kļuvis par interneta standartu, jo īpaši tas ir iekļauts daudzās šifrēšanas bibliotēkās, piemēram, OpenSSL un Crypto ++, un kļūst arvien populārāks ārpus savas izcelsmes valsts. 2010. gadā GOST tika deklarēts ISO standartizācijai kā pasaules šifrēšanas standarts. Ārkārtīgi neliels skaits algoritmu ir spējuši kļūt par starptautiskiem standartiem. ISO / IEC 18033-3: 2010 ir aprakstīti šādi algoritmi: četri 64 bitu šifri-TDEA, MISTY1, CAST-128, HIGHT-un trīs 128 bitu šifri-AES, Camellia, SEED. GOST tiek piedāvāts pievienot tam pašam ISO / IEC 18033-3 standartam.

Pirmo reizi rūpnieciskās standartizācijas vēsturē mēs saskaramies ar šādu konkurētspējīgu algoritmu attiecībā uz izmaksu un drošības līmeņa optimitāti. GOST veic 20 gadus kriptoanalīzes centienus, un vēl nesen tā militārā līmeņa drošība nav apšaubīta.

Kā autors nesen uzzināja no privātas sarakstes, lielākā daļa valstu iebilda pret GOST ISO balsojumā Singapūrā, taču šī balsojuma rezultāti joprojām tiks izskatīti ISO SC27 plenārsēdē, tāpēc GOST joprojām ir standartizācijas procesā. šī darba publicēšana.

Ekspertu viedokļi par GOST

Neviena pieejamā informācija un literatūra par GOST nedod pamatu uzskatīt, ka šifrs var būt nedrošs. Gluži pretēji, lielais atslēgas izmērs un lielais raundu skaits padara GOST no pirmā acu uzmetiena piemērotu lietošanai gadu desmitiem.

Ikviens, kurš zina Mūra likumu, saprot, ka teorētiski 256 bitu atslēgas paliks drošas vismaz 200 gadus. GOST ir plaši pētījuši vadošie eksperti kriptogrāfijas jomā, kas pazīstami bloku šifrēšanas analīzes jomā, piemēram, Šneiers, Birjukovs, Dankelmens, Vāgners, daudzi Austrālijas, Japānas un Krievijas zinātnieki, ISO kriptogrāfijas eksperti un visi pētnieki pauda, ​​ka viss izskatās tā, ka viņš var būt drošs. Lai gan atzinumā tika panākta plaša izpratne par to, ka GOST struktūra ir ārkārtīgi vāja, piemēram, salīdzinot ar DES, difūzija nav tik laba, tomēr tas vienmēr bija saistīts ar faktu, ka tas būtu jākompensē ar liels raundu skaits (32), kā arī papildu nelinearitāte un difūzija, ko nodrošina moduļa pievienošana.

Birjukovs un Vāgners rakstīja: "Lielais raundu skaits (32) un labi izpētītā Feistel konstrukcija apvienojumā ar secīgām Šenona permutācijām nodrošina stabilu pamatu GOST drošībai." Tajā pašā darbā mēs lasām: "pēc ievērojamiem laika un pūļu ieguldījumiem atklātā literatūrā nav panākts progress standarta kriptoanalīzē." Tādējādi nebija nekādu nozīmīgu uzbrukumu, kas ļautu atšifrēt vai atgūt atslēgas reālā scenārijā, kad GOST tiek izmantots šifrēšanā ar daudzām dažādām izlases atslēgām. Turpretī ir zināms daudz darbu par uzbrukumiem vājajām atslēgām GOST, uzbrukumiem ar saistītajām atslēgām, uzbrukumiem slepeno S-kastīšu atgūšanai. Kriptogrāfijā-2008 tika prezentēta jaucējfunkcijas uzlaušana, pamatojoties uz šo šifru. Visos uzbrukumos uzbrucējam ir ievērojami lielāks brīvības līmenis, nekā viņam parasti būtu atļauts. Tradicionālajos šifrēšanas lietojumos, izmantojot nejauši izvēlētas atslēgas, līdz šim nav atrasti nopietni kriptogrāfijas uzbrukumi GOST, kas 2010. gadā tika izteikts ar pēdējo frāzi: "neskatoties uz kriptoanalītiķu ievērojamajiem centieniem pēdējo 20 gadu laikā, GOST vēl nav izdevies krekinga "(Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, 219.-233. lpp., 2010).

Lineārā un diferenciālā analīze GOST

Šneiera pazīstamajā grāmatā mēs lasām: "Pret diferenciālo un lineāro kriptoanalīzi GOST, iespējams, ir izturīgāks par DES." Galveno GOST drošības novērtējumu 2000. gadā sniedza Gabidulins et al. Viņu rezultāti ir ļoti iespaidīgi: ja drošības līmenis ir 2 ^ 256, pietiek ar piecām kārtām, lai aizsargātu GOST no lineārās kriptoanalīzes. Turklāt, pat nomainot S kastes ar identiskām un vienīgo nelineāro šifrēšanas darbību - pievienošanas mod 2 ^ 32 - šifrs joprojām ir izturīgs pret lineāro kriptoanalīzi pēc 6 kārtām no 32. GOST diferenciālā kriptoanalīze izskatās salīdzinoši vienkāršāka un piesaista lielāku uzmanību. Lai iegūtu 2 ^ 128 drošības līmeni, pētnieki (Vitālijs V. Šorins, Vadims V. Jeļezņakovs un Ernsts M. Gabiduļins: Krievijas GOST lineārā un diferenciālā kriptoanalīze, 2001. gada 4. aprīļa Elsevier Preprint iesniegtais pirmsdrukas paraugs) uzskatīja, ka 7 kārtās ir pietiekama izturība. . Pēc viņu domām, lauzt GOST vairāk nekā piecās kārtās ir "ārkārtīgi grūti". Turklāt divi japāņu pētnieki ir pierādījuši, ka klasiskajam tiešajam diferenciālajam uzbrukumam ar vienu diferenciālo raksturlielumu ir ārkārtīgi maza varbūtība iziet cauri daudziem raundiem. Pamatojoties uz faktu, ka tiek pētīts pietiekami “labs” iteratīvs diferenciālais raksturlielums ierobežotam raundu skaitam (kuram pašam ir varbūtība iziet ne labāk kā 2–11,4 vienā kārtā), piemēroto taustiņu kopas vērtība ir mazāka par pusi . Pilna apļa GOST gadījumā šāds uzbrukums ar vienu raksturlielumu darbosies tikai ar nenozīmīgu 2–62 taustiņu daļu (un pat šajā mazajā daļā tam būs garām ne vairāk kā 2–60 ).

Sarežģītāki uzbrukumi ietver vairākus diferenciāļus, kas seko noteiktiem modeļiem, piemēram, izmantojot atsevišķas S-kastes ar nulles diferenciāli, bet citiem bitiem-nulles. Mēs runājam par diskriminējošiem uzbrukumiem, kuru pamatā ir sliktas GOST difūzijas īpašības. Labākais no šiem uzbrukumiem darbojas pret 17 GOST kārtām, ir atkarīgs no atslēgas, un tam ir ārkārtīgi vājš diskriminētājs no nejaušiem datiem pašā izejā, lai to varētu kaut kādā veidā izmantot, lai iegūtu informāciju par atslēgu.

Slīdēt un novirzīt uzbrukumus

Pēc Birjukova un Vāgnera teiktā, GOST struktūra, kas ietver apakšatslēgu apgriezto secību pēdējās kārtās, padara to izturīgu pret bīdāmiem uzbrukumiem (tā sauktajiem "slaidu uzbrukumiem"). Tomēr, tā kā šifrā ir liela līdzība ar sevi, tas ļauj atslēgt atslēgu inversijas uzbrukumus fiksētu punktu kombinācijām un "atstarošanas" īpašībām (tā sauktie "atstarojošie uzbrukumi") noteiktām vājām atslēgām. Šī uzbrukuma sarežģītība ir 2 ^ 192 un 2 ^ 32 saskaņoti vienkāršie teksti.

Jaunākie rezultāti

Jaunie uzbrukumi izmanto arī pārdomas un faktiski salauza GOST, kas tika prezentēts konferencē FSE 2011. Šos uzbrukumus arī šī darba autors atklāja neatkarīgi. Uzbrukumam ir nepieciešami 2 ^ 132 baiti atmiņas, kas patiesībā ir sliktāk nekā lēnāki uzbrukumi ar mazākām atmiņas prasībām.

Dažādi jauni pašlīdzības uzbrukumi darbojas pret visām GOST atslēgām un ļauj izjaukt pilna apļa GOST ar 256 bitu atslēgu, ne tikai vājām atslēgām, kā tas bija agrāk. Visi šie uzbrukumi prasa ievērojami mazāk atmiņas un ir ievērojami ātrāki.

Šos jaunos uzbrukumus var uzskatīt par piemēriem jaunai vispārējai paradigmai, kas paredzēta bloku šifru kriptoanalīzei un ko sauc par "algebriskās sarežģītības samazināšanu", un šie uzbrukumi tiek vispārināti, attiecinot tos uz daudziem īpašiem uzbrukumu gadījumiem ar zināmiem fiksētiem punktiem, slaidiem, involācijām un cikliem. Ir svarīgi, lai visu šo uzbrukumu ģimenē būtu tādi, kas ļauj veikt GOST kriptoanalīzi bez jebkādām pārdomām un bez simetriskiem punktiem, kas parādās aprēķinu gaitā. Viens piemērs ir vienkāršs GOST hakeru uzbrukums bez pārdomām šajā darbā.

Algebriskā kriptoanalīze un zemas datu sarežģītības uzbrukumi samazinātu kārtu šifriem

Algebriskos uzbrukumus bloku un plūsmu šifriem var attēlot kā problēmu, kas atrisina lielu Būla algebrisko vienādojumu sistēmu, kas atbilst konkrētas kriptogrāfijas shēmas ģeometrijai un struktūrai. Pati ideja meklējama Šenonā. Praksē tas tika prezentēts DES (pirmo reizi iepazīstināja ar šī darba autoru) kā formāla kodēšanas metode, un tas var uzlauzt 6 kārtas tikai vienā zināmā vienkāršā tekstā. Manipulācija ar vienādojumiem ir balstīta uz XL algoritmiem, Grēnera bāzēm, ElimLin metodi, SAT risinātājiem.

Praksē algebriskie uzbrukumi ir īstenoti pret ļoti mazu bloku šifru kārtu skaitu, taču tie jau ir izraisījuši straumes šifru plaisāšanu, kā arī gūti panākumi mikroiekārtu īpaši vieglu šifru laušanā. Atmiņas lieluma un aprēķinu izmaksu aprēķinu grūtību dēļ tie tiek apvienoti ar citiem uzbrukumiem.

Kā uzlauzt GOST?

Šajā publikācijā detalizētāk ir parādīts algebrisks uzbrukums pilna apļa GOST. Iepriekšējā darbā autors jau ir izklāstījis 20 algebriskus uzbrukumus GOST un sagaida lielu skaitu no tiem tuvākajā nākotnē. Šajā darbā ierosinātais uzbrukums nav labākais no tiem, taču tas paver vienkāršu (vismaz kriptogrāfu izpratnei) ceļu turpmākai attīstībai, lai izveidotu īpašu metodiku GOST uzlaušanai.

Praktiskais rezultāts joprojām ir pieticīgs: 2 ^ 64 zināms vienkāršais teksts un 2 ^ 64 atmiņa vienkāršā teksta / šifrētā teksta pāru glabāšanai ļauj uzlauzt GOST 2 ^ 8 ātrāk nekā vienkāršs brutāls spēks. Bet attiecībā uz kriptoanalīzi tas padara apgalvojumu, ka "GOST ir uzlauzts", ir pilnīgi taisnīgs.

secinājumus

GOST ir paredzēts, lai nodrošinātu militāru drošības līmeni 200 gadus uz priekšu. Lielākā daļa vadošo ekspertu, kas pētījuši GOST, ir piekrituši, ka "neskatoties uz ievērojamiem kriptoanalīzes centieniem 20 gadu laikā, GOST vēl nav uzlauzts". 2010. gadā GOST tika paaugstināts līdz ISO 18033 kā globālais šifrēšanas standarts.

Ideju par algebrisko kriptoanalīzi pamatā ir vairāk nekā 60 gadu. Bet tikai pēdējo 10 gadu laikā ir izstrādāti efektīvi programmatūras rīki daudzu NP pilnīgu problēmu (daļējai) risināšanai. Ir uzlauzti vairāki straumes šifri. Ar šo metodi ir salauzts tikai viens bloka šifrs - pats vājais KeeLoq. Šajā darbā autors salauž svarīgu, faktiski lietotu GOST šifru. Viņš atzīmē, ka šī ir pirmā reize vēsturē, kad algebriskā kriptoanalīze ir salauzusi standartizētu stāvokļa šifru.

Vienkāršs "MITM ar pārdomām" uzbrukums GOST jau tika prezentēts konferencē FSE 2011. Šajā rakstā apskatītajā darbā vēl viens uzbrukums tiek prezentēts tikai, lai ilustrētu to, cik daudz uzbrukumu GOST jau ir parādījies, daudzi no tiem ir ātrāki, un algebrisks uzbrukums prasa daudz mazāk atmiņas un paver gandrīz neizsmeļamu iespēju telpu pretiniekam dažādos veidos uzbrukt šifram. Arī šajā rakstā ir parādīts, ka uzlaušanai nav nepieciešams izmantot atstarošanas īpašību.

Autors apgalvo, ka ir acīmredzams, ka GOST ir nopietni trūkumi un tagad nenodrošina ISO prasīto izturības līmeni. Daudzi uzbrukumi GOST ir iesniegti kā daļa no algebriskās sarežģītības samazināšanas paradigmas apstiprinājuma.

Visbeidzot, pētnieks īpaši atzīmē dažus faktus, kas lasītājam vēl nav pieejami, bet pētniekam zināmi, un kas ir svarīgi ISO standartizācijas procesa gaitā. Šis uzbrukums nav tikai "sertifikācijas" uzbrukums GOST, kas ir ātrāks par brutāla spēka brutāla spēka uzbrukumu. Patiesībā GOST standartizēšana tagad būtu ārkārtīgi bīstama un bezatbildīga. Tas ir tāpēc, ka daži uzbrukumi ir praktiski. Praksē dažas GOST atslēgas var pat atšifrēt neatkarīgi no tā, vai tās ir vājas atslēgas vai atslēgas no privātajām GOST lietojumprogrammām. Iepriekšējā darbā autors detalizēti aplūko praktisku uzbrukumu iespējamības gadījumus. Zīmīgi, ka "šī ir pirmā reize vēsturē, kad matemātisks uzbrukums ir apdraudējis nopietnu standartizētu bloku šifru, kas paredzēts militāra līmeņa noslēpumu aizsardzībai un paredzēts valsts noslēpumu aizsardzībai valdībām, lielām bankām un citām organizācijām."