Feistel şifresi - Feistel cipher

İçinde kriptografi, bir Feistel şifresi (Ayrıca şöyle bilinir Luby – Rackoff blok şifresi) yapımında kullanılan simetrik bir yapıdır blok şifreleri, adını Almanca doğmuş fizikçi ve kriptograf Horst Feistel kim için çalışırken öncü araştırma yaptı IBM (AMERİKA BİRLEŞİK DEVLETLERİ); aynı zamanda yaygın olarak bir Feistel ağı. Büyük oranda blok şifreleri ABD dahil şemayı kullanmak Veri Şifreleme Standardı, Sovyet / Rus GOST ve daha yeni Balon balığı ve İki balık şifreler. Bir Feistel şifresinde, şifreleme ve şifre çözme çok benzer işlemlerdir ve her ikisi de "yuvarlak işlev" adı verilen bir işlevi sabit sayıda yinelemeli olarak çalıştırmayı içerir.

Tarih

Birçok modern simetrik blok şifresi, Feistel ağlarına dayanmaktadır. Feistel ağları ticari olarak ilk kez IBM'in Lucifer şifre, tasarlayan Horst Feistel ve Don Bakırcı Feistel ağları, ABD Federal Hükümeti'nin DES (Lucifer'e dayalı bir şifre, NSA DES'in diğer bileşenleri gibi, Feistel yapısının yinelemeli doğası, şifreleme sisteminin donanımda uygulanmasını kolaylaştırır (özellikle DES'in tasarımı sırasında mevcut olan donanımda).

Tasarım

Bir Feistel ağı, bir yuvarlak işlev, iki giriş, bir veri bloğu ve bir alt anahtar alan ve veri bloğu ile aynı boyutta bir çıktı veren bir fonksiyon.^[1] Her turda, yuvarlak işlevi şifrelenecek verilerin yarısında çalıştırılır ve çıktısı, verilerin diğer yarısı ile XOR'lanır. Bu, sabit sayıda tekrarlanır ve son çıktı şifrelenmiş verilerdir. Feistel ağlarının diğer şifreleme tasarımlarına kıyasla önemli bir avantajı: ikame-permütasyon ağları yuvarlak işlevin kendisi tersine çevrilemese bile işlemin tamamının tersine çevrilebilir olması garanti edilir (yani, şifrelenmiş verilerin şifresi çözülebilir). Döndürme işlevi, tersine çevrilebilir olarak tasarlanması gerekmediğinden, keyfi olarak karmaşık hale getirilebilir.^[2]^:465 ^[3]^:347 Ayrıca, şifreleme ve şifre çözme işlemler çok benzerdir, hatta bazı durumlarda aynıdır ve yalnızca işlemin tersine çevrilmesini gerektirir. anahtar program. Bu nedenle, böyle bir şifreyi uygulamak için gereken kod veya devrenin boyutu neredeyse yarı yarıya azalır.

Teorik çalışma

Feistel şifrelerinin yapısı ve özellikleri kapsamlı bir şekilde analiz edilmiştir. kriptograflar.

Michael Luby ve Charles Rackoff Feistel şifre yapısını analiz etti ve yuvarlak işlevin kriptografik olarak güvenli olduğunu kanıtladı. sözde rasgele işlevi, K ile_ben çekirdek olarak kullanılırsa, blok şifrelemeyi a yapmak için 3 tur yeterlidir. sözde rasgele permütasyon 4 tur, onu "güçlü" bir sözde rasgele permütasyon yapmak için yeterliyken (bu, alan bir rakip için bile sözde rasgele olarak kalacağı anlamına gelir. kehanet ters permütasyonuna erişim).^[4] Luby ve Rackoff'un bu çok önemli sonucu nedeniyle, Feistel şifrelemelerine bazen Luby – Rackoff blok şifreleri adı verilir.

Daha fazla teorik çalışma, inşaatı bir şekilde genelleştirdi ve güvenlik için daha kesin sınırlar verdi.^[5]^[6]

İnşaat detayları

İzin Vermek ${ displaystyle { rm {F}}}$ yuvarlak işlev ve izin ver ${ displaystyle K_ {0}, K_ {1}, ldots, K_ {n}}$ turların alt anahtarları olun ${ displaystyle 0,1, ldots, n}$ sırasıyla.

Ardından temel işlem şu şekildedir:

Düz metin bloğunu iki eşit parçaya bölün, ( ${ displaystyle L_ {0}}$ , ${ displaystyle R_ {0}}$ )

Her tur için ${ displaystyle i = 0,1, noktalar, n}$ , hesaplamak

{ displaystyle L_ {i + 1} = R_ {i} ,}

{ displaystyle R_ {i + 1} = L_ {i} oplus { rm {F}} (R_ {i}, K_ {i}).}

Nerede ${ displaystyle oplus}$ anlamına geliyor ÖZELVEYA. O halde şifreli metin ${ displaystyle (R_ {n + 1}, L_ {n + 1})}$ .

Bir şifreli metnin şifresini çözme ${ displaystyle (R_ {n + 1}, L_ {n + 1})}$ hesaplama yoluyla gerçekleştirilir ${ displaystyle i = n, n-1, ldots, 0}$

{ displaystyle R_ {i} = L_ {i + 1} ,}

{ displaystyle L_ {i} = R_ {i + 1} oplus operatöradı {F} (L_ {i + 1}, K_ {i}).}

Sonra ${ displaystyle (L_ {0}, R_ {0})}$ yine düz metindir.

Diyagram hem şifreleme hem de şifre çözmeyi göstermektedir. Şifre çözme için alt anahtar sırasının tersine çevrildiğine dikkat edin; bu, şifreleme ve şifre çözme arasındaki tek farktır.

Dengesiz Feistel şifresi

Dengesiz Feistel şifreleri, değiştirilmiş bir yapı kullanır. ${ displaystyle L_ {0}}$ ve ${ displaystyle R_ {0}}$ eşit uzunlukta değildir.^[7] Skipjack şifre böyle bir şifrenin bir örneğidir. Texas Instruments dijital imza aktarıcısı gerçekleştirmek için tescilli dengesiz bir Feistel şifresi kullanır meydan okuma-yanıt kimlik doğrulaması.^[8]

Thorp karıştırma bir tarafın tek bit olduğu, dengesiz bir Feistel şifresinin aşırı bir durumudur. Bu, dengeli bir Feistel şifresinden daha iyi kanıtlanabilir bir güvenliğe sahiptir, ancak daha fazla tur gerektirir.^[9]

Diğer kullanımlar

Feistel yapısı, blok şifrelerinden başka kriptografik algoritmalarda da kullanılır. Örneğin, optimum asimetrik şifreleme dolgusu (OAEP) şeması, belirli şifreli metinleri rastgele hale getirmek için basit bir Feistel ağı kullanır. asimetrik anahtar şifreleme şemaları.

Genelleştirilmiş bir Feistel algoritması, ikinin kuvveti olmayan küçük boyutlu alanlarda güçlü permütasyonlar oluşturmak için kullanılabilir (bkz. biçimi koruyan şifreleme ).^[9]

Tasarım bileşeni olarak Feistel ağları

Şifrenin tamamı bir Feistel şifresi olsun veya olmasın, Feistel benzeri ağlar bir şifrenin tasarımının bir bileşeni olarak kullanılabilir. Örneğin, MISTY1 yuvarlak işlevinde üç yuvarlak Feistel ağı kullanan bir Feistel şifresidir, Skipjack G permütasyonunda bir Feistel ağı kullanan değiştirilmiş bir Feistel şifresidir ve Üç balık (parçası Skein ) Feistel benzeri bir MIX işlevi kullanan, Feistel olmayan bir blok şifresidir.

Feistel şifrelerinin listesi

Feistel veya değiştirilmiş Feistel:

Genelleştirilmiş Feistel:

Ayrıca bakınız

Kriptografi
Kesintisiz şifreleme
İkame-permütasyon ağı
Kaldırma şeması ayrık dalgacık dönüşümü için hemen hemen aynı yapıya sahiptir
Biçimi koruyan şifreleme
Lai – Massey planı

Referanslar

^ Menezes, Alfred J .; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Uygulamalı Kriptografi El Kitabı (Beşinci baskı). s.251. ISBN 978-0849385230.
^ Schneier, Bruce (1996). Uygulamalı Kriptografi. New York: John Wiley & Sons. ISBN 0-471-12845-7.
^ Stinson, Douglas R. (1995). Kriptografi: Teori ve Uygulama. Boca Raton: CRC Basın. ISBN 0-8493-8521-0.
^ Luby, Michael; Rackoff, Charles (Nisan 1988), "Pseudorandom İşlevlerinden Pseudorandom Permütasyonlar Nasıl Yapılandırılır", Bilgi İşlem Üzerine SIAM Dergisi, 17 (2): 373–386, doi:10.1137/0217022, ISSN 0097-5397
^ Patarin, Jacques (Ekim 2003), Boneh, Dan (ed.), "Luby – Rackoff: 2 için 7 Tur Yeterli^{n(1 − ε)} Güvenlik" (PDF), Kriptolojideki Gelişmeler — CRYPTO 2003, Bilgisayar Bilimleri Ders Notları, 2729: 513–529, doi:10.1007 / b11817, ISBN 978-3-540-40674-7, S2CID 20273458, alındı 2009-07-27
^ Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki (1989-08-20). Kanıtlanmış Olarak Güvenli ve Herhangi Bir Kanıtlanmamış Hipoteze Dayanmayan Blok Şifrelerin Oluşturulması Üzerine. Kriptolojideki Gelişmeler - CRYPTO '89 Bildiriler. Bilgisayar Bilimlerinde Ders Notları. 435. sayfa 461–480. doi:10.1007/0-387-34805-0_42. ISBN 978-0-387-97317-3.
^ Schneier, Bruce; Kelsey, John (1996-02-21). Dengesiz Feistel ağları ve blok şifreleme tasarımı. Hızlı Yazılım Şifreleme. Bilgisayar Bilimlerinde Ders Notları. 1039. s. 121–144. doi:10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. Alındı 2017-11-21.
^ Bono, Stephen; Yeşil, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (2005-08-05). "Kriptografik Olarak Etkinleştirilmiş Bir RFID Cihazının Güvenlik Analizi" (PDF). USENIX Güvenlik Sempozyumu Bildirileri. Alındı 2017-11-21.
^ ^a ^b Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). Küçük Bir Etki Alanındaki Mesajlar Nasıl Şifrelenir (PDF). Kriptolojideki Gelişmeler - CRYPTO 2009. Bilgisayar Bilimlerinde Ders Notları. 5677. s. 286–302. doi:10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Alındı 2017-11-21.

Dış bağlantılar

Feistelnetwork - Go'da uygulama

[1] Menezes, Alfred J .; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Uygulamalı Kriptografi El Kitabı (Beşinci baskı). s.251. ISBN 978-0849385230.

[2] Schneier, Bruce (1996). Uygulamalı Kriptografi. New York: John Wiley & Sons. ISBN 0-471-12845-7.

[stinson-3] Stinson, Douglas R. (1995). Kriptografi: Teori ve Uygulama. Boca Raton: CRC Basın. ISBN 0-8493-8521-0.

[pseudorandom-4] Luby, Michael; Rackoff, Charles (Nisan 1988), "Pseudorandom İşlevlerinden Pseudorandom Permütasyonlar Nasıl Yapılandırılır", Bilgi İşlem Üzerine SIAM Dergisi, 17 (2): 373–386, doi:10.1137/0217022, ISSN 0097-5397

[7-rounds-5] Patarin, Jacques (Ekim 2003), Boneh, Dan (ed.), "Luby – Rackoff: 2 için 7 Tur Yeterli^{n(1 − ε)} Güvenlik" (PDF), Kriptolojideki Gelişmeler — CRYPTO 2003, Bilgisayar Bilimleri Ders Notları, 2729: 513–529, doi:10.1007 / b11817, ISBN 978-3-540-40674-7, S2CID 20273458, alındı 2009-07-27

[6] Zheng, Yuliang; Matsumoto, Tsutomu; Imai, Hideki (1989-08-20). Kanıtlanmış Olarak Güvenli ve Herhangi Bir Kanıtlanmamış Hipoteze Dayanmayan Blok Şifrelerin Oluşturulması Üzerine. Kriptolojideki Gelişmeler - CRYPTO '89 Bildiriler. Bilgisayar Bilimlerinde Ders Notları. 435. sayfa 461–480. doi:10.1007/0-387-34805-0_42. ISBN 978-0-387-97317-3.

[7] Schneier, Bruce; Kelsey, John (1996-02-21). Dengesiz Feistel ağları ve blok şifreleme tasarımı. Hızlı Yazılım Şifreleme. Bilgisayar Bilimlerinde Ders Notları. 1039. s. 121–144. doi:10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. Alındı 2017-11-21.

[crypto-rfid-8] Bono, Stephen; Yeşil, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (2005-08-05). "Kriptografik Olarak Etkinleştirilmiş Bir RFID Cihazının Güvenlik Analizi" (PDF). USENIX Güvenlik Sempozyumu Bildirileri. Alındı 2017-11-21.

[thorp-9] Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). Küçük Bir Etki Alanındaki Mesajlar Nasıl Şifrelenir (PDF). Kriptolojideki Gelişmeler - CRYPTO 2009. Bilgisayar Bilimlerinde Ders Notları. 5677. s. 286–302. doi:10.1007/978-3-642-03356-8_17. ISBN 978-3-642-03355-1. Alındı 2017-11-21.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]