RSA

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

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[değiştir | kaynağı değiştir]

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[değiştir | kaynağı değiştir]

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

Anahtar Üretimi[değiştir | kaynağı değiştir]

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 p \, ve 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. n = p q \, hesaplayın.
    • n \, özel ve ortak anahtarlar için mod değeri olarak kullanılacaktır.
  3. Bu sayıların totientı olan \varphi(n) = (p-1)(q-1) \, hesaplayın.
  4. Bir tam sayı üretin ve adını da e \, koyun. Bu sayı, 1 < e < \varphi(n) \, koşuluna uygun olmalı ve \varphi(n) \, ile en büyük ortak böleni 1 olmalıdır (başka bir deyişle \varphi(n) \, ve e \, kendi aralarında asal olmalıdır).
    • e \, ortak anahtar olarak açıklanır.
    • Bit uzunluğu kısa olan ve küçük Hamming Ağırlığına sahip e \, değerleri (yaygın olarak 0x10001 = 65,537) daha verimli şifreleme sağlarlar. Fakat küçük e \, değerleri (örneğin 3) bazı durumlarda güvenliği azaltabilir.
  5. d e \equiv 1 \pmod{\varphi(n)} olacak şekilde bir d \,'yi belirleyin.

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

Şifreleme[değiştir | kaynağı değiştir]

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

Şifre Çözme[değiştir | kaynağı değiştir]

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

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

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

Örnek[değiştir | kaynağı değiştir]

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

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

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

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

c=2790’ın şu şekilde şifresini çözebiliriz: 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[değiştir | kaynağı değiştir]

  • Küçük şifreleme üssü (örn. e \, = 3) kullanıldığında şifrelenen m \, mesajı da küçükse (m<n^{1/e}), m^e \, değeri n \,’den küçük bir değere karşılık gelir. Bu durumda şifreli mesajlar tam sayılardaki e. \, dereceden kökleri alınarak kolayca çözülebilirler.
  • Eğer bir mesaj aynı şifreleme üssü e \, ve farklı n \, değerleri ile birden çok kişiye gönderiliyorsa, bu mesaj Çin Kalan Teoremi 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, m_1^em_2^e\equiv (m_1m_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 c = m^e\text{ (mod }n\text{)} 'nin çözümünü elde etmek isteye bir saldırgan rastgele bir r \, değeri seçip, özel anahtara sahip kişiye şüpheli gözükmeyen c' = c r^e\text{ (mod }n\text{)} mesajını gönderip deşifre etmesini isteyebilir. Çarpımsal özellikten dolayı c', mr\text{ (mod }n\text{)}'in şifreli halidir. Eğer saldırgan atakta başarılı olursa mr\text{ (mod }n\text{)} değerini elde eder ve r^{-1} ile çarpıp kolayca m değerini bulur.

Dolgu Şemaları[değiştir | kaynağı değiştir]

Tüm bu problemleri ortadan kaldırmak için kullanılan RSA uygulamaları şifrelemeden önce düz mesaj olan m \,’ye rastsallaştırılmış dolgu uygularlar. Bu dolgu n \,’yi güvensiz düz metin aralığında olmaktan korur ve 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[değiştir | kaynağı değiştir]

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 n \,’de 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 n \,’de 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ş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.

Doğruluk İspatları[değiştir | kaynağı değiştir]

Fermat’nın Küçük Teoremi ile İspatı[değiştir | kaynağı değiştir]

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

Her m mesajı için (me)d  \equiv m \bmod pq denkliğinin doğru olduğunu göstermek istiyoruz.

e d \equiv 1\text{ (mod }(p-1)(q-1)\text{)}. olduğunu biliyoruz. Yani negatif olmayan bir p tamsayısı için e d - 1 = h(p-1)(q-1) yazabiliriz. Eğer med \equiv m mod p ve med \equiv m mod q olduğunu gösterirsek Çin Kalan Teoreminden med \equiv m mod pq olduğunu ispatlamış oluruz.

med \equiv m mod p olduğunu göstermek için m \equiv 0 mod p ve m \not\equiv 0 mod p durumlarına bakalım. İlk durumda med, p 'nin katı olduğundan med \equiv 0 \equiv m mod p. İkinci durumda da mp-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^{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{)} .

med \equiv m mod q olduğunu da benzer şekilde gösterip algoritmanın doğruluğunu ispatlamış oluruz.

Euler teoremi ile ispatı[değiştir | kaynağı değiştir]

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 m mesajı için (me)d  \equiv m \bmod pq denkliğinin doğru olduğunu göstermek istiyoruz. ed \equiv 1 mod \varphi(n) olduğunu biliyoruz. Dolayısıyla negatif olmayan bir h tamsayısı için ed çarpımını ed = 1 + h\varphi(n) şeklinde yazabiliriz. m ve n’nin aralarında asal olduğunu varsayarsak

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 m ve n aralarında asal değilse bu argüman doğru olmaz. m \equiv 0 mod p vem \equiv 0 mod q durumları yukarıdaki ispatta olduğu gibi gösterilebilir.