Rastgelelik ve Sözde Rastgelelik
Rastgelelik, kriptografinin can damarıdır — anahtarların, nonce'ların ve meydan okumaların öngörülemez olması gerekmektedir — ve sözde rastgelelik, kısa, gerçek rastgele bir tohumun herhangi bir etkili düşman için rastgelelikten ayırt edilemez uzun dizilere genişletilmesine olanak tanımaktadır.
Tanım
Sözde rastgelelik, gerçek rastgelelikten hesaplama açısından ayırt edilemez olma özelliğidir; bir sözde rastgele üreteç, kısa bir rastgele tohumu deterministik olarak, hiçbir etkili algoritmanın rastgelelikten ayırt edemeyeceği daha uzun bir çıktıya genişletmektedir.
Kapsam
Bu konu, kriptografide rastgeleliğin rolünü kapsamaktadır: entropi kaynakları ve gerçek rastgele sayı üreteçleri üzerindeki gereksinimler, kriptografik olarak güvenli sözde rastgele üreteçlerin ve sözde rastgele fonksiyonların tanımları ve yapıları ile zayıf veya yeniden kullanılan rastgeleliğin feci sonuçları ele alınmaktadır. Sözde rastgele nesnelerin simetrik ilkelleri nasıl biçimlendirdiğini açıklamaktadır. Kardeş konularda ele alınan belirli şifreleri ve zorluk varsayımlarını hariç tutmaktadır.
Temel sorular
- Kriptografi neden öngörülemez rastgelelik gerektirmektedir ve bu olmadan neler yanlış gitmektedir?
- Kriptografik olarak güvenli bir üreteci istatistiksel olandan ayıran nedir?
- Kısa, gerçek rastgele bir tohum, uzun sözde rastgele çıktıya nasıl genişletilebilmektedir?
- Sözde rastgele fonksiyonlar ve permütasyonlar nelerdir ve şifreleri nasıl modellemektedirler?
- Gerçek sistemlerde yüksek kaliteli entropi nasıl toplanmakta ve işlenmektedir?
Anahtar kavramlar
- entropi ve gerçek rastgelelik
- rastgele sayı üreteçleri
- sözde rastgele üreteç (PRG)
- sözde rastgele fonksiyon (PRF)
- sözde rastgele permütasyon (PRP)
- hesaplama açısından ayırt edilemezlik
- tohum ve anahtar türetme
- rastgelelik yeniden kullanım hataları
- entropi işleme
Temel kuramlar
- Sözde rastgele üreteçler
- Bir sözde rastgele üreteç, kısa bir tohumu, herhangi bir etkili ayırt edici için tekdüze rastgelelikten ayırt edilemez daha uzun bir dizeye genişletmektedir; bu tür üreteçler, ancak ve ancak tek yönlü fonksiyonlar varsa var olmakta, sözde rastgeleliği kriptografinin temellerine bağlamaktadır.
- Sözde rastgele fonksiyonlar ve permütasyonlar
- Herhangi bir sözde rastgele üreteçten inşa edilebilen bir sözde rastgele fonksiyon ailesi, onu sorgulayan bir düşman için gerçek bir rastgele fonksiyondan ayırt edilemezdir; bu nesne, blok şifrelerin ve mesaj doğrulama kodlarının güvenlik modellemesinin temelini oluşturmaktadır.
Mekanizmalar
Gerçek bir rastgele sayı üreteci, fiziksel entropiyi (termal gürültü, zamanlama titremesi) toplamakta, bu entropi işlenmekte ve bir sistemin ihtiyaç duyduğu tüm rastgele görünen bitleri deterministik olarak üreten kriptografik olarak güvenli bir sözde rastgele üreteci beslemek için kullanılmaktadır. Sözde rastgele fonksiyonlar üreteçlerden (GGM yapısı) inşa edilmekte ve anahtarlı ilkelleri modellemektedir; bir blok şifre, bir sözde rastgele permütasyon olarak ele alınmaktadır. Güvenlik tanımları, çıktıları verilen hiçbir etkili düşmanın daha fazla biti tahmin edememesini veya bunları rastgelelikten ayırt edememesini gerektirmektedir.
Klinik önem
Rastgelelik hataları, feci gerçek dünya ihlallerinin tekrar eden bir kaynağıdır: 2008 Debian OpenSSL hatası anahtar üretimini sakatlamış, öngörülebilir ECDSA nonce'ları özel anahtarları sızdırmış (Sony PlayStation 3, bazı Bitcoin cüzdanları) ve zayıf gömülü cihaz entropisi, büyük ölçekte tahmin edilebilir anahtarlar üretmiştir. Bu nedenle, sağlam rastgelelik — uygun entropi toplama ve onaylanmış sözde rastgele üreteçler — her kriptografik dağıtım için elzemdir.
Kanıt ve kılavuzlar
NIST SP 800-90A/B/C, onaylanmış deterministik rastgele bit üreteçlerini, entropi kaynağı doğrulamasını ve yapılandırma rehberliğini belirtmektedir. En iyi uygulama, işletim sisteminin onaylanmış kriptografik RNG'sini kullanmakta (kendi RNG'sini geliştirmek yerine), anahtarları üretmeden önce yeterli entropi sağlamakta ve nonce'ları asla yeniden kullanmamaktadır. İstatistiksel test paketleri büyük kusurları tespit etmeye yardımcı olmakta ancak kriptografik gücü belirleyememektedir.
Tarihçe
Sözde rastgeleliğin hesaplama teorisi, 1982 civarında Blum ve Micali ile Yao tarafından kurulmuş, öngörülemezlik ve ayırt edilemezliği tanımlamıştır. Goldreich, Goldwasser ve Micali, 1986'da üreteçlerden sözde rastgele fonksiyonların nasıl inşa edileceğini göstermiş, Hastad, Impagliazzo, Levin ve Luby ise daha sonra tek yönlü fonksiyonlar varsa sözde rastgele üreteçlerin var olduğunu kanıtlamıştır. Zayıf rastgelelikten kaynaklanan tekrarlayan pratik felaketler, entropi ve RNG kalitesini merkezi bir mühendislik endişesi olarak tutmuştur.
Öne çıkan isimler
- Oded Goldreich
- Shafi Goldwasser
- Silvio Micali
- Manuel Blum
- Andrew Yao
İlgili konular
Temel eserler
- goldreich1986
- goldreich2001
- katz2020
Sıkça sorulan sorular
- Kriptografi için neden rand() gibi normal bir rastgele fonksiyonu kullanamam?
- Sıradan rastgele sayı üreteçleri, öngörülemezlik için değil, istatistiksel tekdüzelik ve hız için inşa edilmektedir; çıktıları birkaç örnekten tahmin edilebilmektedir. Kriptografi, geçmiş çıktı verildiğinde bile gelecekteki çıktısı tahmin edilemez olan üreteçlere ihtiyaç duymaktadır, bu da gerçek entropi ile beslenen kriptografik olarak güvenli bir RNG gerektirmektedir.
- Gerçek rastgelelik ile sözde rastgelelik arasındaki fark nedir?
- Gerçek rastgelelik, fiziksel, öngörülemez bir kaynaktan gelmekte ve arzı sınırlıdır. Sözde rastgelelik, kısa, gerçek rastgele bir tohumdan deterministik olarak üretilmekte ve toplu olarak üretilebilmektedir; yalnızca herhangi bir etkili düşman için gerçek rastgelelikten ayırt edilemez olması gerekmektedir, bu da kriptografik kullanım için yeterlidir.