AnalizGenel

RSA ASALLARI ÜZERİNE ANALİZ

Bu analizde , RSA asimetrik şifreleme yönteminde kullanılan N=p.q (p ve q asal sayılar) sayısını oluşturan asalları bulmak. Bu sayıları bulurken geçen süreyi incelemek.

İncelenecek örnek N değerleri ve Asal Sayılar:

N=116720482813980117819756292001478720794548981072626168055657

p= 48112959837082048697

q=2425967623052370772757633156976982469681

N=189620700613125325959116839007395234454467716598457179234021

p=671998030559713968361666935769

q=282174488599599500573849980909

N=706113762068412435747683199935230839398684490635512212296530712933315635896349355029272628861810919

p=22953686867719691230002707821868552601124472329079 q=30762542250301270692051460539586166927291732754961

N=3466376984661165777669671161883339457593705965604490867666627969231285053691607253508981564548308471

p=5570373270183181665098052481109678989411

q=622288097498926496141095869268883999563096063592498055290461

N=1320333474059737985041119302651298538904187342804899133125136778545013153665237601904424104644940211951708286103379790019194167102616032787860299429721616738361

p=4669523849932130508876392554713407521319117239637943224980015676156491

q=282755483533707287054752184321121345766861480697448703443857012153264407439766013042402571

N=1291074959783370401081689254425643224321733371878113128778271297105566754948001732331617463592122539890008613666279352530001653410237203411297656581153462915497

p=622288097498926496141095869268883999563096063592498055290461

q=2074722246773485207821695222107608587480996474721117292752992589912196684750549658310084416732550077

C++ dili ile yazdığımız programı kullanarak C++ programlama dilinin müsaade ettiği en büyük tamsayı değerleri için programın çalışma süresini değişik değerler için inceledik. Bu inceleme yapılırken kullanılan sistem Intel i5 2.50 GHz 64 Bit 4 mantıksal çekirdekli işlemci ve  4GB Ram donanımlı bir bilgisayar.

Hazırladığımız programın  kaba kodu:

 for i=2  den kök(N)

if n mod i = 0 küçük asal bulundu

büyükasal=N/küçükasal

yazdır N = büyükasal*küçükasal

Programın çalışma prensibi : N sayısının ,2 den başlayarak N sayısının kareköküne kadar olan tüm sayılara bölünebilmesi durumunu kontrol eder. Bu sayede  küçük  asal çarpanı bulup, N sayısını çarpanlarına ayırır.

Aşağıda 13 ile 19 basamak aralıklarında  4 farklı N sayısının çarpanlara ayrılması incelenmiştir.

Denemelerde elde ettiğimiz sonuçlar şu sorunları ortaya koydu :

Sorun 1 : Zaman sorunu : Bize verilen sayılardan en küçüğü 60 basamaklı bir sayıdır . Bu sayıya ait  küçük asal 20 Basamaklı bir sayı

20 Basamaklı küçük asalı olan bir sayıyı mevcut programla çözümlemeye çalışırsak , son denediğimiz sayıya göre :

katı büyüklükte bir asal sayıya sahip

17,44*1010 Saniye = 5530 yıl gerekli !!!!

Çözüm Önerileri : 

  1. Öneri : Paralel programla yöntemi ile tüm işlemli çekirdeklerini devreye sokmak : Bu durumda çekirdek sayısına bağlı olarak süre 2,4,8,16 gibi bir oranda azaltılabilir.

2. Öneri: Tüm sayılara bölünmeyi kontrol etmek yerine sadece asallara bölünmeyi kontrol etmek : İlk 50 milyon asalın ilk 109 sayı arasında olduğunu biliyoruz yani kontrol edeceğimiz sayılar 1/20 oranına düşecek. Bu oranın geçerliliğini kontrol etmek için 1010 dan küçük kaç asal olduğunu buldurduk . 

455milyon adet olduğu sonucuna vardık (Program Çalışma süresi : 74330 Saniye =20 saat  ) . Oranda küçük bir değişim oldu . Yeni oran 1/22 . Sayı büyüdükçe asal sayıların seyrekleşmesini beklesek de yeterince seyrekleşmeyecek .

Sorun 2 : Data Tipi Sorunu  : C++ programı  ile kullanılabilecek en büyük tam sayı (9.223.372.036.854.775.807 )

19 basamaklı bir sayı bu da küçük asalı en çok 9 basamaklı bir sayı ile çalışmamızı sağlıyor ..

1.Öneri : C# programlama dilinde BigInteger data tipi ile çalışmak: Yaptığımız çalışmada BigInteger data tipinin C++ da kullanılan integer data tipine göre 3-4 kat daha yavaş işlem hızı olduğunu gördük.

Sorun 3 : Hafıza Sorunu :  Zaman sorunu azaltmak için kullanacağımız asal sayıların depolanması büyük bir bellek sorunu teşkil ediyor

109 dan küçük asal sayılar 50

Milyon adet .TXT dosya içinde tuttuğu yer 496MB

1010 dan küçük asal sayılar 455 Milyon adet .TXT dosya içinde tuttuğu yer 5 GB

1019 dan küçük asal sayılar 400.109 Milyon adet .TXT dosya içinde tuttuğu yer 5 Milyon TB (tahmini)

1. Öneri : Asal sayıları kullanarak zamanı azaltsak da imkansız hafıza gerektiriyor. Bu durumda asal sayıları kullanmamak                                               daha  iyi bir  çözüm olabilir .

Sorun 4 : Yeniden Zaman Sorunu :  Asal sayıları bulmak yine zaman sorunu oluşturuyor. Sadece 1010 dan küçük asal sayıları bulmak (üstelik hiçbir yere yazdırmadan sadece vector içinde tutarak) 20 saat sürdü . 60 basamaklı bir sayı için 30 basamaklı ve daha küçük asal sayılara ihtiyaç vardır. Bunları bulmak sayıyı çarpanlara ayırmak için gerekli süreden bile fazla olacaktır. Sadece 1  adet 19 basamaklı asal sayının , asal olduğunu kontrol etmek bile yaklaşık 55 saniye sürmüştür.

  1. Öneri : Asal sayıların kullanılmaması : Asal sayıları kullanmak zamanı 20-25 kata kadar hızlandıracak olsa da onları üretmek mevcut zaman sorunundan daha büyük .
  2. Öneri : Hazır bir data seti bulmak : Böyle bir data seti hafıza sorunu teşkil edecektir bir yerden temin edilerek taşınması mevcut şartlarda imkansızdır.

Sonuç : Mevcut teknolojik altyapıyla RSA da kullanılan N sayılarının küçük asalı 15 basamak ve üstünde bile olsa sıradan bir şifre kırma eylemine karşı oldukça güçlü olacaktır. Eğer bu asal sayı 20 basamak ve üstünde olduğu takdirde bile donanımlı bir şifre kırma eylemine karşı güçlü olacaktır.  Basamak sayıları arttırıldıkça güvenlik seviyesi de üstel olarak artacaktır.

Analizde kullandığımız  sistem mevcut teknolojiye göre sıradan bir PC dir.  Eğer elinizde 93 petaflop performanslı  bir süper bilgisayar  yoksa 60 basamaklı bir RSA sayısını çarpanlara ayırmaya çalışmak için yeterli gücünüz yok demektir.

Eğer elinizde 100 basamaklı bir RSA değeri varsa mevcut süper bilgisayarlar bile yeterince kısa bir zamanda sizin mesajlarınızı deşifre edemeyecektir.

Müstecep ŞAHİN

Emrullah DURUMLU

Yorum Ekle