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. Orijinal makaledeki küçük bir hata Laurent Fousse et al. 'da düzeltilmiştir. == Sistem tanımı == Çoğu Açık anahtarlı şifreleme yöntemi gibi, bu sistem de {\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. === Anahtar oluşturma === Açık/gizli anahtar çifti aşağıdaki şekilde oluşturulur: # Bir r blok uzunluğu sayısı seçilir. # {\displaystyle r\vert (p-1),\operatorname {gcd} (r,(p-1)/r)=1,} ve {\displaystyle \operatorname {gcd} (r,(q-1))=1} olacak şekilde p ve q büyük asal sayıları seçilir. # {\displaystyle n=pq,\phi =(p-1)(q-1)} olsun. # {\displaystyle y^{\phi /r} ot \equiv 1\mod n} olmak üzere bir {\displaystyle y\in \mathbb {Z} _{n}^{*}} seçilir. :: Not: 2011'de yayınlanan Fousse et al. 'da belirtilen bilgiye göre r asal değilken, yukarıdaki, orijinal makalede belirtilmiş şart, doğru deşifreleme için yeterli değildir. D(E(m)) = m tüm durumlarda sağlamalıdır. Bu sebepten dolayı yazarlar şu kontrolü yapmayı tavsiye etmektedir: r=p_1p_2\dots p_k 'nin r'nin asal çarpanları olduğunu varsayalım. Öyle bir y \in \mathbb{Z}^*_n seçelim ki her çarpan p_i için y^{\phi/p_i} e 1\mod n sağlasın. # x=y^{\phi/r}\mod n sağlayacak x seçilir. Açık anahtar y,n ve gizli anahtar {\displaystyle \phi ,x} dir. === Mesajı şifreleme === {\displaystyle m\in \mathbb{Z} _{r}} olan bir m mesajını şifrelemek için: # Rastgele bir {\displaystyle u\in \mathbb{Z} _{n}^{*}} seçilir. # Şifrelenmiş m mesajı {\displaystyle E_{r}(m)=y^{m}u^{r}\mod n} formülünden elde edilir. === Mesajı deşifreleme === {\displaystyle c\in \mathbb{Z} _{n}^{*}} olan bir c metnini çözmek için: # {\displaystyle a=c^{\phi /r}\mod n} hesaplanır. #{\displaystyle x^{m}\equiv a\mod n} olacak şekilde çıktı {\displaystyle m=\log _{x}(a)} bulunur. Her {\displaystyle m\in \mathbb{Z} _{r}} ve {\displaystyle u\in \mathbb{Z} _{n}^{*}} nin şu özelliklere sahip olması gerekmektedir: a = (c) ^ 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 0\dots (r-1) için 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 O(\sqrt{r}) zorluğunda elde etmek için kullanılabilir. === Güvenlik === 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 z \equiv x^r \mod n sağlasın. ==Kaynakça== Kategori:Kriptografik algoritmalar