Perfect Secrecy

Bir cipher text (CT)’in perfect secrecy’ye sahip olması için ne gerekiyor? 1949’da ABD’li matematikçi Claude Shannon çıkmış ve çok basit bir teorem ortaya atmış. Basit olmasına basit ama oldukça güçlü bir fikir.

perfect_secrecy

 

Yukarıda kısaca anlatılan şey şu: Eğer herhangi farklı ama aynı uzunlukta iki mesaj texti aldığımızda, bu textlerin aynı key ile aynı cipher text’i oluşturma olasılıkları aynıysa, bu cipher perfect secrecy’ye sahiptir. Daha kolay anlamak için tersten gidecek olursak: Elimizde bir cipher text var ve bu text üzerinde encryption ve decryption işlemlerinde kullandığımız key ile asıl mesajı elde etmeye çalışıyoruz. Eğer bu cipher text’ten, iki farklı mesaja ulaşma olasılığımız aynıysa, öyleyse burda perfect secrecy var demektir. Çünkü hangi mesajın doğru olduğunu asla bilemezsiniz. Çok basit ama akıl dolu bir teorem.

Bununla birlikte, perfect secrecy’ye ulaşmak tabii ki o kadar kolay değil. Shannon, One Time Pad adlı algoritmanın perfect secrecy’ye sahip olduğunu kanıtladıktan sonra, farklı bir teorem daha kanıtlıyor. Bu teoreme göre ise, perfect secrecy’ye sahip olan bir cipher’da, key uzunluğu mutlaka mesaj uzunluğuna eşit ya da mesajdan daha uzun olmalı. Bu da işleri bir hayli zorlaştırıyor; çünkü pratikte en az mesaj kadar uzun keyler kullanmak pek akıl karı değil.

Cryptography I

Introduction to Data Science dersi devam ediyor, şimdi yine Coursera üzerinde Cryptography dersi başladı. Dersi Stanford University’den Dan Boneh veriyor. Derse güzel bir giriş yaptı, biraz da işin tarihiyle ilgili bilgiler verdi. Bunları paylaşmak da şimdi bana düşüyor.

Kriptografi, veri alışverişlerinde güvenliği sağlamak için kullanılıyor. Buna internet, GSM, Bluetooth, Wireless communicationları da dahil. Peki kriptografinin amacı ne?

  1. No eavesdropping (iletişimin dinlenmesini engelleme)
  2. No tampering (iletişimin kurcalanmasını/verinin değiştirilmesini engelleme)

Şimdi ortada iki adet algoritma bulunuyor. Bunlardan birisi encryption algoritması, diğeriyse decryption algoritması. Encode ve decode diyelim bunlara. Bu tarz algoritmalarda encryption algoritmaları kamuya açık şekilde dağıtılıyor; zaten burda korumayı sağlayan temel öğe “secret key” denen anahtar kelime. Bu anahtar kelime encode ve decode eden bilgisayarlar tarafından bilindiği ve iletişim sırasında açığa çıkmadığı için güvenli bir iletişim sağlanmış oluyor. Dan Boneh diyor ki, “bu tarz bir yaklaşıma (secret key) sahip olmayan cipherları kesinlikle kullanmayın.” Buna sebep olarak ise reverse engineering ile bu algoritmaların kolayca kırılabilmesi.

Konu üzerinden biraz atlama yapalım ve dijital imzalardan bahsedelim. Gerçek hayatta imzamız tek ve benzersiz. Ancak aynı yöntemi dijital dünyada kullanamıyoruz; çünkü böyle imzalar kolaylıkla kopyalanabilir. Bunun yerine dijital imzaların güvenliği, her seferinde imzanın değiştirilmesiyle sağlanıyor. Aranızda kullanan varsa mobil imzaların çalışma şeklinin buna bir örnek olduğunu fark edecektir. Mobil imza kullanırken bize her seferinde 32 karakterlik farklı bir alfanumerik kod gösterilir ve bu kodun server ve client üzerinde aynı olması beklenir.

Dan Boneh burda biraz seçim sistemlerinden bahsediyor. Kriptografi ile bireysel oylar açığa çıkmadan istatistiksel sonuçların verilebileceğini söylüyor. Sonra da benzer yöntemle kapalı sistem açık artırmalar yapılabildiğini anlatıyor. Bunu anlatırken benim hoşuma giden bir örnek verdi: Vickrey Auction. Bu açık artırma sistemine göre (ki GittiGidiyor da bu sistemi kullanmaktadır) en yüksek teklifi veren açık artırmayı kazanır ancak ödeyeceği miktar, en yüksek ikinci teklif kadardır. Seçim ve açık artırma sistemlerini kriptografiye bağlayan nokta, tüm bu sistemlerin bir trusted authority üzerinden çalışması; daha doğrusu az sonra söyleyeceğim üzere buna gerek olmaması. Siz bu trusted authority’ye güvenmek zorundasınız ki bu trusted authority gerekli sayımları yapacak ve size sonucu verecek. Ancak bu otoriteye her zaman güvenemezsiniz.

Kriptografi dünyasında bir teorem diyor ki: “Anything that can done with trusted authority can also be done without.” Yani diyor ki, trusted authority ile yapılan her işlem, onsuz da yapılabilir.

Bunları anlattıktan sonra, Google’ın iki üç yıldır kullanmakta olduğu deneysel bir arama algoritmasından da bahsediyor – ki gizliliği sağlamak ve hızı artırmak konusunda bence çok iddialılar. İstemci (client) arama yapmak istediği query’yi encrypted olarak Google’a yolluyor, Google bunu decrypt etmeden gerekli aramayı yapıyor ve aynı şekilde sonuçları da encrypted olarak istemciye geri yolluyor. Dan Boneh bu uygulama için crypto magic terimini kullandı. Ben mi çok basit düşünüyorum bilmiyorum ama Google’ın elindeki inanılmaz büyüklükteki datanın bu uygulamanın arkasındaki güç olduğunu düşünüyorum. Yine de çok farklı secret keyler olduğunu düşününce bu işlemler o kadar da kolay değil.

Kriptografinin üç adımı var:

  1. Precisely specify threat model
  2. Propose a construction
  3. Prove that breaking construction under threat model will solve an underlying hard problem

Encrypter’ın ve decrypter’ın ikisinin de aynı secret key’i kullandığı cipherlara symmetric cipher deniyor.

Buraya kadar oldukça karışık bir yazı yazmış olduğumu fark ettim, ancak elimde derste tuttuğum notlar bulunuyor ve bu notlara bakarak yazıyorum. Biraz derleme bir yazı olduğunun farkındayım ancak şimdi de kısa bir kriptografi tarihiyle devam edeceğim. Bahsedeceğim tüm yöntemler tarih boyunca çeşitli zamanlarda kullanılmış ve hepsi kırılmış yöntemler. Zaten Dan Boneh üstüne basa basa şunu söyledi: “Yeni bir kripto metodu yaratmaya çalışmayın; siz bunu kamunun analizi için açar açmaz birileri kırıp geri gönderecektir. Yıllar boyunca kırılmamış ve yüzlerce kişi tarafından test edilmiş hali hazırdaki metodları kullanmak çok daha yararlı olacaktır.”

İlk örneğimiz substitution cipher. Artık anaokullarında dahi öğretilen, basit yer değiştirme metodu. Bir harfi farklı bir harfle kodluyorsunuz ve şifrelemiş oluyorsunuz. Bunun bir benzerini Caesar yapmış, buna da Caesar cipher denmiş. Substitution cipher’dan daha da basit, çünkü herhangi bir key kullanmıyor. Substitution cipher’da herhangi bir harfe istediğiniz harfi atayabiliyorken, Caesar cipher’ın sabit bir key space’i var. O da tüm harfleri üç kere kaydırması. Yani A yerine D, B yerine E vs. koyuyor.

Bu noktada daha ilginç bir noktaya geliyoruz ve Dan Boneh İngilizce yazınında en çok kullanılan harfin 12.7% ile E harfi, ikincinin 9.1% ile T harfi, üçüncünün de 8.1% ile A harfi olduğunu söylüyor. Harflerin kullanılma oranlarının bilinmesi, mesajları kırma yolunda önemli bir adımmış. Bu üç harf dışındaki harflerin hepsi yaklaşık olarak aynı frekansa sahiplermiş – fakat Q ve X gibi nispeten az kullanılan harfler de varmış.

Bir substitution cipher’ı kırmak için bu frekanslardan faydalanıyoruz. Hatta ve hatta daha da ileri gidip digram denen ikili harflerin frekanslarını da kullanıyoruz. Boneh, örnek olarak yine İngilizce yazınında en çok kullanılan ikilileri “he”, “an”, “in” ve “th” olarak söylüyor.

Bunun ardından tarihte bir atlama yaparak rönesansa gidiyoruz. Bu tarihlerde Vigener cipher adında bir şifreleme metodu ortaya çıkıyor. Bu metoda göre, anahtarımız bir kelime. Aslında mantık çok basit ve güzel. Bir kelime seçiyoruz, mesela bu kelime “CRYPTO” olsun. Ardından bu kelimenin altına şifrelemek istediğimiz yazıyı yazıyoruz. Yazının üzerine, her bir harfe bir harf gelecek şekilde anahtar kelimemizi CRYPTOCRYPTOCRYPTO… şeklinde döşüyoruz. Burdaki mantık, harfleri değerleri 1-26 arasında değişen şekillerde (A=1, B=2, … , Z=26) toplamak ve mod(26) işlemiyle çıkan sonucu yine aynı harf-sayı kodlamasına dayanarak harflere çevirmek. Örneğin WHATANICEDAYTODAY cümleciği CRYPTO anahtar kelimesiyle ZZZJUCLUDTUNWGCQS gibi bir sonuç veriyor. Peki bunu kırmak için nasıl bir yöntem lazım? Açıkçası Dan Boneh bunu anlattı, fakat iki üç kez dinlememe rağmen tam anlayamadığımı söylemeliyim. Anlarsam bir update yaparım ilerde. 🙂 Boneh’nin bahsettiğine göre mod(26)’ya göre toplama yapmak çok parlak bir fikir ancak Vigener bunu zayıf bir şekilde uygulayabilmiş. Bahsettiğine göre dersin ilerleyen zamanlarında daha iyi bir uygulamasını gösterecekmiş.

Ve ufaktan 19. ve 20. yüzyıla geliyoruz. Sırada rotor makineleri var. Bu makineler artık mekanik bir şekilde işi otomatize ediyor. Single rotor olarak da adlandırılan Hebern machine, yazılan her harften sonra içerdeki key space’i bir yana kaydırıyor. Yani diyelim ki key space şu şekilde: A->K, B->U, C->P. Üç defa C harfine basacak olursak, encrypted hali PUK oluyor. İkinci Dünya Savaşı sırasında Almanların kullandığı Enigma bu rotor makinelerine bir örnek. Enigma 3 ila 5 rotor kullanıyor. Bletchley Park’taki İngiliz kriptografların Enigma’yı kırması sonucu Almanların bilgileri deşifre oluyor.

20. yüzyıl ile birlikte artık mekanik yerini dijitale bırakıyor ve ABD’nin bu konuda bir standart istemesi sonucu IBM 1974 yılında Data Encryption Standard (DES) ile geliyor. Tabii ki artık DES de günümüzde kullanılmamalı, çünkü günümüzün güçlü bilgisayarları brute force ile bu kodları rahatça kırabiliyor, diyerekten tarih kısmını da kısaca bitirmiş oluyoruz.

Fractional Knapsack Problem

Algoritma dersi alırken bir hafta Knapsack Problem ile ilgili küçük bir araştırma yapmıştım. Türkçe kaynak pek yoktu, İngilizce olaraksa basit bir dil kullanan çok az sayıda yayın buldum. Bunlardan birini de University of Nebraska-Lincoln’ün Computer Science dekanı Dr. Steve Goddard’ın dersi için hazırladığı sunumlardan birinde buldum. Oldukça basit bir şekilde 0/1 Knapsack Problem’ı açıklamış. Üstüne biraz daha araştırma yaparak Knapsack Problem üzerine çalıştım ve algoritma anlatımını daha da basitleştirdim. Sonra da hem Türkçe bir kaynak bulunması için, hem de kendime ilerde referans olarak bırakmak için buraya yazmaya karar verdim. 🙂

Knapsack Problem’ın iki çeşidi var. İlki, Dynamic Programming ile çözülen 0/1 Knapsack Problem. İkincisi de Greedy Algorithm ile çözülen Fractional Knapsack Problem. Fractional Knapsack Problem çok daha kolay. O nedenle öncelikle Fractional’ın üstünden geçeceğim, sonra da 0/1’ı daha detaylı bir şekilde anlatacağım. Ama öncelikle bilmeyenler için Knapsack Problem’ın biraz üstünden geçelim. Bu problemde elimizde sınırlı hacme sahip boş bir çanta var. Bu çantaya, elimizdeki çeşitli hacimdeki ve değerdeki eşyaları sığdırmaya ve bu yerleştirmeden maksimum değer elde etmeye çalışıyoruz. Yani amacımız çantamızı doldurarak maksimum değeri elde etmek. Değişkenlerimiz: Çantanın toplam hacmi (W), eşyalarımızın hacimleri (w_i) ve eşyalarımızın değerleri (b_i). Burdaki “i”yi, eşyalarımızın bir nevi id’si olarak düşüneceğiz. Yani 2 numaralı eşyamızın hacmi w_2, değeri de b_2 değişkeniyle anılacak. Devam edecek olursak…

Fractional Knapsack Problem, eşyaları bölerek kullanmamıza izin verir. Yani hacmi 6 olan bir eşyayı çantaya tüm olarak koymak zorunda değiliz. 2/3’ünü alıp çantaya koyma imkanımız var. Peki bunun bize ne gibi bir faydası olabilir? Diyelim ki çantamızı son eşyaya kadar doldurduk ve çantamızda 4 hacimlik yer kaldı. Kullanabileceğimiz son eşyamızın da hacmi 6. Yani eşyayı olduğu gibi yerleştiremiyoruz. Biz de eşyanın 2/3’ünü alıp çantaya koyuyoruz. Böylece eşyanın değerinin 2/3’ünü de çantamızın getireceği değere ekleyebiliyoruz. Çok basit.

Şimdi küçük bir örnek yapalım. Aşağıda her birinin hacim ve değerleri verilen 4 eşyamız var. Çantamızın hacmi de, W = 6.

Hacim (weight); Değer (benefit)

w_1 = 3; b_1 = 5
w_2 = 2; b_2 = 3
w_3 = 1; b_3 = 0.5
w_4 = 2; b_4 = 2

Açıkça görüldüğü üzere üç eşyanın toplam hacmi 8, yani çantaya hepsini koyamıyoruz. Yapacağımız ilk işlem, her bir eşyanın göreceli değerlemesini bulmak. Bunun için hacim başına düşen değeri bulacağız. Biz buna kazanç (n_i) diyelim.

n_1 = b_1 / w_1 = 5/3
n_2 = b_2 / w_2 = 3/2
n_3 = b_3 / w_3 = 0.5/1 = 1/2
n_4 = b_4 / w_4 = 2/2

Görüldüğü üzere n_1 > n_2 > n_4 > n_3. Bu sıralama, bizim eşyaları çantaya koyma sıralamamız. Çantada yer oldukça koymaya çalışacağımız eşya önce 1 numara, sonra yer kalırsa 2 numara, sonra yine yer kalırsa 4 numara, sonra yine yer kalırsa 3 numara.

1 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 3. Elde ettiğimiz toplam değer: 5.
2 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 1. Elde ettiğimiz toplam değer: 8.
4 numaralı eşyayı çantaya koyamadık. Çünkü çantanın kalan hacmi 1, sıradaki eşyanın (4 numara) hacmi 2. Burda dikkat etmemiz gereken şey, 3 numaralı eşyanın hacmi 1 olmasına rağmen bu eşyayı değil, hacmi 2 olan 4 numaralı eşyayı koymak istiyoruz. Çünkü 4 numaralı eşyanın 1 hacminden kazanacağımız değer daha fazla. Çantanın kalan hacmi 1 ise, biz de 4 numaralı eşyanın 1 hacmini alıp çantaya koyuyoruz. Bu hacim bize 1 değer getirecek.

Çantanın kalan hacmi: 0. Elde ettiğimiz toplam değer: 9.

Böylece çantamızı optimal şekilde doldurmuş olduk. Çantaya koyduğumuz eşyalar 1 ve 2’nin tamamı ile 4’ün bir kısmı. Elde ettiğimiz toplam değer ise 9 oldu. Bu çözüm için pseudo-code vermiyorum, çünkü oldukça basit.

Aslında 0/1 Knapsack Problem’ı da bu postta anlatacaktım ama yazacak pek gücüm kalmadı. Önümüzdeki günlerde 0/1 yazısı da gelecek.

Dipnot 1: Aslında weight’in türkçesi “ağırlık” anlamına geliyor ama ben hacim demeyi tercih ediyorum.

Dipnot 2: Dr. Steve Goddard’ın orijinal sunumuna ulaşmak için buraya tıklayabilirsiniz.