Güvensiz kanaldan anahtar değişimi

Bilindiği gibi anahtar değişimi problemi simetrik şifrelemenin en büyük sorunudur. Simetrik şifreleme oldukça küçük anahtar boyutlarıyla, yüksek güvenlikli şifreleme işlemi yapabiliyor olsa bile ortak kullanılan anahtarın güvensiz bir kanalı kullanılarak oluşturulması işlemi Whitfield Diffie ve Martin Hellman'ın adıyla anılan yönteme kadar yapılamamaktaydı. Bu işlem için güvenli bir kanalın kullanılması zorunluydu. 1976'da yayınlanan makale [1] açık anahtarlı şifrelemenin en önemli adımlarından biridir. Temel aldığı matematik onu ilk defa okuyanda "bunu ben de düşünebilirdim" hissini uyandıracak kadar basit ve güzeldir.

Algoritmanın matematik tarafına geçmeden önce renklerle anlatımına bir bakalım.

Alice ve Bob ortak bir renk üzerinde anlaşıyorlar. Yukarıdaki örnekte bu sarı renk oluyor. Bu rengi herkes biliyor. Ardından her ikisi de birbirlerine bile söylemedikleri birer renk seçiyorlar. Alice pembe, Bob da mavi rengi seçmiş olsun. Bu seçtikleri renkleri sarı ile karıştırıp herkesin görebildiği bir ortamda birbirlerine iletiyorlar. Herkes ortak rengin sarı olduğunu bilmesine rağmen ona hangi rengin karıştırılıp bu yeni renklerin elde edildiğini anlayamıyor, çünkü renk yelpazesi çok geniş (matematik tarafına baktığımızda burası daha kabul edilebilir olacak). Alice Bob'tan aldığı karışımın üzerine kendi rengi olan pembeyi, Bob da Alice'den aldığı karışıma maviyi karıştırdığında her ikisinin de elinde sarı, pembe ve maviden oluşan aynı renk bulunmuş oluyor. Bu karışımın rengi her ikisinde de aynı ve onu hiç transfer etmediler.

Şimdi bu güzel fikrin matematik tarafı nasıl işliyor ona bakalım.

Alice ve Bob güvensiz kanalı kullanarak p ve g sayılarını seçiyorlar. Burada p bir asal sayı ve g de mod p'ye göre primitif kökü. Daha sonra Alice bir a sayısını seçiyor ve bunu kimseye söylemiyor. Aşağıdaki gibi bir hesaplamayla A değerini hesaplayıp yine güvensiz kanalı kullanarak, yani herkesin görebileceği şekilde Bob'a gönderiyor.

Bu A ifadesinde g ve p değerleri bilinmesine rağmen a hesaplanamıyor çünkü g mod p'ye göre primitif kök. Yani; g'nin kuvvetleri p'den küçük bütün tam sayıları kapsıyor. a'nın sonsuz değeri için A aynı şekilde hesaplanabilir. Benzer şekilde Bob da sadece kendisinin bildiği bir b değeri seçip onunla benzer hesaplamayı yapıyor ve Alice'e gönderiyor.

Şimdi artık her ikisi de karşıdan aldıkları sayılarla kendilerinde gizli tuttukları sayıları işleme tabi tutup aynı gizli değeri elde edebilirler.

Diffie–Hellman anahtar değişimi algoritmasının getirdiği büyük yenilik, güvensiz bir kanalı kullanarak sadece gönderici ve alıcının bilebildiği bir sır oluşturabilmeleridir. Ayrıca tarafların birbirlerine kendi sırlarını da ulaştırmalarının gerekmemesi bu algoritmayı internette güvenli iletişim için kullanılabilir kılmaktadır.


[1] https://ee.stanford.edu/~hellman/publications/24.pdf

"Kod yazabiliyorum ama algoritmasını yazamıyorum"

Yıllardır bilgisayar mühendisliği öğrencilerine algoritma ve programlamaya giriş anlatıyorum. Bütün eğitim hayatları boyunca sadece problem çözmeye odaklanmış olan öğrenciler için problemi çözme süreci üzerinde düşünmek çok zor geliyor. Öğrencilerin bir kısmı üniversiteye gelmeden önce de kodlamayı bir miktar biliyor olmasına rağmen bir problemi hangi süreçleri takip ederek çözdükleri üzerine neredeyse hiç düşünmemiş oluyorlar. Bu elbette bireysel olarak onların eksikliği değil, onları bu hale eğitim sistemimiz getiriyor.

Algoritma üzerinde düşünmek aslında problemi çözmek değil de onu çözümlemek anlamına geliyor. Üniversiteye gelene kadar problem çözümlerinde hep kısa yollar, formüller öğrenmiş; kavramları, tanımları önemsememiş gençler için bunları öğrenmek ve üzerinde düşünmek zorlu bir süreç oluyor. Hemen kod yazmaya geçmek istiyorlar ama problemi çözümlemeden kodunu yazmak işlevsiz bir çaba oluyor. Algoritma yazmak veya akış şeması çizmek için harcanan zaman boşa geçiyormuş gibi geliyor genç arkadaşlara.

Bu denizi doldurmak için yapılan çalışmalara benziyor biraz. Kayaları taşıyan ilk kamyonların döktüklerinin suyun içinde kaybolup gittiğini görürüz başlarda. Sanki bir sonsuzluğun içine bıraktığımız bu kayalar asla kıyının seviyesine gelemeyecek gibidir. Eğer yeterince kayayı suya dökersek zamanla suyun yüzeyinden görülebilir olduklarını görürüz. Bu işleme sabırla devam edince kayalar suyun yüzeyini de aşarlar. Programlama öğrenme sürecinin başında algoritma üzerinde düşünürken, yazarken işte bu kayaları denize döküyoruz. Hemen ortaya bir şey çıkarmak isteyenler, for'ları, while'ları ve if'leri yazmak ve o denizi hemen doldurmak istiyorlar.

Karl Marx'ın en kötü mimarı en iyi arıdan ayıran özelliğinin mimarın yapacağı işi önce aklında inşa etmesi olarak vurgulamasını yazılım dünyası için de düşünmek hatalı olmayacaktır. 

İşin doğrusu bazı durumlarda çözülecek problem üzerinde çokça düşünmeye değecek kadar derinlikli olmuyor. Hele iş hayatında insanın karşısına sürekli meydan okumalarla dolu sorunlar çıkmıyor. Süreç üzerinde düşünme disiplini olmayan biri için her sorun böyle kolayca çözülebilir gibi geliyor olabilir ama elbette her zaman böyle olmuyor.

Bir örnekle problemin önce akılda çözülmesinin önemini göstermek istiyorum. Aşağıda bir üçgen şeklinde dizilmiş sayılara bakalım. Bize yukarıdan aşağı doğru sadece birbirine temas eden sayılarla elde edebileceğimiz en büyük toplam soruluyor olsun.

Takip edilebilecek rotaların sayısı sadece 8 olduğundan olası bütün rotaları hesaplayıp en büyüğünü seçersek 308 toplamını bulmak zor olmayacaktır. Şimdi bu sayı dizisini biraz büyütelim.

Yukarıdaki şekilde 15 satır var, yani takip edilebilecek rotaların sayısı 2^14 tane. Bu da 16384 farklı rota demek oluyor. İlkine göre bir hayli fazla olsa da burada da tüm rotaları hesaplayıp en büyüğünü seçmek imkanı var. En yavaş bilgisayarlarda bile oldukça kısa sürede hesaplanabilecek şekilde kodlamak mümkün bu yöntemi.

Peki ya satırların sayısı 100 olsaydı? Bu durumda hesaplanacak farklı rota sayısı 2^99 olacaktı. Bu da 633825300114114700748351602688 farklı rota demek olur. Bu 30 basamaklı bir sayı olduğundan bütün rotaları hesaplayarak sonuca ulaşamayacağımız herkes için çok açık olmalı. Ne bu kadar farklı rotayı hesaplayabilir ne de, hesaplasak bile, bunları bir yerde saklayabiliriz. İşte "kod yazabiliyorum ama algoritmasını yazamıyorum" diyenlerin tıkandığı nokta burasıdır. Yöntem üzerinde düşünmeyen ancak sonucu apaçık görünen problemleri çözebilir.

Buraya kadar sabırla okuyanlar için çözümü de yazıp öyle bitirmek istiyorum bu yazıyı. Çözümü 8 farklı rotanın olduğu durum için anlatacağım ama kolayca genişletebilirsiniz. Problemi yukarıdan aşağıya doğru değil de aşağıdan yukarı doğru çözmeye çalışalım. En alttaki satırın bir üstüne kadar gelmiş olsaydık en alt satırdakilerden hangisini seçerdik diye düşünelim. Yani bir şekilde 17'ye gelmiş olsaydık, en büyük toplamı elde etmek için 18'e mi, 35'e mi giderdik? Elbette 35'e gitmeliydik. Aynı şekilde 47'den de 87'ye gitmeliydik. Son olarak 82'den de 87'ye giderdik. O zaman üçüncü satırdaki her sayıdan altındaki satırdaki ulaşabildiği sayıların en büyüğüne gideceğimizi görmüş olduk. Şimdi problem şu hale geldi.

                                   75
                       95                       64
17+max(18,35)  47+max(35,87)  82+max(87, 10)

İşlemleri yapınca:

     75
   95 64
52 134 169

Aynı işlemi ikinci satır için yapalım:
                         75
95+max(52,134) 64+max(134,169)

Burada işlemleri yapalım:
     75
229 233

Aradığımız sonuç böylece 75+max(229,233)=308 olacaktır. Bir kere böyle düşünmeyi akıl ettiğimizde satır sayısının ne kadar fazla olduğunun bir önemi kalmayacaktır. Yazacağımız kod 100 satır için bir saniyede çözüm bulacakken, bunu düşünmeyenlerin yazacağı kod milyarlarca yılda sonlanmayacaktır. Algoritma hakkında düşünmek ve düşünmemek arasındaki fark işte bu büyük uçurumdur.