Yazan : Şadi Evren ŞEKER

Bu yazının amacı, özellikle veri güvenliği konusunda, çarpanlara ayırmaya dayanan zorluk üzerine inşa edilmiş olan şifreleme algoritmalarına bir saldırı için kullanılan ikinci derecenden kalbur (quadratic sieve) konusunu açıklamaktır.

Sistem kabaca bir sayıyı çarpanlarına ayırır. Bu ayırma işlemi aşağıdaki adımlardan oluşur.

Ö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ın n sayısı ile legrende sembolünü buluyoruz ve bu değer sayılarımız asal sayı olduğu için -1 veya 1 çıkıyor. Bu sonuçlardan 1 çıkaranları alıyor ve -1 sonucu verenleri B kümesinden eliyoruz.

Ardından kalbur işlemi (eleme, sieving) devreye giriyor ve hedef aralık belirleyerek bu aralıktaki sayıları eliyoruz. Hedef aralık hesaplanırken n sayısının kareköküne yakın değerler hesaplanır.

Bu değerlerden B kümesindeki sayılar ile çarpan şeklinde yazılabilenleri alıyor, geri kalanlarını eliyoruz. Kalan kümemize H ismini verelim. Sonuçta elde ettiğimiz sayılardan iki sonuç elde edeceğiz.

x = H kümesindeki sayıların çarpımı

y = h , H kümesinin her bir elemanı olmak üzere h2-n şeklinde yazılsan sayıların çarpımının karekökü

Sonuçta x2≡y2 (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 ve son adım olarak iki çarpan:

gcd(x-y , n ) ve gcd (x+y,n) olarak elde edilir.

Yukarıda anlatılan bu algoritmayı bir örnek üzerinden anlamaya çalışalım:

Örnek

Çarpanlarına ayırmak istediğimiz sayı n = 87463 olsun.

b = 37 seçimini yaptığımızı kabul edelim.

P = {2,3,5,7,11,13,17,19,23,29,31,37} şeklinde asal sayılar kümesini elde edeceğiz. (bu kümenin elde edilmesi ile ilgili kalbur problemi başlıklı yazıyı okuyabilirsiniz)

Bu asal sayılar kümesinin her elemanı için legrende sembolünü uygulayalım ve sonuçlarını aşağıdaki şekilde bir tablo haline getirelim:

Yukarıdaki şekilde elde ettiğimiz sayılardan 1 sonucunu verenleri bırakıyor ve -1 sonucunu verenleri eliyoruz. Bu durumda kümemiz:

B= {2,3,13,17,19,29} halini alıyor.

Eleme adımına başlamak için bir aralık belirliyoruz. Çarpanlarını bulmaya çalıştığımız n değerinin karekökü etrafında bir değer olacağı için 87463 sayısının karekökünü alıyoruz. Bu değer yaklaşık olarak 295 sonucunu verir ve biz de 260 ile 330 sayıları arasındaki sayılarda eleme işlemi yapacağız. Aradığımız sayılar, B kümesindeki sayılar cinsinden çarpanlara ayrılabilen sayılardır.

Bulduğumuz sayılar :

H = {265, 278, 296, 299, 307 , 316} sayılarıdır.

Bu kümedeki sayıları h2-n bölümünde, çıkan çarpanlarına göre aşağıdaki tabloyu hazırlıyoruz:

Yukarıdaki tabloda, her satır, ilgili kümedeki sayının çarpanlarıdır.

Örneğin 265 sayısını ele alalım.

2652 = 70225

70225 – 87463 = -17238 = -1 x 2 x 3 x 132 x 17

Şeklinde yazılabilen sayıdır. Bu durumda 265 sayısının çarpanları, yukarıdaki tabloda görüldüğü gibi işaretlenir.

Yukarıda elde ettiğimiz matrisin tersyüzünü alıp (transpose), sonucu 0 yapan vektörü arıyoruz (yöney, vector)

Bu sonuca ulaşan birden fazla vektör bulunabilmektedir. Bunlardan bir tanesi aşağıda verilmiştir:

V= ( 1,1,1,0,1,0 )

Ardından bulduğumuz V vektöründe 1 değerinin bulunduğu sıradaki H kümesinin elemanlarını alıyoruz. 0’a tekabül eden sayıları eliyoruz.

H = {265, 278, 296, 299, 307 , 316} idi, bu kümedeki 4. Ve 6. sayılara, V vektöründe 0 gelmiştir. Bu sayıları eliyoruz ve kümemiz:

H = {265, 278, 296, 307 } halini alıyor.

Kümemizin son haline ulaştıktan sonra x ve y değerlerini üretebiliriz.

x sayısını, H kümesindeki elemanların çarpımından oluşur :

x = 265.278.296.307 = 6694540240 º 34757 (mod n)

Denklemini çözdüğümüzde ise:

y = 13497354 º 28052 (mod n) sonucunu elde ediyoruz.

Bulduğumuz x ve y değerlerini denkleme yerleştirirsek :

gcd (x-y ,n) gcd (x+y , n) çarpımı:

= gcd(34757 – 28052, 87463) gcd ( 34757 + 28052 , 87463)

= gcd ( 6705, 87463) gcd (62809, 87463)

= 149 x 587 olarak çarpanları bulmuş oluyoruz. Gerçekten de bu çarpımın sonucu 87463 olarak bulunabilir.

Yorumlar

  1. BAHAR

    Merhaba, öncelikle B sayısını neden 37 seçtiğimizi sormak istiyorum. Ayrıca (260,330) aralğnı neye göre seçtiğimizi ve son olarak bu ralıktan seçtiğimiz sayıların yani H kümesinin neye gööre seçildiğini hiç anlamadım. Ve yarın sınavım var, bugün cevpalayabilirseniz çok sevinirim. şimdiden teşekkürler

  2. Şadi Evren ŞEKER Article Author

    Merhaba;
    37 sayısı asal sayılar kümesindeki herhangi bir sayı. Kalburumuzu oluşturacağımız limit değeri ve yazıda P olarak isimlendirilen küme (asal sayılar kümesi) 37 sayısına kadar olan sayıları içeriyor. Bu sayıyı istediğimiz gibi seçebiliriz (asal sayı olmak şartıyla). Sayının büyük olması kalburun her adımındaki işlem sayısını arttırırken sayının küçük olması ise toplam işlem sayısını arttırır. Çarpanlarına ayrılmak istenen sayıya göre büyütmek mantıklıdır. Belki bu sayının hesaplanması ve optimum değerin bulunması için bir yol bulunabilir ama benim bildiğim böyle bir yöntem yok.

    260,330 aralığı ise, çarpanlarına ayırmak istediğimiz sayının, kareköküne yakın değerlerdir. Örnekte karekök değeri 295 ve biz bu sayının 35 aşağı ve 35 yukarı değerlerini alıp aralık belirledik.

    H kümesi ise bu aralıktaki (260,330 sayıları arasındaki) sayılardan B kümesindeki sayıların çarpımı cinsinden yazılabilen sayılardır.

    Örneğin yazıda 265 sayısı için örnek verilmiştir:

    265^2 = 70225

    70225 – 87463 = -17238 = -1 x 2 x 3 x 13^2 x 17

    Tekrar etmek gerekirse, H kümesindeki sayılar h^2-n denkleminin sonucu B kümesindeki çarpanlar cinsinden yazılabilen sayılardır. Bu sayıların bulunması sırasında kalbur problemi çözümü uygulanabilir.

    Sınavınızda başarılar

  3. Süha

    Hocam, ben bu hesaplamanın dayandığı temel mantığı kavrayamadım. Örneğin, Legrende sembolünü niçin buluyoruz? Neden bir asal sayılar kümesi oluşturuyoruz? Neden bir matris var? Neden ters çevriliyor..ilh. Cevabınızdan memnuniyet duyacağım.

  4. Süha

    Hocam, cevabınız için teşekkür ederim. Bağlantılardaki yazıları okudum, ama benim sormak istediğim husus, yani “temel mantık” dan kastım “yöntemin mantığı” idi, yani şöyle bir şeydi:
    Mesela malumunuz, çarpanlara ayırmada kullanılan yöntemlerden biri de bölme yöntemi. Sayı teorisine göre bütün bileşik sayılar asal sayıların çarpımlarından oluşmuşlardır. Dolayısıyla N gibi bir bileşik sayı kendisinden küçük bir asala bölünebilir. Bir bileşik sayının en küçük çarpanı sayının karekökünden küçüktür (tamkare sayılar hariç). Çarpanlar asal ve asalların da hepsi teksayı olduğu için (2 hariç), karekökten geriye doğru teksayıların N sayısını kalansız bölüp bölmediğini kontrol ederiz, kalan 0 olduğu noktada küçük çarpan bulunmuş olur. Mantık budur.

    Başka bir örnek, fermat yöntemi. Fransız matematikçi Fermat ispat etmiştir ki, bütün teksayılar iki kare farkı şeklinde yazılabilir. N=xkare-ykare eşitliği geçerlidir. Bu ifade cebirsel olarak N=(x+y)*(x-y) şeklinde de yazılabilir. Bir tercih olarak, bu formülden ykare=xkare-N yazılabilir (isterseniz xkare=ykare+N formülünü seçebilirsiniz). ykare değerinin negatif olmaması için En küçük xkare değeri N sayısından büyük olmalıdır, bunun için N sayısının karekökünün 1 fazlası hesaplanarak işe başlanır. Elde edilen değerin tam kare olup olmadığına bakılır (karekökü alınır), değilse tam kare olan ykare değeri bulunana kadar x değeri arttırılarak işlem devam eder. Tam kare değeri bulunduğunda, (x+y) ve (x-y) değerleri hesaplanarak işlem tamamlanır. Mantık budur.

    Ben mantık derken böyle bir şeyi kastetmiştim. Değerli vaktinizi aldıysam özür dilerim.

  5. Şadi Evren ŞEKER Article Author

    Anladım, aslında cevabını linkini verdiğim yazılarda açıkladığımı sanıyordum ama sanırım açıkça yazmamışım. Şu şekilde anlatmaya çalışayım. Kalbur yöntemi çarpanların çarpanlarını da elemeye dayalıdır.

    Basitçe sizin bölme işleminizi ele alalım. Diyelim ki çarpanlarını aradığımız sayı 71 olsun (Aslında bir asal sayı). Ancak karekökünden eşit ve küçük sayılara bakacağız. kök(71) = 8 olduğuna göre 8’den başlayarak geriye doğru bütün ihtimalleri denememiz gerekiyor değil mi?

    Daha iyi anlaşılsın diye açıkça yazıyorum:
    2,3,4,5,6,7,8 sayılarına sırasıyla bölüp tam bölen var mı diye bakacağız.

    Şimdi kalbur yöntemi diyor ki, 2’ye böl. Diyelim ki bölünmedi o zaman 2’nin katlarını ele, yani artık bölmek için kontrol edeceğin sayılar aşağıdaki gibi olmalı:
    3,5,7

    Burada 4,6 ve 8 ile bölmek için denememize artık gerek kalmadı diyebiliriz çünkü 6’ya veya 8’e bölünen herşey aslında 2’ye bölünür.

    Kalbur yöntemini herhangi bir problemde kullanabilirsiniz amaç ihtimalleri azaltmaktır.

    Daha akılda kalıcı olamsı açısından, aslında elimizde n adet ihtimal varken bir ihtimali elediğimizde (n-1 ihtimal kaldığında) şayet bağlantıları kullanarak başka ihtimalleri de eleyebiliyorsak aslında kalbur yöntemini kullanıyoruz diyebiliriz.

    Çok genel ve detaya girmeden açıklamaya çalıştım ama sanırım bunu soruyordunuz, yine de merak ettiğiniz veya anlaşılmayan birşeyler varsa lütfen cevap yazınız.

    Başarılar

  6. Süha

    Hocam, biliyorum, sizi uğraştırıyorum ama, zamanınız varsa benim gibi matematik cahili birisine “matris sonucunu sıfır yapan vektörün” nasıl bulunabileceğini açıklayabilir misiniz? Şimdiden teşekkür ederim.

  7. Şadi Evren ŞEKER Article Author

    Sorunuzu tam olarak anlayamadım, sormak istediğiniz bir matrisin tersi ise (yani ikinci bir matris), aşağıdaki yazı işinize yarayabilir:

    http://www.bilgisayarkavramlari.com/2008/11/19/matrisin-tersinin-alinmasi-mantrix-inverse/

    Sormak istediğiniz bir matrisin çekirdeği (kernel, null space) ise bununla ilgili bir yazı yok sitede henüz yazar eklerim. Ya da farklı birşeyi kastediyorsanız lütfen belirtin bilebildiğim kadarıyla cevaplamaya çalışayım.

    Başarılar

  8. Süha

    Hocam, matrisin “transpose” sini anladım. Benim anlamadığım husus, “ikinci dereceden kalbur” yazınızda geçen “sonucu 0 yapan vektörü arıyoruz ” cümlesidir. Matrisler konusunda bilgim az olduğu için, matrisin sonucu ve bu sonucun 0 yapılması deyimlerini anlayamadım. İnternette araştırdım, bir matris ile bir vektörün nasıl çarpılacağı gibi konular var ama “matrisin sonucunu 0 yapan vektör” konusuna rastlamadım. Bana göre, bir vektörün tüm elemanlarının sıfır olması çarpım sonucunun sıfır olması için yeterliydi. Neden başka bir vektör arıyoruz ve bu vektörü nasıl buluyoruz?

    Daha sonra “Bu sonuca ulaşan birden fazla vektör bulunabilmektedir. Bunlardan bir tanesi aşağıda verilmiştir: V= ( 1,1,1,0,1,0 )” diyorsunuz. İşte ben bu vektörü nasıl bulduğunuzu da öğrenmek istiyorum. Ayrıca, vektörün ilk elemanı ile matrisin ilk elemanı çarpılınca 1 çıktığı için çarpım sonucunun sıfır olmayacağını, en azından vektörün ilk elemanının 0 olması gerektiğini düşünüyorum. Nerede yanlış yapıyorum?

    Yukarıda arzettiğim konularda cehaletimi giderirseniz memnun olacağım.

  9. Şadi Evren ŞEKER Article Author

    EstagfurUllah, lütfen böyle “cahillik” gibi kelimeler kullanmayın. Bana göre sadece bilmeyen bilmediğini de bilmeyene cahil denir ki öyle birisine hiç benzemiyorsunuz.

    Sorunuzun cevabı şu, bakın iki matrisin çarpımı

    2 2 2 2 2 0 2

    sonucunu verir (bunu çarparak deneyebilirsiniz veya isterseniz internette hazır bu işi yapan appletler var)

    Bu vektör elbette 0 değil ancak unutmamamız gereken nokta ikilik tabanda (binary) çalışıyor olduğumuz. dolayısıyla bu sayıları 2’lik tabanda yazarsak (2’lik tabanda 2’nin 0 olduğunu hatırlayınız)

    0 0 0 0 0 0 0

    vektörünü elde ederiz ki buna da kısaca 0 denilebilir.

    Başarılar

  10. Şadi Evren ŞEKER Article Author

    Bu arada nasıl bulunduğunu da sormuşsunuz onu cevaplamamışım, cevabı matrix kernel veya null space hesaplama ile yapılıyor. Basitçe anlatacak olursak bir matristeki her satır bir denklem olarak düşünülebilir. Kaç kolon varsa o kadar bilinmeyen ve kaç satır varsa o kadar denklem vardır elimizde. Yukarıdaki örnekte 6 bilinmeyenli 7 denklem vardır. Bu denklemlerin tamamını 0’a eşitleyip çözmek olarak düşünebilirsiniz. Dediğim gibi bunu yazarak açıklamam daha uygun olacak sanırım ama şu andaki yoğunluğumdan dolayı bu konuyu yazılacaklar listesine ekleyip daha sonra uygun bir zamanda yazacağım.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

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