模m加法的一类线性逼近关系研究

doi:10.3969/j.issn.0372-2112.2015.11.009

电子学报 ›› 2015, Vol. 43 ›› Issue (11): 2194-2199.DOI: 10.3969/j.issn.0372-2112.2015.11.009

模m加法的一类线性逼近关系研究

王健, 戚文峰, 郑群雄

解放军信息工程大学数学工程与先进计算国家重点实验室, 河南郑州 450001

收稿日期:2014-05-04 修回日期:2015-03-05 出版日期:2015-11-25
- 通讯作者:
- 王健
- 作者简介:
- 戚文峰 男,1963年生,教授,博士生导师,研究方向为有限域、密码学.E-mail:wenfeng.qi@263.net;郑群雄 男,1984年生,博士,研究方向为密码学.E-mail:qunxiong_zheng@163.com
- 基金资助:
- 国家自然科学基金 (No.61272042,No.61402524); 信息保障技术重点实验室开放基金 (No.KJ-13-005)

Research on the Linear Approximation Relationship of Addition Modulo m

WANG Jian, QI Wen-feng, ZHENG Qun-xiong

PLA Information Engineering University State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou, Henan 450001, China

Received:2014-05-04 Revised:2015-03-05 Online:2015-11-25 Published:2015-11-25
- Supported by:
- National Natural Science Foundation of China (No.61272042, No.61402524); Open Fund of Key Laboratory of Information Assurance Technology (No.KJ-13-005)

摘要/Abstract

摘要：

该文研究模m加法的线性逼近问题,其中m为大于3的整数.利用分类计数方法,文中给出了任意k个整数求和模m的最低两个比特异或值用每一个整数的最低两个比特异或值去逼近时概率值的精确计算公式.此外,对于k=2、3或4,文中还进一步分析了这类线性逼近的效果.

关键词: 密码学, 线性分析, 模加法, 线性逼近

Abstract:

The linear approximation of addition modulo m is studied in this paper,where m>3.Using classification counting method,an exact probability formula of the XOR of the lowest two bits of the summation of k integers modulo m approximate to the XOR of the lowest two bits of every integer is given in this paper.Moreover,the effect of this approximation is discussed for k=2,3 or 4.

Key words: cryptography, linear cryptanalysis, modular addition, linear approximation

中图分类号:

TN918.1

王健, 戚文峰, 郑群雄. 模m加法的一类线性逼近关系研究[J]. 电子学报, 2015, 43(11): 2194-2199.

WANG Jian, QI Wen-feng, ZHENG Qun-xiong . Research on the Linear Approximation Relationship of Addition Modulo m[J]. Acta Electronica Sinica, 2015, 43(11): 2194-2199.

参考文献

[1] Matsui M.Linear cryptanalysis method for DES ciphers[A]. In Advances in Cryptology-EUROCRYPT 1993,Lecture Notes in Computer Science 765[C]. Berlin:Springer-Verlag,1994.386-397.
[2] Coppersmith D,Halevi S,Jutla C.Cryptanalysis of stream ciphers with linear masking[A]. In Advances in Cryptology-CRYPTO 2002,Lecture Notes in Computer Science 2442[C]. Berlin:Springer-Verlag,2002.515-532.
[3] Wallén J.Linear approximations of addition modulo 2ⁿ[A]. In Fast Software Encryption 2003,Lecture Notes in Computer Science 2887[C]. Berlin:Springer-Verlag,2003.261-273.
[4] 孙莹,金晨辉.进位返加与逐位模2加及模2ⁿ加的相容程度分析[J]. 高校应用数学学报A辑,2005,20(3):371-376. Sun Ying,Jin Chen-hui.Consistent degree analysis of ones complement addition with bit-wise exclusive-OR and with addition module 2ⁿ[J]. Appl Math J Chinese Univ Ser A,2005,20(3):371-376.(in Chinese)
[5] 张龙,吴文玲,温巧燕.mod 2ⁿ加运算与F₂上异或运算差值的概率分布和递推公式[J]. 北京邮电大学学报,2007,30(1):85-89. Zhang Long,Wu Wen-ling,Wen Qiao-yan.Probability distribution and recursive formula of difference between mod 2ⁿ sum and XOR over F₂[J]. Journal of Beijing University of Posts and Telecommunications,2007,30(1):85-89.(in Chinese)
[6] 陈士伟,金晨辉,李席斌.模2ⁿ加整体逼近模2加产生的噪声函数的概率分布研究[J]. 电子与信息学报,2009,31(10):2397-2401. Chen Shi-wei,Jin Chen-hui,Li Xi-bin.Research on the noise functions produced by macrocosm approximation of XOR with addition modulo 2ⁿ[J]. Journal of Electronics & Information Technology,2009,31(10):2397-2401.(in Chinese)
[7] 薛帅,戚文峰.模2ⁿ加法最佳线性逼近关系研究[J]. 电子与信息学报,2012,34(9):2156-2160. Xue Shuai,Qi Wen-feng.Research on the best linear approximation of addition modulo 2ⁿ[J]. Journal of Electronics & Information Technology,2012,34(9):2156-2160.(in Chinese)
[8] 薛帅,戚文峰.模2ⁿ减法最佳线性逼近关系研究[J]. 信息工程大学学报,2013,14(1):1-6. Xue Shuai,Qi Wen-feng.Research on the best linear approximation of subtraction modulo 2ⁿ[J]. Journal of Information Engineering University,2013,14(1):1-6.(in Chinese)
[9] 丁林,关杰.Trivium流密码的基于自动推导的差分分析[J]. 电子学报,2014,42(8):1647-1652. Ding Lin,Guan Jie.Differential cryptanalysis of trivium stream cipher based on automatic deduction[J]. Acta Electronica Sinica,2014,42(8):1647-1652.(in Chinese)
[10] Nyberg K,Wallén J.Improved linear distinguishers for SNOW 2.0[A]. In Fast Software Encryption 2006,Lecture Notes in Computer Science 4047[C]. Berlin:Springer-Verlag,2006.144-162.
[11] Berson T A.Differential cryptanalysis mod 2³² with applications to MD5[A]. In Advances in Cryptology-EUROCRYPT 1992,Lecture Notes in Computer Science 658[C]. Berlin:Springer-Verlag,1993.71-80.
[12] ETSI/SAGE.Specification of the 3GPP confidentiality and integrity algorithms 128-EEA3 & 128-EIA3.Document 4:design and evaluation report,version:2.0[EB/OL]. http://zuc.dacas.cn/thread.aspx?ID=2304,2011.
[13] Feng X T,C F Zhou,C K W.Linear approximations of addition modulo 2ⁿ-1[A]. In Fast Software Encryption 2011,Lecture Notes in Computer Science 6733[C]. Berlin:Springer-Verlag,2011.359-377.
[14] Tian T,Qi W F.Linearity properties of binary FCSR sequences[J]. Designs Codes and Cryptography,2009,52(3):249-262.
[15] Klapper A,Goresky M.2-Adic shift registers[A]. In Fast Software Encryption 1993,Lecture Notes in Computer Science 809[C]. Berlin:Springer-Verlag,1994.174-178.
[16] 柯召,魏万迪.组合论(上册)[M]. 北京:科学出版社,1981.

模m加法的一类线性逼近关系研究

Research on the Linear Approximation Relationship of Addition Modulo m

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	赵璐, 刘春红, 杜蛟, 曹天庆. Z₄上两类具有最优自相关四元序列的线性复杂度研究[J]. 电子学报, 2021, 49(4): 631-636.
[2]	陈露, 相峰, 孙知信. 基于属性密码体制的区块链安全技术研究进展[J]. 电子学报, 2021, 49(1): 192-200.
[3]	窦家维, 王颖囡, 葛雪. 区间关系保密计算若干问题研究[J]. 电子学报, 2021, 49(1): 50-57.
[4]	戚珉, 陈明. 标准模型下基于身份的混淆乐观公平交换方案[J]. 电子学报, 2020, 48(8): 1516-1527.
[5]	杨启良, 周彦伟, 杨坤伟, 王涛. 标准模型下可公开验证的匿名IBE方案的安全性分析[J]. 电子学报, 2020, 48(2): 291-295.
[6]	李顺东, 杜润萌, 杨颜璟, 魏琼. 有理数相等的保密判定[J]. 电子学报, 2020, 48(10): 1933-1937.
[7]	窦家维, 陈明艳. 多重集的保密计算及应用[J]. 电子学报, 2020, 48(1): 204-208.
[8]	杨小东, 王美丁, 裴喜祯, 李雨潼, 陈春霖, 麻婷春. 一种标准模型下无证书签名方案的安全性分析与改进[J]. 电子学报, 2019, 47(9): 1972-1978.
[9]	窦家维, 王文丽, 刘旭红, 李顺东. 有理区间的安全多方计算与应用[J]. 电子学报, 2018, 46(9): 2057-2062.
[10]	杜蛟, 刘春红, 张恩, 尚玉婧, 董乐. 基于拉丁方的GF(p)上q元旋转对称弹性函数的新构造[J]. 电子学报, 2018, 46(9): 2173-2180.
[11]	董丽华, 曾勇, 王春红, 胡予濮. LFCSR:基于FCSR的新密码学部件[J]. 电子学报, 2018, 46(8): 1924-1930.
[12]	李顺东, 杨晓莉, 左祥建, 周素芳, 亢佳, 刘新. 保护私有信息的图形相似判定[J]. 电子学报, 2017, 45(9): 2184-2189.
[13]	窦家维, 马丽, 李顺东. 最小值问题的安全多方计算及其应用[J]. 电子学报, 2017, 45(7): 1715-1721.
[14]	魏长河, 李俊志, 张少武. 对288轮Trivium算法的线性分析[J]. 电子学报, 2017, 45(6): 1456-1461.
[15]	付立仕, 崔霆, 金晨辉. 嵌套SP网络的New-Structure系列结构的零相关线性逼近与不可能差分性质研究[J]. 电子学报, 2017, 45(6): 1367-1374.