MAT106U-MATEMATİK-II
Ünite 7: Şifreleme Kuramına Giriş
Doğrusal Şifreleme
a ve b tamsayılar, n ise birden büyük bir doğal sayı olsun.
Doğrusal şifreleme ş 𝑥 = 𝑎𝑥 + 𝑏 (mod 𝑛) formülü ile verilir. a ve b sayıları negatif de olabilir. Doğrusal şifrelemede n sayısı a ile aralarında asal olan herhangi bir doğal sayı olabilir. Çoğu zaman n asal sayı olarak alınır. a ile n’in aralarında asal olması 𝑎𝑥 ≡ 1 (mod 𝑛) denkleminin x çözümünün olması için önemlidir. x sayısı uzunluğu n olan bir alfabenin harflerini temsil ettiği için 𝑥 ∈ {0,1, … , 𝑛 − 1} olmalıdır. Deşifre işlemi için ebob 𝑎, 𝑛 = 1 koşulu gereklidir. Bu da 𝑎𝑥 ≡ 1 (mod 𝑛) denklemiyle bağlantılıdır. Burada a tamsayı, n doğal sayı, x ise bilinmeyen bir tamsayıdır. a ve n verildiğinde, ax sayısı n’ye bölündüğünde 1 kalanını veren x tamsayısı aranır. Şifreleme açısından modüler aritmetiğe göre bulunan en küçük pozitif değer x olarak kabul edilir. 𝑎𝑥 ≡ 1 (mod 𝑛) denkleminin çözümü ancak ebob 𝑎, 𝑛 = 1 iken vardır. 𝑎𝑥 ≡ 1 (mod 𝑛) denklemini sağlayan x sayısına a’nın n moduna göre tersi denir. Bu sayı c olarak tanımlanırsa; 𝑎 . 𝑐 ≡ 1 mod 𝑛 . Bir çok yöntemde deşifre işlemi için bir sayının belli bir mod’a göre tersinin alınması işlemi kullanılmaktadır.
ş 𝑥 = 𝑎𝑥 + 𝑏 (mod 𝑛)
doğrusal şifreleme için
𝑑 𝑦 = 𝑐(𝑦 − 𝑏) (mod 𝑛)
deşifre fonksiyonudur, yani gönderilecek sayı ş 𝑥 fonksiyonu yardımıyla şifrelenip, 𝑑 𝑦 yardımıyla deşifre edilir.
𝑥 → ş 𝑥 ≡ 𝑦(mod 𝑛) ≡ 𝑐(𝑎𝑥 + 𝑏 − 𝑏) Gönderici ve alıcının aynı anahtarı kullandığı ya da alıcının anahtarı göndericinin anahtarlarından elde edebildiği şifreleme yöntemlerine simetrik yöntemler denir. Simetrik şifrelemede bu anahtarlar gizli kalmalıdır ve gönderici ile alıcının anahtar konusunda anlaşmaları gerekir. Simetrik şifreleme çok hızlı bir yöntemdir.
Kuvvet Fonksiyonuyla Şifreleme
Kuvvet fonksiyonuyla şifreleme yöntemi asal sayılar ve modüler aritmetiğin aşağıdaki teoremine dayalıdır.
Teorem 𝑝 > 2 bir asal sayı, e ise (𝑝 − 1) ile aralarında asal bir sayı olsun, yani ebob 𝑒, 𝑝 − 1 = 1 koşulu sağlansın. d sayısı, 𝑒 . 𝑑 ≡ 1(mod 𝑝 − 1) koşulunu sağlayan bir sayı ise her M sayısı için
𝑀!" ≡ 𝑀 (mod 𝑝)
denkliği sağlanır.
Bu teoreme dayalı şifreleme fonksiyonu
ş 𝑥 = 𝑥! (mod 𝑝)
deşifre fonksiyonu ise
𝑑(𝑦) = 𝑦! (mod 𝑝)
olur. Gönderici p’den küçük olan M sayısını ş 𝑥 fonksiyonu ile şifreler, alıcı ise aldığı şifreli sayıyı 𝑑(𝑦) ile deşifre edip M’ye ulaşır. Alıcı ve gönderici p,e ve d sayılarını bilmektedir. Şifreleme ve şifreyi okuma işlemi şu şekildedir:
1. Gönderici ve alıcı 𝑝 > 2 asal sayısını, 𝑝 − 1 ile aralarında asal olan e sayısını ve 𝑒 . 𝑑 ≡ 1 (mod 𝑝 − 1) koşulunu sağlayan d sayısını seçerler. 2. Gönderici M sayısını şifreleyip göndermek için
𝑀!(mod 𝑝)
sayısı olan y’yi hesaplar. y şifreli mesajdır, bunu alıcıya gönderir.
3. Alıcı da 𝑦!(mod 𝑝)’yi hesaplayıp M’ye ulaşır.
Kuvvet fonksiyonu kullanılarak yapılan şifrelemelerde şifrelenen mesajı alıcının çözebilmesi için göndericinin ve alıcının şifreleme ve deşifre fonksiyonlarını bilmesi gerekir.
RSA Yöntemi
İlk açık anahtarlı şifreleme sistemi olan RSA, ismini bu yöntemi 1977 yılında bulan üç kişinin soyadlarının birinci harflerinden alır. Bu yöntem, asal sayılar ve modüler aritmetiğin iki önemli teoremine dayalıdır. Yöntemin güvenirliği yani şifrenin kırılamaması ise iki büyük asal sayının çarpımı olan bir sayıyı asal çarpanlarına ayırmanın çok zor olması olgusuna dayalıdır. Yüz basamaklı bir asal sayı:
35324619344027701212726049781984643686711974001 97625023649303468776121253679423200058547956528 088349
Teorem
𝑎𝑥 ≡ 1 (mod 𝑛) denkleminin çözümü ancak ebob 𝑎, 𝑛 = 1 yani a ve n sayıları aralarında asal iken vardır.
Teorem p ve q sayıları farklı asal sayılar, 𝑒 ≥ 1 sayısı ise
ebob 𝑒, 𝑝 − 1 𝑞 − 1 = 1
koşulunu sağlayan bir sayı olsun (yani e ile 𝑝 − 1 𝑞 − 1 sayıları aralarında asal olsunlar). d sayısı
𝑒 . 𝑑 ≡ 1 mod 𝑝 − 1 𝑞 − 1 (7.1)
koşulunu sağlasın. O zaman her M pozitif tamsayısı için
𝑀!" ≡ 𝑀(mod 𝑝𝑞)
sağlanır.
Doğrusal şifrelemede ki teoreme göre ebob 𝑎, 𝑛 = 1 ise 𝑎𝑥 ≡ 1 (mod 𝑛) denkleminin x çözümü vardır. a sayısını e olarak, n sayısını ise 𝑝 − 1 𝑞 − 1 şeklinde düşünürsek 𝑥 = 𝑑 çözümünün varlığı sağlanmış olur. M sayısını karşı tarafa göndermek için 𝑀!(mod 𝑝𝑞)
hesaplanır. Bunu y olarak tanımlarsak, y sayısı şifrelenmiş sayıdır. y sayısı alıcıya gönderilir. Alıcı da
𝑦!(mod 𝑝𝑞)
ifadesini (yani y’nin d. kuvvetini alıp pq sayısına bölümünden kalanı) hesaplayıp gerçek M sayısına ulaşır. Çünkü teoreme göre
𝑦! ≡ 𝑀! ! ≡ 𝑀!" ≡ 𝑀 mod 𝑝𝑞 .
RSA yönteminin çalışma prensibi şöyledir:
1. Önce alıcı iki tane farklı p ve q asalları seçip onların N çarpımını hesaplar: 𝑁 = 𝑝. 𝑞 . Sonra 𝑝 − 1 𝑞 − 1 ile aralarında asal olan e sayısı belirlenir. p ve q gizli tutulmasına karşın (N,e) ikilisi alıcının açık adresi olarak ilan edilir. 2. Gönderici göndereceği M sayısını şifrelemek için N ve e sayılarını kullanır ve
𝑦 ≡ 𝑀! mod 𝑁
sayısını hesaplar. Yani 𝑀! kuvvetinin N’ye
bölümünden kalanı hesaplar. Artık y şifreli sayı olur.
3. Gönderici y’yi açık biçimde kimseden saklamadan herhangi bir yolla alıcıya gönderir. Alıcı
𝑒. 𝑑 ≡ 1 mod 𝑝 − 1 𝑞 − 1
koşulunu sağlayan en küçük pozitif d sayısını hesaplar. Alıcı bu d sayısını gizli tutar. d’yi hesapladıktan sonra
𝑦! mod 𝑁
sayısını hesaplayıp M’ye ulaşır, çünkü
𝑦! mod 𝑁 ≡ 𝑀.
Bu yöntemde N ve e sayıları açık, p,q ve d sayıları gizlidir. Bunların hepsini alıcı belirler.
Günümüzde RSA şifrelemesi için p ve q sayıları 512 bitlik yani 2!"# sayısına yakın sayılar olarak seçiliyor, bu da
yaklaşık olarak 150 basamaklı asal sayı demektir. Büyük sayıların büyük kuvvetlerinin modlarını hesaplamak için kuvvetlerin kendilerini hesaplamaya gerek yoktur. 𝑀! gibi
bir kuvveti hesaplarken e üssü 2-lik tabanda yazılıp bilgisayarın da yardımıyla kuvvetin modülü kolayca hesaplanır.
Her bir sayı 2-lik tabanda yazılabilir. Örneğin,
45 = 32 + 8 + 4 + 1 Kuvvetlerin modüllerini hesaplamak için kuvvetteki sayı 2-lik tabanda yazılır, sonra üslü sayı çarpanlara ayrılır. Örneğin, 13!" (mod 11) üslü sayısı
!" !!!!!!!! !! !! !! 13 = 13 = 13 . 13 . 13
şeklinde yazılır, sonra
!!! ! ! 13! = 13!
formülünden yararlanılıp modül hesaplanır:
!! ! 13 ≡ 13 ≡ 2 (mod 11) böylece
13!" ≡ 9.5.2
bulunur.
Kelimelerle yazılmış metinleri sayılara dönüştürmek için çeşitli yöntemler vardır. En yaygın olan ASCII denilen sistemdir. Bu sistemde her harfin (hem küçük hem de büyük), her noktalama işaretinin ve her sembolün 0 ve 1’lerden oluşan 8 basamaklı (8 bitlik) bir ifadesi vardır. Şifre metni önce 0 ve 1’lerden oluşan büyük basamaklı bir sayıya dönüştürül, sonra sayı belli uzunluklu (örneğin 64- lük) bloklara ayrılır ve tekrar her blok 10-luk tabana dönüştürülerek sayılar elde edilir.
Geçmişten Günümüze Kriptoloji: Kısa bir özet
Kriptolojinin yazının bulunmasıyla başladığı tahmin edilmektedir. 9. yüzyılda Arap bilim adamı El-Kindi tarafından harflerin frekans analizinin bulunması mevcut şifreleme yöntemlerini güvensiz hale gelmiş ve 16. yüzyıldan başlayarak Vigenere şifresi kullanılmaya başlanmıştı. Böylece frekans analizinin uygulanmasıyla yenilgi yaşayan kriptograflar Vigenere şifresinin bulunmasıyla üstünlük elde ettiler. Ancak 200 yıla yakın güvenle kullanılan bu şifre de 1860 yıllarında kırılmış oldu. 19. yüzyılın bitiminde telsiz keşfedildi ve bu keşif, haberleşmede büyük avantajlar sağlasa da yeni sorunları getirmiş oldu. Kriptanalistler I. Dünya Savaşının kaderinin değişmesinde önemli bir rol oynadılar. Örneğin, o dönem Alman Dışişleri Bakanı Zimmerman’ın Meksika hükümetine 16 Ocak 1917’de gönderdiği telgrafın İngilizler tarafından yakalanıp deşifre edilmesi, o zamana kadar tarafsız olan Amerika’nın savaşa girme nedenlerinden biri oldu. Artık kriptograflar kâğıt kalemle yapılan şifreleme yöntemleri yerine şifre makinalarının bulunması gerekliliğini anladılar. Almanlar tarafından 1920’li yıllarda kullanılmaya başlanan ENIGMA şifreleme makinası bu tür makinalardandı. Bilgisayarın keşfi ve kullanımı şifrelemede bilgisayarların kullanımının yolunu açsa da, yeni güvenlik problemlerini ortaya çıkarmış oldu. DES şifrelemesi, Diffie-Hellman anahtar değşimi algoritması, RSA açık anahtarlı şifreleme sistemi gibi şifreleme yöntemleri bulundu.