Trigger Warning : Math
Ve bunu yapmak için kullandığımız iki farklı algoritma var. Simetrik ve Asimetrik Şifreleme Algoritmaları.
Bu yazımda Asimetrik Kriptografi(asimetrik şifrelemle algoritmaları)’ndan bahsedeceğim.
RSA
RSA, güvenliği tam sayıları çarpanlarına ayırmanın algoritmik zorluğuna dayanan bir tür public-key şifreleme yöntemidir.
Alice ve Bob birbirlerine güvenli bir şekilde mesaj göndermek isteyen iki kişidir. Bunu yapmak için de RSA algoritmasını kullanacaklar. Yapmaları gerekenler :
1/ ilk olarak p ve q olarak çok büyük 2 asal sayı seçiyorlar.
2/ n = p * q olacak şekilde bir n değeri hesaplıyorlar.
3/ Φ(n) = (p-1) * (q-1) olacak şekilde bir Φ(n) değeri hesaplıyorlar.
4/ {1,2,3 ……….. Φ(n) -1} kümesinden EBOB(e, Φ(n)) = 1 denklemini sağlayacak bir e sayısı seçiyorlar.
5/ d * e ≡ 1 (mod Φ(n)) sağlayacak şekilde bir Kpr = d(private-key) belirliyoruz.
Burası anahtar üretme süreciydi. Buradan sonra Alice ve Bob, Kpub = (n, e) sıralı ikilisini birbirlerine gönderiyor. Şimdi de Bob, Alice’e mesaj göndermek istiyor. Göndereceği mesajı Alice’in public keyi ile şifrelemeli.
Bunu da y = e(x) ≡ x^e (mod n) olacak şekilde hesaplıyor ve y değerini Alice’e gönderiyor.
Alice de x = d(y) ≡ y^d (mod n) denklemini kullanarak şifreyi çözüyor ve x değerini okuyabiliyor.
Ayrık Logaritma Kripto Sistemleri
Diffie-Helman Key Exchange
Diffie-Helman Key Exchange’de aslında yaptığımız şey private-key’lerimizi kullanarak birer public key üretiyoruz. Bu public key’i taraflar birbiri ile paylaşıp ortak bir anahtar hesaplıyor ve bu sayede birbirlerine güvenli mesaj iletebiliyorlar. Ne demek istediğimi matematiği görürsek daha kolay anlayabiliriz sanırım.
Alice ve Bob ilk olarak birer private key seçmeli. Bu private key’i bulmak için öncelikle bir aralık seçmeliler. Bu aralık için asal bir sayı olan p’yi seçiyorlar. Sonrasında da bir tamsayı olan x’i ortak olarak belirliyorlar.
Yani ikisi de (Zp)* = {2,3….p-2} aralığından random birer private-key seçiyor. Sonrasında birbirlerine iletmek için birer public-key oluşturmalılar( (Zp)* gösteriminde Z tam sayılar kümesini, * Sıfır’ın kümeye dahil olmadığını, p de kümenin sınırını belirler).
Bunun için önceden belirlediğimiz x’i kullanacaklar. Alice, A = x^a (mod p) değerini hesaplıyor(A Alice’in public-key’i, a da random seçtiği private key)
Bob da B = x^b (mod p) değerini hesaplıyor(B, Bob’un public-key’i, b de random seçtiği private-key)
Sonrasında public-key’lerini birbirlerine gönderiyorlar. Sonrasında Alice B^a (mod p) değerini(B, Bob’un public-key’i , a da kendisinin private-key’i), Bob da A^b (mod p) değerini hesaplıyor. Ve şaşırtıcı olarak bu iki değer birbirine eşit çıkıyor. Yani B^a ≡ A^b (mod p) oluyor. Bu eşit olan değerleri kendilerinden başkası bilemeyeceği için birbirlerine simetrik-şifreleme ile veri iletseler herhangi bir sorun çıkmıyor.
Peki bu sayılar neden eşit?
A = x^a (mod p) demiştik. Bob, B = A^b (mod p) değerini hesaplıyor. A yerine x^a değerini yazarsak B = (x^a)^b = x^(a*b) olur.
B = x^b (mod p) demiştik. Alice, A = B^a (mod p) değerini hesaplıyor. B yerine x^b değerini yazarsak A = (x^b)^a = x^(b*a) olur.
Gördüğümüz gibi bu iki değer birbirine eşit. Biz bu değeri mesajları şifrelemede ve bu şifreleri çözmede kullanabiliriz. Çünkü bu değeri kırmak çok zordur.
Şimdi de bunun kırılmasının neden zor olduğunu ve Ayrık Logaritma problemine dayanan kripto sistemlerini incelemeye geçelim. Bunun için önce birkaç matematiksel yapıyı tanıtmam gerekecek.
İkili İşlem
A herhangi bir küme olsun. AxA’dan A’ya tanımlı bir * :
AxA — -> A
(x,y) — -> x*y
Fonksiyonuna A içinde(A üzerinde) bir ikili işlem denir.
Her (x,y) sıralı ikilisi için x * y = y * x sağlanıyorsa * ikili işlemi değişme özelliği gösterir deriz. Örneğin Reel sayılarda toplama ve çarpma işlemleri değişme özelliği gösterir.
5 + 4 = 4 + 5 = 9 sağlanır.
Eğer (a*b)*c = a*(b*c) eşitliği A kümesinin elemanı olan her a,b,c sayısı için sağlanıyorsa bu ikili işlem birleşme özelliği gösteriyordur deriz(Yani A kümesindeki a,b,c yerine koyduğunuz her eleman için bu eşitlik sağlanmalı). Örneğin Reel sayılarda toplama ve çarpma işlemleri birleşme özelliği gösterir.
5 + (4 + 9) = (5 + 4) + 9 = 18 sağlanır.
Eğer A kümesindeki her x elemanı için e*x = x*e = x eşitliklerini sağlayan bir e elemanıdır A varsa bu ikili işlemin birim elemanı vardır ve bu birim eleman e’dir deriz(Kriptografide bu birim eleman önemli. Biz kriptografide e=1 kullanacağız). Örneğin Reel sayılar üzerinde toplama işleminde 0 birim elemandır.
X + 0 = 0 + X = X sağlanır. //her ikili işlemde bulunmak zorunda değil.
Eğer Her x elemanıdır A için x * x^-1 = x^-1 * x = e(birim eleman) sağlanıyorsa * ikili işleminin tersi vardır deriz(Buradaki x^-1 ‘i 1/x olarak düşünmeyin x elemanının tersi olarak düşünün). Bir ikili işlemde ters elemandan bahsedebilmemiz için öncelikle birim elemanın varlığından söz edebilmeliyiz. Birim elemanın var olma şartı var yani. Ayrıca ters eleman tektir. Yani her bir elemanın sadece bir tersi vardır(örneğin reel sayılarda çarpmada 3 * 1/3 gibi 3^-1 = 1/3’tür başka bir değere eşit değildir).
Sonlu Gruplar
Bir küme üzerinde bir veya daha fazla ikili işlem tanımlanmış ise bu ikili işlemler ile birlikte o kümeye cebirsel yapı denir.
<A,*> : A kümesi ve onun üzerinde bir * ikili işlemi ile oluşmuş cebirsel yapı
<A,*, ^ > : A kümesi ve onun üzerinde * ve ^ ikili işlemleri ile oluşmuş cebirsel yapı
Grup nedir?
A bir küme ve * ,A üzerinde bir ikili işlem olsun. Eğer aşağıdaki dört koşul sağlanırsa <A,*> bir gruptur.
1/ Eğer <A,*> bir grup ise ve a * b = c ise a, b ve c, A kümesinin elemanı olmalıdır.
2/ <A,*> birleşme özelliğine sahipse
3/ <A,*> birim elemanı varsa
4/ A’nın her elemanı * ikili işlemine göre terse sahip ise <A,*> bir gruptur.
Eğer bunların yanında grup değişme özelliği de gösteriyorsa(Her (x,y) sıralı ikilisi için x * y = y * x sağlanıyorsa) bu gruba değişmeli grup(Abelyen grup) denir..
Bazı tanımları verdik. Şimdi bunlara modüler aritmetiği dahil ederek örnek çözelim.
(Z9)* = {1,2,3,4,5,6,7,8} olsun. < Z9* , *>’nin grup olup olmadığını belirleyelim. ( * sembolü bu örnekte çarpma işlemi olarak tanımlanmıştır)
Bunun bir küme olmadığı açıktır çünkü daha ilk maddeden kaybediyoruz. 7 * 8 = 56 ve bu kümedeki bir eleman değildir. Ama bu örneği verme sebebim bu değil. Asıl göstermek istediğim şey ters operatörünün bazı sayılarda neden olmadığı. O yüzden direkt oraya geçiyorum.
Kümeden bir eleman seçelim. Ben 2'yi seçiyorum. Şimdi yapmamız gereken 2 * 2^-1 ≡ 1 (mod 9) olmalı. Öncelikle 1'in denklik sınıfını yazalım.
{10,19,28,37,46,55,64,73}. Yani 2 * 2^-1 değeri buradaki elemanlardan birine eşit olmalı. 2 * 2^-1 ∈ {10,19,28,37,46,55,64,73}. 2^-1 değerinin (Z9)* = {1,2,3,4,5,6,7,8} kümesinden olmak zorunda olduğunu biliyoruz. 2^-1 yerine bunu yazarsak
2 * {1,2,3,4,5,6,7,8} ∈ {10,19,28,37,46,55,64,73}. Buradan {2,4,6,8,10,12,14,16} ∈ {10,19,28,37,46,55,64,73} olur ve 2^-1 = 5 olduğunu görüyoruz.
2 elemanı için ters vardır yani.
Bunu bir de 3 için deneyelim. 3 * {1,2,3,4,5,6,7,8} ∈ {10,19,28,37,46,55,64,73}. Çarpmayı yaptığımızda eşleşen herhangi bir eleman olmadığını göreceğiz. Bunun sebebi EBOB(3,9)’un 3'e eşit olması. Ters elemanın olması için EBOB(a,p) = 1 olmalı(a tersini bulmak istediğimiz eleman p de önceden belirlediğimiz üst limit).
Ancak biz gruplarla uğraşmak istiyoruz. Birazdan kriptografide çok önemli olan döngüsel gruplara gireceğiz ve bu ters eleman koşulunun sağlanması gerekecek. Bu durumu çözmek için ne yapabiliriz peki? 2 yolumuz var. Birincisi EBOB(a,p) != 1 olan elemanları listeden atarız. Ancak biz sistemimizi bir de bunu hesaplayarak yormak istemiyoruz. Bunun için ikinci yöntemi kullanıyoruz. O da p’yi asal seçmek. Eğer p asal olursa herhangi bir tamsayı p’yi bölemez.
Döngüsel Gruplar
Döngüsel gruplar, içerisindeki tek bir eleman tarafından üretilebilen gruplara denir. Döngüsel gruplar, eleman sayısı c kolacak şekilde a^c = a * a * a * a * ……… * a(c defa) = 1(birim eleman) şartını sağlamalıdır.
Bir örnek üzerinden gidelim. (Z11)* = {1,2,3,4,5,6,7,8,9,10}. 2'nin tüm kuvvetlerini alırsak ne olacağını merak ediyoruz. Hesaplayalım :
2¹ = 2 (mod 11)
2² = 4 (mod 11)
2³ ≡ 8 (mod 11)
2⁴ ≡ 5 (mod 11)
2⁵ ≡ 10 (mod 11)
2⁶ ≡ 9 (mod 11)
2⁷ ≡ 7 (mod 11)
2⁸ ≡ 3 (mod 11)
2⁹ ≡ 6 (mod 11)
2¹⁰ ≡ 1 (mod 11)
Görüldüğü üzere tanımdaki gibi gruptaki tek bir elemanı kullanarak bütün elemanları üretebildik. Bu durumda bu grupa döngüsel grup diyoruz. 2'ye ilkel eleman veya generator diyebiliriz. Ve bu durumu ord(2) = 10 olarak gösteriyoruz. Ord(a) grubun kaç elemanda bir döndüğünü gösterir. Yani ord(2) = 10 yazdığımızda döngünün 10 elemanda bir gerçekleştiğini söylüyoruz.
Ayrık Logaritma Problemi
(Zp*) = {1,2 ……… p-1} grubunun döngüsel olduğunu ve generator’un a olduğunu varsayalım. (Zp*) kümesinin bir elemanı olan b için, a^x ≡ b (mod p) denkleminde x’i bulmaya ayrık logaritma problemi denir. Sayılar yeterince büyük olursa ve iyi seçilirse problemi çözmek neredeyse imkansız hâle gelebilir. Bu problemde x’i bulmak için kullanacağımız fonksiyon logaritma olduğu için bu probleme ayrık logaritma problemi denir.
Diffie-Helman Problem
Diffie-Helman Key Exchange hakkında konuştuk. Şimdi olaya bir de atak kısmından bakalım. Yani biz bu sisteme nasıl atak yapabiliriz?
Öncelikle neleri biliyoruz : x, p, A ve B’yi biliyoruz. Peki bilmek istediğimiz şey ne? B^a (mod p) = A^b (mod p)değerini bilmek istiyoruz ki aradaki mesajları okuyabilelim.
B^a (mod p) = A^b (mod p) = x^a*b (mod p) olduğunu da biliyoruz. Yani biz aslında x^a (mod p) ve x^b (mod p) değerlerini biliyoruz bize gereken a ve b değerleri. Yapmamız gereken işlem a = logx(A) (mod p). Bu değeri hesapladıktan sonra B^a (mod p) değerini bilebiliriz çünkü B değerini zaten biliyorduk. Ve mesajı okuyabiliriz. Bu noktadaki sıkıntı eğer Alice ve Bob yeterince akıllı ise(sayıları iyi seçtilerse) bizim a = logx(A) (mod p) değerini çözeyemeyecek olmamız. Buna Diffe-Helman problemi diyoruz.
Atak yapmanın bir başka yolu henüz bilinmediği için Diffie-Helman problemi ile Ayrık logaritma problemini de bir tutuyoruz.
Elliptic Curve Cryptography
Yine geldik iki gözümün çiçeğine. Elliptic Curve’den bir önceki yazımda bahsettim. Elliptic Curve Cryptography dediğimiz şey aslında bir grup ve ikili işlemlerden oluşur. Bunu <E,+,*> olarak düşünebiliriz. E dediğimiz Elliptic Curve denklemini sağlayan elemanlar, + addition(toplama) işlemi ve * de multiplication(çarpma) işlemidir.
Elliptic Curve’lerde toplama ve çarpma işlemlerinden önceki yazımda bahsetmiştim. O yazıdan alıntı yapıyorum.
Elliptic curve üzerindeki toplama, P1 ve P2 elliptic curve üzerinde olmak üzere, P3 = P1 + P2'yi sağlayacak şekilde bir P3 olduğunu söyler. Geometrik olarak bu P3 noktası, P1 ve P2 arasında bir doğru çizerek hesaplanır. P1 ve P2 ‘den geçen bir doğru mutlaka elliptic curve üzerindeki bir P3 noktasından da geçecektir(Bezout teoremi). Doğrunun eğri ile kesiştiği 3. nokta P3’ = (x, y) olsun. P3 ‘ü bulmak için x ekseninde yansımasını alırız ve P3 = (x, –y) buluruz.
İkili işlemlerdeki birim elemandan bahsetmiştik. Bunun Elliptic Curve’deki karşılığı point at infinity’dir.
Elliptic curve’lerde aynı zamanda “point at infinity” denilen 0 ile toplamaya denk gelen bir nokta da vardır. Bilgisayarlarda bazen x = y = 0 olarak gösterilir(elliptic curve denklemini sağlamaz ama ayrı olarak kontrol edilebilecek bir durumdur). Bazı durumlarda( P1 ve P2'nin eşit x ama farklı y değerlerinin olduğu), doğru dikey olacaktır. Bu durumda P3 = point at infinity olur.
Çarpma işleminden de bahsedelim.
Bildiğimiz gibi çarpma aslında tekrarlı toplamadır. Yani biz 5 * 5 dediğimiz zaman aslında 5 + 5 + 5 + 5 + 5'i kast ediyoruz. Elliptic curve’ler için de durum böyledir ancak toplama operatörünün sağlaması gereken kurallar yukarıda belirttiğimiz gibidir. Yani “normal” toplamadan farklıdır.
Örneğin eğer 5 * P1 ‘i hesaplamak istersek P1 + P1 + P1 + P1 + P1 ‘i hesaplamamız gerekir. 5 küçük bir sayı olduğu için bu işlem bize bir sorun yaratmaz ancak büyük sayılarla uğraşıyorsak tek tek yapmak sorun yaratacaktır. Onun yerine biz gruplama yaparız. Yani P1 + P1 ‘i hesaplarız. Bu işlemin sonucuna Q1 diyelim. P1 + P1 + P1 + P1 + P1 işlemi Q1 + Q1 + P1 ‘e dönüşür. Bu da bize işlem kolaylığı sağlar. Burada yaptığımız P1 + P1 işlemine Doubling, P1 + Q1 işlemine de addition(toplama) denir.
Okuduğunuz için teşekkür ederim.
