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:

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:

C_i ≡ P_i + K_i mod 26

P_i ≡ C_i – K_i

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:

K_i ≡ C_i – P_i 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:

(C_i,C_i+1) = M (P_i,P_i+1) , buradaki M �ifrelemede kullan�lan matristir.

�ayet kullan�c� aç�k mesaj� ve �ifreli mesaj� ayn� anda biliyorsa

(C_i,C_i+1) (P_i,P_i+1) ^-1 = M , i�lemiyle anahtar� bulabilir.

c) Affine Cipher:

Bu �ifreleme yöntemi de blok �ifreleme yöntemlerindendir a�a��daki �ekilde �ifreler:

C_i=aP_i +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 C_i ve P_i de�erlerini biliyorsa basitçe:

C_i – aP_i = b denkleminde a ile b aras�nda bir e�itlik bulur. Dikkat edilirse bu e�itlik iki bilinmeyenlidir. (C_i ve P_i 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:

C_i – aP_i = b

C_j – aP_j = 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:

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 ⁷ mod 33 = 6 , �ifreli mesaj� bulunur. Soru burada bitmektedir ancak sa�lama olarak �ifrenin do�ru aç�ld���n� gösterelim:

6 ³ mod 33 = 18 olmal�d�r ki bu durum do�rudur.

Soru 3) �stedi�iniz herhangi bir programlama dilinde y² = x³ + 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 = (3x_P² + a) / (2y_P ) , farkl� noktalar için(P ve Q) : s = (y_P - y_Q) / (x_P - x_Q), Toplam noktas� ( P + Q = R) : xR = s² - x_P - x_Q ve y_R = -y_P + s(x_P - x_R) formüllerini kullanabilirsiniz)

Soru 4) El Gamal �ifrelemesi için, p bir asal say� g ise Z_p 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 = g^x 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:

c₁ = g^y

c₂ = m h^y

Açma:

m = ( c₂ / c₁^x )

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

m₁ = c₁^x1

m₂ = c₁^x2

m₃ = c₁^x3

Bu durumda Alice gelen mesajlar ile ( c₂ / c₁^x ) i�lemini kolayca yapabilir çünkü c₁^x1 c₁^x2 c₁^x3 çarp�m de�eri de�eri için c₁^x1+x2+x3 �eklinde yaz�labilir. Bu de�er ayn� zamanda c₁^x de�erine e�ittir ( x = x1 + x2 + x3 oldu�unu hat�rlay�n�z) denklemin pay�nda bulunan terim ise c₂ 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.