215E225 TÜBİTAK 3001 PROJESİ SONUÇ RAPORU
Rastgele Sayı Test Paketleri ile İlgili Çalışmalar
Rasgele sayı üreteçleri tarafından üretilen rasgele sayıların istatistiki olarak yeterliliklerini test etmek amacıyla çeşitli test paketleri kullanılmaktadır. Bu paketler çeşitli matematiksel testlerin bir veya farklı parametrelerle birden fazla çalıştırılması şeklinde sonuç üretmektedir. Bu proje kapsamında bu test paketlerinden 3’ü kullanılmıştır. Kullanılan her bir test paketi hakkında aşağıda bilgiler verilmiş ve bu paketlerle ile ilgili yapılan çeşitli çalışmalara değinilmiştir.
DIEHARD (Eddelbuettel vd., 1995), rastgele sayı üreteçlerini test eden test paketidir. DIEHARD test paketinde; doğum günü aralıkları (birthday spacings), çakışan permütasyonlar (overlapping permutations), matris sıraları (ranks of matrices), maymun testleri (monkey tests), 1'lerin sayısı (count the 1s), minimum mesafe (minimum distance), park yeri testi (parking lot test), rastgele küreler (random spheres), sıkıştırma (the squeeze), çakışan toplamlar (overlapping sums), akışlar (runs) ve kreps (craps) testleri yer almaktadır.
• Doğum Günü Aralıkları Testi (Birthday Spacings Test): Büyük bir aralıkta rastgele noktalar seçilmektedir. Noktalar arasındaki boşluklar asimptotik olarak üstel dağılmalıdır.
• Çakışan Permütasyonlar Testi (Overlapping Permutations Test): Ardışık beş rastgele sayı dizisi analiz edilmektedir. 120 olası sıralama istatistiksel olarak eşit olasılıkla yapılmalıdır.
• Matris Sıraları Testi (Ranks of Matrices Test): Periyodikliğe bağlı olarak rastgele bir sıralamadan rastgele dağılımın sapmasıdır.
• Maymun Testleri (Monkey Tests): Bazı bitlerin sayısı "kelimeler" olarak değerlendirilmektedir. Bir akıştaki örtüşen kelimeler sayılmaktadır. Görünmeyen "kelimeler" sayısı bilinen bir dağılımı izlemelidir.
• 1’ lerin Sayısı Testi (Count the 1s Test): Bayt akışı içindeki 1’lerin sayısını vermektedir.
• Park Yeri Testi (Parking Lot Test): Daireler 100 × 100 kareye rastgele yerleştirilmektedir. Bir daire, başarılı bir şekilde park edilmiş bir parkurla çakışmazsa, başarıyla park edilmiş olur. 12.000 denemeden sonra başarıyla park edilmiş dairelerin sayısı bilinen bir normal dağılımı izlemelidir.
• Minimum Mesafe Testi (Minimum Distance Test): 10.000 × 10.000 kare arasında 8000 puan rastgele yerleştirilmekte, ardından çiftler arasındaki minimum mesafe bulunmaktadır. Bu mesafenin karesi belli bir ortalamayla katlanarak dağılmalıdır.
• Rastgele Küreler Testi (Random Spheres Test): 1000 kenarlı bir küp üzerinde rastgele 4000 nokta seçilmektedir. Her noktayı merkezi kabul eden ve diğer bir noktaya olan uzaklığı minimum olacak şekilde yarıçapa sahip bir küre yerleştirilir. En küçük kürenin hacmi belli bir ortalamayla üstel olarak dağılmalıdır.
• Sıkıştırma Testi (The Squeeze Test): 231‘i (0-1) arasındaki rastgele belirlenen ondalıklı sayılar 1’e ulaşıncaya kadar çarpılmaktadır. Bu 100.000 kez tekrarlanmaktadır. 1'e ulaşmak için gerekli ondalıklı sayılar belli bir dağılımı izlemelidir.
• Çakışan Toplamlar Testi (Overlapping Sums Test): (0,1) arasında ondalıklı sayılardan oluşan uzun bir dizi oluşturulmaktadır. Bu sayılar, karakteristik ortalama ve varyans ile normal dağılım sergilemelidirler.
• Akış Testi (Runs Test): Dizideki 0 ve 1’lerin arasındaki dalgalanmaların kontrol edilmesidir.
• Kreps Testi (Craps Test): Bu test 200.000 defa craps adlı oyunu oynama, kazanma, sayma ve oyun başına atış sayısını sayma işlemlerinden oluşmaktadır. Her sayım belirli bir dağılımı izlemelidir.
ENT çalışmasında (Walker, 2008), dosyalarda depolanan bayt dizilerine çeşitli testler uygulayan ve bu testlerin sonuçlarını gösteren bir program açıklanmıştır. Program, şifreleme ve istatistiksel örnekleme uygulamaları, sıkıştırma algoritmaları ve bir dosyanın bilgi yoğunluğunun ilgisinin olduğu diğer uygulamalar için sahte rastgele sayı üreteçlerini değerlendirmede kullanışlı görülmüştür. Ent testi; Ki-kare (Chi-Square), aritmetik ortalama, Monte Karlo değeri, seri korelasyon katsayısı testlerini içermektedir.
• Ki-kare Testi (Chi-Square Test): Ki-kare dağılımı, girdi olarak verilen dosyadaki bayt akışı için hesaplanmaktadır ve bu dağılım mutlak bir sayı ve gerçekten rastgele bir dizinin hesaplanan değeri aştığı sıklığı gösteren yüzde olarak ifade edilmektedir. Yüzde, test edilen dizinin rastgele olma ihtimalinden şüphelenilen derece olarak yorumlanmaktadır. Oran %99'dan büyükse veya %1'den düşükse, sıralama kesinlikle rastgele değildir. Oran %99 ile %95 arasında veya %1 ile %5 arasında ise, dizi şüphelidir. Oranın %90 ile %95 ve %5 ile %10 arasında olması, dizinin "neredeyse şüpheli" olduğunu göstermektedir.
• Aritmetik Ortalama: Dosyadaki tüm baytların toplanıp dosya uzunluğuna bölünmesidir. Veriler rastgele ise, bu değer yaklaşık 127,5 olmalıdır.
• Pi için Monte Carlo Değeri: Altı baytın birbirini izleyen her dizisi bir karede 24 bit X ve Y koordinatları olarak kullanılmaktadır. Rastgele üretilen nokta mesafesi kare içine yazılmış bir dairenin yarıçapından daha küçükse, altı baytlık dizi "vuruş" olarak kabul edilmektedir. İsabet yüzdesi, Pi değerini hesaplamak için kullanılmaktadır. Çok büyük akışlar için, dizinin rastgele olması durumunda değer Pi sayısına yaklaşmaktadır.
• Seri Korelasyon Katsayısı: Bu değer, dosyadaki her baytın bir önceki bayta ne ölçüde bağlı olduğunu ölçmektedir. Rastgele sekanslar için, bu sıfıra yakın olmalıdır.
NIST testini anlatan temel makalede (Rukhin vd., 2010), rastgele ve sözde rastgele sayı üreteçlerinin seçilmesi ve istatistiksel olarak test edilmesinin bazı yöntemleri anlatılmıştır. Bu jeneratörlerin çıktıları, anahtar malzemenin üretilmesi gibi birçok şifreleme uygulamasında kullanılabilmektedir. Rastgelelik için önerilen istatistiksel testler bu çalışmada detaylı bir şekilde verilmiştir. Bu testlerin, bir jeneratörün belirli bir şifreleme uygulaması için uygun olup olmadığının belirlenmesinde ilk adım olarak yararlı olabileceği savunulmuştur.
NIST İstatistik Test Paketi; Frekans (frequency), blok frekans (block frequency), kümülatif toplamlar (cumulative sums), akış (runs), bloktaki en uzun birler (longest runs of ones), sıra (rank), spektral (spectral), çakışmayan şablon eşleştirmeleri (non-overlapping template matchings), çakışan şablon eşleştirmeleri (overlapping template matchings), evrensel istatistiksel (universal statistical), rastgele geziler (random excursions), rastgele gezi varyantı (random excursions variant), yaklaşık entropi (approximate entropy), seri (serial) ve doğrusal karmaşıklık (linear complexity) testlerini içermektedir. Bu testlerin sonuçları olasılık değerlerine göre değerlendirilmektedir. Örneğin; frekans testinin olasılık değeri 0,01’den küçükse test başarısızdır.
• Frekans Testi (Frequency Test): Dizinin 0 ve 1 oranlarının test edilmesidir.
• Blok Frekans Testi (Block Frequency Test): Dizideki 0 ve 1’lerin oranının M bitlik bloklar içinde kontrol edilmesidir.
• Kümülatif Toplamlar Testi (Cumulative Sums Test): Dizinin başlangıcından itibaren 0 ve 1 oranlarının kontrol edilmesidir.
• Akış Testi (Runs Test): Dizideki 0 ve 1’lerin arasındaki dalgalanmaların kontrol edilmesidir.
• Bloktaki En Uzun Birler Testi (Longest Runs Of Ones Test): Dizinin M-bitlik bloklarında bulunan en uzun 1’ler grubunun kontrol edilmesidir.
• Sıra Testi (Rank Test): Periyodikliğe bağlı olarak rastgele bir sıralamadan rastgele dağılımın sapmasıdır.
• Spektral Testi (Spectral Test): Bit akışındaki periyodik özelliklerin kontrol edilmesidir.
• Çakışmayan Şablon Eşleştirmeleri Testi (Non-overlapping Template Matchings Test): Periyodik olmayan şablonların miktarını kontrol eder.
• Çakışan Şablon Eşleştirmeleri Testi (Overlapping Template Matchings Test): Blokların M bitlik akışını kontrol eder.
• Evrensel İstatistiksel Test (Universal Statistical Test): Sıkıştırılabilirliğin kontrol edilmesidir.
• Rastgele Geziler Testi (Random Excursions Test): Rastgele bir yürüyüşün belirli bir yere yapılan ziyaret sayısının dağılımından sapmanın kontrol edilmesidir.
• Rastgele Gezi Varyantı Testi (Random Excursions Variant Test): Birçok rastgele yürüyüş boyunca toplam ziyaret sayısının dağılımından sapmanın kontrol edilmesidir.
• Yaklaşık Entropi Testi (Approximate Entropy Test): M uzunluklu dizilerin dağınık olmayan dağılımının kontrol edilmesidir.
• Seri Testi (Serial Test): M uzunluklu bitlerin dağınık olmayan dağılımının kontrol edilmesidir. Yaklaşık entropi testine benzer.
• Doğrusal Karmaşıklık Testi (Linear Complexity Test): Sonlu alt diziler için doğrusal karmaşıklığın dağılımından sapmanın kontrol edilmesidir.
DIEHARD (Eddelbuettel vd., 1995), rastgele sayı üreteçlerini test eden test paketidir. DIEHARD test paketinde; doğum günü aralıkları (birthday spacings), çakışan permütasyonlar (overlapping permutations), matris sıraları (ranks of matrices), maymun testleri (monkey tests), 1'lerin sayısı (count the 1s), minimum mesafe (minimum distance), park yeri testi (parking lot test), rastgele küreler (random spheres), sıkıştırma (the squeeze), çakışan toplamlar (overlapping sums), akışlar (runs) ve kreps (craps) testleri yer almaktadır.
• Doğum Günü Aralıkları Testi (Birthday Spacings Test): Büyük bir aralıkta rastgele noktalar seçilmektedir. Noktalar arasındaki boşluklar asimptotik olarak üstel dağılmalıdır.
• Çakışan Permütasyonlar Testi (Overlapping Permutations Test): Ardışık beş rastgele sayı dizisi analiz edilmektedir. 120 olası sıralama istatistiksel olarak eşit olasılıkla yapılmalıdır.
• Matris Sıraları Testi (Ranks of Matrices Test): Periyodikliğe bağlı olarak rastgele bir sıralamadan rastgele dağılımın sapmasıdır.
• Maymun Testleri (Monkey Tests): Bazı bitlerin sayısı "kelimeler" olarak değerlendirilmektedir. Bir akıştaki örtüşen kelimeler sayılmaktadır. Görünmeyen "kelimeler" sayısı bilinen bir dağılımı izlemelidir.
• 1’ lerin Sayısı Testi (Count the 1s Test): Bayt akışı içindeki 1’lerin sayısını vermektedir.
• Park Yeri Testi (Parking Lot Test): Daireler 100 × 100 kareye rastgele yerleştirilmektedir. Bir daire, başarılı bir şekilde park edilmiş bir parkurla çakışmazsa, başarıyla park edilmiş olur. 12.000 denemeden sonra başarıyla park edilmiş dairelerin sayısı bilinen bir normal dağılımı izlemelidir.
• Minimum Mesafe Testi (Minimum Distance Test): 10.000 × 10.000 kare arasında 8000 puan rastgele yerleştirilmekte, ardından çiftler arasındaki minimum mesafe bulunmaktadır. Bu mesafenin karesi belli bir ortalamayla katlanarak dağılmalıdır.
• Rastgele Küreler Testi (Random Spheres Test): 1000 kenarlı bir küp üzerinde rastgele 4000 nokta seçilmektedir. Her noktayı merkezi kabul eden ve diğer bir noktaya olan uzaklığı minimum olacak şekilde yarıçapa sahip bir küre yerleştirilir. En küçük kürenin hacmi belli bir ortalamayla üstel olarak dağılmalıdır.
• Sıkıştırma Testi (The Squeeze Test): 231‘i (0-1) arasındaki rastgele belirlenen ondalıklı sayılar 1’e ulaşıncaya kadar çarpılmaktadır. Bu 100.000 kez tekrarlanmaktadır. 1'e ulaşmak için gerekli ondalıklı sayılar belli bir dağılımı izlemelidir.
• Çakışan Toplamlar Testi (Overlapping Sums Test): (0,1) arasında ondalıklı sayılardan oluşan uzun bir dizi oluşturulmaktadır. Bu sayılar, karakteristik ortalama ve varyans ile normal dağılım sergilemelidirler.
• Akış Testi (Runs Test): Dizideki 0 ve 1’lerin arasındaki dalgalanmaların kontrol edilmesidir.
• Kreps Testi (Craps Test): Bu test 200.000 defa craps adlı oyunu oynama, kazanma, sayma ve oyun başına atış sayısını sayma işlemlerinden oluşmaktadır. Her sayım belirli bir dağılımı izlemelidir.
ENT çalışmasında (Walker, 2008), dosyalarda depolanan bayt dizilerine çeşitli testler uygulayan ve bu testlerin sonuçlarını gösteren bir program açıklanmıştır. Program, şifreleme ve istatistiksel örnekleme uygulamaları, sıkıştırma algoritmaları ve bir dosyanın bilgi yoğunluğunun ilgisinin olduğu diğer uygulamalar için sahte rastgele sayı üreteçlerini değerlendirmede kullanışlı görülmüştür. Ent testi; Ki-kare (Chi-Square), aritmetik ortalama, Monte Karlo değeri, seri korelasyon katsayısı testlerini içermektedir.
• Ki-kare Testi (Chi-Square Test): Ki-kare dağılımı, girdi olarak verilen dosyadaki bayt akışı için hesaplanmaktadır ve bu dağılım mutlak bir sayı ve gerçekten rastgele bir dizinin hesaplanan değeri aştığı sıklığı gösteren yüzde olarak ifade edilmektedir. Yüzde, test edilen dizinin rastgele olma ihtimalinden şüphelenilen derece olarak yorumlanmaktadır. Oran %99'dan büyükse veya %1'den düşükse, sıralama kesinlikle rastgele değildir. Oran %99 ile %95 arasında veya %1 ile %5 arasında ise, dizi şüphelidir. Oranın %90 ile %95 ve %5 ile %10 arasında olması, dizinin "neredeyse şüpheli" olduğunu göstermektedir.
• Aritmetik Ortalama: Dosyadaki tüm baytların toplanıp dosya uzunluğuna bölünmesidir. Veriler rastgele ise, bu değer yaklaşık 127,5 olmalıdır.
• Pi için Monte Carlo Değeri: Altı baytın birbirini izleyen her dizisi bir karede 24 bit X ve Y koordinatları olarak kullanılmaktadır. Rastgele üretilen nokta mesafesi kare içine yazılmış bir dairenin yarıçapından daha küçükse, altı baytlık dizi "vuruş" olarak kabul edilmektedir. İsabet yüzdesi, Pi değerini hesaplamak için kullanılmaktadır. Çok büyük akışlar için, dizinin rastgele olması durumunda değer Pi sayısına yaklaşmaktadır.
• Seri Korelasyon Katsayısı: Bu değer, dosyadaki her baytın bir önceki bayta ne ölçüde bağlı olduğunu ölçmektedir. Rastgele sekanslar için, bu sıfıra yakın olmalıdır.
NIST testini anlatan temel makalede (Rukhin vd., 2010), rastgele ve sözde rastgele sayı üreteçlerinin seçilmesi ve istatistiksel olarak test edilmesinin bazı yöntemleri anlatılmıştır. Bu jeneratörlerin çıktıları, anahtar malzemenin üretilmesi gibi birçok şifreleme uygulamasında kullanılabilmektedir. Rastgelelik için önerilen istatistiksel testler bu çalışmada detaylı bir şekilde verilmiştir. Bu testlerin, bir jeneratörün belirli bir şifreleme uygulaması için uygun olup olmadığının belirlenmesinde ilk adım olarak yararlı olabileceği savunulmuştur.
NIST İstatistik Test Paketi; Frekans (frequency), blok frekans (block frequency), kümülatif toplamlar (cumulative sums), akış (runs), bloktaki en uzun birler (longest runs of ones), sıra (rank), spektral (spectral), çakışmayan şablon eşleştirmeleri (non-overlapping template matchings), çakışan şablon eşleştirmeleri (overlapping template matchings), evrensel istatistiksel (universal statistical), rastgele geziler (random excursions), rastgele gezi varyantı (random excursions variant), yaklaşık entropi (approximate entropy), seri (serial) ve doğrusal karmaşıklık (linear complexity) testlerini içermektedir. Bu testlerin sonuçları olasılık değerlerine göre değerlendirilmektedir. Örneğin; frekans testinin olasılık değeri 0,01’den küçükse test başarısızdır.
• Frekans Testi (Frequency Test): Dizinin 0 ve 1 oranlarının test edilmesidir.
• Blok Frekans Testi (Block Frequency Test): Dizideki 0 ve 1’lerin oranının M bitlik bloklar içinde kontrol edilmesidir.
• Kümülatif Toplamlar Testi (Cumulative Sums Test): Dizinin başlangıcından itibaren 0 ve 1 oranlarının kontrol edilmesidir.
• Akış Testi (Runs Test): Dizideki 0 ve 1’lerin arasındaki dalgalanmaların kontrol edilmesidir.
• Bloktaki En Uzun Birler Testi (Longest Runs Of Ones Test): Dizinin M-bitlik bloklarında bulunan en uzun 1’ler grubunun kontrol edilmesidir.
• Sıra Testi (Rank Test): Periyodikliğe bağlı olarak rastgele bir sıralamadan rastgele dağılımın sapmasıdır.
• Spektral Testi (Spectral Test): Bit akışındaki periyodik özelliklerin kontrol edilmesidir.
• Çakışmayan Şablon Eşleştirmeleri Testi (Non-overlapping Template Matchings Test): Periyodik olmayan şablonların miktarını kontrol eder.
• Çakışan Şablon Eşleştirmeleri Testi (Overlapping Template Matchings Test): Blokların M bitlik akışını kontrol eder.
• Evrensel İstatistiksel Test (Universal Statistical Test): Sıkıştırılabilirliğin kontrol edilmesidir.
• Rastgele Geziler Testi (Random Excursions Test): Rastgele bir yürüyüşün belirli bir yere yapılan ziyaret sayısının dağılımından sapmanın kontrol edilmesidir.
• Rastgele Gezi Varyantı Testi (Random Excursions Variant Test): Birçok rastgele yürüyüş boyunca toplam ziyaret sayısının dağılımından sapmanın kontrol edilmesidir.
• Yaklaşık Entropi Testi (Approximate Entropy Test): M uzunluklu dizilerin dağınık olmayan dağılımının kontrol edilmesidir.
• Seri Testi (Serial Test): M uzunluklu bitlerin dağınık olmayan dağılımının kontrol edilmesidir. Yaklaşık entropi testine benzer.
• Doğrusal Karmaşıklık Testi (Linear Complexity Test): Sonlu alt diziler için doğrusal karmaşıklığın dağılımından sapmanın kontrol edilmesidir.