Şifreleme ve Deşifreleme
RSA`da hem şifreleme hem de deşifreleme, tamsayıların tamsayı kuvvetlerini almayı ve mod alma işlemlerini gerektirir. Eğer ilk önce tamsayıların üslerini alıp, daha sonra mod n ile indirgersek, ara değerler devasa büyüklükte sayılar olurlar. Neyse ki bu sorunu bir nebze azaltmak için modüler aritmetiğin şu özelliğinden yararlanabiliriz:
Bu sayede, ara değerleri modül n`e göre indirgeyebiliriz. Bu da hesaplamayı pratik hale getirir.
Diğer bir husus, üssün verimidir. Çünkü, RSA ile, potansiyel olarak büyük üsler ile işlem yaparız. Verimin nekadar artabiliceğini görmek için, `yı hesaplamak istediğimizi varsayalım. Dürüst bir yöntem 15 çarpım gerektirir:
Bununla birlikte, aynı sonuca, her bir kısmi sonucun karesini alarak olacak şekilde dört adımda da ulaşabiliriz.
Daha genel olarak varsayalım ki biz değerini hesaplamak istiyoruz ve biliyoruz ki a ve m birer pozitif tam sayı. Eğer biz m`i gibi ***lik sayı gibi ifade edecek olursak:
Böylece,
olur.
Bu sonuç sayesinde, işlemini hesaplamak üzere aşağıdaki algoritmayı geliştirebiliriz. Ve algoritmanın altındaki tablo da algoritmanın çalışmasını örneklemektedir. c değerinin aslında gerekli olmadığını düşünebilirsiniz; gerçekten de algoritma içerisinde direk bir fonksiyonu yoktur. Fakat son değeri üssün değerine eşit olacağından dolayı açıklayıcı bir niteliktedir.
c<-0; d<-1
for i<-k downto 0
do c<-2 x c
d<-(d x d)mod n
if bi=1
then c<-c+1
d<-(d x a)mod n
return d
__________________
RSA`da hem şifreleme hem de deşifreleme, tamsayıların tamsayı kuvvetlerini almayı ve mod alma işlemlerini gerektirir. Eğer ilk önce tamsayıların üslerini alıp, daha sonra mod n ile indirgersek, ara değerler devasa büyüklükte sayılar olurlar. Neyse ki bu sorunu bir nebze azaltmak için modüler aritmetiğin şu özelliğinden yararlanabiliriz:
Bu sayede, ara değerleri modül n`e göre indirgeyebiliriz. Bu da hesaplamayı pratik hale getirir.
Diğer bir husus, üssün verimidir. Çünkü, RSA ile, potansiyel olarak büyük üsler ile işlem yaparız. Verimin nekadar artabiliceğini görmek için, `yı hesaplamak istediğimizi varsayalım. Dürüst bir yöntem 15 çarpım gerektirir:
Bununla birlikte, aynı sonuca, her bir kısmi sonucun karesini alarak olacak şekilde dört adımda da ulaşabiliriz.
Daha genel olarak varsayalım ki biz değerini hesaplamak istiyoruz ve biliyoruz ki a ve m birer pozitif tam sayı. Eğer biz m`i gibi ***lik sayı gibi ifade edecek olursak:
Böylece,
olur.
Bu sonuç sayesinde, işlemini hesaplamak üzere aşağıdaki algoritmayı geliştirebiliriz. Ve algoritmanın altındaki tablo da algoritmanın çalışmasını örneklemektedir. c değerinin aslında gerekli olmadığını düşünebilirsiniz; gerçekten de algoritma içerisinde direk bir fonksiyonu yoktur. Fakat son değeri üssün değerine eşit olacağından dolayı açıklayıcı bir niteliktedir.
c<-0; d<-1
for i<-k downto 0
do c<-2 x c
d<-(d x d)mod n
if bi=1
then c<-c+1
d<-(d x a)mod n
return d
__________________