基于区间上离散对数问题的改进算法

1、关于区间上离散对数问题的改进算法 报告人：王瑶 2015年10月23号王瑶，吕克伟研究内容研究内容 在群G上区间大小为N 的离散对数问题为：给定群元素g，h以及大整数N，找到整数n ( )，使得 。 通常对于该问题的求解主要是对Pollards kangaroos method的改进,尝试通过减少跳跃次数来优化算法，目前解决这一问题的最优低存储算法是van Oorschot和 Wiener 版本的Pollards kangaroos method，其平均情况下的时间代价是 次群运算。 文中对经典Pollards kangaroos method进行改进，得到新的求解算法。新算法是通过利用多次小

2、整数乘法代替一次完整的大整数乘法来减少kangaroos每次跳跃的时间代价实现算法效率的提高。进一步，文章中通过增加kangaroos的数量使得算法在跳跃次数和每次跳跃的时间代价两方面都得到改进，从而得到区间上离散对数问题的更有效的求解算法。Nn0ngh No )1 (2( 研究背景研究背景 经典离散对数问题（DLP）是许多密码系统和协议的安全性基础，但随着密码学的发展，出现了一些特殊的离散对数问题用于解决实际中的密码学问题，比如在某个区间上的离散对数问题。该问题的出现是由于在实际应用中，如果没有进行有效的保护措施，敌手可能通过某些侧信道攻击的手段获取关于离散对数的某些比特位信息，从而推断出待

3、求解离散对数所在的区间范围，之后敌手在进行离散对数求解时只需要在该区间范围内求解即可。 目前用Baby-step Giant-step method解决区间上的离散对数问题，需要执行 次群运算、需要 空间。因此该算法需要较大的存储空间并且查表的速度对算法的影响很大，最快变体在平均情况下的时间代价为 次群运算。 直到2010年，Galbraith等人通过增加kangaroos的只数实现总的跳跃次数的减少，从而对经典Pollards kangaroos method给予改进，使得算法的代价从 次群运算降低到 次群运算。并说明，当四只kangaroos同时跳跃时算法的效率最高。)( nO)( nOn

4、34no )1 (2 ( no )1 (714. 1 (相关算法相关算法p 经典经典Pollards kangaroos算法算法 给定循环群G，群中元素g，h，大整数N，计算n使得 选择一个正整数的小集合S作为kangaroos的跳跃步集合，从群G中随机均匀选取一些元素构成可区分集合D，定义一个从群G到集合S的随机映射f： 。 一只kangaroo跳跃就对应一个G中的序列： ，i=0,1,2, 从给定的 开始。同时定义一序列 , 令 ，i=0,1,2, 因此，是kangaroo前i次跳跃的距离和，那么， ，i=0,1,2,ngh)0 (NnSG相关算法相关算法 Pollards kangaro

5、os是基于随机步的算法，每只kangaroo每次跳跃一步。定义两只kangaroos分别为T和W。T从区间中点开始向区间右侧跳跃，W从群元素h开始（即未知离散对数的群元素）向区间右侧跳跃，两者使用同样的随机步集合。在串行计算机上对T和W交替操作，无论何时只要kangaroos的跳跃落地点的群元素属于可区分点集合D，记录此时的落地点。当某个落地点值被不同类型（T或者W）kangaroos访问时即发生碰撞，算法终止。 经典的Pollards kangaroos method针对每只kangaroo，每次跳跃都需要计算一次大整数乘法，但只有当其满足可区分点条件时才将该跳跃点存储下来以备碰撞检测，否则

6、丢弃该点值不进行存储。因此存储操作不是每次都进行，故每次跳跃都花费很大的时间代价计算一次完整大整数乘法并没有必要，这是经典Kangaroos算法的一个不足。相关算法相关算法 p Cheon-Hong-Kim算法算法 经典Pollards rho method是通过迭代找到碰撞来求出离散对数，2008年Jung HeeCheon等人提出利用预定义的可区分点的条件通过减少每次迭代的计算量来降低Pollards rho算法的时间代价。主要通过定义合适的函数，计算简单的函数值，判断预先定义的可区分点条件，只有满足可区分点条件时才计算一次完全乘法得到对应的群元素，存入表中，并与表中已有元素进行碰撞检测，

7、而不满足条件时只需要进行简单的运算得到下次迭代需要的索引下标s即可。 Cheon等人改进的算法通过一定量的预计算，把每次迭代中计算两个群元素乘积转换成多次小整数乘积，使得算法的运行时间至少比原始算法快10倍。但其只是减少了每次迭代的计算量，并没有考虑减少迭代次数（可类比为kangaroos算法中的跳跃次数），而迭代次数过分依赖于迭代函数的选取。改进的改进的Pollards kangaroos算法算法p 主要思想主要思想 尝试在减少跳跃次数的基础上再减少每次跳跃的时间代价，这样可以从两方面提升经典算法的运行时间。经典算法中，每次群运算的时间代价主要是迭代过程中计算两个大整数的乘积，但该计算并不是

8、每次都必需的。所以，我们通过设计合适的迭代函数，做一定量的预计算，每次用多次小整数乘积代替一次大整数乘积计算，只有需要进行存储操作时才进行一次大整数乘法，从而减少大整数乘积的计算次数，使得计算效率得到提高。p 算法描述算法描述 固定索引集合S=0,1,2，k-1，k是一小整数。选择小的正整数集合S = 作为跳跃步长集合，令 M= 。固定一个小正整数l，并且预计算集合 中值 ，即为至多个M中元素乘积的集合。标签集合T=0,1,.,T-1，T=kb，b是一小整数。改进的改进的Pollards kangaroos算法算法 定义集合T=0,1,2,t-1，定义下面四个函数： 索引函数s： 辅助索引函数

9、 标签函数 辅助标签函数 定义 ， ，使其满足下面两点：1. 是满射并且原象近似均匀，也就是说群G中的元素对应的S下的象点将群G划分成大小相近的子集。2. 我们设计函数 ，定义函数 ： 给定， 总可以写成下列形式：改进的改进的Pollards kangaroos算法算法 定义辅助标签函数 ， 函数是将一次大整数乘法转换为多次小整数乘法的关键。可区分点条件定义为： 。 一只kangaroo就是一个G中的序列： ， 不用计算 的乘积，可利用 得到下次索引值 ， 同样，不用计算出 就可得到 。依次计算索引值，每次迭代都不用计算完全乘法，只有满足可区分点的条件时才计算一次完全乘法,获得此时对应的 ，其

10、中 已预计算，可通过查表得到。 定义两只kangaroos ，分别为T和W，T、W从区间中点和h开始向区间右侧跳跃，交替执行上述算法，当满足可区分点条件时，计算出此时的跳跃点值进行存储，当某个值被不同类型（T或者W）kangaroos访问时即发生碰撞，算法终止。 算法再优化算法再优化 为了从跳跃次数上再优化kangaroos算法，可将kangaroos的只数取为四只，相应的对原始算法做一定的修改即可。设置两只wild kangaroos，起始点分别为h和 。为了更快得到wild-wild碰撞，我们应将S集合中的元素均取为偶数，即每次的跳跃步长均为偶数。为了保证wild-tame碰撞，需要设置两

11、只tame kangaroos，起始点取为相邻两点（一奇一偶），可取区间中点 。这样取值还有一点好处就是不会出现无用的tame-tame碰撞，但会发生我们需要的tame-wild碰撞。 这样的改变可以使得区间宽度减半，发生碰撞时每只kangaroos的跳跃步数减少，这样，相比原始的kangaroos算法，既减少了跳跃步数，又减少了每次跳跃的时间代价，使得算法的总体运行时间代价减少。改进前后算法代价对比改进前后算法代价对比算法算法跳跃次数跳跃次数一次跳跃时间代价一次跳跃时间代价一次跳跃时间代一次跳跃时间代价价（p是是1024bits）经典 two kangaroos1次1024比特乘法（1048576次比特运算）改进的 two kangaroos64次16比特与32比特比特乘法（32768次比特运算）four kangaroos1次1024比特乘法（1