Rabin şifreleme sistemi - Rabin cryptosystem

Rabin şifreleme sistemi asimetrik kriptografik teknik, kimin güvenliği, bunun gibi RSA, zorluk derecesi ile ilgilidir tamsayı çarpanlara ayırma. Bununla birlikte, Rabin şifreleme sisteminin, RSA için bilinen böyle bir kanıt yokken, saldırgan tam sayıları etkili bir şekilde çarpanlara 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ış olma avantajına sahiptir.^[1]^:145 Rabin işlevinin her çıktısının olası dört girdiden herhangi biri tarafından üretilebilmesi dezavantajına sahiptir; her çıktı bir şifreli metin ise, dört olası girdiden hangisinin gerçek düz metin olduğunu belirlemek için şifre çözmede ekstra karmaşıklık gerekir.

Tarih

Algoritma, Ocak 1979'da Michael O. Rabin.^[2] Rabin şifreleme sistemi, şifreli metinden şifresiz metni kurtarmanın faktoring kadar zor olduğu kanıtlanabilen ilk asimetrik şifreleme sistemiydi.

Şifreleme algoritması

Tüm asimetrik şifreleme sistemleri gibi, Rabin sistemi de bir anahtar çifti kullanır: Genel anahtar şifreleme ve bir Özel anahtar şifre çözme için. Genel anahtar herkesin kullanması için yayınlanırken, özel anahtar yalnızca mesajın alıcısı tarafından bilinmeye devam eder.

Anahtar oluşturma

Rabin şifreleme sisteminin anahtarları şu şekilde oluşturulur:

İki büyük farklı seçin asal sayılar ${ displaystyle p}$ ve ${ displaystyle q}$ öyle ki ${ displaystyle p eşdeğeri 3 { bmod {4}}}$ ve ${ displaystyle q eşdeğeri 3 { bmod {4}}}$ .
Hesaplama ${ displaystyle n = pq}$ .

Sonra ${ displaystyle n}$ açık anahtar ve çift ${ displaystyle (p, q)}$ özel anahtardır.

Şifreleme

Bir mesaj ${ displaystyle M}$ önce bir sayıya dönüştürülerek şifrelenebilir ${ displaystyle m$ tersine çevrilebilir bir eşleme kullanarak, ardından hesaplama ${ displaystyle c = m ^ {2} { bmod {n}}}$ . Şifreli metin ${ displaystyle c}$ .

Şifre çözme

Mesaj ${ displaystyle m}$ şifreli metinden kurtarılabilir ${ displaystyle c}$ karekök modülünü alarak ${ displaystyle n}$ aşağıdaki gibi.

Karekökünü hesapla ${ displaystyle c}$ modulo ${ displaystyle p}$ ve ${ displaystyle q}$ bu formülleri kullanarak:
${ displaystyle { begin {align} m_ {p} & = c ^ {{ frac {1} {4}} (p + 1)} { bmod {p}} m_ {q} & = c ^ {{ frac {1} {4}} (q + 1)} { bmod {q}} end {hizalı}}}$
Kullan genişletilmiş Öklid algoritması bulmak ${ displaystyle y_ {p}}$ ve ${ displaystyle y_ {q}}$ öyle ki ${ displaystyle y_ {p} cdot p + y_ {q} cdot q = 1}$ .
Kullan Çin kalıntı teoremi dört karekök bulmak ${ displaystyle c}$ modulo ${ displaystyle n}$ :
${ displaystyle { begin {align} r_ {1} & = left (y_ {p} cdot p cdot m_ {q} + y_ {q} cdot q cdot m_ {p} sağ) { bmod {n}} r_ {2} & = n-r_ {1} r_ {3} & = left (y_ {p} cdot p cdot m_ {q} -y_ {q} cdot q cdot m_ {p} sağ) { bmod {n}} r_ {4} & = n-r_ {3} end {hizalı}}}$

Bu dört değerden biri orijinal düz metindir ${ displaystyle m}$ dördünden hangisinin doğru olduğu ek bilgi olmadan belirlenemez.

Karekökleri hesaplama

Yukarıdaki 1. adımdaki formüllerin aslında kareköklerini ürettiğini gösterebiliriz. ${ displaystyle c}$ aşağıdaki gibi. İlk formül için bunu kanıtlamak istiyoruz ${ displaystyle m_ {p} ^ {2} equiv c { bmod {p}}}$ . Dan beri ${ displaystyle p eşdeğeri 3 { bmod {4}},}$ üs ${ textstyle { frac {1} {4}} (p + 1)}$ bir tamsayıdır. Kanıt önemsizdir eğer ${ displaystyle c eşdeğeri 0 { bmod {p}}}$ bu yüzden bunu varsayabiliriz ${ displaystyle p}$ bölünmez ${ displaystyle c}$ . Bunu not et ${ displaystyle c eşdeğeri m ^ {2} { bmod {pq}}}$ ima ediyor ki ${ displaystyle c eşdeğeri m ^ {2} { bmod {p}}}$ yani c a ikinci dereceden kalıntı modulo ${ displaystyle p}$ . Sonra

{ displaystyle m_ {p} ^ {2} equiv c ^ {{ frac {1} {2}} (p + 1)} equiv c cdot c ^ {{ frac {1} {2}} (p-1)} equiv c cdot 1 mod p}

Son adım, Euler'in kriteri.

Misal

Örnek olarak ${ displaystyle p = 7}$ ve ${ displaystyle q = 11}$ , sonra ${ displaystyle n = 77}$ . Al ${ displaystyle m = 20}$ bizim düz metnimiz olarak. Şifreli metin bu nedenle ${ displaystyle c = m ^ {2} { bmod {n}} = 400 { bmod {77}} = 15}$ .

Şifre çözme şu şekilde ilerler:

Hesaplama ${ displaystyle m_ {p} = c ^ {{ frac {1} {4}} (p + 1)} { bmod {p}} = 15 ^ {2} { bmod {7}} = 1}$ ve ${ displaystyle m_ {q} = c ^ {{ frac {1} {4}} (q + 1)} { bmod {q}} = 15 ^ {3} { bmod {11}} = 9}$ .
Hesaplamak için genişletilmiş Öklid algoritmasını kullanın ${ displaystyle y_ {p} = - 3}$ ve ${ displaystyle y_ {q} = 2}$ . Bunu teyit edebiliriz ${ displaystyle y_ {p} cdot p + y_ {q} cdot q = (- 3 cdot 7) + (2 cdot 11) = 1}$ .
Dört düz metin adayını hesaplayın:
${ displaystyle { begin {align} r_ {1} & = (- 3 cdot 7 cdot 9 + 2 cdot 11 cdot 1) { bmod {77}} = 64 r_ {2} & = 77-64 = 13 r_ {3} & = (- 3 cdot 7 cdot 9-2 cdot 11 cdot 1) { bmod {77}} = mathbf {20} r_ {4} & = 77-20 = 57 end {hizalı}}}$

ve bunu görüyoruz ${ displaystyle r_ {3}}$ istenen düz metindir. Dört adayın hepsinin 15 mod 77'nin karekökleri olduğuna dikkat edin. Yani, her aday için, ${ displaystyle r_ {i} ^ {2} { bmod {77}} = 15}$ yani her biri ${ displaystyle r_ {i}}$ aynı değere şifreler, 15.

Dijital İmza Algoritması

Rabin şifreleme sistemi oluşturmak ve doğrulamak için kullanılabilir dijital imzalar. İmza oluşturmak için özel anahtar gerekir ${ displaystyle (p, q)}$ . Bir imzayı doğrulamak için genel anahtar gerekir ${ displaystyle n}$ .

İmzalama

Bir mesaj ${ displaystyle m$ özel bir anahtarla imzalanabilir ${ displaystyle (p, q)}$ aşağıdaki gibi.

Rastgele bir değer oluşturun ${ displaystyle u}$ .
Kullanın kriptografik karma işlevi ${ displaystyle H}$ hesaplamak ${ displaystyle c = H (m | u)}$ , çubuğun birleştirmeyi gösterdiği yer. ${ displaystyle c}$ şundan küçük bir tamsayı olmalıdır ${ displaystyle n}$ .
Tedavi etmek ${ displaystyle c}$ Rabin ile şifrelenmiş bir değer olarak ve özel anahtarı kullanarak şifresini çözmeye çalışın ${ displaystyle (p, q)}$ . Bu, olağan dört sonucu üretecektir, ${ displaystyle r_ {1}, r_ {2}, r_ {3}, r_ {4}}$ .
Her birinin şifrelenmesi beklenebilir ${ displaystyle r_ {i}}$ üretecekti ${ displaystyle c}$ . Ancak, bu yalnızca ${ displaystyle c}$ olur ikinci dereceden kalıntı modulo ${ displaystyle p}$ ve ${ displaystyle q}$ . Durumun böyle olup olmadığını belirlemek için ilk şifre çözme sonucunu şifreleyin ${ displaystyle r_ {1}}$ . Şifrelemiyorsa ${ displaystyle c}$ , bu algoritmayı yeni bir rastgele ${ displaystyle u}$ . Uygun bir algoritma bulmadan önce bu algoritmanın beklenen tekrarlanma sayısı ${ displaystyle c}$ 4'tür.
Bir ${ displaystyle r_ {1}}$ hangisine şifreler ${ displaystyle c}$ , imza ${ displaystyle (r_ {1}, u)}$ .

Bir imzayı doğrulama

Bir imza ${ displaystyle (r, u)}$ bir mesaj için ${ displaystyle m}$ genel anahtar kullanılarak doğrulanabilir ${ displaystyle n}$ aşağıdaki gibi.

Hesaplama ${ displaystyle c = H (m | u)}$ .
Şifrele ${ displaystyle r}$ genel anahtarı kullanmak ${ displaystyle n}$ .
İmza, yalnızca ve ancak şifreleme ${ displaystyle r}$ eşittir ${ displaystyle c}$ .

Algoritmanın değerlendirilmesi

Etkililik

Ş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ı ve yaygın pratik kullanım bulmasını engelleyen faktörlerden biridir.

Düz metin bir metin mesajını temsil etmek için tasarlanmışsa, tahmin etmek zor değildir; ancak düz metnin sayısal bir değeri temsil etmesi amaçlanmışsa, bu sorun bir tür belirsizliği giderme şeması ile çözülmesi gereken bir sorun haline gelir. Özel yapılara sahip düz metinler seçmek veya eklemek mümkündür dolgu malzemesi, bu sorunu ortadan kaldırmak için. Ters çevirmenin belirsizliğini ortadan kaldırmanın bir yolu Blum ve Williams tarafından önerilmiştir: kullanılan iki asal 3 modulo 4 ile uyumlu astarlar ile sınırlandırılmıştır ve karenin alanı ikinci dereceden kalıntılar kümesiyle sınırlıdır. Bu kısıtlamalar, kareleme işlevini bir tuzak kapısı permütasyon belirsizliği ortadan kaldırarak.^[3]

Verimlilik

Şifreleme için kare modulo n hesaplanmalıdır. Bu daha etkilidir RSA, en az bir küpün hesaplanmasını gerektirir.

Şifre çözme için, Çin kalıntı teoremi iki ile birlikte uygulanır modüler üsler. Burada verimlilik RSA ile karşılaştırılabilir.

Netleştirme, ek hesaplama maliyetleri getirir ve Rabin şifreleme sisteminin yaygın pratik kullanım bulmasını engelleyen şey budur.^{[kaynak belirtilmeli ]}

Güvenlik

Bir Rabin şifreli değerin şifresini çözen herhangi bir algoritmanın modülü çarpanlarına ayırmak için kullanılabileceği kanıtlanmıştır. ${ displaystyle n}$ . Bu nedenle, Rabin şifre çözme en azından tamsayı çarpanlara ayırma problemi kadar zordur, bu RSA için kanıtlanmamıştır. Genel olarak faktoring için polinom-zaman algoritmasının olmadığına inanılır, bu da Rabin şifreli bir değerin özel anahtar olmadan şifresini çözmek için etkili bir algoritma olmadığı anlamına gelir. ${ displaystyle (p, q)}$ .

Rabin şifreleme sistemi, ayırt edilemezlik karşısında seçili düz metin şifreleme süreci deterministik olduğundan saldırılar. Bir şifreli metin ve bir aday mesaj verilen bir rakip, şifreli metnin aday mesajı kodlayıp kodlamadığını kolayca belirleyebilir (basitçe aday mesajı şifrelemenin verilen şifreli metni verip vermediğini kontrol ederek).

Rabin şifreleme sistemi bir seçilen şifreli metin saldırısı (meydan okuma mesajları, mesaj alanından rastgele olarak tek tip olarak seçildiğinde bile).^[1]^:150 Örneğin son 64 bitin tekrarı gibi fazlalıklar eklenerek, sistemin tek bir kök üretmesi sağlanabilir. Bu, şifre çözme algoritması yalnızca saldırganın zaten bildiği kökü ürettiği için, bu belirli seçilmiş şifreli metin saldırısını engeller. Bu teknik uygulanırsa, çarpanlara ayırma problemiyle eşdeğerliğin ispatı başarısız olur, bu nedenle bu varyantın güvenli olup olmadığı 2004 itibariyle belirsizdir. Uygulamalı Kriptografi El Kitabı Menezes, Oorschot ve Vanstone tarafından yazılan bu eşdeğerlik, ancak köklerin bulunması iki aşamalı bir süreç olduğu sürece (1. kökler ${ displaystyle { bmod {p}}}$ ve ${ displaystyle { bmod {q}}}$ ve 2. Çin kalanı teoreminin uygulanması).

Ayrıca bakınız

Notlar

^ ^a ^b Stinson, Douglas (1995). Kriptografi: Teori ve Uygulama. CRC Press LLC.
^ Rabin, Michael (Ocak 1979). "Faktorizasyon Kadar Kontrol Edilemez Sayısal İmzalar ve Açık Anahtar Fonksiyonları" (PDF). MIT Bilgisayar Bilimleri Laboratuvarı.
^ Shafi Goldwasser ve Mihir Bellare "Kriptografi Üzerine Ders Notları". Kriptografi üzerine yaz kursu, MIT, 1996-2001

Referanslar

Buchmann, Johannes. Kryptographie'de Einführung. İkinci baskı. Berlin: Springer, 2001. ISBN 3-540-41283-2
Menezes, Alfred; van Oorschot, Paul C .; ve Vanstone, Scott A. Uygulamalı Kriptografi El Kitabı. CRC Press, Ekim 1996. ISBN 0-8493-8523-7
Rabin, Michael. Faktorizasyon Kadar Kontrol Edilemez Sayısal İmzalar ve Açık Anahtar Fonksiyonları (PDF olarak). MIT Bilgisayar Bilimleri Laboratuvarı, Ocak 1979.
Scott Lindhurst, Shank'ın sonlu alanlarda karekök hesaplama algoritmasının bir analizi. R Gupta ve K S Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, cilt 19 CRM Proc & Lec Notes, AMS, Ağustos 1999.
R Kumanduri ve C Romero, Bilgisayar Uygulamalı Sayı Teorisi, Alg 9.2.9, Prentice Hall, 1997. Kuadratik bir kalıntı modulo a asalının karekökü için bir olasılık.

Dış bağlantılar

Menezes, Oorschot, Vanstone, Scott: Uygulamalı Kriptografi El Kitabı (ücretsiz PDF indirmeleri), 8. Bölüme bakın

[stinson-1] Stinson, Douglas (1995). Kriptografi: Teori ve Uygulama. CRC Press LLC.

[2] Rabin, Michael (Ocak 1979). "Faktorizasyon Kadar Kontrol Edilemez Sayısal İmzalar ve Açık Anahtar Fonksiyonları" (PDF). MIT Bilgisayar Bilimleri Laboratuvarı.

[3] Shafi Goldwasser ve Mihir Bellare "Kriptografi Üzerine Ders Notları". Kriptografi üzerine yaz kursu, MIT, 1996-2001

[1]

[2]

[3]