AÇIK ANAHTARLI KRİPTOGRAFİ (PUBLIC KEY CRYPTOGRAPHY)

Bu belgede, açık anahtarlı kriptografinin ne olduğundan ve açık anahtarlı kriptografi uygulamalarından bahsedilmektedir. Belgede verilen bilgileri tam olarak anlayabilmek için -şart olmamakla beraber-, geleneksel şifrelemenin mantığı ve geleneksel (simetrik) şifreleme algoritmaları ile ilgili bilgi sahibi olunması faydalı olacaktır.
Belgenin son hali, http://wolf.comu.edu.tr/~evreniz/belgeler/pkc/pkc.html adresinden temin edilebilir.
Bu belge, A. Murat EREN, Faruk ESKİCİOĞLU ve S. Serdar YÜKSEL'in 2002 yılındaki çalışmalarının bir kısmından A. Murat EREN tarafından derlenmiştir; belgeyi bu açıklama satırlarını silmemek kaydı ile istediğiniz gibi kullanabilirsiniz.
Belge içerisindeki bilgiler Cryptography and Network Security (William Stallings) isimli eser başta olmak üzere Applied Cryptography (Alfred J. Menezes, Paul C. van Oorschot, A. Vanstone) ve konu ile ilgili çeşitli makalelerden derlenmiştir.
Belge hakkındaki eleştirileriniz, tavsiyelerinizi ve kriptografi hakkındaki sorularınız için meren [at] uludag.org.tr mail adresini kullanabilirsiniz.

v.0.2 (05/2003) A. Murat EREN, meren [at] uludag.org.tr, http://cekirdek.uludag.org.tr/~meren

 

İÇİNDEKİLER

 

Açık Anahtarlı Kriptografi

Açık Anahtarlı Kripto Sistemlerin Prensipleri

Açık Anahtarlı Kripto Sistemlerin Karakteristikleri

Açık Anahtarlı Kripto Sistem Uygulamaları

Açık Anahtarlı Kriptografi İçin Greklilikler

Açık Anahtarlı Kripto Analiz

 

RSA Algoritması

Algoritmanın Tanımı

Hesaplama yöntemleri

Şifreleme ve Deşifreleme

Anahtar Üretimi

RSA'nın Güvenliği

Çarpan Problemi

Zaman Atakları

 

Anahtar Yönetimi

Açık Anahtarların Dağıtımı

Açık Anahtarların Duyurulması

Herkes Tarafından Erişilebilir Adres Rehberi

Açık Anahtar Yetkilisi

Açık Anahtar Sertifikası

Gizli Anahtarların Açık Anahtarlı Dağıtımı

Basit Gizli Anahtar Dağıtımı

Güvenli Gizli Anahtar Dağıtımı ve Kimlik Doğrulama

Melez (Hibrit) Bir Yöntem

Diffie-Hellman Anahtar Değişimi

 

Eliptik Eğri Kriptografisi

Eliptik Eğriler

Sonlu Alanlardaki Eliptik Eğriler

Eliptik Eğriler ile Kriptografi

Diffie-Hellman Anahtar Değişimi Örneği

Eliptik Eğri Şifrelemesi/Deşifrelemesi

Eliptik Eğri Kriptografisinin Güvenliği

 

 

AÇIK ANAHTARLI KRİPTOGRAFİ

 

Açık anahtarlı kriptografinin gelişmesi, bütün kriptografi tarihindeki en büyük devrimdir. Başlangıcından günümüze kadar, bütün kriptografik sistemler, süpstütüsyon ve permütasyon işlemlerinin temel alınmasıyla oluşturuldular. Sadece elle hesaplanabilen algoritmalarla çalışabilme döneminden sonra, şifreleme/deşifreleme yapan rotor makinelerinin ortaya çıkması sonucunda, geleneksel kriptografide büyük bir gelişme kaydedildi. Elektro mekanik rotor, çok fazla inceliklere sahip ve karmaşık kriptografik sistemlerin geliştirilebilmesini sağladı. Mevcut bilgisayarlarla daha karmaşık sistemler tasarlandı ve en tanınanlarından olan -IBM´in- Lucifer girişimi gelişerek DES´i oluşturdu ve DES`i dünyadaki kriptografi teknikleri arasında en yüksek seviyeye getirdi. Rotor makineleri ve DES (Data Encryption Standart), önemli avantajlar sunmalarına rağmen, halen, süpstütüsyon ve permütasyon işlemlerine bağımlıdırlar.

 

Açık anahtarlı kriptografi, daha önceki gelişmelerden radikal bir kopuştur. Açık anahtarlı kriptografik sistemlerin en önemli noktaları, süpstütüsyon ve permütasyondan çok matematiksel işlevler üzerine temellenmiş olmalarıdır. Daha da önemlisi, açık anahtarlı kriptografi, tek anahtar kullanan simetrik geleneksel şifreleme algoritmalarının tersine, iki ayrı anahtarın asimetrik kullanımını öngörür. Birazdan göreceğimiz gibi, anahtar dağıtımı ve kimlik denetimi gibi gizlilik ve güven gerektiren durumlarda, iki anahtar kullanımı etkili sonuçlar ortaya koymuştur.

 

İlerlemeden önce, açık anahtarlı şifreleme ile ilgili bazı yaygın, yanlış bilgilerden bahsetmeliyiz. Bu yanlış düşüncelerden birisi, açık anahtarlı şifrelemenin, kriptoanalize karşı geleneksel şifreleme yöntemlerinden daha güvenli olduğudur. Örneğin böyle bir iddia, Gardner´ın meşhur Scientific America adlı 1977 yılında yayınladığı makalesinde yapıldı . Aslında, şifrelemenin güvenliği, anahtarın uzunluğuna ve, kırılan şifreli metnin içerdiği hesapsal işlemlerin karmaşıklığına dayanır. İster geleneksel ister açık anahtarlı şifreleme olsun, kriptonaliz bakış açısına göre birini direğinden üstün tutmak yanlış olur.

 

Bir ikinci yanlış düşünce de, genel amaçlı kullanım için geliştirilmiş bir teknik olan açık anahtarlı şifrelemenin, geleneksel şifrelemeyi modası geçmiş kıldığıdır. Tam tersine, geleneksel şifrelemeden vazgeçileceği sanısı, açık anahtarlı şifreleme yöntemlerinin, matematiksel fonksiyonlarından dolayı, ihtimal dışı gözüküyor.

 

Son olarak, açık anahtarlı şifreleme kullanılırken, geleneksel şifrelemenin daha hantal anahtar dağıtım merkezleri ile karşılaştırıldığında, açık anahtarlı sistemlerin anahtar dağıtımının üzerinde kafa yorulması gerekmeyen, sıradan ve basit bir iş olduğuna dair yanlış bir anlayış vardır. Aslında, protokolün bazı biçimleri gereklidir fakat, geleneksel şifreleme yöntemlerinin ihtiyaç duyduğu merkez temsilciler ve prosedürler, açık anahtarlı şifrelemenin ihtiyaç duyduklarından daha basit daha karmaşık ya da daha etkili değildir.

 

Bu bölüm, açık anahtarlı şifrelemeye genel bir giriş mahiyetinde olacaktır. İlk önce, işin kavramsal çerçevesine bakmaya çalışacağız. Bu noktada açık anahtarlı kriptografi ile ilgili enteresan bir anektodu es geçmek olmaz: açık anahtarlı kriptografinin, pratik olarak uyarlanışı gösterilmeden, tekniğin mimarisi geliştirildi ve doğru kabul edilerek yayınlandı. Kimse pratiğini görmeden teorisi kabul gördü. Daha sonra, açık anahtarlı şifreleme yöntemi için, uygulanabilir olarak gösterilen en önemli şifreleme/deşifreleme algoritması olan, RSA algoritmasını inceleyeceğiz. Daha sonrada, açık anahtarlı sistemler için, anahtar dağıtımını ve anahtar dağıtım yönetimlerini inceleyeceğiz.

 

Açık anahtarlı kripto sistemlerinin çoğunluğu, sayılar teorisini temel almıştır. Bu bölümde verilen sonuçları algılamak için, sayılar teorisini anlamanıza yada biliyor olmanıza çok da gerek yoktur. Bununla birlikte, açık anahtarlı şifreleme algoritmaları hakkında kesin bir yargıya varmak için, sayılar teorisinin bazı kısımlarını bilmek gerekmektedir.

Açık Anahtarlı Kripto Sistemlerin Prensipleri

 

Açık anahtarlı şifrelemenin genel amacı, gerçekleştireceği devrim ile geleneksel şifrelemenin en büyük iki problemine çözüm sağlamaktı. Bu problemlerden ilki gizli anahtarların dağıtımıdır. Gizli anahtar derken, geleneksel kriptografi uygulamalarının (DES, IDEA, Blowfish, CAST128, RC5, ...) kullandığı anahtarları kastediyoruz.

 

Geleneksel şifrelemeden yararlanarak birbirlerine şifrelenmiş metinler gönderecek olan taraflar, şifreleme ve de şifreleme işlemleri için, ya bir şekilde kendilerine ulaştırılmış olan anahtarı kullanacaklar, ya da, bir anahtar dağıtım merkezinden faydalanacaklardır. Açık anahtarlı kriptografinin mucitlerinden birisi olan Whitfield Diffie (diğeri de Stanford Üniversitesinden Martin Hellman`dır), kriptografinin özü olan, iletişimde %100 güvenlik esasını hiçe sayan bir anahtar dağıtım merkezi kullanma gerekliliğini ortadan kaldırdı. Tarafların kullanacakları gizli anahtarları bir anahtar dağıtım yetkilisinden almaları, istediği taktirde üçüncü parti bir kişinin iletişimi anlaşılır kılabileceği tehlikesini barındırmakta idi.

 

Diffie, üzerinde düşündüğü ikinci problem olan "dijital imza" konusunun, önceki ile ilgisi olmayan başka bir konu olduğunu gördü. Eğer kriptografinin kullanımı, sadece askeri konularda değil, ö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, kağıt dokümanlarda kullanılan kişisel imzalara gerek duyulurdu. Ve dijital imzalar sayesinde, bir mesajı kimin gönderdiği kesinlikle bilinmiş olur ve bu da herkesi memnun eden bir metot olurdu.

 

Diffie ve Hellman, 1976`da, her iki probleme de, daha önceki bütün kriptografik gelişimlerden ve buluşlardan farklı, radikal bir çözüm getiren hayret verici bir buluş gerçekleştirmeyi başardılar.

 

Az sonra, açık anahtarlı kriptografinin iskeletine göz atacağız. Daha sonra da, bu yöntemin kalbi olan şifreleme/de şifreleme algoritmalarının ihtiyaçlarını göreceğiz.

 

Açık Anahtarlı Kripto Sistemlerin Karakteristikleri

 

Açık anahtarlı şifreleme/deşifreleme algoritmaları, şifreleme için bir anahtara, de şifreleme içinse bu anahtarla ilişkisi olan ama bu anahtar olmayan ikinci bir anahtara ihtiyaç duyarlar. Bu durumda bir güvenlik sağlamış olur. Bu algoritmalar şu önemli karakteristiğe sahiptirler:

 

·                   Sadece kriptografik algoritma ve de şifreleme anahtarı verilmişken, bir takım hesaplamalar yolu ile şifreleme anahtarını bulmak mümkün değildir.

 

Bununla beraber RSA gibi bazı algoritmalar şu karakteristikleri de gösterirler:

 

·                   Her iki benzer anahtar da şifreleme ve de şifreleme için kullanılabilir. Bununla beraber, bir anahtar şifreleme için kullanılmışsa, de şifreleme için diğer anahtar kullanılmalıdır.

 

Şekil 1(a), açık anahtarlı şifreleme yöntemi gösterilmiştir. Başlıca adımlar şunlardır:

 

1.               Her ağdaki her son sistem, mesaj alındığında şifreleme ve de şifreleme için kullanacak olduğu anahtar parçasını yaratır.

2.               Her sistem, şifreleme anahtarını herkesçe erişilebilecek bir dosya yada yazmaç içerisine kaydederek paylaştırır. Bu anahtarın, açık olan kısmıdır (public key). Özel anahtar saklı tutulur.

3.               Eğer, A, B`ye bir mesaj yollamak isterse, mesajı B`nin açık anahtarını kullanarak şifreler.

4.               B, mesajı aldığında, bu mesajı kendi özel anahtarını kullanarak de şifre eder. Diğer hiçbir alıcı mesajı de şifreleyemez, çünkü mesajı de şife edecek olan özel anahtarı sadece B bilir.

 

 

 

Şekil 1

 

 

Bu şekilden de anlaşıldığı üzere her katılımcı, diğerlerinin açık anahtarlarına erişim hakkına sahiptir. Ve katılımcılar özel anahtarlarlarını lokal olarak yaratırlar. Bu yüzden, özel anahtarların paylaşılmasına gerek yoktur. Herhangi bir sebepten ötürü özel anahtarlar sahipleri tarafından değiştirilmek istenebilirler, bu durumda değişmiş olan yeni açık anahtar ilgili yerlere yeniden gönderilerek eskisi ile yer değiştirilir.

 

Tablo 1, geleneksel ve açık anahtarlı şifrelemenin farklarını açıkça göstermektedir. Geleneksel şifrelemede kullanılan anahtarı, açık anahtarlı şifrelemede kullanılan anahtarlardan ayırmak için onu gizli anahtar olarak anacağız. Açık anahtarlı şifrelemede kullanılan iki anahtarı da, genel anahtar ve özel anahtar olarak anacağız. Özel anahtar, her zaman gizli tutulacak olan anahtardır, fakat, geleneksel şifrelemedeki gizli anahtarla karışmaması için ona gizli anahtar yerine özel anahtar diyoruz.

 

 

 

Geleneksel şifrelemede:

Açık anahtarlı şifrelemede:

 

Çalışması için:

 

1. Şifreleme ve de-şifreleme için aynı algoritma aynı anahtarla birlikte kullanılır.

1. Şifreleme ve de-şifreleme için bir algoritma ve anahtarlardan birisi kullanılır. Şifreleme için kullanılan anahtar, de-şifreleme için kullanılamaz.

 

2. Gönderen ve alan, algoritmayı ve anahtarı paylaşmalıdır.

2. Gönderen ve alan, ilişkili anahtarlardan birine sahip olmalıdırlar (aynı olanı değil).

 

Güvenlik için:

 

1. Anahtar gizli tutulmalıdır.

1. Anahtarlardan biri gizli tutulmalıdır.

2. Diğer bilgiler saklandığında, mesajı deşifre etmek imkansız olmalıdır.

2. Diğer bilgiler saklandığında, mesajı deşifre etmek imkansız olmalıdır.

 

3. Algoritma ve şifreli metin örnekleri bilmek, anahtarı çözmek için yetersiz olmalıdır.

3. Algoritma, şifreli metin örnekleri bilmek ve anahtarlardan birine sahip olmak, diğer anahtarı bulmak için yetersiz olmalıdır..

Tablo 1 Geleneksel ve açık anahtarlı şifreleme
 

 

 

Şekil 2

 

 

 

Şimdi, Şekil 2 yardımıyla, açık anahtarlı şifreleme yapısını oluşturan başlıca elementlere bakalım. A, mesaj gönderecek bir kaynak olsun. Ve göndermeyi düşündüğü , genel bir alfabe kullanarak oluşturduğu, M sonlu sayısında kelimeden oluşan bir mesaj olsun. Bu X mesajı, B alıcısı için tasarlanır. B, birbiri ile ilişkili olan bir anahtar çifti yaratır: bir genel anahtar; ve bir özel anahtar . , yalnız B tarafından bilinir. ise, A tarafından erişilebilecek olan B`nin açık anahtarı olacaktır.

X düz metnini ve anahtarını girdi olarak alan A, mesajı şifreleyerek, metnine dönüştürür.

 

 

Alıcı olan B, özel anahtarın sahibi olarak, şifreli metni düz yazıya aşağıdaki fonksiyon ile çözümleyebilir.

 

 

Bir rakip, iletişimi izleyerek şifreli metin Y`yi ele geçirirse, ve `ye sahipse, aynı zamanda, ya da, X için bir erişim hakkına sahip değilse, X ya da `yi elde etme girişiminde bulunacaktır. Rakibin, şifreleme ve deşifreleme algoritmalarını bildiği varsayılır. Eğer, rakip sadece bu mesaj ile ilgileniyorsa, şifreli metni üzerinde yapacağı hesaplamalarla, bir düz metni oluşturmaya çabalayacaktır. Bununla beraber, rakibin teşebbüsü genellikle gelecek mesajları da okuyabilmek üzere, tahmini üstünde hesaplamalar yaparak `yi elde etmek olur.

 

Şekil 3
 
 

 

 


Her iki benzer anahtardan, yani, şifreleme için kullanılacak olan anahtar ve diğeri de deşifreleme için kullanılmak anahtardan genel olarak bahsetmiş olduk. Umarız, oldukça farklı olan bu kriptografik yapıyı açıklayabilmek için yeterli olmuştur. Şekil 2`de, güvenliğin sağlanması gösterilirken, 2 ve 3`te, açık anahtarlı kriptografinin kimlik doğrulamayı nasıl sağladığı gösterilmiştir:

 

 

Bu durumda, A, B`ye göndermek üzere bir mesaj hazırlıyor ve göndermeden önce mesajı kendi özel anahtarıyla şifreliyor. B, bu mesajı, -sadece- A`nın genel anahtarını kullanarak deşifre edebilir. Çünkü, A mesajı kendi özel anahtarı ile şifrelemiştir dolayısıyla sadece, A bu mesajı hazırlayabilir. Bu yüzden özel anahtar ile şifrelenmiş tüm mesajlar dijital imza olarak düşünülebilir. Bununla birlikte, A`nın kendi özel anahtarı ile şifrelediği mesajın, A`nın özel anahtarına sahip olmayan bir kişi tarafından değiştirilmesi imkansızdır, dolayısıyla, bu şekilde, hem bütünlük hem de kaynak doğrulama ihtiyaçları karşılanmış olur.

 

Önceki yapıda, tüm mesaj şifrelenmiş ve gönderici ve mesajın içeriğinin güvenliği sağlanmıştı. Fakat bu, mesajın saklanması ve pratik kullanımı esnasında sorunlara neden olacaktır. Her doküman, pratik kullanım için düz metin halinde saklanmalıdır. Fakat orijinalliğinin ispat edilmesi gereken durumlarda kullanılmak üzere, mesajın şifrelenmiş hali de ayrıca saklanmalıdır. Bu işi başarmanın daha verimli bir yolu olarak, mesajın en önemli olan bitlerinin şifrelenmesi düşünülebilir. Örneğin öyle bir bit grubu olsun ki, bu kısım mesajın tanımlayıcısı olsun ve bu belirleyici bilinmeden/değiştirilmeden dokümanda bir değişiklik yapılması mümkün olmasın. Eğer bu belirleyici, göndericinin özel anahtarı ile şifrelenmişse, bu kısım, mesajın orijinalliğini, ardışıklığını ve içeriğini güvenlik altında tutan bir imza gibi düşünülebilir. Bu belgede dijital imzanın ayrıntılarına derinlemesine girilmeyecektir. Belki ilerleyen zamanlarda, talebe göre bu konuda bilgi içeren bir kısım da belgeye eklenebilir.

 

Şunu vurgulamak önemlidir ki, şifreleme olayı açıklandığı kadarki hali ile gizliliği sağlamaz. Yani, mesajın değiştirilmesi engellenilmiş olsa da, bu mesajın gizlice dinleyenlerce ele geçirilmesini engelleyemez. Ortadadır ki, mesajın bir parçasının imza olacak şekilde şifrelenmiştir ve mesajın geriye kalan kısmı şifrelenmemiş şekilde gönderilmiştir. Hatta mesajın tamamının şifrelenmiş olması halinde bile, Şekil 3`te gösterildiği gibi, gizlilik mümkün değildir. Çünkü, herhangi bir izleyici, mesajı göndericinin genel anahtarı yardımıyla deşifre edebilir.

 

Bununla birlikte, hem kimlik doğrulama, hem de, gizlilik iki açık anahtar kullanılması ile sağlanabilir (Şekil 4):

 

 

Şekil 4
 
 

 

 


Bu durumda, bir mesajı şifrelemeye başlamadan önce, onu özel anahtarımız ile şifreleriz. Bu adım kimlik doğrulamayı sağlar. Daha sonra, bu yeni şifreli mesajı, alıcının genel anahtarı ile yeniden şifreleriz. Bu da gizliliği sağlar. Bu metodun dezavantajı iki kez şifrelenmiş olan metinin iki kez deşifrelenerek açılması esnalarında kaybedilecek fazladan zaman olarak düşünülebilir. Fakat mesaja sağladığı gizlilik ve kimlik doğrulama vazgeçilemez bir özelliktir.

 

 

Açık Anahtarlı Kripto Sistem Uygulamaları

 

Açıklamaya başlamadan önce, açık anahtarlı kripto sistemlerin bir yönünü açıklamalıyız yoksa, karışıklığa yol açmış oluruz. Açık anahtarlı sistemler karakteristik olarak, birisi gizli tutulan, diğeri ise genel kullanım için açılmış olan iki anahtarla çalışan kriptografik algoritmalar kullanırlar. Uygulamaya bağımlı olarak, gönderici, ya kendisinin özel anahtarını, ya alıcının genel anahtarını ya da ikisini birden, kimi kriptografik fonksiyonları gerçeklemek için kullanır. Geniş bir bakış açısı ile, açık anahtarlı kripto sistemlerin kullanımını üç kategoride inceleyebiliriz:

 

·                   Şifreleme/De-Şifreleme: Gönderici, bir mesajı alıcının genel anahtarı ile şifreler.

·                   Dijital İmza: Gönderen, mesajı kendi özel anahtarı ile imzalar. Bu imzalama, mesajın tamamını yada önemli görülen belirleyici bir kısmını şifrelemek ile yapılır.

·                   Anahtar Değişimi: İki taraf ortaklaşa bir oturum anahtarını değiş tokuş ederler. Bir çok farklı yöntem mümkündür. Anahtar değişimi senaryoları ilerde ayrıntıları ile ele alınacaktır.

 

 

Kimi algoritmalar, bu özelliklerden sadece bir yada iki tanesini gerçekleştirebilirken, bazıları bunların tümünü gerçekleştirebilir. Tablo 2, kimi açık anahtarlı algoritmaların bu özelliklerden hangilerini desteklediğini göstermektedir.

 

 

 

Algoritma

 

 

Şifreleme/De-şifreleme

 

Dijital İmza

 

 

Anahtar Değişimi

 

RSA

 

 

Evet

 

 

Evet

 

 

Evet

 

 

Diffie-Hellman

 

Hayır

 

 

Hayır

 

 

Evet

 

DSS

 

Hayır

 

Evet

 

 

Hayır

 

Tablo 2 Açık anahtarlı kripto sistemler için uygulamalar
 

 

 

 

Açık Anahtarlı Kriptografi için Gereklilikler

 

Kripto sistem, Tablo 2`de, iki benzer anahtarı temel alan kriptografik algoritmaya bağlıkları yoluyla ifade edilmiştir. Diffie ve Hellman, bu algoritmaların varlığını göstermeksizin bu sistemi varsaymışlardır. Bununla beraber, bu algoritmaların yerine getirmeleri gereken durumları şöyle ifade etmişlerdir:

 

1.               Bir B için, anahtar parçalarını (genel anahtar ve özel anahtar) yaratmak, hesapsal olarak kolay olmalıdır.

2.               Gönderenin (A olsun), mesajı göndereceği kişinin (B olsun) genel anahtarını bildiği ve şifrelenecek olan mesajı (M olsun) bildiği durumda, uygun şifreli metni yaratmak hesapsal olarak kolay olmalıdır.

 

 

3.               Alıcı B`nin, özel anahtarını kullanarak, şifrelenmiş mesajı orijinal haline getirmesi hesapsal olarak kolay olmalıdır.

 

 

4.               Herhangi bir rakip için, genel anahtarı bilerek, özel anahtarı bulması hesapsal olarak imkansız olmalıdır.

5.               Herhangi bir rakip için, genel anahtarı, şifreli metini (C`yi) bilerek orijinal mesajı (M`yi) elde etmesi hesapsal olarak imkansız olmalıdır.

 

 

Bunlara ek olarak, yararlı olmasına rağmen gerekli olmayan altıncı bir madde ekleyebiliriz:

 

6. Şifreleme ve de-şifreleme fonksiyonları her iki sıra ile de uygulanabilir olmalıdır.

 

 

Bunlar gerçekleştirilmesi çok zor gerekliliklerdir bu yüzden, açık anahtarlı kriptografi fikrinin ileri sürüldüğünden bu yana geçen yıllar süresince sadece tek bir algoritma geniş bir kitle tarafından kabul edilmiştir.

 

Bu kadar zor gerekliliklerin istenmesinin sebeplerini açıklamadan önce en önemli noktayı, tek yönlü fonksiyonu (one-way function) açıklayalım. Söz konusu olan tek yönlü fonksiyon şöyledir: fonksiyonun bire-bir olduğu bir aralıkta, tersini hesaplamak imkansız iken, fonksiyonun kendisinin hesaplanması kolaydır.

 

çok kolay,

imkansız...

 

Genellikle, "kolay" dan kasıt, fonksiyonun girdi uzunluğuna bağlı olarak polinomal bir zaman süresi içerisinde çözülebilir olmasıdır. Şöyle ki, eğer girdi uzunluğu bit kadarsa, fonksiyonun hesaplanması için gereken süre bir sabit sayı iken, gibi bir fonksiyonla orantılı olmalıdır. Çoğu algoritmanın, P sınıfı algoritma olduğu söylenir. "imkansız" ise, oldukça bulanık bir durumu ifade etmek için kullanılır. Bir problemin çözümünün olanaksız olduğundan, giriş büyüklüğüne bağlı olarak çözüm için harcanan çabanın, polinomal zamandan daha hızlı arttığı durumda bahsedebiliriz. Örneğin, girdi bit ile gösterilirken, fonksiyonun çözülme zamanı gibi bir fonksiyona bağlı olarak artıyorsa, bu fonksiyonun çözümünün imkansız olduğunu düşünebiliriz. Ne yazık ki, eğer bir algoritma parçası bu kompleksliği barındırıyorsa, bu karışıklığı belirlemek zordur. Ayrıca , hesapsal kompleksliğin geleneksel fikirleri bir algoritmanın kompleksliğini en kötü duruma yada ortalama bir duruma odaklar. Bu oranlar kriptografi için değersizdir. Çünkü kriptografide bir fonksiyonu tüm girilenler için tersine çevirmek nerdeyse olanaksızdır, bu genelleme, en kötü durum yada ortalama durum için geçerli değildir.

 

Şimdi, bir taraftan hesaplanması kolay, diğer bir taraftan ise belirli ek bilgiler bilinmedikçe hesaplanması olanaksız olan tuzak kapılı tek yönlü fonksiyonun (trap-door one-way function) açıklanmasına bakalım. Polinominal zamanda fonksiyonun tersi ek bilgiyle hesaplanabilir. Adım-adım özetleyebiliriz: Tuzak kapılı tek yönlü fonksiyon, tersine çevrilebilir fonksiyonların () bir ailesidir. Şöyle ki;

 

 

ve biliniyorsa, kolay

* ve biliniyorsa, kolay

biliniyor fakat * bilinmiyorsa çözülemez

 

 

Böylece, uygulamalı genel anahtarın yapısının gelişimi uygun bir tuzak kapılı tek yönlü fonksiyon bulunuşuna bağlıdır.

 

 

Açık Anahtarlı Kripto Analiz

 

Brute-force saldırısına karşı (Brute-force saldırısı, anahtar uzayının tüm elemanlarının sırası ile algoritma içerisinde teker teker denenmesi yolu ile doğru anahtarı elde etmeye çalışmaktır), bir genel anahtarlı şifreleme yapısı geleneksel şifreleme yapıları ile aynı derecede savunmasızdır. Çözüm aynıdır: Geniş anahtar uzayı kullanmak. Bununla birlikte, hesaba katılan bir trade-off vardır. Açık anahtarlı kripto sistemler, bazı kısa, tersine dönüştürülebilir matematiksel fonksiyonların kullanımına bağlıdır. Bu fonksiyonların hesabının karışıklığı, anahtardaki bitlerin sayısıyla doğrusal olarak ölçülemeyebilir; ancak karışıklık daha hızlı artar. Anahtarın büyüklüğü, brute-force saldırısını makul olanaklılık derecesinin dışına çıkarmak için yeterince büyük olmalıdır. Aynı zamanda da pratik şifreleme ve de-şifreleme için yeterince küçük olmalıdır. Pratikte, önerilmiş olan anahtar büyüklükleri brute-force saldırısını olanaksız kılar (Elbette bu hesaplama teknolojilerindeki hızlı gelişime bağlı olarak göreceli bir durumdur). Ancak, sonuçta şifreleme ve de şifreleme hızları genel amaç kullanımı için çok yavaş olur. Gizli anahtarlı simetrik şifrelemenin açık anahtarlı şifrelemeye nazaran çok daha hızlı olmasından ötürü, açık anahtarlı şifreleme yaygın olarak anahtar yönetimi ve imza kullanımlarında sınırlandırılır.

 

Saldırının diğer bir şekli; özel anahtarı hesaplamanın bir yolunu bulmak için, verilen genel anahtarı kullanmaktır. Şu ana dek, bir genel anahtarlı algoritma parçacığı için bu tip bir saldırının başarılı olmasının mümkün olmadığı matematiksel olarak ispatlanmamıştır. Böylece, verilen herhangi bir algoritma (geniş çapta kullanılan RSA algoritmalarını içeren) şüphelidir. Kriptonalizin tarihi, bütünüyle farklı bir yönden bakıldığında çözümü bulunabilecek, bir yönden de çözümsüz gibi gözüken bir problemin varlığını gösterir.

 

Son olarak, genel anahtarlı sistemler için tuhaf bir saldırı şekli daha vardır. Özünde bu saldırı bir olası-mesaj saldırısıdır. Varsayalım ki; 56 bitlik DES anahtarıyla gönderilmek üzere oluşturulmuş bir mesaj olsun. Bir saldırgan, genel anahtarı kullanarak olası tüm anahtarları şifreleyebilir ve herhangi bir mesajı gönderilmiş şifreli metinle karşılaştırarak deşifre edebilirdi. Böylece genel anahtarlı yapının anahtar büyüklüğünün önemi kalmaz, saldırı 56 bitlik bir anahtara yapılan brute-force saldırısına dönüştürülürdü. Bu saldırı; bu gibi basit mesajlara rasgele bazı bitler eklenerek, önlenebilir.

 

 

RSA ALGORİTMASI

 

Diffie ve Hellman tarafından hazırlanmış öncü bir makale 1976 yılında, kriptografi için yeni bir yöntem tanıttı, ve sonuçta, genel anahtarlı sistemlerin gerekliliklerini yerine getiren bir kriptografik algoritmada görüş birliğine varan kriptolojistlere karşı meydan okudu. Bu meydan okumaya karşı yanıtlardan ilki; 1977'de MIT'de Ron Rivest, Adi Shamir, ve Len Adleman (RSA) tarafından ortaya atıldı, ve ilk olarak 1978'de (A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, February 1978) basıldı. Rivest-Shamir-Adleman (RSA) yapısı; üstünlüğü kabul gördüğünden itibaren, geniş çapta tek olarak kabul edildi ve genel anahtarlı şifreleme yönteminin genel amacını yerine getirdi.

 

RSA yapısı, birtakım `ler için ve arasındaki tamsayılardan oluşan şifreli ve düz metinin içinde yer alan bir blok şifrelemedir. Bu bölümde RSA`yı bazı detaylarla birlikte, algoritmanın açıklamasıyla başlayarak inceleyeceğiz. Daha sonra RSA`nın hesapsal ve kripto analitik anlamlarını incelemeye çalışacağız.

 

Algoritmanın Tanımı

 

Rivest, Shamir, ve Adleman tarafından bulunan yapı, destekleyici görüşlerle birlikte ifadenin kullanımını meydana getirir. Düz metin, blokların içinde şifrelenir. Her blok, birtakım sayısından daha az bir ikili değere sahiptir. Bloğun büyüklüğü, `e eşit yada ondan daha az olmalıdır; pratikte, blok büyüklüğü bittir, aralığında. Şifreleme ve de şifreleme bazı düz metin bloğu ve şifreli metin bloğu için şu şekildedir:

 

 

 

Hem gönderen hem de alıcı `in değerini bilmelidir. Gönderen `nin değerini bilir, ve sadece alıcı `nin değerini bilir. Böylece; bir genel anahtar, ve bir özel anahtar olur ve bu bir genel anahtarlı şifreleme algoritmasıdır. Genel anahtarlı şifreleme için tatmin edici olması için, bu algoritma için aşağıdaki gereklilikler yerine getirilmelidir:

 

1. olduğu koşulda, iken, değerlerini bulmak mümkün olmalıdır.

 

2. koşulunu sağlayan tüm değerleri için, ve hesaplanması nisbeten kolay olmalıdır.

 

3. Yalnız ve verildiğinde, `nin hesaplanması imkansız olmalıdır.

 

 

Şimdi, ilk sorun üzerinde odaklanalım ve diğerlerine sonra geçelim. Aşağıdaki form için bir ilişki bulmamız gerekiyor:

 

 

Euler`in teoremine göre, verilen iki asal sayı p ve q, ve iki tamsayı n ve m olmak üzere, ve olduğu durumda, keyfi seçilmiş bir tamsayısı seçilmiş sayılar ile şöyle bir ilişki oluşturur:

 

 

Buradaki fonksiyonunun döndürdüğü değer, `den küçük olan ve ile aralarında asal olan tam sayıların sayısıdır. ve asal sayı olmak üzere olur (Bunun ispatı konumuzun dışındadır, bu yüzden burada yapılmayacaktır). Böylece aşağıdaki eşitlik sağlanıyorsa istenilen ilişkiye ulaşabiliriz:

 

 

Bu durumda aşağıdaki denkliklerden söz edilebilir:

 

 

* ve , `in çarpmaya göre tersidir. Dikkat edecek olursak, modüler aritmetiğin kurallarına göre, bu denkliğin doğru olması yalnız `nin (ve sonucunda `nin) ile aralarında asal olması durumunda mümkündür. Bu durumda, gcd( , ) = 1 demektir.

 

Şimdi, RSA yapısını açıklamaya hazırız. Yapının bileşenleri sırasıyla şöyledir (parantez içlerinde, sayıların nasıl elde edildiklerini ve genel mi yoksa gizlimi olduklarını belirtilmektedir):

 

; iki asal sayı (gizli, seçilmiş)

;(genel, hesaplanmış)

*; gcd( , ) = 1; olacak şekilde (genel, seçilmiş)

; (gizli, hesaplanmış)

 

 

* çifti özel anahtarı, çifti ise genel anahtarı oluşturur. Varsayalım ki, bir kullanıcısı, kullanıcısına, kullanıcısının genel anahtarını kullanarak bir mesajını göndermek istiyor. Bu durumda , formülü yardımı ile şifreli mesajını elde edecek ve bunu `ya gönderecektir. kullanıcısı bu mesajı aldığında, formülü ile mesajı de şifre edecektir.

 

Bu kıymetli algoritmanın doğrulunu özetlemek için biraz sıkıntıya girmeye değer :) Biz, ve `yi aşağıdaki denkliği sağlayacak şekilde seçmiştik:

 

Bunun sonucunda,

 

 

Bu yüzden , `in bir formudur. Bu denkliğin Euler teoreminin bir sonucu olduğu, iki asal sayı olan ve , birer tamsayı olan () ve () alınarak kolaylıkla ispatlanabilir.

 

 

Dolayısıyla görüyoruz ki, ;

 

 

Şekil 5
 
 

 

 

 


Şekil 5`te, RSA algoritması özetlenmiştir. Ve Şekil 6` da da bir örnek vierlmiştir ve bu örnekteki anahtarlar şu şekilde yaratılmıştır (siz de kağıt üstünde kendi seçtiğiniz sayılar ile deneyiniz):

 

1.     İki adet asal sayı seçelim, ve

2.     değerini hesaplayalım,

3.     değerini hesaplayalım,

4.     Şimdi de, `den küçük olacak ve ile aralarında asal olacak şekilde bir sayısı seçelim, burada olsun…

5.     Son olarak, öyle bir belirleyelim ki, ve olsun. Doğru değer, olacaktır. Çünkü, `dir.

 

Şekil 6
 
 

 

 


Bu işlemler sonucunda elde ettiğimiz değerlere göre genel anahtar , özel anahtar da oldular. Bu örnek bize, bu anahtarların düzmetni için kullanımını gösteriyor. Şifreleme için, un beşinci kuvveti alınıyor ve sayısı elde ediliyor. Daha sonra bu sayının `a bölümünden kalan bulunuyor ve ortaya şifreli metin olan çıkıyor. Deşifreleme işleminde de, işlemi sayesinde de şifrelenmiş metin olarak 19 elde ediliyor.

 

Hesaplama Yöntemleri

 

Şimdi, RSA`nın kullanımı için gerekli hesabın karışıklığıyla ilgili önemli noktaya geri dönüyoruz. Aslında düşünülmesi gereken iki önemli nokta vardır: anahtar üretimi, şifreleme/deşifreleme. Önce şifreleme/deşifreleme işlemlerine bakmaya çalışacak ve daha sonra anahtar üretimi konusuna döneceğiz.

 

 

Şifreleme ve Deşifreleme

 

RSA`da hem şifreleme hem de deşifreleme, tamsayıların tamsayı kuvvetlerini almayı ve mod alma işlemlerini gerektirir. Eğer ilk önce tamsayıların üslerini alıp, daha sonra ile indirgersek, ara değerler devasa büyüklükte sayılar olurlar. Neyse ki bu sorunu bir nebze azaltmak için modüler aritmetiğin şu özelliğinden yararlanabiliriz:

 

 

Bu sayede, ara değerleri modül `e göre indirgeyebiliriz. Bu da hesaplamayı pratik hale getirir.

 

Diğer bir husus, üssün verimidir. Çünkü, RSA ile, potansiyel olarak büyük üsler ile işlem yaparız. Verimin nekadar artabiliceğini görmek için, `yı hesaplamak istediğimizi varsayalım. Dürüst bir yöntem 15 çarpım gerektirir:

 

 

Bununla birlikte, aynı sonuca, her bir kısmi sonucun karesini alarak olacak şekilde dört adımda da ulaşabiliriz.

 

Daha genel olarak varsayalım ki biz değerini hesaplamak istiyoruz ve biliyoruz ki ve birer pozitif tam sayı. Eğer biz `i gibi ikilik sayı gibi ifade edecek olursak:

 

olur.

 

Böylece,

 

 

 

 

 

olur.


Bu sonuç sayesinde, işlemini hesaplamak üzere aşağıdaki algoritmayı geliştirebiliriz. Ve algoritmanın altındaki tablo da algoritmanın çalışmasını örneklemektedir. değerinin aslında gerekli olmadığını düşünebilirsiniz; gerçekten de algoritma içerisinde direk bir fonksiyonu yoktur. Fakat son değeri üssün değerine eşit olacağından dolayı açıklayıcı bir niteliktedir.

 

c0; d1

for ik downto 0

     do c2 x c

          d(d x d)mod n

          if bi=1

               then cc+1

                    d(d x a)mod n

return d

 

 

9

8

7

6

5

4

3

2

1

0

1

0

0

0

1

1

0

0

0

0

1

2

4

8

17

35

70

140

280

560

7

49

157

526

160

241

298

166

67

1

 

 

 

Anahtar Üretimi

 

Açık anahtarlı kriptosistemin uygulamasından önce, her iki katılımcı anahtar parçalarını üretmelidir. Bu üretim işlemi aşağıdaki vazifeleri ihtiva eder:

 

·                   İki asal sayı hesaplanması, ve

·                   ya da `nin seçilip diğerinin hesaplanması.

 

Öncelikle, ve nun seçimini düşünelim. Çünkü, herhangi bir potansiyel saldırgan `nun değerini biliyor olacaktır, ayrıntılı methodlarla ve nun bulunmasını engellemek için, ve sayıları yeterince büyük bir seriden seçilmiş olmalıdırlar ( ve büyük sayılar olmalıdır). Diğer bir yandan, büyük asal sayıları bulmak için kullanılan yöntem yeterince verimli olmalıdır.

 

Günümüzde, verimli ve büyük asal sayılar üreten kullanışlı bir teknik yoktur. Genel olarak kullanılan yöntem şöyle çalışmaktadır: istenen büyüklük aralığında rastgele bir tek sayı seçilir ve bunun asal olup olmadığını kontrol edilir. Eğer asal değilse, bu işlem asal bir sayı buluncaya kadar sürdürülür.

 

Asallığı kontrol eden bir çok test geliştirilmiştir. Testlerin nerdeyse tümü yaklaşıklıktan bahseder yani, test, verilen (yeterince büyük) bir tam sayının muhtemelen asal olup olmadığını belirleyecektir. Bu kesinlik eksikliğine karşın, testler, sayının asal olma olasılığının 1,00`a çok yakın olduğu durumlarda çalışabilirler. Örnek olarak, en verimli ve popüler test algoritmalarından birisi Miller-Rabin algoritmasıdır. Bu algoritmada ve diğer bir çok algoritmada, sayısının asallığını kontrol etmek için, ile bir takım işlemlere sokulmak üzere den küçük bir rastgele sayısı seçilir. Eğer testi geçemezse bunun anlamı sayısının asal olmadığıdır. Eğer testi geçerse bu durumda sayı asal olabilir, olmayadabilir. Eğer sayısı bu gibi çok fazla sayıda (milyonlarca..) testten başarılı olursa, için muhtemelen asal denilir.

 

Özet olarak, asal sayı kontrol prosedürü aşağıdaki adımları izler:

 

1.     Rastgele bir tek tam sayı "" seçilir.

2.     koşulunu sağlayan bir rastgele bir sayısı seçilir.

3.     için asallığı yaklaşık olarak test eden Miller-Rabin gibi bir test gerçekleştirilir, eğer testi geçemezse birinci adıma geri dönülür.

4.     Eğer