布尔函数的代数攻击

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

布尔函数的代数攻击

杨文峰, 胡予濮, 高军涛

文章导航 > 电子科技大学学报 > 2010 > 39(6): 831-834

杨文峰, 胡予濮, 高军涛. 布尔函数的代数攻击[J]. 电子科技大学学报, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

引用本文:

杨文峰, 胡予濮, 高军涛. 布尔函数的代数攻击[J]. 电子科技大学学报, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

YANG Wen-feng, HU Yu-pu, GAO Jun-tao. Algebraic Attack on Boolean Functions[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

Citation:

YANG Wen-feng, HU Yu-pu, GAO Jun-tao. Algebraic Attack on Boolean Functions[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

布尔函数的代数攻击

doi: 10.3969/j.issn.1001-0548.2010.06.006

1.
西安电子科技大学计算机网络与信息安全教育部重点实验室西安 710071

基金项目:

国家自然科学基金(60833008,60803149);国家973计划(2007CB311201)

作者简介:
杨文峰(1971-)，男，博士生，副教授，主要从事密码学方面的研究

中图分类号: TN918.1

Algebraic Attack on Boolean Functions

1.
Key Laboratory of Computer Networks and Information Security Ministry of Education,Xidian University Xi'an 710071

摘要: 基于代数攻击，提出了一种已知部分真值表还原整个布尔函数的方法。对于n元d次布尔函数, 该方法的空间复杂度和数据复杂度均为O(N)，计算复杂度为O(N3)，其中N=1+C1n+C2n+…+Cdn。由复杂度可知，所求密码函数的代数次数越低，该方法的有效性越高。攻击方法表明密码设计中应该谨慎使用代数次数较低的布尔函数。
- 代数方法 /
- 布尔函数 /
- 密码分析 /
- 密码学
Abstract: Based on algebraic attack, a new reconstruction method of Boolean functions from the partial truth table is proposed. For the Boolean function with n variables and the degree of d, the proposed method requires O(N) values in the truth table, and the computational complexity is O(N3), and the memory complexity is O(N), where N=1+C1n+C2n+…+Cdn. From the above complexity, the lower the degree of the Boolean function is，the more efficient the method is. The proposed attack shows the designer of stream cipher should use Boolean functions with low degree carefully.
- algebraic approach /
- Boolean function /
- cryptanalysis /
- cryptology

[1]	秦华旺, 朱晓华, 戴跃伟. 基于环境感知的防泄漏多秘密共享方案 . 电子科技大学学报, 2015, 44(1): 101-105. doi: 10.3969/j.issn.1001-0548.2015.01.017
[2]	吴淮, 孙颖, 许春香, 伍玮. 对一种基于身份环签名方案的安全性分析 . 电子科技大学学报, 2013, 42(6): 926-929. doi: 10.3969/j.issn.1001-0548.2013.06.022
[3]	秦华旺, 朱晓华, 戴跃伟. 访问结构上的动态先应式秘密共享方案 . 电子科技大学学报, 2012, 41(6): 927-931. doi: 10.3969/j.issn.1001-0548.2012.06.021
[4]	陈艾东, 陈运, 曹娜娜. 模乘碰撞攻击的分析方法改进 . 电子科技大学学报, 2012, 41(5): 684-687. doi: 10.3969/j.issn.1001-0548.2012.05.008
[5]	甘元驹, 彭银桥, 梅其祥. 防欺诈的动态(t,n)认证加密方案 . 电子科技大学学报, 2011, 40(2): 201-203. doi: 10.3969/j.issn.1001-0548.2011.02.008
[6]	孙颖, 许春香, 吴淮, 陈艾东. 对一种代理签名方案的攻击和改进 . 电子科技大学学报, 2011, 40(4): 616-619.
[7]	董晓丽, 胡予濮, 陈杰. 不可能差分攻击AES中的新密钥筛选算法 . 电子科技大学学报, 2011, 40(3): 396-400. doi: 10.3969/j.issn.1001-0548.2011.03.014
[8]	张应辉, 马华, 王保仓. Schnorr签名中的阈下信道及其封闭方法 . 电子科技大学学报, 2010, 39(6): 826-830. doi: 10.3969/j.issn.1001-0548.2010.06.005
[9]	苏万力, 张跃宇, 张晓红, 王育民. 无证书盲签名方案 . 电子科技大学学报, 2009, 38(4): 533-536. doi: 10.3969/j.issn.1001-0548.2009.04.014
[10]	胡荣磊, 刘建伟, 张其善. 自认证公钥体制Ad hoc网络密钥管理方案 . 电子科技大学学报, 2009, 38(6): 943-947. doi: 10.3969/j.issn.1001-0548.2009.06.010
[11]	甘元驹, 谢仕义, 付东洋, 李小立. 防欺诈的广义多秘密分享方案 . 电子科技大学学报, 2008, 37(1): 68-69,80.
[12]	陈运, 吴震, 陈俊, 万武南, 吕永其. 防范边信道攻击的等功耗编码实现算法 . 电子科技大学学报, 2008, 37(2): 168-171.
[13]	张传武. 细胞自动机组合伪随机序列发生器 . 电子科技大学学报, 2008, 37(5): 716-719.
[14]	庞辽军, 李慧贤, 王育民. 基于LUC密码体制防欺诈的秘密共享方案 . 电子科技大学学报, 2007, 36(1): 108-111.
[15]	甘元驹, 彭银桥, 施荣华. 一种有效的可转换的认证加密方案 . 电子科技大学学报, 2005, 34(2): 172-174.
[16]	洪洁, 范修斌, 方刚, 路晓峰. 布尔函数最优连续化 . 电子科技大学学报, 2004, 33(5): 621-622,626.
[17]	陈勤. 严格平衡雪崩布尔函数的研究 . 电子科技大学学报, 2001, 30(1): 26-28,32.
[18]	陈运, 龚耀寰. 大数幂剩余的二进制冗余数Montgomery算法 . 电子科技大学学报, 2000, 29(6): 587-590.
[19]	陈运, 龚耀寰. 基于二进制冗余数的递归余数和算法 . 电子科技大学学报, 2000, 29(1): 1-4.
[20]	陈运. 基于乘同余对称特性的快速RSA算法的改进 . 电子科技大学学报, 1997, 26(5): 477-482.

WeChat

点击查看大图

计量

文章访问数: 4516
HTML全文浏览量: 218
PDF下载量: 135
被引次数: 0

布尔函数的代数攻击

doi: 10.3969/j.issn.1001-0548.2010.06.006

1. 西安电子科技大学计算机网络与信息安全教育部重点实验室西安 710071

基金项目:

国家自然科学基金(60833008,60803149);国家973计划(2007CB311201)

作者简介:
杨文峰(1971-)，男，博士生，副教授，主要从事密码学方面的研究

收稿日期: 2009-04-10
修回日期: 2009-07-08
刊出日期: 2010-12-15

中图分类号: TN918.1

关键词:

摘要: 基于代数攻击，提出了一种已知部分真值表还原整个布尔函数的方法。对于n元d次布尔函数, 该方法的空间复杂度和数据复杂度均为O(N)，计算复杂度为O(N3)，其中N=1+C1n+C2n+…+Cdn。由复杂度可知，所求密码函数的代数次数越低，该方法的有效性越高。攻击方法表明密码设计中应该谨慎使用代数次数较低的布尔函数。

English Abstract

杨文峰, 胡予濮, 高军涛. 布尔函数的代数攻击[J]. 电子科技大学学报, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

引用本文:

杨文峰, 胡予濮, 高军涛. 布尔函数的代数攻击[J]. 电子科技大学学报, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

YANG Wen-feng, HU Yu-pu, GAO Jun-tao. Algebraic Attack on Boolean Functions[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

Citation:

YANG Wen-feng, HU Yu-pu, GAO Jun-tao. Algebraic Attack on Boolean Functions[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(6): 831-834. doi: 10.3969/j.issn.1001-0548.2010.06.006

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

期刊在线

编辑办公

友情链接

电子科技大学

版权所有 © 《电子科技大学学报》编辑部

地址: 成都市建设北路二段四号电子科技大学主楼中350室电话: 028-83202308,83207559 Email: xuebao@uestc.edu.cn

本系统由北京仁和汇智信息技术有限公司开发