Crypto 101 – [1] Merhaba Exclusive OR ( XOR )

Merhaba

Uzun zamandır heves ettiğim ve bir türlü gerekli motivasyonu ve zamanı bulamadığım bir konu olan Kriptoloji bilimine giriş yapma hevesi ile yola çıkmış bulunuyorum. Kriptoloji ile ilgili bir çok bilgiyi bildiğimi düşünüyor olsam da, eminim ki teorik olan bu bilgileri pratik ile bir araya getirmek istediğimde bir çok problem ile karşılacağım. Bu nedenle işi en temelinden alarak adım adım her şeyi tek tek uygulayarak ilerleyeceğimiz bir eğitim ile burada olacağım. Tüm uygulamaların kaynak kodlarına https://github.com/mmetince/crpyto101-egitim adresi üzerinden erişebilirsiniz.

Ortalama her hafta 1 yada 2 yazı ile arayı soğuk tutmamaya özen göstereceğimin sözünü de vermek isterim. Her zaman ki tüm sorularınızı yorum olarak yazarsanız her zaman cevap alacaksınız :-)

Lafı daha fazla uzatmadan ilk yazımız olan Merhaba XOR ile başlıyoruz.

Merhaba Exclusive OR ( XOR )

XOR, boolean ve binary operator olarak tanımlanmaktadır ve Exclusive OR anlamına gelmektedir. Temel olarak çok basit bir işlemi vardır ve matematiksel gösterimi ⊕ işaretidir.

 

Yukarıda ki tablo XOR kapısının yaptığı işlemi göstermektedir. Tablodan da anlaşıldığı üzere 0-0 ve 1-1 durumlarında çıkış 0 olmakta, 0-1 veya 1-0 durumlarında ise çıkış 1 olmaktadır. Peki bizim için neden XOR işlemi önemlidir ? sorusu akıllara gelecektir. Cevap ise yine yukarıda ki tabloda saklıdır. Bu soruya, soruyla cevap verirsek; Çıkışı 0 olan bir işlemde girişlerin ne olduğunu söyleyebilir misiniz ? Bizim için veri gizliliğinin ilk adımı bu soruyla oluşmaktadır. Örneğin;

Birbirleri ile konuşmak isteyen Alice ve Bob (evet tüm yazı serisi boyunca bu iki ünlü arkadaşı kullanıyor olacağız ) aralarında gizli bir anahtar belirlemiş olduklarını var sayalım. Alice’in göndermek istediği mesaj ise 10101 olsun.

Mesaj = 10101

Anahtar = 10111

Alice mesajını göndermeden önce (Mesaj ⊕ Anahtar) işlemini gerçekleştirecektir.

10101 ⊕ 10111 = 00010

Göndermek istediği orjinal mesaj 10101 iken Alice bunun yerine 00010 mesajını gönderecektir. Bu sayede mesajı taşıyacak olan kişiden orijinal mesaj gizlenmiş olacaktır. Çünkü mesajı elde eden saldırgan 10101’in XOR işlemine tabi tutulduğu Key’i bilememektedir. Mesajı alan Bob ise Alice’in yaptığı işlemin aynısını ( Gelen mesaj ⊕  Anahtar ) yaparak orjinal mesaja ulaşmış olacaktır.

00010 ⊕ 10111 = 10101 ( Orjinal Mesaj )

Özetle; Exclusive OR yani XOR bizim için kriptolojinin temel matematik operatörü olmuştur.

XOR Özellikleri

Tüm yazı serisi boyunca XOR ve özelliklerini kullanacağımız için XOR kapısının matematiksel özelliklerini bilmekte/hatırlamakta fayda var.

1 – Temel işlemler

Giriş kısmında verilen 4 işlem aşağıda ki gibidir.

0 ⊕ 0 = 0

0 ⊕ 1 = 1

1 ⊕ 0 = 1

1 ⊕ 1 = 0

2 – XOR Değişme Özelliği

XOR işleminin, a ⊕ b = b ⊕ a  eşitliği vardır. Buna orta okul yıllarında öğrenilen XOR’un değişme özelliği denir.

3 – XOR Sıfırlama Özelliği

Bir değişken kendisiyle XOR işlemine girdiğinde sonuç 0’dır. Yani; a ⊕ a = 0

4 – XOR ile Sıfır işlemi

Herhangi bir değişken sıfır ile XOR işlemine girerse, sonuç kendisine eşittir. Yani; a ⊕ 0 = a

Tüm bu kurallar bir arada kullanılarak, a ⊕ b ⊕ a = b olduğunu ispatlayalım.

a ⊕ b ⊕ a = a ⊕ a ⊕ b ( 2. kural, değişme özelliği )

= 0 ⊕ b ( 3. kural sıfırlama özelliği )

= b ( 4. kural, 0 ile işlem sonucu özelliği )

One-time pads

One-time pad,  1918 yılında Gilbert Vernam tarafından bulunmuş bir yöntemdir. En genel hatları ile, sadece bir defa kullanmak üzere üretilen bir anahtarı ifade eder. Eğer sadece bir defa kullanılmak üzere üretilen bu anahtarda, bitler gerçekten rastgele ise ve üretilen bu anahtar sadece ve sadece 1 defa kullanılıyor ise ciphertext’i elde eden saldırganın plaintext’e ulaşması mümkün değildir.

NOT: Yeni terimler öğrendiniz. ciphertext; şifrelenmiş metin. plaintext: metnin şifresiz, açık hali anlamına gelir. Bu terimleri lütfen ezberleyinizi, kalan yazılar boyunca bu terimleri kullanıyor olacağız.

Peki neden OTP (One-time pads) gücünü gerçekten rastgele olan anahtarların sadece ve sadece bir defa kullanılıyor olmasından almaktadır ? Bu soruya XOR kapısının matematiksel özelliklerinden yararlanarak cevap verebiliriz.

Alice ile Bob konuşmalarını One-time pads ile şifreliyor olsunlar. Tüm bu iletişimi dinleyen Eve isimli bir saldırganımız olsun. C1,C2,C3,…,Cn ise gönderilen ciphertext mesajları ifade etsin. OTP’nin gücünü her anahtarın sadece 1 defa kullanılıyor olmasından kaynaklandığını söylediğimiz için, varsayalım ki C2 ve C7 aynı anahtar ile XOR işlemine girmiş olsun.

Bu iki mesajı elde eden Eve, yapacağı aşağıdaki işlem ile plaintext mesaj hakkında bilgi sahibi olacaktır.

C2 ⊕ C7 = ( P2 ⊕ K ) ⊕ ( P7 ⊕ K )

= P2 ⊕ P7 ⊕ K ⊕ K

= P2 ⊕ P7 ⊕ 0

= P2 ⊕ P7

XOR işleminin matematiksel özelliklerinden yararlanara, yukarıda ki denklemler ile de ispat edildiği üzere, aynı key’e sahip iki ciphertext’in bir biri ile XOR işlemine sokulması, plaintext’lerin bir biri ile XOR yapılmasının sonucuna eşittir. Yani özetle; XOR’un özelliğinden yararlanılarak K ile ifade edilen key denklemden elemine edilebilir..! Elde edlen P2 ⊕ P7 sonucu bize ne P2 nede P7 hakkında net bilgi vermiyor olsada, bu sonuç bize önemli bilgiler ifade edecektir.

Tüm bu laf kalabalığını aşağıdaki resim örneği ile anlatalım. ( Resmin büyük hali için resme tıklayınız. )

crypo101-xor-same-key-image

 

Yukarıda ki resimde iki farklı resim gözükmekte. Bu resimler aynı key ile XOR işlemine girdiler ve her resmin aşağısında bulunana “karıncalı” görüntü oluştu. Bu “karıncalı” verileri Eve isimli saldırganımız tarafından ele geçirilen cipher-text verilerimiz. XOR işleminde kullanılan key’i bilmeyen Eve bu iki resim birbiri ile XOR işlemine soktuğunda ise aşağıdaki resim oluşacaktır.

Crypto XOR result

Bu işlemleri gerçekleştirmek için aşağıdaki python kodları yazılmıştır. ( https://github.com/mmetince/crpyto101-egitim )

Yazı serisinin ikinci bölümünü okumak için; https://www.mehmetince.net/crypto-101-2-block-cipher-encryption-ve-des-analizi/ tıklayınız.

  • Başarılı bir yazı olmuş ellerine sağlık

  • Candan BÖLÜKBAŞ

    Ellerine saglik, gayet basarili olmus. serinin devamini heyecanla bekliyoruz.

    • Motivasyon için eyvallah, sırada ki yazı OTP’nin kullanılabilirliği ve Block Cipher olacak :-)

  • Kubilay Onur Gungor

    One time pad icin bir baska gereklilik, key ile sifrelenecek metnin uzunlugunun ayni olmasi ile ilgili.

  • Muhammed N. Kartal

    Ellerinize sağlık çok başarılı ve güzel bir giriş olmuş yazının devamını beklemekteyiz.

    • Teşekkürler. İkinci yazıya, https://www.mehmetince.net/crypto-101-2-block-cipher-encryption-ve-des-analizi/ adresinden ulaşabilirsiniz.

      • Muhammed N. Kartal

        İkinci yazıyıda okudum , des ve 3des ile ilgili yabancı kaynaklardan anlayamadığım f fonksiyonunu rahatlıkla anladım çok teşekkür ediyorum.
        Rsa alg. ile ilgili olan bölümleri sabırsızlıkla bekliyorum.

        • Beğenmenize çok sevindim. Asimetrik encryptionlar ile ilgili yazılar serinin ilerleyen bölümlerinde gelecek. Önümüzde ki 1-2 yazı, DES saldırıları, AES, stream cipher’lar ile ilgili olacağını haber vermek isterim :-)