Rabin şifreleme sistemi

Rabin şifreleme sistemi, Rabin kriptoloji veya Rabin kriptosistemi, güvenliği 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. 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.

Algoritma Ocak 1979'da Michael O. Rabin tarafından yayınlandı. Rabin şifreleme sistemi, şifreli metinden düz metni kurtarmanın çarpanlara ayırma kadar zor olduğu kanıtlanabilen ilk asimetrik şifreleme sistemiydi.

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.

İki tane çok büyük ve farklı , asal sayıları seçilir. Kare kökün hesaplanmasını basitleştirmek için bir tanesini yöntemi ile seçebiliriz. Fakat yöntem herhangi daha büyük asal sayılarla çalışır.

Bizim basit örneğimizde bizim düz metin uzayımızdır. Biz 'yi bizim düz metnimiz olarak alacağız. Bu yüzden şifreli metin, 'dir. Açıkça ’nin 4 farklı değeri için, şifreli metin 15 üretilir. Bu Rabin algoritması tarafından üretilen çoğu şifreli metinler için geçerlidir.

ve '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 , böylece her aynı değere (15) şifreler.

Rabin şifreleme sistemi, dijital imza'lar oluşturmak ve doğrulamak için kullanılabilir. İmza oluşturmak için özel anahtarı gerekir. Bir imzanın doğrulanması için ortak anahtarı gerekir.

'i hesaplamak için bir kriptografik özet fonksiyonunu kullanın, buradaki | notasyonu birleştirmeyi () gösterir. , değerinden küçük bir tam sayı olmalıdır.

'yi Rabin tarafından şifrelenmiş bir değer olarak ele alın ve özel anahtarı kullanarak şifresini çözmeye çalışın. Bu, olağan şekilde dört sonucunu üretecektir.

Her bir şifrelemenin üreteceği beklenebilir. Ancak, bu yalnızca bir kuadratik kalıntı mod ve olursa doğru olacaktır. Durumun böyle olup olmadığını belirlemek için, ilk şifre çözme sonucunu şifreleyin. olarak şifrelemezse, bu algoritmayı yeni bir rastgele ile tekrarlayın. Uygun bir bulmadan önce bu algoritmanın tekrarlanması gereken beklenen tekrar sayısı 4'tür.

Ş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 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ı permütasyonuna dönüştürerek belirsizliği ortadan kaldırır.

Rabin ile şifrelenmiş bir değerin şifresini çözen herhangi bir algoritmanın 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 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). 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, köklerin bulunması iki parçalı bir süreç olduğu sürece (1. ve kökleri ve 2. Çin kalan teoreminin uygulaması) bu eşdeğerliğin muhtemel olduğunu düşünmektedir.