Pseudorandom algoritme

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 16. marts 2021; verifikation kræver 1 redigering .

En pseudo-tilfældig krypteringsalgoritme  er en sådan krypteringsalgoritme , at hver blok (tegn) i kildeteksten er krypteret med sin egen nøgle , og hver næste nøgle er det næste medlem af den pseudo-tilfældige sekvens , og hovednøglen (grundlæggende) er det første element i denne sekvens.

Konstruktionsfunktioner

Valg af intern algoritme

Valget af den interne algoritme afhænger stærkt af kravene til den pseudo-tilfældige krypteringsalgoritme. Så der er en række opgaver, hvor selv den interne algoritme er valgt til at være den mest kryptografisk sikre , dog er pseudo-tilfældige algoritmer meget mere udbredte, hvor en ret simpel algoritme bruges som en intern krypteringsalgoritme, derfor er det ikke en kryptografisk sikker algoritme i sig selv. Valget af en simpel algoritme er direkte relateret til kravene til hastigheden af ​​kryptering og dekryptering.

Valget af en pseudo-tilfældig talgenerator afhænger også af kravene til en pseudo-tilfældig krypteringsalgoritme. Hvis den maksimale meddelelseslængde er ret stor (fra 16 MB), og bloklængdekravene er høje (f.eks. ikke mere end 1 byte pr. blok eller endnu højere), kan selv de bedste kongruente generatorer ikke bruges som pseudo-tilfældig talgenerator vi har brug for. Men hvis omfanget af vores pseudo-tilfældige algoritme er kryptering af relativt korte meddelelser (mindre end 1 Kb i længden), og deres relevans i tid ikke er signifikant, så kan en ret simpel generator vælges som en pseudo-tilfældig talgenerator , hvilket også vil øge hastigheden af ​​kryptering og dekryptering.

Eksempler

  1. Overvej den enkleste brug af en sådan algoritme. Som en intern algoritme tager vi Cæsar-chifferet , vi tager blokstørrelsen lig med et tegn, og som en pseudo-tilfældig talgenerator tager vi k i +1 = ( a  k i  +  b ) mod p , dvs. hver næste nøgle i vores algoritme beregnes af en sådan formel fra den forrige , vi sætter nøglelængden lig med henholdsvis ~256 bit, vi tager p 2 256 , vi sætter konstanterne a og b , henholdsvis (3 + 2 255 ) og 0. Som du ved, er sløjfeperioden for en sådan pseudo-tilfældig talgenerator ~ p / 4, det vil sige 2 254 , hvilket er ganske nok til at kryptere en fil af ganske stor længde, hvilket eliminerer muligheden for at gentage cyklussen mange gange, tilstrækkeligt til frekvensanalyse . Denne algoritme har dog åbenlyse ulemper. Nemlig at kende en del af chifferteksten (f.eks. en kryptoanalytiker ved, at du starter hver af dine beskeder med ordet "Hej!"), kan du nemt gendanne nøglen ved trin 1-7, og dermed alle nøglerne. Dette bringer os til en lille ændring af denne algoritme.
  2. Som en intern algoritme tager vi den samme Cæsar-chiffer , vi tager blokstørrelsen lig med et tegn, som en pseudo-tilfældig talgenerator tager vi m i +1 = ( a  m i  +  b ) mod p , k i +1 = SumC(( a  m i  +  b ) mod p ), vi sætter også nøglelængden lig med henholdsvis ~256 bit, vi tager p 2 256 , vi sætter konstanterne a og b , henholdsvis (3 + 2 255 ) og 0, og SumC-funktionen er en funktion, der beregner summen af ​​cifre i et tal, mens grundtallet nøglen ikke længere er k 1 , men m 1 . Bemærk, at i dette tilfælde er beregningen af ​​m i , selv ved at kende k i , meget vanskelig.
  3. En af disse algoritmer blev udviklet og implementeret af Alexander Berezinsky mellem 2005 og 2009. I den blev Cæsar-algoritmen på Charov-cirklen taget som en intern algoritme , der adskiller sig fra den sædvanlige Cæsar-chiffer ved, at ASCII-tabellen bruges i stedet for alfabetet på 26 tegn, mens H i  + 1  = H i 7 mod 10 100 bruges som en pseudo-tilfældig talgenerator , k i +1 = SumC( H ( i ) 7 mod 10 100 ), hvor H 1  er grundnøglen , hvis længde er ~332 bit, og SumC er en funktion der beregner summen af ​​cifrene i et tal. Der leveres også fra 2 til 10 runder med kryptering (antallet af runder er lig med det første signifikante ciffer H 1  + 1), det vil sige ved slutningen af ​​kryptering af en runde, indlæses den krypterede fil og krypteres igen, og H 1 i hver næste runde er lig med den sidste H n i den foregående.
  4. Men som du ved, er der udover Cæsar-chifferet mange meget mere kryptografisk stærke krypteringsalgoritmer og meget bedre pseudo-tilfældige talgeneratorer end dem, der er præsenteret ovenfor, det vil sige, du kan tage AES som en krypteringsalgoritme og kongruente generatorer som en pseudo-tilfældig talgenerator i henhold til algoritmen foreslået af National US Bureau of Standards , som har en periodelængde på 2 24 . Det er dog ikke svært at forstå, at en sådan algoritme vil køre længere end alle ovenstående.

Noter

Alle eksemplerne ovenfor er symmetriske krypteringsalgoritmer . Der er ingen information om asymmetriske pseudo-tilfældige krypteringsalgoritmer fra 2009 . Der er både stream- cifre og blok- cifre implementeret i konceptet med en pseudo-tilfældig chiffer -algoritme .

Litteratur

1. "Introduktion til kryptografi", red. V. V. Yashchenko.

2. Varnovsky N. P. "Om stabiliteten af ​​elektroniske signaturordninger med hardwareunderstøttelse." Teknisk rapport. MSU Laboratory for Mathematical Problems of Cryptography, 1997.

3. Gary M., Johnson D. "Computere og vanskelige problemer." M.: Mir, 1982.

4. Impagliazzo R., Levin L., Luby M. Pseudo-tilfældig generering fra envejsfunktioner // Proc. 21. år. ACM Symp. om databehandlingsteori. 1989. S. 12-24.

5. Anokhin M. I., Varnovsky N. P., Sidelnikov V. M., Yashchenko V. V. "Kryptografi i bankvirksomhed". M.: MEPhI, 1997.

6. Blum M., Micali S. Hvordan man genererer krytografisk stærke sekvenser af pseudo-tilfældige bits // SIAM J. Comput. V. 13, nr. 4, 1984. P. 850-864.

7. Goldwasser S., Micali S., Rackoff C. Videnkompleksiteten af ​​interaktive bevissystemer // SIAM J. Comput. V. 18, nr. 1, 1989. S. 186-208.

8. Goldreich O., Micali S., Wigderson A. Beviser, der ikke giver andet end deres gyldighed eller alle sprog i NP har nul-viden bevissystemer // J. ACM. V. 38, nr. 3, 1991. P. 691-729.

9. Hastad J. Pseudo-tilfældige generatorer under ensartede antagelser // Proc. 22. år. ACM Symp. om databehandlingsteori. 1990. s. 395-404.

10. Impagliazzo R., Luby M. Envejsfunktioner er afgørende for kompleksitetsbaseret kryptografi // Proc. 30. år. Symp. på Fundet. af computer. sci. 1989. S. 230-235.

Eksterne links

1. De enkleste generationsalgoritmer

2. Analyse af pseudo-tilfældige sekvenser