Sıra | DOSYA ADI | Format | Bağlantı |
---|---|---|---|
01. | Şifrelemeye Giriş | pptx | Sunumu İndir |
Transkript
Understanding Cryptography – Öğrenci ve Uygulamacılar İçin Ders kitabıwww.crypto-textbook.comÜnite1 – Şifrelemeye GirişÇeviren: Selman YAKUT
2/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
3/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
4/36• Şifreleme hakkında daha çok okuma ve bilgiAddition to Understanding Cryptography .• A.Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography.CRC Press, October 1996.• H.v.Tilborg (ed.), Encyclopedia of Cryptography and Security, Springer, 2005History of Cryptography (great bedtime reading)• S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor, 2000.• D. Kahn, The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. 2nd edition, Scribner, 1996.Software (excellent demonstration of many ancient and modern ciphers)• Cryptool, http://www.cryptool.de
• Şifreleme alanlarının sınıflandırılmasıCryptologyCryptography CryptanalysisSymmetric CiphersAsymmetric CiphersProtocolsBlock Ciphers Stream Ciphers5/36
6/36• Bazı temel gerçekler• İlk çağ şifreleme: ilk şifreleme işaretleri M.Ö. 2000 mısırda kahirede görülmüştür. Harf-tabanlı şifreleme yapısı (örneğin sezar şifreleme) ondan sonra popülerleşti.• Simetrik şifreleme: Tarihöncesi zamanlardan 1976 ya kadar olan bütün şifreleme yapıları buna örnektir.• Asymmetric ciphers: 1976'da açık anahtar (veya asimetrik) şifreleme Diffie, Hellman ve Merkle tarafından açık bir şekilde önerildi.• Karışık yapılar: günümüz protokollerinin büyük bir kısmı bu yapıdadır, örneğin ikisini kullanan• Simetrik şifreleme (örneğin şifreleme ve mesaj doğrulama için) ve• Asimetrik şifreleme (örneğin; mesaj değişimi ve sayısal imza için).
7/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
• Symmetric CryptographyAlternatif isimler: özel anahtarlı, tek anahtarlı veya gizli anahtarlı şifreleme.Oscar (bad guy)Unsecurechannel(e.g. Internet)8/36Alice (good)Bob (good)x x• Problem Statement:1)Alice ve BOB güvenli olmayan kanal üzerinden haberleşmek istiyorlar (örneğin, WLAN or Internet).2) kötü niyetli üçüncü kişi olan Oscar kanala ulaşabilir fakat fakat haberleşmeyi anlayamamalı.
• Symmetric CryptographyAlice (good)Bob (good)Oscar (bad guy)Encryption e( )Key GeneratorDecryption d( )Secure ChannelKx yKxUnsecure channel(e.g. Internet)9/36• x düz metin• y şifreli metin• K anahtar değeri• Bütün anahtar değerleri {K1, K2, ...,Kn} anahtar uzayıdırÇözüm: simetrik şifre ile şifrelemektir.⇒ Oscar sadece şifreli metni elde edebilir buda rastgele bit dizisidir.y
• Simetrik şifreleme• Şifreleme denklemi• Şifre çözme denklemi10/36y = eK(x) x = dK(y)• önemli: anahtar Bob ve Alice arasında güvenli bir kanaldan iletilmeli.• Güvenli kanal kurye veya benzeri yöntemlerle oluşturulabilir.• Bununla birlikte saldırgan K anahtar değerini bilmediği sürece güvenlidir. ⇒ güvenli haberleşme problemini güvenli iletim ve Kanahtar değerinin saklanması azaltmaktadır.• İki tarafta da aynı anahtar değeri kullanılıyorsa şifreleme ve şifre çözme işlemleri birbirinin tersidir:dK(y) = dK(eK(x)) = x
11/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
• Neden kripto analize ihtiyaç duyarız?• Herhangi pratik bir şifre için güvenliğin matematiksel bir kanıtı yoktur.• Sistemin güvenli olduğunu garanti etmenin tek yolu sistemi kırmaya çalışmaktır!Kerckhoff prensibi modern şifrelemede çok iyidir:Saldırgan gizli anahtar dışında sistemle ilgili her şeyi biliyor olsa bile şifreleme sistemi güvenli olmalıdır .• Kirşof prensiplerini pratikte uygulayabilmek için:Sadece iyi şifreleyiciler tarafından birkaç yıl kriptoanaliz edilmiş geniş bir ölçekte kullanılan şifreler kullanılmalı! (Understanding Cryptography only treats such ciphers)• dikkat: şifrelemenin daha güvenli olması için şifreleme yapısının detaylarını gizlemek daha cazip gelebilir. Bununla beraber, fakat zaman gösteriyor ki bu yapılar mühendisler tarafından incelendiğinde her zaman kırılmıştır. (örneğin: DVD içeriğini korumak için kullanılan program Content Scrambling System (CSS).)12/36
• Şifre Analizi: Şifreleme Sistemlerine Saldırı• Klasik saldırılar• Matematiksel analiz• Kaba kuvvet saldırısı• Uygulama saldırıları: Ters mühendislikle veya güç ölçümüyle anahtar değerini çıkarmaya çalışırız, örneğin bankalar için kullanılan banking smart card.• Sosyal mühendislik: örneğin kullanıcının şifresini vermesi için kandırmak13/36
• Şifreye blok kutular gibi davranır.• En az bir düz metin şifreli metin çifti (x0, y0) gerekir.• Şart gerçekleşene kadar bütün mümkün anahtarları kontrol eder:dK(y0) = x0• Kaç türlü anahtara ihtiyaç duyarız ?• Simetrik Şifrelemeye Karşı Kaba Kuvvet Saldırısı14/36?Önemli: karşı taraf başarmak için sadece bir saldırıya ihtiyaç duyar. Böylece, sosyal mühendislik gibi diğer saldırılar yapılabiliyorsa uzun anahtar uzayı pekte faydalı olmayacaktır..Key length in bitKey space Security life time(assuming brute-force as best possible attack)64264Short term (few days or less)1282128 Long-term (several decades in the absence of quantum computers)2562256 Long-term (also resistant against quantum computers – note that QC do not exist at the moment and might never exist)
15/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
16/36• Yer Değiştirmeli Şifreleme• Tarihsel şifreleme• Kaba kuvvet vs analitik saldırıları anlamak için harika bir araç• İkinci dünya savaşına kadar bitlerden ziyade harflere dayanan şifreler kullanılıdı.fikir: düz metindeki her bir harfe şifreli metinde sabit bir harfle yer değiştirsin.örneğin, ABBA kddk gibi şifrelenebilir• örnek (şifreli metin):iq ifcc vqqr fb rdq vfllcq na rdq cfjwhwzhwwhbsqvqbre hwq vhlqhr bnnb hcc• Yer değiştirmeli şifreleme ne kadar güvenlidir? Saldırılara bakalım…Plaintext CiphertextA B Ck d w....
17/36• Yer değiştirme şifrelemeye karşı saldırılar1. Saldırı: sonsuz anahtar arama (kaba kuvvet saldırısı)• Basitçe mantıklı bir düz metin elde edilene kadar bütün mümkün yer değiştirmelerin yapılması (dikkat edin ki yer yer değiştirme bir anahtardır)..• How many substitution tables (= keys) are there?26 x 25 x … x 3 x 2 x 1 = 26! 288288 Anahtar arasından değerleri araştırmak günümüz bilgisayarları için mümkün değildir!• S: kaba kuvvet saldırısı mümkün olmadığı için yer değiştirme şifresinin güvenli olduğunu çıkarabilir miyiz?• A: hayır! Bütün saldırılara karşı güvenli olmalıdır…
• 2. saldırı: harf frekanslarının analizi (kaba kuvvet saldırısı)E T A O I N S H R D L C U M W F G Y P B V K J X Q Z0.00002.00004.00006.00008.000010.000012.000014.0000• İngilizcede harflerin farklı kullanım sıklığı vardır.• Dahası: düz metindeki sıklık şifreli metinde de korunur.• Örneğin, „e“ ingilizcede en çok kullanılan harftir; tipik bir ingilizce metindeki harflerin 13% „e“ dir.• Diğer en çok kullanılan harf yaklaşık 9% la t’ dir.İng i l i zcede ke l ime s ık l ık la r ı18/36LettersFrequency in %
19/36• Harf sıklıkları analiziyle yer değiştirme şifrelerinin kırılması• Şimdi örneğimize dönüp en çok geçen harfi bulalım:iq ifcc vqqr fb rdq vfllcq na rdq cfjwhwz hr bnnb hcc hwwhbsqvqbre hwq vhlq• Şimdi şifreli metinde q'nun yerine E yazalım :iE ifcc vEEr fb rdE vfllcE na rdE cfjwhwz hr bnnbhcc hwwhbsEvEbre hwE vhlE• Kalan harflerin sıklığına dayanarak daha fazla tahmin yapılır ve düz metin bulunur:WE WILL MEET IN THE MIDDLE OF THE LIBRARY AT NOON ALL ARRANGEMENTS ARE MADE
20/36• Harf sıklıkları analiziyle yer değiştirme şifrelerinin kırılması• Pratikte, sadece harflerin değil ingilizcede sık kullanılan kelime ikilileri ve üçlüleri de şifreli metni çözmek için kullanılır. • Problem 1.1 in Understanding Cryptography kitabın ilgili metnindeki şifreli metni kırmaya çalışabilirsiniz! önemli ders: yer değiştirmeli şifre 288 gibi yeterli büyüklükte anahtar uzayına sahip olmasına rağmen, sayısal yöntemlerle kolaylıkla kırılabilir. Bu şifreleme yapılarının bütün saldırılara karşı dayanıklı olması gerektiğini gösteren çok güzel bir örnektir.
21/36Ünite içeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
22/36• Modüler aritmetiğe kısa bir girişNeden modüler aritmetik çalışmaya ihtiyacımız var?• Asimetrik şifreleme için çok önemlidir (RSA, elliptic curves gibi.)• Bazı tarihsel şifreler modüler aritmetikle güzel bir şekilde ifade edilebilir(örneğin Caesar and affine cipher later on).
• Modüler aritmetiğe kısa bir giriş1211 12347 568910Genel konuşursak, birçok şifreleme sistemi sayı kümelerine dayanır şöyle ki 1. ayrı (sayılı kümeler oldukça faydalıdır)2. sonlu (ör. sadece sonlu sayılarla hesaplayabilirsek)23/36 çok mu soyut gözüküyor? --- şimdi sonlu kümelere ayrık sayılarla bakalım saate oldukça aşinayızdır. Enteresan bir şekilde, saat sürekli artmasına rağmen biz belli bir sayı kümenin dışına çıkmayız:1, 2, 3, … 11, 12, 1, 2, 3, … 11, 12, 1, 2, 3, …:
• Modüler aritmetiğe kısa bir giriş• Let a= 12 and m= 9 :• Let a= 37 and m= 9:• Let a= -7 and m= 9:12 ≡ 3 mod 934 ≡ 7 mod 9-7 ≡ 2 mod 9• saate bulunan (1,2,3, … ,12) gibi sayılarla sonlu bir kümeyi hesaplamak için bir aritmetik sistem geliştirelim.• Çarpma ve toplama gibi işlemlerden sonra elde edilen sayıların yine küme içerisinde kalması çok önemlidir. (örneğin asla 12 den büyük olamaz).Definition: Modulus OperationLet a, r, m be integers and m > 0. We writea ≡ r mod mif (r-a) is divisable by m.• “m” is called the modulus• “r” is called the remainderModüler azalma için bir örnek.24/36
25/36• Modüler aritmetiğin özellikleri• Kalan tek değildirŞurası ilginçtir ki verilen bir mod m’de kalan a değerine karşılık sonsuz değer denk gelmektedir.örneğin:• 12 ≡ 3 mod 9• 12 ≡ 21 mod 9• 12 ≡ -6 mod 9→ 3 geçerli kalandır çünkü 9 böler (3-12)→ 21 geçerli kalandır çünkü 9 böler(21-12)→ 6 geçerli kalandır çünkü 9 böler (-6-12)
• Hangi kalanı seçmeliyiz?Genel olarak, en küçük pozitif sayı r yi alırız. Bu sayı şöyle hesaplanabilir:quotienta = q m + r• Example: a=12 and m= 912 = 1 x 9 + 3remainderwhere 0 ≤ r ≤ m-1→ r = 3dikkat: This is just a convention. Algoritmik olarak şifreleme fonksiyonumuzu hesaplamak için herhangi bir geçerli kalan kümesini almakta serbestiz .• Modüler aritmetiğin özellikleri26/36
27/36• Modüler bölme işlemi nasıl yapılır?İlk olarak, şunu belirtelim ki, bölme yapmaktan çok tersini alarak çarpmayı tercih ederiz. Ex:b / a≡ b x a-1 mod ma-1 sayısı a sayısının tersidir ve şöyle tanımlanır:a a-1 ≡ 1 mod mEx: 5 / 7 mod 9 nedir ?mod 9 da 7 nin tersi 4 çünkü 7 x 4 ≡ 28 ≡ 1 mod 9, böylece:5 / 7 ≡ 5 x 4 = 20 ≡ 2 mod 9• Modüler aritmetiğin özellikleri• Ters hesaplama nasıl yapılır?a sayısının mod m d tersi vardır eğer sadece ve sadece:gcd (a, m) = 1(yukarıdaki örneğe dikkat edildiğinde gcd(5, 9) = 1, bundan dolayı modulo 9 da 5 in tersi vardır)Understanding Cryptography kitabının 6. ünitesinde bu konu daha ayrıntılı anlatılmıştır.
• Modüler aritmetiğe cebirsel bakış: halka Zm We can view modular arithmetic in terms of sets and operations in the set. By doing arithmetic modulo m we obtain the integer ring Zm .with the following properties:28/36• Kapatma: herhangi iki sayıyı toplayıp çarpabiliriz sonuç yine halka içindedir .• Toplama ve çarpmada birleşme özelliği vardır ör: a,b,c Zm için a + (b + c) = (a + b) + c a (b c) = (a b) cVe toplamada değişim özelliği de vardır: a + b = b + a• dağılma kuralı : a×(b+c) = (a×b)+(a×c) şeklindedir a,b,c Zm toplama için etkisiz eleman sıfırdır, i.e., for all a Zm a + 0 a mod m• Zm, her zaman toplamaya göre tersi –a vardır. Şöyle ki a + (-a) 0 mod m• çarpmaya göre etkisiz eleman 1 dir, örneğin a Zm içina 1 a mod m• çarpmaya göre ters a-1a a-1 1 mod m Zm deki bazı değerler için vardır hepsi için olmayabilir.
• Modüler aritmetiğe cebirsel bakış: halka Zm Kısaca, halka üzerinde toplama çıkarma çarpma işlemlerini yapabildiğimiz bir yapıdır fakat sadece bazı elemanları bölebiliriz (yani çarpmaya göre tersi olanları).• Eğer sadece : gcd (a, m) = 1 ise Zm deki bir sayının çarpmaya göre tersi vardır. o zaman a ve m nin aralarında asal olduğunu söyleyebiliriz.• Ör: şu halkaya dikkat edersek Z9 = {0,1,2,3,4,5,6,7,8}0, 3 ve 6 nın tersi yoktur çünkü bu sayılar 9 la aralarında asaldır. Diğer elemanların tersi ise şu şekildedir:29/361-1 1 mod 9 2-1 5 mod 9 4-1 7 mod 95-1 2 mod 9 7-1 4 mod 9 8-1 8 mod 9
30/36Ünite İeriği• Şifreleme alanlarına genel bakış • Simetrik şifrelemenin temelleri• Kripto analiz• Yer değiştirmeli şifreleme• Modüler aritmetik• Kaymalı (veya sezar) şifreleme ve Affine şifreleme
31/36• kaymalı (veya Sezar) şifreleme •İlk şifrelerin Julius Caesar tarafından kullanıldığı iddia edilir.• Düz metindeki her harfin yerine bir harf yazılır.•Değişim kuralı oldukça basit: belirlenen bir k anahtar değeriyle her harften k:sonraki harf alınır.• Örnek k = 7 içinDüz metin = ATTACK = 0, 19, 19, 0, 2, 10Şifreli metin = haahr = 7, 0, 0, 7, 17Burada işlemler mod 26 da yapılmaktadır yani 26 değerini aşan durumda mod 26 daki değeri alınır.A B C D E F G H I J K L M0 1 2 3 4 5 6 7 8 9 10 11 12N O P Q R S T U V W X Y Z13 14 15 16 17 18 19 20 21 22 23 24 25
• Kaymalı (veya Sezar) Şifreleme • S; kaymalı şifre güvenli midir?• C: Hayır! Birkaç saldırı mümkün, including:• Sonsuz anahtar arama (anahtar uzayı sadece 26!)• Harf sıklığı analizi, yer değiştirme şifresinde olduğu gibi• Şifrelemenin zekice matematiksel tarifi.Let k, x, y ε {0,1, …, 25}32/36• Encryption:• Decryption:y = ek(x) ≡ x + k mod 26 x = dk(x) ≡ y - k mod 26
• Affine Şifreleme • Şifreleme işleminde tersini almaya ihtiyaç duyduğumuz için, aşağıdaki ifadeye göre sadece tersi olan sayılar kullanılır:gcd(a, 26) = 1 bu şartı sağlayan 12 değer vardır.• Bundan dolayı anahtar uzayı sadece 12 x 26 = 312 (cf. Sec 1.4 in Understanding Cryptography)• Yine aşağıdakileri içeren birkaç saldırı vardır:• Detaylı anahtar uzayı ve harf sıklığı analizi, yer değiştirme şifresine karşı benzer saldırılar.• Kaymalı şifrenin gelişmiş hali: düz metne sadece anahtar değerini eklemekten ziyade, başka bir anahtar değeriyle de toplarız.• Burada iki parçadan oluşan bir anahtar değeri kullanırız : k = (a, b)Let k, x, y ε {0,1, …, 25}33/36• Encryption:• Decryption:y = ek(x) ≡ a x + b mod 26x = dk(x) ≡ a-1( y – b) mod 26