Sessiz Teori: RSA Algoritması

RSA Algoritması

Adsız Yorum yok 20 Mar 2014

Şifreleme işlemi antik çağlardan günümüze kadar insanoğlunun üzerinde düşündüğü ve çalışmalar yaptığı konulardan birisi olmuştur. Şifreleme işlemini belli bir tekniğe dayandırarak gerçekleme ise Sezar’ın basit yer değiştirme tekniği ile başlamıştır diyebiliriz. Zamanla kullanılan şifreleme tekniklerin deşifre edilmesi farklı teknik ve şifreleme yöntemleri bulmak adına yapılan çalışmaları arttırmıştır. Teknolojinin hızla gelişmesiyle beraber ayrı bir araştırma ve bilim dalı olarak kriptoloji(şifre bilimi) ortaya çıkmıştır.

Günümüz teknolojisinin baş döndürücü hızla gelişimine paralel olarak bilgisayar, akıllı telefon, vb. elektronik cihazlar hayatımızda daha fazla yer almaya ve daha fazla kullanılmaya başlamıştır. Bu cihazlar aracılığıyla banka işlemleri, alış-veriş(e-ticaret) ve haberleşme gibi bir çok işlemin kolaylıkla gerçekleştirilebiliyor olması insanları cezbettiği için her geçen bu tür cihazları kullanan insan sayısının artmaktadır. Güvensiz bir ortam olan internet üzerinden bu kadar çok işlemin güvenli bir şekilde gerçekleştirilmesinin sağlanması ise gelişen teknolojinin en büyük dezavantajlarından birisidir.
İnternet, sağladığı sınırsız imkanlar ve sunduğu onca kolaylıklara karşın son derece güvensiz bir ortamdır. Onun için bu ortamda bankacılık işlemleri, askeri sistemler, özel görüşmeler gibi işlemleri gerçekleştirirken iki nokta arasında veya sistemler arası haberleşmede gizlilik, bütünlük ve kullanılabilirlik ilkelerine göre bilginin güvenliği sağlanmalıdır. Bu kapsamda ilk olarak güvenli iletim ortamının sağlanması adına bir çok çözüm üretilebilir fakat %100 güvenli hiç bir sistem yoktur sözü göz önünde bulundurulacak olursa iletilecek olan bilgi üzerinde de ayrıca bir güvenlik tedbiri uygulanmalıdır diyebiliriz. Bu tedbirlerden en önemlisi olarak sayılabilecek olan giden ve gelen verinin şifrelenerek anlaşılmaz hale getirilmesi ve bu şekilde iletilmesidir. Yıllardır bu alanda yapılan çalışmalar neticesinde bir çok şifreleme tekniği bulunmuş ve kullanılmıştır. Fakat bunlardan bazısı zayıflık barındırdığı, bazısı gelişen teknoloji karşısında gücünü kaybettiği, bazısının da yeni donanımlarla uyumlu çalışamaması neticesinde rafa kaldırıldığını söyleyebiliriz. Bu zorlu süreçlerden güvenilirliğini ispatlayarak ve koruyarak günümüze kadar gelebilen bir kaç tane şifreleme algoritması vardır. Bunlardan birisi de en yaygın kullanılan asimetrik şifreleme algoritmalarından birisi olan RSA şifreleme algoritmasıdır.

Bu makale kapsamında günümüzde en çok kullanılan açık anahtarlı(asimetrik) şifreleme algoritmalarından olan RSA şifreleme algoritması incelenecektir. RSA şifreleme algoritmasının ortaya çıkış tarihinden başlanarak, anahtarların üretimi, şifreleme ve şifre çözme işlemlerinin nasıl gerçekleştirildiği, algoritmanın doğruluğunun ispatı ve algoritmanın gücünden bahsedilerek algoritmaya karşı yapılan saldırıların neler olduğunu ve nasıl yapıldığı incelenecektir.

2. RSA ALGORİTMASI

RSA şifreleme algoritması, digital ortamda verinin güvenli aktarımının sağlanması fikri temel alınarak yapılan araştırmalar neticesinde bulunan çok büyük tam sayıları çarpanlara ayırmanın algoritmik zorluğu göz önüne alınarak geliştirilen açık anahtarlı bir şifreleme tekniğidir. Günümüzde en çok kullanılan hem şifreleme hem de sayısal imza atma olanağı tanıyan bir yöntemdir. 1974 yılında Diffie ve Hellman tarafından bulunan Açık Anahtarlı(Asimetrik) şifreleme yönetimini kullanan Ronald Rivest, Adi Shamir ve Leonard Adleman, kendi isimlerinin ilk harflerini verdikleri RSA algoritmasını bulmuşlardır. Algoritmayı ilk defa inceleyen birisine göre son derece basit matematiksel işlemlere dayanan bir yöntem izlenimi veren algoritmada bu matematiksel işlemler neticesinde iki farklı anahtar üretilmektedir. Anahtarlardan birisi herkesin erişebileceği açık anahtar, diğeri ise gizli anahtardır. Herkes kendisine şifreli bir mesaj göndermek isteyen birisinin gönderilecek mesajı sadece kendisinin açabileceği şekilde şifreleyebilmesi için açık anahtarını yayınlar ve bu açık anahtarı kullanılarak mesaj şifrelenir ve gönderir. Gönderilen şifreli mesajı ise sadece şifrelendiği açık anahtarın eşi olan gizli anahtara sahip olan kişi görüntüleyebilir.

3. TARİHİ

Teknik temelleri bir ingiliz matematikçi ve kriptolog olan Clifford Christopher Cocks tarafından Hükümet İletişim Karargahında(GCHQ) yaptığı çalışmalar neticesinde 1973 yılında açıklanmıştır. Fakat gerek açıklamış olduğu sistemin o zamanın teknolojisi ile gerçekleştirilmesinin mali yönden sıkıntılı olması gerekse çalışmakta olduğu kurumun gizlilik politikaları nedeniyle Cocks’un yaptığı çalışmalara dair dışarıya herhangi bir açıklama yapılmamıştır. Ancak 1998 yılında Cocks’un çalışmalarına ait dökümanlar yayınlanınca Cocks’un da eşdeğer bir sistem tasarlamış olduğu ortaya çıkmıştır. Bu zamana kadar Cocks’un yapmış olduğu çalışmalar hakkında herhangi bir bilgi paylaşılmamış olduğundan RSA yöntemini Cocks’un çalışmasından bağımsız olarak tasarlamış ve 14 Aralık 1977 yılında algoritmayı bulan Ron Rivest, Adi Shamir ve Leonard Adleman tarafından isimlerinin ilk harfleri ile isimlendirilerek duyurulmuştur. Daha sonra ise geliştirilen bu algoritma için 20 Eylül 1983 yılında MIT’den patent de alınmıştır.

4. İŞLEMLER

Açık anahtarlı şifreleme tekniği olan RSA algoritması ile anahtar üretimi, şifreleme ve şifre çözme işlemlerinin nasıl gerçeklendiğini anlatmadan önce açık anahtarlı şifreleme tekniğini hatırlamakta fayda olduğunu düşünmekteyim. Açık anahtarlı şifreleme, şifre ve şifre çözme işlemleri için farklı anahtarların kullanıldığı bir şifreleme tekniğidir. Açık anahtarlı şifreleme tekniğini temel alarak yapılan şifreli haberleşme işlemlerinde haberleşen tarafların sahip olduğu bir çift anahtar vardır. Bu anahtarlardan biri herkesin bildiği, öğrenebildiği ve kullanabildiği açık anahtardır; diğeri ise kullanıcıya ait sadece kullanıcının bildiği ve bilmesi gerektiği gizli anahtardır. Bu anahtarlardan açık anahtar sadece kendisi ile çift oluşturacak olan gizli anahtarın sahibi tarafından oluşturulabilir ve herkesin erişimine açılır. Şifreleme işlemleri bu açık anahtar ile yapılır ve kullanılan bu açık anahtarın çifti olan gizli anahtar dışında şifreli metni hiçbir anahtar açamaz. Basit bir şekilde açık anahtarlı şifreleme ile haberleşme aşağıda bulunan resimdeki gibi gösterilebilir.

Şekil 1 - Açık anahtarlı şifreleme ile haberleşme

Açık anahtarlı şifreleme mantığınının anlaşıldığı kabul edilirse, açık anahtarlı şifreleme yöntemi olan RSA için anahtarlar üretimi, şifreleme ve şifre çözme işlemlerinin nasıl yapıldığını inceleyebiliriz.

4.1 Anahtar Üretimi

RSA’nın çok büyük tam sayıları çarpanlara ayırmanın algoritmik zorluğu göz önüne alınarak geliştirilen açık anahtarlı bir şifreleme tekniği olduğunu söylemiştik. Burada bahsi geçen çok büyük tam sayıyı oluşturma işlemi için çok büyük ve birbirinden farklı olan iki asal sayı kullanılarak daha güvenli bir yapı oluşturulmuştur. RSA şifreleme algoritması için anahtar oluşturma işlemlerini sıra sıra ele alarak görelim.
1-) Bundan sonra N ile ifade edeceğimiz çok büyük tamsayıyı oluşturacak olan iki faklı ve büyük asal sayı belirlenir. Bu sayılar p ve q olarak isimlendirilir.
2-) İki asal sayının çarpımını asal çarpanlarına ayırmak asal olmayan sayıları asal çarpanlarına ayırmaktan daha zor olduğu için N tam sayısını oluştururken bu iki asal sayının çarpımından elde ettiğimiz değeri kullanıyoruz.
N = p.q
3-) N sayısının totient değeri hesaplanır. Totient, sayılar teorisinde bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayı adedini belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsveçli matematikçi Leonhard Euler tarafından tanımlanmıştır. Totient fonksiyonu, Yunan harflerinden phi(φ) ile simgelendiği için Phi fonksiyonu olarak da anılabilir.[1]
φ(N) = (p-1)(q-1)
4-) 1 < e < φ(N) ve EBOB(e, φ(N)) = 1
Yukarıdaki matematiksel ifadeden de anlaşıldığı üzere 1 ile Totient değeri arasında olan ve Totient değeri ile aralarında asal olan bir tam sayı seçilir ve e olarak isimlendirilir. Burada seçilecek olan e sayısının küçük seçilmesi(ör: 3 gibi) mod ve üs alma gibi işlemleri yaparken performanstan kazandırıyor olsa da bazı durumlarda güvenliği azaltmaktadır.
5-) d.e ≡ 1 (mod φ(N))
Denkliğini sağlayan ve gizli anahtarı oluşturmada kullanılacak olan d sayısı bulunur. Burada yapılacak olan işlem e sayısının mod φ(N)’de tersinin bulunmasıdır. Bu değeri bulurken Genişletilmiş Öklid Algoritması kullanılabilir. Yapacağımız örnekte bu algoritmanın nasıl uygulanacağını göstereceğim için burada detaya girmiyorum.
Açık ve gizli anahtar oluşturmak için gerekli olan tüm değişkenleri/değerleri oluşturduk. Gizli anahtarı oluşturan d sayısının hesaplanmasında kullanılan (p,q, φ(N)) sayılarının gizli kalması şartı ile (N,e) çifti açık anahtarı; (N,d) çifti ise gizli anahtarı oluşturmaktadır.

4.2 Şifreleme İşlemi

RSA kullanılarak gerçekleştirilecek olan şifreli haberleşmede gönderilecek olan metin, alıcı kişinin herkese açık olan (N,e) değerleri yani açık anahtarı ile şifrelenmelidir ki bu mesajı istenilen alıcı dışında kimse görüntüleyemesin. Bunun için açık anahtar olan e kullanılır ve şifrelenecek bilginin sayısal karşılığının e’inci kuvvetinin mod N’deki karşılığı da şifrelenmiş metni oluşturur.
c = m^e (mod N)

4.3 Şifre Çözme İşlemi

Açık anahtarlı şifreleme tekniğinin yapısı gereği açık anahtar ile şifrelenmiş bir metin ancak o açık anahtarın çifti olan gizli anahtar ile açılabilir. Bu yüzden (N,e) açık anahtarı kullanarak şifrelediğimiz yukarıdaki m mesajını sadece bu açık anahtarın çifti olan (N,d) gizli anahtarı kullanarak açabiliriz. Bunun için de şifrelenmiş metnin yani c’nin sayısal karşılığının d’inci kuvveti alınır ve bunun mod N’deki karşılığı bulunarak şifre çözme işlemi gerçekleştirilir ve açık metin elde edilir.
m = c^d (mod N)

4.4 Örnek

Yukarıda anlatılan anahtar üretimi, şifreleme, şifre çözme ve öklid algoritmasının uygulanması işlemlerini bir örnek yaparak görelim.
- İlk adım olarak N tamsayısını oluşturacağımız p ve q sayılarını seçelim. Gerçekte çok büyük iki farklı asal sayı olması gerekiyor fakat burda örnek yaptığımız için küçük sayılar kullanıyoruz.
p = 7 ve q = 19
- İkinci adım olarak bu sayıların çarpımını bularak N tam sayısının değerini buluyoruz.
N = p.q => N = 7.19 => N = 133
- Bu N sayısının Totient değerini hesaplıyoruz.
φ(N) = (p-1).(q-1) => φ(N) = 6.18 = 108
- Son olarak bu Totient değeri ile aralarında asal olan e sayısı seçerek e’nin tersine eşit olan d sayısını buluyoruz.
1 < e < 108 ve EBOB(e, 108) = 1
Denklemlerini sağlayan e sayısını 5 olarak seçelim. Öyleyse 5’in mod 108’e göre tersini bulursak, d sayısını da bulmuş olucaz.
d.5 ≡ 1 (mod 108)
denkliğini sağlayan d sayısını genişletilmiş öklid algoritması kullanarak bulabileceğimizi söylemiştik. Şimdi bunu nasıl yapacağımıza bakalım; önce Öklid algortimasını uygulayarak bu iki sayının en büyük ortak bölenini buluruz(Biz zaten bu sayıları aralarında asal olacak şekilde seçtiğimiz için bir yanlışlık yapmaz isek sonucun 1 olması gerekiyor):
108 = 21.5 + 3
  5 = 1.3 + 2
  3 = 1.2 + 1
  2 = 2.1 + 0
Sıfırdan bir önceki değer bize bu iki saynın EBOB’unu vermektedir. Öyleyse:
EBOB(108,5) = 1
Yani beklendiği üzere bu iki sayı aralarında asaldır. Şimdi bir adım daha ileri giderek Genişletilmiş Öklid Algoritmasını uygulayalım ve d sayısını bulalım. Bunun için de EBOB’tan yola çıkarak geriye doğru giden matematiksel/mantıksal işlemler yapmamız gerekiyor.
1 = 3 – 1.2
= 3 – 1.(5 – 1.3)
= 3 – 5 + 3
= 2.3 -5
= 2.(108 – 21.5) – 5
= 2.108 - 42.5 – 5
= 2.108 - 43.5
Hangi sayının tersi aranıyorsa onun yanındaki çarpan kendisinin tersi olmaktadır. Biz 5 sayısının mod 108’de tersini arıyorduk, o zaman 5 sayısının yanındaki çarpan aradığımız değerdir. Bu sayı görüldüğü üzere (-43)’tür veya başka bir deyişle 108+(-43) = 65’tir. Sonuç olarak gizli anahtar için aradığımız d sayısını 65 olarak bulmuş olduk. Tüm değerleri bulduğumuza göre artık açık ve gizli anahtarlarımızı oluşturarak şifreleme ve şifre çözme işlemlerine geçebiliriz.
Şifrelemede kullanılacak açık anahtarımız : (N,e) = (133,5)
Şifre çözmede kullanılacak gizli anahtarımız : (N,d) = (133,65)
Anahtarlarımız ile şifreleme ve şifre çözme işlemini gerçekleyerek şifrelenen metin ile şifre çözme sonucunda elde edilen metnin aynı olup olmadığını test edelim. Bu örnek için m=15 sayısını açık anahtarımız ile şifreleyip gizli anahtarmız ile açalım ve çıkan sonuçları karşılaştıralım.
c = m^e= 15⁵ = 78 (mod 133)
m = c^d  => m = 78⁶⁵ (mod 133) => m = 15
Not: Bu işlemlerin doğruluğunu Wolfram Alpha kullanarak test edebilirsiniz.

5. YAPILAN ATAKLAR

RSA algoritması duyurulalı otuz beş yıldan fazla oldu. Bu uzun süre zarfında RSA’in popularitesi ve buna bağlı olarak kullanım alanı ve oranı arttı. Çok kullanılan bir şifreleme tekniği olduğu için de haliyle bügüne kadar bir çok saldırıya maruz kalmıştır. Yapılan bu saldırılar yan kanal ve kriptanaliz saldırıları olmak üzere iki ana başlık altında toplanabilir. Burada kriptanaliz, şifreyi algoritmanın zayıflığından yararlanarak çözmeye çalışırken yan kanal saldırıları, algoritmanın çalıştığı fiziksel ve elektriksel ortamın sağladığı bilgilerden yararlanarak çözmeye çalışır.

Şekil 2 - Yan Kanal Saldırılarında kullanılabilecek bilgiler

RSA’e yapılan yan kanal analizi saldırılarında başarılı sonuçlar elde edilmiş olmasına karşın kriptanaliz yöntemleri ile pratikte RSA’ın kırılması hala daha gerçekleşmemiştir. Anahtar üretiminde kullanılan sayının büyüklüğüne göre RSA’ın güvenlik seviyeside artmaktadır. Yani yeni saldırı metotları veya daha güçlü makineler kullanılarak yapılacak olan saldırıları bertaraf etmek için daha büyük asal sayılar kullanılabilir. Bügüne kadar yapılan her bir saldırı ağır matematik işlemleri içeren ayrı bir makale olabilecek seviyededir. Onun için yapılan saldırıları ele alıp inceleme gibi bir seçeneğimiz bu makale kapsamında bulunmamaktadır. Bu bölümde daha çok yapılan saldırı çeşitleri ele alınarak tanıtılacak ve bu saldırıları kimlerin bulduğuna değinilecektir. Bahsi geçen saldırı çeşitleri hakkında yapılan çalışmalar üzerine detaylı bilgi edinmek isteyenler için ise referans olarak makalelerin kaynakları verilecektir.

Zamanlama Saldırıları

Temel felsefe, algoritmanın ya da algoritmanın adımlarının birinde yürütülen işlemin ne kadar sürede çalıştığını tespit edip buna göre çıkarımlar yapmaktır.

Şekil 3 - Zamanlama saldırısı gerçeklenmesi

Bu alanda yapılan ilk çalışma amerikalı bir kriptocu olan Paul Carl Kocher tarafından 1995 yılında gerçekleştirilmiş.[2] Bu çalışmadan beş yıl sonra bu sefer başka bir kriptocu olan Werner Schindler 2000 yılında çinli kalan teoremi ile RSA’ya karşı bir zamanlama saldırısı yapılabileceğini göstermiştir.[3] Daha sonra ise 2003 yılında Brumley ve Boneh yaptıkları çalışma ile bir ağ üzerinden elde edilen veriler kullanılarak RSA’yı çarpanlarına ayırmanın daha kolay ve pratik bir yolunu bulduklarını açıkladır.[4]

Güç Analizi Saldırıları

Bilindiği gibi en küçük donanım parçası transistörlerdir. Bir transistörün girişine uygulanan gerilim ile üzerinden akım geçmeye başlar. Bu akımdan dolayı transistörde güç tüketimi ve elektromanyetik alan oluşur. Güç analizi saldırılarında da işte bu akım farklarından yararlanarak bilgi toplanmaya çalışılır. Bu saldırı çeşidinin iki farklı türü vardır; sadece işlemcinin harcadığı enerjinin analiz edildiği Basit Güç Analizi(Simple Power Analysis) ile buna ek olarak istatistiki analizlerden ve hata düzeltme algoritmalarından yararlanılarak yapılan Farksal Güç Analizi(Differential Power Analysis) saldırılarıdır. RSA’e yapılan güç analizi saldırıları için öncelikli olarak ünlü kriptocu Kocher’in diferansiyel güç analizi üzerine yapmış olduğu çalışmalar[5][6] incelenmelidir. Bu çalışmaların yanında bir türk güvenlik uzmanı olan Onur Acıiçmez’in bu konu üzerine yaptığı ve başarılı sonuçlar elde ettiği çalışmasına[7] göz atılabilir.

Hata Analizi Saldırıları

Algoritma işletilirken çevresel bazı parametrelerin(sıcaklık, sistem saati, ışık, radyasyon, voltaj vb.) değiştirilmesi sağlanarak sistemde hatalı çalışmaya sebebiyet verilir. Hataya zorlanan sistemden elde edilen yanlış çıktılar ile beklenen doğru çıktıların karşılaştırılması ile elde edilen bilgiler yorumlanarak kriptografik anahtar ve algoritmanın koruduğu varlıklar hakkında bilgi toplanmaya çalışılır. Hata analizi ile RSA’e yapılan ilk saldırı 2010 yılında uygulanmıştır.[8] Bunun dışında incelenmesi gereken diğer bir çalışma ise Bellcore saldırısıdır.[9]

Akustik Kriptanaliz

Şifreleme ve şifre çözme işlemleri sırasında işlemci üzerinde yapılan matematiksel işlemler artmaktadır. Bundan dolayı da işlemciden insan kulağının duyabildiği ve duyamadığı bazı sesler çıkmaktadır. İşte bu seslerin geliştirilen cihazlar aracılığı ile dinlenmesi ve analiz edilip yorumlanarak bilgi toplanması işlemidir. RSA’in mimarlarından olan Shamir 2004 yılında sadece işlemciden çıkan ses ile zamanlama saldırısı yapılabileceğini ispatlayarak bu saldırı tekniği için kapıyı aralamış oldu. Daha sonra içerisinde yine Shamir’inde bulunduğu bir ekip bu araştırmalarını geliştirerek 2013 yılının sonlarında başarılı sonuçlar veren yeni bir saldırı tekniğini duyurmuşlardır.[10]

Elektromanyetik Alan Saldırıları

İşlemcilerin temelini oluşturan donanımın en küçük parçası olan transistörler durum geçişlerinde yüksek akım çekerler. Bu akım değişimi ile bir elektromanyatik alan oluşur. İşte bu yan kanal bilgisi analiz edilerek işlenen veri hakkında bilgi toplama üzerine inşa edilmiş bir saldırıdır. Bu alanda yapılan saldırı ve nasıl yapıldığı, intel atom işlemcileri üzerine yapılmış olan çalışma üzerinde incelenebilir.[11]

Çarpanlara ayırma saldırısı

Klasik şifre çözme yöntemi olan kaba kuvvet saldırısının RSA veriyonudur diyebiliriz. Anahtar üretimnde kullanılan N tam sayısını çarpanlarına ayırıp p ve q asal sayılarını bulmak amaçlı yapılan saldırıları kapsamaktadır. Bu işlemlerin nasıl gerçekleştiğini öğrenmek için bu alanda yapılan birkaç çalışmaya göz atmak yeterli olacaktır.[12][13]

Küçük ‘e’ sayısı saldırısı

Kullanıcının aynı mesaji bir çok kişiye aynı e sayısı ile şifreleyip gönderdiği durumda eğer e sayısı 3 gibi küçük bir sayı ise o zaman araya girip trafiği dinleyen bir kişi topladığı veriler ile çinli kalan teoremini kullanarak gönderilen mesajı ele geçirebilir. Daha detaylı olarak bu saldırıyı incelemek için bu saldırı üzerine geliştirilmiş olan Hastad ve Coppersmith teorileri incelenebilir.[14]

Kuantum Hesaplama Gücü ile yapılan Saldırılar

RSA basit görünen fakat bir o kadar da işlem gücü gerektiren matematik temelli bir şifreleme ve şifre çözme algoritmasıdır. Bu işlemler büyük sayıların modülü ve üslerinin hesaplanması olduğu için ciddi anlamda sağlam bir donanıma sahip bilgisayar veya paralel olarak çalışan bilgisayarlar üzerinde gerçekleştirildiği zaman verim alınabilir, aksi taktirde bu işlemlerin yapılması yıllar sürebilir. Ünlü matematikçi Peter Shor 1994 yılında kuantum bilgisayarlar üzerinde çalışan ve RSA algoritmasının güvenlik duvarı olan N sayısının çarpanlarına ayrılması işlemini yerine getiren Shor Algoritmasını[15] duyurur. Bu algoritma kendisine verilen bir sayının çarpanlarını çıktı olarak üretmek üzerine çalışmaktadır. Bu da demek oluyorki kuantum bilgisayarların gelişimi ile günümüzde kullanılan RSA algoritmalarının kırılması mümkün olacak.

6. DOĞRULUK İSPATI

RSA algoritması ile ilgili en ilgi çekici husus, RSA’in temelinde yüzyıllardan bu yana bilinmekte olan matematiksel bir teorem yatmasıdır. Fermat’nın “küçük teoremi” (Fermat’s little theorem) olarak bilinen ve ilginç, ancak ilk görüşte çok da işe yarayan bir şey olmadığı düşünülebilecek bu teorem kabaca şöyle ifade edilebilir; her p asal sayısı, a tam sayı olmak üzere, her (a^p – a) sayısını böler. Bu, modüler aritmetik sembolleriyle şöyle ifade edilebilir:
a^p ≡ a (mod p) yani a^p-1 ≡1 (mod p)
Burada p, asal bir sayı ve a ise p’den küçük sıfırdan farklı herhangi bir tamsayıdır. Bu teorem ile kabaca, p gibi asal bir sayıdan küçük bir tamsayının modüler olarak (p-1). üssünü hesapladığımızda bunun her zaman 1 tamsayısına eşit olduğu söylenir. Matematik bilgisi çok da kuvvetli olmayan birisi için oldukça soyut görünmesine rağmen bu teorem RSA algoritması için çok önemlidir. Gerçi RSA algoritmasında Fermat’nın küçük teoremi değil onun Euler tarafından genelleştirilmiş hali kullanılır.
Görüldüğü üzere, Fermat ve Euler tarafından, sadece entelektüel bir edimin sonucunda bulunmuş bir teorem yüz yıllar sonrasında (Fermat 17. Euler ise 18. yüzyıllarda yaşamışlardır), elektronik imza gibi devrim niteliğindeki bir teknolojiye temel oluşturmaktadır. Pierre de Fermat bu teoremi öne sürmüş, fakat ispatlamamıştır. Teorem, daha sonra Leonhard Euler tarafından 1736'da ispatlanmıştır. Teorem asallık testlerinde ve bilgisayarda büyük sayılarla işlemlerde kullanılır. Örneğin; a = 2 ve p = 7 ise, 2⁷ = 128, ve 128 − 2 = 7 × 18 sayısı 7'nin tam katıdır.[16]

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

Her m mesajı için (m^e)^d  ≡ m (mod N) denkliğinin doğruluğunu göstermemiz gerekiyor. Yukarıda açıkladığımız ve gösterdiğimiz gibi Fermat’ın küçük teoremi; p asalı ve p’nin bölmediği bir a tam sayısı için a^p-1 ≡ 1 (mod p) denkliğinin doğru olduğunu gösterir.
a^p-1 ≡ 1 (mod p)
d.e ≡1 (mod φ(N)) yani d.e ≡1 (mod (p-1)(q-1))
Öyleyse; d.e -1 = k.(p-1)(q-1) şeklinde yazılabilir.
(m^e)^d  ≡ m (mod N) yani (m^e)^d  ≡ m (mod p.q)
(m^e)^d  ≡ m (mod p) ve (m^e)^d  ≡ m (mod q) olduklarını gösterebilirsek Çinli kalan teoremi göre (m^e)^d  ≡ m (mod p.q) olduğunu ispatlamış oluruz.
(m^e)^d ≡ m (mod p) olduğunu göstermek için m ≡ 0 (mod p) ve m ≢ 0 (mod p) durumlarına bakalım. İlk durumda (m^e)^d, p 'nin katı olduğundan (m^e)^d ≡ 0 ≡ 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:
(m^e)^d = m^(e.d-1).m = m^k.(p-1)(q-1).m = (m^p-1)^k.(q-1).m ≡ 1^k(q-1).m ≡ m (mod p)
(m^e)^d ≡ m (mod q) olduğunu da benzer şekilde gösterip algoritmanın doğruluğunu ispatlamış oluruz.

6.2. Euler Teoremi ile İspat

Rivest, Shamir ve Adleman orjinal 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 m mesajı için (m^e)^d ≡ m (mod p.q) denkliğinin doğru olduğunu göstermek istiyoruz.
e.d ≡ 1 (mod φ(N)) olduğunu biliyoruz. Dolayısıyla negatif olmayan bir h tamsayısı için e.d çarpımını e.d = 1 + h. φ(n) şeklinde yazabiliriz. m ve n’nin aralarında asal olduğunu varsayarsak:

Son eşitlik Euler teoremi’nin bir sonucudur. Eğer ve aralarında asal değilse bu argüman doğru olmaz. m ≡ 0 (mod p) ve m ≡ 0 (mod q) durumları yukarıdaki ispatta olduğu gibi gösterilebilir.[17]
Sonuç olarak açık anahtarlı şifreleme algoritmalarında, sistemin güvenliği anahtar uzunluğuna bağlıdır. Bu algoritmaları daha güvenli hale getirmek için büyük/uzun anahtar değerleri kullanılmaktadır. Günümüzde de RSA şifreleme algoritmasını daha güvenli hale getirebilmek için çok daha büyük asal sayılar kullanılmaktadır. RSA şifreleme algoritması ile şifrelenmiş mesajın kırılması için anahtarların üretildiği bu asal sayıların tahmin edilmesi veya bulunması gerekmektedir. Günümüzde RSA algoritmasında anahtarları üretmek için kullanılan asal sayılar binlerce haneli olarak üretilebilmektedir. Bu da RSA algoritmasının kriptanaliz ve kaba kuvvet saldırıları ile kırılmasının şu anki teknoloji ile yıllar sürebileceğine işarettir. Bundan dolayı RSA şifreleme algoritması hala daha gücünü korumaktadır.