HASH GAME - Online Skill Game GET 300

　　2、7) 摘要 本发明提供了一种哈希值密码的恢复方法 和装置， 该方法包括 ： 配置系统初始化信息 ； 利用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹 表文件中 ； 在彩虹表文件中的任一彩虹表与预设 彩虹表的参数相匹配的情况下， 从哈希值文件中 获取一个待恢复的哈希值 ； 判断能否利用 GPU 对 该待恢复的哈希值进行密码恢复 ； 如果判断结果 为是， 则利用 GPU 对该待恢复的哈希值进行密码 恢复， 直至恢复完成哈希值文件中所有待恢复的 哈希值的密码 ； 其中， 系统初始化信息包括哈希 算法类型、 与彩虹表相关的信息等。 本发明提供的 方法和装置， 利用 CPU 和 GPU 分别生。

　　3、成彩虹表， 并 结合 GPU 和彩虹表算法来恢复哈希值密码， 可大 大降低哈希值密码的恢复时间。 (51)Int.Cl. 权利要求书 4 页 说明书 12 页 附图 6 页 (19)中华人民共和国国家知识产权局 (12)发明专利申请 权利要求书4页 说明书12页 附图6页 (10)申请公布号 CN 103400072 A CN 103400072 A *CN103400072A* 1/4 页 2 1. 一种哈希值密码的恢复方法， 其特征在于， 包括 ： 配置系统初始化信息 ； 利用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹表文件中 ； 在彩虹表文件中的任一彩虹表与预设彩虹表的参数相。

　　4、匹配的情况下， 从哈希值文件中 获取一个待恢复的哈希值 ； 判断能否利用 GPU 对该待恢复的哈希值进行密码恢复 ； 如果判断结果为是， 则利用 GPU 对该待恢复的哈希值进行密码恢复， 直至恢复完成哈 希值文件中所有待恢复的哈希值的密码 ； 其中， 所述系统初始化信息包括哈希算法类型， 字符集， 字符集文件， 彩虹链的长度 , 每个彩虹表的彩虹链的个数， 需生成的彩虹表的个数， 初始彩虹表表号索引， 密码口令的最 小长度和最大长度， 生成的彩虹表存储路径， 待恢复的哈希值文件和恢复结果文件。 2. 如权利要求 1 所述的方法， 其特征在于 ： 利用 CPU 生成彩虹表的步骤， 具体包括 ： 。

　　5、随机生成一条彩虹链链首值 T1； 对所述 T1进行哈希运算得到 HT1； 对所述 HT1进行截短函数运算得到 RHT1； 将 RHT1重复进行预定次数的哈希运算和截短函数运算， 得到彩虹链链尾值 ； 根据所述彩虹链链首值和所述彩虹链链尾值形成彩虹链并保存于彩虹表 ； 利用 GPU 生成彩虹表的步骤， 具体包括 ： 根据 GPU 的计算能力设置执行彩虹链生成核函数需分配的块数和块中的线程数 ； 随机生成多个彩虹链链首值并保存于 GPU 显存中 ； 调度彩虹链生成核函数的线程， 对所述多个彩虹链链首值并行进行预定次数的哈希运 算和截短函数运算， 得到与其对应的彩虹链链尾值 ； 根据所述多个彩虹链链。

　　6、首值及其对应的彩虹链链尾值分别形成彩虹链并保存于彩虹 表。 3.如权利要求1所述的方法， 其特征在于， 所述利用GPU对该待恢复的哈希值进行密码 恢复的步骤， 具体包括 ： 根据 GPU 的计算能力设置执行预计算核函数和在线分析核函数各自需分配的块数和 块中的线程数 ； 将所述待恢复的哈希值和各猜测位置相结合进行截短函数运算后得到对应的各链首 节点值 Spos（P） ； 调度预计算核函数的线程， 对所述各 Spos（P） 并行进行从其对应的猜测位置后移一个 节点至彩虹链链尾位置前移两个节点的彩虹链节点值的还原计算， 得到所述各 Spos（P） 对 应的链尾节点值 Epos（P） ； 根据二分查。

　　7、找法在彩虹表中查找链尾节点值与所述各 Epos（P） 相同的彩虹链， 并获取 该些彩虹链的各链首节点值 Sj（P） 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹 链上的各相应位置值 Ij（P） ； 调度在线分析阶段核函数的线程， 对所述各 Sj（P） 并行进行从彩虹链链首位置至 Ij（P） 前移一个节点的彩虹链节点值的还原计算， 得到所述各 Sj（P） 对应的链尾节点值 Ej（P） ； 权 利 要 求 书 CN 103400072 A 2 2/4 页 3 任取一个 Ej（P） 进行哈希运算得到第一预判定哈希值 ； 如果所述第一预判定哈希值与待恢复哈希值相同， 则密码恢复。

　　8、成功， 将与所述第一预 判定哈希值对应的密码进行存储 ； 其中， 猜测位置为从彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 4. 如权利要求 1 所述的方法， 其特征在于， 还包括 ： 如果不能利用 GPU 对该待恢复的哈 希值进行密码恢复， 则利用 CPU 对该待恢复的哈希值进行密码恢复 , 具体包括 ： 将待恢复哈希值和猜测位置相结合进行截短函数运算后得到链首节点值 Spos（P） ； 将所述 Spos（P） 进行从猜测位置后移一个节点至彩虹链链尾位置前移 两个节点的节点数次的哈希运算和截短函数运算得到的链尾节点值 Epos（P） ； 根据二分查找法在彩虹表中查找链尾节点值与所述。

　　9、 Epos（P） 相同的彩虹链， 并获取该 些彩虹链的各链首节点值 Sj(P) 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹链上 的各相应位置值 Ij（P） ； 根据 Sj(P) 和 Ij（P） 分别获得一个彩虹链链首元素值 Sjs（P） 及其在彩虹链上的相应 位置元素值 Ijs（P） ； 根据 Sjs（P） 进行自彩虹链链首位置至 Ijs（P） 前移一个节点的节点数次的哈希运算和 截短函数运算后得到预判定值 ； 将所述预判定值进行哈希运算后得到相应的第二预判定哈希值 ； 如果所述第二预判定哈希值与待恢复的哈希值相同， 则密码恢复成功， 将与所述第二 预判定哈希值对应密。

　　10、码进行存储 ； 其中， 所述猜测位置为彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 5. 如权利要求 1 所述的方法， 其特征在于， 在配置系统初始化信息的步骤之后， 还包 括 ： 对系统进行优化配置， 包括对与彩虹表相关的参数进行优化， 对截短函数进行优化和 对 GPU 的计算轮数进行优化， 其中， 所述对与彩虹表相关的参数进行优化具体为 ： 在密码空间允许的情况下， 增加每个彩 虹表中的彩虹链的个数和彩虹表的个数 ； 所述对截短函数进行优化具体为 ： 设置截短函数为； 其中， Si,j(P) 为第 i 条彩虹链第 j 位置的初始节点值， 1 i c, 1 j l, c 为每 张彩。

　　11、虹表的彩虹链的个数， l 为彩虹链的长度， N 为密码空间大小 ； 所述对 GPU 的计算轮数进行优化， 具体为 ： 在 GPU 设备计算功能级的主版本号分别为 1， 2， 3 的情况下， 则块中线， 配置块数分别为设备上处理器数量的 3 倍， 3 倍， 16 倍。 6. 一种哈希值密码的恢复装置， 其特征在于， 包括 ： 初始化配置单元， 用于配置系统初始化信息 ； 其中， 所述系统初始化信息包括哈希算法 类型， 字符集， 字符集文件， 彩虹链的长度 , 每个彩虹表的彩虹链的个数， 需生成的彩虹表 的个数， 初始彩虹表表号索引， 密码口令的最小长度和最大。

　　12、长度， 生成的彩虹表存储路径， 待恢复的哈希值文件和恢复结果文件 ； 彩虹表生成单元， 用于利用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹表文件 权 利 要 求 书 CN 103400072 A 3 3/4 页 4 中 ； 待恢复哈希值获取单元， 用于在彩虹表文件中的任一彩虹表与预设彩虹表的参数相匹 配的情况下， 从哈希值文件中获取一个待恢复的哈希值 ； 判断单元， 用于判断能否利用 GPU 对该待恢复的哈希值进行密码恢复 ； 第一哈希值密码恢复单元， 用于利用 GPU 对该待恢复的哈希值进行密码恢复， 直至恢 复完成哈希值文件中所有待恢复的哈希值的密码。 7. 如权利要求 6 所。

　　13、述的装置， 其特征在于， 所述彩虹表生成单元具体包括 ： 第一链首值生成子单元， 用于随机生成一条彩虹链链首值 T1； 第一计算子单元， 用于对所述 T1进行哈希运算得到 HT1； 第二计算子单元， 用于对所述 HT1进行截短函数运算得到 RHT1； 第一链尾值生成子单元， 用于将RHT1重复进行预定次数的哈希运算和截短函数运算， 得 到彩虹链链尾值 ； 第一彩虹链形成子单元， 用于根据所述彩虹链链首值和所述彩虹链链尾值形成彩虹链 并保存于彩虹表 ； 第一核函数设置子单元， 用于根据 GPU 的计算能力设置执行彩虹链生成核函数需分配 的块数和块中的线程数 ； 第二链首值生成子单元， 用于随机生。

　　14、成多个彩虹链链首值并保存于 GPU 显存中 ； 第二链尾值生成子单元， 用于调度彩虹链生成核函数的线程， 对所述多个彩虹链链首 值并行进行预定次数的哈希运算和截短函数运算， 得到与其对应的彩虹链链尾值 ； 第二彩虹链形成子单元， 用于根据所述多个彩虹链链首值及其对应的彩虹链链尾值分 别形成彩虹链并保存于彩虹表。 8. 如权利要求 6 所述的装置， 其特征在于， 所述第一哈希值密码恢复单元具体包括 ： 第二核函数设置子单元， 用于根据 GPU 的计算能力设置执行预计算核函数和在线分析 核函数各自需分配的块数和块中的线程数 ； 第一链首节点值生成子单元， 用于将所述待恢复的哈希值和各猜测位置相结合。

　　15、进行截 短函数运算后得到对应的各链首节点值 Spos（P） ； 第一链尾节点值生成子单元， 用于调度预计算核函数的线程， 对所述各链首节点值 Spos （P） 并行进行从其对应的猜测位置后移一个节点至彩虹链链尾位置前移两个节点的彩虹链 节点值的还原计算， 得到所述各 Spos（P） 对应的链尾节点值 Epos（P） ； 第一链首节点值获取子单元， 用于根据二分查找法在彩虹表中查找链尾节点值与所述 各 Epos（P） 相同的彩虹链， 并获取该些彩虹链的各链首节点值 Sj（P） 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹链上的各相应位置值 Ij（P） ； 第二链尾节点值生。

　　16、成子单元， 用于调度在线分析阶段核函数的线程， 对所述各 Sj（P） 并 行进行从彩虹链链首位置至 Ij（P） 前移一个节点的彩虹链节点值的还原计算， 得到所述各 Sj（P） 对应的链尾节点值 Ej（P） ； 第一预判定哈希值生成子单元， 用于任取一个 Ej（P） 进行哈希运算得到第一预判定哈 希值 ； 第一密码存储子单元， 用于当所述第一预判定哈希值与待恢复哈希值相同时， 将与此 所述第一预判定哈希值对应的密码进行存储 ； 权 利 要 求 书 CN 103400072 A 4 4/4 页 5 其中， 猜测位置为从彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 9. 如权利要求 6 所。

　　17、述的装置， 其特征在于， 还包括第二哈希值密码恢复单元， 用于当不 能利用 GPU 对该待恢复的哈希值进行密码恢复， 则利用 CPU 对该待恢复的哈希值进行密码 恢复， 具体包括 ： 第二链首节点值生成子单元， 用于将待恢复哈希值和猜测位置相结合进行截短函数运 算后得到链首节点值 Spos（P） ； 第三链尾节点值生成子单元， 用于将所述 Spos（P） 进行从猜测位置后移一个节点至彩 虹链链尾位置前移两个节点的节点数次的哈希运算和截短函数运算得到的链尾节点值 Epos （P） ； 第二链首节点值获取子单元， 用于根据二分查找法在彩虹表中查找链尾节点值与所述 Epos（P） 相同的彩虹链， 并。

　　18、获取该些彩虹链的各链首节点值 Sj(P) 及根据各 Epos（P） 、 各 Sj （P） 和猜测位置确定的在彩虹链上的各相应位置值 Ij（P） ； 彩虹链元素获取子单元， 用于根据 Sj(P) 和 Ij（P） 分别获得一个彩虹链链首元素值 Sjs （P） 及其在彩虹链上的相应位置元素值 Ijs（P） ； 预判定值生成子单元， 用于根据 Sjs（P） 进行自彩虹链链首位置至 Ijs（P） 前移一个节 点的节点数次的哈希运算和截短函数运算后得到预判定值 ； 第二预判定哈希值生成子单元， 用于将所述预判定值进行哈希运算后得到相应的第二 预判定哈希值 ； 第二密码存储子单元， 用于当所述第二预判定哈希。

　　19、值与待恢复的哈希值相同时， 将与 所述第二预判定哈希值对应的密码进行存储 ； 其中， 猜测位置为从彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 10. 如权利要求 6 所述的装置， 其特征在于， 还包括优化配置单元， 用于对系统进行优 化配置， 具体包括 ： 彩虹表参数优化配置子单元， 用于对与彩虹表相关的参数进行优化， 包括在密钥空间 允许的情况下， 增加每个彩虹表的彩虹链的个数和彩虹表的个数 ； 截短函数优化配置子单元， 用于对截短函数进行优化， 包括： 设置截短函数为； 其中， Si,j(P) 为第 i 条彩虹链第 j 位置的初始节点值， 1 i c, 1 j l, c 为每 。

　　20、个彩虹表中的彩虹链的个数， l 为彩虹链的长度， N 为密码空间大小 ； GPU 计算轮数优化配置子单元， 用于对 GPU 的计算轮数进行优化， 包括在 GPU 设备计算 功能级的主版本号分别为 1， 2， 3 的情况下， 配置块中线， 块数分别 为设备上处理器数量的 3 倍， 3 倍， 16 倍。 权 利 要 求 书 CN 103400072 A 5 1/12 页 6 哈希值密码的恢复方法和装置 技术领域 0001 本发明属于密码恢复领域， 特别涉及一种哈希值密码的恢复方法和装置。 背景技术 0002 哈希 (Hash) 算法 , 即散列函数 , 是一种。

　　21、单向密码体制 , 即是一种从明文到密文 的不可逆映射， 只有加密过程， 没有解密过程。同时 , 哈希算法可以将任意长度的输入经过 变化以后得到固定长度的输出。 哈希算法的这种单向特征和输出数据长度固定的特征使得 它可以生成消息或者数据。 0003 目前， 常见的哈希算法主要包括 MDx 系列和 SHA 系列， 其广泛应用于信息加密、 数 字签名、 文件校验、 鉴权协议等方面， 相应地， 对破解哈希算法的需求也越来越高。 破解哈希算法， 即恢复哈希值的密码， 其主要任务是 ： 对于给出的一个哈希值 y， 反算 出一个 x 来满足 h(x)=y。理论上有以下两种极端的方式 ： 第一种， 暴力破解法。

　　22、， 即穷尽搜索 X 中的所有元素， 验证是否存在 x(x X) 使得 h(x)=y， 这样最多需要对 h 进行 X 次赋值。 0004 第二种， 查表法， 即将所有 x(x X) 及其哈希值 y 进行保存， 当已知某个 y 时， 在 存储空间中搜索 y 对应的 x。 0005 上述两种方式在理论上都是可以的， 但第一种方式需要海量的计算时间， 第二种 方式需要海量的存储空间， 在实际应用中， 第一种方式的时间复杂度和第二种方式的空间 复杂度都是人类无法接受的范围。 0006 基于此， 提出了彩虹表算法， 它是结合了暴力破解法和查表法并在这两者之间取 得一个折中， 用人类可以承受的时间范围和。

　　23、存储空间范围来恢复哈希值的密码， 其核心思 想是将明文计算得到的哈希值由一个截短函数 （R 函数） 映射回到明文空间， 进而可交替地 计算明文和哈希值， 以减少恢复哈希值密码的时间。 0007 利用彩虹表算法对哈希值的密码进行恢复， 虽能够分别获得比暴力破解法及查表 法高得多的时间效率和空间效率， 但对于恢复密码较长的哈希值， 其预计算阶段及在线分 析阶段需要大量的彩虹链计算， 在采用 CPU 的串行计算方式的情况下， 需要的时间仍然是 不能承受的范围。因此， 由于 CPU 计算能力的限制， 很难做到将彩虹表算法应用于密码较长 的哈希值的恢复。 0008 图形处理器 （Graphic Proc。

　　24、essing Unit， GPU） 作为近年来迅速发展的通用并行计 算平台， 其并行线程执行模型和线程同步技术专用于解决大规模的并行计算， 使得 GPU 在 大多数数据处理型应用上的性能优于 CPU。 0009 但是， 目前还没有将 GPU 与彩虹表算法相结合用来恢复哈希值密码的方案。 发明内容 0010 本发明所要解决的技术问题是提供一种哈希值密码的恢复方法和装置， 解决由于 CPU 计算能力的限制， 无法用彩虹表算法恢复密码较长的哈希值的问题。 说 明 书 CN 103400072 A 6 2/12 页 7 本发明一方面提供了一种哈希值密码的恢复方法， 包括 ： 配置系统初始化信息 ； 利。

　　25、用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹表文件中 ； 在彩虹表文件中的任一彩虹表与预设彩虹表的参数相匹配的情况下， 从哈希值文件中 获取一个待恢复的哈希值 ； 判断能否利用 GPU 对该待恢复的哈希值进行密码恢复 ； 如果判断结果为是， 则利用 GPU 对该待恢复的哈希值进行密码恢复， 直至恢复完成哈 希值文件中所有待恢复的哈希值的密码 ； 其中， 所述系统初始化信息包括哈希算法类型， 字符集， 字符集文件， 彩虹链的长度 , 每个彩虹表的彩虹链的个数， 需生成的彩虹表的个数， 初始彩虹表表号索引， 密码口令的最 小长度和最大长度， 生成的彩虹表存储路径， 待恢复的哈希值文件和。

　　26、恢复结果文件。 0011 进一步的， 利用 CPU 生成彩虹表的步骤， 具体包括 ： 随机生成一条彩虹链链首值 T1； 对所述 T1进行哈希运算得到 HT1； 对所述 HT1进行截短函数运算得到 RHT1； 将 RHT1重复进行预定次数的哈希运算和截短函数运算， 得到彩虹链链尾值 ； 根据所述彩虹链链首值和所述彩虹链链尾值形成彩虹链并保存于彩虹表。 0012 进一步的， 利用 GPU 生成彩虹表的步骤， 具体包括 ： 根据 GPU 的计算能力设置执行彩虹链生成核函数需分配的块数和块中的线程数 ； 随机生成多个彩虹链链首值并保存于 GPU 显存中 ； 调度彩虹链生成核函数的线程， 对所述多个彩虹。

　　27、链链首值并行进行预定次数的哈希运 算和截短函数运算， 得到与其对应的彩虹链链尾值 ； 根据所述多个彩虹链链首值及其对应的彩虹链链尾值分别形成彩虹链并保存于彩虹 表。 0013 进一步的， 所述利用 GPU 对该待恢复的哈希值进行密码恢复的步骤， 具体包括 ： 根据 GPU 的计算能力设置执行预计算核函数和在线分析核函数各自需分配的块数和 块中的线程数 ； 将所述待恢复的哈希值和各猜测位置相结合进行截短函数运算后得到对应的各链首 节点值 Spos（P） ； 调度预计算核函数的线程， 对所述各 Spos（P） 并行进行从其对应的猜测位置后移一个 节点至彩虹链链尾位置前移两个节点的彩虹链节点值的还原。

　　28、计算， 得到所述各 Spos（P） 对 应的链尾节点值 Epos（P） ； 根据二分查找法在彩虹表中查找链尾节点值与所述各 Epos（P） 相同的彩虹链， 并获取 该些彩虹链的各链首节点值 Sj（P） 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹 链上的各相应位置值 Ij（P） ； 调度在线分析阶段核函数的线程， 对所述各 Sj（P） 并行进行从彩虹链链首位置至 Ij （P） 前移一个节点的彩虹链节点值的还原计算， 得到各 Sj（P） 对应的链尾节点值 Ej（P） ； 任取一个 Ej（P） 进行哈希运算得到第一预判定哈希值 ； 如果所述第一预判定哈希值与待恢复哈希值相同。

　　29、， 则密码恢复成功， 将与所述第一预 说 明 书 CN 103400072 A 7 3/12 页 8 判定哈希值对应的密码进行存储 ； 其中， 猜测位置为从彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 0014 进一步的， 本方法还包括 ： 如果不能利用 GPU 对该待恢复的哈希值进行密码恢复， 则利用 CPU 对该待恢复的哈希值进行密码恢复 , 具体包括 ： 将待恢复哈希值和猜测位置相结合进行截短函数运算后得到链首节点值 Spos（P） ； 将所述 Spos（P） 进行从猜测位置后移一个节点至彩虹链链尾位置前移 两个节点的节点数次的哈希运算和截短函数运算得到的链尾节点值 Epos（。

　　30、P） ； 根据二分查找法在彩虹表中查找链尾节点值与所述各 Epos（P） 相同的彩虹链， 并获取 该些彩虹链的各链首节点值 Sj(P) 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹链 上的各相应位置值 Ij（P） ； 根据 Sj(P) 和 Ij（P） 分别获得一个彩虹链链首元素值 Sjs（P） 及其在彩虹链上的相应 位置元素值 Ijs（P） ； 根据 Sjs（P） 进行自彩虹链链首位置至 Ijs（P） 前移一个节点的节点数次的哈希运算和 截短函数运算后得到预判定值 ； 将所述预判定值进行哈希运算后得到相应的第二预判定哈希值 ； 如果所述第二预判定哈希值与待恢复的哈希值相。

　　31、同， 则密码恢复成功， 将与所述第二 预判定哈希值对应的密码进行存储 ； 其中， 从猜测位置为彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 0015 进一步的， 在配置系统初始化信息的步骤之后， 还包括 ： 对系统进行优化配置， 包括对与彩虹表相关的参数进行优化， 对截短函数进行优化和 对 GPU 的计算轮算进行优化， 其中， 所述对与彩虹表相关的参数进行优化具体为 ： 在密码空间允许的情况下， 增加每个彩 虹表中的彩虹链的个数和彩虹表的个数 ； 所述对截短函数进行优化具体为 ： 设置截短函数为； 其中， Si,j(P) 为第 i 条彩虹链第 j 位置的初始节点值， 1 i c, 1。

　　32、 j l, c 为每 张彩虹表的彩虹链的个数， l 为彩虹链的长度， N 为密码空间大小 ； 所述对 GPU 的计算轮数进行优化， 具体为 ： 在 GPU 设备计算功能级的主版本号分别为 1， 2， 3 的情况下， 则块中线， 配置块数分别为设备上处理器数量的 3 倍， 3 倍， 16 倍。 0016 本发明同时提出一种哈希值密码的恢复装置， 包括 ： 初始化配置单元， 用于配置系统初始化信息 ； 其中， 所述系统初始化信息包括哈希算法 类型， 字符集， 字符集文件， 彩虹链的长度 , 每个彩虹表的彩虹链的个数， 需生成的彩虹表 的个数， 初始彩虹表表号索。

　　33、引， 密码口令的最小长度和最大长度， 生成的彩虹表存储路径， 待恢复的哈希值文件和恢复结果文件。 0017 彩虹表生成单元， 用于利用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹表文 件中 ； 待恢复哈希值获取单元， 用于在彩虹表文件中的任一彩虹表与预设彩虹表的参数相匹 配的情况下， 从哈希值文件中获取一个待恢复的哈希值 ； 说 明 书 CN 103400072 A 8 4/12 页 9 判断单元， 用于判断能否利用 GPU 对该待恢复的哈希值进行密码恢复 ； 第一哈希值密码恢复单元， 用于利用 GPU 对该待恢复的哈希值进行密码恢复， 直至恢 复完成哈希值文件中所有待恢复的哈希值的。

　　34、密码。 0018 进一步的， 所述彩虹表生成单元包括 ： 第一链首值生成子单元， 用于随机生成一条彩虹链链首值 T1； 第一计算子单元， 用于对所述 T1进行哈希运算得到 HT1； 第二计算子单元， 用于对所述 HT1进行截短函数运算得到 RHT1； 第一链尾值生成子单元， 用于将RHT1重复进行预定次数的哈希运算和截短函数运算， 得 到彩虹链链尾值 ； 第一彩虹链形成子单元， 用于根据所述彩虹链链首值和所述彩虹链链尾值形成彩虹链 并保存于彩虹表 ； 第一核函数设置子单元， 用于根据 GPU 的计算能力设置执行彩虹链生成核函数需分配 的块数和块中的线程数 ； 第二链首值生成子单元， 用于随机生。

　　35、成多个彩虹链链首值并保存于 GPU 显存中 ； 第二链尾值生成子单元， 用于调度彩虹链生成核函数的线程， 对所述多个彩虹链链首 值并行进行预定次数的哈希运算和截短函数运算， 得到与其对应的彩虹链链尾值 ； 第二彩虹链形成子单元， 用于根据所述多个彩虹链链首值及其对应的彩虹链链尾值分 别形成彩虹链并保存于彩虹表。 0019 进一步的， 所述第一哈希值密码恢复单元具体包括 ： 第二核函数设置子单元， 用于根据 GPU 的计算能力设置执行预计算核函数和在线分析 核函数各自需分配的块数和块中的线程数 ； 第一链首节点值生成子单元， 用于将所述待恢复的哈希值和各猜测位置相结合进行截 短函数运算后得到对应。

　　36、的各链首节点值 Spos（P） ； 第一链尾节点值生成子单元， 用于调度预计算核函数的线程， 对所述各链首节点值 Spos （P） 并行进行从其对应的猜测位置后移一个节点至彩虹链链尾位置前移两个节点的彩虹链 节点值的还原计算， 得到所述各 Spos（P） 对应的链尾节点值 Epos（P） ； 第一链首节点值获取子单元， 用于根据二分查找法在彩虹表中查找链尾节点值与所述 各 Epos（P） 相同的彩虹链， 并获取该些彩虹链的各链首节点值 Sj（P） 及根据各 Epos（P） 、 各 Sj（P） 和猜测位置确定的在彩虹链上的各相应位置值 Ij（P） ； 第二链尾节点值生成子单元， 用于调度在线、阶段核函数的线程， 对所述各 Sj（P） 并 行进行从彩虹链链首位置至 Ij（P） 前移一个节点的彩虹链节点值的还原计算， 得到所述各 Sj（P） 对应的链尾节点值 Ej（P） ； 第一预判定哈希值生成子单元， 用于任取一个 Ej（P） 进行哈希运算得到第一预判定哈 希值 ； 第一密码存储子单元， 用于当所述第一预判定哈希值与待恢复哈希值相同时， 将与此 所述第一预判定哈希值对应的密码进行存储 ； 其中， 猜测位置为从彩虹链链首位置至彩虹 链链尾位置前移两个节点之间的位置。 0020 进一步的， 本装置还包括第二哈希值密码恢复单元， 用于当不能利用 GPU 对该待 恢复的哈希值进行密码恢复， 。

　　38、则利用 CPU 对该待恢复的哈希值进行密码恢复， 具体包括 ： 说 明 书 CN 103400072 A 9 5/12 页 10 第二链首节点值生成子单元， 用于将待恢复哈希值和猜测位置相结合进行截短函数运 算后得到链首节点值 Spos（P） 第三链尾节点值生成子单元， 用于将所述 Spos（P） 进行从猜测位置后移一个节点至彩 虹链链尾位置前移两个节点的节点数次的哈希运算和截短函数运算得到的链尾节点值 Epos （P） ； 第二链首节点值获取子单元， 用于根据二分查找法在彩虹表中查找链尾节点值与各 Epos（P） 相同的彩虹链， 并获取该些彩虹链的各链首节点值 Sj(P) 及根据各 Epos。

　　39、（P） 、 各 Sj （P） 和猜测位置确定的在彩虹链上的各相应位置值 Ij（P） ； 彩虹链元素获取子单元， 用于根据 Sj(P) 和 Ij（P） 分别获得一个彩虹链链首元素值 Sjs （P） 及其在彩虹链上的相应位置元素值 Ijs（P） ； 预判定值生成子单元， 用于根据 Sjs（P） 进行自彩虹链链首位置至 Ijs（P） 前移一个节 点的节点数次的哈希运算和截短函数运算后得到预判定值 ； 第二预判定哈希值生成子单元， 用于将所述预判定值进行哈希运算后得到相应的第二 预判定哈希值 ； 第二密码存储子单元， 用于当所述第二预判定哈希值与待恢复的哈希值相同时， 将与 所述第二预判定哈希值对应的。

　　40、密码进行存储 ； 其中， 猜测位置为从彩虹链链首位置至彩虹链链尾位置前移两个节点之间的位置。 0021 进一步， 本装置还包括优化配置单元， 用于对系统进行优化配置， 其中具体包括 ： 彩虹表参数优化配置子单元， 用于对与彩虹表相关的参数进行优化， 包括在密钥空间 允许的情况下， 增加每个彩虹表的彩虹链的个数和彩虹表的个数 ； 截短函数优化配置子单元， 用于对截短函数进行优化， 包括 ： 设置截短函数为； 其中， Si,j(P) 为第 i 条彩虹链第 j 位置的初始节点值， 1 i c, 1 j l, c 为每 个彩虹表中的彩虹链的个数， l 为彩虹链的长度， N 为密码空间大小 ； GPU 。

　　41、计算轮数优化配置子单元， 用于对 GPU 的计算轮数进行优化， 包括在 GPU 设备计算 功能级的主版本号分别为 1， 2， 3 的情况下， 配置块中线， 块数分别 为设备上处理器数量的 3 倍， 3 倍， 16 倍。 0022 本发明提出的哈希值密码的恢复方法和装置， 利用CPU和GPU分别生成彩虹表， 将 GPU 的并行计算能力和彩虹表算法相结合来恢复哈希值的密码， 大大降低了哈希值密码的 恢复时间。 附图说明 0023 图 1 是本发明哈希值密码的恢复方法第一实施例的流程图 ； 图 2 是本发明哈希值密码的恢复方法第二实施例的流程图 ； 图3是本发明。

　　42、哈希值密码的恢复方法第四实施例中利用GPU对该待恢复的哈希值进行 密码恢复的流程图 ； 图 4 是本发明哈希值密码的恢复装置第一实施例的结构示意图 ； 图 5 是本发明哈希值密码的恢复装置第二实施例的结构示意图 ； 图 6 是本发明哈希值密码的恢复装置第四实施例中的第一哈希值密码恢复单元的结 说 明 书 CN 103400072 A 10 6/12 页 11 构示意图。 具体实施方式 0024 为使本发明的上述目的、 特征和优点能够更加明显易懂， 下面结合附图和具体实 施方式对本发明作进一步详细的说明。 0025 参照图1， 示出了本发明哈希值密码的恢复方法第一实施例的流程图。 其中包括如 下。

　　44、le） 。 0027 S13， 利用 CPU 和 GPU 分别生成彩虹表并按顺序存储于彩虹表文件中。 0028 S15， 在彩虹表文件中的任一彩虹表与预设彩虹表的参数相匹配的情况下， 从哈希 值文件中获取一个待恢复的哈希值。 0029 具体的， 在彩虹表文件中获取一个彩虹表， 将其与根据需要而预设的彩虹表的各 参数进行对比， 检验是否匹配。 0030 S17， 根据系统硬件信息判断能否利用 GPU 对该待恢复的哈希值进行密码恢复， 如 果判断结果为是， 转 S19。 0031 S19， 利用 GPU 对该待恢复的哈希值进行密码恢复， 直至恢复完成哈希值文件中所 有待恢复的哈希值的密码。 003。

　　45、2 在本发明提出的哈希值密码的恢复方法第一实施例中， 利用 CPU 和 GPU 分别生成 彩虹表， 将 GPU 的并行计算能力和彩虹表算法相结合来恢复哈希值的密码， 大大降低了哈 希值密码的恢复时间。 0033 参照图 2， 示出了本发明哈希值密码的恢复方法第二实施例的流程图， 本方法第二 实施例是在上述方法第一实施例基础上的改进， 在 S11 之后， 还包括如下步骤 ： S12， 对系统进行优化配置， 包括对与彩虹表相关的参数进行优化， 对截短函数进行优 化和对 GPU 的计算轮数进行优化， 其中， 对与彩虹表相关的参数进行优化具体为 ： 在密码空间允许的情况下， 增加每个彩虹表 中的彩虹链。

　　46、的个数和彩虹表的个数。 0034 其中， 设每个彩虹表中的彩虹链个数为， 彩虹链长度为 ， 彩虹表个数为 ， 密码 空间总大小为。 0035 对于一个的彩虹表， 其查找成功率为 ：， 其中 （， ） ，个表的查找成功率满足如下方程 ：； 同时结合 GPU 的块内线程数的约束 （块内线 的幂） ， 可确定=4096。因此， 在密码空间允许的 说 明 书 CN 103400072 A 11 7/12 页 12 情况下， 增大及 更容易提高彩虹表的性能。 0036 对截短函数进行优化具体为 ： 保证截短函数值在 N 上是均匀分布的。 0037 设置截短函数为； 其中， Si,j(P) 为第。

　　47、 i 条彩虹链 第 j 位置的初始节点值， 1 i c, 1 j l, c 为每张彩虹表的彩虹链的个数， l 为彩 虹链的长度， N 为密码空间大小。 0038 对GPU的计算轮数进行优化具体为 ： 由于GPU的显存大小的限制， 需要将彩虹表分 解到 GPU 可完成有效计算的最大单位 （块内线程数 thread 块数 block） 逐一完成。从数 据传输效率和 GPU 并行计算能力的角度来考虑， 应尽量扩大每次 SP（流处理器） 传输的数 量， 以避免通讯开销。 0039 因此， 在GPU设备计算功能级的主版本号分别为1， 2， 3的情况下， 配置块中线、， 块数分别为设备上处理器数量的 3 倍， 3 倍， 16 倍。 0040 进一步的， 将介绍本发明哈希值密码的恢复方法第三实施例， 该方法第三实施例 是在上述方法第二实施例基础上的改进。 0041 在该方法第三实施例中， S13 具体包括利用 CPU 生成彩虹表和利用 GPU 生成彩虹 表。 0042 其中， 利用 CPU 生成彩虹表， 具体包括 ： S1311， 随机生成一条彩虹链链首值 T1。 0043 S1312， 对 T1进行哈希运算得到 HT1。 0044 S1313， 对 HT1进行截短函数运算得到 RHT1。 0045 S1314， 将RHT1重复进行预定次数的哈希运算和截短函。

　　49、数运算， 得到彩虹链链尾值， 其中， 预定次数为配置的彩虹链的长度值。 0046 S1315， 根据S1311中生成的彩虹链链首值和S1314中生成的彩虹链链尾值形成彩 虹链并保存于彩虹表中。 0047 其中， 利用 GPU 生成彩虹表， 具体包括 ： S1321， 根据 GPU 的计算能力设置执行彩虹链生成核函数需分配的块数 （block） 和块中 的线程数 （thread） 。 0048 其中， GPU 的计算能力是指 GPU 中的运算平台 （CUDA， Compute Unified Device Architecture） 的计算能力。 0049 S1322， 随机生成多个彩虹链链首值并保存于 GPU 显存中。 0050 S1323, 调度彩虹链生成核函数的线程， 对多个彩虹链链首值并行进行预定次数 的哈希运算和截短函数运算， 得到与多个彩虹链链首值对应的彩虹链链尾值。 其中， 预定次 数为配置的彩虹链的长度值。 0051 S1324,根据S13。

　　本发明提供了一种哈希值密码的恢复方法和装置，该方法包括：配置系统初始化信息；利用CPU和GPU分别生成彩虹表并按顺序存储于彩虹表文件中；在彩虹表文件中的任一彩虹表与预设彩虹表的参数相匹配的情况下，从哈希值文件中获取一个待恢复的哈希值；判断能否利用GPU对该待恢复的哈希值进行密码恢复；如果判断结果为是，则利用GPU对该待恢复的哈希值进行密码恢复，直至恢复完成哈希值文件中所有待恢复的哈希值的密码；其中，系统初始化信息包括哈希算法类型、与彩虹表相关的信息等。本发明提供的方法和装置，利用CPU和GPU分别生成彩虹表，并结合GPU和彩虹表算法来恢复哈希值密码，可大大降低哈希值密码的恢复时间。

　　其中，系统初始化信息包括哈希算法类型（hash），字符集（charset），字符集文件（charsetfile），密码口令的最小长度（minplainlen）和最大长度（maxplainlen），彩虹链的长度（chainlen）,每个彩虹表的彩虹链的个数（chaincount），需生成的彩虹表的个数（tablecount），初始彩虹表表号索引（tableindex），彩虹表存储路径（filepath），待恢复的哈希值文件（inputfile）和恢复结果文件（outputfile）。

　　其中，系统初始化信息包括哈希算法类型（hash），字符集（charset），字符集文件（charsetfile），密码口令的最小长度（minplainlen）和最大长度（maxplainlen），彩虹链的长度（chainlen）,每个彩虹表的彩虹链的个数（chaincount），需生成的彩虹表的个数（tablecount），初始彩虹表表号索引（tableindex），彩虹表存储路径（filepath），待恢复的哈希值文件（inputfile）和恢复结果文件（outputfile）。