EPOC (krypteringsschema)

EPOC ( Efficient Probabilistic Public Key Encryption ; effektiv probabilistisk offentlig nyckelkryptering) är ett probabilistiskt krypteringsschema för offentlig nyckel .

EPOC utvecklades i november 1998 av T. Okamoto, S. Uchiyama och E. Fujisaki från NTT Laboratories i Japan . Den är baserad på en slumpmässig orakelmodell , där en krypteringsfunktion för publik nyckel konverteras till ett säkert krypteringsschema med hjälp av en (verkligen) slumpmässig hashfunktion; det resulterande schemat är utformat för att vara semantiskt säkert mot attacker baserat på den valda chiffertexten [1] .

Typer av scheman

EPOC-krypteringsfunktionen är en OU-funktion (Okamoto-Uchiyama) som är lika svår att invertera som att faktorisera en offentlig heltalsnyckel. Det finns tre versioner av EPOC [2] :

EPOC-1, med en enkelriktad funktion (engelsk fallluckafunktion) och en slumpmässig funktion (hashfunktion) [3] .;
EPOC-2 som använder en envägsfunktion , två slumpmässiga funktioner (hashfunktioner) och symmetrisk nyckelkryptering (som engångsblock- och blockchiffer) [4] ;
EPOC-3 använder en enkelriktad OU-funktion (Okamoto-Uchiyama) och två slumpmässiga funktioner (hash-funktioner), såväl som alla symmetriska krypteringsscheman som engångsblock (engelsk engångsknapp) eller blockchiffer .

Egenskaper [1] [5]

EPOC har följande egenskaper:

EPOC-1 är semantiskt säker , resistent mot utvalda chiffertextattacker ( IND-CCA2 eller NM-CCA2 ) i den slumpmässiga orakelmodellen [6] under p-undergruppsantagandet , vilket är beräkningsmässigt jämförbart med antaganden om kvadratisk rest och högre grad av rester.
EPOC-2 med engångsplatta är semantiskt säker , resistent mot valda chiffertextattacker ( IND-CCA2 eller NM-CCA2 ) i en slumpmässig orakelmodell under faktoriseringsantagande.
EPOC-2 med symmetrisk kryptering är semantiskt säker , resistent mot attacker baserat på vald chiffertext ( IND-CCA2 eller NM-CCA2 ) i den slumpmässiga orakelmodellen under faktoriseringsantagandet, om den underliggande symmetriska krypteringen är säker mot passiva attacker (se attacker där kryptanalytikern har förmågan att bara se de överförda chiffertexterna och skapa din egen med den publika nyckeln .).

Bakgrund

Diffie och Hellman föreslog konceptet med ett kryptosystem med offentlig nyckel (eller envägsfunktion ) 1976. Även om många kryptografer och matematiker har gjort omfattande forskning för att implementera konceptet med publika nyckelkryptosystem i över 20 år, har väldigt få specifika metoder hittats som är säkra [7] .

En typisk klass av metoder är RSA-Rabin , som är en kombination av en polynomalgoritm för att hitta roten till ett polynom i ringen av rester modulo ett sammansatt tal (i ett ändligt fält ) och ett olösligt faktoriseringsproblem (i termer av beräkningsmässigt komplexitet ). En annan typisk klass av metoder är Diffie-Hellman, ElGamal-metoden , som är en kombination av den kommutativa egenskapen hos logaritmen i en finit Abelisk grupp och det olösliga diskreta logaritmproblemet [8] .

Bland RSA-Rabin- och Diffie-Hellman-ElGamal- metoderna för att implementera en envägsfunktion har ingen annan funktion än Rabin-funktionen och dess varianter, såsom dess elliptiska kurva och Williams-versioner, visat sig vara lika robust som den primitiva problem [9] (t.ex. faktorisering och diskreta logaritmproblem ).

Okamoto och Uchiyama har föreslagit en enkelriktad funktion som kallas OU (Okamoto-Uchiyama) som är praktisk, bevisligen säker och har några andra intressanta egenskaper [10] .

OU-funktionsegenskaper [ 11]

Sannolikhetsfunktion: Detta är en enkelriktad, sannolikhetsfunktion . Låta vara en klartext chiffertextmed slumpmässig. $E(m,r)$ $m$ $r$
En funktions ensidighet: Att invertera en funktion har visat sig vara lika svårt som faktorisering. $n:=p^{2}q$
Semantisk säkerhet: En funktion är semantiskt säker om följande antagande är sant ( p-undergruppsantagandet ):ochberäkningsmässigt omöjliga att särskilja, därochär enhetligt och oberoende valda från. Detta antagandeom omöjlighet med chiffertext för attacker med matchad klartext är beräkningsmässigt jämförbart med att hitta en kvadratisk rest och en högre gradsrest. $E(0,r)=h^{r}{\text{ mod }}n$ $E(1,r')=gh^{r'}{\text{ mod }}n$ $r$ $r'$ $\mathbf {Z} /n\mathbf {Z}$
Effektivitet: I en kryptosystemmiljö med publik nyckel där det offentliga nyckelkryptosystemet endast används för att sprida den hemliga nyckeln (till exempel 112 och 128 bitar långa) för det hemliga nyckelkryptosystemet (till exempel Triple DES och IDEA ), krypteringen och dekrypteringen hastigheten för OU-funktionen är jämförbar (flera gånger långsammare) med hastigheten för elliptiska kurvor kryptosystem .
Homomorphic encryption-egenskap: Funktionen har egenskapen homomorphic encryption: (Denna egenskap används för e-röstning och andra kryptografiska protokoll ). $E(m_{0},r_{0})E(m_{1},r_{1}){\text{ mod }}n=E(m_{0}+m_{1},r_{ 3}),{\text{ if }}m_{0}+m_{1}<p$
Ciphertext omöjlig att särskilja : Även någon som inte känner till den hemliga nyckeln kan ändra chiffertexten,, till en annan chiffertext,, samtidigt som den behåller klartexten m (dvs.), och kopplingen mellanochkan döljas (d.v.s.ochsärskilja). Den här egenskapen är användbar för sekretessprotokoll.) $C=E(m,r)$ $C'=Ch^{r'}{\text{ mod }}n$ $C'=E(m,r'')$ $C$ $C'$ $(C,C')$ $(C,E(m',t)$

Bevis på säkerheten för ett krypteringsschema

En av de viktigaste egenskaperna hos kryptering av offentlig nyckel är bevisbar säkerhet . Det starkaste säkerhetskonceptet vid kryptering med offentliga nyckel är semantiskt skydd mot attacker baserat på en vald chiffertext .

Semantiskt attackskydd baserat på adaptivt vald chiffertext ( IND -CCA2 ) har visat sig vara likvärdigt (eller tillräckligt) med det starkaste säkerhetskonceptet ( NM-CCA2 ) [12] [13] .

Fujisaki och Okamoto har implementerat två vanliga och effektiva åtgärder för att omvandla en probabilistisk envägsfunktion till en säker IND-CCA2-krets i en slumpmässig orakelmodell [ 6] . En av dem är konverteringen av en semantiskt säker ( IND-CPA ) envägsfunktion till ett säkert IND-CCA2-schema . Andra, från envägsfunktion (OW-CPA) och symmetrisk nyckelkryptering (inklusive engångsplatta) till säkert IND-CCA2-schema . Den senare omvandlingen kan garantera den fullständiga säkerheten för ett krypteringssystem för offentliga nyckel i kombination med ett symmetriskt nyckelkrypteringsschema [14] .

EPOC-krypteringsschema

Översikt

EPOC-krypteringsschemat för publik nyckel , som specificeras av tripletten , där är nyckelgenereringsoperationen, är krypteringsoperationen och är dekrypteringsoperationen. $({\mathcal {G}},{\mathcal {E}},{\mathcal {D}}))$ ${\mathcal {G}}$ ${\mathcal {E}}$ $\mathcal{D}$

EPOC-scheman: EPOC-1 och EPOC-2.

EPOC-1 är för nyckeldistribution, medan EPOC-2 är för nyckeldistribution och krypterad dataöverföring, och längre nyckeldistribution med en begränsad publik nyckelstorlek.

Nyckeltyper

Det finns två typer av nycklar: OU offentlig nyckel och OU privat nyckel, som båda används i EPOC-1, EPOC-2 kryptografiska krypteringsscheman [15] .

OU offentlig nyckel [15]

Den publika nyckeln för en organisationsenhet är en uppsättning vars komponenter har följande värden: $(n,g,h,pLen)$

$n$ är ett icke-negativt heltal
$g$ är ett icke-negativt heltal
$h$ är ett icke-negativt heltal
$pLen$ — hemlig parameter, icke-negativt heltal

I praktiken, i den offentliga nyckel-OU, har modulen formen , där och är två olika udda primtal, och bitlängden på och är lika med . -element i så att ordningen i är , där . -element i . $n$ $n:=p^{2}q$ $sid$ $q$ $sid$ $q$ $pLen$ $g$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}$ $(\mathbf {Z} /p^{2}\mathbf {Z} )^{*}$ $sid$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $h$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$

OU privat nyckel [15]

Den privata nyckeln för en OU är en uppsättning vars komponenter har följande värden: $(p,g,pLen,w)$

$sid$ — första faktorn, icke-negativt heltal
$h$ — andra faktorn, icke-negativt heltal
$pLen$ — hemlig parameter, icke-negativt heltal
$w$ — värde , där , icke-negativt heltal $L(g_{p})$ $L(x)={\frac {x-1}{p))$

EPOC-1 [14]

Nyckelskapande: G

Ingång och utgång är som följer: ${\mathcal {G}}$

[Input]: Den hemliga parametern ( ) är ett positivt heltal. $k$ $=plen$

[Utdata]: Par offentlig nyckel och privat nyckel . $(n,g,h,H,pLen,mLen,hLen,rLen)$ $(p,g_{p})$

Inloggningsoperationen ser ut så här: ${\mathcal {G}}$ $k$

Låt oss välja två primtal , ( ) och beräkna . Här och så att och är primtal, och och så att . $sid$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Vi väljer slumpmässigt så att ordningen är lika med (Observera att gcd( , ) och gcd( , ) ). $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $sid$ $sid$ $q-1$ ${\displaystyle=1}$ $q$ $p-1$ ${\displaystyle=1}$

Vi väljer från slumpmässigt och oberoende av . Låt oss räkna ut . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g$ $h:=h_{n}^{0}{\text{ mod }}n$

Installera . Installera och sådant . $pLen:=k$ $mLen$ $rLen$ $mLen+rLen\leq pLen-1$

Låt oss välja en hashfunktion . $H:\{0,1\}^{*}\högerpil \{0,1\}^{hLen}$

Obs: är en extra parameter som ökar effektiviteten för dekrypteringen och kan beräknas från och . när ( -konstant ). kan fixas av systemet och delas av många användare. $g_{p}$ $sid$ $g$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$

Kryptering: E

Ingång och utgång är som följer: ${\mathcal {E}}$

[Inmatning]: Klartext tillsammans med publik nyckel . ${\displaystyle M\in \{0,1\}^{mLen))$ $(n,g,h,H,pLen,mLen,hLen,rLen)$

[Utdata]: Chiffertext C.

Inmatningsoperationen ser ut så här: ${\mathcal {E}}$ $M$ $(n,g,h,H,mLen,rLen)$

Låt oss välja och beräkna . Här står för sammanlänkning och . ${\displaystyle R\in \{0,1\}^{rLen))$ $r:=H(M\parallel R)$ $M\parallel R$ $M$ $R$

Beräkna : $C$

$C:=g^{(M\parallel R)}h^{r}{\text{ mod }}n.$

Dekryptering: D

Ingång och utgång är som följer: $\mathcal{D}$

[Input]: Chiffertext tillsammans med offentlig nyckel och privat nyckel . $C$ $(n,g,h,H,pLen,mLen,hLen)$ $(p,g_{p})$

[Utdata]: Vanlig text eller nollsträng. $M$

Operationen med ingångar och ser ut så här: $\mathcal{D}$ $C$ $(n,g,h,H,pLen,mLen,hLen)$ $(p,g_{p})$

Låt oss beräkna , och , var . $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$ $X:={\frac {L(C_{p})}{L(g_{p))}}{\text{ mod }}p$ $L(x):={\frac {x-1}{p))$

Låt oss kontrollera om följande ekvation är sann: . $C=g^{X}h^{H(X)}{\text{ mod }}n$

Om uttrycket är sant, matas ut som dekrypterad klartext, där betecknar de mest signifikanta bitarna i . Annars kommer vi att mata ut en nollsträng. ${\displaystyle [X]^{mLen))$ ${\displaystyle [X]^{mLen))$ $mLen$ $X$

EPOC-2 [16] [14]

Nyckelskapande: G

Ingång och utgång är som följer: ${\mathcal {G}}$

[Input]: Hemlig parameter ( ). $k$ $=plen$

[Utdata]: Par offentlig nyckel och privat nyckel . $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $(p,g_{p})$

Inloggningsoperationen ser ut så här: ${\mathcal {G}}$ $k$

Låt oss välja två primtal , ( ) och beräkna . Här och så att och är primtal, och och så att . $sid$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Vi väljer slumpmässigt så att ordningen blir lika med . $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $sid$

Vi väljer från slumpmässigt och oberoende av . Låt oss räkna ut . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g$ $h:=h_{n}^{0}{\text{ mod }}n$

Installera . Installera och sådant . $pLen:=k$ $mLen$ $rLen$ $mLen+rLen\leq pLen-1$

Vi väljer hashfunktioner och . $H:\{0,1\}^{*}\högerpil \{0,1\}^{hLen}$ $G:{0,1}^{*}\rightarrow \{0,1\}^{hLen}$

Obs: är en extra parameter som ökar effektiviteten för dekrypteringen och kan beräknas från och . när ( -konstant ). och kan fixas av systemet och delas av många användare. $g_{p}$ $sid$ $g$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$ $G$

Kryptering: E

Låt vara ett par krypterings- och dekrypteringsalgoritmer med en symmetrisk nyckel , där längden är . Krypteringsalgoritmen tar en nyckel och klartext och returnerar en chiffertext . Dekrypteringsalgoritmen tar nyckeln och chiffertexten och returnerar klartexten . $SymE=(SymEnc,SymDec)$ $K$ $K$ $gLen$ $SymEnc$ $K$ $X$ $SymEnc(K,X)$ $SymDec$ $K$ $Y$ $SymDec(K,Y)$

Ingång och utgång är som följer: ${\mathcal {E}}$

[Inmatning]: Klartext tillsammans med publik nyckel och . ${\displaystyle M\in \{0,1\}^{mLen))$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymEnc$

[Utdata]: Chiffertext . $C=(C_{1},C_{2})$

Operationen med ingångar och ser ut så här: ${\mathcal {E}}$ $M$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymEnc$

Låt oss välja och beräkna . $r\in \{0,1\}^{rLen}$ $G(R)$

Låt oss räkna ut . Här står för sammanlänkning och . $H(M\parallel R)$ $M\parallel R$ $M$ $R$

$C_{1}:=g^{R}h^{H(M\parallel R)}{\text{ mod }}n$ ; $C_{2}:=SymEnc(G(R),M)$

Obs: En typisk implementering är engångsblocket. Det vill säga , och , där betecknar den bitvisa XOR- operationen . $SymE$ $SymEnc(K,X):=K\oplus X$ $SymDec(X,Y):=X\oplus Y$ $\ plus$

Dekryptering: D

Ingång och utgång är som följer: $\mathcal{D}$

[Input]: Chiffertexten tillsammans med den offentliga nyckeln , hemlig nyckel och . $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $(p,g_{p})$ $SymDec$

[Utdata]: Vanlig text eller nollsträng. $M$

Operationen med ingångarna , och är som följer: $\mathcal{D}$ $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen)$ $(p,g_{p})$ $SymDec$

Låt oss beräkna , och , var . $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$ $R':={\frac {L(C_{p})}{L(g_{p))}}{\text{ mod }}p$ $L(x):={\frac {x-1}{p))$

Beräkna $M':=SymDec(G(R'),C_{2}).$

Låt oss kontrollera om följande ekvation är sann: . $C=g^{R'}h^{H(M'\parallel R')}{\text{ mod }}n$

Om uttrycket är sant, matas ut som den dekrypterade klartexten. Annars kommer vi att mata ut en nollsträng. $M'$

Anteckningar

↑ 1 2 T. Okamoto; S. Uchiyama, 1998 , sid. ett.
↑ Katja Schmidt-Samoa, 2006 .
↑ T. Okamoto; S. Uchiyama, 1998 , sid. 2-3.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , sid. 3-4.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , sid. 8-11.
↑ 1 2 E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung, 2000 .
↑ W. DIFFIE AND ME HELLMAN, 1976 .
↑ T. Elgamal, 1985 .
↑ T. Okamoto; S. Uchiyama, 1998 , sid. 5.
↑ T. Okamoto; S. Uchiyama, 1998 , sid. fyra.
↑ T. Okamoto; S. Uchiyama, 1998 , sid. 3-4.
↑ Maxwell Krohn, 1999 , sid. 53.
↑ Bellare, M., Desai, A., Pointcheval, D., och Rogaway, P., 1998 .
↑ 1 2 3 T. Okamoto; S. Uchiyama, 1998 , sid. 5.
↑ 1 2 3 NTT Corporation, 2001 , sid. 7.
↑ NTT Corporation, 2001 , sid. 9-10.

Litteratur

Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. Säker integration av asymmetriska och symmetriska krypteringsscheman . — 1999.
W. DIFFIE OCH JAG HELLMAN. Nya anvisningar i kryptografi . — 1976.
Maxwell Krohn. Om definitionerna av kryptografisk säkerhet : Attack med vald chiffertext återbesökt . — 1999.
T. Elgamal. Ett kryptosystem med publik nyckel och ett signaturschema baserat på diskreta logaritmer . — 1985.
NTT Information Sharing Platform Laboratories, NTT Corporation. EPOC-2- specifikation . - 2001. - S. 7-10 .
Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. EPOC: Efficient Probabilistic Public-Key Encryption . - 1998. - S. 1-12 .
Utvärderare: Prof. Jean-Jacques Quisquater, Math RiZK, konsult; Vetenskapligt stöd: Dr. François Koeune, K2Crypt. Säkerhetsutvärdering av krypteringsschemat . – 2002.
E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung. Designvalideringar för diskreta logaritmbaserade signaturscheman . - 2000. - S. 276-292 .
Bellare, M., Desai, A., Pointcheval, D. och Rogaway, P. Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. av Crypto'98, LNCS 1462, Springer-Verlag, (engelska) . - 1998. - S. 26-45 .
Katja Schmidt Samoa. En ny falldörrspermutation av Rabin-typ som motsvarar faktorisering . - 2006. - S. 86–88 .