Yerine Koyma Şifrelemesi (Substitution Cipher)

Yazan : Şadi Evren ŞEKER

Yerine koyma şifrelemesinde amaç bir alfabede bulunan karakterlerin her birisinin yerine aynı alfabeden farklı bir karakter koyarak şifreleme yapmaktır. Buna göre bir tablo oluşturularak her karaktere karşılık gelen alternatif karakter tabloda tutulur. Mesajı şifrelemek isteyen kişi bu tablo yardımıyla her karakteri teker teker karşılık geldiği karaktere çevirir. Şifrelenmiş mesajı açmak isteyen kişi ise aynı tabloda tersi işlemi uygular.

Örnek olarak aşağıdaki yerine koyma tablosu verilmiş olsun (dilimizde 8 karakter olduğunu düşünelim, daha çok karakter için tablo uzatılabilir. Ayrıca aşağıdaki tablo tamamen rast gele üretilmiştir.) :
a b c d e f g h
f d e a c h g b

Buna göre şifrelenecek mesaj : “baba dede” olarak kabul edilsin
Anahtar: fdeachgb
Şifreli Metin: “dfdf acac” olacaktır.

Şifreyi açmak için aynı ahahtara sahip olan kişi tersi işlem uygulayarak tabloda hangi harfin hangisine karşılık geldiğini bulacak ve orjinal mesaj olan “baba dede” mesajını bulacaktır.

Kriptoanalizi

Gelen soru üzerine yerine koyma saldırısının kripto analizine (cryptoanalysis) yer vermek istiyorum. Yerine koyma şifrelemesi özellikle frekans saldırısına (frequencey attack) karşı zayıf bir şifrelemedir. Ancak şifreleme sisteminin anahtar uzayını çıkararak (key space), kaba kuvvet saldırısına (brute froce attack) karşı en kötü ihtimal (worst case analysis) analizi yapmaya çalışalım.

Öncelikle yerine koyma şifrelemesinde her harfin farklı bir harf ile yer değiştirmesi gerektiğini biliyoruz. Bu duruma yukarıda verilen örnekte olduğu gibi 8 karakterli bir alfabeyi ele alalım ve durumu inceleyelim.

a 8
b 7
c 6
d 5
e 4
f 3
g 2
h 1

Yukarıdaki tabloda, her harfe karşılık kaç farklı harf gelebileceği incelenmiştir. Örneğin a harfine karşılık 8 farklı harf yerleştirilebilir. Bu durumda b harfine karşılık yerleştirilebilecek 7 farklı harf kalmış olur (alfabedeki bir harf zaten a harfine karşılık olarak yerleştirilmiştir ve ikinci kere kullanılamaz)

Bu durumda kaba kuvvet saldırısı 8! ihtimal içerir.

Yukarıdaki tabloda dikkat edilebilecek bir durum. Bu tablodaki ilk harf olan a harfi için 8 farklı olasılık değerlendirilirken, a harfine karşılık yine a harfinin yazılabilme ihtimalinin de içerilmesidir. Oysaki yerine koyma şifrelemesinde, bir harf başka bir harf ile ikâme edilirken aynı harf kullanılmaz. Diğer bir deyişle a yarfinin şifreli mesajda da a harfi olarak kullanılması doğru olmaz. O halde a harfi için aslında 7 olasılık bulunmaktadır.

a harfi için (a hariç) 7 olasılıktan birisi kullanıldıktan sonra (diyelim ki c kullanıldı), b harfi için bu sefer 6 olasılık kalmış olur. Diğer harfler için de durum devam eder. Bu durumu aşağıdaki tabloda görmeye çalışalım:

harf muhtemel  harfler ihtimal sayısı örnek harf
a bcdefgh 7 h
b acdefg 6 g
c abdef 5 f
d abce 4 e
e abcd 4 d
f abc 3 c
g ab 2 b
h a 1 a

Yukarıdaki tabloda görüldüğü üzere yapılan seçimlere ve muhtemel harflere göre ihtimaller hesaplanmıştır. Bu durumda sonuç n! x n / 2 olarak bulunur. Ancak yukarıdaki tablo karşılaşılabilecek en kötü durum değildir. En kötü durumda, ilk başta aynı harfle değiştirilmesinden endişe ettiğimiz için kullanmadığımız a harfinin kullanılmasını aşağıdaki tabloda görmeye çalışalım:

harf muhtemel  harfler ihtimal sayısı örnek harf
a bcdefgh 7 b
b acdefgh 7 c
c bdefgh 6 b
d cefgh 5 c
e dfgh 4 d
f egh 3 e
g fh 2 h
h f 1 f

Yukarıdaki bu son durumda görüldüğü üzere ihtimal sayısı, bir önceki duruma göre daha yüksektir ve n harfli bir alfabe için (n-1) x (n-1)! olarak hesaplanır.  Biz de kaba kuvvet saldırısında (brute force attack) en kötü ihtimali aradığımız için, yerine koyma şifrelemesinde olasılık olarak (n-1) x (n-1)! almamız daha doğru olur. Örneğin 26 alfabeli ingilizce için bu durum 25 x 25! veya 29 harfli Türkçe için 28×28! olarak hesaplanabilir.

Yorumlar

  1. müyesser

    substition cipher da key space i 26! aldık onu neden öyle aldık anlamadım.25! olmazmı.İlk karakter için kendinin olma olasılıgını cıkartıyoruz ama 2.karakter için sadece biröncekinin olma olasılıgını cıkartıp tekrar 25 farklı çözum olacagını dusunuyoruz.
    Şimdiden teşekkürler…

  2. Şadi Evren ŞEKER Article Author

    yerine koyma şifrelemesinde gerçek olasılık 25×25!’dir ancak diğer şifreleme yöntemleri ile karşılaştırılırken kolaylık olsun diye 26! kabul edilebilir. (elbette ingilizce alfabe kullanılması ve dilde 26 harf bulunması durumunda)

    Bu durum ilk başta belki hemen anlaşılamayabilir bunun için yukarıdaki yazıya örnek üzerinden hesaplamayı gösteren bir kısım ekledim umarım yardımcı olur.

    başarılar

  3. Huseyin Erenkoy

    Merhaba hocam, substitution cipher, worst case olarak 26! ihtimalde kırılabiliyorsa eğer, bugün sıradan bir pentium II ile bu ihtimalleri denemek ne kadar zamanımızı alır acaba. Diğer bir deyişle bilgisayarın 26! ihtimali işleme süresi ne kadardır ve nasıl hesaplanılır. Teşekkür ederim.

  4. miray

    sayın hocam Elinizde Türkçe alfabe ve şifreleme anahtarı ile şifrelenmiş bir paragraf olduğunu düşünün. Şifreleme yöntemi olarak “Yerine Koyma” şifreleme kullanılmış olsun. Türkçe alfabeyi biliyorsunuz fakat elinizde şifreleme anahtarı yok. Şifreleme anahtarı olmadan bu şifreyi hangi şifre çözme yöntemi ile çözebilirsiniz?

  5. Şadi Evren ŞEKER

    Klasik olarak frekans saldırısı kullanılabilir. Yukarıdaki yazıda kriptoanaliz kısmında da bahsetmiştim ama bir kere daha linkini vereyim:
    http://www.bilgisayarkavramlari.com/2008/02/21/veri-guvenliginde-frekans-analizi-cryptoanalysis/

    Ayrıca işe yarayabilecek diğer saldırı yöntemleri şunlar olabilir.

    http://bilgisayarkavramlari.sadievrenseker.com/2009/03/02/secilmis-acik-mesaj-saldirisi-chosen-plaintext-attack/
    http://bilgisayarkavramlari.sadievrenseker.com/2009/08/20/sozluk-saldirisi-dictionary-attack/
    http://bilgisayarkavramlari.sadievrenseker.com/2008/12/28/kaba-kuvvet-algloritmasi-brute-force-attack/
    http://bilgisayarkavramlari.sadievrenseker.com/2009/02/28/kasiski-saldiri-yontemi-kasiski-attack/
    http://bilgisayarkavramlari.sadievrenseker.com/2009/03/02/bilinen-acik-mesaj-saldirisi-known-plain-text-attack/

miray için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir