Gizli Alan Denklemleri - Hidden Field Equations - Wikipedia

Gizli Alan Denklemleri (HFE), Ayrıca şöyle bilinir HFE trapdoor fonksiyonu, bir Genel anahtar şifreleme sistemi hangi tanıtıldı Eurocrypt 1996'da ve öneren (Fransızcada) Jacques Patarin fikrini takiben Matsumoto ve Imai sistemi. Dayanmaktadır polinomlar bitmiş sonlu alanlar ${ displaystyle mathbb {F} _ {q}}$ arasındaki ilişkiyi gizlemek için farklı boyutta Özel anahtar ve Genel anahtar. HFE aslında HFE'nin temel HFE ve kombinatoryal versiyonlarından oluşan bir ailedir. HFE şifreleme sistemi ailesi, çok değişkenli bir sisteme çözüm bulma sorununun sertliğine dayanmaktadır. ikinci dereceden denklemler (sözde MQ sorunu) çünkü özel afin dönüşümler uzantı alanını ve özel alanı gizlemek için polinomlar. Gizli Alan Denklemleri ayrıca dijital imza şemaları oluşturmak için kullanılmıştır, örn. Quartz ve Sflash.^[1]

Matematiksel arka plan

Gizli Alan Denklemlerinin nasıl çalıştığını anlamanın temel kavramlarından biri, bunu iki uzantı alanı için görmektir. ${ displaystyle mathbb {F} _ {q ^ {n}}}$ ${ displaystyle mathbb {F} _ {q ^ {m}}}$ aynı temel alan üzerinde ${ displaystyle mathbb {F} _ {q}}$ bir sistemi yorumlayabilir ${ displaystyle m}$ çok değişkenli polinomlar içinde ${ displaystyle n}$ değişkenler bitti ${ displaystyle mathbb {F} _ {q}}$ işlev olarak ${ displaystyle mathbb {F} _ {q ^ {n}} - mathbb {F} _ {q ^ {m}}}$ uygun bir temel nın-nin ${ displaystyle mathbb {F} _ {q ^ {n}}}$ bitmiş ${ displaystyle mathbb {F} _ {q}}$. Hemen hemen tüm uygulamalarda polinomlar ikinci dereceden, yani 2. dereceye sahiptirler.^[2] En basit türden polinomlarla, yani monomlarla başlıyoruz ve nasıl ikinci dereceden denklem sistemlerine yol açtıklarını gösteriyoruz.

Bir düşünün sonlu alan ${ displaystyle mathbb {F} _ {q}}$, nerede ${ displaystyle q}$ 2'nin kuvveti ve bir uzantı alanıdır ${ displaystyle K}$. İzin Vermek ${ displaystyle 0$ öyle ki ${ displaystyle h = q ^ { theta} +1}$ bazı ${ displaystyle theta}$ ve gcd${ displaystyle (h, q ^ {n} -1) = 1}$. Kondisyon gcd${ displaystyle (h, q ^ {n} -1) = 1}$ haritanın ${ displaystyle u ila u ^ {h}}$ açık ${ displaystyle K}$ bire bir ve bunun tersi harita ${ displaystyle u ila u ^ {h '}}$ nerede ${ displaystyle h '}$ çarpımsal tersidir ${ displaystyle h { bmod {q}} ^ {n} -1}$.

Rastgele bir eleman al ${ displaystyle u in mathbb {F} _ {q ^ {n}}}$. Tanımlamak ${ displaystyle w in mathbb {F} _ {q ^ {n}}}$ tarafından

${ displaystyle w = u ^ {h} = u ^ {q ^ { theta}} u (1)}$

İzin Vermek ${ displaystyle beta _ {1}, ..., beta _ {n}}$ biri olmak temel nın-nin ${ displaystyle K}$ olarak ${ displaystyle mathbb {F} _ {q}}$ vektör alanı. Temsil ediyoruz ${ displaystyle u}$ temeli ile ilgili olarak ${ displaystyle u = (u_ {1}, ..., u_ {n})}$ ve ${ displaystyle w = (w_ {1}, ..., w_ {n})}$. İzin Vermek ${ displaystyle A ^ {(k)} = {a_ {ij} ^ {(k)}}}$ doğrusal dönüşümün matrisi olun ${ displaystyle u ila u ^ {q ^ {k}}}$ temele göre ${ displaystyle beta _ {1}, ..., beta _ {n}}$, yani öyle ki

${ displaystyle beta _ {i} ^ {q ^ {k}} = sum _ {j = 1} ^ {n} a_ {ij} ^ {k} beta _ {j}, a_ {ij } ^ {k} in mathbb {F} _ {q}}$

için ${ displaystyle 1 leq i, k leq n}$. Ek olarak, temel unsurların tüm ürünlerini temel açısından yazın, yani:

${ displaystyle beta _ {i} beta _ {j} = toplamı _ {l = 1} ^ {n} m_ {ijl} beta _ {l}, m_ {ijl} in mathbb { F} _ {q}}$

her biri için ${ displaystyle 1 leq i, j leq n}$. Sistemi ${ displaystyle n}$ açık olan denklemler ${ displaystyle w_ {i}}$ ve ikinci dereceden ${ displaystyle u_ {j}}$ (1) 'i genişleterek ve sıfıra eşitleyerek elde edilebilir. ${ displaystyle beta _ {i}}$.

İki gizli afin dönüşüm seçin ${ displaystyle S}$ ve ${ displaystyle T}$ , yani iki ters çevrilebilir ${ displaystyle n kere n}$ matrisler ${ displaystyle M_ {S} = {S_ {ij} }}$ ve ${ displaystyle M_ {T} = {T_ {ij} }}$ girişlerle ${ displaystyle mathbb {F} _ {q}}$ ve iki vektör ${ displaystyle v_ {S}}$ ve ${ displaystyle v_ {T}}$ uzunluk ${ displaystyle n}$ bitmiş ${ displaystyle mathbb {F} _ {q}}$ ve tanımla ${ displaystyle x}$ ve ${ displaystyle y}$ üzerinden:

${ displaystyle u = Sx = M_ {S} x + v_ {S} w = Ty = M_ {T} y + v_ {T} (2)}$

(2) 'deki afin ilişkileri kullanarak ${ displaystyle u_ {j}, w_ {i}}$ ile ${ displaystyle x_ {k}, y_ {l}}$sistemi ${ displaystyle n}$ denklemler doğrusal içinde ${ displaystyle y_ {l}}$ ve 2. dereceden ${ displaystyle x_ {k}}$. Uygulanıyor lineer Cebir verecek ${ displaystyle n}$ açık denklemler, her biri için bir ${ displaystyle y_ {l}}$ 2. derecenin polinomları olarak ${ displaystyle x_ {k}}$.^[3]

Çok değişkenli şifreleme sistemi

HFE ailesinin bunu çok değişkenli olarak kullanma temel fikri şifreleme sistemi gizli anahtarı bir polinom ${ displaystyle P}$ bilinmeyen bir yerde ${ displaystyle x}$ biraz fazla sonlu alan ${ displaystyle mathbb {F} _ {q ^ {n}}}$ (normalde değer ${ displaystyle q = 2}$ kullanıldı). Bu polinom kolayca ters çevrilebilir ${ displaystyle mathbb {F} _ {q ^ {n}}}$, yani denklem için herhangi bir çözüm bulmak mümkündür ${ displaystyle P (x) = y}$ böyle bir çözüm var olduğunda. Gizli dönüşüm de şifre çözme ve / veya imza bu ters çevirmeye dayanmaktadır. Yukarıda açıklandığı gibi ${ displaystyle P}$ bir sistemle tanımlanabilir ${ displaystyle n}$ denklemler ${ displaystyle (p_ {1}, ..., p_ {n})}$ sabit bir temel kullanarak. İnşa etmek şifreleme sistemi polinom ${ displaystyle (p_ {1}, ..., p_ {n})}$ kamusal bilgi orijinal yapıyı gizleyecek ve tersine dönmeyi önleyecek şekilde dönüştürülmelidir. Bu, görüntüleyerek yapılır. sonlu alanlar ${ displaystyle mathbb {F} _ {q ^ {n}}}$ olarak vektör alanı bitmiş ${ displaystyle mathbb {F} _ {q}}$ ve iki doğrusal seçerek afin dönüşümler ${ displaystyle S}$ ve ${ displaystyle T}$. Üçlü ${ displaystyle (S, P, T)}$ özel anahtarı oluşturur. Özel polinom ${ displaystyle P}$ üzerinde tanımlandı ${ displaystyle mathbb {F} _ {q ^ {n}}}$.^[1][4] Genel anahtar ${ displaystyle (p_ {1}, ..., p_ {n})}$. MQ-trapdoor için şema aşağıdadır ${ displaystyle (S, P, T)}$ HFE'de

${ displaystyle { text {input}} x ila x = (x_ {1}, ..., x_ {n}) { taşma {{ text {gizli}}: S} { to}} x '{ taşan {{ text {gizli}}: P} { to}} y' { taşan {{ text {gizli}}: T} { to}} { text {çıktı}} y}$

HFE polinomu

Özel polinom ${ displaystyle P}$ derece ile ${ displaystyle d}$ bitmiş ${ displaystyle mathbb {F} _ {q ^ {n}}}$ bir unsurdur ${ displaystyle mathbb {F} _ {q ^ {n}} [x]}$. Şartları polinom ${ displaystyle P}$ en fazla var ikinci dereceden şartlar bitti ${ displaystyle mathbb {F} _ {q}}$ o zaman genel polinomu küçük tutacaktır.^[1] Durumda ${ displaystyle P}$ formun tek terimlilerinden oluşur ${ displaystyle x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}$yani 2 kuvvet ile ${ displaystyle q}$ üssünde, temel versiyonu HFEyani ${ displaystyle P}$ olarak seçilir

${ displaystyle P (x) = toplamı c_ {i} x ^ {q ^ {s_ {i}} + q ^ {t_ {i}}}}$

Derece ${ displaystyle d}$ of polinom aynı zamanda güvenlik parametresi olarak da bilinir ve değeri ne kadar büyük olursa güvenlik için o kadar iyidir, çünkü sonuçta ortaya çıkan ikinci dereceden denklemler seti rastgele seçilen bir ikinci dereceden denklemler setine benzer. Diğer tarafta büyük ${ displaystyle d}$ deşifreyi yavaşlatır. Dan beri ${ displaystyle P}$ bir polinom en fazla derece ${ displaystyle d}$ tersi ${ displaystyle P}$ile gösterilir ${ displaystyle P ^ {- 1}}$ hesaplanabilir ${ displaystyle d ^ {2} ( ln d) ^ {O (1)} n ^ {2} mathbb {F} _ {q}}$ operasyonlar.^[5]

Şifreleme ve şifre çözme

Genel anahtar, ${ displaystyle n}$ çok değişkenli polinomlar ${ displaystyle (p_ {1}, ..., p_ {n})}$ bitmiş ${ displaystyle mathbb {F} _ {q}}$. Bu nedenle mesajın aktarılması gerekir ${ displaystyle M}$ itibaren ${ displaystyle mathbb {F} _ {q ^ {n}} - mathbb {F} _ {q} ^ {n}}$ şifrelemek için, yani bunu varsayıyoruz ${ displaystyle M}$ bir vektör ${ displaystyle (x_ {1}, ..., x_ {n}) in mathbb {F} _ {q} ^ {n}}$. Mesajı şifrelemek için ${ displaystyle M}$ her birini değerlendiririz ${ displaystyle p_ {i}}$ -de ${ displaystyle (x_ {1}, ..., x_ {n})}$. Şifreli metin ${ displaystyle (p_ {1} (x_ {1}, ..., x_ {n}), p_ {2} (x_ {1}, ..., x_ {n}), ..., p_ { n} (x_ {1}, ..., x_ {n})) in mathbb {F} _ {q} ^ {n}}$.

Şifre çözmeyi anlamak için şifrelemeyi şu terimlerle ifade edelim: ${ displaystyle S, T, P}$. Bunların olduğunu unutmayın değil gönderen tarafından kullanılabilir. Değerlendirerek ${ displaystyle p_ {i}}$ ilk uyguladığımız mesajda ${ displaystyle S}$, sonuçlanan ${ displaystyle x '}$. Bu noktada ${ displaystyle x '}$ transfer edildi ${ displaystyle mathbb {F} _ {q ^ {n}} - mathbb {F} _ {q ^ {n}}}$ böylece özel polinomu uygulayabiliriz ${ displaystyle P}$ hangisi bitti ${ displaystyle mathbb {F} _ {q ^ {n}}}$ ve bu sonuç şu şekilde gösterilir: ${ displaystyle y ' in mathbb {F} _ {q ^ {n}}}$. Bir kere daha, ${ displaystyle y '}$ vektöre aktarılır ${ displaystyle (y_ {1} ', ..., y_ {n}')}$ ve dönüşüm ${ displaystyle T}$ uygulanır ve nihai çıktı ${ displaystyle y in mathbb {F} _ {q ^ {n}}}$ -dan üretilmiştir ${ displaystyle (y_ {1}, ..., y_ {n}) in mathbb {F} _ {q} ^ {n}}$.

Şifresini çözmek için ${ displaystyle y}$yukarıdaki adımlar ters sırada yapılır. Bu, özel anahtarın ${ displaystyle (S, P, T)}$ bilinen. Deşifre etmedeki en önemli adım, ${ displaystyle S}$ ve ${ displaystyle T}$ daha çok çözümün hesaplamaları ${ displaystyle P (x ') = y'}$. Dan beri ${ displaystyle P}$ bir eşleştirme gerekli değildir, bu tersine çevirme için birden fazla çözüm bulunabilir (en fazla d farklı çözüm vardır ${ displaystyle X '= (x_ {1}', ..., x_ {d} ') in mathbb {F} _ {q ^ {n}}}$ dan beri ${ displaystyle P}$ d) derecesinde bir polinomdur. Fazlalık olarak belirtildi ${ displaystyle r}$ mesaja ilk adımda eklenir ${ displaystyle M}$ doğru olanı seçmek için ${ displaystyle M}$ çözüm kümesinden ${ displaystyle X '}$.^[1][3][6] Aşağıdaki şema, şifreleme için temel HFE'yi göstermektedir.

${ displaystyle M { taşma {+ r} { to}} x { taşma {{ text {gizli}}: S} { to}} x '{ taşma {{ text {gizli}}: P} { to}} y '{ taşıyor {{ text {gizli}}: T} { to}} y}$

HFE varyasyonları

Gizli Alan Denklemlerinin dört temel varyasyonu vardır: +, -, v ve f ve bunları çeşitli şekillerde birleştirmek mümkündür. Temel ilke şudur:

01. + işaret, genel denklemlerin bazı rastgele denklemlerle doğrusal olarak karıştırılmasından oluşur.

02. - işaret nedeniyle Adi Shamir ve halka açık denklemlerin fazlalık 'r'yi kaldırmayı amaçlamaktadır.

03. f işaret bazılarını düzeltmekten oluşur ${ displaystyle f}$ genel anahtarın girdi değişkenleri.

04. v işareti bir yapı olarak tanımlanır ve bazen oldukça karmaşıktır, öyle ki fonksiyonun tersi ancak sirke değişkenleri adı verilen değişkenlerin bazı v'leri sabitse bulunabilir. Bu fikir Jacques Patarin'den kaynaklanmaktadır.

Yukarıdaki işlemler, işlevin tuzak kapısı çözülebilirliğini bir dereceye kadar korur.

HFE- ve HFEv, imza oluşturma sürecini yavaşlatmayı önledikleri ve aynı zamanda HFE'nin genel güvenliğini artırdıkları için imza şemalarında çok kullanışlıdır. şifreleme hem HFE- hem de HFEv, oldukça yavaş şifre çözme bu nedenle ne çok fazla denklem kaldırılamaz (HFE-) ne de çok fazla değişken eklenmemelidir (HFEv). Quartz elde etmek için hem HFE- hem de HFEv kullanılmıştır.

Şifreleme için, durum HFE + ile daha iyidir çünkü şifre çözme işlem aynı süreyi alır, ancak ortak anahtarın değişkenlerden daha fazla denklemi vardır.^[1][2]

HFE saldırıları

HFE'ye iki ünlü saldırı vardır:

Özel Anahtarı Kurtar (Shamir -Kipnis): Bu saldırının kilit noktası, özel anahtarı uzantı alanı üzerinde seyrek tek değişkenli polinomlar olarak kurtarmaktır. ${ displaystyle mathbb {F} _ {q ^ {n}}}$. Saldırı yalnızca temel HFE için çalışır ve tüm varyasyonları için başarısız olur.

Hızlı Gröbner Üsleri (Faugère): Fikir Faugère saldırıları, hesaplamak için hızlı algoritma kullanmaktır. Gröbner temeli polinom denklem sisteminin. Faugère, 2002'de 96 saatte ve 2003'te Faugère ve Joux HFE'nin güvenliği için birlikte çalıştı.^[1]

Referanslar

• Nicolas T. Courtois, Magnus Daum ve Patrick Felke, HFE, HFEv- ve Quartz'ın Güvenliği Üzerine
• Andrey Sidorenko, Gizli Alan Denklemleri, EIDMA Semineri 2004 Technische Universiteit Eindhoven
• Yvo G. Desmet, Açık Anahtarlı Şifreleme-PKC 2003, ISBN  3-540-00324-X