şifrelemede asal sayıların kullanımı

Dönem ödevinden:


Bu public/private key çiftini üretmek için özel bir algoritma kullanılır. Bu algoritma ilk kez Amerikalı üç bilim adamı tarafından 1977 yılında geliştirimiştir ve ismini bu üç kişinin baş harflerinden almıştır RSA. Rivest, Shamir, Adleman. (Her ne kadar İngilizler ikici dünya savaşı yıllarında bu tip te bir yöntem keşfettiklerini ve bu yöntemi güvenlik amacıyla kimseye söylemedikleri belirtseler bile RSA yöntem olarak ilk kabul edilmiştir.)

RSA mantık olarak şöyle çalışır.
Tamamiyle asal sayılar üzerinde hareket eder..
Önce bir adet asal sayı seçilir ve buna p sayısı denir. Sonra bir tane daha asal sayı seçilir ve bunada q denir.

p = 3
q = 11 (3 ve 11 asal sayıdır dimi?)

Daha sonra bir adet bu iki sayının çarpımından oluşan N sayısı oluşturulur.
N = (p * q)
N = (3 * 11)
N = 33

Bu N sayısı Modulus olarak kabul edilir. Ve hem public hemde private key in bir parçasını oluşturur.

Daha sonra bir a sayısı oluşturulur ve bu a sayısı p değerinin bir eksiği ve q değerinin bir eksiniğinin çarpımından oluşur.

a = (p -1 ) * (q -1)
a = (3 -1 ) * (11 – 1)
a = 2 * 10
a = 20
sayısı elde edilir.


Daha sonra bir e sayısı oluşturulur ve bu e sayısı a ile herhangi bir ortak böleni olmayan bir sayı olmalıdır.
e = 7 (denebilir)
7 sayısının 20 ile ortak böleni yoktur.

Bu oluşturulan e ve N sayılar public key dir (e Exponent (yani üs) N modulus (yani mod alınacak sayı)

Daha sonra private key i oluşturmak için bir adet d sayısı üretilir ve bu d sayısı e sayısı ile çarpılıp a sayısı ile mod landığında kalanı 1 verecek şekilde bir sayı olmalıdır.

d = ? * e mod a => 1 sonucunda olmadır

bunun matematik teki yazımı şöyledir. d * e = 1 mod a, yani

d * 7 = 1 mod 20
d = 3 sonucu bulunur
çünkü 3 * 7 = 21 mod 20 de 1 sonucunu verir.

Oluşturulan bu d sayısı ile N sayısı da private key dir (d Exponent, N modulus)

Yukarıdaki örnek devam ettirilirse Bob’un kendi adına public ve private key lerini oluşturduğunu fazedelim
Bob un key çifti :
Public key : e = 7 ve N = 33
Private key : d = 3 ve N = 33

Bob oluşturduğu bu keylerden private key i çok iyi bi şekilde saklar. Ve public key i Alice’ e yollar. Alice bu bu public key ile mesajı şu şekilde şifreler. Diyelimki ‘A’ karakterini şifreleyip göndermek istiyor. ‘A’ harfine karşılık gelen herhangibi sayı oluşturur (burada ascii kodları kullanılabilir)

A harfinin sayısal değerini 16 olarak seçelim. 16 sayısını public key de bulunan e sayısı ile üs alır ve N sayısı ile de çıkan sonucun mod unu alır. Yani
X = 16 ^ 7 mod 33
X = 268435456 mod 33
X = 25

16 sayısını (ayni A harfini) 25 sayısına çevirerek Bob’a yollar.

Bob’da almış oluduğu bu 25 sayısını d ile üs alıp, N ile modlar

X = 25 ^ 3 mod 33
X = 15625 mod 33
X = 16 ya geri çevirir. (yani A)

Görüldüğü gibi Alice 16 sayısını şifreleyip 25 e çevirmişti. Bob’da 25 sayısını çözüp 16 sayısına geri çevirdi.

(Burade belirtilen örnekte şifrelemek için 33 sayısına eşit yada büyük bir sayı kullanılmamalıdır. Neden?)

Asimetrik şifreleme metodunun iki güvenliği vardır. Birincisi secret-key yönteminde olduğu gibi gizli bir veriyi karşı tarafa yollmak gerekli değildir. İkisinciside şifrenin çözülmesi için gerekli olan ihtimal sayısı çok fazladır.
Asimetrik bir algoritmanın çözülmesi için gerekli olan, p ve q sayılarının bulunmasıdır. p ve q sayıları bilinen (ve herkese açık olan) public key içerisindeki N sayısından bulunabilir. (nasıl?)
Burada belirttiğimiz örnekte sayıları hesaplayabilelim diye çok küçük asal sayılar seçtik 3 ve 11 gibi. Ancak bu şifreleme metodunda kullanılan sayılar oldukça büyüktür.
128 bitlik şifrelemede ortalama 45 haneli asal sayılar kullanılmaktadır. N sayısını oluşturmak için 45 haneli iki sayının çarpımı bulunmalıdır.
128bit lik bir şifrenin çözülmesi için ihtimal sayısı 2 üzeri 128 dir. Ve bu kadar ihtimal normal bir bilgisayar ile ortalama 2 trilyon yılda çözülür. (Saniyete 1 trilyon işlem yapabilen 1 milyon dolarlık süper bilgisayarlarla bu süre 1190 yıl dır)
Japonyada 64bit bir şifre yaklaşık 100.000 (yüzbin) bilgisayarın paralel bağlanarak ortak çalışması sonucunda yaklaşık 3,5 yılda çözülmüştür.
Bügün internet üzerinde SSL ile kurulu sayfalarda 128bit lik şifreleme kullanılır. (sizin kredi kartı bilgilerinizin korunması için) ve her zaman şifrelemede verinin geçerlilik süresi çözülme süresinden az ise güvendesiniz demektir.
Yani SSL kullanılan bir sayfada şifrelenerek yollanan kredi kartı bilgileriniz 1190 yıldan fazla süre yürürlükte kalmayacağı için 1190 yıl sonra çözülmüş olmasının bir mahzuru yoktur. Özel şifreleme programları ile 4096 bitlik (PGP Corporation - Hard Disk Encryption, File Encryption, Secure ftp Server, Hard Drive Encryption, Enterprise Data Protection - PGP Corporation) şifreleme yapılabilir bu şekilde gerçekleştirilmiş bir şifrenin çözülme ihtimali 2 üzeri 4096 yani yaklaşık olarak 10 üzeri 500 dür. Bu sayının büyüklüğünü anlamak için şöyle bir örnek verilebilir. Dünyada bilinen atom sayısı 10 üzeri 70 dir.

Yazının devamı burada. ve burada