Okamoto-Uchiyama kryptosystem

Okamoto-Uchiyama- kryptosystemet är ett probabilistiskt kryptosystem som föreslagits 1998 av Tatsuaki Okamoto och Shigenori Uchiyama , baserat på den logaritmiska funktionen definierad över den multiplikativa gruppen , där , och och är stora primtal. $L$ $\mathbb {(} {Z}/n\mathbb {Z} )^{*}$ $n=p^{2}q$ $sid$ $q$

Till exempel, if är ett stort primtal och , sådan att för , har då strukturen av en grupp med avseende på multiplikationsmodulen . Funktionen som ansluter till är definierad på och har homomorfa egenskaper, och i synnerhet: $sid$ $\gamma _{p}\subset \mathbb {Z_{p^{2}}^{n}}$ ${\displaystyle \gamma _{p}=x<p^{2))$ $x=1{\bmod {p}}$ ${\displaystyle \gamma _{p))$ $p^{2}$ ${\displaystyle \log \colon \gamma _{p}\longrightarrow Z_{p))$ ${\frac {x-1}{p}}$ $x$ $n=p^{2}q$

{\forall (x,y\in \gamma _{p))){\log(xy{\bmod {p))^{2})=\log(x)+\log(y){ \bmod {p}}}

eller mer allmänt:

{\displaystyle {\forall (g\in \gamma _{p},m\in Z_{p))){\log(g^{m}{\bmod {p))^{2})=m\ log(g){\bmod {p))))

Algoritmisering

Nyckelgenerering

Två stora distinkta primtal och väljs och ; $sid$ $q$ $n=p^{2}q$
Ett nummer väljs så att ; $g\in ({\mathbb {Z} }/n{\mathbb {Z} })^{*}$ ${g^{p-1}\neq 1\mod p^{2))$
Beräknad ${\displaystyle {h=g^{n}{\bmod {n))))$

Således är den offentliga nyckeln , är den hemliga nyckeln . $(n,g,h)$ $(p,q)$

Kryptering

För att kryptera ett k-bit meddelande där : $m$ ${0<m<2^{k-1))$

Slumpmässigt väljs ; ${r\in {\mathbb {Z} }/n{\mathbb {Z} }}$
Chiffertexten är beräknad: ${\displaystyle {C=g^{m}h^{r}{\bmod {n))))$

Dekryptering

För att dekryptera ett meddelande : $L(x)={\frac {x-1}{p))$ $C$

m={\frac {L\left(C^{p-1}{\bmod {p}}^{2}\right)}{L\left(g^{p-1}\mod p ^{2}\right)}}{\bmod {p}}

Egenskaper

Kryptosystemet är additivt homomorft , sedan när : ${\displaystyle {m_{1}+m_{2}<p))$

{{\mathcal {E}}(m_{1})\cdot {\mathcal {E}}(m_{2})=(g^{m_{1}}r_{1}^{c} )(g^{m_{2}}r_{2}^{c}){\bmod {n}}=g^{m_{1}+m_{2}}(r_{1}r_{2}) ^{c}{\bmod {=}}{\mathcal {E}}(m_{1}+m_{2}})}

var är meddelandets krypteringsfunktion . ${\displaystyle {{\mathcal {E}}(m)))$ $m$

Styrkan i Okamoto-Uchiyama-kryptosystemet är baserad på komplexiteten i talfaktoriseringsproblemet och kräver bitvisa operationer. $n$ $O(\log _{3}n)$

Minska komplexiteten i dekrypteringen

Det är möjligt att reducera komplexiteten hos kretsen till , för detta väljs den genom en stor (160-bitars) koefficient enligt följande [1] : och kretsen modifieras enligt följande: $O(\log _{2}n)$ $sid$ $t$ ${p-1=tu}$

Välj ett godtyckligt antal så att $g<n$ ${g_{p}=g^{(p-1)}{\bmod {p}}^{2}}$
Beräkna ${\displaystyle {G=g^{u}{\bmod {n))))$
Välj ett godtyckligt tal och beräkna $g^{\prime }<n$ ${\displaystyle {H={g^{\prime ))^{nu}{\bmod {n))))$

Sedan bildar trippeln av värden en offentlig nyckel och en hemlig nyckel. ${\displaystyle {(n,G,H)))$ ${\displaystyle {(p,q)))$

Kryptering

Välj ett slumpmässigt tal $r<n$
Dekryptera -bitmeddelande enligt följande: . ${\displaystyle {(k-1)))$ $m$ ${\displaystyle {c=G^{m}H^{r}{\bmod {n))))$

Dekryptering

${c^{\prime }=c^{t}{\bmod {p}}^{2}=g^{m(p-1)}g^{\prime nr(p-1)} =g_{p}^{m}{\bmod {p}}^{2}}$ ;
${\displaystyle {m=\log(c^{\prime })\log(g_{p})^{-1}{\bmod {p))))$ .

Anteckningar

↑ Accelererar Okamoto-Uchiyamas Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)

Litteratur

Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "Ett nytt kryptosystem med offentlig nyckel lika säkert som factoring". Framsteg inom kryptologi - EUROCRYPT'98.
Accelererar Okamoto-Uchiyamas Public-Key Cryptosystem (Jean-S´ebastien Coron, David Naccache, Pascal Paillier)

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA