EPOC (krypteringsskema)
EPOC ( Efficient Probabilistic Public Key Encryption ; effektiv probabilistisk offentlig nøglekryptering) er en probabilistisk
offentlig nøglekryptering .
EPOC blev udviklet i november 1998 af T. Okamoto, S. Uchiyama og E. Fujisaki fra NTT Laboratories i Japan . Den er baseret på en tilfældig orakelmodel , hvor en offentlig nøglekrypteringsfunktion konverteres til et sikkert krypteringsskema ved hjælp af en (virkelig) tilfældig hashfunktion; det resulterende skema er designet til at være semantisk sikkert mod angreb baseret på den valgte chiffertekst [1] .
Typer af skemaer
EPOC-krypteringsfunktionen er en OU-funktion (Okamoto-Uchiyama), der er lige så svær at invertere, som det er at faktorisere en offentlig heltalsnøgle. Der er tre versioner af EPOC [2] :
- EPOC-1, der bruger en envejsfunktion (engelsk falddørsfunktion) og en tilfældig funktion (hashfunktion) [3] .;
- EPOC-2 ved hjælp af en envejsfunktion , to tilfældige funktioner (hash-funktioner) og symmetrisk nøglekryptering (såsom engangspude- og blokcifre) [4] ;
- EPOC-3 bruger en envejs OU-funktion (Okamoto-Uchiyama) og to tilfældige funktioner (hash-funktioner) samt ethvert symmetrisk krypteringsskema, såsom engangs-pads (engelsk engangs-pad) eller blokchiffer .
EPOC har følgende egenskaber:
- EPOC-1 er semantisk sikker , modstandsdygtig over for udvalgte chiffertekstangreb ( IND-CCA2 eller NM-CCA2 ) i den tilfældige orakelmodel [6] under p-undergruppeantagelsen , som er beregningsmæssigt sammenlignelig med den kvadratiske rest og højere grads restantagelser.
- EPOC-2 med engangspude er semantisk sikker , modstandsdygtig over for udvalgte chiffertekstangreb ( IND-CCA2 eller NM-CCA2 ) i en tilfældig orakelmodel under faktoriseringsantagelse.
- EPOC-2 med symmetrisk kryptering er semantisk sikker , modstandsdygtig over for angreb baseret på valgt chiffertekst ( IND-CCA2 eller NM-CCA2 ) i den tilfældige orakelmodel under faktoriseringsantagelsen, hvis den underliggende symmetriske kryptering er sikker mod passive angreb (se angreb hvor kryptanalytikeren har mulighed for kun at se de transmitterede chiffertekster og generere din egen ved hjælp af den offentlige nøgle .).
Baggrund
Diffie og Hellman foreslog konceptet med et offentligt nøglekryptosystem (eller envejsfunktion ) i 1976. Selvom mange kryptografer og matematikere har lavet omfattende forskning for at implementere konceptet med offentlige nøglekryptosystemer i over 20 år, er der fundet meget få specifikke metoder, der er sikre [7] .
En typisk klasse af metoder er RSA-Rabin , som er en kombination af en polynomiel algoritme til at finde roden af et polynomium i ringen af rester modulo et sammensat tal (i et endeligt felt ) og et uløseligt faktoriseringsproblem (i form af beregningsmæssigt ). kompleksitet ). En anden typisk klasse af metoder er Diffie-Hellman, ElGamal metoden , som er en kombination af logaritmens kommutative egenskab i en finit Abelsk gruppe og det uløselige diskrete logaritmeproblem [8] .
Blandt RSA-Rabin- og Diffie-Hellman-ElGamal- metoderne til implementering af en envejsfunktion har ingen anden funktion end Rabin-funktionen og dens varianter, såsom dens elliptiske kurve og Williams-versioner, vist sig at være lige så robust som den primitive. problemer [9] (f.eks. faktorisering og diskrete logaritmeproblemer ).
Okamoto og Uchiyama har foreslået en envejsfunktion kaldet OU (Okamoto-Uchiyama), som er praktisk, beviseligt sikker og har nogle andre interessante egenskaber [10] .
- Sandsynlighedsfunktion: Dette er en envejs, sandsynlighedsfunktion . Lade være en almindelig tekst chiffertekstmed tilfældig.
- Ensidighed af en funktion: Invertering af en funktion har vist sig at være lige så svært som faktorisering.
- Semantisk sikkerhed: En funktion er semantisk sikker , hvis følgende antagelse er sand ( p-undergruppeantagelsen ):ogberegningsmæssigt ude af skel, hvoroger ensartet og uafhængigt valgt fra. Denne antagelse om ikke-skelnelighed med chiffertekst for matchede klartekst-angreb er beregningsmæssigt sammenlignelig med at finde en kvadratisk rest og en højere grads rest.
- Effektivitet: I et offentligt nøglekryptosystemmiljø , hvor det offentlige nøglekryptosystem kun bruges til at udbrede den hemmelige nøgle (f.eks. 112 og 128 bit lang) af det hemmelige nøglekryptosystem (f.eks. Triple DES og IDEA ), krypteringen og dekrypteringen OU-funktionens hastighed er sammenlignelig (flere gange langsommere) med hastigheden af elliptiske kurvekryptosystemer .
- Homomorf krypteringsegenskab: Funktionen har den homomorfe krypteringsegenskab: (Denne egenskab bruges til e-afstemning og andre kryptografiske protokoller ).
- Ciphertext udeskelnelighed : Selv en person, der ikke kender den hemmelige nøgle, kan ændre chifferteksten,, til en anden chiffertekst,, mens den beholder klarteksten m (dvs.), og forbindelsen mellemogkan skjules (dvs.ogikke skelnes). Denne egenskab er nyttig til privatlivsprotokoller.)
Bevis for sikkerheden af et krypteringsskema
En af de vigtigste egenskaber ved offentlig nøglekryptering er bevisbar sikkerhed . Det stærkeste sikkerhedskoncept i kryptering med offentlig nøgle er semantisk beskyttelse mod angreb baseret på en valgt chiffertekst .
Semantisk angrebsbeskyttelse baseret på adaptivt valgt chiffertekst ( IND -CCA2 ) har vist sig at være ækvivalent (eller tilstrækkelig) til det stærkeste sikkerhedskoncept ( NM-CCA2 ) [12] [13] .
Fujisaki og Okamoto har implementeret to fælles og effektive foranstaltninger til at transformere en probabilistisk envejsfunktion til et sikkert IND-CCA2-kredsløb i en tilfældig orakelmodel [6] . En af dem er konverteringen af en semantisk sikker ( IND-CPA ) envejsfunktion til et sikkert IND-CCA2-skema . Andre, fra envejsfunktion (OW-CPA) og symmetrisk nøglekryptering (inklusive engangspude) til sikker IND-CCA2-ordning . Sidstnævnte transformation kan garantere den fuldstændige sikkerhed af et offentligt nøglekrypteringssystem i kombination med et symmetrisk nøglekrypteringsskema [14] .
EPOC-krypteringsskema
Oversigt
EPOC offentlige nøglekrypteringsskemaet , som er specificeret af tripletten , hvor er nøglegenereringsoperationen, er krypteringsoperationen og er dekrypteringsoperationen.
EPOC-skemaer: EPOC-1 og EPOC-2.
EPOC-1 er til nøgledistribution, mens EPOC-2 er til nøgledistribution og krypteret dataoverførsel og længere nøgledistribution med en begrænset offentlig nøglestørrelse.
Nøgletyper
Der er to typer nøgler: OU offentlig nøgle og OU privat nøgle, som begge bruges i EPOC-1, EPOC-2 kryptografiske krypteringssystemer [15] .
OU offentlig nøgle [15]
Den offentlige nøgle til en OU er et sæt, hvis komponenter har følgende værdier:
- er et ikke-negativt heltal
- er et ikke-negativt heltal
- er et ikke-negativt heltal
- — hemmelig parameter, ikke-negativt heltal
I praksis, i den offentlige nøgle-OU, har modulet formen , hvor og er to forskellige ulige primtal, og bitlængden af og er lig med . -element i sådan at rækkefølgen i er , hvor . -element i .
OU privat nøgle [15]
Den private nøgle til en OU er et sæt, hvis komponenter har følgende værdier:
- — første faktor, ikke-negativt heltal
- — anden faktor, ikke-negativt heltal
- — hemmelig parameter, ikke-negativt heltal
- — værdi , hvor , ikke-negativt heltal
Nøgleoprettelse: G
Input og output er som følger:
[Input]: Den hemmelige parameter ( ) er et positivt heltal.
[Output]: Par af offentlig nøgle og privat nøgle .
Login-handlingen ser sådan ud:
- Lad os vælge to primtal , ( ) og beregne . Her og sådan at og er primtal, og og sådan at .
- Vi vælger tilfældigt, så rækkefølgen er lig med (Bemærk at gcd( , ) og gcd( , ) ).
- Vi vælger tilfældigt og uafhængigt af . Lad os beregne .
- Installer . Installer og sådan .
Bemærk: er en ekstra parameter, der øger effektiviteten af dekryptering og kan beregnes ud fra og . når ( -konstant ). kan rettes af systemet og deles af mange brugere.
Kryptering: E
Input og output er som følger:
[Input]: Almindelig tekst sammen med offentlig nøgle .
[Output]: Chiffertekst C.
Indtastningsoperationen ser sådan ud
:
- Lad os vælge og beregne . Her står for sammenkædning og .
- Beregn :
Dekryptering: D
Input og output er som følger:
[Input]: Chiffertekst sammen med offentlig nøgle og privat nøgle .
[Output]: Almindelig tekst eller nul-streng.
Operationen med input og ser sådan ud:
- Lad os beregne , og , hvor .
- Lad os kontrollere, om følgende ligning er sand: .
- Hvis udtrykket er sandt, så output som dekrypteret klartekst, hvor angiver de mest signifikante bits i . Ellers udsender vi en nul-streng.
Nøgleoprettelse: G
Input og output er som følger:
[Input]: Hemmelig parameter ( ).
[Output]: Par af offentlig nøgle og privat nøgle .
Login-handlingen ser sådan ud:
- Lad os vælge to primtal , ( ) og beregne . Her og sådan at og er primtal, og og sådan at .
- Vi vælger tilfældigt, så rækkefølgen er lig med .
- Vi vælger tilfældigt og uafhængigt af . Lad os beregne .
- Installer . Installer og sådan .
Bemærk: er en ekstra parameter, der øger effektiviteten af dekryptering og kan beregnes ud fra og . når ( -konstant ). og kan rettes af systemet og deles af mange brugere.
Kryptering: E
Lad være et par krypterings- og dekrypteringsalgoritmer med en symmetrisk nøgle , hvor længden er . Krypteringsalgoritmen tager en nøgle og almindelig tekst og returnerer en chiffertekst . Dekrypteringsalgoritmen tager nøglen og chifferteksten og returnerer klarteksten .
Input og output er som følger:
[Input]: Almindelig tekst sammen med offentlig nøgle og .
[Output]: Chiffertekst .
Operationen med input og ser sådan ud:
- Lad os vælge og beregne .
- ;
Bemærk: En typisk implementering er engangspuden. Det vil sige , og , hvor angiver den bitvise XOR- operation .
Dekryptering: D
Input og output er som følger:
[Input]: Chifferteksten sammen med den offentlige nøgle , hemmelig nøgle og .
[Output]: Almindelig tekst eller nul-streng.
Betjeningen med indgangene , og er som følger:
- Lad os beregne , og , hvor .
- Beregn
- Lad os kontrollere, om følgende ligning er sand: .
- Hvis udtrykket er sandt, så output som den dekrypterede klartekst. Ellers udsender vi en nul-streng.
Noter
- ↑ 1 2 T. Okamoto; S. Uchiyama, 1998 , s. en.
- ↑ Katja Schmidt-Samoa, 2006 .
- ↑ T. Okamoto; S. Uchiyama, 1998 , s. 2-3.
- ↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , s. 3-4.
- ↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , s. 8-11.
- ↑ 1 2 E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung, 2000 .
- ↑ W. DIFFIE OG MIG HELLMAN, 1976 .
- ↑ T. Elgamal, 1985 .
- ↑ T. Okamoto; S. Uchiyama, 1998 , s. 5.
- ↑ T. Okamoto; S. Uchiyama, 1998 , s. fire.
- ↑ T. Okamoto; S. Uchiyama, 1998 , s. 3-4.
- ↑ Maxwell Krohn, 1999 , s. 53.
- ↑ Bellare, M., Desai, A., Pointcheval, D., og Rogaway, P., 1998 .
- ↑ 1 2 3 T. Okamoto; S. Uchiyama, 1998 , s. 5.
- ↑ 1 2 3 NTT Corporation, 2001 , s. 7.
- ↑ NTT Corporation, 2001 , s. 9-10.
Litteratur
- Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. Sikker integration af asymmetriske og symmetriske krypteringssystemer . – 1999.
- W. DIFFIE OG MIG HELLMAN. Nye retninger i kryptografi . - 1976.
- Maxwell Krohn. Om definitionerne af kryptografisk sikkerhed : Angreb med valgt krypteringstekst genbesøgt . – 1999.
- T. Elgamal. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer . - 1985.
- NTT Information Sharing Platform Laboratories, NTT Corporation. EPOC-2- specifikation . - 2001. - S. 7-10 .
- Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. EPOC: Effektiv probabilistisk offentlig nøglekryptering . - 1998. - S. 1-12 .
- Evaluator: Prof. Jean-Jacques Quisquater, Math RiZK, rådgivning; Videnskabelig støtte: Dr. François Koeune, K2Crypt. Sikkerhedsvurdering af krypteringsskemaet . - 2002.
- E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung. Designvalideringer for diskrete logaritmebaserede signaturskemaer . - 2000. - S. 276-292 .
- Bellare, M., Desai, A., Pointcheval, D., og Rogaway, P. Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. af Crypto'98, LNCS 1462, Springer-Verlag, (engelsk) . - 1998. - S. 26-45 .
- Katja Schmidt Samoa. En ny fældedør-permutation af Rabin-typen svarende til faktorisering . - 2006. - S. 86–88 .