Asal çarpanlara ayırmak: R-S-A Şifreleme

Geçen yazımızda “Bu yüzden çok büyük (ama çok çok büyük) bir sayıyı asal çarpanlarına hızlıca ayırabilirim diyen beni acil bulsun.” demiştim ya, işte tamda o konuya geliyoruz. Hani hepimizin bildiği herhangi bir asal sayıyı, 1 ve kendisi olmak üzere iki tane çarpanına ayırıyoruz, peki ya biz çok büyük iki asal sayı seçersek ve bunları çarparsak bunu nasıl ayıracağız…? İşte beni bulun dediğim noktaya geliyoruz. Sevgili Romalılar, 2009 yılında yapılan bir çalışmada 232 basamaklı bir sayıyı (RSA-768), yüzlerce makinayı iki yıl boyunca çalıştırarak çarpanlarına ayırmışlardır. Eh anca. Belli uzunluktaki her sayının çarpanlara ayrılma zorluğu aynı değil elbette. RSA gibi çok sayıda kriptografik protokol bu problemin veya benzerinin zorluğuna dayanır. Daha ayrık logaritma var. O daha beter. Bir başka deyişle eğer bir sayıyı hızlı bir şekilde çarpanlara ayırma algoritması bulunsaydı (bu yüzden beni acil bulun diyorum), RSA tabanlı açık anahtar kriptografisi güvenliğini yitirirdi ve ayvayı yerdik. Efendim, aritmetiğin temel teoremi der ki, her pozitif tamsayı asal çarpanlarına tek bir biçimde ayrılır (1 için özel bir duruma gerek yoktur, boş çarpım tanımının olması yeterlidir). Fakat, aritmetiğin temel teoremi bu çarpanların nasıl bulunacağı konusunda tek kelime etmez; sadece var olduklarını söyler.

Birleşik Krallık haberalma teşkilatında çalışan İngiliz matematikçi Clifford Cocks 1973’te bu teşkilatın içerisinde bir sistem açıkladı. Fakat bu sistemi çalıştırabilmesi için çok donanımlı ve oldukça pahallı bilgisayarlara ihtiyacı vardı. Bildiğimiz kadarıyla maddi yetersizliklerden dolayı bu sistem hiç uygulanamadı ve 1998 yılına kadar bu buluş çok gizli olduğu için açığa çıkarılmadı. İşte tam bu noktada bizim kahramanlarımız devreye giriyor: Rivest, Shamir ve Adleman. RSA yöntemini Cocks’un çalışmasından bağımsız olarak tasarladılar. RSA şifrelemesi, Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunan ve kendi isimlerinin baş harflerini kullanan açık anahtarlı bir şifreleme yönetimidir. Bir RSA kullanıcısı (siz) iki büyük (çok çok büyük) asal sayının çarpımını üretir ve seçtiği başka bir değerle beraber ortak anahtar olarak ilan eder. Seçilmiş olan asal çarpanları ise saklar. Ortak anahtarı kullanan biri, istediği mesajı istediği gibi şifreleyebilir, fakat şu anki yöntemlerle eğer ortak anahtar yeterince büyükse (cehennem kadar büyüklükten bahsediyorum) sadece asal çarpanları bilen kişi bu mesajı çözebilir. Bilgilerin, verilerin korunmasında güvenlik için kullanılacak asal sayıların olabildiğince fazla basamaklı olması gerekiyor. Bu yüzden de çok büyük basamaklı sayıları asal çarpanlarına ayırma zorluğu karşımıza çıkıyor. Günümüzde, RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problem olarak bilinir.

11201194_1641661676115687_2426717600997293743_n

Gelelim sistemin çalışmasına. Açık anahtarlı şifreleme yönteminden az da olsa bir önceki yazımızda bahsetmiştim, yine de küçük bir hatırlatma yapalım. İki adet anahtar kullanılır demiştik. Bunlardan biri Public key (genel anahtar) ve bu herkesin görebileceği bir anahtardır. Bir diğeri ise gizli anahtar (Secret Key) bu da sadece yazının çözülmüş (deşifrelenmiş) halini elde etmeye yarayacak olan anahtardır. Bu iki anahtar çifti matematiksel olarak birbirleriyle bağlantılıdır. RSA algoritması; anahtar üretimi, şifreleme ve şifre çözme olmak üzere 3 aşamadan oluşmaktadır. Tek tek inceleyelim. Anahtar üretelim önce:

1) Yeterince (aslında baya baya koskocaman) büyük iki asal sayı seçilir. Bu sayılar rastgele seçilmeli, birbirinden farklı ve yakın uzunlukta olursa güvenlik açısından o kadar iyi olur. Bu sayıları asallık testinden (yazının sonunda bahsedeceğim) de geçirebilirsiniz. Bunlar $p$ ve $q$ olsun.
2) $n = p.q$ hesaplanır. Buradaki n sayısı hem genel (public) hem de gizli (secret) şifreler için taban (modulus) olarak kabul eder.
3) Toitent fonksiyonu hesaplanır. Hani sayılar teorisinde, bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayı sayısını belirten fonksiyon varya işte o. Bu verdiğimiz örnek için p ve q asal olduğu için $ϕ(n)=(p−1).(q−1)$ hesaplanır.
4) Hesaplanan toitent fonksiyonu değeri ile aralarında asal öyle bir sayı seçeriz ki bu sayı $1 < e < ϕ(n)$ olmalıdır. Bu seçilen $e$ sayısı genel anahtar (public key) olarak ilan edilebilir.

5) Daha sonra d gibi bir sayı hesaplanır ki, bu sayı için şu denklik geçerli olmalıdır: $d.e ≡ 1 \: mod \: ϕ(n)$ İşte bu d değeri gizli anahtar (private key) olarak saklanır. Bu sayının hesaplanılması sırasında uzatılmış öklid algoritmasından faydalanılır.

Anahtarımızı ürettik. şimdi gelelim şifelemeye;

Şifreleme işlemi için Bahar kendi genel anahtar (public key) şifresi olan (n,e) ikililerini yayınlasın. Bu şifreyi alan da Ayhan şu şeklide mesajı şifreler: $c ≡ m^e \: mod \: n$ burada $m$, şifrelenecek olan açık metin, $e$ ve $n$ ise Bahar tarafından yayınlanan genel anahtardır (public key). c ise şifreli metin.

Şifrenin açılması için şöyle bir işlem yapıyoruz:

$m ≡ c^d \: mod \: n$ burada açılacak olan şifrelenmiş metin c, Bahar’ın private key şifresi ise d ile gösterilmiştir. n ise taban değeri olan modulustür diyoruz. İşte bu kadar.

12208616_1641662709448917_8699915918217419812_n

Haydi bir örnek yapalım. İki asal sayı seçelim. Aslında ≥1024 bit seçmemiz lazım ama biz p=61 ve q=53 seçelim.
n= 61.53 = 3233
ϕ(n) = 60.52 = 3120 Toient fonksiyonu sonucu ile aralarında asal olan ve 1’den büyük sayı seçilir. e>1 ise e=17 seçeyim. Çünkü 3120 ile aralarında asal, seçebilirim. Private key olması için d sayısını buluyoruz. d.e ≡ 1 mod ϕ(n) olacak şekilde d sayısı bulunur.
d.17 ≡ 1 mod 3120 buradan d=2753 (uzatılmış öklid algoritması kullanarak bulduk-çarpmaya göre tersi $17^{-1}  ≡ 2753 \: mod \: 3120$ ) bu d değeri private key olarak saklanır. Yani gizli anahtarımız 2753.

Örneğin mesaj olarak 123 gönderilecek olsun.
$c ≡ m^e \:mod \: n$
$123^{17} ≡ 855 \: mod \: 3233$ işte bu kadar. Şifreli metin 855.
Deşifre etmek için; $855^{2753} \: mod \: 3233$ buradan 123 olarak buluruz.

Gelelim asallık testlerine. Bir sayının asal sayı olup olmadığının bulunması özellikle kriptoloji konusunda oldukça önemlidir. Fermat’ın küçük teoremi bu iş için biçilmiş kaftandır diyebiliriz. Bu teoreme göre, eğer p bir asal sayı ise, her a tamsayısı $a^p-a$ sayısını böler.

$a^p ≡ a \:mod \: p$
$a^{p-1} ≡ 1 \:mod \: p$

Şunu da unutmamak gerekir ki, bir p sayısı her $1 < n < p$ için $n^{(p-1)}-n$ ‘yi bölebilir ama genelde asal olmayabilir. Bu tür sayılara yalancı Fermat asalları ya da bilindiği üzere Carmicheal sayıları da denir. 561 en küçük carmicheal sayısıdır. Fermat bu teoremi öne sürmüş fakat ispatlamamıştır, bunun üzerine Euler 1736’da kalemi eline almış ve ispatı vermiştir.

Bir de Agrawal, Kayal, Saxena abilerin bulduğu AKS asallık testi var. Yine yöntemi geliştiren kişilerin isimlerinin baş harfleri. Denklem şu şekilde:

$(x – a)^n ≡ (x^n – a) \: mod \: n$  Dikkat ettiyseniz, Fermat‘ın küçük teoreminin genişletilmiş halidir ve n ile aralarında asal olan a değerlerini bulmamıza yarar.

Algoritma şöyle çalışr:

Eğer a>0 ve b>1 için  n = ab eşitliği sağlanıyorsa, n sayısı asal değildir.
Or(n) > (log2 n)2 denklemini sağlayan en küçük r değeri bulunur.
Eğer 1 < gcd(a,n) < n denklemini sağlayan bir a ≤ r değeri bulunabiliyorsa sayı asal değildir.
Eğer n ≤ r ise n asal sayıdır.
a =1’den ⌊φ(r) log2(n)⌋ değerine kadar olan değerler için
Eğer (X+a)n≠ Xn+a (mod Xr − 1,n) eşitsizliği sağlanıyorsa sayı asal değildir.
Yukarıdaki şartlar sağlanırsa, sayı asaldır.

Meraklısına: Bkz.

(Or(n) fonksiyonu çarpım derecesini (multiplicative order) gösterir.  φ(n)’nin zaten toient fonksiyonu olduğunu biliyorsunuz.)

Bunlar haricinde Miller-Rabin asallık testi de güçlü bir testtir. Sonuç olarak 300 rakamlı bir sayının asal olup olmadığına bu testlerle bir kaç saniyede görebiliyoruz. Unutmayın asallık testi ve çarpanlarına ayırma birbirinden tamamen farklı iki problemdir. Asallık testi için çarpanları var mı diye bakarsanız çok yanlış işler yapıyorsunuz demektir. Ayrıca şunu da unutmayın asal sayıları üreten basit bir formül ya da denklem yok. Boşuna uğraşmayın. Asal sayılar meraklısına şu kitabı önereceğim: ilginizi çekebilir. Öptüm.

B.

Bahar Uğurdoğan hakkında 8 makale
Kriptolojistimsi.

5 yorum

  1. Merhaba. Bu p ve q asallarını Fermat asalları veya Mersenne asalları olarak seçmek neden güvenliği azaltır? Ve yine bu asalların birbirine yakın seçilmesi neden daha güvenlidir? Hiç bir yerde bu ifadelerin bir açıklamasını bulamadım maalesef. Şimdiden teşekkürler.

    • Perihan selamlar,

      Asal sayıların bazı çarpanlara ayırma metodlarına karşı dirençli olmalarını sağlayan özellikleri vardır. Bu yüzden güçlü asal sayılar kullanmanın faydası büyüktür. Dikkat edilmesi gereken bir nokta anahtar çiftelerinin oluşturulması esnasında güçlü asal sayıların seçimi ile anahtar oluşturma süreleri artmaktadır. p ve q, birbirlerine yakın uzunlukta olmalıdır dedik çünkü bu çarpanlarına ayrılmasını zorlaştıran bir etkendir. Bu yüzden yakın seçiyoruz Peri. Asal sayılardan birinin küçük olması çarpanlara ayırma işlemini önemli ölçüde kolaylaştırır. Modülü oluşturan p ve q asal sayılarının 512-bitlik bir modulde 256 bitlik iki asal sayı olarak seçilmesi en uygun seçimdir.

      Unutmayalım ki biz iki asal sayı seçiyoruz, yalancı birine nasıl güveneceğiz? n sıfırdan küçük olmayan bir tam sayı olmak üzere,
      $F_n = 2^{2^n}+1 $ Dolayısıyla, n > 4 için asal bir Fermat sayısı olup olmadığı hala açık bir soru olduğundan güvenlik açısından kullanmak ne kadar doğru olur?
      Bilindiği gibi;
      F0 = 2^1 + 1 = 3
      F1 = 2^2 + 1 = 5
      F2 = 2^4 + 1 = 17
      F3 = 2^8 + 1 = 257
      F4 = 2^16 + 1 = 65537
      F5 = 2^32 + 1 = 4294967297
      F6 = 2^64 + 1 = 18446744073709551617
      F7 = 2^128 + 1 = 340282366920938463463374607431768211457
      F8 = 2^256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937.

      F5,…,F11’in asal olmadığı bilinmektedir. Elbette içlerinden asal olanları seçebiliriz; fakat asal ve birbirine yakın ise. Çünkü güvenliği ancak bu şekilde sağlayabiliriz. Birbirine yakın olursa ayırması zor oluyor bu yüzden bunu yapıyoruz. Ayrıca, bu algoritmada iki asal sayının çarpımını kullanarak anahtar oluşturulmasının sebebi, iki asal sayının çarpımını asal çarpanlarına ayırmak asal olmayan sayıları ayırmaktan daha zorlu olmasıdır.

      Velhasıl; RSA anahtarının büyüklüğü kullanıcıya göre değişmektedir. Burada gözönünde bulundurulması gereken şeyler; korunması gereken verinin değeri, verinin ne kadar süre için korunması gerektiği ve ikinci olarakta saldırıyı yapacak kişilerin ne kadar tehlikeli olduğu dikkate alınmalıdır. Anahtarın büyük seçilmesi güvenliği arttırmaktadır ancak işlem sürelerini arttıracaktır. Anahtar büyüklüğü 512 bit ile 2048 bit arasında olabilir. Anlamadığın bir yer olursa tekrar sor, teşekkür ederim.

  2. Perihan hanıma bir noktada katılıyorum; seçilen iki asalın yakın olması bulunmalarını zorlaştırmaz, aksine kolaylaştırır. Bu konuda kaynak belirtebilirseniz sevinirim.

  3. Merhaba, ben de son zamanlarda asimetrik algoritmalar ile ilgiliyim.Temelde asal sayıları yada en temelinde yüksek basamaklı sayıları çarpanlarına ayırmak zor oluyor.Ben pascal üçgenindeki herhangi 2 yada daha cok sayı seçerek caprma işlemi yapıyorum.Ama bunu yaparken sondan başlıyorum.Örneğin 7*11 bu kolay bi örnek tabiki güvenilir bir anahtar olmaz.Ancak pascal da 7 nin karesini veren ikilileri buluyorum.aynı şeyi 11 in karesini veren ikililer içinde yapıyorum.7’nin karesi(21,28) ikilisi olucak.11 in karesini veren ikili( 55,66) oluyor.içteki sayıları elersek,
    21+66=87 ve 7 ile 11 arasında 4 sayı fark var bunu da pascal üçgeninde kurduğum mantığa göre 10 çıkarmam gerekiyor sonuç 77 oluyor.tabiki asal seçmezsek bu sefer bu ikililik olasığı daha da arıyor iş zora giriyor.Ancak demek istediğim bu mantığı pascal da kullanıp asimetrik algoritmaları şifreleme konusunda yardımcı bi etken olabilir mi?yani pascalda aralarında asal cok büyük 2 sayı da seçsek sonuç olarak sayıların kareleri orada olacağından bu düşündüğüm uygulama kullanılabilir mi?Ancak sorun olacak bi durum var bunu programlayacak bi sistem olur mu ?ol sa da bu bilgisayarın işlemcisini kasacak.Siz bu konuda ne önerebilirsiniz?

  4. Ben söylemek istediğimi çok iyi ifade edemedim.Ama dediğim pascal üçgeninde düşündüğüm uygulama konusunda daha detaylı resimler gönderebilirim.Yani orada hangi sayıyı çarpıcaksanız bile kendini oluşturan ikilileri görebilirsiniz.Ancak üçgenin basamak değeri artıkça sayılar daha uzun ve kompleks hal alıyor.Bazen ulaşmak istediğimiz tek bi sonuç farklı çarpanların artması durumu ile farklı ikililere ulaşma olasılığı durumu zorlayabiliyor.

Bir yanıt bırakın

E-posta hesabınız yayımlanmayacak.


*