KLASİK KRİPTOGRAFİ 1

BÖLÜM 1 :  KLASİK KRİPTOGRAFİ

1. GİRİŞ : Örnek Kriptosistemler

Kriptografinin temel amacı, genellikle Alice ve Bob olarak adlandırılan iki kişinin güvenli olmayan bir kanal üzerinden Oscar olarak adlandırılan düşmanın ne söylendiğini öğrenmesi önlenerek haberleşmesini sağlamaktır. Bu kanal bir telefon hattı veya bilgisayar ağı olabilir. Alice’in Bob’a göndermek istediği bilgi (plaintext) İngilizce bir metin, nümerik bir veri veya yapısı tamamen keyfe bağlı olan herhangi birşey olabilir. Alice, önceden kararlaştırılan bir anahtar kullanarak plaintext’i şifreler ve şifrelenen ciphertext’i kanal üzerinden gönderir. Oscar kanal içindeki ciphertext’i gözler. Ancak plaintext’in ne olduğunu tespit edemez. Bob ise şifreleme anahtarını bildiği için ciphertext’in şifresini çözer ve plaintext’i elde eder.

Bu kavram aşağıdaki matematiksel yaklaşım kullanılarak daha biçimsel olarak tanımlanmıştır :

TANIM 1.1  Bir kriptosistem aşağıdaki koşulları sağlayan bir beşliden (P, C, k, E, D)      meydana gelir.

1. P ; Plaintext’lerin sonlu kümesidir.
2. C ; Ciphertext’lerin sonlu kümesidir.
3. K ; anahtar alan, anahtarların sonlu kümesidir.
4. Her K e k olmak üzere bir  e_K e E şifreleme kuralı ve buna bağlı olarak bir d_K e D şifre çözme kuralı vardır. Her e_K : P à C   ve d_K : C à P fonksiyonları her plaintext xeP için  d_K (e_K (x)) = x  sağlar.

Burada temel özellik 4. koşuldur ve anlatılmak istenen  e_K kullanılarak bir plaintext(x) şifrelenir ve elde edilen ciphertext daha sonra d_K  kullanılarak çözülür ve orjinal plaintext x elde edilir.

Alice ve Bob aşağıdaki protokolü belirli bir kriptosistem kullanarak çalıştıracaklardır. Öncelikle, rasgele bir anahtar seçerler (Ke k). Anahtar seçme işlemi Alice ve Bob aynı yerdeyken ve Oscar tarafından gözetlenmiyorken ya da farklı yerlerdeyken ancak güvenli bir kanala eriştikleri zaman yapılabilir. 

Şekil 1.1 Haberleşme Kanalı

Daha sonra Alice’in Bob’a güvenli olmayan bir kanal üzerinden bir mesaj göndermek istediğini varsayalım ve bu mesaj örneğin  şu şekilde olsun:

x = x₁ x₂ ....... x_n          , n ³ 1  x_i e P , 1 £ i  £ n

Her x_i önceden belirlenen K anahtarı ile e_k şifreleme kuralı kullanılarak şifrelenir. Alice, y_i=e_k(x_i)  , 1<=i<=n’i hesaplar ve sonuç olarak ciphertext’i (y) elde ederek kanal üzerinden gönderir.

y = y₁ y₂ .......y_n

Bob y = y₁ y₂ .......y_n’i aldığı zaman d_k şifre çözme kuralını kullanarak şifreyi çözer ve x = x₁ x₂ ....... x_n  plain text’i elde eder. Bu haberleşme kanalı Şekil 1.1’de gösterilmektedir.

Açıkça görüldüğü üzere, her şifreleme fonksiyonu (e_k) bire-bir fonksiyon olmalıdır. Aksi halde, şifre çözme belirli bir yöntem kullanılarak geliştirilemez. Örneğin eğer,

y = e_k(x₁) = e_k(x₂)       x₁ º x₂ 

olduğu bir durumda Bob, y’nin x₁ ile mi yoksa x₂ ile mi çözüleceğini bilemez. Eğer P=C ise, her şifreleme fonksiyonu bir permütasyondur. Yani, eğer plaintext’lerin ve ciphertext’lerin kümesi özdeş ise, her şifreleme fonksiyonu bu kümenin elemanlarını tekrardan düzenler.

1.1   Kaydırma Şifresi (The Shift Cipher)

Bu bölümde, modüler aritmetiğe dayanan kaydırma şifresini tanımlayacağız. Ancak önce modüler aritmetikle ilgili bazı temel tanımlamaları gözden geçirelim.

TANIM 1.2  a ve b’nin tamsayılar, m’nin pozitif bir tamsayı olduğunu varsayalım.Eğer m,b-a ’ı bölebiliyorsa a º b (mod m) yazabiliriz. a º b (mod m) deyimi  “a, b’ye mod m’e göre denktir” şeklinde okunur. m tamsayısına modüler denir. 

            a ve b’yi m ile bölüm ve kalanı elde etmek için böldüğümüzü varsayalım. Kalan 0 ile m-1 arasında bir değer alacaktır. Bu; 0£ r₁ £ m-1  ve  0£ r₂ £ m-1 olduğu durumlarda a=q₁m+r₁  ve  b=q₂m+r₂  eşitliklerini verir. Bu eşitliklerden sadece ve sadece,  r₁ = r₂ olduğu zaman a º b (mod m) olabileceğini kolayca görebiliriz. b mod m ifadesini, a; m ile bölündüğünde kalanı göstermek için kullanacağız. Böylece, a º b (mod m) sadece ve sadece

a mod m = b mod m olduğu durumda doğrudur. Burda a yerine a mod m koyduk, a’ya mod m’e göre  indirgenmiş denir.

UYARI : Birçok bilgisayar programlama dili a mod m’i, a ile aynı işarete sahip –m+1,....,m-1 aralığında kalan olarak tanımlar. Örneğin, -18 mod 7, yukarda tanımladığımız gibi 3 yerine –4 olacaktır. Ancak a mod m’i her zaman n-negatif olarak tanımlamak daha kullanışlı olacaktır.

Aritmetik modül m:Z_m, + ve x işlemleri ile {0,........,m-1} kümesi olarak tanımlanır. Z_m’deki toplama ve çarpma şlemleri çıkan sonuçların modül m’e indirgenmesi dışında bilinen toplama ve çarpma işlemleri ile aynıdır.

Örneğin, 11x13’ü Z₁₆’da hesaplamak isteyelim. Tamsayılar olarak 11x13=143. 143’ü mod 16’ya indirgemek için bölme işlemini gerçekleştiririz: 143 = 8x16+15. Böylece 143 mod 16 = 15 yani 11x13=15  Z₁₆’dır.

Z_m’de yaptığımız bu toplama ve çarpma işlemlerinin tanımları, aritmetikte birçok benzer kuralı karşılamaktadır. Aşağıda bu özellikler listelenmiştir:

1. Toplamanın kapalılık özelliği, herhangi bir  a, b e Z_m için a+b e Z_m’dir.
2. Toplamanın değişme özelliği, herhangi  a, b e Z_m  için a+b = b+a’dır.
3. Toplamanın dağılma özelliği, herhangi  a, b, c e Z_m  için (a+b)+c = a+(b+c)
4. Toplamada etkisiz eleman 0’dır, herhangi bir  a e Z_m  için  a+0 = 0+a = a
5. Herhangi bir a e Z_m’in toplamaya göre tersi m-a’dır, a+(m-a) = (m-a)+a = 0
6. Çarpmanın kapalılık özelliği, herhangi  a, b e Z_m  için ab e Z_m 
7. Çarpmanın değişme özelliği, herhangi  a, b e Z_m  için ab = ba
8. Çarpmanın dağılma özelliği, herhangi  a, b, c e Z_m  için (ab)c = a(bc)
9. Çarpmada etkisiz eleman 1’dir, herhangi bir  a e Z_m  için ax1 = 1xa = a
10. Çarpmanın toplama üzerinde dağılma özelliği vardır, herhangi  a, b, c e Z_m  için, (a+b)c = (ac)+(bc)  ve  a(b+c) = (ab)+(ac)

Zm’de toplamaya göre tersi alınabildiği için, 11+13 mod 31=24. diğer bir yolda, önce 11’den 18’i çıkarıp –7’yi elde ederiz ve daha sonra –7 mod 31=24.

ŞEKİL 1.2

Kaydırma Şifresi (Shift Cipher)

P = C = k = Z26 olsun, 0 £ K £ 25      için                         ek(x) = (x+K) mod 26             ve                         dk(y) = (y-K) mod 26     tanımlanır.      (x,y e Z26)

 

            Kaydırma şifresini Şekil 1.2’de gösterdik. İngiliz alfabesinde 26 harf olduğundan şifreleme Z₂₆’da tanımlandı. Kaydırma şifresi yukarda tanımlandığı gibi bir kriptosistemi şekillendirir. Örneğin, bütün x e Z₂₆’da tanımlandı. Kaydırma şifresi yukarıda tanımlandığı gibi bir kriptosistemi şekillendirir. Örneğin, bütün x  e Z₂₆ için d_K(e_K(x)) = x’dir.

UYARI : k = 3 için kriptosistem Caesar şifresi olarak bilinir.

            Kaydırma şifresini İngilz alfabesindeki harfleri mod 26’ya göre A -> 0, B -> 1, ……Z -> 25 şeklinde şifreleyerek kullanacağız.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

Örnek 1.1

Kaydırma şifresi k=11 olsun ve plaintext’te

                                   wewillmeetatmidnight.    olsun.

Öncelikle plaintext’i yukarıdaki tabloyu kullanarak tamsayılara çeviririz.

                                  

22  4   22  8  11  11  12  4  4  19

0   19  12  8    3  13    8  6  7  19

Daha sonra herbirine mod 26’ya göre 11 ekleriz :

                                    7   15   7   19   22   22   23  15  15  4

11    4  23  19  14    24  19   17  18  4

Son olarak, bu tamsayıları ciphertxt’i elde etmek üzere alfabetik karakterlere çeviririz.

                                   HPHTWWXPPELEXTOYTRSE.

Ciphertext’in şifresini çözmek için, Bob öncelikle harfleri tamsayılara çevirir, sonra her değerden mod 26’a göre 11’i çıkarır ve son olarak tamsayıları alfabetik sayılara dönüştürerek plaintext’i elde eder.

NOT: Yukarıdaki örnekte okunabilirliliği arttırmak için büyük harfler, plaintext için de küçük harfler kullandık.

            Eğer bir kriptosistem pratik olarak kullanılacaksa, bir takım özellikleri sağlamalıdır:

1. Her şifreleme fonksiyonu e_k ve her şifre çözme fonksiyonu d_k hesaplanabilir olmalıdır.
2. Oscar, cipher text y’i gördüğünde, kullanılan K anahtarını ya da plaintext x’i belirleyememelidir.

İkinci özellik “güvenlik” fikrini tanımlamaktadır. Verilen bir cipher text y’den K anahtarını hesaplamaya çalışma işlemine kriptoanaliz denir. Eğer Oscar K’yı tespit edebilirse, Bob’un yaptığı gibi d_k ile y’nin şifresini çözebilir. K’nın tesbit edilmesi en az plaintext x’in tahmin edilmesi kadar zor olmalıdır.

Shift Cipher, güvenli bir yöntem değildir. Çünkü “ayrıntılı anahtar arama yöntemi” ile kriptoanaliz edilebilir. Sadece 26 mümkün anahtar olabileceği için, anlamlı bir plaintext elde edene kadar olası bütün şifre çözme kuralı (d_k)’yı denemek kolaydır. Bu aşağıdaki örnekte gösterilmiştir.

Örnek 1.2

Verilen ciphertext ;

                                   JBCRCLQRWCRVNBJENBWRWN,

Şifre çözme anahtarları d₀, d₁,......vb. kullanarak şunları elde ederiz.

                       jbcrclqrwcrvnbjenbwrwn

                                   iabqbkpqvbqumaidmavqvm

                                   hzapajopuaptlzhclzhclzupul

                                   gyzozinotzoskygbkytotk

                                   fxynyhmnsynrjxfajxsnsj

                                   ewxmxglmrxmqiweziwrmri

                                   dvwlwfklqwlphvdyhvqlqh

                                   cuvkvejkpvkogucxgupkpg

                                   btujudijoujnftbwftojof

                                   astitchintimesavesnine

            Bu noktada, plaintext’i belirleyebildik. Anahtar K=9’dur. Ortalama olarak bir plaintext 26/2 = 13 şifre çözme kuralı denenerek hesaplanabilir. Yukardaki örnekte görüldüğü üzere, bir kriptosistemin güvenli olması için, örneğin anahtar alanın çok büyük olması durumunda olacağı gibi ayrıntılı anahtar arama yönteminin mümkün olmaması gerekir. Ancak tahmin edilebileceği gibi büyük bir anahtar alan da güvenliği garanti edebilmek için yeterli değildir.

1.1.2        Değiştirme Şifresi (The Substitution Cipher)

Diğer bilinen kriptosistemlerden bir tanesi de değiştirme şifresidir. Bu kriptosistem yüzlerce yıl boyunca kullanılmıştır. Bu şifre Şekil 1.3’de tanımlanmıştır.

ŞEKİL 1.3

Değiştirme şifresi

P = C = Z26 olsun. K; 26 sembolün 0,1,.......,25 bütün olası permütasyonlarından oluşsun. Her  p e k  permütasyonu için, p -1  p’nin ters permütasyonu olmak üzere ;                         ek(x) = p(x) , ve                         dk(x) = p -1(y)        tanımlanır.

 

                                  

    

            Örnek olarak, plaintext karakterleri küçük harflerle ve ciphertext karakterleri de büyük harflerle yazılmıştır.

a

b

c

d

e

f

g

h

i

j

k

l

m

X

N

Y

A

H

P

O

G

Z

Q

W

B

T

n

o

p

q

r

s

t

u

v

w

x

y

z

S

F

L

R

C

V

M

U

E

K

J

D

I

            Şifre çözme fonksiyonu alfabetik sıranın tersidir.

A

B

C

D

E

F

G

H

I

J

K

L

M

d

l

r

y

v

o

h

e

z

x

w

p

t

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

b

g

f

j

q

n

m

u

s

k

a

c

i

d_p (A) = d , d_p(B) = l , .......vb.

Okuyucu bu şifre çözme fonksiyonunu kullanarak aşağıdaki ciphertext’i şifreleyebilir :

                                   MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA.

            Değiştirme şifresi için gerekli olan bir anahtar sadece 26 alfabetik karakterin bir permütasyonundan meydana gelmektedir. Bu permütasyonların sayısı 4.0x10²⁶’dan daha fazla olan 26!’dır. Böylelikle, bir bilgisayar için bile bir ayrıntılı anahtar araması mümkün değildir. Ancak daha sonra göreceğimiz diğer yöntemlerle Değiştirme şifresi kolayca kriptoanaliz edilebilir.  

1.1.3        Affine Şifresi

Değiştirme şifresi, kaydırma şifresinin 26 elemanının olası 26!’dan sadece 26’sını içeren özel bir durumudur. Kaydırma şifresinin başka bir özel durumu da şimdi bahsedeceğimiz Affine şifresidir. Affin şifresinde, şifreleme fonksiyonları;a,b e Z₂₆

e(x) = (ax+b)  mod 26

fonksiyonları şeklinde sınırlandırılır. Bu fonksiyonlara Affin fonksiyonları denir.(a = 1 iken yerdeğiştirme şifresi elde edilir.)

            Şifre çözmenin mümkün olması için, bir Affin fonksiyonunun ne zaman bire bir olacağını sormak gereklidir. Başka bir deyişle, herhangi y e Z₂₆ için,

ax+b º y (mod26)

denkliğinin x için tek bir çözümü olmasını isteriz. Bu eşleşim,

ax º y-b  (mod26) ‘ya eşittir.

Bu durumda y, Z₂₆’da farklı değerler aldığı müddetçe, y-b’de Z₂₆’da farklı değerler alacaktır.

Bu eşleşim her y için sadece ve sadece gcd(a,26) = 1 olduğu zaman tek bir çözüme sahiptir. (gcd fonksiyonu argümanların en büyük ortak bölenini göstermektedir.) Öncelikle, gcd(a,26) = d >1 olduğunu varsayalım.  Buna göre, ax º 0 (mod 26) denkliği Z₂₆’da x = 0 ve x = 26/d olmak üzere en azından iki farklı çözüme sahiptir. Bu durumda, e(x) = ax+b mod 26 bire bir fonksiyon değildir ve buna bağlı olarak da doğru bir şifreleme fonksiyonu  da olamaz.

            Örneğin, gcd(4,26) = 2 olduğu için, 4x+7 doğru bir şifreleme fonksiyonu değildir. Çünkü herhangi bir x e Z₂₆ için x ve x+13 aynı değeri şifreleyecektir.

            Şimdi de gcd(a,26) = 1 olduğunu varsayalım. Herhangi x₁ ve x₂ için 

ax₁ º ax₂ (mod 26)  olduğunu varsayalım.

a(x₁-x₂) º 0  (mod 26) ,

26 | a(x₁-x₂).

Şimdi bölmenin bir özelliğini kullanacağız. Eğer gcd(a,b) = 1 ve a | bc ise, a | c’dir.

gcd (a,26) = 1 olduğu için 26 |  a(x₁-x₂)’i

26 | (x₁-x₂)  şeklinde yazabiliriz.

Örneğin, x₁ º x₂  (mod 26)’dır.

            Bu noktada, eğer gcd (a,26) = 1 ise ax º y (mod 26) denkliğinin Z₂₆’da en çok bir çözümü vardır. Buna bağlı olarak, x’in  Z₂₆’da değişmesine izin verirsek, ax mod 26; 26 farklı değer alır. Buda her değeri sadece bir kere alması anlamına gelmektedir. Herhangi bir y e Z₂₆ için ax º y (mod 26) denkliğinin y için tek bir çözümü vardır.

TEOREM 1.1

            ax º b (mod m) denkliğinin her b e Z_m için, sadece gcd (a,m) = 1 olduğunda tek bir x e Z_m çözümü vardır.

26 = 2 x 13 olduğundan, gcd(a,26) = 1 için a e Z₂₆ değerleri , a = 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, ve 25’dir. b parametresi Z₂₆’da herhangi bir eleman olabilir. Buna bağlı olarak Affine şifresinin 12 x 26 = 312 anahtarı vardır. (tabiki buda güvenlik için yeterli değildir.)

TANIM 1.3  a ³ 1 ve m ³ 2 tamsayılar olsun. Eğer gcd(a,m) = 1 ise a ve m aralarında asaldır. m ile aralarında asal olan Z_m’deki tamsayıların sayısı f(m) ile gösterilir. (Bu fonksiyona Euler phi-fonksiyonu denir.)

TEOREM 1.2

p_i’lerin asal sayı ve e_i > 0.1 £ i £ n olduğu yerlerde

                                                            _n                

m = P p_i ^ei  olduğunu varsayalım.

                                                        i=1

Daha sonra,

                                                                    n

f(m) = P (p_i ^ei  - p_i ^ei –1 )

                                                                   i=1

Zm üzerindeki Affine şifresi içindeki anahtarların sayısı yukarıdaki formülde verilen mf(m)’dir. (Şifreleme fonksiyonu e(x) = ax+b olduğu durumda b için seçimlerin sayısı m, ve a için seçimlerin sayısı f(m)’dir. ) Örneğin m=60 olduğu zaman f(60) = 2x2x4 = 16 ve Affine şifresindeki anahtarların sayısı da 960’dır.

            Şimdi de Affine şifresinde, m=26 modülle şifre çözme işlemini düşünelim. gcd(a,26) = 1 olduğunu varsayalım. Şifre çözmek için, x için y º ax+b (mod 26) denkliğini çözmemiz gerekir. Yukarıda anlatılanlar denkliğin Z₂₆’da tek bir çözümü olacağından bahsetmektedir. Ancak bu çözüm bize çözümü bulmak için etkin bir yöntem sunmamaktadır. Bizim için gerekli olan şey bunu yapabilmek için etkin bir algoritmadır. Neyseki, modüler aritmetikteki bazı sonuçlar bize istenilen şifre çözme algoritmasını sağlamaktadır.

TANIM 1.4  a e Z_m olsun.a’nın tersi aa^-1 º a^-1a º 1 (mod m) gibi bir a^-1 e Z_m’dir.

ŞEKİL 1.4

Affine Şifresi

	P = C = Z26  ve k {(a,b) e Z26 x Z26 : gcd(a,26) = 1}  olsun. K = (a,b) e k için, ek(x) = ax+b mod 26   ve dk(y) = a-1(y-b) mod 26   tanımlanır (x,y e Z26)

y º ax+b (mod 26) denkliğini düşünelim. Bu denklik ax º y-b (mod 26)’ya eşittir. Denkliğin her iki tarafını da a^-1 ile çarpalım :

a^-1 (ax) º a^-1 (y-b)   (mod 26)

a^-1 (ax) º (a^-1a) x º 1x º x

x º a^-1 (y-b)  (mod 26)

Şifre çözme fonksiyonu da,

d(y) = a^-1 (y-b)  (mod 26)

Örnek 1.3

K = (7,3) olsun. 7^-1 mod 26 = 15’dir. Şifreleme fonksiyonu,

e_k(x) = 7x + 3 ,

ve buna bağlı olarak şifre çözme fonksiyonu da,

d_k(y) = 15 (y-3) = 15y – 19

d_k(e_k(x)) = d_k(7x+3)

=15 ( 7x + 3 ) – 19

= x + 45 – 19

= x

Örneklemek için hot plaintext’ini şifreleyelim. Öncelikle, h, o, t harflerini modül 26’ya göre 7, 14 ve 19 olarak dönüştürürüz. Şimdide şifreleyelim :

7x7+3 mod 26 = 52 mod 26 = 0

7x14+3 mod 26 = 101 mod 26 = 23

7x19+3 mod 26 = 136 mod 26 = 6

Böylece üç ciphertext karakteri AXG’e karşılık gelen 0, 23 ve 6’dır.

1.1.4        Vigenere Şifresi

ŞEKİL 1.5

Vigenere Şifresi

	m sabit pozitif bir tamsayı olsun. P = C = k = (Z26)m tanımlansın. Bir K= (k1,k2,....,km) anahtarı için, ek(x1,x2,....,xm) = (x1+k1, x2+k2,....., xm+km)  ve dk(y1,y2,....,ym) = (y1-k1, y2-k2,....., ym-km) tanımlanır.

Kaydırma şifresinde ve Kaydırma şifresinde bir anahtar seçildikten sonra her alfabetik karakter tek bir alfabetik karaktere haritalanır. Bu nedenle, bu kriptosistemlere monoalfabetik denir. Şekil 1.5’de Vigenere Şifresi olarak adlandırılan monoalfabetik olmayan bir kriptosistemi gösterdik.

Daha önceden tanımladığımız A -> 0,  B -> 1, ........, Z -> 25 bağlantıları kullanılarak, her K anahtarını; anahtar kelime(keyword) denilen m uzunluklu bir alfabetik dizi ile bağlayabiliriz. Vigenere Şifresi, her plaintext elemanı m alfabetik karaktere eşit olduğu zaman bu karakterleri şifreler.

Küçük bir örnek yapalım.

Örnek 1.4

            m = 6 ve anahtar kelime de CIPHER olsun. Bunun numerik eşdeğeri, 

K = (2,8,15,7,4,17)’dir. plaintext’in aşağıdaki diziden oluştuğunu varsayalım:

Thiscryptosystemisnotsecure.

Bu plaintext elemanlarını aşağıdaki gibi mod 26’ya göre 6’lı gruplar halinde yazıp, anahtar kelimeyi ekleriz:

Bu alfabetik eşitliğin ciphertext dizisi :

VPXZGIAXIVWPUBTTMJPWIZITWZT.

Şifre çözmek için, aynı anahtar kelimeyi kullanırız ancak, toplama yerine mod 26’a göre çıkarma yaparız. Vigenere şifresinde, m uzunluğundaki anahtar kelimelerin sayısı 26^m ‘dir.m uzunluğunda anahtar kelimeye sahip bir Vigenere şifresinde, bir alfabetik karakter; m alfabetik karakterlerden birine haritalanabilir. (anahtar kelimenin m farklı karakter içerdiğini varsayarsak.) Böyle bir kriptosisteme polialfabetik denir. Genel olarak, kriptoanaliz polialfabetik kriptosistemlerde , monoalfabetik kriptosistemlerde olduğundan daha zordur.

1.1.2        Hill Şifresi

Bu bölümde Hill Şifresi olarak adlandırılan başka bir polialfabetik kriptosistemi tanımlayacağız. Bu şifreleme 1929 yılında Lester S. Hill tarafından bulunmuştur. m pozitif bir tamsayı olsun ve P = C = (Z₂₆)^m olarak tanımlansın. Buradaki temel fikir, bir plaintext elemanı içindeki m alfabetik karakterlerin, m lineer kombinasyonunu almaktır. Böylece, bir ciphertext elemanı içinde m alfabetik karakter üretilir.

Örneğin, m = 2 ise, bir plaintext elemanını x = (x₁ , x₂)  ve ciphertext elemanını da

y = (y₁ , y₂) olarak yazabiliriz. Burada, y₁;  x₁ ve x₂’nin lineer bir kombinasyonu olucaktır. Aynı durum y₂ içinde geçerlidir.

     y₁ = 11x₁ + 3x₂

y₂ = 8x₁ + 7x₂  ’i ele alalım.

Tabiki, bunu daha kısa olarak aşağıdaki gibi matris gösterimiyle yazmak da mümkündür :

Genel olarak, K anahtarı için mxm’lik bir matris kullanacağız. x = (x₁,........ ,x_m) e P  ve K e k için, y = e_k(x) = (y₁,....,y_m) aşağıdaki gibi hesaplanır : 

Yani, y = x K’dır. Plaintext’ten ciphertext’i bir lineer dönüşüm ile elde ederiz. Şifre çözmenin nasıl çalışacağını yani y’den x’i nasıl hesaplayacağımızı düşünmemiz gerekiyor. Şifre çözmek için K^-1 ters matrisini kullanacağız. Ciphertext şifresinin çözümü için x = yK^-1 formülü kullanılır.

            Eğer A = (a_i,j) l x m matrisi ve B = (b_j,k) m x n matrisi ise, matris çarpımı AB = (c_i,k)’yı aşağıdaki formülle tanımlarız :

                                                                        _m

c_i,k = S  a_i,j b_j,k    1 £ i £ l  ve  1 £ k £ n

                                                                        ^j=1

mxm birim matris I_m ile gösterilir. 2x2’lik birim matris :

                

Herhangi bir lxm A matrisi ve mxn B matrisi için AI_m = A  ve BI_m = B’dir. mxm A matrisinin tersi A^-1 matrisi için  AA^-1 = A^-1A = I_m. Her matrisin ters matrisi yoktur. Ancak eğer tersi varsa, bu tektir.

Elimizdeki bu açıklamalarla, yukarıda verilen şifre çözme fonksiyonunu çıkarmak kolaydır :

y = xK  denkleminde her iki tarafıda K^-1 ile çarparak :

y K^-1 = (xK) K^-1 = x (K K^-1) = xI_m = x  elde edilir.

Yukarıdaki şifreleme matrisinin Z₂₆’da tersi vardır : 

Şimdi Hill Şifresindeki şifrelemeyi ve şifre çözmeyi göstermek için bir örnek yapalım :

 TANIM 1.5  2X2’lik A = (a_i,j)  matrisinin determinant değeri :

det A = a_1,1 a_2,2 – a_1,2 a_2,1

Determinantlarda iki önemli özelliklerden bir tanesi   det I_m = 1 , diğeride 

det(AB) = det A x det B

Bir K matrisinin determinantı sıfırdan farklı olduğu durumda tersi vardır. Ancak biz Z₂₆’da işlemlerimizi yaptığımız için; K matrisinin tersi sadece gcd(det K,26)  = 1 olduğu durumlarda vardır.

Bunu kanıtlamak için öncelikle gcd(detK,26) = 1 olduğunu varsayalım. O zaman det K’nın Z₂₆’da tersi vardır. 1 £ i £ m  ,  1 £ j £ m için K matrisinin i. sırası ve i. sütunu silinerek elde edilmiş bir K_ij matrisi tanımlayalım. Değeri  (-1) ^i+j det K_ji olan bir K*  matrisi tanımlayalım. (K* matrisine adjoint matris denir.)

K^-1 = (det K)^-1 K*

Buna bağlı olarak K’nın tersi alınabilir.

Tersi olarak, K’nın K^-1 tersi olduğunu varsayalım. Determinantların çarpım kuralından;

1 = det I = det (K K^-1) = det K det K^-1.

Buna bağlı olarak da K, Z₂₆’da tersi alınabilir bir matristir. 

Şekil 1.6’da Hill Şifresi ayrıntılı olarak tanımlanmıştır.

ŞEKİL 1.6

Hill Şifresi

	m herhangi bir sabit pozitif tamsayı olsun. P = C = (Z26)m  ve k = {Z26’da mxm tersi alınabilir matrisler}    olsun. K anahtarı için, eK(x) = xK ve dK(x) = yK-1 tanımlanır.

ŞEKİL 1.7

Permütasyon Şifresi

m herhangi bir sabit pozitif tamsayı olsun. P = C = (Z26)m  ve   k, {1,.......m}’in tüm permütasyonlarından oluşsun. Bir p  anahtarı için, ep(x1,......,xm) = (xp(1),........, xp(m)) ve dp(y1,......,ym) = (yp-1(1),........, yp-1(m))     tanımlanır. (p-1, p’nin ters permütasyonudur.)

                                     

                        

1.1.2        Permütasyon Şifresi

Buraya kadar bahsettiğimiz bütün kriptosistemler kaydırmayı içeriyordu. Plaintext karakterleri yerine, farklı ciphertext karakterlerini koyuyorduk. Permütasyon şifresinde ise plaintext karakterleri değiştirilmez ancak tekrardan düzenlenerek yerleri değiştirilir.

Aşağıda Permütasyon şifresi ile ilgili bir örnek verilmiştir:

Örnek 1.6

m = 6  ve  anahtarda aşağıdaki gibi p permütasyonu olsun :

1	2	3	4	5	6
3	5	1	6	4	2

                                              

Ters permütasyon p^-1’de aşağıdaki gibidir : 

    

1	2	3	4	5	6
3	6	1	5	2	4

Plaintext’in  “shesellsseashellsbytheseashore.”  olsun.

Öncelikle plaintext’i altı harf olacak biçimde gruplara ayırırız.

shesel | lsseas | hellsb | ythese | ashore

Daha sonra bu altı harfli grupları p  permütasyonuna göre tekrardan düzenleriz.

EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS

Böylece ciphertext  EESLSHSALSESLSHBLEHSYEETHRAEOS. olur.

p^-1  ters permütasyonu kullanılarak ciphertext’in şifresi benzer şekilde çözülür.

            Gerçekte, Permütasyon şifresi; Hill şifresinin özel bir durumudur. {1,......m} kümesinin verilen bir p  permütasyonu ile aşağıdaki formülle bağlantılı bir mxm’lik

K_p = (k_ij) permütasyon matrisi tanımlayabiliriz :

 Bir permütasyon matrisinin tüm satır ve sütunlarında mutlaka 1 vardır ve geri kalan değerler 0’dır. Permütasyon matrisini, birim matrisin satır ve sütunlarının permütasyonu ile elde edebiliriz.

Yukarıdaki örnekte kullanılan p  permütasyonu için permütasyon matrisleri :

 1.1.7 Akım (Stream) Şifresi

Bu noktaya kadar incelediğimiz tüm kriptosistemlerde, plaintext elemanları aynı K anahtarı kullanılarak şifrelendi. Ciphertext dizisi y aşağıdaki gibi elde edildi :

y = y₁y₂........ = e_K(x₁) e_K(x₂)..............

Bu tipteki kriptosistemlere blok şifreler denir.

            Başka bir yaklaşım ise stream şifrelerini kullanmaktır. Buradaki temel fikir bir

z =z₁ z₂ ........ anahtar akımı meydana getirmek ve plaintext dizisi x = x₁ x₂........’i aşağıda tanımlanan kurala göre şifrelemek için kullanmaktır.

y = y₁y₂........ = e_z1(x₁) e_z2(x₂)..............

K e k  anahtar ve x₁ x₂........ de plaintext olsun. f_i fonksiyonu z_i (anahtar akımının i. elemanı)’yi oluşturmak için kullanılır. İlk i-1  plaintext karakterleri :

z_i = f_i (K, x₁........,x_i-1)

Anahtar akım elemanı z_{i ,}  x_i’i şifrelemek için kullanılır. Bu nedenle x = x₁ x₂........ plaintext’ini şifrelemek için  z₁ , y₁ , z₂ , y₂  hesaplarız. y₁y₂........ ciphertext dizisinin şifresini çözmek için de  z₁ , x₁ , z₂ , x₂  hesaplanır.

TANIM 1.6  Bir Stream Şifresi aşağıdaki koşulları sağlayan (P, C, k, L, F, E, D)’dan oluşmaktadır.

1.      P ; plaintextlerin sonlu kümesidir.

2.      C ; ciphertextlerin sonlu kümesidir.

3.      k ; anahtar alan, anahtarların sonlu kümesidir.

4.       L ; keystream alfabesi denilen sonlu bir kümedir.

5.      F = (f₁,f₂,......)   keystream generator. i ³ 1 için;

F_i : k  x  P^i-1  ->  L

6.      Her z e L için, e_z e E olmak üzere bir şifreleme fonksiyonu ve ve buna bağlı olarak

d_z e D olmak üzere de bir şifre çözme fonksiyonu vardır. e_z : P -> C ve d_z : C -> P  fonksiyonları her x e P plaintext’i için d_z(e_z (x) = x’dir.

      Block Cipher’ı, stream cipher’ın özel bir durumu gibi düşünebiliriz : tüm  i ³ 1 için

z_i = K. Bir stream cipher eğer keystream plaintext dizisinden bağımsızsa senkron’dur ve bir stream cipher tüm i ³ 1 tamsayıları için d  (z_i+d = z_i)periyodu ile periyodiktir.

      Stream cipher’lar çoğunlukla ikili alfabelerle gösterilirler. Örneğin, P = C = L = Z₂₆

Bu durumda, şifreleme ve şifre çözme işlemleri :

e_z (x) = (x + z)  mod 2

ve

d_z (y) = (y + z)  mod 2

Örnek 1.7

M = 4 ve keystream kuralı da:

z_i + 4 = z_i + z_i+1   mod 2     olsun. (i ³ 1)

Eğer keystream  (0, 0, 0, 0)’den farklı herhangi bir vektör ile başlatılmışsa, o zaman periyodu 15 olan bir keystream elde deriz. Örneğin, (1, 0, 0, 0) ile başlayan keystream :

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1,....................

 ŞEKİL 1.8

Lineer Geribeslemeli Kaydırma Regiterı (LFSR)

Bir kaydırma registerını m safhada kullanırız. (k₁,.....k_m) vektörü kaydırma registerını başlatmak için kullanılır. Herbir birimde, aşağıdaki işlemler gerçekleştirilir :

1.      k₁ bir sonraki keystream biti olarak bağlantı kurulur.

2.      k₂,....,k_m sola doğru bir safha kaydırılır.

3.   k_m’in yeni değeri,                              _m-1

S  c_j k_j+1

                                                                                              ^{j = 0}

olarak hesaplanır. (Bu “lineer geribeslemedir.”)

Örnek 1.8

Anahtar K = 8 ve plaintext   

rendezvous.    olsun.

Öncelikle plaintext’i bir sıra tamsayıya dönüştürürüz:

17    4    13    3    4    25    21    14    20    18

Keystream aşağıdaki gibidir :

8    17    4    13    3    4    25    21    14    20

İlgili elemanlara mod 26’a göre ekleme yaparız :

25    21    17    16    7    3    20    9    8    12

ve alfabetik şekilde ciphertext :

ZVRQHDUJIM.

Şimdi Alice’in ciphertext2in şifresini nasıl çözeceğine bakalım. İlk olarak alfabetik diziyi nümerik diziye çevirir:

25    21    17    16    7    3    20    9    8    12

Daha sonra sırasıyla x₁ , x₂  ,......hesaplar:

x₁ = d₈(25) = 25-8   mod 26 = 17

x₂ = d₁₇(21) = 21-17  mod 26 = 4

Her seferinde başka bir plaintext karakteri bulur ve bulduğu her karakteri bir sonraki keystream elemanını bulmak için kullanır.

ŞEKİL 1.9

Autokey Şifresi

	P = C = k = L = Z26 , z1 = K  ve zi = xi-1  (i ³ 2)  olsun. 0 £ z £ 25 için , ez (x) = x + z   mod 26 ve dz (y) = y – z   mod 26   ( x , y e Z26 )  tanımlanır.

Autokey Şifresinde sadece 26 olası anahtar olduğu için güvenli bir şifreleme değildir.

1.2 KRİPTOANALİZ

Bu bölümde bazı kriptoanaliz tekniklerinden bahsedeceğiz. Genel olarak Oscar’ın kullanılan kriptosistemi bildiği varsayılır ve buna Kerckhoff prensibi denir. Tabiki, Oscar kullanılan kriptosistemi bilmiyorsa şifreyi çözebilmesi daha zor olacaktır. Ancak biz Kerckhoff’un prensibine göre bir kriptosistemi tasarlayacağız. Yani Oscar’ın kullanılan kriptosistemi bildiğini varsayacağız.

İlk olarak, kriptoanaliz tiplerini tanımlayalım :

Sadece ciphertext

            Oscar, y ciphertext dizisine hükmeder.

Bilinen plaintext

            Oscar x plaintext dizisine ve ona bağlı olarak da y ciphertext dizisine hükmeder.

Seçilen plaintext

            Oscar, şifreleme makinasına geçici olarak erişim sağlar. Böylece, bir x plaintext dizisi seçebilir ve ona bağlı olarak bir y ciphertext dizisi yapılandırabilir.

Seçilen ciphertext

            Oscar, şifre çözme makinasına geçici olarak erişim elde eder. Böylece, bir y ciphertext dizisi seçebilir ve ona bağlı olan bir x plaintext dizisi yapılandırabilir.

Her durumda amaç kullanılan anahtarı belirlemektir. Bunlar arasındaki en zayıf tip kriptoanaliz sadece ciphertext olandır.

TABLO 1.1

26 Harfin meydana gelme olasılıkları

harf                  olasılık	harf               olasılık
A                     .082  B                     .015  C                     .028  D                     .043  E                      .127  F                      .022  G                      .020  H                      .061  I                       .070  J                       .002  K                      .008  L                       .040  M                      .024	N                    .067 O                    .075 P                     .019 Q                    .001 R                     .060 S                     .063 T                     .091 U                     .028 V                     .010 W                    .023 X                     .001 Y                     .020     Z                      .001

Tablo 1.1’e göre  26 harfi aşağıdaki gibi 5’li gruplara ayırabiliriz :

1.      E, 0.120 civarında olasılığı olan

2.      T, A, O, I, N, S, H, R   0.06  ve  0.09 arasında olasılığı olanlar

3.      D, L 0.04 civarında olasılığı olanlar

4.      C, U, M, W, F, G, Y, P, B   0.015 ile 0.023 arasında olasılığı olanlar

5.      V, K, J, X, Q, Z   0.01’den daha az olasılığı olanlar.

Bunlar dışında en çok yanyana kullanılan 30 ikili harfler : TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI VE OF. Yine yanyana çokca kullanılan 12 harf : THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR  ve DTH.

1.2.1 Affine Şifresinin Kriptoanalizi

           

Örnek 1.9

Affine şifresinden elde edilen ciphertext aşağıdaki gibi olsun :

FMXVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDK

APRKDLYEVLRHHRH

Bu ciphertext’in frekans analizi tablo 1.2’de verilmiştir.

Ciphertext’de sadece 57 karakter vardır . Ancak bu bir Affine şifresini kriptoanaliz etmek için yeterlidir. Ençok kullanılan ciphertext karakterleri şunlardır : R (8 kere tekrar etmiş), D

(6 kere tekrar etmiş), E, H, K (herbiri 5 kere tekrar etmiş)  ve  F, S, V (herbiri 4 kere tekrar etmiş). İlk tahmin olarak, e harfinin şifresi R ve t harfinin şifresi de D olarak düşünülebilir. (e ve t en çok kullanılan harflerdir.) Numerik olarak ifade edersek, e_k(4) =17  ve e_k(19) = 3. a ve b bilinmeyenler olmak üzere e_k(x) = ax + b denklemini ele alalım. Böylece iki bilinmeyenli iki eşitlik elde ederiz :

4a + b = 17

19a + b = 3

Bu sistem Z26’da a = 6 ve b = 19 olan tek bir çözüme sahiptir. Ancak bu doğru olmayan bir anahtardır. Çünkü gcd(a,26) = 2 > 1. Böylece ilk tahminimiz yanlış çıktı.

TABLO 1.2

26 Ciphertext harflerinin kullanım sıklığı

harf                  frekans	harf               frekans
A                       2  B                       1  C                       0  D                       6  E                       5  F                       4  G                      0  H                      5  I                        0  J                        0  K                       5  L                        2  M                       2	N                      1 O                      1 P                       3 Q                      0 R                       8 S                       3 T                       0 U                      2 V                      4 W                     0 X                      2 Y                      1     Z                       0

         

   

Bir sonraki tahminimiz, e harfinin şifresinin R ve t harfinin şifresinin E olduğu durum olabilir. Ancak yukarda yaptığımız işlemlerle bu seferde a = 13 bulunurki buda doğru bir tahminleme değildir. Bir sonraki olasılık, e harfinin şifresinin R ve t harfinin şifresinin H olduğu durumdur. Ancak burda da a = 8 olduğu için yanlış bir tahmindir. Bu şekilde devam ederek, e harfinin şifresinin R ve t harfinin şifresinin K olduğunu varsayalım. Bu durumda da en azından olası bir anahtar elde ederiz. Çünkü a = 3 ve b = 5 olarak hesaplanır. K = (3,5)’e göre ciphertext’in şifresi anlamlı bir dizi elde edilecekmi diye kontrol edilmek üzere çözülür. Bu şekilde (3,5)’in geçerliliği kontrol edilir.

Bu işlemleri gerçekleştirerek, dk(y) = 9y – 19 elde edilir ve verilen ciphertext’in şifresi aşağıdaki gibi çözülür :

algorithmsarequitegeneraldefinitionsofarit

      hmeticprocesses

Doğru anahtarı bulduğumuzu ispatlamış olduk.

1.2.2 Kaydırma Şifresinin Kriptoanalizi

Örnek 1.10

Kaydırma şifresinden elde edilen ciphertext aşağıdaki gibi olsun :

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Bu ciphertext’in frekans analizi Tablo 1.3’de verilmiştir.

TABLO 1.3

26 Ciphertext harflerinin kullanım sıklığı

harf                  frekans	harf               frekans
A                       0  B                       1  C                      15  D                      13  E                        7  F                       11  G                        1  H                        4  I                         5  J                        11  K                        1  L                         0  M                       16	N                      9 O                      0 P                       1 Q                      4 R                     10 S                       3 T                       2 U                      5 V                      5 W                     8 X                      6 Y                     10     Z                      20

            Z, diğer ciphertext karakterlerinden daha fazla kullanıldığı için,  d_k(Z) = e  varsayımını yapabiliriz. Geri kalan ciphertext karakterlerinden en az 10 kere tekrarlananlar da : C, D, F, J, M, R, Y. Bu harflerin, t, a, o, i, n, s, h, r  kümesinin şifrelenmiş şekli olduğunu düşünebiliriz. Ancak harflerin tekrar sayıları bize yeterli derecede bilgi vermemektedir.

            Bu nedenle, özellikle  –Z ve Z– şeklindeki ikililerin kullanım çokluklarına bakmalıyız. Örneğin, DZ ve ZW (herbiri 4 kere kullanılmış); NZ ve ZU (herbiri 3 kere kullanılmış); ve RZ, HZ, XZ, FZ, ZR, ZV, ZC, ZD, VE ZJ (herbiri 2 kere kullanılmış). WZ, 4 kere tekrarlanmış ancak ZW hiç tekrarlanmadığından dolayı, W diğer  birçok karakterden daha az tekrarlanmıştır. Bu nedenle d_K(W) = d varsayımını yapabiliriz. DZ 4 kere ve ZD de 2 kere tekrarlandığı için D_K(D) e {r,s,t} olarak düşünebiliriz. Ancak üç olasılıktan hangisinin doğru olduğu açık olarak görülmemektedir.

Eğer d_K(Z) = e ve d_K(W) = d tahminlemesi üzerinde hareket edip tekrar ciphertext’e bir göz atarsak, ZRW ve RZW’nun ciphertext’in başlarına doğru bir yerlerde kullanıldığını ve RW’nun da daha sonra tekrar kullanıldığını farkederiz. R, ciphertext’de sıkça kullanıldığından ve nd’de oldukça kullanılan bir ikili olduğundan dolayı  d_K(R) = n olasılığını deneyebiliriz.    

Bu varsayımla aşağıdakini elde ederiz :

                   - - - - - - e n d  -  - - - - - - - - - e - - - - - n e d - - - - e - - - - - - - - - - - - -

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

                  - - - - - - - - -  e - - - - - e - - -  - - - - - -  n - -  d - - - en  - - - - e - - - - - -e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

                    - e - - -  n - - - - - - -n - - - - - -  e d  - -  - e - - -  e - - -n e – n d – e - e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

                    - e d - - - - - - n - - - - - - - - - - - - - -e - - - - e d - - - - - - - d -- - - e -- n 

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Bir sonraki adımımız, NZ ortak bir ikili olduğu ve ZN olmadığı için d_K(N) = h’ı denemek olabilir. Eğer bu doğruysa, o zaman ne – ndhe plaintext parçası d_K (C) = a olmasını gerektirir. Bu tahminlere bağlı olarak aşağıdakini elde ederiz :

                   - - - - - - e n d  -  - - - - a - - - - e -a - - - n e d h - - -e - - - - - - a - - - - - -

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

                    h - - - - - - - e a - - - - e - a -  - - a - - -  n h a d -a - en  - - a - e -  h -  - e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

                    h e - a - n - - - - - - -n - - - - - -  e d  - -  - e - - -  e - - -n e a n d h e - e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

                    - e d -  a - - -  n h - - - - h a - - - - a -e - - - - e d - - - - - a - d -- - he -- n 

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Şimdide ikinci en çok kullanılan ciphertext karakteri olarak da M’i düşünelim. d_K(M) = i ya da o olabilir. (CM) ai, ao’dan daha mantıklı geldiği için öncelikle d_K(M) = i olması durumunu deneyelim. Bu şekilde aşağıdakini elde ederiz :

                   - - - - - i e n d  -  - - - - a - i - - e -a - - i n e d  h i - -e - - - - - - a - - - - i -

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

                    h - - - - -i  - e a -  i- - e - a -  - - a - i -  n h a d -a - en  - - a - e -  h  i  - e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

                    h e - a - n - - - - -  i  n -  i  - - -  e d  - -  - e - - -  e -  i n e a n d h e - e--

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

                    - e d -  a - -  i n h  i - - - h a i - - - a -e - i - - e d - - - - - a - d -- - he -- n 

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Bir sonraki aşamada o harfinin hangi harfle şifrelendiğini belirlemeye çalışacağız. Mümkün olan olasılıklar : D, F, J, Y. Y diğerlerinden daha mümkün olan gibi gözükmektedir. Bu nedenle d_E(Y) = o olduğunu varsayalım.

Üç tane en çok kullanılan ciphertext harfleri de D, F, J’dir ve bu harfler r, s, t ‘nin herhangi bir sırasını şifrelemek için kullanılabilir. N M D ‘den d_E(D) = s olarak ve H N C M F ‘den 

d_E(F) = r  , d_E(H) = c  ve  d_E(J) = t   olarak buluruz. O zaman tekrar düzenlersek :

   

       o-r  - r i e n d  -  r o - - a r  i  s e - a -  i n e d  h  i s e - - t - - -  a s s  -  i t

YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJ

                    h s -r – r i s  e a s i  - e -  a - o r a t i  on h a d  ta- en - -  a c e -  h  i  - e

NDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZ

                    h e - a s n t - o o -  i  n - i  - o-r e d  s o - e – o r e -  i n e a n d h e s ett

NZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ

                    - e d -  a c -  i n h  i s  c h a i  r -  a c et i  - t e d - -t o - a  r d s t h es- n 

XZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR

Artık örnek 1.10 için plaintext’i ve anahtarı belirlemek çok kolaydır :

Our friend from Paris examined his empty glass with surprise, as

  if evaporation had taken place while he wasn’t looking. I poured some

more wine and he settled back in his chair , face tilted up towards the

        sun.

1.2.3 Vigenere Şifresinin Kriptoanalizi

Bu bölümde Vigenere şifresinin kriptoanalizi için bazı yöntemleri tanımlayacağız. İlk adım, m ile gösterdiğimiz anahtar kelimenin uzunluğunu belirlemektir. Bunun için kullanılan birkaç teknik vardır. Bunlardan ilki Kasiski testi olarak adlandırılır, ikincisi ise raslantı indeksi kullanır.

Kasiski testi ilk olarak 1863 yılında Friedrich Kasiski tarafından tanımlanmıştır. Plaintext’in iki özdeş segmenti aynı ciphertext’e şifrelenebilir. (x º 0).

Örnek 1.11

Vigenere şifresinden elde edilen ciphertext:

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW

RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK

LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX

VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR

ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT

AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI

PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP

WQAIIWXNRMGWOIIFKEE

Öncelikle Kasiski testini deneyelim. CHR ciphertext dizisi ciphertext içinde dört yerde tekrarlanmıştır. (1, 166, 236 ve 286). Birinci tekrardan diğer üç tekrara olan mesafeler : 165, 235, ve 285’dir. Bu üç tamsayının gcd’si 5’dir. Bu da anahtar kelime uzunluğudur.

            Şimdide raslantısal indislerin hesaplanmasıyla aynı sonucu elde edip edemeyeceğimize bakalım. m = 1 ile raslantısal indeks 0.045’dir. m = 2 ile iki indis 0.046 ve 0.041’dir. m = 3 ile 0.043, 0.050, 0.047 elde ederiz. m = 4 ile 0.042, 0.039, 0.046, 0.040 indisleri elde edilir. Daha sonra m = 5 denenir ve 0.063, 0.068, 0.069, 0.061 ve 0.072 değerlerini elde ederiz. Bu da anahtar kelimenin uzunluğunun beş olduğunu kanıtlar.

Bu varsayım altında anahtar kelimeyi nasıl belirleyeceğiz?

TANIM 1.8  x = x₁x₂.....x_n  ve  y = y₁y₂....y_n’ , n ve n’ alfabetik karakterlerin dizileri olsun. x ve y’nin MI_c(x,y) ile gösterilen raslantısal ortak indeksi, x’in rasgele bir elemanının y’nin rasgele bir elemanı ile özdeş olması olasılığını tanımlar. Eğer x ve y deki A,B,C,......Z’nin frekansları f_o,f₁,.....,f₂₅ ve f_o’,f₁’,.......f₂₅’ olarak gösterilirse o zaman MI_c(x,y) şu şekilde görülür:

 ₂₅

S        f_i f '_i

                                                               MI_c(x,y)=          ⁱ⁼⁰

                                                                          ^nn’

K = (k₁,k₂,......,k_m)  anahtar kelime olduğunu varsayalım. MI_c(y_i,y_j)’i tahmin edip edemeyeceğimize bakalım. Yi ve yj’de rasgele bir karakter düşünelim.

TABLO 1.4 

Beklenen Raslantısal İndisler

ilişkili kaydırma	Beklenen MIc  değeri
0 1 2 3 4 5 6 7 8 9 10 11 12 13	0.065 0.039 0.032 0.034 0.044 0.033 0.036 0.039 0.034 0.034 0.038 0.045 0.039 0.043

                        _{25                                            25}

 MI_c(y_i,y_j) » S  P_h-ki, P_h-kj = S P_h P_h+k,-kj   olduğunu tahmin ederiz.

                           ^{h = 0                        h = 0}            

Dikkat edilirse bu tahmindeki değer sadece ki-kj arasındaki farklılığa bağlıdır. Buna ilişkili kaydırma diyoruz. Aynı zamanda, 

                                              

_{25                         25}

S  P_h P_h+1 = S P_h P_h-l

^{h = 0                    h = 0}

eşitliğinden, l’nin ilişkili bir kaydırması ,26-l’nin ilişkili bir kaydırması gibi aynı MI_c tahminini kabul eder.

0 ile 13 arasındaki  ilişkili kaydırmalar için yapılan tahminler Tablo 1.4’de gösterilmiştir.

Burda dikkat edilmesi gereken nokta, ilişkili kaydırma sıfırdan farklıysa bu tahminler 0.031 ve 0.045 arasında değişmektedir. İlişkili kaydırmanın sıfır olması durumunda 0.065 tahmin olarak kabul edilir. Bu durumu dikkate alarak, y_i ve y_j’nin ilişkili kaydırması olarak l = K_i-K_j gibi bir formül çıkartabiliriz. y_i’i sabitlediğimizi varsayalım ve e₀,e₁,e₂ ile y_j şifrelemesinin etkisini düşünelim. Sonuç dizilerini y_j⁰,y_j¹,...vb. ile gösterelim. MI_c (y_i,y_j^g) , 0 £ g £ 25 indislerini hesaplamak kolaydır. Bu aşağıdaki formül kullanılarak yapılır :

           ₂₅

S        f_i f '_i-g

                                                               MI_c(x,y^g) =       ⁱ⁼⁰

                                                                          ^nn’

g = l ve y_i ve y_j’nin ilişkisel kaydırmaları sıfır olduğu zaman, MI_c 0.65’e yakın bir değer olmalıdır. g ¹ l’nin değerleri 0.31 ile 0.45 arasında değişir.

Bu tekniği kullanarak y_i altdizilerinin herhangi iki ilişkisel kaydırmalarını elde edebiliriz.Bu da kolayca elde edilebilecek 26 olası anahtar kelime eder.

Şimdi Örnek 1.11’e dönerek bu yaptıklarımızı bir örnekle açıklayalım.

Örnek 1.11 (Devamı)
Anahtar kelimenin uzunluğunu 5 olarak belirlemiştik. Şimdi de ilişkili kaydırmaları hesaplamaya çalışacağız. Bilgisayar ile 1 £ i < j £ 5,0 £ g £ 25 olduğu yerlerde; 260 MI_c(y_i,y_j^g) değerini hesaplamak zor bir işlem değildir. Bu değerle Tablo 1.5’de gösterilmiştir. Her (i,j) çifti için, 0.065’e yakın olan MI_c(y_i,y_j^g) değerlerini aradık.

Tablo 1.5’de 6 değer kutu içine alınmıştır. Bu değerler y₁ ve y₂’nin ilişkisel kaymasının 9, y₁ ve y₅’in ilişkisel kaymasının 16, y₂ ve y₃’ün ilişkisel kaymasının 13, y₂ ve y₅’in ilişkisel kaymasının 7, y₃ ve y₅’in ilişkisel kaymasının 20 ve y₄ ve y₅’in ilişkisel kaymasının 11 olduğunu gösteren güçlü kanıtlardır. Bu sonuçlardan K₁, K₂, K₃, K₄, K₅ beş tane bilinmeyen olmak üzere aşağıdaki eşitlikleri elde ederiz :

K₁ – K₂ = 9

 K₁ - K₅ = 16

  K₂ - K₃ = 13

K₂ - K₅ = 7

 K₃ - K₅ = 20

  K₄ - K₅ = 11

Bu bize beş K_i’i K₁ cinsinden yazabilmemize olanak verir :

K₂ = K₁ + 17

  K₃ = K₁ + 4

K₄ = K₁ + 21

K₅ = K₁ + 10

TABLO 1.5

Elde edilen Ortak Raslantısal İndisler

i	j	MIc(yi,yjg)  değeri
1	2	.028     .027     .028     .034     .039     .037     .026     .025     .052 .068     .044     .026     .037     .043     .037     .043     .037     .028 .041     .041     .034     .037     .051     .045     .042     .036
1	3	.039     .033     .040     .034     .028     .053     .048     .033     .029 .056     .050     .045     .039     .040     .036     .037     .032     .027 .037     .036     .031     .037     .055     .029     .024     .037
1	4	.034     .043     .025     .027     .038     .049     .040     .032     .029 .034     .039     .044     .044     .034     .039     .045     .044     .037 .055     .047     .032     .027     .039     .037     .039     .035
1	5	.043     .033     .028     .046     .043     .044     .039     .031     .026 .030     .036     .040     .041     .024     .019     .048     .070     .044 .028     .038     .044     .043     .047     .033     .026     .046
2	3	.046     .048     .041    .032     .036     .035     .036     .030     .024 .039     .034     .029     .040     .067     .041     .033     .037     .05 .033     .033     .027     .033     .045     .052     .042     .030
2	4	.046     .034     .043    .044     .034     .031     .040     .045     .040 .048     .044     .033    .024     .028     .042     .039     .026     .034 .050     .035     .032    .040     .056     .043     .028     .028
2	5	.033     .033     .036    .046     .026     .018     .043     .080     .050 .029     .031     .045    .039     .037     .027     .026     .031     .039 .040     .037     .041    .046     .045     .043     .035     .030
3	4	.038     .036     .040    .033     .036     .060     .035     .041      .029 .058     .035     .035    .034     .053     .030     .032     .035      .036 .036     .028     .046    .032     .051     .032     .034     .030
3	5	.035     .034     .034    .036     .030     .043     .043     .050     .025 .046     .048     .041    .032     .036     .035     .036     .030     .024 .027     .030     .072    .035     .034     .032     .043     .027
4	5	.052     .038     .033    .038     .041     .043     .037     .048     .024 .028     .036     .061    .033     .033     .032     .052     .034     .027 .0392    .043     .033    .027     .030     .039     .048     .035

Herhangi K₁ e Z₂₆ için, anahtar; (K₁, K₁+17, K₁+4, K₁+21, K₁+10) şeklindedir.Şifrenin tatamıyla çözülmüş şekli aşağıda verilmiştir :

The almond tree was in tentative blossom. The days were longer, often ending with magnificient evenings of corrugated pink skies. The hunting season was over, with hounds and guns put away for six months. The vineyards were busy again as the well-organized farmers treated their vines and the more lackadaisical neighbors hurried to do the pruning they should have done in November.

1.2.4 Hill Şifresinin Kriptoanalizi

Hill şifresinin, sadece-ciphertext analizi plaintext analizinden daha zordur. İlk başta Oscar’ın kullanılan m değerini belirlediğini varsayalım. 1 £ j £ m için y_i = e_K(x_j) olmak üzere

x_j = (x_1,j , x_2,j , ......., x_m,j)  ve  y_j = (y_1,j , y_2,j , ......., y_m,j)  değerlerini elde etmiş olsun. Eğer

X =  (x_i,j)  ve  Y = (y_i,j)  mxm’lik matrisleri tanımlamışsak, K bilinmeyen anahtar olmak üzere Y = XK matris eşitliğini yazabiliriz. Y matrisi tersi alınabilir bir matris ise, Oscar K = X^-1Y anahtarını hesaplayıp sistemi kırabilir. Değilse başka bir grup m plaintext-ciphertext çifti alınır.

 1.2.5 LFSR-tabanlı Sream Şifresinin Kriptoanalizi