Beterin beteri: Ayrık Logaritma Problemi

Bir önceki yazımızda açık anahtar algoritmalarının pek çoğu çarpanlara ayrılmanın zorluğuna (RSA’deki gibi) dayanır demiştik. Geldik beterin beterine. Discrete Logarithm Problem (DLP) yani ayrık logaritma problemi. Daha çok soyut matematik alanında kullanılır. Şimdi en basit haliyle, şu şekilde hayal etmenizi istiyorum. Sarı boyanız var içine biraz mavi karıştıralım. Karıştırdınız ne çıktı, yeşil. Yeşili normal logaritma olarak hayal edelim. Normal logaritma üst alma işleminin tersidir. Doğal ya da karmaşık sayılar için $ log_a b $ logaritmanın gösterimi $ a^x = b $ işleminin tersidir ve sonucumuzda x değeridir. Logaritma işlemimiz yeşil demiştik. Ayrık logaritma ise karmaşık veya doğal sayılar üzerinde tanımlı değil, dairesel (cyclic group) gruplar üzerinde tanımlıdır ve n elemanlı sonlu bir döngüsel grup olan G grubu için $ g^x = h $ ifadesinin tersini verir, h’nin g tabanındaki ayrık logaritması denir. Ne diyorsun diyenler için elinizdeki yeşil boyayı çıkarın masanın üzerine. Sarı boyayı ayırmaya çalışın, bekliyorum. İşte bunu ayırmak ne kadar zorsa ayrık logaritmadaki x’i bulmak o denli zordur. Deneme yanılma ile halledilebilirim diyen BruteForce meraklılarına sesleniyorum (-ki size pyhton’da güzel bir algoritma yazdım göreceğiz birazdan) bunlar 6 basamağı aşan sayılar olunca iş biraz zorlaşıyor gençler (!) biraz derken geri çevrilmesi zamanla kıyaslanınca imkansız gibi birşey. Hala sarıyı ayıramadınız, o halde fırçayı bırakalım ve yazıyı okumaya devam edelim.

10583096_1654088661539655_1600501156_n

Ayrık logaritmaları anlamamızın en kolay yolu $ (Z_p)^* $ olan congruence class (denklik sınıfı) dır. Bu sınıf {1, …, p − 1} denkliklerini ihtiva eden bir kümedir ve asal sayı p modunda çarpmaya göre kapalıdır. Bu küme üzerinden yapılan herhangi bir işlem yine bu küme içerisinden sonuç verir. Yani anlayacağımız şey kısaca, bu küme üzerinde herhangi bir işlem yaptınız ve yapılan her işlem p tabanında modulo olarak alınır. Modulo p işlem kümesi diyebiliriz, p asal olmak şartı ile. Örneğin bir elemanın k’ıncı kuvvetini yani üst değerini bulmak istediniz diyelim önce tamsayılar kümesinde sonucu bulup p değerine bölersiniz ve sonuç bölme işleminin kalan kısmıdır. İşte bu kalan k’yı verir. Bu işleme, ayrık kuvvet alma işlemi denir. Basit bir örnek yapalım. Yeşili elde ediyoruz bakın: $ (Z_{17})^* $ denklik sınıfında $ 3^4 $ işlemini ele alalım. Biliyoruz ki $ 3^4 = 81$ dir. 81 sayısının 17 ile bölümünden kalan 13 dir. Sonuç olarak $ (Z_{17})^* $ denklik sınıfında  $3^4 = 13 $ dir. Yani elimizdeki yeşil boya bu.

Ayrık logaritma ise bu kuvvet alma işlemin tersidir. Yani $ 3^k = 13\: (mod 17) $ ifadesini ele alalım. Buradaki k değerinin 4 olduğunu görmüştük fakat bu tek çözüm değildir.  3’ün üssünü k sayısına yükselttiğimizde çözüm eşit olasılıkla 0 ile 17 arasında kalan sayılardan biri olacaktır.  Fakat bu işlemin tersi zordur. Örneğin $ 3^{16} = 1\: (mod 17) $ dir. n tam sayı olmak şartıyla, tüm çözümler için şunu yazabiliriz $3^{4+16n} = 13 x 1^n = 13\: (mod 17) $ dir. Bu yüzden, 4+16n şeklinde sonsuz çözüm vardır. Çözüm kümesini  k ≡ 4 (mod 16) şeklinde de ifade edilebiliriz.

Hemen bir örnek yapalım. 2 sayısının  $ (Z_{37}) $ da bir ilkel kökü (primitive root) olup olmadığını bulalım ve  $ (L_2 (19)) $ ayrık logaritma değerini bulalım. 2 sayısının ilkel kökünün bulunması demek, herhangi bir üstünün mod 37’de 1’e eşit olması
demektir. $ (L_2 (19)) $ değeri ise, 2 sayısı ile ürettiğimiz grubun 19 değerine sahip olduğu eleman sayısıdır. Bu işlemi yapabilmek için BruteForce’cu arkadaşlarımızı sahneye davet ediyoruz çünkü bütün üstleri tek tek deneyeceğiz. Fakat birazcık python biliyorsak bunu kolaylıkla çözebiliriz.

$ 2^1 = 2\ mod 37$
$ 2^2 = 4\ mod 37$
$ 2^3 = 8\ mod 37$
…….
$ 2^{35} = 19\ mod 37$
$ 2^{36} = 1\ mod 37$

Bunu python’da $ (Z_{37}) $ da bir ilkel kökü (primitive root) olup olmadığını şu şekilde buluyoruz:

12545802_1662805330667988_1128934067_o

 

Algoritmaya şöyle üstünden bakarsak, Primitif kök modülo m, mod m’de sıfır olmayan tüm sayıların üslerini yaratabilen bir b sayısıdır. 1 den m’ye kadar mümkün olan bütün değerleri dener, bulunduğunda çıktısını verir. Ayrıca birden fazla çözüm olabileceğini unutmayın. Bu durumda algoritmamız en küçük olası bir değer yazacak veya -1 döndürecek.

şimdi buradaki bahar(b, c, m): değerlerinin anlamını açıklayalım:
b=taban yani örneğimizden gidersek 2, c=1 ilkel kökünü bulmak istediğimiz için 1 değerini verdik, m=37 modulus olarak yazdık ve bize ilk pencerede görmüş olduğunuz 36 sonucunu verdi. (Hatırlarsanız bunu başka şekilde de bulabiliriz: Fermat’ın küçük teoreminde $a^{p-1}=1\ mod p $ p asal ve a’yı bölmemek şartı ile. )

Ayrık logaritmasını bulmak için ise c=19 değerini yazmamız yeterlidir:

12544713_1662805380667983_1455501860_o

 

Ayrık logaritması ise $ (L_2 (19))\ =35 $ dir ve ilkel bir kökü olduğunu söyleyebiliriz. Tabi asal sayımız büyüdükçe işler karışacak örneğin:

7337488745629403488410174275830423641502142554560856136484326749638755396267050319392266204256751706077766067020335998122952792559058552724477442839630133

154 basamaklı bir asal sayı görüyoruz, bunu modulus olarak kullanmayı deneyin polinom zamanda çözülemeyeceğini göreceksiniz. Torunlarınızın torunları belki görebilir. Dünya üzerindeki işlem gücünün tamamına erişiminiz olsa bile bu olasılıkları denemek binlerce yıl sürebilir. Tek yönlü fonksiyonları güçlü kılan şey tersine çevrilebilmeleri için gereken zamandır. Buna karşın, Peter Shor tarafından keşfedilmiş kuantum bilgisayarlarda çalışan, polinom zamanlı verimli bir algoritma bilinmektedir. Buradan buyurun. Evet çarpma işlemini kullanarak deneme yanılma yöntemini kullanmak isteyen arkadaşlara yukarıdaki asal sayıyı hediye ederek, bir sonraki yazımızda görüşmek üzere diyorum. Öptüm.

B.

About Bahar Uğurdoğan

Kriptolojistimsi.

One thought on “Beterin beteri: Ayrık Logaritma Problemi

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

*

Şu HTML etiketlerini ve özelliklerini kullanabilirsiniz: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>