代数分析的方法、技 术与挑战
报告人：林东岱 2013年５月24日
目录
研究背景 理论算法 程序设计 硬件实施
什么是代数分析？
• 密码算法
加密密钥 解密密钥
明文
加密
密文
解密
原始明文
• 代数密码分析是一种试图通过求解代数方程组来破解、分 析或评估密码体制的一种方法。
– 建立关于密钥/明文与密文之间的（超定）代数方程组; – 处理方程组以降低次数/减少变元/减少单项式； – 求解方程组，恢复密钥/明文或评估求解的困难性。
Groebner基方法
Groebner基方法是求解代数方程组的最主要方法之一。 主要思想：基于定义在单项式上的序，获得理想的一组特 殊生成元，以获得理想中所有多项式的首项信息。
多项式系统有唯一解 所有变元作为首项出 现在Groebner基中
基本运算：S多项式计算、多项式除法/约化等。
Groebner基方法
为什么代数分析？
• 代数分析的特点
–机械化：将密码分析质的困难性转化为量的复杂性， 是一种脑力劳动的机械化； –适用于计算机计算：从而可以充分利用计算机的优势， 实现金钱到能力的一种转化； –方法统一：可以成为安全性评估的一般性方法；
• 代数攻击的效率
–数据量：需要的明密文对或密钥流（流密码）的数量； –时间复杂度：完成攻击所需要的基本运算量； –空间复杂度：攻击过程所需要的内存大小。
提出线性化理论，利用矩 阵等线性技术处理多项式 的约化过程（如F4算法）
Buchberger标准 Moller合冲标准 F5的合冲/重写标准 GVW等签名算法的重写标准
目录
研究背景 理论算法 程序设计 硬件实施
程序设计面临的难度与挑战
• 提高基本运算计算效率
– 数据结构：链表、数组、ZDD、递归 – 基础算法
• 控制内存增长
– 变量替换 – 内存共享 – 算法优化（计算次序）
• 减少冗余计算
代数分析中主要基本运算
特征列方法的基本运算：


主变元选取、初式的计算。 多项式的加法、乘法运算。 多项式的伪除法。 线性多项式约化其他多项式。
多项式取首项运算。 多项式加法、多项式乘单项式运算。 多项式与数组的相互转化（基于F4/F5算法）。 稀疏和稠密矩阵的消去算法（基于F4/F5算法）。 给定单项式，从大量单项式中寻找能整除此单项式的 运算。
目录
研究背景 理论算法 程序设计 件的完美结合提高计算效率 如何利用超级计算机，实现多节点上真正 的高性能计算？
（Ｅ级）超级计算的挑战
• 2010年4月，IBM公司《Some Challenges on Road from Petascale to Exascale》报告指出E 级系统的五大挑战：访存、通信、可靠性、能耗、 应用
为什么代数分析？
• the cryptanalyst can set up equations for the different key elements k1, k2, …, kr (namely the enciphering equations)... Each of these equations should therefore be complex in the ki, and involve many of them. Otherwise the enemy can solve the simple ones and then the more complex ones by substitution • if we could show that solving a certain system requires at least as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type, then we would have a lower bound of sorts for the work characteristic.
近似算法？(Håstad, 2001) 概率算法？
Ritt-Wu特征列方法
特征列方法的研究是计算机代数中的一个重要方向，广泛
运用于方程求解、机器证明等方向。
主要思想：通过消元的方法，将输入多项式系统三角化。
f1 ( x1 , x2 , , xn ) f1 ( x1 , x2 , , xn ) ... f m ( x1 , x2 , , xn )
树型结构：BDD（真值表），ZDD（单项式集合）
优点：可以共享内存，乘法效率较高。 缺点：只能用于布尔多项式，加法效率较低。
中间结果膨胀
中间结果膨胀问题在代数方程组求解算法中不可避免。 提高程序的空间效率的关键，是解决中间结果膨胀问题， 这也是研究的最大难点和挑战！
– 输入往往是稀疏多项式组，输出往往是唯一解。 – 运算过程中：容易产生极大多项式，使得计算无法继续下去。 例如：判断布尔多项式组 f1, f2 ,, fn 是否有公共解最简单的算 法，计算 i ( fi 1)，判断其是否恒等于0。计算过程 中显然会生成极复杂的中间多项式。
为什么代数分析？
• 特殊性...机会
–方程的超定性：通常可以得到比理论求解所需多得多 的方程； –方程的稀疏性：由于实际应用方面的限制问题，许多 密码算法的设计都具有较为简单的代数表示; –内部结构的脆弱性：如线性性、不平衡性等。
• 困难性…挑战
–怎样建立密码分析的代数模型? –怎样求解代数方程组或评估其困难性?
用最新生成的多项式 冲突分析？（SAT求解器中类似技巧，当某一组赋值出现矛盾时， 分析矛盾原因，添加一个新的子式，避免矛盾再次出现，即充分 利用之前得到的矛盾信息）
难度和挑战
通过Zdd存储布尔多项式，在提高了空间效率的同时，却 降低了时间效率。是否存在兼顾空间效率与时间效率的数 据结构？ 算法通过创建分支可以降低单分支内的计算复杂度，提高 单分支的时间效率。但过多的分支数同样会影响算法的整 体时间和空间效率。 如何平衡单分支规模与分支数？能否实现自适应、智能化 的创建分支？ 分支算法天然具备可并行的特点，但由于数据存在共享。 如何在实现高效的并行化同时有效的解决数据共享问题？ 如何将分支相对平均的分配给并行运算的结点进行计算？
为什么代数分析？
• 普遍认为....
– 大规模的代数方程组很容易变得的难于求解;
• 多项式方程组的整数解问题是不可判定的(Hilbert第十问题). • 复数/实数上的多项式方程组求解复杂度是双指数的(Collins, 1970s). • 判断一个布尔多项式系统是否有解是NP-C问题(Smale提出的 NPC研究模型).
中间结果膨胀问题的解决与数据结构的选择有密切关系。
冗余计算问题
对特征列算法来说，零点分解的过程中会产生大量的分支， 而大多数分支为空，即冗余分支。提前找到冗余分支中的 矛盾能减少新分支的产生，避免冗余运算。
Groebner基计算中大部分关键对会约化为零，但这部分 计算对Groebner基贡献几乎为零，怎样找一种机制来避 L xc 免约化为零计算 避免重复计算
• 代数分析关心的几个问题
–访存问题 –通信问题 –软件技术
g1 ( y1 ) g 2 ( y1 , y2 ) ... g p ( y1 , y2 , , yn )
基本运算：主变元选取、初式的计算、多项运算法、多项 的伪除
Ritt-Wu特征列方法
复数域C上的代数系统:
特征列理论的基础，1978s，吴文俊的开创性工作。
特征列理论的完善与改进：
– Garey (1979) 证明了 MQ问题是NP-hard问题; – Garey 证明了求解有限域上的多元多项式方程组是NP-hard问题, 多元 多项式方程组的求解问题等价于MQ问题.
• 但是....
– 真正使方程组变的困难的不是变量和方程的个数，而是方程的内部结构 和方程个数与方程中出现的单项式个数之间的平衡性。从而使得许多方 程组，如稀疏的、超定的方程系统变得比预想的要容易求解得多。
Groebner基方法的基本运算：
多项式的几种表示方法
链式表示：通过链表将单项式连接起来
优点：支持任何域上的多项式表示，加法效率较高。 缺点：操作复杂，乘法效率非常低。
数组表示：将各单项式系数序列对应一个数组
优点：进行加法、消去运算非常便捷。 缺点：内存消耗巨大（无法表示密码多项式），乘法效率较低。
[C. E. Shannon 1949]《保密系统的通信理论》
为什么代数分析？
高级加密标准AES可以写成含有1600个变量8000个方程 的二次布尔多项式方程组。 (N. Courtios，Asiacrypt 2002) 欧洲公钥密码算法HFE的挑战问题(通过80比特的密文求 解80比特的明文)，可以通过方程组求解的方法，在几十 小时内求解。 (J. Faugere，F4/F5算法，Crypto 2003)
－ G. Polya,Mathematical Discovery, Vol. 1, John Wiley & Sons, 1962
代数方程组的求解技术
代数方程组求解的三个层次
理论算法 程序设计 硬件实施 实施
程序
算法
目录
研究背景 理论算法 程序设计 硬件实施
代数方程组求解理论与算法
Greobner基相关算法：
Sun-Wang 于2008年提出了布尔环上的分支Groebner基算法(以 求解零点为目的，而不再计算完整的Groebner基）
理论算法的优化与改进
Groebner基算法改 进方向 避免不 该进行 的冗余 运算 减少和避免 冗余计算