Yazan : Şadi Evren ŞEKER Bir sayının asal çarpanlarına ayrılması için kullanılan yöntemlerden birsidir. Yöntemin ismi kalbur probleminden (sieving problem) gelmektedir. Sayı alan kalburu (NFS), yapı olarak bir Ferma’nın çarpanlara ayırma sistemine dayanan (Fermat’s Factorization) bir denklik elde etmek ister. Buna göre amacımız a2 = b2 mod n şeklinde bir denklik yakalamaktır. Bu denklik elde […]
Category: Veri Güvenliği(Cryptography)
AKS Asallık Testi (AKS Primality Test)
Yazan : Şadi Evren ŞEKER Verilen bir sayının asal sayı olup olmadığının bulunması, bilgisayar bilimlerinde, özellikle veri güvenliği (kriptoloji) konusunda oldukça önemlidir. AKS asallık testinin ismi, yöntemi geliştiren üç kişinin isimlerinden türetilmiştir. ( Agrawal, Kayal, Saxena) Yöntemin dayandığı matematiksel yapı aşağıdaki denklemdir : (x – a)n ≡ (xn – a) mod n Aslında bu denklem, […]
Atkin Kalburu (Sieve of Atkin)
Yazan : Şadi Evren ŞEKER Belirli bir aralıkta verilen bütün asal sayıları bulmaya yarayan algoritmadır. Bu algoritmada bir kalbur problemi olarak görülebilir ve daha önceden problemle uğraşmış olan Eratosten tarafından geliştirilen çözümün gelişmiş halidir. Algoritmanın ismi, 2004 yılında bu yöntemi geliştiren kişiden gelmektedir. Algoritma adımları aşağıda açıklanmıştır: Öncelikle bütün sayılar mod 60 ta çalışır. Yani […]
Eliptik Eğri ile Çarpanlara Ayırma (Elliptic Curve Factorization)
Yazan : Şadi Evren ŞEKER Bu yazının amacı bilgisayar bilimlerinde özellikle veri güvenliği ve şifreleme konularında (kriptoloji) oldukça önemli bir yeri olan çarpanlara ayırma işleminin hızlı bir şekilde gerçekleşmesi için kullanılan eliptik eğri ile çarpanlara ayırma metodunu açıklamaktır. Literatürde Elliptic Curve Factorization Method olarak geçen ve bazan ECM olarak kısaltılan yöntem, aşağıdaki adımlardan oluşmaktadır. Öncelikle […]
Pollard RHO Çarpanlara Ayırma Yötemi
Yazan : Şadi Evren ŞEKER Pollard’s rho çarpanlara ayırma metodu (factorization), büyük asal sayıların hızlı bir şekilde çarpanlara ayırılmasını amaçlamaktadır. Veri güvenliği (kriptoloji) açısından oldukça önemli olan bu yöntemin çalışması aşağıdaki adımlardan oluşur: Çarpanlarına ayrılmak istenen sayının n olduğunu kabul edelim. Bulacağımız çarpan d olarak isimlendirilecektir ve d sayısı d | n şartını sağlayacaktır (tam […]
İ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ı […]
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 […]
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ü […]
Veri Güvenliği 2 dersi vize çözümleri
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 […]
Zaman Etiketlemeli Yetkilendirme (Timestamp based authentication)
Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinin bir alt alanı olarak değerlendirilebilecek olan şifreleme (kriptoloji) konusunda kullanılan yetkilendirme (authentication) algoritmalarından birisidir. Özellikle günümüzde gelişmekte olan akıllı kart (smart card) kullanımıyla birlikte, bu algoritmaya duyulan gereksinim artmış ve sıkça kullanılır olmuştur. Algoritma 3 aşamadan oluşur: Kayıt aşaması (registration phase) Giriş aşaması (login phase) Onay Aşaması (verification […]