Rabin şifreleme sistemi sayfasının kaynağını görüntüle

'''Rabin şifreleme sistemi''', '''Rabin kriptoloji''' veya '''Rabin kriptosistemi''', güvenliği [[RSA (şifreleme yönetimi)|RSA]]'daki gibi tam sayı çarpanlarına ayırmanın zorluğu üzerine kurgulanmış olan asimetrik bir kriptografik tekniktir. Bununla birlikte, Rabin kriptosisteminin avantajı, saldırgan tam sayıları verimli bir şekilde çarpanlarına ayıramadığı sürece, seçilmiş bir düz metin saldırısına karşı hesaplama açısından güvenli olduğu matematiksel olarak kanıtlanmıştır, oysa RSA için bilinen böyle bir kanıt yoktur.<ref name=stinson>{{Kitap kaynağı|başlık=Cryptography: Theory and Practice|soyadı=Stinson|ad=Douglas|yayıncı=CRC Press LLC|yıl=1995}}</ref>{{rp|145}} Rabin fonksiyonunun her çıktısının dört olası girdiden herhangi biri tarafından üretilebilmesi dezavantajı; her çıktı bir şifreli metinse, olası dört girdiden hangisinin gerçek düz metin olduğunu belirlemek için şifre çözmede ekstra karmaşıklık gerekir.

== Tarihçe ==
Algoritma Ocak 1979'da [[Michael O. Rabin]] tarafından yayınlandı.<ref>{{Web kaynağı | url = http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf | başlık = Digitalized Signatures and Public-Key Functions as Intractable as Factorization | soyadı = Rabin | ad = Michael | yayıncı = MIT Laboratory for Computer Science | ay = Ocak | yıl = 1979 | arşivurl = https://web.archive.org/web/20100712010627/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf | arşivtarihi = 12 Temmuz 2010}}</ref> Rabin şifreleme sistemi, şifreli metinden düz metni kurtarmanın [[çarpanlara ayırma]] kadar zor olduğu kanıtlanabilen ilk asimetrik şifreleme sistemiydi.

==Şifreleme algoritması==
Tüm asimetrik şifreleme sistemleri gibi, Rabin şifreleme sistemi de bir anahtar çifti kullanır: şifreleme için [[genel anahtar]] ve şifre çözme için [[özel anahtar]]. Genel anahtar, herkesin kullanması için yayınlanırken, özel anahtar yalnızca mesajın alıcısı tarafından bilinir.

=== Anahtar üretimi ===
Rabin şifreleme sisteminin anahtarları şu şekilde oluşturulur:

# İki tane çok büyük ve farklı <math>p</math>, <math>q</math> asal sayıları seçilir. Kare kökün hesaplanmasını basitleştirmek için bir tanesini <math>p \equiv q \equiv 3 \pmod{4}</math> yöntemi ile seçebiliriz. Fakat yöntem herhangi daha büyük asal sayılarla çalışır.
# <math>n = p \cdot q</math> hesaplanır. Burada <math>n</math> açık anahtar, asal sayılardan oluşan <math>(p, q)</math> ise özel anahtardır.

===Şifreleme===
Bir <math>M</math> mesajı, önce tersine çevrilebilir bir eşleme kullanılarak <math>m < n</math> sayısına dönüştürülerek ve ardından <math>c = m^2 \pmod{n}</math> hesaplanarak şifrelenebilir. Şifreli metin, <math>c</math>'dir.

===Şifre çözme===
<math>m</math> mesajı, şifreli <math>c</math> metninden karekök modül <math>n</math>'si aşağıdaki gibi alınarak elde edilebilir.

# Aşağıdaki formülleri kullanarak <math>c</math> modül <math>p</math> ve <math>q</math>'nun karekökünü hesaplayın;
#: <math>\begin{align}
  m_p &= c^{\frac{1}{4}(p+1)} \pmod{p} \\
  m_q &= c^{\frac{1}{4}(q+1)} \pmod{q}
\end{align}</math>
# <math>y_p\cdot p + y_q \cdot q = 1</math> olacak şekilde <math>y_p</math> ve <math>y_q</math>'i bulmak için [[Genişletilmiş Öklid algoritması]] kullanın.
# <math>c</math> modül <math>n</math>'nin dört karekökünü bulmak için [[Çin kalan teoremi]]'ni kullanın:
#: <math>\begin{align}
   r_1 &= \left( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p \right) \pmod{n} \\
   r_2 &= n - r_1  \\
   r_3 &= \left( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p \right) \pmod{n} \\
   r_4 &= n - r_3 
\end{align}</math>

Bu dört değerden biri orijinal düz metin <math>m</math>'dir, ancak dördünden hangisinin doğru olduğu ek bilgi olmadan belirlenemez.

Kesin anahtar üretimi süreci aşağıdaki gibidir:

====Karekökleri hesaplama====
Yukarıdaki 1. adımdaki formüllerin aslında <math>c</math>'in kareköklerini aşağıdaki gibi ürettiğini gösterebiliriz. İlk formül için, <math>m_p^2 \equiv c \pmod{p}</math> olduğunu kanıtlamak istiyoruz. <math>p \equiv 3 \pmod{4}</math> olduğundan, <math display="inline">\frac{1}{4}(p+1)</math> üssü bir tam sayıdır. <math>c \equiv 0 \pmod{p}</math> ise ispat önemsizdir, bu nedenle <math>p</math>'nin <math>c</math>'yi bölmediğini varsayabiliriz. <math>c \equiv m^2 \pmod{pq}</math> ögesinin <math>c \equiv m^2 \pmod{p}</math> anlamına geldiğini unutmayın, dolayısıyla <math>c</math> modül <math>p</math>'ye göre bir [[kuadratik kalıntı]]dır (rezidü). Buradan;

: <math>m_p^2 \equiv c^{\frac{1}{2}(p+1)} \equiv c\cdot c^{\frac{1}{2}(p-1)} \equiv c \cdot 1 \pmod{p}</math>

yazılabilir. Son adım [[Euler ölçütü]] tarafından doğrulanır.

Deşifreleme şifreli metninin kare köklerini hesaplamak için <math>c</math> mod asal sayı <math>p</math> ve <math>q</math>'yu gerektirir.

:<math>m_p = c^{\frac{(p+1)}{4}} \, \pmod{p}</math> ve

:<math>m_q = c^{\frac{(q+1)}{4}} \, \pmod{q}</math> olur.

Biz bu metodun <math>p</math> için çalışmasını aşağıdaki gibi gösterebiliriz. İlk <math>\frac{(p+1)}{4}</math>'ün, <math>p \equiv 3\!\!\!\pmod{4}</math> bir tam sayı olduğunu gösterir. <math>c \equiv 0 \pmod{p}</math> için varsayım basittir. Bu yüzden biz <math>p</math>'nin <math>c</math>'ye bölünmediğini varsayabiliriz. O zaman:

:<math>m_p^2 \equiv c^{\frac{(p+1)}{2}} \equiv c\cdot c^{\frac{(p-1)}{2}} \equiv c \cdot\left({c\over p}\right) \pmod{p},</math>
:<math>\left({c\over p}\right)</math> [[Legendre sembolü]]dür. 
:<math>c\equiv m^2\pmod{pq}</math>'dan aşağıdaki gibi 
:<math>c\equiv m^2\pmod{p}</math> olarak hesaplanır.

Bu yüzden <math>x</math>, modül <math>p</math>'nin kuadratik kalanıdır. Buradan;
:<math>\left({c\over p}\right)=1</math> ve 
:<math>m_p^2 \equiv c \pmod{p}</math> elde edilir.
:<math>p \equiv 3\pmod{4}</math> ilişkisi bir gereksinim değildir. Çünkü kare kökler in diğer asal sayılarla modülü de hesaplanabilir.

Rabin kare köklerin asal sayılarla modlarını bulmak için [[Berlekamp algoritması]]nın özel bir durumunu kullanmayı önerir.

===Örnek===
Örnek olarak, <math>p = 7</math> ve <math>q = 11</math> olarak alalım, ardından <math>n=77</math> olur (Elbette burada anahtarların seçimi kötüdür. 77'nin çarpanlarına ayrılması basittir gerçek örneklerde çok çok daha büyük sayılar kullanılır). Düz metnimiz olarak <math>m = 20</math> alalım. Şifreli metin bu şekilde

:<math>c = m^2 \pmod{n} = 400 \pmod{77} = 15</math> olarak elde edilir.

Bizim basit örneğimizde <math>P = \{ 0, \dots, 76 \}</math> bizim düz metin uzayımızdır. Biz <math>m = 20</math>'yi bizim düz metnimiz olarak alacağız. Bu yüzden şifreli metin, <math>c = m^2 \, \pmod{n} = 400 \, \pmod{77} = 15</math>'dir. Açıkça <math>m</math>'nin 4 farklı değeri <math>m \in \{ 13, 20, 57, 64 \}</math> için, şifreli metin 15 üretilir. Bu Rabin algoritması tarafından üretilen çoğu şifreli metinler için geçerlidir.

Şifre çözme işlemi şu şekilde ilerler:
# <math>m_p = c^{\frac{1}{4}(p+1)} \pmod{p} = 15^2 \pmod{7} = 1</math> ve <math>m_q = c^{\frac{1}{4}(q+1)} \pmod{q} = 15^3 \pmod{11} = 9</math> hesaplanır.
# <math>y_p = -3</math> ve <math>y_q = 2</math>'yi hesaplamak için genişletilmiş Öklid algoritması kullanılır. <math>y_p \cdot p + y_q \cdot q = (-3 \cdot 7) + (2 \cdot 11) = 1</math> olduğunu doğrulayabiliriz.
# Dört düz metin adayını hesaplayın:
#: <math>\begin{align}
  r_1 &= (-3 \cdot 7 \cdot 9 + 2 \cdot 11 \cdot 1) \pmod{77} = 64 \\
  r_2 &= 77 - 64 = 13 \\
  r_3 &= (-3 \cdot 7 \cdot 9 - 2 \cdot 11 \cdot 1) \pmod{77} = \mathbf{20} \\
  r_4 &= 77 - 20 = 57
\end{align}</math>

ve <math>r_3</math>'in istenen düz metin olduğunu görüyoruz. Dört adayın hepsinin 15 mod 77'nin karekökleri olduğuna dikkat edin. Yani, her aday için <math>r_i^2 \pmod{77} = 15</math>, böylece her <math>r_i</math> aynı değere (15) şifreler.

Eğer <math>c</math> ve <math>r</math> bilinirse düz metin <math>m^2 \equiv c\pmod{r}</math> ile <math>m \in \{ 0, \dots, n-1 \}</math> olacaktır. <math>r</math> bir kompozit sayıdır kompozit sayı asal olmayan herhangi bir pozitif sayıdan daha büyük pozitif sayı demektir. Eğer <math>N > 0</math> bir tam sayı ise ve <math>N = a \times b</math> gibi <math>1 < a, b < N</math> sayısı var ise o zaman <math>N</math> kompozit sayı demektir (yani Rabin algoritmasının <math>n = p \cdot q</math> formülüne benzer). <math>m</math>'yi bulmak için bilinen daha etkili bir metot yoktur. Eğer asal ise (Rabin algoritmasındaki <math>p</math> ve <math>q</math> gibi) [[Çin kalan teoremi]] <math>m</math>'nin çözümü için başvurulabilecek bir metottur. Bu yüzden kare kökler;

:<math>m_p = \sqrt{c} \, \pmod{p}</math> ve

:<math>m_q = \sqrt{c} \, \pmod{q}</math> hesaplanmış olmalıdır.

Bizim örneğimizde <math>m_p = 1</math> ve <math>m_q = 9</math> alalım, 
Genişletilmiş Öklid Algoritması uygulanarak biz <math>y_p</math> ve <math>y_q</math>'yu bulmak isteyelim.
<math>y_p \cdot p + y_q \cdot q = 1</math> ile bulunur. Bizim örneğimizde <math>y_p = -3</math> ve <math>y_q = 2</math> bulunur.

Şimdi, Çin kalan teoremi yardımıyla, <math>c + n \mathbb{Z} \in \mathbb{Z} / n \mathbb{Z}</math>'nin dört karekökü <math>+r</math>, <math>-r</math>, <math>+s</math> ve <math>-s</math> şeklinde hesaplanır (burada <math>\mathbb{Z} / n \mathbb{Z}</math>, <math>\bmod{n}</math> uyum sınıfları halkası [ring of congruence classes] anlamına gelir.) 4 kare kök <math>\{ 0, \dots, n-1 \}</math> kümesi içindedir:

:<math>\begin{matrix}
r & = & ( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \, \pmod{n} \\
-r & = & n - r \\
s & = & ( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \, \pmod{n} \\
-s & = & n - s 
\end{matrix}</math>'dir.

Bu kare köklerin bir tanesi <math>\bmod {n}</math> orijinal düz metin <math>m</math>'dir. Bizim örneğimizde <math>m \in \{ 64, \mathbf{20}, 13, 57 \}</math>'dir.

Rabin kendi makalesinde eğer bir kişi hem <math>r</math> hem de <math>s</math>'yi hesaplayabilirse o zaman <math>n</math>'nin çarpanlarını da hesaplayabileceğini bize şöyle gösteriyor;
:ya <math>\gcd(|r-s|, n) = p</math> ya <math>\gcd(|r-s|, n) = q</math>, burada <math>\gcd</math> (Greatest Common Divisor) yani [[en büyük ortak bölen]] (EBOB) anlamına gelir.

Çünkü eğer bir kişi <math>r</math> ve <math>s</math>'yi biliyorsa, en büyük ortak bölen <math>n</math>'nin çarpanlarını bulmak için etkili bir hesaplama yöntemidir bizim örneğimizde (<math>57</math> ve <math>13</math>'ü <math>r</math> ve <math>s</math> olarak alalım):

:<math>\gcd(57-13, 77) = \gcd(44, 77) = 11 = q</math> bulunur.

==Dijital İmza Algoritması==
Rabin şifreleme sistemi, [[dijital imza]]'lar oluşturmak ve doğrulamak için kullanılabilir. İmza oluşturmak için <math>(p, q)</math> özel anahtarı gerekir. Bir imzanın doğrulanması için <math>n</math> ortak anahtarı gerekir.

===İmzalama===
Bir <math>m < n</math> mesajı, bir özel anahtar <math>(p, q)</math> ile aşağıdaki gibi imzalanabilir.

# Rastgele bir <math>u</math> değeri oluşturun.
# <math>c = H(m|u)</math>'i hesaplamak için bir <math>H</math> [[kriptografik özet fonksiyonu]]nu kullanın, buradaki | notasyonu birleştirmeyi ({{dil|en|concatenation}}) gösterir. <math>c</math>, <math>n</math> değerinden küçük bir tam sayı olmalıdır.
# <math>c</math>'yi Rabin tarafından şifrelenmiş bir değer olarak ele alın ve özel anahtarı <math>(p, q)</math> kullanarak şifresini çözmeye çalışın. Bu, olağan şekilde dört <math>r_1, r_2, r_3, r_4</math> sonucunu üretecektir.
# Her bir <math>r_i</math> şifrelemenin <math>c</math> üreteceği beklenebilir. Ancak, bu yalnızca <math>c</math> bir [[kuadratik kalıntı]] mod <math>p</math> ve <math>q</math> olursa doğru olacaktır. Durumun böyle olup olmadığını belirlemek için, ilk şifre çözme sonucunu <math>r_1</math> şifreleyin. <math>c</math> olarak şifrelemezse, bu algoritmayı yeni bir rastgele <math>u</math> ile tekrarlayın. Uygun bir <math>c</math> bulmadan önce bu algoritmanın tekrarlanması gereken beklenen tekrar sayısı 4'tür.
# <math>c</math> olarak şifreleyen bir <math>r_1</math> bulduktan sonra, imza <math>(r_1, u)</math> olur.

===İmzanın doğrulanması===
<math>m</math> mesajı için bir <math>(r, u)</math> imzası, <math>n</math> genel anahtarı kullanılarak aşağıdaki gibi doğrulanabilir.

# <math>c = H(m|u)</math>'yi hesapla.
# <math>r</math>'yi <math>n</math> ortak/açık anahtarını kullanarak şifrele. 
# İmza, ancak ve ancak <math>r</math> şifrelemesinin <math>c</math>'ye eşit olması durumunda geçerlidir.

==Algoritmanın değerlendirilmesi==

===Etkinlik===
Şifre çözme, doğru sonuca ek olarak üç yanlış sonuç üretir, böylece doğru sonucun tahmin edilmesi gerekir. Bu, Rabin şifreleme sisteminin en büyük dezavantajıdır ve yaygın pratik kullanım bulmasını engelleyen faktörlerden biridir.

Düz metnin bir metin mesajını temsil etmesi amaçlanıyorsa, tahmin etmek zor değildir; bununla birlikte, eğer düz metin sayısal bir değeri temsil etmeyi amaçlıyorsa, bu konu, bir tür belirsizliği giderme şemasıyla çözülmesi gereken bir problem haline gelir. Bu problemi ortadan kaldırmak için özel yapılara sahip düz metinler seçmek veya [[Doldurma (kriptografi)|dolgu]] eklemek mümkündür. Tersine çevirmenin belirsizliğini ortadan kaldırmanın bir yolu Blum ve Williams tarafından önerilmiştir: kullanılan iki [[asal sayı]], 3 modül 4 ile uyumlu asal sayılarla sınırlandırılmıştır ve kare alma alanı, ikinci dereceden kalıntılar kümesiyle sınırlandırılmıştır. Bu kısıtlamalar, kare alma fonksiyonunu bir [[tuzak kapı fonksiyonu|tuzak kapı]] [[permütasyon]]una dönüştürerek belirsizliği ortadan kaldırır.<ref>[[Shafi Goldwasser]] and [[Mihir Bellare]] [http://cseweb.ucsd.edu/~mihir/papers/gb.html "Lecture Notes on Cryptography"] {{Webarşiv|url=https://web.archive.org/web/20120421084751/http://cseweb.ucsd.edu/~mihir/papers/gb.html|tarih=21 Nisan 2012}}. Summer course on cryptography, MIT, 1996-2001</ref>

===Verimlilik===
Şifreleme için bir kare modül n hesaplanmalıdır. Bu, en az bir küpün hesaplanmasını gerektiren [[RSA (şifreleme yönetimi)|RSA]]'dan daha verimlidir.

Şifre çözme için, iki modüler üsle birlikte [[Çin kalan teoremi]] uygulanır. Burada verimlilik RSA ile karşılaştırılabilir.

Belirsizliği giderme, ek hesaplama maliyetleri getirir ve Rabin şifreleme sisteminin yaygın pratik kullanım bulmasını engelleyen şeydir.{{cn|date=Temmuz 2019}}

===Güvenlik===
Rabin ile şifrelenmiş bir değerin şifresini çözen herhangi bir algoritmanın <math>n</math> modülünü çarpanlara ayırmak için kullanılabileceği kanıtlanmıştır. Bu nedenle, Rabin şifre çözme en az tam sayı çarpanlarına ayırma problemi kadar zordur, bu RSA için kanıtlanmamış bir şeydir. Genellikle çarpanlara ayırma için polinom-zaman algoritması olmadığına inanılır, bu da özel anahtar <math>(p, q)</math> olmadan Rabin ile şifrelenmiş bir değerin şifresini çözmek için verimli bir algoritma olmadığı anlamına gelir.

Rabin şifreleme sistemi, şifreleme süreci [[deterministik]] olduğu için seçilen düz metin saldırılarına karşı ayırt edilemezlik sağlamaz. Bir şifreli metin ve bir aday mesaj verilen bir rakip, şifreli metnin aday mesajı kodlayıp kodlamadığını kolayca belirleyebilir (sadece aday mesajı şifrelemenin verilen şifreli metni verip vermediğini kontrol ederek).

Rabin şifreleme sistemi, seçilen bir şifreli metin saldırısına karşı güvensizdir (sorgulama mesajları, mesaj uzayından homojen bir biçimde rastgele seçilse bile).<ref name=stinson/>{{rp|150}} Fazlalıklar, örneğin son 64 bitin tekrarı eklenerek, sistem tek bir kök üretmek için yapılmıştır. Bu, seçilen şifreli metin saldırısını engeller, çünkü şifre çözme algoritması yalnızca saldırganın zaten bildiği kökü üretir. Eğer bu teknik uygulanırsa, çarpanlara ayırma problemi ile denkliğin ispatı başarısız olur, bu yüzden bu varyantın güvenli olup olmadığı 2004 itibarıyla belirsizdir. Menezes, Oorschot ve Vanstone tarafından hazırlanan ''Handbook of Applied Cryptography'',<ref>{{kaynak|url=http://cacr.uwaterloo.ca/hac/|yazar1=Alfred J. Menezes|yazar2=Paul C. van Oorschot|yazar3=Scott A. Vanstone|isbn=0-8493-8523-7|yayıncı=CRC Press|özgünyıl=1996|basım=5|yıl=2001|ay=Ağustos|başlık=Handbook of Applied Cryptography|erişimtarihi=14 Mart 2020|arşivurl=https://web.archive.org/web/20210203194011/https://cacr.uwaterloo.ca/hac/|arşivtarihi=3 Şubat 2021|ölüurl=hayır}}</ref> köklerin bulunması iki parçalı bir süreç olduğu sürece (1. <math>\bmod{p}</math> ve <math>\bmod{q}</math> kökleri ve 2. Çin kalan teoreminin uygulaması) bu eşdeğerliğin muhtemel olduğunu düşünmektedir.

==Notlar==
{{Kaynakça}}

==Ayrıca bakınız==
* [[Kriptografi konuları]]
* [[Blum Blum Shub]]
* [[Shanks–Tonelli algoritması]]
* [[Schmidt-Samoa Şifreleme|Schmidt-Samoa şifreleme sistemi]]
* [[Blum-Goldwasser şifreleme sistemi]]

== Kaynakça ==
* {{kaynak|yazar=Buchmann, Johannes|başlık=Einführung in die Kryptographie|dil=Almanca|basım=2.|yer=Berlin|yayıncı=Springer|yıl=2001|isbn=3-540-41283-2}}
* {{kaynak|yazar=Rabin, Michael|url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf|başlık=Digitalized Signatures and Public-Key Functions as Intractable as Factorization|biçim=PDF|yayıncı=MIT Bilgisayar Bilimi Laboratuvarı|ay=Ocak|yıl=1979|erişimtarihi=14 Mart 2020|arşivurl=https://web.archive.org/web/20100712010627/http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-212.pdf|arşivtarihi=12 Temmuz 2010|ölüurl=hayır}}
* {{kaynak|yazar=Scott Lindhurst|başlık=An analysis of Shank's algorithm for computing square roots in finite fields|editörler=R. Gupta & K. S. Williams|konferans=Proc. 5th Conf. Can. Nr. Theo. Assoc.|yıl=1999|cilt=19|çalışma=CRM Proc. & Lec. Notes|yayıncı=AMS|ay=Ağustos}}
* {{kaynak|yazar1=R. Kumanduri|yazar2=C. Romero|çalışma=Number Theory w/ Computer Applications|kısım=Alg 9.2.9|yayıncı=Prentice Hall|yıl=1997|başlık=İkinci dereceden bir kalan modülasının kare kökü için bir olasılık}}

== Dış bağlantılar ==
* {{kaynak|url=http://cacr.uwaterloo.ca/hac/|yazar1=Alfred J. Menezes|yazar2=Paul C. van Oorschot|yazar3=Scott A. Vanstone|isbn=0-8493-8523-7|yayıncı=CRC Press|özgünyıl=1996|basım=5.|yıl=2001|ay=Ağustos|başlık=Handbook of Applied Cryptography|biçim=PDF|kısım=Bölüm 8|erişimtarihi=14 Mart 2020|arşivurl=https://web.archive.org/web/20210203194011/https://cacr.uwaterloo.ca/hac/|arşivtarihi=3 Şubat 2021|ölüurl=hayır}}

{{Açık anahtarlı şifreleme}}

{{Otorite kontrolü}}

[[Kategori:Elektronik ticaret]]
[[Kategori:Kriptografik algoritmalar]]
[[Kategori:Açık anahtarlı şifreleme programları]]