Constructions of Maximal Distance Separable Matrices with Minimum XOR-counts
-
摘要: 随着物联网等普适计算的发展,传感器、射频识别(RFID)标签等被广泛使用,这些微型设备的计算能力有限,传统的密码算法难以实现,需要硬件效率高的轻量级分组密码来支撑。最大距离可分(MDS)矩阵扩散性能最好,通常被用于构造分组密码扩散层,异或操作次数(XORs)是用来衡量扩散层硬件应用效率的一个指标。该文利用一种能更准确评估硬件效率的XORs计算方法,结合一种特殊结构的矩阵—Toeplitz矩阵,构造XORs较少效率较高的MDS矩阵。利用Toeplitz矩阵的结构特点,改进矩阵元素的约束条件,降低矩阵搜索的计算复杂度,在有限域
${\mathbb{F}_{{2^8}}}$ 上得到了已知XORs最少的4×4MDS矩阵和6×6MDS矩阵,同时还得到XORs等于已知最优结果的5×5MDS矩阵。该文构造的具有最小XORs的MDS Toeplitz矩阵,对轻量级密码算法的设计具有现实意义。-
关键词:
- 分组密码 /
- 轻量级扩散层 /
- 最大距离可分矩阵 /
- 异或数 /
- Toeplitz矩阵
Abstract: With the development of the internet of things, small-scale communication devices such as wireless sensors and the Radio Frequency IDentification(RFID) tags are widely used, these micro-devices have limited computing power, so that the traditional cryptographic algorithms are difficult to implement on these devices. How to construct a high-efficiency diffusion layer becomes an urgent problem. With the best diffusion property, the Maximal Distance Separable (MDS) matrix is often used to construct the diffusion layer of block ciphers. The number of XOR operations (XORs) is an indicator of the efficiency of hardware applications. Combined with the XORs calculation method which can evaluate hardware efficiency more accurately and a matrix with special structure——Toeplitz matrix, efficient MDS matrices with less XORs can be constructed. Using the structural characteristics of the Toeplitz matrix, the constraints of matrix elements are improved, and the complexity of matrices searching is reduced. The 4×4 MDS matrices and the 6×6 MDS matrices with the least XORs in the finite field${\mathbb{F}_{{2^8}}}$ are obtained, and the 5×5 MDS matrices with the XORs which are equal to the known optimal results are obtained too. The proposed method of constructing MDS Toeplitz matrices with the least XORs has significance on the design of lightweight cryptographic algorithms. -
表 1 本文构造结果与已知结果对比
矩阵维度 不可约多项式 矩阵实例${\text{M}}$ $C\left( {\text{M}} \right)$ 文献 $4 \times 4$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Toep}}\left( {1,1,{x^2},1,{x^{ - 1}},x,{x^2}} \right)$ 20 本文 $4 \times 4$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Circ}}\left( {1,1,x,{x^{ - 2}}} \right)$ 24 文献[12] $4 \times 4$ ${x^8} + {x^7} + {x^6} + x + 1$ ${\rm{Toep}}\left( {1,1,x,{x^{ - 1}},{x^{ - 2}},1,{x^{ - 1}}} \right)$ 27 文献[12] $4 \times 4$ ${x^8} + {x^7} + {x^6} + x + 1$ ${\rm{Left - Circ}}\left( {1,1,x,{x^{ - 2}}} \right)$ 32 文献[14] $4 \times 4$ ${x^8} + {x^7} + {x^6} + x + 1$ ${\rm{Had}}\left( {1,x,{x^2},{x^{ - 2}}} \right)$ 52 文献[12] $5 \times 5$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Toep}}\left( {1,{x^2},1,{x^{ - 1}},{x^{ - 1}},{x^{ - 1}},{x^{ - 1}},1,{x^2}} \right)$ 40 本文 $5 \times 5$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Circ}}\left( {1,1,x,{x^{ - 2}},x} \right)$ 40 文献[12] $5 \times 5$ ${x^8} + {x^7} + {x^6} + x + 1$ ${\rm{Left - Circ}}\left( {1,1,x,{x^{ - 2}},x} \right)$ 55 文献[14] $6 \times 6$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Toep}}\left( {1,x,x,1,{x^{ - 2}},{x^2},{x^{ - 2}},{x^2},{x^{ - 2}},1,x} \right)$ 80 本文 $6 \times 6$ ${x^8} + {x^6} + {x^5} + x + 1$ ${\rm{Circ}}\left( {1,x,{x^{ - 1}},{x^{ - 2}},1,{x^3}} \right)$ 84 文献[12] $6 \times 6$ ${x^8} + {x^7} + {x^6} + x + 1$ ${\rm{Left - Circ}}\left( {1,x,{x^{ - 1}},{x^{ - 2}},1,{x^3}} \right)$ 108 文献[14] -
BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3–72. doi: 10.1007/BF00630563 MATSUI M. Linear cryptanalysis method for DES cipher[C]. Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 1993: 386–397. SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128-bit blockcipher CLEFIA (extended abstract)[C]. The 14th International Workshop on Fast Software Encryption, Luxembourg, Luxembourg, 2007: 181–195. BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. The 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, Austria, 2007: 450–466. GUO Jian, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]. The 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 326–341. YANG Gangqiang, ZHU Bo, SUDER V, et al. The SIMECK family of lightweight block ciphers[C]. The 17th International Workshop on Cryptographic Hardware and Embedded Systems, Saint-Malo, France, 2015: 307–329. SIM S M, KHOO K, OGGIER F, et al. Lightweight MDS involution matrices[C]. The 22nd International Workshop on Fast Software Encryption, Istanbul, Turkey, 2015: 471–493. LIU Meicheng and SIM S M. Lightweight MDS generalized circulant matrices[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 101–120. LI Yongqiang and WANG Mingsheng. On the construction of lightweight circulant involutory MDS matrices[C]. The 23rd International Conference on Fast Software Encryption, Bochum, Germany, 2016: 121–139. SARKAR S and SYED H. Lightweight diffusion layer: Importance of Toeplitz matrices[J]. IACR Transactions on Symmetric Cryptology, 2016, 2016(1): 95–113. doi: 10.13154/tosc.v2016.i1.95-113 JEAN J, PEYRIN T, SIM S M, et al. Optimizing implementations of lightweight building blocks[J]. IACR Transactions on Symmetric Cryptology, 2017, 2017(4): 130–168. doi: 10.13154/tosc.v2017.i4.130-168 BEIERLE C, KRANZ T, and LEANDER G. Lightweight multiplication in GF(2n) with applications to MDS matrices[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 625–653. SARKAR S and SYED H. Analysis of Toeplitz MDS matrices[C]. The 22nd Australasian Conference on Information Security and Privacy, Auckland, New Zealand, 2017: 3–18. KHOO K, PEYRIN T, POSCHMANN A Y, et al. FOAM: Searching for hardware-optimal SPN structures and components with a fair comparison[C]. The 16th International Workshop on Cryptographic Hardware and Embedded Systems, Busan, South Korea, 2014: 433–450. JUNOD P and VAUDENAY S. Perfect diffusion primitives for block ciphers[C]. The 11th International Workshop on Selected Areas in Cryptography, Waterloo, Canada, 2004: 84–99. -
表(1)
计量
- 文章访问数: 2574
- HTML全文浏览量: 1160
- PDF下载量: 88
- 被引次数: 0