Rabin Şifreleme

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Rabin şifreleme sistemi, Rabin kriptoloji veya Rabin kriptosistemi, asitmetrik şifreleme tekniğidir. Güvenliği RSA ya benzemektedir. Büyük sayıların çarpmanın zorluğuna dayanan kriptosistemlerdir. Bununla birlikte RSA problemi için kriptosistemin doğru olduğu şu anda kanıtlanamamış tamsayıları çarpma zorluğu Rabin kriptosistemler için kanıtlanmıştır. Rabin fonksiyonunun her bir çıktısı herhangi mümkün 4 girdi tarafından üretilebilmesinden dolayı bir dez avantaja sahiptir. Eğer her bir çıktı bir şifreli metin ise, extra bir karmaşıklık 4 mümkün girdiden düz metin için doğru olanı seçmemiz gerektiğinden Rabin kriptosistemlerde mevcuttur.

TARİH[değiştir | kaynağı değiştir]

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.

ANAHTAR ÜRETİMİ[değiştir | kaynağı değiştir]

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ğıda ki gibidir: ---iki tane çok büyük ve farklı p , 'q asalsayıları seçilir. kare kökün hesaplanmasını basitleştirmek için bir tanesini p \equiv q \equiv 3 \pmod{4} yöntemi ile seçebiliriz. fakat yöntem herhengi bir asal sayıyla çalışır.

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 ‘ ninp q çarpanları gereklidir.

Bir örnek olarak eğer p = 7 and q = 11, o zaman 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)

ŞİFRELEME[değiştir | kaynağı değiştir]

Ş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.

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

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 P = \{ 0, \dots, 76 \} bizim düzmetin uzayımızdır. Biz m = 20 yi bizim düz metnimiz olarak alacağız.bu yüzden şifreli metin c = m^2 \, \bmod \, n = 400 \, \bmod \, 77 = 15. Açıkça m nin 4 farklı değeri 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.

DEŞİFRELEME[değiştir | kaynağı değiştir]

Şifrelimetini çözmek için özel anahtarlar gerekir. Süreç aşağıdaki gibidir. Eğer c ve r bilinirse düz metin m^2 \equiv c\pmod{r} ile 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 tamsayı 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 n = p \cdot q 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

:m_p = \sqrt{c} \, \bmod \, p

ve

:m_q = \sqrt{c} \, \bmod \, q

Hesaplanılmış olmalıdır. Bizim örneğimizde m_p = 1 ve m_q = 9. alalım Genişletilmiş Eöklidian Algoritması uygulanarak biz y_p ve y_q yu bulmak isteyelim.

 y_p \cdot p + y_q \cdot q = 1.  ile  bulunur.ve bizim örneğimizde   y_p = -3 and y_q = 2 bulunur.

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

\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 kare köklerin bir tanesi \mod \, n orijinal düzmetin m dir. Bizim örneğimizde m \in \{ 64, \mathbf{20}, 13, 57 \} dir.

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

:ya \gcd(|r-s|,n) = p ya \gcd(|r-s|,n) = q, where \gcd means Greatest common divisor.
gcd en büyük ortak bölen anlamına gelir.

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

\gcd(57-13,77) = \gcd(44,77) = 11 = q

KARE KÖKLERİN HESAPLANMASI[değiştir | kaynağı değiştir]

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

m_p = c^{\frac{(p+1)}{4}} \, \bmod \, p

and

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.ilk (p+1)/4 ün , p \equiv 3\!\!\!\pmod{4} bir tamsayı 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:

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},

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

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

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

m_p^2 \equiv c \pmod{p}.

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.

ALGORİTMANIN GELİŞİMİ[değiştir | kaynağı değiştir]

ETKİLİLİĞİ[değiştir | kaynağı değiştir]

Çözme aşaması bir doğru sonuca ek 3 yanlış sonuç üretir.Bu yüzden doğru sonucun tahmin edilmesi gereklidir.bu Rabin kripto sistemin ana dez avantajıdır.ve geniş alanda pratik kullanımda yaygınlaşmasını önleyen faktörlerden bir tanesi bu dez avantajıdır.

Eğer düz meitn metin mesajını gösterebilmek için girintili başlarsa, tahmin etmek hiç zor olmayacaktır Ancak eğer düz metin sayısal bir değeri göstermeye niyetlenilmişse , bu bazı belirsiz şemaların çözülmesi problemini beraberinde getirir. Belirli yapılarla düzmetni seçmek mümkündür ya da ekleme yaparak bu problemin üstesinden gelinilebilir. Tersine yapının belirsizliğini ortadan kaldırmanın bir yöntemi Blum ve Williams tarafından prtaya atılmıştır. 2 kullanılan iki asal sayı mod 3 ve mod 4 e eşleşik asal sayılara ayrılır ve karenin alanı kuadratik kalanların kümesine ayrılır. Bu ayrımlar belirsizliği eler

VERİMLİLİĞİ[değiştir | kaynağı değiştir]

Şifreleme için, kare mod n hesaplanılmış olmalıdır. Bu en azından kübik hesaplama gerektiren RSA dan daha etkindir.

Deşifreleme için çin kalan teoremi 2 moduler üssellerle birlikte uygulanır. Burada de verimliliği yine RSA nın ki ile karşılaştırılabilir.

GÜVENLİĞİ[değiştir | kaynağı değiştir]

Rabin kripto sistemin büyük avantajı rasgele bir düz metni ancak ancak n açık anahtarını çarpanlarına ayırabilen bir hasım tarafından şifreli metinden tümüyle elde edilebilmesinin kolay olmamasıdır. Bu güvenlik seviyesinin en düşüğüdür. Rabin kriptosistemin genişletilmesi güvenliği daha da sağlamlaştırmıştır.

Rabin kriptosistemin çözülmesi tamsayıları çarpanlara ayırma probleminin çözümüne eş olduğu kanıtlanmıştır. Bu da Rabin i RSA dan daha farklı kılar. Bu yüzden Rabin sistemi Rsa dan daha güvenlidir. Ve çarpanalra ayırma problemi için bir çözüm keşfedilene kadar böyle kalacaktır. (bu düzmetnin kolayca çözecek belirli bir yapıyla oluşturulmadığını varsayar.)

Çünkü çarpanlara ayırma problemine bir çözüm birçok farklı yönlerde araştırılmıştır. Herhangi bir çözüm (NSA gibi araştırma organizasyonu dışında sınıflanan) tüm bilimsel topluluğa çabucak ulaşacaktır. Bununla birlikte bir çözüm gelmesi uzundur ve çarpanlara ayırma problemi pratik olarak bir çözüm bulunamamıştır. Bu gibi bir avantajı olmadan bir saldırgan bugün kodu çözecek şansa sahip olamayacaktır. Bu kriptosistem seçilmiş düz metin ataklarına karşı kanıtlanmış güvenilirdir.

Bununla birlikte aktif bir saldırgan sistemi seçilmiş şifreli metin ataklarını kullanarak kırabilir bu da matematiksel olarak kanıtlanılabilirdir.

Fazlalıkları ekleyerek mesala son 64 bitin tekrarıyla sisteme tek bir kök ürettirilebilir. Bu seçilmiş şifreli metin saldırganını engeller çünkü çözme algoritması sadece saldırganın çoktan bildiği kökleri üretir. Eğer bu teknik uygulanırsa, çarpanlara ayırma probleminin zorluğuna eşdeğerlik kanıtı başarısızı oluru bu yüzden 2004'ten beri belirsiz kalmıştırHandbook of Applied Cryptography kitabında bu kanıtlanılabilir eşitlik göz önüne alınmıştır

Kaynaklar[değiştir | kaynağı değiştir]

İngilizce Wikipedia

Dış bağlantılar[değiştir | kaynağı değiştir]