Benalo kriptorendszer

A Benalo kriptorendszer a Goldwasser-Micali kriptorendszer egy módosítása . Legfőbb különbségük, hogy a kriptorendszer lehetővé teszi egy-egy adatblokk titkosítását, míg a Goldwasser és Micali sémában minden adatbit külön titkosításra kerül [1] .

Josh Benalo tervezte 1988-ban. Elektronikus szavazórendszerekben használták [2] .

A rendszer részben homomorf . Mint sok nyilvános kulcsú kriptorendszer, ez a rendszer a csoportban működik , ahol két prímszám szorzata . $\mathbb {(} {Z}/n\mathbb {Z} )^{*}$ $n$

Az algoritmus leírása

Kulcsgenerálás

Egy méretű blokkot és két nagy különböző prímszámot kell kiválasztani, amely megfelel a következő feltételeknek: $r$ $p$ $q$
1. $r$ és coprime; $(p-1)/r$
2. $r$ és koprime. $q-1$
Kiszámolja , ; $n=p\times q$ $\phi =(p-1)(q-1)$
úgy van kiválasztva , hogy . Megjegyzés: ha összetett, akkor a fenti feltételek nem elegendőek a helyes visszafejtéshez [3] , vagyis annak biztosításához . Ennek elkerülése érdekében javasolt a következő ellenőrzés elvégzése: legyen . Ezután úgy van megválasztva, hogy mindegyikhez . $y\in \mathbb {Z} _{n}^{*}$ $y^{\phi /r}\not \equiv 1\mod n$
$r$ $D(E(m))=m$ ${\displaystyle r=p_{1}p_{2}\dots p_{k))$ $y$ $p_{{i}}$ $y^{\phi /p_{i}}\neq 1\mod n$
Legyen ; $x=y^{\phi /r}\mod n$

Ekkor a nyilvános kulcs , a titkos kulcs pedig . ${\megjelenítési stílus (y,r,n)}$ $(\phi ,x)$

Titkosítás

Üzenet titkosítás : ${\displaystyle m\in {\mathbb {Z} }_{r))$

Önkényes választják ; $u\in {\mathbb {Z} _{n}^{*}}$
Akkor . $E_{r}(m)=y^{m}u^{r}\mod n$

Dekódolás

Először is vegye figyelembe, hogy bármelyik és esetén a következők érvényesek: ${\displaystyle m\in {\mathbb {Z} }_{r))$ $u\in {\mathbb {Z} }_{n}^{*}$ $a=(c)^{\phi /r}\equiv (y^{m}u^{r})^{\phi /r}\equiv (y^{m})^{\phi / r}(u^{r})^{\phi /r}\equiv (y^{\phi /r})^{m}(u)^{\phi }\equiv (x)^{m}( u)^{0}\equiv x^{m}\mod n$

Így a kiszámításához ismeretében a diszkrét logaritmus műveletét hajtjuk végre a bázishoz képest . Ha a szám kicsi, akkor kimerítő kereséssel, azaz az egyenlőség ellenőrzésével lehet megtalálni . Nagy értékek esetén a megállapítás a Gelfond-Shanks algoritmussal (nagy és kis lépések algoritmusa) végezhető el , megkapva a visszafejtés időbeli összetettségét . $m$ $a$ $a$ $x$ $r$ $m$ $x^{i}\equiv a\mod n$ $0\dots (r-1)$ $r$ $m$ $O({\sqrt {r)))$

Rejtjelezett szöveg visszafejtése : $c\in {\mathbb {Z} }_{n}^{*}$

Számított ; $a=c^{\phi /r}\mod n$
Ki van választva , vagyis olyan, hogy $m=\log _{x}(a)$ $m$ $x^{m}\equiv a\mod n$

Kriptorendszer tulajdonságai

Homomorfizmus

A Benalo kriptorendszer homomorf az összeadási művelet tekintetében:

${\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}u_{1}^{r}) (g^{x_{2}}u_{2}^{r})=g^{x_{1}+x_{2}}(u_{1}u_{2})^{r}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}r)$ , ahol az üzenetből származó titkosítási funkció ${\mathcal {E}}(x)$ $x$

Kitartás

A Benalo kriptorendszer ereje a magas fokú maradványok megoldhatatlan problémáján alapul. A blokkméret , modul és rejtjelezett szöveg ismeretében , ahol a szám faktorizálása ismeretlen, számításilag nehéz meghatározni a nyílt szöveget . $r$ $n$ $E(M)$ $n$

Irodalom

A. I. Trubey „Homomorf titkosítás: felhőalapú számítástechnikai biztonság és egyéb alkalmazások (áttekintés)”
Benaloh, Josh (1994): "Sűrű valószínűségi titkosítás"

Jegyzetek

↑ Benaloh, Josh (1994) "Dense Probabilistic Encryption"
↑ Homomorf titkosítás: felhőalapú számítástechnikai biztonság és egyéb alkalmazások (áttekintés) (A.I.Trubey)
↑ Fousse, Laurent; Lafourcade, Pascal; Alnuaimi, Mohamed (2011). "A Benaloh's Dense Probabilistic Encryption Revisited"

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya