RSA Algoritması

RSA, güvenliği tam sayıları çarpanlarına ayırmanı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 haber alma teşkilatı GCHQ’da çalışan İngiliz matematikçi 1973’te kurum içi bir dokü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.

Patent

MIT'e 20 Eylül 1983'te algoritmayı kullanan bir "Şifreleme iletişim sistemi ve yöntemi" için ABD Patenti 4,405,829 verildi.Patent 21 Eylül 2000'de sona erecek olsa da (patent süresi 17 yıldır), algoritma iki hafta önce 6 Eylül 2000'de RSA Security tarafından kamuya açıklandı. Algoritmanın ayrıntılı bir açıklaması Scientific American'ın Ağustos 1977 sayısında Matematik Oyunları sütununda yayınlandığından, patent başvurusunun Aralık 1977 dosyalama tarihinden önce dünyanın geri kalanının çoğunda düzenlemeler başka yerlerde ve sadece ABD patenti verildi. Cocks'un çalışmaları herkes tarafından biliniyor olsaydı, ABD'deki bir patent de yasal olmayacaktı.

'nin patent özetinden,

Sistem bir kodlama cihazına sahip en az bir terminale ve bir kod çözme cihazına sahip en az bir terminale bağlanmış bir iletişim kanalı içerir. Aktarılacak bir mesaj, önceden belirlenmiş bir kümede M sayısı olarak kodlanarak kodlama terminalindeki şifreli metne şifrelenir. Bu sayı daha sonra önceden belirlenmiş bir güce (istenen alıcı ile ilişkili) yükseltilir ve son olarak hesaplanır. Kalan veya kalıntı C, ... üssel sayı, önceden belirlenmiş iki asal sayının çarpımına (hedeflenen alıcı ile ilişkili) bölündüğünde hesaplanır.

İşlemler

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

Anahtar Üretimi

RSA için bir ortak anahtar bir de özel anahtar gerekir. Ortak anahtar herkes tarafından bilinir ve mesajı şifrelemek için kullanılır. Bir ortak anahtarla şifrelenmiş mesaj sadece özel anahtarla çözülebilir. RSA anahtarları şu şekilde oluşturulur:

1. İki adet birbirinden değişik asal sayı seçin, bunların adını da ${\displaystyle p\,}$ve ${\displaystyle q\,}$ koyalım.
   • Güvenlik amacıyla p ve q sayıları rastgele seçilmeli ve yakın uzunlukta olmalıdırlar. Bu sayılar asallık testi kullanılarak etkin bir şekilde bulunabilir.
2. ${\displaystyle n=pq\,}$ hesaplayın.
   • ${\displaystyle n\,}$ özel ve ortak anahtarlar için mod değeri olarak kullanılacaktır.
3. Bu sayıların totientı olan ${\displaystyle \varphi (n)=(p-1)(q-1)\,}$ hesaplayın.
4. Bir tam sayı üretin ve adını da ${\displaystyle e\,}$ koyun. Bu sayı, ${\displaystyle 1<e<\varphi (n)\,}$ koşuluna uygun olmalı ve ${\displaystyle \varphi (n)\,}$ ile en büyük ortak böleni 1 olmalıdır (başka bir deyişle ${\displaystyle \varphi (n)\,}$ ve ${\displaystyle e\,}$ kendi aralarında asal olmalıdır).
   • ${\displaystyle e\,}$ ortak anahtar olarak açıklanır.
   • Bit uzunluğu kısa olan ve küçük sahip ${\displaystyle e\,}$ değerleri (yaygın olarak 0x10001 = 65,537) daha verimli şifreleme sağlarlar. Fakat küçük ${\displaystyle e\,}$ değerleri (örneğin 3) bazı durumlarda güvenliği azaltabilir.
5. ${\displaystyle de\equiv 1{\pmod {\varphi (n)}}}$ olacak şekilde bir ${\displaystyle d\,}$'yi belirleyin.
   • ${\displaystyle d\,}$ özel anahtar üssü olarak saklanır.
   • ${\displaystyle d\,}$ değeri genellikle kullanılarak hesaplanır.

Ortak anahtar mod değeri olan ${\displaystyle n\,}$’den ve ortak üs olan ${\displaystyle e\,}$’den oluşur. Özel anahtar ise mod değeri olan ${\displaystyle n\,}$’den ve özel üs olan ve gizli kalması gereken ${\displaystyle d\,}$’den oluşur. (${\displaystyle p\,}$, ${\displaystyle q\,}$ ve ${\displaystyle \varphi (n)\,}$ değerleri de gizli kalmalıdır çünkü ${\displaystyle d\,}$’yi hesaplamada kullanılırlar.)

Şifreleme

Alice ortak anahtarı (${\displaystyle n\,}$, ${\displaystyle e\,}$)’yi Bob’a gönderir, özel anahtarını gizli tutar. Bob ${\displaystyle M\,}$ mesajını Alice’e göndermek istediği zaman ilk olarak ${\displaystyle M\,}$’yi ters çevrilebilir bir protokol ile (dolgu şeması) ${\displaystyle 0<m<n}$ olacak şekilde bir ${\displaystyle m\,}$ tam sayısına dönüştürür. Daha sonra şifrelenmiş mesaj ${\displaystyle c\,}$’yi ${\displaystyle c=m^{e}{\text{ (mod }}n{\text{)}}}$ olacak şekilde hesaplar. Bunu karesini alarak üs alma yöntemiyle hızlı bir şekilde hesaplayabilir. Bob ${\displaystyle c\,}$’yi Alice’e iletir.

Şifre Çözme

Alice ${\displaystyle m\,}$ mesajını özel anahtarı olan ${\displaystyle d\,}$’yi kullanarak şifreli mesaj ${\displaystyle c\,}$’den şu şekilde hesaplar:

${\displaystyle m=c^{d}{\text{ (mod }}n{\text{)}}}$

Alice ${\displaystyle m\,}$’yi bulduktan sonra dolgu şemasının tersini alarak orijinal mesaj ${\displaystyle M\,}$’yi elde eder.

Örnek

1. İki farklı asal sayı seçelim. ${\displaystyle p=61}$ ve ${\displaystyle q=53}$ olsun.
2. ${\displaystyle n=pq}$ değerini hesaplayalım. 61 × 53 = 3233.
3. Totient değerini hesaplayalım. ${\displaystyle \varphi (3233)=(61-1)(53-1)=3120}$.
4. 1 ile 3120 arasında 3120 ile aralarında asal olan bir ${\displaystyle e}$ değeri seçelim. ${\displaystyle e}$ değerini asal seçersek sadece 3120’nin böleni olup olmadığını kontrol etmemiz gerekir. ${\displaystyle e=17}$ olsun.
5. ${\displaystyle d}$’yi ${\displaystyle e}$’nin mod ${\displaystyle \varphi (n)}$’deki çarpmaya gore tersi olarak hesaplayalım. ${\displaystyle d=2753}$.

Ortak Anahtar: ${\displaystyle (n=3233,e=17)}$. Herhangi bir ${\displaystyle m}$ mesajı için şifreleme fonksiyonu ${\displaystyle m^{17}}$ (mod 3233).

Özel Anahtar: ${\displaystyle (n=3233,d=2753)}$. Herhangi bir ${\displaystyle c}$ şifreli mesajı için şifre çözme fonksiyonu ${\displaystyle c^{2753}}$ (mod 3233).

Örneğin ${\displaystyle m=65}$’i şu şekilde şifreleriz: ${\displaystyle c=65^{17}{\text{ (mod }}3233{\text{)}}=2790}$.

${\displaystyle c=2790}$’ın şu şekilde şifresini çözebiliriz: ${\displaystyle m=2790^{2753}{\text{ (mod }}3233{\text{)}}=65}$

Tüm bu hesaplamalar karesini alarak üs alma yöntemiyle hızlı bir şekilde gerçekleştirilebilir.

Düz RSA karşısındaki Saldırılar

• Küçük şifreleme üssü (örn. ${\displaystyle e\,}$ = 3) kullanıldığında şifrelenen ${\displaystyle m\,}$ mesajı da küçükse ${\displaystyle (m<n^{1/e})}$, ${\displaystyle m^{e}\,}$ değeri ${\displaystyle n\,}$’den küçük bir değere karşılık gelir. Bu durumda şifreli mesajlar tam sayılardaki ${\displaystyle e.\,}$ dereceden kökleri alınarak kolayca çözülebilirler.
• Eğer bir mesaj aynı şifreleme üssü ${\displaystyle e\,}$ ve farklı ${\displaystyle n\,}$ değerleri ile birden çok kişiye gönderiliyorsa, bu mesaj kullanılarak kolayca çözülebilir.
• RSA algoritması herhangi bir rastsallık içermediği için bazı düz mesajlar şifrelenip herhangi bir şifreli mesaja eşit olup olmadığı kontrol edilebilir. Dolayısıyla dolgu kullanılmayan RSA anlamsal güvenliğe sahip değildir.
• RSA yönteminde iki şifreli mesajın çarpımı, kendilerine karşılık gelen düz mesajların çarpımının şifrelenmiş haline eşittir. Yani, ${\displaystyle m_{1}^{e}m_{2}^{e}\equiv (m_{1}m_{2})^{e}{\text{ (mod }}n{\text{)}}.}$ Bu çarpımsal özelliğinden dolayı RSA’e seçilmiş şifreli mesaj atağı gerçekleştirilebilir. Örneğin, bir şifreli mesaj olan ${\displaystyle c=m^{e}{\text{ (mod }}n{\text{)}}}$ 'nin çözümünü elde etmek isteye bir saldırgan rastgele bir ${\displaystyle r\,}$ değeri seçip, özel anahtara sahip kişiye şüpheli gözükmeyen ${\displaystyle c'=cr^{e}{\text{ (mod }}n{\text{)}}}$ mesajını gönderip deşifre etmesini isteyebilir. Çarpımsal özellikten dolayı ${\displaystyle c'}$, ${\displaystyle mr{\text{ (mod }}n{\text{)}}}$'in şifreli halidir. Eğer saldırgan atakta başarılı olursa ${\displaystyle mr{\text{ (mod }}n{\text{)}}}$ değerini elde eder ve ${\displaystyle r^{-1}}$ ile çarpıp kolayca m değerini bulur.

Dolgu Şemaları

Tüm bu problemleri ortadan kaldırmak için kullanılan RSA uygulamaları şifrelemeden önce düz mesaj olan ${\displaystyle m\,}$’ye rastsallaştırılmış uygularlar. Bu dolgu ${\displaystyle n\,}$’yi güvensiz düz metin aralığında olmaktan korur ve ${\displaystyle n\,}$’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 ${\displaystyle n\,}$’de ${\displaystyle d.\,}$ 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 ${\displaystyle n\,}$’de ${\displaystyle e.\,}$ 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ştirilirken de gibi güvenli dolgu şemaları kullanılması gereklidir. Ayrıca güvenlik açısında şifrelemede ve imzada aynı anahtar kullanılmamalıdır.

Doğruluk İspatları

Fermat’nın Küçük Teoremi ile İspatı

Fermat'nın küçük teoremi ${\displaystyle p}$ asalı ve ${\displaystyle p}$’nin bölmediği bir ${\displaystyle a}$ tam sayısı için ${\displaystyle a^{(p-1)}\equiv 1{\text{ (mod }}p{\text{)}}}$ denkliğinin doğru olduğunu belirtir.

Her ${\displaystyle m}$ mesajı için (m^e)^d${\displaystyle \equiv }$ m ${\displaystyle {\bmod {p}}q}$ denkliğinin doğru olduğunu göstermek istiyoruz.

${\displaystyle ed\equiv 1{\text{ (mod }}(p-1)(q-1){\text{)}}.}$ olduğunu biliyoruz. Yani negatif olmayan bir ${\displaystyle p}$ tam sayısı için ${\displaystyle ed-1=h(p-1)(q-1)}$ yazabiliriz. Eğer m^ed ${\displaystyle \equiv }$ m mod p ve m^ed ${\displaystyle \equiv }$ m mod q olduğunu gösterirsek m^ed ${\displaystyle \equiv }$ m mod pq olduğunu ispatlamış oluruz.

m^ed ${\displaystyle \equiv }$ m mod p olduğunu göstermek için m ${\displaystyle \equiv }$ 0 mod p ve m ${\displaystyle \not \equiv }$ 0 mod p durumlarına bakalım. İlk durumda m^ed, p 'nin katı olduğundan m^ed ${\displaystyle \equiv }$ 0 ${\displaystyle \equiv }$ m mod p. İkinci durumda da m^p-1' ‘in Fermat’nın küçük teoreminden dolayı 1’e denk olmasını kullanarak ispatı yapabiliriz:

${\displaystyle m^{ed}=m^{(ed-1)}m=m^{h(p-1)(q-1)}m=(m^{p-1})^{h(q-1)}m\equiv 1^{h(q-1)}m\equiv m{\text{ (mod }}p{\text{)}}}$.

m^ed ${\displaystyle \equiv }$ m mod q olduğunu da benzer şekilde gösterip algoritmanın doğruluğunu ispatlamış oluruz.

Euler teoremi ile ispatı

Rivest, Shamir ve Adleman orijinal makalelerinde RSA yönteminin çalışmasını açıklarken Fermat’nın küçük teoremini kullanmalarına rağmen genellikle ispatlarda Euler teoremi kullanılır.

Her ${\displaystyle m}$ mesajı için (m^e)^d${\displaystyle \equiv }$ m ${\displaystyle {\bmod {p}}q}$ denkliğinin doğru olduğunu göstermek istiyoruz. ed ${\displaystyle \equiv }$ 1 mod ${\displaystyle \varphi (n)}$ olduğunu biliyoruz. Dolayısıyla negatif olmayan bir ${\displaystyle h}$ tam sayısı için ${\displaystyle ed}$ çarpımını ${\displaystyle ed=1+h\varphi (n)}$ şeklinde yazabiliriz. ${\displaystyle m}$ ve ${\displaystyle n}$’nin aralarında asal olduğunu varsayarsak

${\displaystyle m^{ed}\equiv m^{1+h\varphi (n)}\equiv m(m^{\varphi (n)})^{h}\equiv m{\text{ (mod }}n{\text{)}}.}$

Son eşitlik Euler teoremi’nin bir sonucudur. Eğer ${\displaystyle m}$ ve ${\displaystyle n}$ aralarında asal değilse bu argüman doğru olmaz. m ${\displaystyle \equiv }$ 0 mod p vem ${\displaystyle \equiv }$ 0 mod q durumları yukarıdaki ispatta olduğu gibi gösterilebilir.

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, rastgele 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 tam sayı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); 

Kaynakça

1. ^ ^{a b} MOLLIN, RICHARD A. (2019). Rsa And Publıc-Key Cryptography. [S.l.]: CRC PRESS. ISBN . OCLC 1112201971. 
2. ^ ^{a b} Prodhan, Georgina (4 Ekim 2010). "Secret coding inventors finally win recognition". Reuters (İngilizce). 13 Ocak 2021 tarihinde kaynağından . Erişim tarihi: 11 Ocak 2021. 
3. ^ dotnet-bot. . docs.microsoft.com (İngilizce). 31 Aralık 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 11 Ocak 2021.