Criptosistemul Benalo

Criptosistemul Benalo este o modificare a criptosistemului Goldwasser-Micali . Principala lor diferență este că criptosistemul vă permite să criptați un bloc de date la un moment dat, în timp ce în schema Goldwasser și Micali, fiecare bit de date este criptat separat [1] .

Proiectat de Josh Benalo în 1988. A fost utilizat în sistemele de vot electronic [2] .

Sistemul este parțial homomorf . Ca și în cazul multor criptosisteme cu cheie publică, acest sistem funcționează în grupul , unde este produsul a două numere prime . $\mathbb {(} {Z}/n\mathbb {Z} )^{*}$ $n$

Descrierea algoritmului

Generare cheie

Se aleg un bloc de dimensiune și două numere prime mari diferite și , care îndeplinesc următoarele condiții: $r$ $p$ $q$
1. $r$ și sunt coprime; $(p-1)/r$
2. $r$ și sunt coprime. $q-1$
Calculează , ; $n=p\times q$ $\phi =(p-1)(q-1)$
este ales astfel încât . Notă: dacă sunt compuse, atunci condițiile de mai sus nu sunt suficiente pentru a asigura decriptarea corectă [3] , adică pentru a se asigura că . Pentru a evita acest lucru, se propune efectuarea următoarei verificări: let . Apoi este ales în așa fel încât pentru fiecare . $y\in \mathbb {Z} _{n}^{*}$ $y^{\phi /r}\nu \equiv 1\mod n$
$r$ $D(E(m))=m$ $r=p_{1}p_{2}\dots p_{k)$ $y$ $p_{{i}}$ $y^{\phi /p_{i}}\neq 1\mod n$
Lasă ; $x=y^{\phi /r}\mod n$

Atunci cheia publică este , iar cheia secretă este . $(y,r,n)$ $(\phi ,x)$

Criptare

Criptarea mesajelor : $m\in {\mathbb {Z} }_{r)$

Se alege arbitrar ; $u\in {\mathbb {Z} _{n}^{*}}$
Apoi . $E_{r}(m)=y^{m}u^{r}\mod n$

Decriptare

În primul rând, rețineți că pentru orice și , sunt valabile următoarele: $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$

Astfel, pentru a calcula , cunoscând , se efectuează operația cu logaritm discret a lui față de baza . Dacă numărul este mic, se poate găsi printr-o căutare exhaustivă, adică prin verificarea egalității pentru toți . Pentru valori mari de , constatarea poate fi efectuată folosind algoritmul Gelfond-Shanks (algoritmul pașilor mari și mici) , obținându-se complexitatea de timp a decriptării . $m$ $A$ $A$ $X$ $r$ $m$ $x^{i}\equiv a\mod n$ $0\dots (r-1)$ $r$ $m$ $O({\sqrt {r))}$

Decriptarea textului cifrat : $c\in {\mathbb {Z} }_{n}^{*}$

Calculat ; $a=c^{\phi /r}\mod n$
Este selectat , adică astfel încât $m=\log _{x}(a)$ $m$ $x^{m}\equiv a\mod n$

Proprietățile criptosistemului

Omomorfism

Criptosistemul Benalo este homomorf în ceea ce privește operația de adăugare:

${\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)$ , unde este funcția de criptare din mesaj ${\mathcal {E}}(x)$ $X$

Rezistenta

Puterea criptosistemului Benalo se bazează pe problema insolubilă a reziduurilor de grad înalt. Cunoscând dimensiunea blocului , modulul și textul cifrat , unde factorizarea numărului este necunoscută, este dificil din punct de vedere computațional să se determine textul simplu . $r$ $n$ $E(M)$ $n$

Literatură

A. I. Trubey „Criptarea homomorfă: securitatea cloud computing și alte aplicații (recenzie)”
Benaloh, Josh (1994) „Criptare probabilistică densă”

Note

↑ Benaloh, Josh (1994) „Criptare probabilistică densă”
↑ Criptare homomorfă: securitate cloud computing și alte aplicații (recenzie) (A.I.Trubey)
↑ Fousse, Laurent; Lafourcade, Pascal; Alnuaimi, Mohamed (2011). „Criptarea probabilistică densă a lui Benaloh a fost revizuită”

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP