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 II

Dan Boneh’nin kriptografi üzerine yayınladığı dersler devam ediyor. Şifreleme sistemlerine geçmeden önce hızlı bir Discrete Probability dersi verdi. Yaklaşık yarım saatlik bu dersin sonlarına doğru iki teorem inanılmaz ilgimi çekti. Dolayısıyla bunları paylaşmak istiyorum:

An important property of XOR

XOR işlemi yuvarlak içine alınmış artı işaretiyle gösteriliyor. Bitwise olarak truth table’ı şu şekilde:

xor-tableDiscrete Probability’den konuşurken random variable, uniform variable ve independence gibi terimleri ve ne anlama geldiklerini bilmek gerekiyor. Bu terimleri uzun uzun anlatacak kadar zamanım ve bilgim yok. Altta kısaca bahsedeceğim ama yine de terimleri bildiğinizi varsayıyorum. Eğer bilmiyorsanız ve yazının devamını okumak istiyorsanız, tavsiyem wikipedia üzerinden bu terimlere bir göz atmanız.

Teorem diyor ki;

Y {0,1}^n üzerinde bir random variable olsun.
X {0,1}^n üzerinde bir independent uniform variable olsun.

Yani Y’nin alacağı distribution değerlerini bilmiyoruz ama X’inkileri (uniform olduğu için) biliyoruz.

Öyle ki, Z = Y xor X {0,1}^n üzerinde bir uniform variable’dır. Yani Y’nin dağılımı ne olursa olsun, Z’yi etkilemiyor.

Bunun kanıtını da n=1 için yapalım; n=1 için Y’nin de X’in de alabileceği ikişer değer var: Bunlar 0 ve 1.

Y’nin 0 olma olasılığına P0, 1 olma olasılığına P1 diyelim.
X’in uniform olması, bizi X’in 0 olma olasılığının da 1 olma olasılığının da 1/2 olduğu gerçeğine götürüyor.

Şimdi Z’nin değerlerini hesaplayalım. Z’nin alabileceği iki değer var: Bunlar 0 ve 1. X’in dağılımındaki değerler birbirinden farklı oldukları için (independence), Y xor X’in sonucuna olasılıkların çarpımlarıyla ulaşabiliyoruz. Yani;

Y=0, X=0 için Pr[Z]=P0/2
Y=0, X=1 için Pr[Z]=P0/2
Y=1, X=0 için Pr[Z]=P1/2
Y=1, X=1 için Pr[Z]=P1/2

Bu noktada tamamen bizim tercihimize bağlı olarak, Z’nin 0 olduğu olasılığı bulalım. Z’nin 0 olması için (x,y) = (0,0) veya (x,y) = (1,1) olması gerekiyor. Öyleyse Pr[Z=0] = P0/2 + P1/2 = (P0+P1) / 2.

Y’nin 0 olma olasılığına P0, 1 olma olasılığına P1 demiştik. Yani P0+P1=1 olmalı. Bu durumda Pr[Z=0] = 1/2 çıkıyor. Aynı şekilde Pr[Z=1] = 1/2 çıkıyor. Biz de Z’nin uniform variable olduğunu görmüş oluyoruz.

The birthday paradox

Bir diğer özellik ise, doğum günü paradoksu. Teorem diyor ki:

U adında bir universe belirleyelim ve bu universe’ün 1’den n’e kadar giden r1, r2, …, rn şeklinde independent ve identically distributed random variableları olsun. |U|’ya U’nun boyutu dersek,

n = 1.2 * |U|^(1/2) olursa, birbirine eşit olmayan i ve j için ri ve rj variablelarının eşit olma olasılığı 1/2’den fazladır. Bunu söze dökecek olursak, bu U içerisinde n’i hesaplayacağız ve eğer U’da n kadar eleman varsa, bu iki elemanın değerinin ya da bu iki kişinin doğum gününün aynı olma olasılığı oldukça yüksektir.

Bu teoremi ilkokulda bile gösterilen kesinlik ilkesine bağlayacak olursak, aslında bu doğum günü işini oldukça eksik öğrendiğimizi görüyoruz. Bir yıl 365 gün ve eğer ortamad 366 kişi varsa en az iki kişinin doğum günü kesinlikle aynıdır deriz. Ancak bu teoreme göre |U|=365’ten n yaklaşık olarak 24 çıkıyor. Yani teoreme göre ortamda 24 kişi varsa, bu 24 kişinin en az ikisinin doğum günlerinin aynı olması kesin değil ama yüksek ihtimal.

 

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.