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.

Leave a Reply