Hızlı sendroma dayalı karma - Fast syndrome-based hash - Wikipedia

İçinde kriptografi, hızlı sendrom tabanlı hash fonksiyonları (FSB) bir aileyiz kriptografik hash fonksiyonları 2003 yılında Daniel Augot, Matthieu Finiasz ve Nicolas Sendrier tarafından tanıtıldı.^[1]Günümüzde kullanılan diğer şifreleme hash fonksiyonlarının çoğundan farklı olarak, FSB'nin bir dereceye kadar güvenli olduğu kanıtlanabilir. Daha doğrusu, FSB'yi kırmanın en az belirli bir sorunu çözmek kadar zor olduğu kanıtlanabilir. NP tamamlandı bilinen sorun düzenli sendrom kod çözme yani FSB kanıtlanabilir şekilde güvenli. Bilinmemekle birlikte NP tamamlandı sorunlar çözülebilir polinom zamanı, genellikle olmadığı varsayılır.

FSB'nin çeşitli versiyonları önerilmiş ve en sonuncusu SHA-3 kriptografi yarışması ancak ilk turda reddedildi. FSB'nin tüm sürümleri kanıtlanabilir güvenlik iddiasında bulunsa da, bazı ön sürümler sonunda bozuldu. ^[2] FSB'nin en son sürümünün tasarımı bu saldırıyı hesaba katmış ve şu anda bilinen tüm saldırılara karşı güvenli kalmıştır.

Her zamanki gibi, kanıtlanabilir güvenliğin bir bedeli vardır. FSB, geleneksel hash işlevlerinden daha yavaştır ve oldukça fazla bellek kullanır, bu da onu bellek kısıtlı ortamlarda kullanışsız kılar. Ayrıca, FSB'de kullanılan sıkıştırma işlevi, güvenliği garanti etmek için büyük bir çıktı boyutuna ihtiyaç duyar. Bu son sorun, son sürümlerde çıktıyı başka bir sıkıştırma işleviyle basitçe sıkıştırarak çözüldü. Girdap. Bununla birlikte, yazarlar bu son sıkıştırmanın eklenmesinin güvenliği azaltmadığını iddia etse de, resmi bir güvenlik kanıtını imkansız hale getiriyor. ^[3]

Karma işlevinin açıklaması

Bir sıkıştırma işlevi ile başlıyoruz ${ displaystyle phi}$ parametrelerle ${ displaystyle {n, r, w}}$ öyle ki ${ displaystyle n> w}$ ve ${ displaystyle w log (n / w)> r}$. Bu işlev yalnızca uzunluktaki mesajlarda çalışacaktır. ${ displaystyle s = w log (n / w)}$; ${ displaystyle r}$ çıktının boyutu olacaktır. Dahası, istiyoruz ${ displaystyle n, r, w, s}$ ve ${ displaystyle günlük (n / w)}$ doğal sayılar, nerede ${ displaystyle log}$ gösterir ikili logaritma. Nedeni ${ displaystyle w cdot log (n / w)> r}$ istediğimiz bu mu ${ displaystyle phi}$ bir sıkıştırma işlevi olması için girdinin çıktıdan daha büyük olması gerekir. Daha sonra kullanacağız Merkle-Damgård inşaatı alanı rastgele uzunluktaki girişlere genişletmek için.

Bu işlevin temeli (rastgele seçilen) bir ikili dosyadan oluşur ${ displaystyle r kere n}$ matris ${ displaystyle H}$ mesajına göre hareket eden ${ displaystyle n}$ bitler matris çarpımı. Burada kodluyoruz ${ displaystyle w log (n / w)}$vektör olarak bit mesajı ${ displaystyle ( mathbf {F} _ {2}) ^ {n}}$, ${ displaystyle n}$-boyutlu vektör alanı üzerinde alan iki öğeden oluştuğundan, çıktı bir mesaj olacak ${ displaystyle r}$ bitler.

Güvenlik amaçlarının yanı sıra daha hızlı bir hash hızı elde etmek için yalnızca "normal ağırlık kelimeleri kullanmak istiyoruz ${ displaystyle w}$"Matrisimiz için girdi olarak.

Tanımlar

• Bir mesaja denir ağırlık kelimesi ${ displaystyle w}$ ve uzunluk ${ displaystyle n}$ eğer oluşursa ${ displaystyle n}$ bit ve tam olarak ${ displaystyle w}$ bu bitlerden biri.
• Bir ağırlık kelimesi ${ displaystyle w}$ ve uzunluk ${ displaystyle n}$ denir düzenli eğer her aralıkta ${ displaystyle [(i-1) (n / w), ben (n / w))}$ tümü için tam olarak sıfır olmayan bir giriş içerir ${ displaystyle 0$. Daha sezgisel olarak, bu şu anlama gelir: w eşit parçalar varsa, her bölüm tam olarak sıfır olmayan bir giriş içerir.

Sıkıştırma işlevi

Tam olarak var ${ displaystyle (n / w) ^ {w}}$ farklı düzenli kelimeler ${ displaystyle w}$ ve uzunluk ${ displaystyle n}$yani tam olarak ihtiyacımız var ${ displaystyle log ((n / w) ^ {w}) = w log (n / w) = s}$ bu normal kelimeleri kodlamak için veri bitleri. Uzunluktaki bit dizilerinden bir eşleme düzeltiriz ${ displaystyle s}$ normal kelimeler kümesine ${ displaystyle w}$ ve uzunluk ${ displaystyle n}$ ve ardından FSB sıkıştırma işlevi aşağıdaki gibi tanımlanır:

1. girdi: boyutta bir mesaj ${ displaystyle s}$
2. normal uzunlukta kelimeye dönüştür ${ displaystyle n}$ ve ağırlık ${ displaystyle w}$
3. matrisle çarp ${ displaystyle H}$
4. çıktı: boyut karması ${ displaystyle r}$

Bu sürüm genellikle sendroma dayalı sıkıştırma. Çok yavaştır ve pratikte farklı ve daha hızlı bir şekilde yapılır ve sonuçta hızlı sendroma dayalı sıkıştırma. Biz ayrıldık ${ displaystyle H}$ alt matrislere ${ displaystyle H_ {i}}$ boyut ${ displaystyle r kere n / w}$ ve uzunluktaki bit dizilerinden bir bijeksiyon düzeltiyoruz ${ displaystyle w log (n / w)}$ dizi dizisine ${ displaystyle w}$ 1 ile arasındaki sayılar ${ displaystyle n / w}$. Bu, normal uzunluktaki kelimeler kümesine bir eşleştirme ile eşdeğerdir ${ displaystyle n}$ ve ağırlık ${ displaystyle w}$, böyle bir kelimeyi 1 ile 1 arasındaki sayılar dizisi olarak görebildiğimiz için ${ displaystyle n / w}$. Sıkıştırma işlevi aşağıdaki gibi görünür:

1. Giriş: boyutta mesaj ${ displaystyle s}$
2. Dönüştürmek ${ displaystyle s}$ bir dizi ${ displaystyle w}$ sayılar ${ displaystyle s_ {1}, noktalar, s_ {w}}$ 1 ile ${ displaystyle n / w}$
3. Matrislerin karşılık gelen sütunlarını ekleyin ${ displaystyle H_ {i}}$ bir ikili dizi elde etmek için ${ displaystyle r}$
4. Çıktı: boyut karması ${ displaystyle r}$

Şimdi kullanabiliriz Merkle-Damgård inşaatı keyfi uzunluktaki girdileri kabul etmek için sıkıştırma işlevini genelleştirmek.

Sıkıştırma örneği

Durum ve başlatma: Bir mesajı karma hale getirin ${ displaystyle s = 010011}$ kullanma ${ displaystyle 4 times 12}$ matris H
${ displaystyle H = left ({ begin {array} {llllcllllcll} 1 & 0 & 1 & 1 & ~ & 0 & 1 & 0 & 0 & ~ & 1 & 0 & 1 & 1 0 & 1 & 0 & 0 & 0 & ~ & 0 & 1 & 1 & 1 & ~ & 0 & 1 & 0 & 0 & 0 & 1 & 1 & ~ & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & sağ)}$
ayrılan ${ displaystyle w = 3}$ alt bloklar ${ displaystyle H_ {1}}$, ${ displaystyle H_ {2}}$, ${ displaystyle H_ {3}}$.

Algoritma:

1. Girişi böldük ${ displaystyle s}$ içine ${ displaystyle w = 3}$ uzunluk kısımları ${ displaystyle log _ {2} (12/3) = 2}$ ve anlıyoruz ${ displaystyle s_ {1} = 01}$, ${ displaystyle s_ {2} = 00}$, ${ displaystyle s_ {3} = 11}$.
2. Her birini dönüştürüyoruz ${ displaystyle s_ {i}}$ bir tam sayıya girin ve ${ displaystyle s_ {1} = 1}$, ${ displaystyle s_ {2} = 0}$, ${ displaystyle s_ {3} = 3}$.
3. İlk alt matristen ${ displaystyle H_ {1}}$, ikinci alt matristen 2. sütunu seçiyoruz ${ displaystyle H_ {2}}$ sütun 1 ve üçüncü alt matristen sütun 4.
4. Seçilen sütunları ekliyoruz ve sonucu alıyoruz ${ displaystyle r = 0111 oplus 0001 oplus 1001 = 1111}$.

FSB'nin güvenlik kanıtı