Benaloh şifreleme sistemi

Benaloh kriptosistemi 1994 yılında Josh (Cohen) Benaloh tarafından oluşturulan Goldwasser-Micali şifreleme sisteminin bir genişletilmesidir. Goldwasser-Micali'de bitler tek tek şifrelenirken, Benaloh Kriptosisteminde veri blokları grup olarak şifrelenmektedir.^[1] Orijinal makaledeki küçük bir hata Laurent Fousse et al. 'da düzeltilmiştir.

Çoğu Açık anahtarlı şifreleme yöntemi gibi, bu sistem de ${\displaystyle {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}}$ kümesinde çalışmaktadır. Burada n iki büyük Asal sayının çarpımıyla elde edilir. Bu sistem homomorfik ve bununla birlikte kolay biçimlendirilebilirdir.

Homomorfik, iki şifreli sayının toplamının iki sayının ayrı ayrı elde edilmesine gerek kalmadan deşifre edilebilmesidir.

Açık/gizli anahtar çifti aşağıdaki şekilde oluşturulur:

1. Bir r blok uzunluğu sayısı seçilir.
2. ${\displaystyle {\displaystyle r\vert (p-1),\operatorname {gcd} (r,(p-1)/r)=1,}}$ ve ${\displaystyle {\displaystyle \operatorname {gcd} (r,(q-1))=1}}$ olacak şekilde p ve q büyük asal sayıları seçilir.
3. ${\displaystyle {\displaystyle n=pq,\phi =(p-1)(q-1)}}$ olsun.
4. ${\displaystyle {\displaystyle y^{\phi /r}\not \equiv 1\mod n}}$ olmak üzere bir ${\displaystyle {\displaystyle y\in \mathbb {Z} _{n}^{*}}}$ seçilir.

Not: 2011'de yayınlanan Fousse et al.^[2] 'da belirtilen bilgiye göre r asal değilken, yukarıdaki, orijinal makalede belirtilmiş şart,

doğru deşifreleme için yeterli değildir. ${\displaystyle D(E(m))=m}$ tüm durumlarda sağlamalıdır. Bu sebepten dolayı yazarlar şu kontrolü yapmayı tavsiye etmektedir: ${\displaystyle r=p_{1}p_{2}\dots p_{k}}$ 'nin r'nin asal çarpanları olduğunu varsayalım. Öyle bir ${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ seçelim ki her çarpan ${\displaystyle p_{i}}$ için ${\displaystyle y^{\phi /p_{i}}\neq 1\mod n}$ sağlasın.

1. ${\displaystyle x=y^{\phi /r}\mod n}$ sağlayacak x seçilir.

Açık anahtar y,n ve gizli anahtar ${\displaystyle {\displaystyle \phi ,x}}$ dir.

${\displaystyle {\displaystyle m\in \mathbb {Z} _{r}}}$ olan bir m mesajını şifrelemek için:

1. Rastgele bir ${\displaystyle {\displaystyle u\in \mathbb {Z} _{n}^{*}}}$ seçilir.
2. Şifrelenmiş m mesajı ${\displaystyle {\displaystyle E_{r}(m)=y^{m}u^{r}\mod n}}$ formülünden elde edilir.

${\displaystyle {\displaystyle c\in \mathbb {Z} _{n}^{*}}}$ olan bir c metnini çözmek için:

1. ${\displaystyle {\displaystyle a=c^{\phi /r}\mod n}}$ hesaplanır.
2. ${\displaystyle {\displaystyle x^{m}\equiv a\mod n}}$ olacak şekilde çıktı ${\displaystyle {\displaystyle m=\log _{x}(a)}}$ bulunur.

Her ${\displaystyle {\displaystyle m\in \mathbb {Z} _{r}}}$ ve ${\displaystyle {\displaystyle u\in \mathbb {Z} _{n}^{*}}}$ nin şu özelliklere sahip olması gerekmektedir:

${\displaystyle 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}\ modn}$

a dan m yi elde etmek için a nın x tabanında ayrık logaritması alınır. Eğer r küçükse m yi kapsamlı bir arama yaparak elde edebiliriz. Yani her ${\displaystyle 0\dots (r-1)}$ için ${\displaystyle x^{i}\equiv a\mod n}$ sağlıyor mu diye bakarız. Daha büyük r değerleri için Bebek adımı, dev adımı algoritması m yi ${\displaystyle O({\sqrt {r}})}$ zorluğunda elde etmek için kullanılabilir.

Bu sistemin güvenliğinin temelinde Higher residuosity problem yatmaktadır. Spesifik olarak, z, r ve n için, n'nin çarpanları bilinmezken, z'nin mod n'nin r'inci artığı olup olmadığını günümüz bilgisayarlarıyla yeterli zamanda hesaplamak mümkün değildir. Yani, öyle bir x olsun ki ${\displaystyle z\equiv x^{r}\mod n}$ sağlasın.