高级搜索

具有最小异或数的最大距离可分矩阵的构造

陈少真 张怡帆 任炯炯

引用本文: 陈少真, 张怡帆, 任炯炯. 具有最小异或数的最大距离可分矩阵的构造[J]. 电子与信息学报, 2019, 41(10): 2416-2422. doi: 10.11999/JEIT181113 shu
Citation:  Shaozhen CHEN, Yifan ZHANG, Jiongjiong REN. Constructions of Maximal Distance Separable Matrices with Minimum XOR-counts[J]. Journal of Electronics and Information Technology, 2019, 41(10): 2416-2422. doi: 10.11999/JEIT181113 shu

具有最小异或数的最大距离可分矩阵的构造

    作者简介: 陈少真: 女,1967年生,教授,研究方向为密码学信息安全;
    张怡帆: 女,1993年生,硕士生,研究方向为信息安全;
    任炯炯: 男,1994年生,博士生,研究方向为信息安全
    通讯作者: 张怡帆,zhangyifan_fan@163.com
  • 基金项目: 信息保障技术重点实验室开放基金(KJ-17-002),国家密码发展基金(MMJJ20180203),数学工程与先进计算国家重点实验室开放基金(2018A03)

摘要: 随着物联网等普适计算的发展,传感器、射频识别(RFID)标签等被广泛使用,这些微型设备的计算能力有限,传统的密码算法难以实现,需要硬件效率高的轻量级分组密码来支撑。最大距离可分(MDS)矩阵扩散性能最好,通常被用于构造分组密码扩散层,异或操作次数(XORs)是用来衡量扩散层硬件应用效率的一个指标。该文利用一种能更准确评估硬件效率的XORs计算方法,结合一种特殊结构的矩阵—Toeplitz矩阵,构造XORs较少效率较高的MDS矩阵。利用Toeplitz矩阵的结构特点,改进矩阵元素的约束条件,降低矩阵搜索的计算复杂度,在有限域${\mathbb{F}_{{2^8}}}$上得到了已知XORs最少的4×4MDS矩阵和6×6MDS矩阵,同时还得到XORs等于已知最优结果的5×5MDS矩阵。该文构造的具有最小XORs的MDS Toeplitz矩阵,对轻量级密码算法的设计具有现实意义。

English

    1. [1]

      BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3–72. doi: 10.1007/BF00630563

    2. [2]

      MATSUI M. Linear cryptanalysis method for DES cipher[C]. Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, 1993: 386–397.

    3. [3]

      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.

    4. [4]

      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.

    5. [5]

      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.

    6. [6]

      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.

    7. [7]

      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.

    8. [8]

      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.

    9. [9]

      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.

    10. [10]

      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

    11. [11]

      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

    12. [12]

      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.

    13. [13]

      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.

    14. [14]

      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.

    15. [15]

      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. [1]

      伊文坛, 鲁林真, 陈少真. 轻量级密码算法MIBS的零相关和积分分析. 电子与信息学报, 2016, 38(4): 819-826.

    2. [2]

      崔霆, 金晨辉. 嵌套代替-扩散网络的CLEFIA结构零相关线性逼近的构造. 电子与信息学报, 2012, 34(1): 227-230.

    3. [3]

      苏崇茂, 韦永壮, 马春波. 10轮3D分组密码算法的中间相遇攻击. 电子与信息学报, 2012, 34(3): 694-697.

    4. [4]

      陈韬, 罗兴国, 李校南, 李伟. 一种基于流处理框架的可重构分簇式分组密码处理结构模型. 电子与信息学报, 2014, 36(12): 3027-3034.

    5. [5]

      倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用. 电子与信息学报, 2020, 42(2): 295-306.

    6. [6]

      欧庆于, 罗芳, 叶伟伟, 周学广. 分组密码算法抗故障攻击能力度量方法研究. 电子与信息学报, 2017, 39(5): 1266-1270.

    7. [7]

      谢作敏, 陈少真, 鲁林真. 11轮3D密码的不可能差分攻击. 电子与信息学报, 2014, 36(5): 1215-1220.

    8. [8]

      唐学海, 李超, 王美一, 屈龙江. 3D密码的不可能差分攻击. 电子与信息学报, 2010, 32(10): 2516-2520.

    9. [9]

      罗伟, 郭建胜. Eagle-128算法的相关密钥-矩形攻击. 电子与信息学报, 2014, 36(6): 1520-1524.

    10. [10]

      郭瑞, 金晨辉. 低轮FOX64算法的零相关-积分分析. 电子与信息学报, 2015, 37(2): 417-422.

    11. [11]

      崔霆, 金晨辉. (2n,r,t)_GFNSP结构一类不可能差分对的构造方法. 电子与信息学报, 2011, 33(1): 194-198.

    12. [12]

      李云强, 张小勇, 王爱兰. AES-128 Biclique结构的分布特征. 电子与信息学报, 2016, 38(1): 135-140.

    13. [13]

      肖皇培, 张国基. Rijndael算法的代数方程系统改进. 电子与信息学报, 2008, 30(10): 2459-2463.

    14. [14]

      海昕, 唐学海, 李超. 对Zodiac算法的中间相遇攻击. 电子与信息学报, 2012, 34(9): 2259-2262.

    15. [15]

      郭瑞, 金晨辉. Lai-Massey结构伪随机特性研究. 电子与信息学报, 2014, 36(4): 828-833.

    16. [16]

      刘国强, 金晨辉. 一类动态S盒的构造与差分性质研究. 电子与信息学报, 2014, 36(1): 74-81.

    17. [17]

      谢作敏, 陈少真. 对7轮ARIA-192的不可能差分分析. 电子与信息学报, 2013, 35(10): 2301-2306.

    18. [18]

      沈璇, 孙兵, 刘国强, 李超. 数字视频广播通用加扰算法的不可能差分分析. 电子与信息学报, 2019, 41(1): 46-52.

    19. [19]

      郭建胜, 崔竞一, 罗伟, 刘翼鹏. MD-64算法的相关密钥-矩形攻击. 电子与信息学报, 2015, 37(12): 2845-2851.

    20. [20]

      陈少真, 鲁林真. 对8轮ARIA算法的差分枚举攻击. 电子与信息学报, 2011, 33(7): 1770-1774.

  • 表 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]
    下载: 导出CSV
  • 加载中
计量
  • PDF下载量:  35
  • 文章访问数:  785
  • HTML全文浏览量:  553
文章相关
  • 通讯作者:  张怡帆, zhangyifan_fan@163.com
  • 收稿日期:  2018-12-03
  • 录用日期:  2019-05-31
  • 网络出版日期:  2019-06-12
  • 刊出日期:  2019-10-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章