RSA

Bu madde veya bölüm RSA Algoritması maddesine çok benzemektedir ve bu iki maddenin tek başlık altında birleştirilmesi önerilmektedir. Birleştirme işlemi yapıldıktan sonra sayfaya {{Geçmiş birleştir}} şablonunu ekleyiniz.

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.

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 $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.
   • $d \,$ özel anahtar üssü olarak saklanır.
   • $d \,$ değeri genellikle Genişletilmiş Öklid Algoritması kullanılarak hesaplanır.

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

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

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

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

• 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ı

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

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ı

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

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 (m^e)^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 m^ed $\equiv$ m mod p ve m^ed $\equiv$ m mod q olduğunu gösterirsek Çin Kalan Teoreminden m^ed $\equiv$ m mod pq olduğunu ispatlamış oluruz.

m^ed $\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 m^ed, p 'nin katı olduğundan m^ed $\equiv$ 0 $\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:

$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{)}$.

m^ed $\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 $m$ mesajı için (m^e)^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.