rsa
-
https://github.com/…/master/algorithms/maths/rsa.py
adresinde de matematigini anlayabileceginiz basit yazilmis bir anahtar ureteci ornegi var. -
ev hanımlarının da anlayabileceği dilden, 7 aşamada algoritmanın adım adım nasıl çalıştığını anlatmayı deneyeceğim.
1) p ve q olmak üzere 2 tane büyük asal sayı belirleyin.
2) n = p x q denkliğinden yararlanarak n değerini bulun.
3) daha sonra phi(n) = (p-1) x (q-1) denkliğini kullanarak, phi(n) değerini bulun.
4) ardından bir 3 ile 65537 değerleri arasında rastgele bir "e" sayısı yani "public exponent value" belirleyin. tercihen çok küçük ya da çok büyük olmamalı.
5) en son tüm bu oluşturduğunuz değerleri kullanarak, "d" sayısı yani "private exponent value" bulmanız gerekiyor. bunun formülü ise
e mod(phi(n)) denkliğinin çarpımsal tersidir(multiplicative inverse).
yani aslında denklik budur:
e * d = 1 mod (p - 1)(q - 1)
d yi bulmaniz gerekir.
6) bir "m" mesajını şifrelemek için
m^e mod (n) = c
bu denkliği kullanırız.
7) şifrelenmiş halde bulunan bir "c" mesajını deşifreleyebilmeniz için
c^d mod (n) = m
bu denkliği kullanırız.
------------------------------------------------------------
en baştan itibaren ney neydi diye özet geçersek:
- public key : e ve n den oluşur, sahibine mesaj göndermek istediğinizde kullandığınız, herkesin görebileceği açık anahtardır.
- private key : d ve n den oluşur, sahibinden başka kimsenin bilmediği kapalı anahtardır.
- private değer nedir = sadece sahibinin bildiği, husisi değerlerdir.
- public değer nedir = sahibiyle iletişim kurarken, herkesin erişebildiği herkese açık değerlerdir.
- p ve q = ikisi de birer asal sayıdır. private değerdir.
- n = p ve q çarpımından oluşan, modülo olarak kullanılan n değeridir. bir public bi değerdir.
- e = üs değeridir, kullanıcının belirlediği public bir değerdir.
- phi(n) = (p - 1)(q - 1), p ve q değerlerinin bir eksiklerinin çarpımından oluşan değerdir. private değerdir.
- d = bir exponent değerdir. belirlenen e ve phi(n) değerlerinin inverse halidir. private değerdir.
- m = plaintextir, açık mesajdır, şifrelenmek(encrypt) istenen mesajın değeridir. bunu (ascii to hex, ascii to decimal gibi value olabilir)
- c = ciphertexttir, şifrelenmiş mesajdır. deşifrelenmek (decrypt) istenen mesajdır.
-------------------------------------------------------------
basit bi örnekle pekiştirelim soru:
c = 5859
n = 11413
e = 7467
m = ?
cevap:
denkligi bi hatirlayalim
şifrelemek için(to encrypt): m^e mod n = c
deşifrelemek için(to decrypt): c^d mod n = m
bu soruyu çözebilmemiz için:
1) p ve q bulmamiz gerekiyor
2) phi(n) bulmamız gerekiyor
3) d yi yani private exponenti bulmamiz gerek.
4) d yi kullanarak mesajı bulabiliriz.
tabi ki sayılarımız küçük değerler olduğu için bu işlemleri kolayca hesaplayabiliriz.
(kesinlikle gercek hayat sorusu degildir, algoritma nasil calisir onu gostermek icin hazirlanmistir. tabi ki pek cok ayrıntısı mevcuttur araştırabilirsiniz)
1) n = p * q sayı küçük olduğu için çarpanlarına ayırabiliriz.
11413 = 101 * 113
p = 101 , q = 113
2) phi(n) = (p-1) * (q-1)
11200 = 100 * 112
phi(n) = 11200
3) bu aşama en çok kafa karıştıran yerlerden birisi, modular multiplicative ınverse hesaplamanız gerek yani
e * d = 1 mod phi(n)
e * d = 1 mod (p - 1)(q - 1)
7467 * d = 1 mod (101 - 1)(113 - 1)
bu ifadeden d yi hesaplayabilmeniz gerek.
online bir tool bulabilirsiniz, herhangi bir programlama dili kullanabilirsiniz, gerçi elinizle de kolayca hesaplayabilirsiniz.
bu denklikten d = 3 geliyor.
4) artık mesajı deşifrelemek(decrypt) için elimizde private key(d,n) mevcut.
c^d mod n = m
5859^3 mod 11413 = m
cevap: m = 1415
-------------------------------------------------------------
basit kafadan yapılabilecek başka bir örnek soru:
ciphertext(şifrelenmiş hali) = 75
n = 437
e = 3
ve ben mesajımın(plaintext) 8 ya da 9 olduğunu biliyorum desem. p ve q değerini öğrenmeden hangisi olduğunu nasıl bulursunuz ?
cevap: denklikte yerine koyalım, 6. aşamayı hatırlayın
m^e mod (n)
m = 8 olduğunu var sayalım ve deneyelim
8^3 mod 437 = 75 ?
512 mod 437 = 75 evet sağladı cevap m = 8 diyebiliriz.
-------------------------------------------------------------
bu kripto sistemdeki günümüzde güvenilen nokta, aslında "p ve q" değerlerinin devasa büyüklüklerdeki asal sayılar olarak belirlendiğinde n sayisinin çarpanlarına ayırma işlemini günlük bilgisayarlarımızın hesaplamayamamasından kaynaklanır. "p ve q" sayısı özenle hazırlanmış ve leak edilmemiş sayılar olduğu sürece "private key"i elde etmemiz yıllar, yüz yıllar alır.(tabi iyimser bi halle)
zira kuantum bilgisayarlarin bütün bu kripto sistemi alt üst ettiği,
(bkz: ameriga keyleri çatır çatır kırıyor),
(bkz: nsa kıramadığı sistemi kullandırtmaz)
gibi teorilerin savunulduğu gerçeği de mevcut.
kim ne derse desin arkasındaki matematik çok eğlencelidir. ama yakın bir gelecekte kullanılmayacak olan algoritma olacağı neredeyse kesin gözüyle bakılıyor. buna karşılık olarak simetrik algoritmaların yeni nesil versiyonlarini kullanmaya geri döneceğiz büyük ihtimalle. merakla bekliyoruz.
dipnot: sorularınız olursa sormaktan çekinmeyin ya da gözden kaçırdığım bişey olduysa uyarabilirsiniz. -
daha çok bmw ve vag grubu araçlar üzerine çalışan, güzel projeleri olan firma.
-
aynı isimde, sonraları dell tarafından alınan güvenlik şirketi.
-
-
daha iyi algoritmaların olmasına rağmen , pazarlama tekniği sayesinde tutulmuştur.
pazarlama,reklam ve en önemlisi yahudiliğin ne kadar önemli olduğunu gözler önüne sermiştir. -
claus p. schnorr'un yayımladığı makale neticesinde güvenilirliğini yitirmiş, asimetrik şifreleme algoritması.
-
öncelikle, rsa ve ataklar hakkında makaleler:
link
link
link
algoritmayı açıklamak gerekirse şöyledir:
1- daha güvenli olması için birbirine yakın ve büyük rastgele iki p ve q asal sayısı seçilir.
-> p=2 ve q=7 olsun
***gösterim kolaylığı açısından burada küçük asal sayılar seçilmiştir. güvenliği arttırmak için çok daha büyük asal sayılar seçilmelidir.
(p=6337 ve q=6389 gibi)
2- n=p*q (n değeri sonraki adımlarda mod alma için kullanılacak)
-> n= 2*7=14
3- sayıların totient fonksiyonu alınır. t(n)=(p-1)*(q-1)
-> t(n)=(2-1)*(7-1)=6
4- 1<e<t(n) aralığında bir public key (e) seçilir.
***buradaki üretilen e değeri t(n) ile aralarında asal (coprime) olmalı.
int e = 0;
for (e = 5; e <= 2000; e++) {
if (gcd(totient, e) == 1)
break;
}
-> e=5
böylece lock -> (e,n)=(5, 14) olur.
5- private key (d) seçilir.
d*e= 1 mod t(n) olmalı.
int d = 0;
for (d = e + 1; d <= 2000; d++) {
if (((d * e) % totient) == 1)
break;
}
-> 5*d (mod 6)=1
d'yi 5,11... vs. gibi sayılardan seçebiliriz.
d=11 olsun.
key -> (d, n) = (11, 14) olacaktır.
***encrpytion***
(5,14)
c = m ^ e mod (n)
-> m' de girilen harfin ascii karşılığı alınır.
m'yi 2 olarak alırsak;
c = 2 ^ 5 (mod 14) = 32 (mod 14) = 4 (mod 14)
***decryption***
(11,14)
m = c^d mod(n)
4^11(mod 14) = m (mod 14)
ve böylece, m=2 şeklinde deşifre işlemi yapılır. -
rsa mantığı, bir tam sayının çarpanlarına ayrılmasının onu yeni sayılarla çarpmaktan daha zor olduğu gerçeğine dayanmaktadır. yeterince büyük ve birbirinden farklı olan iki asal sayının çarpımından oluşan bir base değer elde edilir. ve diğer anahtar parametreleri de aynı iki asal sayıdan türetilir. bu nedenle base değer çarpanlara ayrılabilirse, özel anahtar tehlikeye atılır. bu nedenle anahtar boyutunu iki veya üçe katlarsak, şifreleme gücü katlanarak artar.
çalışması ise şu şekilde olur,
iki adet asal sayı seçilir. bu sayıların büyük olması güvenlik açısından önemlidir. bu iki sayıya p ve q diyelim.
anahtarlar için base değerinin hesaplanması gerekmektedir. base değerine n dersek;
n = p*q şeklinde bu değer hesaplanabilir.
n değeri için totient fonksiyonu hesaplanır. her iki çarpanda asal olduğu için n değerinin totient fonksiyonu ;
a(n) = (p-1)(q-1) olarak bulunur.
public key değerimize e dersek, e’yi bulmak için 1< e <a(n) aralığından bir asal sayı seçilmelidir. e değerimiz artık bizim public key değerimizdir.
private key değerimize d dersek,
d*e = 1 mod (n) olarak d değeri hesaplanır.
kaynak:
https://medium.com/…edir-nasıl-çalışır-bc351e63364c -
the royal society for the encouragement of arts, manufactures and commerce.
(bkz: royal society of arts)
ekşi sözlük kullanıcılarıyla mesajlaşmak ve yazdıkları entry'leri
takip etmek için giriş yapmalısın.
hesabın var mı? giriş yap