Süre 60 dakika sınav kapalı kitaptır. Sınavda hesaplama aletleri kullanılabilir ancak herhangi bir şekilde hafızalı veya programlanabilir cihazlar kesinlikle yasaktır. Her soru 20 puandır. Son soru 30 puandır. Herkese başarılar J

Soru 0) isminizin ve soy isminizin ilk harflerini shift cipher, substitution cipher ve stream cipher ile şifreleyiniz.

Çözüm: İsim: Şadi Şeker , Baş harfleri ŞŞ , İngiliz alfabesindeki karşılığı : SS

Alfabe:

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25



S -> 18

shift cipher : Anahtar 2 alınmıştır : 18 + 2 = 20 , şifreli mesaj : UU

Substitution cipher: Anahtar için yerine koyma tablosu kullanılmıştır Bu tabloda örneğin 18 -> 5 olarak işaretlenmiş olsun. Şifreli mesaj : FF

Stream Cipher: Örnek stream cipher için birinci şifrelemenin sonucu ikinci şifrelemede anahtar olarak kullanılsın ve shift cipher her blok için işleniyor olsun ve ilk anahtar olarak 2 alalım.

Bu durumda S = 18 + 2 = 20 olarak ilk mesaj şifrelenecek.

S=18 +20 = 38 mod 26 = 12 = M olarak ikinci blok şifrelenecek. Şifreli mesaj : UM

Stream cipher için en basit örnek çözüm olup farklı algoritmalar kullanmış olabilirsiniz





Soru1) Aşağıdaki şifreleme sistemlerinden hangilerinde bilinen açık mesaj saldırısı (known plain text) başarılı sonuç verir? İddialarınızı örnek ile gösterip açıklayınız.

a)Viegnere Cipher

b)Hill Cipher (2x2 matris ile kabul edebilirsiniz)

c)Affine Cipher


Çözüm:

Bu yöntemlerin hepsinde bilinen açık mesaj saldırısı başarılı sonuçlar verir. Kısaca tekalfabeli (monoalphabetic) yerine koyma şifrelemelerinin (substitution cipher) hepsinin bilinen açık mesaj saldırısına karşı zaafiyeti vardır. .

a) Viegnere Cipher:

Blok şifrelemesidir ve her bloğun anahtar kadar kaydırılması ile şifreler. Dolayısıyla sistem aşağıdaki şekilde modellenebilir:

Ci Pi + Ki mod 26

Pi Ci – Ki

Bilinen açık mesaj saldırısında saldıran taraf hem açık mesajı hem de şifreli mesajı bilmektedir. O halde saldıran kişi:

Ki Ci – Pi mod 26 , işlemi ile kolayca anahtarı bulabilir. Bunu bir blok için yapan saldırgan yeterince uzun bir mesaj bilgisine sahipse (tercihen blok uzunluğu veya daha fazla) anahtarın tamamını elde edebilir.


b) Hill Cipher:

Blok şifrelemesidir ve örneğin 2x2 anahtarı için aşağıdaki şekilde şifreleme yapar:

(Ci,Ci+1) = M (Pi,Pi+1) , buradaki M şifrelemede kullanılan matristir.

Şayet kullanıcı açık mesajı ve şifreli mesajı aynı anda biliyorsa

(Ci,Ci+1) (Pi,Pi+1) -1 = M , işlemiyle anahtarı bulabilir.


c) Affine Cipher:

Bu şifreleme yöntemi de blok şifreleme yöntemlerindendir aşağıdaki şekilde şifreler:

Ci=aPi +b mod 26

Buradaki formül, y = ax + b doğrusal bağlantısına benzediği için doğrusal anlamında affine şifrelemesi olarak isimlendirilmiştir.

Şayet saldıran kişi Ci ve Pi değerlerini biliyorsa basitçe:

Ci – aPi = b denkleminde a ile b arasında bir eşitlik bulur. Dikkat edilirse bu eşitlik iki bilinmeyenlidir. (Ci ve Pi bilindiğine göre) Bu durumda iki bilinmeyenli denklemi çözmek için ikinci bir mesajın daha şifreli haline ihtiyacı vardır bu mesaj ile birlikte:

Ci – aPi = b

Cj – aPj = b

şeklinde iki adet iki bilinmeyenli denklem elde edilir ve istenilen yöntem ile çözülebilir.



Soru2) RSA algoritması kullanarak şifreleme yapan bir sistem geliştiriniz. Anahtar kullanımı için sayıları siz belirleyiniz ve isminizin ilk harfini şifreleyiniz.

Çözüm: Öncelikle anahtarlar oluşturulur.

n = p x q şeklinde bir n değeri seçilir.

Örneğin p = 11ve q = 3 olsun.

Bu durumda n = 33 bulunur.

Bu sayının totient fonksiyon değeri hesaplanır:

φ(n) = (11-1)(3-1) = 20

Bu sayıdan (20'den) küçük ve aralarında asal bir başka sayı seçilir (hususî anahtar, private key)

d= 3 olsun.

Bu sayının n için tersi alınır (yani fd = 1 mod n olan sayı)

uzatılmış öklite göre:

Q

X1

X2

X3

Y1

Y2

Y3

T1

T2

T3

6

1

0

20

0

1

3

1

-6

2

1

0

1

3

1

-6

2

-1

7

1


Yukarıdaki yönteme göre sayının tersi 7 olarak bulunmuştur. Dolayısıyla 3 x 7 = 1 mod 20 denklemini sağlayan değer bulunmuştur.

Buna göre umumi şifre (public key) : (7,33)

hususi şifre (private key) : (3,33) olarak seçilmiştir.

Artık şifrelemeye geçilebilir:

mesaj olarak ismimizin ilk harfini Ş -> S -> 18 alalım. 18 7 mod 33 = 6 , şifreli mesajı bulunur. Soru burada bitmektedir ancak sağlama olarak şifrenin doğru açıldığını gösterelim:

6 3 mod 33 = 18 olmalıdır ki bu durum doğrudur.

Soru 3) İstediğiniz herhangi bir programlama dilinde y2 = x3 + x + 2 elipsel eğrisine (elliptic curve) göre P(1,1) noktasından oluşturulabilecek dairesel grubu (cyclic group) oluşturunuz ve bu grubu kullanarak isminizin ilk harfini şifreleyiniz (bildiğiniz herhangi bir yöntemi kullanabilirsiniz)

(Hatırlatma: eğim eşit noktalar için (P) : s = (3xP2 + a) / (2yP ) , farklı noktalar için(P ve Q) : s = (yP - yQ) / (xP - xQ), Toplam noktası ( P + Q = R) : xR = s2 - xP - xQ ve yR = -yP + s(xP - xR) formüllerini kullanabilirsiniz)





Soru 4) El Gamal şifrelemesi için, p bir asal sayı g ise Zp için bir üreteç (Generator) ve x de hususî (private) anahtar olsun. Anahtar x bilgisini daha gizli tutmak için 3 parçaya bölerek 3 farklı sunucuda saklamak istiyorsunuz. Buna göre sunuculardan birisine saldırarak x anahtarının bir kısmını ele geçiren kişinin, x anahtarının tamamı hakkında fikri olmamalı. Senaryomuza göre 0 ile p-1 arasında 3 adet rast gele sayı seçiliyor ve bu sayıların toplamı (x1+x2+x3 = x mod p-1) olarak kabul ediliyor. Her x değeri de farklı bir sunucuda saklanıyor.

a) El Gamal şifrelemesi hakkında açıklayıcı bilgi vererek şifreleme algoritmasının nasıl çalıştığını anlatınız.

b) Alice, C şifreli metnini açmak isterse aşağıdaki adımları yaparak bunu gerçekleştirebileceğini ispatlayınız:

a. C mesajını 3 sunucuya yollar

b. Her sunucu kendisinde bulunan x parçası ile mesajı açar ve Mi mesajını Alice’e geri yollar.

c. M1,M2 ve M3 bilgilerini alan Alice, mesajı oluşturabilir.

c) Şayet 3 sunucuda bulunan anahtarlardan herhangi iki tanesinin mesajı açmak için kullanılabilmesini isteseydik nasıl bir yöntem geliştirmemiz gerektiğini açıklayınız. ( bu soru için sunucular arası iletişim olmadığını kabul ediniz ayrıca gerekli görürseniz bir sunucuda birden fazla anahtar barındırılabilir)

Çözüm :

a) http://shedai.net/bilgisayar/2008/04/30/el-gamal-encryption-el-cemal-sifrelemesi/ adresini okuyunuz. (cevabınız bu kadar detaylı olmamakla birlikte en az anahtar üretimi, şifreleme ve şifre açma aşamalarını (Ya da sadece formüllerini) barındırmalıdır.) Örneğin aşağıdaki cevap tam puan alabilir:

Anahtar üretimi:

Alice q derecesinde bir G grubunu g üreticisi (Generator) ile üretir. Alice bu gruptan { 0 , … , q-1 } rasgele bir x değerini seçer. Alice h = gx değerini hesaplar.

Bu işlemler sonucunda Alice , g, G , q ve h değerlerini umumî anahtar (public key) olarak yayınlar. Hususi şifre olarak (private key) ise x değerini saklar.

Şifreleme:

c1 = gy

c2 = m hy

Açma:

m = ( c2 / c1x )


b) Her sunucudaki farklı x parçası ile aşağıdaki işlemin yapıldığını düşünelim

m1 = c1x1

m2 = c1x2

m3 = c1x3

Bu durumda Alice gelen mesajlar ile ( c2 / c1x ) işlemini kolayca yapabilir çünkü c1x1 c1x2 c1x3 çarpım değeri değeri için c1x1+x2+x3 şeklinde yazılabilir. Bu değer aynı zamanda c1x değerine eşittir ( x = x1 + x2 + x3 olduğunu hatırlayınız) denklemin payında bulunan terim ise c2 terimidir. Dolayısıyla mesaj açılmıştır.

c)Bu soru chinese remainder probleminden öğrendiğimiz yöntem ile ya da moduler aritmetikte kullandığımız ters alma yöntemine göre (uzatılmış öklit ile tersi alınması gibi) çözülebilir.

Örneğin soru 2'de kullanılan sayıları kullanalım. 3 x 7 = 1 mod 20 denklemindeki herhangi 2 sayıyı bilen kişi 3. sayıyı bulabilir (buradaki sayılar 3,7 ve 20'dir) ancak 1 tanesini bilen kişi diğer ikisini bulamaz.