Rabin DEŞİFRELEME

iGrand · 26 Kas 2013

Şifrelimetini çözmek için özel anahtarlar gerekir. Süreç aşağıdaki gibidir. Eğer c ve r bilinirse düz metin

$96418a67c1f1d2f3cf8d847cac67f03d.png$

ile

$8b28c7379417eb38cb76443d207b755a.png$

olacaktır. r bir kompozit sayıdır kompozit sayı asal olmayan her hangi 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

$e023301f320ad0c340b12420b36aeaf0.png$

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
:

$794c92cfa3a810ba6d2c454a4d3f5171.png$

ve
:

$7a31cf40558307da0e008e8b68c99863.png$

Hesaplanılmış olmalıdır. Bizim örneğimizde

$85590cc8bee7c478e5eb6798872b4e6a.png$

ve

$db2f9c8f64ef0914f3c5fd65ce3b1e9f.png$

. alalım Genişletilmiş Eöklidian Algoritması uygulanarak biz

$2e430ef3a43a811857e21bfe31520fad.png$

ve

$efbfa3f1fec1304f7f3d1fab110a955f.png$

yu bulmak isteyelim.

$0bf5153d6da5c825710debb1f081e4bc.png$

. ile bulunur.ve bizim örneğimizde

$16473ff1fd89b98c9b29db133e6625d6.png$

and

$4d68330e62f05926daf8045a9767adb3.png$

bulunur.
Şimdi, çin kalan teoreminin çağırılmasıyla

$cc589c234f2b8484cd918967b6bb8b1c.png$

ve c nin 4 kare kökü (

$69f05b89f802c55ca2ee8cf803e6e487.png$

hesaplanılır. {0,....n-1}

$3b12c071d94d139bc9a69726e1681527.png$

: içindeki 4 kare kök :

$0ad1f78851f2e809401c3a59fbcb1418.png$

Dir. Bu kare köklerin bir tanesi

$acd14c60077fab314e322e3a710064ef.png$

orjinal düzmetin m dir. Bizim örneğimizde

$6fef64dfc66bb31fd315ffdc27ba006c.png$

dir.
Rabin kendi makalesinde eğer bir kişi hem

$4b43b0aee35624cd95b910189b3dc231.png$

hemde

$03c7c0ace395d80182db07ae2c30f034.png$

yi hesaplayabilirse o zaman

$7b8b965ad4bca0e41ab51de7b31363a1.png$

nin çarpanlarınıda hesaplayabileceğini bize şöyle gösteriyor
:ya

$5d53d3e57914de8d99cde9ab031bb698.png$

ya

$51c9adc0ced8b7d75336ff3a116f94c2.png$

, where

$3bc5b65929eb880c1f6b47030dfa5704.png$

means Greatest common divisor.
gcd en büyük ortak bölen anlamına gelir.

Çünkü eğer sen

$4b43b0aee35624cd95b910189b3dc231.png$

ve

$03c7c0ace395d80182db07ae2c30f034.png$

yi biliyorsan ,en büyük ortak bölen

$7b8b965ad4bca0e41ab51de7b31363a1.png$

nin çarpanlarını bulmak için etkili bir hesaplama yöntemidir bizim örneğimizde (

$72b32a1f754ba1c09b3695e0cb6cde7f.png$

ve

$c51ce410c124a10e0db5e4b97fc2af39.png$

ü

$4b43b0aee35624cd95b910189b3dc231.png$

ve

$03c7c0ace395d80182db07ae2c30f034.png$

olarak alalım):

$d4ca12cef03274e3881d8cd83cb2554b.png$

Rabin DEŞİFRELEME

iGrand

Level 19

Şu an konuyu görüntüleyenler (Toplam : 0, Üye: 0, Misafir: 0)

Benzer konular