Benaloh Kriptosistemi

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  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.
  ve   olacak şekilde p ve q büyük asal sayıları seçilir.
  olsun.    
  olmak üzere bir  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.  tüm durumlarda sağlamalıdır. Bu sebepten dolayı yazarlar şu kontrolü yapmayı tavsiye etmektedir:  'nin r'nin asal çarpanları olduğunu varsayalım. Öyle bir  seçelim ki her çarpan  için  sağlasın.
  sağlayacak x seçilir.

Açık anahtar y,n ve gizli anahtar  dir.

Mesajı şifreleme 
 olan bir m mesajını şifrelemek için:

 Rastgele bir  seçilir.
 Şifrelenmiş m mesajı  formülünden elde edilir.

Mesajı deşifreleme 
 olan bir c metnini çözmek için:

  hesaplanır.
 olacak şekilde çıktı  bulunur.

Her  ve  nin şu özelliklere sahip olması gerekmektedir:

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  için  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  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  sağlasın.

Kaynakça

Kriptografik algoritmalar