Açık anahtarlı kripto sistemlerinin ilkeleri

Açık anahtarlı sifrelemenin genel amacı, gerçeklestirecegi devrim ile geleneksel sifrelemenin en büyük iki problemine çözüm saglamaktır. Bu problemlerden ilki gizli anahtarların dagıtımıdır. Gizli anahtar derken, geleneksel kriptografi uygulamalarının (DES, IDEA, Blowfish, CAST128, RC5, ...) kullandıgı anahtarlar kastedilmektedir.

Geleneksel sifrelemeden yararlanarak birbirlerine sifrelenmis metinler gönderecek olan taraflar, sifreleme ve sifre çözme islemleri için, ya bir sekilde kendilerine ulastırılmıs olan anahtarı kullanacaklar, ya da, bir anahtar dagıtım merkezinden faydalanacaklardır. Açık anahtarlı kriptografinin mucitlerinden birisi olan Whitfield Diffie (digeri de Stanford Üniversitesinden Martin Hellman’dır), kriptografinin özü olan, iletisimde %100 güvenlik esasını hiçe sayan bir anahtar dagıtım merkezi kullanma gerekliligini ortadan kaldırmıstır.

Çünkü tarafların kullanacakları gizli anahtarları bir anahtar dagıtım yetkilisinden almaları, istedigi takdirde üçüncü parti bir kisinin iletisimi anlasılır kılabilecegi tehlikesini  barındırmaktadır. Diffie, üzerinde düsündügü ikinci problem olan "sayısal imza" konusunun, yukarıda ifade edilenden farklı bir konu oldugunu görmüstür. Eger kriptografinin kullanımı, sadece askeri konularda degil, özel ve kâr amaçlı uygulamalarda da kullanılacak kadar yaygın olsaydı, bu durumlar için kullanılacak elektronik belge ve dokümanlarda da, kâgıt dokümanlarda kullanılan kisisel imzalara gerek duyulacak ve böylece sayısal imzalar sayesinde, bir mesajı kimin gönderdigi kesinlikle bilinecek, bu da herkesi memnun eden bir yöntem olacaktır.

Açık anahtarlı kripto sistemlerin karakteristikleri
Açık anahtarlı sifreleme/sifre çözme algoritmaları, sifreleme için bir anahtara, sifre çözme içinse bu anahtarla iliskisi olan ama bu anahtardan farklı ikinci bir anahtara ihtiyaç  duyarlar. Bu durumda güvenlik saglanmıs olur. Bu algoritmalar su önemli karakteristige sahiptirler: Sadece kriptografik algoritma ve sifre çözme anahtarı verilmisken, bir takım hesaplamalar yolu ile sifreleme anahtarını bulmak mümkün degildir.Bununla beraber RSA gibi bazı algoritmalar su karakteristikleri de gösterirler:Her iki benzer anahtar da sifreleme ve sifre çözme için kullanılabilir.Bununla beraber, bir anahtar sifreleme için kullanılmıssa, sifre çözme için diger anahtar kullanılmalıdır. Resim 1 de , açık anahtarlı sifreleme yöntemi gösterilmistir.
Baslıca adımlarsunlardır:
1. Her agdaki her son sistem, mesaj alındıgında sifreleme ve sifre çözme için kullanacak oldugu anahtar parçasını yaratır.

2. Her sistem, sifreleme anahtarını herkesçe erisilebilecek bir dosya ya da yazmaç içerisine kaydederek paylastırır. Bu anahtarın, açık olan kısmıdır (public key). Özel anahtar saklı tutulur.

3. Eger, A, B’ye bir mesaj yollamak isterse, mesajı B’nin açık anahtarını kullanarak sifreler.

4. B, mesajı aldıgında, bu mesajı kendi özel anahtarını kullanarak sifreyi çözer. Diger hiçbir alıcı mesajı sifreyi çözemez, çünkü mesajı çözecek olan özel anahtarı sadece B bilir.

                                      Açık anahtarlı kripto sistemi

anlasıldıgı üzere her katılımcı, digerlerinin açık anahtarlarına erisim hakkına sahiptir. Ve katılımcılar özel anahtarlarını yerel olarak yaratırlar. Bu yüzden, özel  anahtarların paylasılmasına gerek yoktur. Herhangi bir sebepten ötürü özel anahtarlar sahipleri tarafından degistirilmek istenebilirler, bu durumda degismis olan yeni açık anahtar ilgili yerlere yeniden gönderilerek eskisi ile yer degistirilir.

. Açık anahtarlı kripto sistem uygulamaları

Açık anahtarlı algoritmaların üç önemli sınıfı vardır:

1. Açık anahtar Dagıtım Seması (Public-Key Distribution Schemes PKDS),bilginin bir kısmının güvenli olarak degistirilmesi için kullanılır (deger iki tarafa baglıdır). Bu deger gizli anahtar seması için bir oturum anahtarı olarak kullanılır.
2. imza Seması (Signature Schemes), sadece sayısal imza üretmek için kullanılır, burada gizli anahtar imzayı üretmekte, açık anahtar ise dogrulamakta kullanılır.
3. Açık anahtar Seması (Public Key Schemes PKS), sifrelemek için kullanılır, burada açık anahtar mesajları sifreler, gizli anahtar mesajların sifresini çözer. Herhangi bir açık anahtar seması, gerekli olan oturum anahtarlı mesajı seçmek suretiyle PKDS olarak kullanılabilir. Çogu açık anahtar seması aynı zamanda imza semasıdır (saglanan sifreleme ve sifre çözme her iki sırada yapılabilir.).

RSA kripto sistemi
RSA kripto sistemi, 1978 yılında "Sayısal imza elde etme yöntemi ve açık anahtarlı kripto sistemler" adlı bir makale ile yayınlanmıstır. Adını yaratıcılarının (Ronald Rivest, Adi Shamir, Leonard Adleman) soyadlarının bas harflerinden alan RSA kripto sistemi, göndericinin bir yöntemle ve herkesçe bilinen açık bir anahtarla mesajlarını sifreledigi bir kripto sistemi olarak tanımlanır. Daha önceki gizli (simetrik) anahtarlı sistemlerin tersine

anahtarı bilmek sifre çözme anahtarını ortaya çıkarmaz. Bu sistem hem gizlilik hem de sayısal imza saglamak amaçlı kullanılabilir. Bu sistemin güvenligi tamsayılarda  çarpanlara ayırma probleminin kolay olmaması temeline dayanır. RSA kripto sisteminde kisilere sifreli mesaj gönderilebilmesi için o kisilerin açık anahtarlarına ihtiyaç vardır. Mesajı alan kisinin de mesajı okuyabilmesi için gizli bir anahtarının olması gerekir. Anahtar olusturma asagıdaki algoritmada ifade edilmistir.

Anahtar olusturma algoritması  Bir A kisisi anahtarını su sekilde olusturur:

iki tane farklı, rasgele ve yaklasık aynı uzunlukta olan p ve q asal sayıları
seçer.

n = pq ve f = (p - 1)*(q-1) degerlerini hesaplar.
1 < e <f ve OBEB (e, f ) = 1 olacak sekilde rasgele bir e sayısı seçer.
Öklid algoritmasını kullanarak, 1 < d <f ve ed _ 1 (mod f ) kosulunu
saglayan d sayısını hesaplar.

A’nın açık anahtarı (n, e); A’nın gizli anahtarı ise d olur.
RSA anahtar olusumunda e ve d tamsayıları sırasıyla sifreleme üssünü ve sifre çözme üssünü ve n ise mod sayısını gösterir. p ve q sayılarının onluk sistemde uzunluklarının 100 ve dolayısıyla da n nin uzunlugunun 200 olması beklenir. Fakat verilecek örneklerde kolaylık olması açısından küçük sayılar seçilecektir.

Sifreleme algoritması
1. B sahsı, A’ya bir m mesajı göndermek istiyor. B, m mesajını sifrelemek için
asagıdakileri yapar:

Öncelikle A’nın açık anahtarını (n,e) alır.
 m mesajını [0, n -1] aralıgında yazar.
Sonra c _ me (mod n) degerini hesaplar.
Olusan c sifresini A’ya gönderir.
2. Sifreli c metninden açık metni bulabilmek için A asagıdaki islemi uygular: d gizli anahtarını kullanarak ve m_ cd (mod n) islemini uygulayarak m açık metnine ulasır.

NOT: Sifre çözme sisteminin çalısmasına ed_1 (mod f ) oldugu için ed = 1 + k f

esitligini saglayan mutlaka bir k tamsayısı bulunur. Eger OBEB (m, p) = 1 ise

Fermat teoreminden dolayı;

mp-1 _ 1 ( mod p) (4.1)
Eger bu denkligin her iki tarafının da k(q-1)’inci kuvvetlerini alırsak
mk(p-1)(q-1) _ 1 (mod p) (4.2)
olur ve her iki tarafı da m ile çarptıgımızda
m1+k(p-1)(q-1) _ m (mod p) (4.3)
sonucuna ulasırız.

Diger taraftan, eger OBEB (m, p) = p olursa yukarıdaki denklik yine geçerli olur; çünkü belli bir k tamsayısı için m = kp oldugunu varsayalım.
Bu durumda;
mp-1 = (kp)(p-1) = k(p-1)p(p-1) _ p (mod p).
olur.

Eger bu denkligin her iki tarafının da k(q - 1)’inci kuvvetlerini alırsak
mk(p-1)(q-1) _ pk(p-1)(q-1) _ p (mod p).
olur ve her iki tarafı da m ile çarptıgımızda
m1+k(p-1)(q-1) _ mp = kp2 _ kp = m (mod p).
buluruz.

iki durumda da
med _ m (mod p)
oldugu görülür. Aynı sekilde,
med _ m (mod q) olur.
Sonuçta p ve q farklı asal sayılar oldugu için,
med _ m (mod n)’dir. Böylelikle,
cd = med _ m (mod n)
oldugu görülür.

Örnek
1. Anahtar olusturma: A sahsı p = 2357 ve q = 2551 olan iki tane asal sayı
seçmis olsun. Öncelikle A,
n = p * q = 6012707 ve
f = (p- 1) * (q- 1) = 6007800
degerlerini hesaplar. A bir tane e = 3674911 degeri seçer. Bu e degeri,
OBEB (e = 3674911, f = 6007800) = 1 ve 1 < e = 3674911 < f = 6007800
kosullarını saglar.
Daha sonra Öklid algoritmasını kullanarak
e * d _ 1 (mod f )
3674911 * d _ 1 (mod 6007800)
d = 422191 degerini hesaplar. A’nın açık anahtarı (n = 6012707;
e = 3674911); gizli anahtarı da d = 422191 olur.

2. Sifreleme: B, m = 5234673 mesajını sifrelemek için A’nın açık anahtarını,
yani (n = 6012707; e = 3674911), alır ve asagıdaki sekilde oldugu gibi
kapalı metin c’yi hesaplar:
c i me (mod n) = 52346733674911 (mod 6012707) _ 3650502
ve bu degeri A’ya gönderir.

3. Sifre çözme: A, gelen c kapalı metninden m açık metnini asagıdaki gibi
hesaplar:
m i cd (mod n) = 3650502422191 (mod 6012707) _ 5234673

RSA imza seması
RSA kripto sistemi sayısal imzalar için de kullanılabilir. (n, e) A sahsının açık anahtarı, d sayısı da A’nın gizli sifre çözme üssü olsun. Öncelikle mesajın imzalanabilmesi için m mesajının {0,1,…, n-1} arasında olması istenir, daha sonra hesaplamalar yapılır.

imzalama
A B’ye imzalı m mesajını göndermek isterse, mesaja kendisinin kapalı
anahtarını uygular, yani
i= md mod n
degerini hesaplar.
Daha sonra (m, _) imzalı mesajı B’ye gönderir.
imzayı dogrulama

B, A’dan aldıgı (m, _) imzalı mesajı dogrulamak için
m = ie mod n
degerini hesaplar. Çıkan sonuç m ise mesaj dogrulanmıs olur.

Örnek
1. Anahtar Olusturma: A kisisi p = 7927 ve q = 6997 asal sayılarını seçer ve
n = pq = 55465219 ve f = 7926* 6996 = 55450296 degerlerini hesaplar.
Daha sonra A, ed = 5d _ 1 (mod 55450296) esitliginden d = 44360237
sayısını bulur. A’nın açık anahtarı (n = 55465219, e = 5); gizli anahtarı d =
44360237 olur.

2. imzalama: m = 31229978 mesajını imzalamak için A sunu hesaplar:
i = md mod n = 3122997844360237 mod 55465219i 30729435
ve (m = 31229978, i = 30729435)’yi B’ye gönderir.

3.imzayı Dogrulama: (m = 31229978, i = 30729435)’yi alan B mesajı
dogrulamak için sunu yapar:
m = ie mod n = 307294355 mod 55465219 i 31229978
Çıkan sayı m oldugu için imza dogrulanmıs olur.

Ayrık logaritma (Discrete logarithm)
RSA kripto sisteminde, RSA fonksiyonu m olarak verilen bir elemanın e. kuvvetini olusturur. Bu fonksiyon bire-bir bir fonksiyondur ve etkili bir sekilde hesaplanır. Eger n’nin çarpanlara ayrılması bilinmiyorsa, e. kökü hesaplamak için etkili bir algoritma yoktur. Sayılar teorisinde hesaplaması kolay fakat tersinin hesaplaması zor olan baska fonksiyonlar da vardır. Bunlardan en önemlilerinden biri de sonlu cisimlerde kuvvet almadır. Basit olarak sadece asal cisimler düsünülecektir.

p bir asal sayı ve g de Zp
* de bir ilkel kök olsun. Ayrık kuvvet fonksiyonu
(discrete exponential function)
Exp: Zp-1 i Zp
*, x a gx,

tekrarlı karesini alma algoritması örneginde oldugu gibi etkili bir sekilde hesaplanabilir. Kuvvetin logaritması fonksiyonunun tersini hesaplamak için etkili bir algoritma bilinmemektedir. Bu tahmine ayrık logaritma tahmini (discrete logarithm assumption) denir.

El-Gamal açık anahtarlı kripto sistemi
El-Gamal açık anahtarlı kripto sistemi, anahtar transferi modunda Diffie- Hellman anahtar anlasması (Diffie-Hellman Key Agreement) olarak görülebilir. Güvenilirligi ayrık logaritma problemi ve Diffie-Helman probleminin kolay çözülememesi temeline dayanır. Temel El-Gamal ve genellestirilmis El- Gamal sifreleme seması bu bölümde tanımlanmıstır.El-Gamal açık anahtarlı sifrelemede anahtar olusturma algoritması

Her kisi kendi açık anahtarını ve buna baglı gizli anahtarını olusturur. Bunu olusturmak için A sahsı sunları uygular:
1. Çok büyük rasgele bir p asal sayısı ve mod p ye göre tamsayıların olusturdugu çarpım grubu Zp
* nin bir üreteci _ yı olusturur.

2. 1 a  p - 2 seklinde olan bir a tamsayısı seçer ve _a mod p degerini hesaplar.

3. A’nın açık anahtarı (p, _, _a ); A’nın gizli anahtarı ise a olur.
El-Gamal açık anahtarlı sifreleme algoritması
B sahsı A için m mesajını sifrelesin.

1. Sifreleme: B mesajı sifreleme için sunları yapar:
A’nın açık anahtarını (p, _, _a ) alır.
mesajı {0, 1, …, p-1} aralıgında m tamsayısı olarak ifade eder.
1          k          p -2’yi saglayan rasgele bir k tamsayısı seçer.
i= ik mod p ve            = m * (i a)k mod p degerlerini hesaplar.
Son olarak c = (i,      ) kapalı metnini A’ya gönderir.
2. Sifre çözme: c kapalı metninden m açık metine ulasmak için A sunları yapar:
a gizli anahtarını kullanarak _-a mod p degerini hesaplar (i-a = i -ak mod p).
i-a *      mod p degerini hesaplayarak m’yi bulur.
i-a *        i -ak * m i ak i m (mod p)

Örnek
1. Anahtar Olusturma: A sahsı bir p = 2357 asal sayısı ve i = 2 Î Z* bir üreteç seçer. Buna ilave olarak bir a = 1751 gizli anahtarı seçer ve
ia mod p = 21751 mod 2357 i 1185
degerini hesaplar. A’nın açık anahtarı (p = 2357, i = 2, ia = 1185)’tir.

2. Sifreleme: m = 2035 mesajını sifrelemek için B sahsı rasgele bir k = 1520 tamsayısı seçer ve 36
i= 21520 mod 2357 _ 1430 ve
             = 2035 *11851520 mod 2357i 697
degerlerini hesaplar. Son olarak B (i= 1430, = 697)’yi A’ya gönderir.

3. Sifre çözme: A gelen kapalı metni çözmek için
ia = 1430i1751 i 1430606 mod 2357 i 872 bulur ve m mesajına da
m = 872 *697 mod 2357 i 2035
böylece ulasır.

El-Gamal imzası
El-Gamal kripto sisteminde imza RSA’da oldugu gibi mesajın dogru kisiden geldigini kontrol etmek için kullanılır. Sadece kapalı metin yerine imzalanmıs kapalı metin gönderilerek o kapalı metnin istenen kisiden gelip gelmedigi de kontrol edilmis olur. A sahsının açık anahtarı (p, _, _a = y) ve gizli anahtarının da a oldugu düsünülsün.

imza algoritması
m mesajının Zp nin bir elemanı oldugu düsünülür. Eger degilse özet fonksiyonu kullanılarak m mesajının Zp nin elemanı olması saglanır. A sahsım mesajını su sekilde imzalar:

1. Rasgele bir t tamsayısı seçer; t tamsayısı 1    t           p - 2 ve OBEB(t, p-1) = 1
kosulunu saglamalıdır.

2. r = i t ve s = t-1(m -ra) mod (p -1) esitliklerini kurar.
3. (m, r, s) A’nın imzalı mesajıdır.

Dogrulama
(m, r, s) imzalı mesajı alan B sahsı aldıgı mesajın A’dan geldigini su sekilde
dogrular:
1. Öncelikle 1            r           p - 1 oldugunu kontrol eder. Eger degilse imzayı
reddeder.
2. Daha sonra v = im ve w = yrrs degerlerini hesaplar (Buradaki y sayısı A’nın
açık anahtarındaki y sayısıdır. )
3. Eger v = w esitligi saglanıyorsa imza kabul edilir, aksi takdirde reddedilir.

Örnek
1. Anahtar Olusturma: A sahsı bir p = 2357 asal sayısı ve _ = 2Î Z* bir
üreteç seçer. Buna ilave olarak bir a = 1751 gizli anahtarı seçer ve
ia mod p = 21751 mod 2357 _ 1185
degerini hesaplar. A’nın açık anahtarı (p = 2357, _ = 2, _a = 1185) tir.

2. imza Olusturma: Basit olması açısından mesaj m = 1463 olarak seçilsin
(Eger mesaj p asal sayısından büyük olsaydı özet fonksiyonundan
geçirilirdi). m = 1463 mesajını imzalamak için A önce rasgele bir t = 1529
sayısı seçer, daha sonra
r = it mod p = 21529 mod 2357 _ 1490 ve
t-1 mod (p - 1) = 1529-1 mod (2356) i 245
s = t-1(m - ra) mod (p - 1) = 245(1463 – 1490 * 1751) mod 2356 _ 1777
A’nın imzası (m = 1463, r = 1490, s = 1777)
3. _mzayı Dogrulama: B aldıgı imzalı mesajı dogrulamak için önce
v = im mod p = 21463 mod 2357 _ 1072
degerini hesaplar. Daha sonra
w = yrrs mod p = 1185149014901777 mod 2357 _ 1072
degerini hesaplar ve v = w oldugu için imzayı kabul eder.