Goldwasser-Micali şifreleme sistemi

Goldwasser–Micali (GM) kriptosistemi 1982 yılında Shafi Goldwasser ve Silvio Micali tarafından geliştirilmiş bir asimetrik anahtar şifreleme algoritmasıdır. GM standart kriptografik varsayımlar altında güvenliği kanıtlanmış ilk probabilistik açık anahtar şifreleme yöntemidir. Bununla birlikte başlangıç düz metinden yüzlerce kez daha geniş olan şifreli metinler olduğundan verimli bir kriptosistem değildir. Kriptosistemin güvenlik özelliğini kanıtlamak için Shafi Goldwasser ve Silvio Micali anlamsal güvenliğin geniş alanda kullanılan bir tanımını önerdiler.

GM kriptosistemi kuadratik kalan probleminin p ve q büyük asal sayılar olmak üzere, N=p.q modunun zorluğunun varsayımına dayanan anlamsal güvenliktir. Bu varsayım verilen(x,N)'nin x'in, +1 için bir Jacobi sembolü olduğunda, N(x=y^2 mod N bazı y'ler için) modulüne göre kuadratik bir kalan olup olmadığını belirleme zorluğunu ifade eder. Kuadratik kalan problemi yeni kuadratik kalanlar herhangi bir kısım tarafından üretilebiliyorken verilen N nin çarpanlara ayırımını bu çarpanla ayrım bilgisi verilemese bile kolayca çözebilir. GM kriptosistemi birbirinden ayrı düz metin bitlerini ya rastgele kuadratik kalanlar ya da tüm kuadratik sembol +1 ile birlikte modül N'ye göre kalmayanları alıp şifreleyerek bu asimetrikliği sağlamış olur. Alıcılar N'nin çarpanlarını gizli anahtar olarak kullanır ve mesajı aldığı şifreli metnin değerlerinin kuadratik kalanını test ederek deşifrelerler.

Çünkü Goldwasser–Micali düz metnin her tek bitini şifrelemek için yaklaşık olarak |N| boyutunda bir değer üretir. GM şifreleme sağlam ölçüde şifreli metin genişlemesini sonucunu verir. Çarpanlara ayırmaya çalışma ataklarını önlemek için, |N| nin yüzlerce bit ya da daha fazla olması tavsiye edilmiştir. Bu yüzden yöntem temelde bir kavram kanıtı olarak hizmet eder ve Elgamal gibi daha etkili kanıtlanabilir güvenlik yöntemleri geliştirilmiştir. Çünkü şifreleme probabilistik algoritma kullanılarak şifrelenmiştir. Verilen bir düzmetin her bir zamanda şifrelediği birbirinden çok farklı şifrelimetinleri üretebilir. Bu hasımın bilinen şifrelimetinleri sözlükle karşılaştırarak haberleşmeler arasında müdahale edip eriştiği mesajlardan herhangi bir benzerlik bulup düz metne erişmeye çalışmasını önleme avantajı demektir.

Goldwasser–Micali 3 algoritma içerir: açık ve gizli anahtar üreten probabilistik anahtar üretimi algoritması, probabilistik kriptosistem algoritması ve bir deterministik deşifreleme algoritması.

Bu yöntem verilen bir x değerinin kare mod N, ((p,q) N nin çarpanları) olup olmadığına karar vermenin zorluğuna güvenmektedir. Bu aşağıdaki prosedürü kullanarak başarılır:

1. x_p = x mod p, x_q = x mod q Hesapla 2. EĞER ${\displaystyle x_{p}^{(p-1)/2}\equiv 1{\pmod {p}}}$ VE ${\displaystyle x_{q}^{(q-1)/2}\equiv 1{\pmod {q}}}$ ise x mod N. ye göre bir kuadratik kalandır.

GM içindeki kullanılan mod alma işlemi RSA kriptosistem içerisindeki aynı yöntemle gerçekleştirilir. (ayrıntılar için RSA anahtar üretimine bakınız)

1.Alice 2 farklı büyük p ve q asal sayılarını rastgele ve her biri bir birinden bağımsız olacak şekilde üretir. 2.Alice N = p q. yu hesaplar 3.Alice ${\displaystyle \left({\frac {x}{p}}\right)=\left({\frac {x}{q}}\right)=-1}$ olacak şekilde bir x bulur ve bundan dolayı Jacobi sembolü ${\displaystyle \left({\frac {x}{N}}\right)}$ is +1 dir.

X değeri rastgele sayılar seçerek ve 2 Legendre sembolünü test ederek bulunabilir. Eğer (p,q) =3 mod 4 (N Blum Tam sayısı) ise o zaman N-1 değeri gereken özelliği karşılıyor anlamına gelir. Açık anahtar (x,N) den oluşur. Gizli anahtar (p,q) çarpanlarından oluşur.

Varsayalım ki Bob Alice e m mesajını göndermeyi istesin:

Bob ilk önce m i (m₁, ..., m_n) bitlerinden oluşan bir string olarak çözecektir.

1.Her m_i, biti için, Bob modulo N den birimler halinde rastgele y değeri üretir veya

GCD(y,N) = 1. olacak şekilde rastgele değerler üretir.
  ${\displaystyle c_{i}=y^{2}x^{m_{i}}{\pmod {N}}}$. değerlerini sonuç olarak üretir.

Bob (c₁, ..., c_n). Şifreli metinlerini gönderir.

Alice (c₁, ..., c_n) i alır. Aşağıdaki prosedürü kullanarak m yi geri elde edebilir.

1.Asal çarpan (p,q) kullanan Her bir i için, Alice ci değerinin kuadratik kalan olup olmadığını belirler eğer öyle ise m_i = 0, değilse m_i = 1. dir.

Alice m = (m₁, ..., m_n). Mesajını çıktı olarak üretir.

Burada basitçe bu kriptosistemi Jacobi sembolü +1 ile rastgele modül N değerinin kuadratik kalan olup olmadığını belirleme problemine dönüştürerek kırmaya çalışma vardır. Eğer verilen bir A algoritması kriptosistemi kırarsa, ardından verilen bir 'x' değerinin kuadratik modül N kalanı olup olmadığını belirlemek için, biz A'yı (x,N) açık anahtarlarını kullanarak kırabildiğini anlamak için test ederiz. Eğer 'x' bir kalan değilse o zaman 'A' doğru olarak çalışacaktır. Ancak eğer 'x' bir kalansa o zaman her şifreli metin basitçe rastgele kuadratik kalan olabilir, bu yüzden 'A' zamanın yarısından daha doğru olamaz. Bundan başka bu problem verilen bir 'B' için her açık anahtarı tıpkı diğer açık anahtar gibi güvenli kılan rastgele kendini dönüştürme problemidir.

GM kriptosistemi homomorfik özelliklere sahiptir. Eğer c₀, c₁ m₀, m₁, bitlerinin şifrelenmiş halleriyse o zaman c₀c₁ mod N, in şifrelenmiş halleri olacaktır. Bu sebebten dolayı GM kriptosistemi bazen daha karmaşık kriptografik ilkel yapılarla birlikte kullanılır.

• S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing. ss. 365-377. doi:10.1145/800070.802212. 
• S. Goldwasser, S. Micali (1984). "Probabilistic encryption". Journal of Computer and System Sciences. 28 (2). ss. 270-299. doi:10.1016/0022-0000(84)90070-9.