İçeriğe atla

Sözde rassal sayı üreteci

Sözde rassal (rastgele) sayı üreteci (pseudorandom number generator, PRNG, sözde rastgele), öğeleri arasında kolay kolay ilişki kurulamayacak bir sayı dizisi üreten algoritma türlerine verilen genel isimdir.

Sözde rassal sayı üreteçlerinin çıktıları gerçek anlamda rassal değildir, bu tür algoritmalar gerçek rassal sayı dizilerinin bazı özelliklerini yaklaşık olarak taşır. John von Neumann'ın da belirttiği gibi "Aritmetik yöntemlerle rassal sayılar üretmeye çalışan biri büyük günah işliyordur.[1]" Her ne kadar rassal sayılar donanımsal rassal sayı üreteçleri ile üretiliyor olsa da, sözde rassal sayılar modern bilgiişlemin önemli bir bölümünü kapsamaktadır ve bunlar kriptolojiden tutun fiziksel sistemleri simüle etmeye yarayan Monte Carlo yöntemlerine dek pek çok yerde kullanılmaktadır. Oak Ridge National Laboratory'den Robert R. Coveyou'nun "rassal sayıların üretimi rastgele gerçekleştirilemeyecek kadar önemlidir[2]" cümlesinde belirttiği gibi üretilmiş olan sayıların rassallığı ciddi ve dikkatli bir matematik analiz gerektirmektedir.

Bu kategorideki pek çok algoritma, tekbiçimli dağılımdan bir örnek oluşturmaya çalışırlar. Bu iş için en sık kullanılan algoritma türleri doğrusal denklik üreteçleri, gecikmeli Fibonacci üreteçleri, doğrusal geribeslemeli kaydırma yazmaçları ve genelleştirilmiş geribeslemeli kaydırma yazmaçlarıdır. Yeni geliştirilmiş algoritmalar arasında ise Blum Blum Shub, Fortuna ve Mersenne Twister vardır.

Özü itibarıyla rassal olmama

Sözde rassal sayı üreteçleri deterministik bir bilgisayarda çalıştıkları için (kuantum bilgisayarı ile karşılaştırın) deterministik algoritmalardır ve bu tür bir algoritma ile üretilen sayı dizisinin gerçek bir rassal dizide olmayan bir özelliği olacaktır: periyodiklik. Şurası kesindir ki, eğer üreteç sabit miktarda hafıza kullanıyorsa yeterli sayıda döngü adımından sonra aynı içsel duruma ikinci kez gelecektir ve ondan sonra da sonsuza dek tekrar edecektir. Periyodik olmayan bir üreteç tasarlanabilir ancak bu tür bir sistemin ihtiyaç duyduğu hafıza miktarı sistem çalıştıkça büyüyecektir. Buna ek olarak bir sözde rassal sayı üreteci keyfi bir başlama noktasından ya da çekirdek durumundan, başlatılabilir ve o andan itibaren özdeş bir sayı dizisi üretir. Periyodikliğin pratik önemi sınırlıdır. Eklenen her bir hafıza biti ile maksimum periyot iki katına çıkar. Herhangi bir bilgisayarın evrenin beklenen yaşam süresi boyunca hesaplayamayacağı kadar uzun periyoda sahip sözde rassal sayı üreteçleri inşa etmek mümkündür. Şifrebilimdeki cevaplanmamış sorulardan biri de iyi tasarlanmış bir sözde rassal sayı üretecinin çıktısını, çekirdeğini (başlangıç paramterlerini) bilmeden, gerçek rassal gürültüden ayırt etmenin mümkün olup olmayacağıdır. Şifrebilimdeki pek çok uygulama uygun bir sözde rassal sayı üretecinin çıktısının gürültüden ayırt edilmeyeceği varsayımına dayanır. En basit örneği dizi şifresidir. Bu algoritma gizli bir mesajı, rassal sayı üretecinin çıktısı ile xor işlemine tabi tutar. Bu tür rassal sayı üreteçlerinin tasarımı bir hayli zordur ve çoğu program çok daha basit üreteçler kullanır.

Uygulamada, pek çok sözde rassal sayı üreteci istatistiksel olarak önemli testleri geçmelerini engelleyen bazı durumlar sergiler. Bunlardan sadece birkaçını söylemek gerekirse:

  • Bazı çekirdek (başlangıç) durumları için beklenenden daha kısa periyodlar
  • Kötü boyutsal dağılım
  • Birbirini takip eden değerlerin bağımsız olmaması
  • Bazı bitlerin diğerlerinden 'daha rassal' olabilmesi
  • Tekbiçimlilik eksikliği

Hatalı sözde rassal sayı üreteçlerinin problemleri kolay kolay tespit edilemeyecek türde olabileceği gibi saçma denecek kadar açık da olabilir. ana çatı bilgisayarlarında yıllarca kullanılmış RANDU isimli algoritma bu türden problemli bir algoritmadır ve o dönemdeki pek çok çalışma da güvenilir olmaktan uzaktır.

Mersenne twister

Makoto Matsumoto ve Takuji Nishimura tarafından 1997 yılında geliştirilen Mersenne twister algoritması yukarıda bahsedilen pek çok problemden uzak güçlü bir sözde rassal sayı üretecidir. Bu üretecin periyodu 219937-1'dir ve 32 bitlik değerler için 623 boyutta eşdağılımlı olduğu ispatlanmış olup pek çok üreteçten daha hızlı çalışmaktadır. Bu algoritma bir süredir istatistik simülasyonlarında ve üretimsel modellemede tercih edilen rassal sayı üreteci olmaya başlamıştır.

Bununla birlikte Mersenne Twister algoritmasının çıktısını analiz edip sayıların rassal olmadıklarını anlamak mümkündür (Berlekamp-Massey algoritmasında veya bunun genişletilmiş hali olan Reed-Sloane algoritmasında olduğu gibi). Mersenne Twister algoritmasının bu bilinen olumsuz yönleri şimdilik onu şifrebilim uygulamalarında kullanılamaz kılmakla birlikte başka açılardan sorun teşkil etmemektedir (modelleme, simülasyon, vb. alanlarda kullanılabilmektedir).

Şifrebilimsel olarak güvenli rassal sayı üreteçleri

Ana madde: Cryptographically secure pseudo-random number generator

Şifrebilimsel olarak uygun olan bir sözde rassal sayı üreteci rassallık testlerini geçmeye ek olarak bazı ek şifrebilimsel koşulları da sağlamak zorundadır.

Bazı şifrebilimsel olarak güvenli sözde rassal sayı üretici algoritmalar şunlardır:

  • Counter modda veya çıktı besleme modunda çalışan dizi veya blok şifreleri.
  • Güvenlik kanıtı olan özel tasarımlar. Örn. Blum Blum Shub algoritmasının güçlü bir koşullu güvenlik kanıtı vardır ancak yavaş çalışmaktadır.
  • Şifrebilimsel olarak güvenliğe dikkat ederek tasarlanmış özel sözde rassal sayı üreteçleri. Örn. ISAAC algoritması. Bu algoritma epey hızlıdır ve periyodu büyüktür.

Bkz.

  • sözde rassal ikili dizi
  • rassallaştırılmış algoritma
  • rassal sayı üreteci
  • rassal sayı üreteç saldırısı
  • sözde rassal sayı üreteçleri listesi
  • Donanımsal rassal sayı üreteci
  • rassallık

Notlar

  1. ^ "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).
  2. ^ Peterson. Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6

Kaynakça

Dış bağlantılar

İlgili Araştırma Makaleleri

Komut kümesi mimarisi, CPU'nun yazılım tarafından nasıl kontrol edileceğini tanımlayan bilgisayar soyut modelinin bir parçasıdır. ISA, işlemcinin ne yapabileceğini ve bunu nasıl yapacağını belirterek donanım ve yazılım arasında bir arayüz gibi davranır.

MIPS, Microprocessor without Interlocked Pipeline Stages, MIPS teknolojileri adlı firma tarafından 1985 yılında geliştirilmiş indirgenmiş komut kümesi türü bir mikroişlemci mimarisidir.

<span class="mw-page-title-main">Derleyici</span> kaynak kodunu bilgisayarın işleyebileceği koda dönüştüren program

Derleyici, kaynak kodu makine koduna dönüştüren yazılımdır. Bir programlama dilinin derleyicisi, o programlama dili kullanılarak yazılmış olan kodu hedef işlemci mimarisine göre uygun şekilde makine koduna derler ve genellikle çıktı olarak yürütülebilir dosyanın oluşturulmasını sağlar. Bu eyleme derleme denir. Bir başka ifadeyle derleyici, bir tür yazı işleyicidir; girdi olarak yazı alır ve çıktı olarak yazı verir.

<span class="mw-page-title-main">RAM</span> herhangi bir sırada okunabilen ve değiştirilebilen bir tür geçici veri deposu

Rastgele erişimli hafıza veya rastgele erişimli bellek mikroişlemcili sistemlerde kullanılan, genellikle çalışma verileriyle birlikte makine kodunu depolamak için kullanılan herhangi bir sırada okunabilen ve değiştirilebilen bir tür geçici veri deposudur. Buna karşın diğer hafıza aygıtları saklama ortamındaki verilere önceden belirlenen bir sırada ulaşabilmektedir, çünkü mekanik tasarımları ancak buna izin vermektedir.

Bellek bilgisayarı oluşturan 3 ana bileşenden biridir.. İşlemcinin çalıştırdığı programı, lar ve programa ait bilgiler bellek üzerinde saklanır. Bellek geçici bir depolama alanıdır. Bellek üzerindeki bilgiler güç kesildiği anda kaybolurlar. Bu nedenle bilgisayarlarda programları daha uzun süreli ve kalıcı olarak saklamak için farklı birimler mevcuttur.

<span class="mw-page-title-main">DRAM (bilgisayar)</span>

Dinamik Rastgele Erişimli Bellek, dinamik rastgele erişimli bellek bir tümleşik devre içinde her bir veri bitini ayrı bir kapasitör içinde saklayan Rastgele Erişimli Bellek türüdür. Kapasitörler yapıları gereği bir süre sonra boşalacağından yenileme/tazeleme (refresh) devresine ihtiyaçları vardır. Bu yenileme ihtiyacından dolayı DRAM, SRAM ve diğer statik belleklerin zıddı durumundadır. DRAM’in SRAM üzerindeki avantajı onun yapısal basitliğidir: 1 bit için 1 transistör ve 1 kapasitör DRAM için yeterliyken SRAM için 6 transistör gerekir. DRAM, yenileme devresinden dolayı çok yer kaplar. Güç kaynağı açık olduğu durumda DRAM ve SRAM sakladığı verileri korur bu nedenle her iki bellek aygıtı da volatiledir.

<span class="mw-page-title-main">/dev/random</span>

Unix türevi işletim sistemlerinde, /dev/random yalancı rastsal sayılar üreten bir stream dosyasıdır. Cihaz sürücülerinden ve diğer kaynaklardan toplanan çevresel gürültüye erişim sağlar. Bloklama ile çalışır. /dev/random normalde talep edildiğinden daha az entropi mevcutsa engeller, /dev/urandom tipik olarak asla engellemez, /dev/arandom yeterli entropi ile güvenli bir şekilde başlatılana kadar önyükleme sonrası bloklar ve daha sonra asla bloklanmaz. /dev/random ve /dev/urandom farklı işletim sistemlerinde farklı şekillerde uygulanmaktadır ve pek azı /dev/arandom desteğine sahiptir.

<span class="mw-page-title-main">Aritmetik mantık birimi</span>

Aritmetik mantık birimi (AMB) aritmetik ve mantık işlemlerini gerçekleştiren bir dijital devredir. AMB en basit işlemi gerçekleştiren mikro denetleyiciden, en karmaşık mikroişlemciye sahip bir bilgisayara kadar tüm işlemcilerin yapıtaşıdır. Modern bilgisayarların içinde bulunan mikroişlemcilerin ve ekran kartlarının içinde çok karışık ve güçlü AMB'ler bulunmaktadır. AMB kavramına ilk olarak 1945 yılında matematikçi John von Neumann EDVAC adlı yeni bir bilgisayar üzerine bulgularını anlatan raporunda değinmiştir.

<span class="mw-page-title-main">Monte Carlo yöntemi</span>

Monte Carlo benzetimi, çok sayıda tekrarlanan rastgele örneklemelerle, bir takım nümerik sonuçlar elde etmeye yarayan ve bilimin birçok alanında yaygın olarak kullanılan bir sayısal hesaplama algoritmaları sınıfıdır. Stokastik olayların yer aldığı fiziksel süreçlerin sonuçlarının tahmin edilmesinde çok kullanışlıdır. Ayrıca, rastgele seçimlerin işe yaradığı ve prensipte deterministik olan bir takım problemlerin çözümünde de kullanılmaktadır. Monte-Carlo yöntemi, Nicholas Constantine Metropolis (1915-1999) tarafından bulunmuştur ve Atom bombasının geliştirildiği Los Alamos Ulusal Labratuvarında, bombanın patlamasından sonra dağılan nötronlara karşı kalkan modellemek için Stanislaw Ulam tarafından günümüze taşınmıştır.

Bilgisayar bilimlerinde değişik amaçlarla pek çok algoritma kullanılır. Aşağıda Vikipedi'de bulunan algoritmaların listesi verilmiştir.

Kriptografide çalışma kipleri, bir blok şifrenin tek bir anahtar altında güvenli bir şekilde tekrarlı kullanımına olanak veren yöntemlerdir. Değişken uzunluktaki mesajları işlemek için veriler ayrı parçalara bölünmelidir. Son parça şifrenin blok uzunluğuna uyacak şekilde uygun bir tamamlama şeması ile uzatılmalıdır. Bir çalışma kipi bu bloklardan her birini şifreleme şeklini tanımlar ve genellikle bunu yapmak için ilklendirme vektörü (IV) olarak adlandırılan rastgele oluşturulmuş fazladan bir değer kullanır.

<span class="mw-page-title-main">Dizi şifresi</span> simetrik anahtar şifreleme metodu

Kriptografide, bir kesintisiz şifreleme, dizi şifresi veya akış şifresi bir simetrik anahtardır. Düz metin bitlerinin bir exclusive-or (XOR) işlemi kullanılarak bir sözde rastgele şifre bit akışı ile birleştirildiği şifrelemedir. Bir akış şifresinde düz metin sayısal basamakları her seferinde bir tane şifrelenir ve ardışık basamakların dönüşümü şifreleme durumu sırasında değişir. Her bir basamağın şifrelenmesi mevcut duruma bağlı olduğundan alternatif bir isim durum şifresidir. Pratikte, basamaklar tipik olarak tek bitler veya baytlardır.

<span class="mw-page-title-main">Kriptografik özet fonksiyonu</span>

Kriptografik özet fonksiyonu çeşitli güvenlik özelliklerini sağlayan bir özet fonksiyonudur. Veriyi belirli uzunlukta bir bit dizisine, (kriptografik) özet değerine, dönüştürür. Bu dönüşüm öyle olmalıdır ki verideki herhangi bir değişiklik özet değerini değiştirmelidir. Özetlenecek veri mesaj, özet değeri ise mesaj özeti veya kısaca özet olarak da adlandırılır.

Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır.

<span class="mw-page-title-main">Eliptik eğri kriptografisi</span>

Eliptik Eğri Kriptolojisi, sonlu cisimler üzerindeki eliptik eğrilerin cebirsel topolojisine dayanan bir açık anahtar şifrelemesidir. Eliptik Eğri Kriptolojisi, diğer şifrelemeler göre daha küçük anahtar boyuna ihtiyaç duyar.

<span class="mw-page-title-main">Gerçek rassal sayı üreteci</span>

Programlama alanında kullanılan donanım rassal sayı üreteci bilgisayar programı kullanmayarak, fiziksel bir işleyiş ile rassal sayı üretimi için kullanılır. Bu tip cihazlar genel olarak mikroskobik olay tabanlı, istatistiksel olarak rassal gürültü sinyalleri içeren; ısıl gürültü, fotoelektrik etkisi kullanan hüzme bölücü ve diğer kuantum etkisi içeren olayları kullanır. Bu stokastik süreçler, teoride önceden kestirilemez ve teorinin öne sürdüğü sava göre deneysel test sonuçlarına tabiidir. Bir donanım rassal sayı üreteci genel olarak bir tip fiziksel bir gücü elektrik sinyaline dönüştürmek için güç çevirici, rassal dalgalanma genliklerini ölçülebilir seviyelere getirebilmek için güç yükselteç ve diğer elektrik devreleri ve de çıkışı sayısal bir veriye dönüştürebilmek için bir çeşit analog sayısal çevirici içerir. Genel olarak elde edilen sayı ikili sayı sisteminin elemanları olan 0 veya 1 dir. Arka arkaya alınan rassal değişen sayı örnekleri sayesinde sıralı olarak rassal sayılar elde edilir.

Kriptografi 'de bir 'Lamport imzası' veya 'Lamport bir defalık imza şeması' dijital imza oluşturmak için kullanılan bir yöntemdir. Lamport imzaları, kriptografik olarak güvenli herhangi bir tek yönlü fonksiyon ile oluşturulabilir; genellikle bir Kriptografik özet fonksiyonu kullanılır.

Kriptografide, scrypt, Colin Percival tarafından Tarsnap çevrimiçi yedekleme hizmeti için oluşturulan bir parola tabanlı anahtar türetme fonksiyonudur. Bu algoritma, büyük miktarda bellek gerektirerek büyük ölçekli özel donanım saldırılarını gerçekleştirmeyi pahalı hale getirmek için özel olarak tasarlanmıştır. 2016 yılında, scrypt algoritması IETF tarafından RFC 7914 olarak yayınlandı. Scrypt algoritmasının, ArtForz kullanıcı adına sahip ve gerçek adı bilinmeyen bir programcı tarafından implemente edilmiş, basitleştirilmiş bir sürümü, önce Tenebrix'te ve ardından Fairbrix ve Litecoin olmak üzere bir dizi kripto para birimi tarafından iş kanıtı şeması olarak kullanıldı.

Bu, Wikipedia'da yer alan sayı teorisi konularıyla ilgili sayfaların bir listesidir.

Kriptografide, bir ayırt edici saldırı, bir saldırganın şifreli verileri rastgele verilerden ayırt etmesini sağlayan bir şifreyle şifrelenmiş veriler üzerinde bulunan herhangi bir kriptanaliz biçimidir. Modern simetrik anahtar şifreleri, böyle bir saldırıya karşı bağışık olacak şekilde özel olarak tasarlanmıştır. Başka bir deyişle, modern şifreleme şemaları sözde rastgele permütasyonlardır ve şifreli metin ayırt edilemezliğine sahip olacak şekilde tasarlanmıştır. Çıktıyı rastgele bir brute force aramasından daha hızlı ayırt edebilen bir algoritma bulunursa, bu bir şifre kırılması olarak kabul edilir.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.