KECCAK, sıfırlarla dolu bir durum dizisi üzerinde nasıl çalışır?
Java'da bir sünger uygulamaya çalışıyorum. Durum, tamamı sıfırlardan oluşan 200 baytlık boş bir dizi olarak başlar. NIST'ten alınan KMAC örnekleri belgesinde aşağıdakiler gerçekleşir:
(siyah çizgi bir pdf sayfa sonudur)
Bunu okuma şeklim, bir grup sıfır içeren bir durumun KECCAK'a gönderilmesi ve ardından görünüşte rastgele verilere sahip bir durumun döndürülmesidir. SHA3 / KECCAK boş verileri rastgele verilere dönüştürür mü? Burada doğru soruları mı soruyorum? Herhangi bir yardım takdir edilmektedir.
Yanıtlar
Ben şahsen Keccak.team Psuedo Kod belgesini Keccak-p.
DannyNiu'nun yorumlarda söylediği gibi, çoğu (tümü?) Kriptografik permütasyon "yuvarlak sabitler" kullanır. Bu sabitler Keccak durumunda bir şekilde karıştırılır.
Sözde kod belgesi yuvarlak sabitleri tablo olarak verir:
RC[0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[2] 0x800000000000808A RC[14] 0x8000000000008089
RC[3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[4] 0x000000000000808B RC[16] 0x8000000000008002
RC[5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[8] 0x000000000000008A RC[20] 0x8000000080008081
RC[9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
ve nasıl kullanıldığını açıklar. İota adımında$n^\text{th}$ Keccak-p yuvarlak $n^\text{th}$ yuvarlak sabit $RC[n]$ tanıtılır ve ilk kelime olan ilk şeritte XOR'lanır.
Yuvarlak sabitlerin yanı sıra, Keccak permütasyonu çok iyi bir difüzyona sahiptir: başlangıç durumunda bir yerde tek bir bit, birçok çıktı bitine önemli ölçüde katkıda bulunacaktır.
Her ikisinin kombinasyonu, Keccak permütasyonunuzun çok rastgele göründüğü anlamına gelir . Elbette sıfır entropiyi rasgele çeviremez, çünkü hiçbir sonlu algoritma bunu yapamaz, ancak Keccak'ın amacı etrafındaki şeyleri karıştırmak ve rastgele görünmelerini sağlamaktır.
Keccak permütasyon fonksiyonu normal olarak sıfır girişini (tüm bitler 0'dır), eğer iota adımı için değilse, durumdaki bir word'ün sıfır olmayan bir sabit ile XORed olduğu sıfır çıktıya eşler.
Tam yayılma için yaklaşık üç (24) tur yeterlidir, yani durumun her biti, üç tur sonra diğer her biti etkiler. Permütasyonun durumu sekiz kez tamamen karıştırdığı söylenebilir. Bu, eğer sadece bir bit 1 ise, durum üzerinde hızlı bir şekilde yayılacağı anlamına gelir, böylece 3 tur sonra durum bitlerinin yaklaşık yarısı 1 olur.
İzin Vermek $R$makul bir şekilde "düzenli görünümlü" olarak adlandırılabilen durum değerleri kümesi olabilir (tam tanım ne olursa olsun), örneğin bitlerin tümü veya hemen hemen tümü aynı değere sahiptir veya kısa bir bit modeli düzenli olarak tekrar eder. Hepsi arasında$2^{1600}$ eyaletler, içinde olanlar $R$çok küçük bir kesirdir. Herhangi bir eyalette olması pek olası değildir$R$ aynı zamanda bir çıktıya eşlenir $R$. Bu olduğu sürece geçerli$|R| \ll 2^{800}$ (bkz. "doğum günü paradoksu").
Bu, normal görünümlü bir çıktıya eşlenen normal görünümlü bir girdi olmadığı anlamına gelir. Ve herhangi bir durumun, içindeki bir çıktıya eşlenme olasılığı$R$ önemsizdir, yani çıktı her zaman rastgele görünecektir, ancak birisi kasıtlı olarak permütasyonun tersini hesaplayarak girdiyi oluşturur.