Blok şifrelerde kullanılan ikili ve MDS matrisler için yeni tasarım teknikleri
New design techniques for binary and MDS matrices used in block ciphers
Yazar: GÖKHAN TUNCAY
Danışman: PROF. DR. MUHARREM TOLGA SAKALLI
Trakya Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Blok şifreler = Block ciphers

Özet:
Maksimum Uzaklıkla Ayrılabilen (MDS) matrisler, maksimum difüzyon sağladıkları ve maksimum dal sayısına sahip oldukları için blok şifreleme ve özet fonksiyonları gibi kriptografik ilkellerin tasarımında difüzyon katmanlarının temel bileşeni olarak kullanılmaktadır. Ancak bu matrislerin uygulamaları genellikle yüksek maliyet gerektirmektedir.
Bu tez çalışmasında, F_(2^m) cismi üzerinde 4x4 boyutlu involutif MDS matrislerin tümünü oluşturmak için doğrudan tasarım ve arama tabanlı yöntemleri birleştiren yeni bir melez teknik önerilmektedir. Önerilen teknik, n, bir kaba kuvvet araması ile elde edilebilecek F_(2^m) cismi üzerinde tanımlı tüm 4x4 boyutlarındaki MDS matrislerin sayısını göstermek üzere, arama uzayı karmaşıklığını √n düzeyinde azaltmaktadır. Dolayısıyla, F_(2^3) ve F_(2^4) cisimleri üzerinde 4x4 boyutlu involutif MDS matrislerin tamamı oluşturulabilmektedir. Bu bağlamda, donanım uygulama maliyetini hesaplamak için kullanılan XOR sayısı metriği açısından, F_(2^3) ve F_(2^4) cisimleri üzerinde bilinen en iyi involutif/involutif olmayan MDS matrisler oluşturulmaktadır. Ardından, elde edilen bu MDS matrislere bir global optimizasyon tekniği olan Boyar-Peralta algoritması uygulanmaktadır. Ayrıca önerilen teknik, F_(2^3) ve F_(2^4) cisimleri üzerinde üretilen 4x4 boyutlu involutif MDS/Almost-MDS matrislerden yararlanarak 12x12 ve 16x16 boyutlu MDBL matrislerin tasarımında da kullanılabilmektedir. Son olarak, yeni bir Hadamard matris özelliği tanımlanmaktadır. Bu özellik, Hadamard matrislerin aslında tüm 2^kx2^k (k>1) boyutlu involutif MDS matrislerin küçük bir miktarını oluşturmak için kullanılabilen temsili bir matris formu olduğunu göstermektedir.

Abstract:
Maximum Distance Separable (MDS) matrices are used as the core component of diffusion layers in the design of cryptographic primitives such as block ciphers and hash functions because they provide the maximum diffusion and have maximum branch number. However, the implementations of these matrices require high-cost, generally. 
In this thesis, we propose a newhybrid technique combining the direct construction methods and the search-based methods to generate all 4x4 involutory MDS matrices over F_(2^m). The proposed technique reduces the search space complexity at the level of √n, where n represents the number of all 4x4 matrices needed in the case of a brute-force search over F_(2^m). Therefore, this allows us to generate all involutory MDS matrices over F_(2^3) and F_(2^4). In this regard, the lightest involutory/non-involutory MDS matrices known over F_(2^3) and F_(2^4) in terms of XOR count metric are generated to estimate hardware implementation cost. Afterward, the Boyar-Peralta algorithm, a global optimization technique, was applied to these MDS matrices obtained. Moreover, the proposed technique can also be used to construct 12x12 and 16x16 MDBL matrices with 4x4 involutory MDS/Almost-MDS matrices generated over F_(2^3) and F_(2^4). Finally, a new property of Hadamard matrix is defined. This property indicates that Hadamard matrices are, in fact, a representative matrix form that can be used to generate a small amount of all 2^kx2^k (k>1) involutory MDS matrices.