RSA Algoritması

RSA, güvenliği tam sayıları çarpanlarına ayrımanın algoritmik zorluğuna dayanan bir tür Açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

Tarihi

Birleşik Krallık haberalma teşkilatı GCHQ’da çalışan İngiliz matematikçi Clifford Cocks 1973’te kurum içi bir dökümanda eşdeğer bir sistemi açıkladı. Fakat bu sistemi hayata geçirmek için epeyce pahalı bilgisayarların kullanılması gerekiyordu ve bilindiği kadarıyla hiç kullanılmadı. Fakat Cocks’un buluşu 1998’e kadar çok gizli olduğu gerekçesiyle açığa çıkarılmadı. Rivest, Shamir ve Adleman RSA yöntemini Cocks’un çalışmasından bağımsız olarak tasarladılar.
RSA algoritması 1978’de MIT’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından açıklandı. RSA harfleri soyisimlerinin baş harflerini temsil etmektedir.

İşlemler

RSA algoritması anahtar üretimi, şifreleme ve şifre çözme olmak üzere 3 basamaktan oluşmaktadır.

Şifreleme

Alice ortak anahtarı (, )’yi Bob’a gönderir, özel anahtarını gizli tutar. Bob  mesajını Alice’e göndermek istediği zaman ilk olarak ’yi ters çevrilebilir bir protokol ile (dolgu şeması)  olacak şekilde bir  tamsayısına dönüştürür. Daha sonra şifrelenmiş mesaj ’yi  olacak şekilde hesaplar. Bunu karesini alarak üs alma yöntemiyle hızlı bir şekilde hesaplayabilir. Bob ’yi Alice’e iletir.

Şifre Çözme

Alice  mesajını özel anahtarı olan ’yi kullanarak şifreli mesaj ’den şu şekilde hesaplar:
Alice ’yi bulduktan sonra dolgu şemasının tersini alarak orijinal mesaj ’yi elde eder.

Dolgu Şemaları

Tüm bu problemleri ortadan kaldırmak için kullanılan RSA uygulamaları şifrelemeden önce düz mesaj olan ’ye rastsallaştırılmış dolgu uygularlar. Bu dolgu ’yi güvensiz düz metin aralığında olmaktan korur ve ’in sabit bir şifreli mesajı olmasını engeller. Dolgulama için tasarlanan PKCS#1 standardının ilk versiyonlarının adaptif seçilmiş şifreli mesaj atağına karşı dayanıksızlığı ortaya çıkınca sonraki versiyonlar bu atağı engellemek için OAEP içermekteler.

Mesaj İmzalama

RSA ayrıca mesajları imzalamak için de kullanılabilir. Alice’in Bob’a imzalanmış bir mesaj göndermek istediğini düşünelim. Alice kendi özel anahtarını kullanarak bunu gerçekleştirebilir. Mesajın özet değerini hesaplayıp mod ’de  kuvvetini alır ve imza olarak mesaja iliştirir. Bob mesajı aldığı zaman aynı özetleme algoritmasıyla mesajın özetini hesaplar. Bob ayrıca mesajın imzasının mod ’de  kuvvetini alır ve mesajın özetiyle karşılaştırır. Eğer iki değer birbirine eşitse mesajın Alice’den geldiğini anlar. RSA ile imza gerçekleştrilirken de RSA-PSS gibi güvenli dolgu şemaları kullanımlası gereklidir. Ayrıca güvenlik açısında şifrelemede ve imzada aynı anahtar kullanılmamalıdır.

RSA algoritması

RSA çok büyük tam sayılarla işlem yapmanın zorluğuna dayanan bir tekniktir. Yani, RSA algoritmasını kullanan kişi 2 büyük asal sayı seçer ve bunları saklar. Bu iki asal sayının çarpımı elde edip, random seçtiği başka bir değer ile birlikte ortak anahtar olarak belirler. Ortak anahtarı kullanan başka bir kullanıcı şifreleme yapabilir bu durumda bu mesajın şifresinin çözülüp anlamlı hale getirilebilmesi için ortak anahtar yeterince büyük olduğundan bu büyük sayının ortak çarpanlarının bilinmesi gerekir. Yani aslında RSA çarpanlara ayırma ile birebir ilişkilidir ki bu algoritma açık anahtarlı şifrelemeyi kullanır. Açık anahtarlı şifrelemede (asimetrik şifreleme) açık anahtarla şifreleme ve gizli anahtarla deşifreleme yapılmasını kolayca gerçekleştirilirken; yalnızca açık anahtarı (iki sayının çarpımını ) bilerek gizli anahtarın bulunmasını zor kılar (büyük olan bu sayının çarpanlarının bilinmesi gerekir). RSA 3 basamakta gerçekleştirilir. Bunlar: anahtar üretimi (2 büyük asal sayının çarpımı ve random seçilmiş bir sayı ile ortak anahtar üretilmesi), şifreleme (Oluşan ortak anahtarı kullanan başka bir kullanıcı şifreleme yapabilir) ve şifre çözmedir (Şifrenin çözülmesi için ortak anahtarın çarpanlarının bilinmesi gerekir). Özet olarak; tamamen random olarak ve birbirine yakın iki asal sayı seçilir. Bu sayılar tutulur. Mod n olacak şekilde ; n=p*q ve m(=(p-1)*(q-1) çarpımları hesaplanır. 1<e<m arasında bir e tamsayısı seçilir. Öyle ki e ve m’nin en büyük ortak böleni 1 olsun. Genel üs olarak kullandığımız e ve m sayıları kullanılarak gizli üs d hesaplanır (1<d<m) (Örneğin ed≡1(mod m)). Genel anahtar (n,e) ve özel anahtar (n,d)’dir. p,q ve m değerleri de gizli tutulmalıdır. .NET framework teknolojisinde kullanan RSA algoritmasına bakacak olursak:

   byte[] dataToEncrypt = ByteConverter.GetBytes("Sifrelenecek Veri");
Şifrelenmiş ve deşifrelenmiş olan verilerin tutulduğu veri tanımları yapılır.

   byte[] encryptedData;
   byte[] decryptedData;
1024 uzunluğunda RSACryptoServiceProvider sınıfından nesne üretilir.

   RSACryptoServiceProvider RSAalg = new RSACryptoServiceProvider(1024);
Aşağıdaki RSAEncrypt metodu veriyi şifrelemeyi sağlar. Metottaki ilk parametre şifrelenecek veridir. Byte array şeklindedir. Metottaki ikinci parametre (RSAalg.ExportParameters(false)) anahtar bilgisinin dışa verilip verilmeyeceğini ifade eder. False olarak değer atanmışsa public anahtar dışa verilir, true olarak değer atanmışsa public ve private anahtarlar dışa verilir. Kodumuzda false olarak değer atandığı için sadece public anahtar dışa verilir. Metottaki üçüncü parametre boolean bir değerdir. Padding mode olarak isimlendirilir. Padding boolean değerinin kullanılması gereklidir çünkü metoda gönderilen verinin şifrelenecek verinin tamamının olup olmadığını bu flag değerinden anlarız. Şifrelenecek veri çok büyük boyutlarda olabilir bu da verinin bloklara bölünmesini gerektirir. Bloklara bölünen verinin tamamının şifrelendiği bu flag değerden anlaşılır. Eğer padding değeri true ise bu halde gelişmiş OAEP 16 kullanılır. Aksi takdirde geleneksel PKCS 1 v1.5 kullanılır.

   encryptedData = RSAEncrypt(dataToEncrypt,RSAalg.ExportParameters(false), false);
Aşağıdaki decryptedData metodu veriyi deşifrelemeye sağlar. Metottaki ilk parametre deşifrelenecek veridir. Byte array şeklindedir. Metottaki ikinci parametre (RSAalg.ExportParameters(true))anahtar bilgisinin dışa verilip verilmeyeceğini ifade eder. False olarak değer atanmışsa public anahtar dışa verilir, true olarak değer atanmışsa public ve private anahtarlar dışa verilir. Kodumuzda true olarak değer atandığı için private ve public anahtar dışa verilir. Metottaki üçüncü parametre boolean bir değerdir. Padding mode olarak isimlendirilir. Padding boolean değerinin kullanılması gereklidir çünkü metoda gönderilen verinin şifrelenecek verinin tamamının olup olmadığını bu flag değerinden anlarız. Şifrelenecek veri çok büyük boyutlarda olabilir bu da verinin bloklara bölünmesini gerektirir. Bloklara bölünen verinin tamamının şifrelendiği bu flag değerden anlaşılır. Eğer padding değeri true ise bu halde gelişmiş OAEP 16 kullanılır. Aksi takdirde geleneksel PKCS 1 v1.5 kullanılır.

   decryptedData = RSADecrypt(encryptedData,RSAalg.ExportParameters(true), false);