Rabin şifreleme sistemi

bullvar_katip · 28 Mayıs 2024

Rabin şifreleme sistemi, Rabin kriptoloji veya Rabin kriptosistemi, güvenliği RSA'daki gibi tam sayı çarpanlarına ayırmanın zorluğu üzerine kurgulanmış olan asimetrik bir kriptografik tekniktir. Bununla birlikte, Rabin kriptosisteminin avantajı, saldırgan tam sayıları verimli bir şekilde çarpanlarına ayıramadığı sürece, seçilmiş bir düz metin saldırısına karşı hesaplama açısından güvenli olduğu matematiksel olarak kanıtlanmıştır, oysa RSA için bilinen böyle bir kanıt yoktur. Rabin fonksiyonunun her çıktısının dört olası girdiden herhangi biri tarafından üretilebilmesi dezavantajı; her çıktı bir şifreli metinse, olası dört girdiden hangisinin gerçek düz metin olduğunu belirlemek için şifre çözmede ekstra karmaşıklık gerekir. Tarihçe Algoritma Ocak 1979'da Michael O. Rabin tarafından yayınlandı. Rabin şifreleme sistemi, şifreli metinden düz metni kurtarmanın çarpanlara ayırma kadar zor olduğu kanıtlanabilen ilk asimetrik şifreleme sistemiydi. Şifreleme algoritması Tüm asimetrik şifreleme sistemleri gibi, Rabin şifreleme sistemi de bir anahtar çifti kullanır: şifreleme için genel anahtar ve şifre çözme için özel anahtar. Genel anahtar, herkesin kullanması için yayınlanırken, özel anahtar yalnızca mesajın alıcısı tarafından bilinir. Anahtar üretimi Rabin şifreleme sisteminin anahtarları şu şekilde oluşturulur: İki tane çok büyük ve farklı , asal sayıları seçilir. Kare kökün hesaplanmasını basitleştirmek için bir tanesini yöntemi ile seçebiliriz. Fakat yöntem herhangi daha büyük asal sayılarla çalışır. hesaplanır. Burada açık anahtar, asal sayılardan oluşan ise özel anahtardır. Şifreleme Bir mesajı, önce tersine çevrilebilir bir eşleme kullanılarak sayısına dönüştürülerek ve ardından hesaplanarak şifrelenebilir. Şifreli metin, 'dir. Şifre çözme mesajı, şifreli metninden karekök modül 'si aşağıdaki gibi alınarak elde edilebilir. Aşağıdaki formülleri kullanarak modül ve 'nun karekökünü hesaplayın; olacak şekilde ve 'i bulmak için Genişletilmiş Öklid algoritması kullanın. modül 'nin dört karekökünü bulmak için Çin kalan teoremi'ni kullanın: Bu dört değerden biri orijinal düz metin 'dir, ancak dördünden hangisinin doğru olduğu ek bilgi olmadan belirlenemez. Kesin anahtar üretimi süreci aşağıdaki gibidir: Karekökleri hesaplama Yukarıdaki 1. adımdaki formüllerin aslında 'in kareköklerini aşağıdaki gibi ürettiğini gösterebiliriz. İlk formül için, olduğunu kanıtlamak istiyoruz. olduğundan, üssü bir tam sayıdır. ise ispat önemsizdir, bu nedenle 'nin 'yi bölmediğini varsayabiliriz. ögesinin anlamına geldiğini unutmayın, dolayısıyla modül 'ye göre bir kuadratik kalıntıdır (rezidü). Buradan; yazılabilir. Son adım Euler ölçütü tarafından doğrulanır. Deşifreleme şifreli metninin kare köklerini hesaplamak için mod asal sayı ve 'yu gerektirir. ve olur. Biz bu metodun için çalışmasını aşağıdaki gibi gösterebiliriz. İlk 'ün, bir tam sayı olduğunu gösterir. için varsayım basittir. Bu yüzden biz 'nin 'ye bölünmediğini varsayabiliriz. O zaman: Legendre sembolüdür. 'dan aşağıdaki gibi olarak hesaplanır. Bu yüzden , modül 'nin kuadratik kalanıdır. Buradan; ve elde edilir. ilişkisi bir gereksinim değildir. Çünkü kare kökler in diğer asal sayılarla modülü de hesaplanabilir. Rabin kare köklerin asal sayılarla modlarını bulmak için Berlekamp algoritmasının özel bir durumunu kullanmayı önerir. Örnek Örnek olarak, ve olarak alalım, ardından olur (Elbette burada anahtarların seçimi kötüdür. 77'nin çarpanlarına ayrılması basittir gerçek örneklerde çok çok daha büyük sayılar kullanılır). Düz metnimiz olarak alalım. Şifreli metin bu şekilde olarak elde edilir. Bizim basit örneğimizde bizim düz metin uzayımızdır. Biz 'yi bizim düz metnimiz olarak alacağız. Bu yüzden şifreli metin, 'dir. Açıkça ’nin 4 farklı değeri için, şifreli metin 15 üretilir. Bu Rabin algoritması tarafından üretilen çoğu şifreli metinler için geçerlidir. Şifre çözme işlemi şu şekilde ilerler: ve hesaplanır. ve 'yi hesaplamak için genişletilmiş Öklid algoritması kullanılır. olduğunu doğrulayabiliriz. Dört düz metin adayını hesaplayın: ve 'in istenen düz metin olduğunu görüyoruz. Dört adayın hepsinin 15 mod 77'nin karekökleri olduğuna dikkat edin. Yani, her aday için , böylece her aynı değere (15) şifreler. Eğer ve bilinirse düz metin ile olacaktır. bir kompozit sayıdır kompozit sayı asal olmayan herhangi bir pozitif sayıdan daha büyük pozitif sayı demektir. Eğer bir tam sayı ise ve gibi sayısı var ise o zaman kompozit sayı demektir (yani Rabin algoritmasının formülüne benzer). 'yi bulmak için bilinen daha etkili bir metot yoktur. Eğer asal ise (Rabin algoritmasındaki ve gibi) Çin kalan teoremi 'nin çözümü için başvurulabilecek bir metottur. Bu yüzden kare kökler; ve hesaplanmış olmalıdır. Bizim örneğimizde ve alalım, Genişletilmiş Öklid Algoritması uygulanarak biz ve 'yu bulmak isteyelim. ile bulunur. Bizim örneğimizde ve bulunur. Şimdi, Çin kalan teoremi yardımıyla, 'nin dört karekökü , , ve şeklinde hesaplanır (burada , uyum sınıfları halkası [ring of congruence classes] anlamına gelir.) 4 kare kök kümesi içindedir: 'dir. Bu kare köklerin bir tanesi orijinal düz metin ’dir. Bizim örneğimizde 'dir. Rabin kendi makalesinde eğer bir kişi hem hem de 'yi hesaplayabilirse o zaman 'nin çarpanlarını da hesaplayabileceğini bize şöyle gösteriyor; ya ya , burada (Greatest Common Divisor) yani en büyük ortak bölen (EBOB) anlamına gelir. Çünkü eğer bir kişi ve 'yi biliyorsa, en büyük ortak bölen 'nin çarpanlarını bulmak için etkili bir hesaplama yöntemidir bizim örneğimizde ( ve 'ü ve olarak alalım): bulunur. Dijital İmza Algoritması Rabin şifreleme sistemi, dijital imza'lar oluşturmak ve doğrulamak için kullanılabilir. İmza oluşturmak için özel anahtarı gerekir. Bir imzanın doğrulanması için ortak anahtarı gerekir. İmzalama Bir mesajı, bir özel anahtar ile aşağıdaki gibi imzalanabilir. Rastgele bir değeri oluşturun. 'i hesaplamak için bir kriptografik özet fonksiyonunu kullanın, buradaki | notasyonu birleştirmeyi gösterir. , değerinden küçük bir tam sayı olmalıdır. 'yi Rabin tarafından şifrelenmiş bir değer olarak ele alın ve özel anahtarı kullanarak şifresini çözmeye çalışın. Bu, olağan şekilde dört sonucunu üretecektir. Her bir şifrelemenin üreteceği beklenebilir. Ancak, bu yalnızca bir kuadratik kalıntı mod ve olursa doğru olacaktır. Durumun böyle olup olmadığını belirlemek için, ilk şifre çözme sonucunu şifreleyin. olarak şifrelemezse, bu algoritmayı yeni bir rastgele ile tekrarlayın. Uygun bir bulmadan önce bu algoritmanın tekrarlanması gereken beklenen tekrar sayısı 4'tür. olarak şifreleyen bir bulduktan sonra, imza olur. İmzanın doğrulanması mesajı için bir imzası, genel anahtarı kullanılarak aşağıdaki gibi doğrulanabilir. 'yi hesapla. 'yi ortak/açık anahtarını kullanarak şifrele. İmza, ancak ve ancak şifrelemesinin 'ye eşit olması durumunda geçerlidir. Algoritmanın değerlendirilmesi Etkinlik Şifre çözme, doğru sonuca ek olarak üç yanlış sonuç üretir, böylece doğru sonucun tahmin edilmesi gerekir. Bu, Rabin şifreleme sisteminin en büyük dezavantajıdır ve yaygın pratik kullanım bulmasını engelleyen faktörlerden biridir. Düz metnin bir metin mesajını temsil etmesi amaçlanıyorsa, tahmin etmek zor değildir; bununla birlikte, eğer düz metin sayısal bir değeri temsil etmeyi amaçlıyorsa, bu konu, bir tür belirsizliği giderme şemasıyla çözülmesi gereken bir problem haline gelir. Bu problemi ortadan kaldırmak için özel yapılara sahip düz metinler seçmek veya dolgu eklemek mümkündür. Tersine çevirmenin belirsizliğini ortadan kaldırmanın bir yolu Blum ve Williams tarafından önerilmiştir: kullanılan iki asal sayı, 3 modül 4 ile uyumlu asal sayılarla sınırlandırılmıştır ve kare alma alanı, ikinci dereceden kalıntılar kümesiyle sınırlandırılmıştır. Bu kısıtlamalar, kare alma fonksiyonunu bir tuzak kapı permütasyonuna dönüştürerek belirsizliği ortadan kaldırır. Verimlilik Şifreleme için bir kare modül n hesaplanmalıdır. Bu, en az bir küpün hesaplanmasını gerektiren RSA'dan daha verimlidir. Şifre çözme için, iki modüler üsle birlikte Çin kalan teoremi uygulanır. Burada verimlilik RSA ile karşılaştırılabilir. Belirsizliği giderme, ek hesaplama maliyetleri getirir ve Rabin şifreleme sisteminin yaygın pratik kullanım bulmasını engelleyen şeydir. Güvenlik Rabin ile şifrelenmiş bir değerin şifresini çözen herhangi bir algoritmanın modülünü çarpanlara ayırmak için kullanılabileceği kanıtlanmıştır. Bu nedenle, Rabin şifre çözme en az tam sayı çarpanlarına ayırma problemi kadar zordur, bu RSA için kanıtlanmamış bir şeydir. Genellikle çarpanlara ayırma için polinom-zaman algoritması olmadığına inanılır, bu da özel anahtar olmadan Rabin ile şifrelenmiş bir değerin şifresini çözmek için verimli bir algoritma olmadığı anlamına gelir. Rabin şifreleme sistemi, şifreleme süreci deterministik olduğu için seçilen düz metin saldırılarına karşı ayırt edilemezlik sağlamaz. Bir şifreli metin ve bir aday mesaj verilen bir rakip, şifreli metnin aday mesajı kodlayıp kodlamadığını kolayca belirleyebilir (sadece aday mesajı şifrelemenin verilen şifreli metni verip vermediğini kontrol ederek). Rabin şifreleme sistemi, seçilen bir şifreli metin saldırısına karşı güvensizdir (sorgulama mesajları, mesaj uzayından homojen bir biçimde rastgele seçilse bile). Fazlalıklar, örneğin son 64 bitin tekrarı eklenerek, sistem tek bir kök üretmek için yapılmıştır. Bu, seçilen şifreli metin saldırısını engeller, çünkü şifre çözme algoritması yalnızca saldırganın zaten bildiği kökü üretir. Eğer bu teknik uygulanırsa, çarpanlara ayırma problemi ile denkliğin ispatı başarısız olur, bu yüzden bu varyantın güvenli olup olmadığı 2004 itibarıyla belirsizdir. Menezes, Oorschot ve Vanstone tarafından hazırlanan Handbook of Applied Cryptography, köklerin bulunması iki parçalı bir süreç olduğu sürece (1. ve kökleri ve 2. Çin kalan teoreminin uygulaması) bu eşdeğerliğin muhtemel olduğunu düşünmektedir. Notlar Ayrıca bakınız Kriptografi konuları Blum Blum Shub Shanks–Tonelli algoritması Schmidt-Samoa şifreleme sistemi Blum-Goldwasser şifreleme sistemi Kaynakça Dış bağlantılar Kategori:Elektronik ticaret Kategori:Kriptografik algoritmalar Kategori:Açık anahtarlı şifreleme programları

Ara

Ara

Foruma hoş geldin 👋, Ziyaretçi

Rabin şifreleme sistemi

bullvar_katip

Administrator

Benzer konular

Tema özelleştirme sistemi

Tam ekran yada dar ekran

Izgara yada normal mod

Forum arkaplan resimleri

Sidebar blogunu kapat/aç

Yapışkan sidebar kapat/aç

Radius aç/kapat

Foruma hoş geldin 👋, Ziyaretçi