Doğrusal kriptanaliz - Linear cryptanalysis - Wikipedia

İçinde kriptografi, doğrusal kriptanaliz genel bir şeklidir kriptanaliz bulmaya dayalı afin a eylemine yaklaşımlar şifre. Saldırılar geliştirildi blok şifreleri ve akış şifreleri. Doğrusal kriptanaliz, blok şifrelere yönelik en yaygın kullanılan iki saldırıdan biridir; diğeri diferansiyel kriptanaliz.

Keşif, Mitsuru Matsui tekniği ilk uygulayan FEAL şifre (Matsui ve Yamagishi, 1992).^[1] Daha sonra Matsui, Veri Şifreleme Standardı (DES), sonunda açık toplulukta bildirilen şifrenin ilk deneysel kriptanalizine yol açtı (Matsui, 1993; 1994).^[2]^[3] DES saldırısı genellikle pratik değildir ve 2⁴⁷ bilinen düz metinler.^[3]

Saldırı için, çoklu doğrusal yaklaşımlar kullanmak veya doğrusal olmayan ifadeleri dahil etmek de dahil olmak üzere, genelleştirilmiş bir kriptanaliz bölümleme. Doğrusal kriptanalize karşı güvenlik kanıtı genellikle yeni şifre tasarımlarından beklenir.

Genel Bakış

Doğrusal kriptanalizin iki bölümü vardır. Birincisi, düz metin, şifreli metin ve yüksek önyargıya sahip anahtar bitleri ilişkilendiren doğrusal denklemler oluşturmaktır; yani, tutma olasılıkları (değişkenlerinin tüm olası değerlerinin uzayı boyunca) 0 veya 1'e olabildiğince yakın olmasıdır. İkincisi, bu doğrusal denklemleri, anahtar bitlerini türetmek için bilinen şifresiz metin-şifreli metin çiftleri ile birlikte kullanmaktır.

Doğrusal denklemler oluşturmak

Doğrusal kriptanalizin amaçları için doğrusal bir denklem, dışlayıcı veya (XOR) işlemiyle birleştirilmiş ikili değişkenlerden oluşan iki ifadenin eşitliğini ifade eder. Örneğin, varsayımsal bir şifreden alınan aşağıdaki denklem, birinci ve üçüncü düz metin bitlerinin XOR toplamını belirtir (bir blok şifresinin bloğunda olduğu gibi) ve birinci şifreli metin biti, anahtarın ikinci bitine eşittir:

${ displaystyle P_ {1} oplus P_ {3} oplus C_ {1} = K_ {2}.}$

İdeal bir şifrede, düz metin, şifreli metin ve anahtar bitleri ile ilgili herhangi bir doğrusal denklem 1/2 olasılıkla tutulur. Doğrusal kriptanalizde ele alınan denklemler olasılık açısından değişeceğinden, daha doğru bir şekilde doğrusal olarak adlandırılırlar. yaklaşımlar.

Yaklaşımlar oluşturma prosedürü her şifre için farklıdır. En temel blok şifreleme türünde, bir ikame-permütasyon ağı analiz, öncelikle S kutuları, şifrenin tek doğrusal olmayan kısmı (yani bir S-kutusunun çalışması doğrusal bir denklemde kodlanamaz). Yeterince küçük S kutuları için, S-box'ın giriş ve çıkış bitleriyle ilgili olası her doğrusal denklemi numaralandırmak, önyargılarını hesaplamak ve en iyilerini seçmek mümkündür. Daha sonra S-kutuları için doğrusal yaklaşımlar, tüm şifre için doğrusal yaklaşımlara ulaşmak için şifrenin permütasyon ve anahtar karıştırma gibi diğer eylemleriyle birleştirilmelidir. istiflenmiş lemma bu kombinasyon adımı için kullanışlı bir araçtır. Doğrusal yaklaşımları yinelemeli olarak geliştirmek için teknikler de vardır (Matsui 1994).

Anahtar bitlerinin türetilmesi

Formun doğrusal bir yaklaşımını elde ettikten sonra:

${ displaystyle P_ {i_ {1}} oplus P_ {i_ {2}} oplus cdots oplus C_ {j_ {1}} oplus C_ {j_ {2}} oplus cdots = K_ {k_ { 1}} oplus K_ {k_ {2}} oplus cdots}$

daha sonra, yaklaşımda yer alan anahtar bitlerin değerlerini tahmin etmek için bilinen şifresiz metin-şifreli metin çiftlerini kullanarak basit bir algoritma (Matsui's Algorithm 2) uygulayabiliriz.

Sağ taraftaki anahtar bitlerinin her bir değer kümesi için (bir kısmi anahtar), yaklaşıklığın bilinen tüm şifresiz metin-şifreli metin çiftleri üzerinde kaç kez doğru olduğunu sayın; bu sayıyı ara T. Kısmi anahtar T en iyisine sahip mutlak fark Düz metin-şifreli metin çiftlerinin sayısının yarısından itibaren, bu anahtar bitler için en olası değerler kümesi olarak belirlenir. Bunun nedeni, doğru kısmi anahtarın yaklaşımın yüksek bir sapma ile tutulmasına neden olacağı varsayılmasıdır. Olasılığın kendisinin büyüklüğünün aksine burada önyargının büyüklüğü önemlidir.

Bu prosedür, bilinmeyen anahtar bitlerinin sayısı saldırıya uğrayabilecek kadar düşük olana kadar, anahtar bitlerinin değerlerinde tahminler elde ederek diğer doğrusal yaklaşımlarla tekrarlanabilir. kaba kuvvet.

Ayrıca bakınız

Referanslar

^ Matsui, M. & Yamagishi, A. "FEAL şifresinin bilinen düz metin saldırısı için yeni bir yöntem". Kriptolojideki Gelişmeler - EUROCRYPT 1992.
^ Matsui, M. "Veri şifreleme standardının ilk deneysel kriptanalizi". Kriptolojideki Gelişmeler - KRİPTO 1994.
^ ^a ^b Matsui, M. "DES şifrelemesi için doğrusal kriptanaliz yöntemi" (PDF). Kriptolojideki Gelişmeler - EUROCRYPT 1993. Arşivlenen orijinal (PDF) 2007-09-26 tarihinde. Alındı 2007-02-22.

Dış bağlantılar

[FEAL_linear-1] Matsui, M. & Yamagishi, A. "FEAL şifresinin bilinen düz metin saldırısı için yeni bir yöntem". Kriptolojideki Gelişmeler - EUROCRYPT 1992.

[experimental_cryptanalysis-2] Matsui, M. "Veri şifreleme standardının ilk deneysel kriptanalizi". Kriptolojideki Gelişmeler - KRİPTO 1994.

[DES_linear-3] Matsui, M. "DES şifrelemesi için doğrusal kriptanaliz yöntemi" (PDF). Kriptolojideki Gelişmeler - EUROCRYPT 1993. Arşivlenen orijinal (PDF) 2007-09-26 tarihinde. Alındı 2007-02-22.

[1]

[2]

[3]