İkinci dereceden kalbur (quadratic sieve)

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ı […]

Devam

Oransal Elek (Kesirli Kalbur, Rational Sieve)

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 […]

Devam

Kalbur Problemi (Sieving Problem, Elek Problemi)

Yazan : Şadi Evren ŞEKER Özellikle sayılar teorisinde (number theory) önemli bir yer tutan, kafes çözümlemelerde (lattice based solutions) birisidir. Bilgisayar bilimlerinde, özellikle veri güvenliği konusunda, şifreleme algoritmalarına saldırı için kullanılmaktadır. Problem basitçe belirli bir üst sınıra kadar olan asal sayıları bulmayı hedefler (örneğin 30’a kadar olan asal sayıları bulmak istiyor olalım). Bu problemin çözümü […]

Devam

İkinci dereceden tortu (quadratic residue)

Yazan : Şadi Evren ŞEKER Sayılar teorisinde (number theory), herhangi bir tam sayının karesi (örneğin x diyelim), verilen bir modüloda (örneğin n diyelim), bir mükemmel sayıya (perfect number) denk ise (örneğin q diyelim), bu x sayısına modulo n’de ikinci dereceden tortu (veya rezidü ) ismi verilir. x2 ≡ q (mod n) Kalan değerin mükemmel sayı […]

Devam

Pohlig Hellman Algoritması

Yazan : Şadi Evren ŞEKER Steven Pohlig ve Marin Hellman tarafından geliştirilen, ayrık logaritma probleminin (discrete logarithm) çözümü için bir alternatif sunan algoritmadır. Algoritma basitçe aşağıdaki denklemde bulunan x değerine bir çözüm arar: e ≡ gx (mod p) Bu durum tam olarak da ayrık logaritmanın tanımıdır ve yukarıdaki denklem, aşağıdaki hale dönüştürülebilir: x ≡ logg […]

Devam

Üçgen sayıları (triangular numbers)

Yazan : Şadi Evren ŞEKER Bir üçgen teşkil eden noktaların sayılarından oluşan seridir. Üçgensel sayılar olarak da isimlendirilir. Aşağıdaki şekilde örnek olarak üçgenler verilmiştir: Yukarıdaki örnek şekillerde görüldüğü üzere, eş kenar üçgen elde edilebilen nokta sayıları verilmiştir. Yukarıdaki sayı serisi aşağıdaki şekilde yazılabilir: 1,3,6,10 … Bu serideki her sayı, serinin kaçıncı elemanı ise, o elemanlık […]

Devam

Merkezi poligon sayıları (Centeral Polygon Numbers)

Yazan : Şadi Evren ŞEKER Bir dairenin verilen doğru sayısıyla kaç farklı parçaya bölünebileceğini veren sayı serisidir. 1, 2, 4, 7, 11 şeklindeki sayılara, merkezi poligon sayıları ismi verilir. Bu sayılar, verilen doğru sayısına göre, bir daireyi kaç farklı şekle böldüğünü gösterir. Örneğin yukarıdaki sayı serisini eksi olmayan tam sayılar ile birebir eşleştirirsek 0 1 […]

Devam

Floyd Üçgeni (Floyd’s Triangle)

Yazan : Şadi Evren ŞEKER Robert Floyd tarafından tasarlanan bir sayı üçgenidir. Üçgen, her satırda, o satır kadar elemandan oluşan ve ardışık sayma sayılarının satırlara dağıtılması ile şekillenen, sağa yaslı bir dik üçgen olarak tanımlanabilir: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Yukarıdaki şekilde üçgenin ilk 5 […]

Devam

Shank Algoritması

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle veri güvenliği konusunda kullanılan ayrık logaritma probleminin (discrete logarithm) çözümü için geliştirilmiş algoritmalardan birisidir. Literatürde algoritmayı bulan kişi olan Daniel Shank’a ithafen Shank’s algorithm olarak geçer. Algoritma basitçe, denklemine çözüm arar. Bu denklemde p bir asal sayı olmak üzere, denklemin çözümünün en azından pozitif tam sayı çözümlerini […]

Devam

Bebek ve Dev Adımı (baby step giant step)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde özellikle şifreleme sistemlerinde kullanılan ve ayrık matematik altında incelenen ayrık logaritma (discrete logarithm) problemini çözmek için geliştirilen bir yöntemdir. İsmi basitçe büyük ve küçük adımlardan esinlenerek konulmuştur. Ayrık logaritma alınırken, en klasik ve etkili yöntem bütün üslerin denenmesidir. Örneğin bir radyoda kanal ararken, önce hızlı çevirerek arama yapılır […]

Devam