Kasiski testi

Kriptanalizde, Kasiski sınaması (Kasiski testi veya Kasiski yöntemi —İngilizce: Kasiski examination veya Kasiski's test veya Kasiski's method― olarak da bilinir.), Vigenère şifresi gibi polialfabetik ikame şifrelerine saldırmak için kullanılan bir yöntemdir. İlk olarak 1863 yılında Friedrich Kasiski tarafından yayımlanmıştır, ancak 1846 gibi erken bir tarihte Charles Babbage tarafından bağımsız olarak keşfedilmiş gibi görünmektedir.

Nasıl çalışır

İkame alfabelerinin bir anahtar kelime kullanılarak seçildiği polifabetik ikame şifresinde, Kasiski testi, bir kriptanalistin anahtar kelimenin uzunluğunu çıkarmasına olanak tanır. Anahtar kelimenin uzunluğu keşfedildikten sonra, kriptanalist şifreli metni n sütun halinde sıralar, burada n anahtar kelimenin uzunluğudur. Daha sonra her sütun bir monoalfabetik ikame şifresinin şifreli metni olarak ele alınabilir. Bu nedenle, her sütuna frekans analizi ile saldırılabilir. Benzer şekilde, bir rotor akış şifrelemesi ("stream cipher") makinesi kullanıldığında, bu yöntem tek tek rotorların uzunluğunun çıkarılmasına izin verebilir.

Kasiski testi, şifreli metin içinde tekrarlanan karakter dizilerinin aranmasını içerir. Testin başarılı olması için dizeler üç karakter veya daha uzun olmalıdır. Daha sonra, dizelerin ardışık oluşumları arasındaki mesafelerin anahtar kelimenin uzunluğunun katları olması muhtemeldir. Böylece daha fazla tekrarlanan dizgi bulmak anahtar kelimenin olası uzunluklarını daraltır, çünkü tüm mesafelerin en büyük ortak bölenini alabiliriz.

Bu testin işe yaramasının nedeni, düz metinde tekrarlanan bir dize varsa ve karşılık gelen karakterler arasındaki mesafe anahtar kelime uzunluğunun bir katı ise, anahtar kelime harflerinin dizenin her iki oluşumunda da aynı şekilde sıralanacak olmasıdır. Örneğin, şu düz metni düşünün:

crypto is short for cryptography.

"crypto" tekrarlanan bir dizedir ve dizeler arasındaki mesafe 20 karakterdir. Düz metni 6 karakterlik bir anahtar kelime olan "abcdef" ile sıralarsak (6, 20'ye bölünmez):

abcdefabcdefabcdefabcdefabcdefabc

crypto is short for cryptography.

"crypto" ilk örneği "abcdef" ile ve ikinci örneği "cdefab" ile eşleşir. İki örnek farklı şifreleme metinlerine şifrelenecek ve Kasiski testi hiçbir şey ortaya çıkarmayacaktır. Ancak, 5 karakterli bir anahtar kelime olan "abcde" (5, 20'ye bölünür):

abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography.

"crypto" ifadesinin her iki oluşumu da "abcdea" ile aynı hizadadır. İki örnek aynı şifreli metne şifrelenecek ve Kasiski testi etkili olacaktır.

Dize tabanlı bir saldırı

Kasiski testini kullanmanın zorluğu, tekrarlanan dizeleri bulmakta yatmaktadır. Bu elle yapılması çok zor bir iştir, ancak bilgisayarlar bunu çok daha kolay hale getirebilir. Bununla birlikte, bazı tekrarlanan dizeler sadece tesadüf ve bazı tekrar mesafeleri yanıltıcı olabileceğinden, yine de dikkatli olmak gerekir. Kriptanalist doğru uzunluğu bulmak için tesadüfleri elemek zorundadır. Ardından, elbette, ortaya çıkan monoalfabetik şifreli metinlerin kriptanalizi yapılmalıdır.

1. Bir kriptanalist, tekrarlanan harf gruplarını arar ve tekrarlanan her grubun başlangıcı arasındaki harf sayısını sayar. Örneğin, şifreli metin FGXTHJAQWNFGXQ ise, FGX grupları arasındaki mesafe 10'dur. Analist, metinde tekrarlanan tüm gruplar için mesafeleri kaydeder.
2. Analist, bu sayıların her birini bir sonraki çarpanlarına ayırır. Bu çarpanlara ayırma işlemlerinin çoğunda herhangi bir sayı tekrarlanıyorsa, bunun anahtar kelimenin uzunluğu olması muhtemeldir. Bunun nedeni, aynı harfler aynı anahtar harfler kullanılarak şifrelendiğinde tekrarlanan grupların ortaya çıkma olasılığının tesadüften daha yüksek olmasıdır; bu özellikle uzun eşleşen dizeler için geçerlidir. Anahtar harfler anahtar uzunluğunun katlarında tekrarlanır, bu nedenle 1. adımda bulunan mesafelerin çoğunun anahtar uzunluğunun katları olması muhtemeldir. Ortak bir çarpan genellikle belirgindir.
3. Anahtar kelime uzunluğu bilindiğinde, Babbage ve Kasiski'nin aşağıdaki gözlemi devreye girer. Anahtar kelime N harf uzunluğundaysa, her N'inci harf anahtar metnin aynı harfi kullanılarak şifrelenmiş olmalıdır. Her N harfi bir araya getiren analist, her biri bir alfabe ikamesi kullanılarak şifrelenmiş N "mesaja" sahip olur ve her bir parça frekans analizi kullanılarak saldırıya uğrayabilir.
4. Çözülen mesajı kullanarak, analist anahtar kelimenin ne olduğunu hızlı bir şekilde belirleyebilir. Ya da parçaları çözme sürecinde analist, mesajı çözmeye yardımcı olmak için anahtar kelimeyle ilgili tahminleri kullanabilir.
5. Durdurucu anahtar sözcüğü öğrendiğinde, bu bilgi aynı anahtarı kullanan diğer mesajları okumak için kullanılabilir.

Üst üste bindirme

Kasiski, aslında Vigenère şifresini çözmek için "üst üste bindirme" (ing. "superimposition") yöntemini kullanmıştır. İşe yukarıdaki gibi anahtar uzunluğunu bulmakla başladı. Daha sonra mesajın birden fazla kopyasını aldı ve her biri anahtar uzunluğu kadar sola kaydırılmış olarak üst üste koydu. Kasiski daha sonra her bir "sütunun" tek bir alfabe ile şifrelenmiş harflerden oluştuğunu gözlemledi. Kasiski'nin yöntemi yukarıda anlatılan yöntemle eşdeğerdi, ancak belki de gözünüzde canlandırması daha kolaydı.

Polialfabetik şifrelere yapılan modern saldırılar, tekrarlanan sayımının bir iyileştirmesi ile yukarıda açıklananlarla temelde aynıdır. Modern bir analist tekrar eden grupları aramak yerine mesajın iki kopyasını alır ve birini diğerinin üzerine koyar.

Modern analistler bilgisayar kullanmaktadır, ancak bu açıklama bilgisayar algoritmalarının uyguladığı prensibi göstermektedir.

Genelleştirilmiş yöntem:

1. Analist alttaki mesajı bir harf sola kaydırır, sonra bir harf daha sola kaydırır, vs. her seferinde tüm mesajı gözden geçirir ve aynı harfin üst ve alt mesajda kaç kez göründüğünü sayar.
2. Alttaki mesaj anahtar uzunluğunun katları kadar kaydırıldığında "tekrarlananların" sayısı hızla artar, çünkü o zaman bitişik harfler aynı alfabeyi kullanan aynı dildedir.
3. Anahtar uzunluğunu bulduktan sonra, kriptanaliz frekans analizi kullanılarak yukarıda açıklandığı gibi ilerler.

Dış bağlantılar

• YouTube'da Cryptanalysis: Breaking a Vigenère ciphertext with Kasiski's test - Kasiski testi kullanılarak bir Vigenère şifreleme metninin nasıl kırılacağını gösteren bir video