Kryptosystém Benaloh - Benaloh cryptosystem

The Kryptosystém Benaloh je rozšířením Kryptosystém Goldwasser-Micali (GM) vytvořil v roce 1985 Josh (Cohen) Benaloh. Hlavní vylepšení kryptosystému Benaloh oproti GM spočívá v tom, že delší bloky dat lze zašifrovat najednou, zatímco v GM je každý bit šifrován samostatně.^[1][2][3]

Definice schématu

Jako mnozí kryptosystémy veřejného klíče, toto schéma funguje ve skupině ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$ kde n je produktem dvou velkých připraví. Toto schéma je homomorfní a tudíž tvárný.

Generování klíčů

Vzhledem k velikosti bloku r, pár veřejného / soukromého klíče je generován následovně:

1. Vyberte si velká prvočísla str a q takhle ${displaystyle rvert (p-1), operatorname {gcd} (r, (p-1) / r) = 1,}$ a ${displaystyle operatorname {gcd} (r, (q-1)) = 1}$
2. Soubor ${displaystyle n = pq, phi = (p-1) (q-1)}$
3. Vybrat ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ takhle ${displaystyle y ^ {phi / r} ot ekviv 1mod n}$.

Poznámka: Li r je složený, poukázali na něj Fousse et al. v roce 2011^[4] že výše uvedené podmínky (tj. podmínky uvedené v původním dokumentu) nestačí k zajištění správného dešifrování, tj. k zajištění toho ${displaystyle D (E (m)) = m}$ ve všech případech (jak by mělo být). Za tímto účelem autoři navrhují následující kontrolu: let ${displaystyle r = p_ {1} p_ {2} tečky p_ {k}}$ být primární faktorizací r. Vybrat ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ tak, že pro každý faktor ${displaystyle p_ {i}}$, je tomu tak ${displaystyle y ^ {phi / p_ {i}} eq 1mod n}$.

1. Soubor ${displaystyle x = y ^ {phi / r} mod n}$

Veřejný klíč je tedy ${displaystyle y, n}$a soukromý klíč je ${displaystyle phi, x}$.

Šifrování zpráv

Šifrovat zprávu ${displaystyle min mathbb {Z} _ {r}}$:

1. Vyberte si náhodný ${displaystyle uin mathbb {Z} _ {n} ^ {*}}$
2. Soubor ${displaystyle E_ {r} (m) = y ^ {m} u ^ {r} mod n}$

Dešifrování zprávy

K dešifrování šifrovacího textu ${displaystyle cin mathbb {Z} _ {n} ^ {*}}$:

1. Vypočítat ${displaystyle a = c ^ {phi / r} mod n}$
2. Výstup ${displaystyle m = log _ {x} (a)}$, tj. najít m takhle ${displaystyle x ^ {m} ekv. amod n}$

Abyste porozuměli dešifrování, nejprve si všimněte, že pro všechny ${displaystyle min mathbb {Z} _ {r}}$ a ${displaystyle uin mathbb {Z} _ {n} ^ {*}}$ my máme:

${displaystyle a = (c) ^ {phi / r} ekviv (y ^ {m} u ^ {r}) ^ {phi / r} ekviv (y ^ {m}) ^ {phi / r} (u ^ { r}) ^ {phi / r} ekviv (y ^ {phi / r}) ^ {m} (u) ^ {phi} ekviv (x) ^ {m} (u) ^ {0} ekviv x x {m } mod n}$

Obnovit m z A, vezmeme diskrétní log z A základna X. Li r je malý, můžeme obnovit m vyčerpávajícím hledáním, tj. kontrolou, zda ${displaystyle x ^ {i} ekv. amod n}$ pro všechny ${displaystyle 0dots (r-1)}$. Pro větší hodnoty r, Baby-step obří krok k obnovení lze použít algoritmus m v ${displaystyle O ({sqrt {r}})}$ čas a prostor.

Bezpečnostní

Zabezpečení tohoto systému spočívá na Problém s vyšší reziduozitou konkrétně daný z,r a n kde je faktorizace n není známo, je výpočetně nemožné určit, zda z je rth zbytek mod n, tj. pokud existuje X takhle ${displaystyle zequiv x ^ {r} mod n}$.

Reference