Rabin şifreleme sistemi

TARİH

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İ

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  yöntemi ile seçebiliriz. Fakat yöntem herhengi bir asal sayıyla çalışır.
. 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  and , o zaman  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.)

ETKİLİLİĞİ

Çö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 dezavantajıdır ve geniş alanda pratik kullanımda yaygınlaşmasını önleyen faktörlerden bir tanesi bu dezavantajıdır.
Eğer düz 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 ortaya atılmıştır. 2 kullanılan iki asal sayı mod 3 ve mod 4 e eşlenik 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İĞİ

Ş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 kalan teorem 2 moduler üssellerle birlikte uygulanır. Burada da verimliliği yine RSA'nın ki ile karşılaştırılabilir.

GÜVENLİĞİ

Rabin kripto sisteminin büyük avantajı rastgele bir düz metni 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 tam sayı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 çarpanlara 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 mesela 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ır. Handbook of Applied Cryptography kitabında bu kanıtlanılabilir eşitlik göz önüne alınmıştır.