Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bir çarpanlara ayırma yöntemi olan oransal eleği anlatmaktır. Bu yöntem, veri güvenliğinde çarpanların dayandığı matematiksel zorluk üzerine kurulu olan algoritmalara saldırı için kullanılır. Örneğin RSA. Algoritmanın çalışmasını anlatarak başlayalım:

Öncelikle elimizde, asal çarpanlarına ayırmak istediğimiz, bir asal olmayan sayı (bileşik sayı, composite number) bulunduğunu düşünelim. Bu sayıya n diyelim. Kesirli kalbur yönteminde, asal çarpanlar için bir üst limit belirlenir.

Algoritma bu limitten küçük çarpanlar üzerinde çalışır. Bu çarpanlar kalbur (sieve) üzerinde eleme yapmak için kullanılır. Bu limite daha sonra dönüp detaylıca açıklayacağız ancak şimdilik en büyük asal sayı limiti olarak b sınırını belirleyelim ( b sayısı asal sayıdır). Bu sayı P kümesinde (asal sayılar kümesi P = { 2,3,5,7,11,13 … } şeklinde giden asal sayılardır) en büyük asal sayıyı belirtir. Örneğin b=11 demek, kümemizin B= {2,3,5,7,11} olması demektir.

Ardından bu asal sayılar kümesindeki sayılarımızı (B kümesindeki) kullanarak bir rast gele çarpan elde ediyoruz ve buna z ismini verelim.

z+n denemesi ile elde ettiğimiz sayının çarpanlarının B kümesinde olup olmadığına bakıyoruz ve şayet bu durumu sağlayan yeterli sayıda denklem elde edersek çarpanlara ayırma işlemini başarıyla tamamlıyoruz çünkü a2≡b2 (mod n) şeklinde bir denklem elde etmiş oluyoruz ve bu denklem Fermat’ın çarpanlara ayırma yöntemine göre çözülmüş sayılır.

Yukarıdaki algoritmanın çalışmasını bir örnek üzerinden anlatmaya çalışalım.

Örnek

Çarpanlarına ayırmak istediğimiz sayı, 187 olsun. ( n = 187)

Önce bir limit değeri belirliyoruz. Örneğin, limit sayımız 7 olsun ( b = 7 ve dolayısıyla B = { 2,3,5,7 } )

Şimdi denklemlerimizi yazabiliriz.

  • 21305070 = 2 ≡ 189 = 20335071………….(1)
  • 20305170 = 5 ≡ 192 = 26315070………….(2)
  • 20325070 = 9 ≡ 196 = 22305072………….(3)
  • 23305071 = 56 ≡ 243 = 20355070………….(4)

Yukarıdaki denklemlerde, rast gele olarak B kümemizdeki asal sayıların üstleri değiştirilmiş ve farklı sonuçlar elde edilmiştir. Elde edilen bu sonuçların ( mod 187 ) için denk olduğu değerler, ve bu denk oldukları değerlerin de çarpanları yazılmıştır. Örneğin 3 numaralı denklemde, 9 ile 196 mod 187 denktir ve dolayısıyla 20325070 ≡ 22305072 değerleri denk olur.

Bu aşamadan sonra hâtî cebir (doğrusal cebir, linear algebra) kullanarak eleme işlemi yapılabilir. Yani yukarıdaki denklemleri bir masfuf (matrix) olarak görmek mümkündür:

 

1

0

0

0

0

0

1

0

0

2

0

0

3

0

0

1

=

0

3

0

1

6

1

0

0

2

0

0

2

0

5

0

0

 

Yukarıdaki iki masfuf (matrix) sayıların üstlerinden elde edilmiştir. Bu masfuf üzerinde satır ve sütun elemeleri yapılarak denklem çözülebilir.

Örneğin 1. Satır ve 4. Satırları ele alalım ve bu iki satırın toplamından çıkan satırı yazalım :

 

4

0

0

1

=

0

8

0

1

 

Yukarıdaki eşitliğin elde edilmesi, üstlerin toplanması ile olmuştur. Aslında bu işlem sayıların çarpılmasıdır. Matris formundan denkleme geri döner ve yukarıdaki çıkarımı denklem üzerinden bir kere daha izlersek:

  • 21305070 = 2 ≡ 189 = 20335071………….(1)
  • 23305071 = 56 ≡ 243 = 20355070………….(4)

Satırları çarpılmıştır:

  • 24305071 = 112 ≡ 45927 = 20385071………….(1) x (4)

Yukarıdaki matris, elde edilen bu denklemin üstlerini tutmaktadır. Bu aşamadan sonra denklemleri sadeleştirebiliriz. Örneğin yukarıdaki denklemin her iki tarafından bulunan 7 değerini eleyelim:

  • 24305070 = 16 ≡ 6561 = 20385070………….(1) x (4) / 7

Biraz daha ilerletip, yukarıdaki denklemleri 2. dereceden yazmaya çalışalım. Örneğin 24 = 42 olarak yazılabilir ve benzer şekilde 38 = 812 şeklinde yazılabilir. Bu sayede denklemin iki tarafında da ikinci dereceyi elde etmiş oluruz:

42 812

Bu adımdan sonra çarpanlara ayırma işlemi tamamlanmış olur çünkü iki kare farkını yakalarız:

a2 ≡ b2

şeklindeki denklemden a2-b2 = (a-b) (a+b) açılımı yapılabileceğine göre, çarpanlarımız 81-4 ve 81+4 olur. Bu sayıların mod 187’de olduğunu hatırlarsak, 187 ile aralarındaki bölenlerin en büyüğünü alıyoruz.

gcd(81-4,187) × gcd(81+4,187) = 11×17 olarak iki çarpanı 11 ve 17 bulmuş oluruz.

Yorumlar

  1. Süha

    Sayın Hocam,
    Burada bizim istediğimiz değerleri sağlayacak denklemleri nasıl ayırabiliriz? Hepsini ikişer ikişer denemek mi gerekiyor? Açıklarsanız sevinirim.
    Örneğin 2 ve 3 ncü denklemlerle sonuca ulaşamadım. Yoksa ben mi yanlış işlem yaptım?

  2. Şadi Evren ŞEKER Article Author

    Hayır her ikili her zaman sonucu vermez hatta bazı durumlarda bu yöntemin kullanılamaması da söz konusudur. Genel bir tecrübe olarak denklemler arasında farklı iki sayı üzeri olma şartı ararsanız çalışır. Örneğin yukarıdaki örnekte sadeleştirmeden sonra soldaki denklem 2 sağdaki denklem 3 cinsinden tek bir asal sayı olarak kalmıştır. Bu durum iki kare farkı yakalamak için avantaj sağlar ancak dediğim gibi farklı sebeplerden dolayı her zaman çalışmayabilir.

    Başarılar

Bir Cevap Yazın

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


− iki = 2