Rastsal Kahin

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Şifrelemede, rastsal kahin kendisine yapılan her sorguya, çıktı uzayından (gerçekten) rastgele, eşit olasılıkla seçilmiş, fakat her bir ayrı sorguya her seferinde aynı şekilde cevap veren bir kahin (kuramsal bir kara kutu)'dur. Başka bir deyişle, rastsal kahin olası her bir sorguyu çıktı uzayından rastgele bir yanıta eşleyen matematiksel bir fonksiyondur.

Rastsal kahinler, şifreleme bilimindeki kanıtlarda kullanılan bir matematiksel soyutlamadır; bunlar genellikle kanıtın gerektirdiği matematiksel özellikleri sağlayan bilinen gerçeklenebilir bir fonksiyon bulunmadığında kullanılmaktadır. Bu şekilde kanıtlanarak güvenli olduğu gösterilen bir sistem standart modeldeki güvenli kavramına karşılık olarak rastsal kahin modelinde güvenli olarak tanımlanır. Uygulamada, rastsal kahinler genellikle özet fonksiyonunun çıktısı hakkında güçlü rastsal varsayımların gerektiği şemalara sahip şifreleme özüt fonksiyonlarını modellemek amacıyla kullanılır. Böyle bir kanıt, genel olarak bir sistemin veya bir protokolün, bir saldırganın protokolü kırabilmesi için ya kahinden olanaksız bir davranış görmesi gerektiğini ya da zor olduğuna inanılan matematiksel bir problemi çözmesi gerektiğini göstererek güvenli olduğunu gösterir. Bütün şifreleme özüt fonksiyonları rastsal kahinler gerektirmez: sadece çakışma dirençlilik özelliğini gerektiren şemaların standart modelde güvenliliği kanıtlanabilir (örn. Cramer-Shoup şifreleme sistemi).

Rastsal kahinler Karmaşıklık Kuramında uzun zamandır kabul görmüştür. (örn. Bennett & Gill[1]). Fiat ve Shamir (1986)[2] imza üretimi protokollerinden etkileşimin çıkarılması konusunda rastsal kahinlerin önemli bir uygulamasını yapmışlardır. Impagliazzo ve Rudich (1989)[3] sadece rastsal kahinlerin varlığının gizli anahtar değişimi için yeterli kanıt olmadığını söyleyerek rastsal kahin modelinin sınırlarını göstermişlerdir. Bellare ve Rogaway (1993)[4] şifreleme yapılarında onların kullanımını savunmuştur. Bu tanımda, rastsal kahin istenilen uzunluğa kesilebilecek olan sonsuz uzunlukta bir bit-dizgesi üretir. Bir rastsal kahin bir güvenlik kanıtı içinde kullanıldığında, rakip ya da rakipler de dahil olmak üzere tüm oyuncular için kullanılabilir durumdadır. Tek bir rastsal kahine her sorgudan önce sabit bir bit-dizgesi eklenerek (örn. başına "1|x" ya da "0|x" eklenmiş sorgular iki ayrı rastsal kahine yapılmış gibi, benzer olarak "00|x", "01|x", "10|x" ve "11|x" eklenmiş sorgular da dört ayrı rastsal kahine yapılmış sorgular gibi kabul edilebilir) birden fazla kahin gibi davranılabilir.

Hiçbir gerçek fonksiyon gerçek bir rastsal kahini gerçekleyemez. Aslında, rastsal kahin modelinde güvenliliği kanıtlanmış olan bazı yapay imza ve şifreleme şemalarının, rastsal kahin yerine herhangi bir gerçek fonksiyon kullanıldığında basitçe güvensiz olduğu bilinmektedir.[5] Bununla birlikte, herhangi bir daha doğal protokol için rastsal kahin modelindeki bir güvenlik kanıtı, varsa (tamsayıların çarpanlara ayrılmasının zorluğu gibi) kanıtın diğer varsayımlarını kırmayan herhangi bir saldırının protokolde kullanılan özüt fonksiyonunun bilinmeyen ve istenmeyen bir özelliğini keşfetmesini gerektiren çok güçlü göstergeler sunar. Birçok şemanın rastsal kahin modelinde güvenli olduğu gösterilmiştir, örnek olarak OAEP ve PSS verilebilir.

Ayrıca bakınız[değiştir | kaynağı değiştir]

Referanslar[değiştir | kaynağı değiştir]

  1. ^ Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing 10 (1): 96–113, ISSN 1095-7111 
  2. ^ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186-194
  3. ^ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44-61
  4. ^ Mihir Bellare and Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp. 62–73 (PS and PDF).
  5. ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).

Dış bağlantılar[değiştir | kaynağı değiştir]