Soru 0) Ayrık logaritma çözme algoritmalarının mod n için kaçar deneme yapacağını yaklaşık olarak hesaplayınız ve algoritmaları buradaki başarısına göre sıralayınız. (30 puan)
- Kaba kuvvet ile ayrık logaritma alma yöntemi mod n için en kötü n deneme gerektirir.
- Bebek ve dev adımlar algoritması Dev adım = d olmak üzere en kötü ihtimalle( n/ d + d -1) adım gerektirir.
- Shank’s algoritması için i ve j değerlerine bağlı olarak n/i ve n/j deneme yapılır, toplamda n/i + n/j denemedir.
- Pohlig Hellman algoritmasında n-1 çarpanlarına ayrılarak her çarpan için denklem çözülür. N-1 sayısının çarpanlarının toplamı m olmak üzere toplamda m deneme yeterli olur.
- Index Calculus yönteminde n sayısının n-1 sayısının çarpanlarının toplamı m olmak üzere, bu çarpanlardan elde edilen en yakın sayı da k olmak üzere m + (n-k) deneme yapılır.
Yukarıdaki algoritmalar ışığında, en kötü algoritma tartışmasız olarak Kaba kuvvettir.
Ardından şartlı olarak aşağıdaki sıralamalar yapılabilir. Aşağıda örnek bir iki sıralama verilmiştir.
i.j > m ise ve i+j > n-k ise ve m > d ise
Shanks > Index Calculus > Pohlig Hellman > bebek ve dev adımlar
i.j > m ve n-k > i + j ise ve d > m ise
Bebek ve dev adımlar > Index Calculus > shanks > pohlig hellman
Soru 1) Alice ile Bob arasındaki mesajlaşmaya saldıran Charlie, Pohlig Hellman algoritmasını kullanıyor ancak beklenenden daha hızlı mesajı çözüyor. Charlie, algoritmanın hızlanması için bebek adımları ve dev adımlarını (baby step, giant step) kullandığını söylüyor. Sizce hangi adımda nasıl bir iyileştirme yapmış olabilir? (25 puan)
Pohlig hellman algoritmasının çarpanları hesaplanırken (Algoritmadaki C terimleri), o anda kullanılan çarpanın tabanında bütün logaritmaların bulunması gerekir. Örneğin mod 5 için 5 farklı ayrık logaritma hesaplanmalıdır ve bu logaritmalar 
şekline yazılan formülden elede edilir. Bu logaritmaların hesaplanması sırasına bebek ve dev adımlar kullanılabilir.
Soru 2) 2 tabanında 6 değerini
Z11, için baby step giant step kullanarak çözünüz. Diğer bir deyişle x : 2x = 6 mod (11) sistemi için x değerini bulunuz. (20 puan)
Dev adım olarak 4 alalım:
| Dev adımlar | 0 | 1 | 2 |
| 24i mod 11 | 1 | 5 | 256 |
| 2-4i mod 11 | 1 | 9 | 4 |
| 6. 2-4i mod 11 | 6 | 10 | 2 |
Yukarıdaki değerlerden 6. 2-8 mod 11 = 21 mod 11 değeri olarak bulunur.
Bu durumda log 2 6 = log 2 21 28 mod 11 bulunur ki buradan denklem çözülmüş olur ve log 2 6 = 9 bulunur.
Soru 3) Diffie Hellman Anahtar değişim algoritmasını kullanarak 3 farklı kişi aynı anahtarı paylaşımını sağladığınızı düşünün. Ayrık logaritma çözen herhangi bir algoritma ile bu değişime nasıl saldırırsınız. Anahtar değişim modelinizin en zayıf noktası neresidir? (25 puan)
Kullanılabilir. Ortak bir mod kabul ederek herkes kendi gizli anahtarını diğer iki kişiye ulaştırırsa, üç kişide de aynı anahtar olmuş olur.
Örneğin
A -> 3
B -> 7
C-> 11
Sayılarını gizli anahtar olarak alıyorlar. Açık anahtar olarak 5 ve 29 kararlaştırılmış olsun. tarafların oluşturduğu sayıları inceleyelim:
A-> 5 3 mod 29 = 9
B-> 5 7 mod 29 = 28
C-> 5 11 mod 29 = 13
Bu ilk hesaptan sonra, bir daire şeklinde, (yani örneğin A -> B -> C -> A sırasıyla)
A’daki sonuç B’ye
B’deki sonuç C’ye
C’deki sonuç A’ya geçiriliyor ve tekrar herkes kendi gizli sayıları ile üst hesaplıyor.
A-> 13 3 mod 29 = 22
B-> 9 7 mod 29 = 28
C-> 28 11 mod 29 = 28
Son olarak bu döndürme işlemini tekrar yapıp anahtar değişimini hesaplamış oluyoruz:
A-> 28 3 mod 29 = 28
B-> 22 7 mode 29 = 28
C-> 28 11 mod 29 = 28
Görüldüğü üzere tarafların tamamında 28 sonucu bulunmuştur.
Yukarıdaki bu sayısal örneği aşağıdaki matematiksel durulmada göstermek mümkündür:
İlk hesaplamada :
A-> p a mod g
B-> p b mod g
C-> p c mod g
Değerlerini hesaplıyorlar (a,b ve c sırasıyla A, B ve C taraflarının gizli sayıları)
Ardından bu sayılar sırayla komşulara iletiliyor:
A-> p ca mod g
B-> p ab mod g
C-> p bc mod g
Değerlerini hesaplıyorlar. Son olarak 2. Değiştirme ile birlikte tarafların hepsinde p abc mod g deperi bulunuyor.
Bu değişim aşağıdaki üçgen ile de gösterilebilir:
Sırasıyla dönüşüm yapılmaktadır. Dolayısıyla her geçişten sonra taraflardaki değerler aşağıda gösterilmiştir:
Yukarıda, 3 geçişin her birisinde taraflarda olan sayı değeri gösterilmiştir.
Saldırgan taraf, yukarıdaki modele, geçirilen değerlerden en az iki tanesini ele geçirerek ve en az iki adet ayrık logaritma çözerek erişebilir. Şayet tek bir değeri ele geçirip ayrık logaritmasını çözerse, tek tarafın anahtarını bulur. Bu bulunan değer ise diğer anahtarlar bilinmediği için bir işe yaramaz. Sadece diğer anahtarların bulunmasını kolaylaştırır.