Rabin şifreleme sistemi

Süreç Michael O. Rabin tarafından Ocak 1979'da yayınlandı. Rabin kriptosistemi asal sayıların çarpımı kadar zorluğu kanıtlanmış, şifreli metinden tüm düz metni kapsayan ilk kriptosistemdi.

Tüm asimetrik kriptosistemlerle birlikte, Rabin sistemi de hem açık anahtar hem de özel anahtar kullanır. Açık anahtar daha sonraki şifrelemeler için gereklidir. Özel anahtar ise sadece mesajın alıcısı tarafından sahip olunulmalıdır.

Kesin anahtar üretimi süreci aşağıdaki gibidir: ---iki tane çok büyük ve farklı p , 'q asalsayıları seçilir. Karekökün hesaplanmasını basitleştirmek için bir tanesini ${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$ yöntemi ile seçebiliriz. Fakat yöntem herhangi bir asal sayıyla çalışır.

${\displaystyle n=p\cdot q}$. Olsun. Burada  n açık anahtardır. Asal sayılar p ve q  özel anahtarlardır.

Mesajı şifrelemek için sadece açık anahtar n gereklidir. Şifreli metni deşifrelemek için n ‘ nin p q çarpanları gereklidir.

Bir örnek olarak eğer ${\displaystyle p=7}$ and ${\displaystyle q=11}$, o zaman ${\displaystyle n=77}$ olur. Açık anahtar 77 paylaşılır ve mesaj 77 kullanılarak şifrelenir. Mesajı çözmek için özel anahtarlar 7 ve 11 bilinmek zorundadır. (Elbette burada anahtarların seçimi kötüdür. 77'nin çarpanlarına ayrılması basittir gerçek örneklerde daha büyük sayılar kullanılır.)

Şifreleme için, sadece açık anahtar n kullanılır, bu yüzden düz metnin haricinde bir şifreli metin üretilmiş olur. Süreç aşağıdaki gibidir.

${\displaystyle P=\{0,\dots ,n-1\}}$ düz metin uzayımız oldun (sayılar içeriyor) ve ${\displaystyle m\in P}$ ve düz metin olsun. Şimdi ${\displaystyle c}$ şifreli metnimiz :

${\displaystyle c=m^{2}\,{\bmod {\,}}n}$. ile belirlenir.

Yani c , n anahtar sayısının moduna göre düz metnin karesinin kuadratik kalanıdır. Bizim basit örneğimizde ${\displaystyle P=\{0,\dots ,76\}}$ bizim düzmetin uzayımızdır. Biz ${\displaystyle m=20}$ yi bizim düz metnimiz olarak alacağız. Bu yüzden şifreli metin ${\displaystyle c=m^{2}\,{\bmod {\,}}n=400\,{\bmod {\,}}77=15}$. Açıkça m nin 4 farklı değeri ${\displaystyle m\in \{13,20,57,64\}}$ için, şifreli metin 15 üretilir. Bu Rabin algoritması tarafından üretilen çoğu şifrelimetinler için geçerlidir.

Şifrelemeyi çözmek için özel anahtarlar gerekir. Süreç aşağıdaki gibidir. Eğer c ve r bilinirse düz metin ${\displaystyle m^{2}\equiv c{\pmod {r}}}$ ile ${\displaystyle m\in \{0,\dots ,n-1\}}$ olacaktır. r bir kompozit sayıdır kompozit sayı asal olmayan herhangi bir pozitif sayıdan daha büyük pozitif sayı demektir. Eğer N >0 bir tam sayı ise ve N=a*b gibi 1<a,b,<N sayısı var ise o zaman N kompozit sayı demektir.(yani Rabin algoritmasının ${\displaystyle n=p\cdot q<nowiki>}$</nowiki> formülüne benzer ) m yi bulmak için bilinen daha etkili bir method yoktur. Eğer asalsa (Rabin algoritmasındaki p ve q gibi )çin kalan teoremi m nin çözümü için başvurulabilecek bir metodtur. Bu yüzden kare kökler

:${\displaystyle m_{p}={\sqrt {c}}\,{\bmod {\,}}p}$

ve

:${\displaystyle m_{q}={\sqrt {c}}\,{\bmod {\,}}q}$

Hesaplanılmış olmalıdır. Bizim örneğimizde ${\displaystyle m_{p}=1}$ ve ${\displaystyle m_{q}=9}$. alalım Genişletilmiş Öklid Algoritması uygulanarak biz ${\displaystyle y_{p}}$ ve ${\displaystyle y_{q}}$ yu bulmak isteyelim.

 ${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$.  ile  bulunur.ve bizim örneğimizde   ${\displaystyle y_{p}=-3}$ and ${\displaystyle y_{q}=2}$ bulunur.

Şimdi, çin kalan teoreminin çağırılmasıyla ${\displaystyle c+n\mathbb {Z} \in \mathbb {Z} /n\mathbb {Z} }$ ve c nin 4 kare kökü (${\displaystyle \mathbb {Z} /n\mathbb {Z} }$hesaplanılır. {0,....n-1} ${\displaystyle \{0,\dots ,n-1\}}$: içindeki 4 kare kök :

${\displaystyle {\begin{matrix}r&=&(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-r&=&n-r\\s&=&(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-s&=&n-s\end{matrix}}}$

dir.

Bu kareköklerin bir tanesi ${\displaystyle \mod \,n}$ orijinal düzmetin m dir. Bizim örneğimizde ${\displaystyle m\in \{64,\mathbf {20} ,13,57\}}$ dir.

Rabin kendi makalesinde eğer bir kişi hem ${\displaystyle r}$ hem de ${\displaystyle s}$ yi hesaplayabilirse o zaman ${\displaystyle n}$ nin çarpanlarınıda hesaplayabileceğini bize şöyle gösteriyor

:ya ${\displaystyle \gcd(|r-s|,n)=p}$ ya ${\displaystyle \gcd(|r-s|,n)=q}$, where ${\displaystyle \gcd }$ means Greatest common divisor.

gcd en büyük ortak bölen anlamına gelir.

Çünkü eğer sen ${\displaystyle r}$ ve ${\displaystyle s}$ yi biliyorsan, en büyük ortak bölen ${\displaystyle n}$ nin çarpanlarını bulmak için etkili bir hesaplama yöntemidir bizim örneğimizde ( ${\displaystyle 57}$ ve ${\displaystyle 13}$ ü ${\displaystyle r}$ ve ${\displaystyle s}$ olarak alalım):

${\displaystyle \gcd(57-13,77)=\gcd(44,77)=11=q}$

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

${\displaystyle m_{p}=c^{\frac {(p+1)}{4}}\,{\bmod {\,}}p}$

and

${\displaystyle m_{q}=c^{\frac {(q+1)}{4}}\,{\bmod {\,}}q}$.

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

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

${\displaystyle \left({c \over p}\right)}$ Legendre symbolü dür.

${\displaystyle c\equiv m^{2}{\pmod {pq}}}$ den  aşağıdaki gibi 
${\displaystyle c\equiv m^{2}{\pmod {p}}}$.  Hesaplanılır.

Bu yüzden c , modul p nin kuadratik kalanıdır. Bu yüzden ${\displaystyle \left({c \over p}\right)=1}$dir ve

${\displaystyle m_{p}^{2}\equiv c{\pmod {p}}.}$

${\displaystyle p\equiv 3{\pmod {4}}}$ ilişkisi bir gereksinim değildir. Çünkü kare kökler in diğer asal sayılarla modulude hesaplanılabilir.

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

• Buchmann, Johannes. Einführung in die Kryptographie. İkinci Baskı. Berlin: Springer, 2001. 3-540-41283-2
• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, Ekim 1996. 0-8493-8523-7
• Rabin, Michael. Digitalized Signatures and Public-Key Functions as Intractable as Factorization (in PDF). MIT Bilgisayar Bilimi Laboratuvarı, Ocak 1979.
• Scott Lindhurst, An analysis of Shank's algorithm for computing square roots in finite fields. in R Gupta and K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, Ağustos 1999.
• R Kumanduri and C Romero, Number Theory w/ Computer Applications, Alg 9.2.9, Prentice Hall, 1997. İkinci dereceden bir kalan modülasının kare kökü için bir olasılık.

• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography ( PDF), Bölüm 8