哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　单向哈希密钥链简析 杭州电子科技大学 邓淑华 （陷门）单向函数 若对于函数f有以下条件： ?给定自变量x，计算y=f(x)是容易的； ?给定y，获取x，使得y=f(x)是困难的(所谓计算困难是指计算上相当复杂，已无实际意义。)； ?存在δ，已知δ时，对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。 注： 1*.仅满足?、?两条的称为单向函数；第?条称为陷门性,δ称为陷门信息。满足以上三条的函数f称为陷门单向函数。 （陷门）单向函数 2*.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密钥记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者(当然可以通过不安全信道传送)；由于设计者拥有Sk。他自然可以解出 。 常见的单向函数（困难问题） (1)大整数分解问题（factorization problem） 若已知两个大素数p和q，求n=pq是容易的，而由n求p和q则是困难的。 (2)离散对数问题（discrete logarithm problem） 给定一个大素数p，p-1含另一个大素数因子q，则可构造一个p-1阶乘法群 （Zp是一个有限域,除去其中的零元则构成p-1阶循环群），它是一个p-1阶循环群。设g是 的一个生成元，1gp-1。已知x，求 是容易的，而已知y、g、p，求x使得 成立则是困难的。 常见的单向函数（困难问题） (3)多项式求根问题 有限域 上的一个多项式： 已知 和 ，求 是容易的，而已知 ，求 则是困难的。 (4)二次剩余问题（quadratic residue problem） 已知 和 ，求满足 的 是容易的；而在 的分解未知时，已知 和 ，求满足 的 则是困难的。 常见的单向函数（困难问题） (5)背包问题（knapsack problem） 给定向量 求和式 是容易的，而由 和 ，求 则是困难的。 当然，还有其他一些单向函数，而更多的单向函数还有待于发掘和应用。 Hash函数 Hash，一般翻译做散列，也有直接音译为哈希的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 Hash函数： 简单的说，就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 Hash函数 Hash函数的性质： ?输入可以是任意长； ?输出是固定长； ?对于给定的x，计算h(x)比较容易； ?对任意给定的Hash值z，找到满足h(x)=z的x在计算上是不可行的，这就是函数的单向性； ?已知x，找到y 满足h(y)=h(x)在计算上是不可行的，这称为抗弱碰撞性； Hash函数 ?对任意两个不同的输入x、y，使h(y)=h(x)在计算上是不可行的，这称为抗强碰撞性； 注： 碰撞性是指对于两个不同的消息x和y，如果它们的Hash值相同，则说发生了碰撞。 单向哈希密钥链 一个单向链 若满足如下条件： 对任意的 ，有 成立，这里 是密码体制中常用的一个单向Hash函数。 那么，该单向链也称为哈希链。 通常，密钥分发者(generator)随机选择一个 作为该哈希密钥链的根密钥（或者说种子密钥）。 然后，通过哈希函数 对这个种子密钥反复迭代计算出该链中其它密钥。最后算出的 我们称之为终值。这个值 通常公开，间接标识了拥有种子密钥的用户的身份。 单向哈希密钥链 如下图所示为一个标准哈希密钥链： 可信性验证： 我们假使验证者（verifier）获得一个生成的哈希链的可信值 ，通过判断 的值是否为 来判断一个输入的检验值 的真实性。如果相等，则是可信的，否则不可信。 注意到，对任意一个已知（可信）的 ，其中 ，对其迭代 次后的值为 的话， 也是可信的。 单向哈希密钥链 遍历性： 当密钥发布者（generator）公布了哈希链中所有的密钥值，我们就称遍历了该哈希链。 目前，generator主要有两种遍历方式： 其一，generator在存储器中存储该哈希链的所有密钥值； 其二，generator通过根密钥与哈希函数验证每个密钥值。 单向哈希密钥链 优缺点： 单向性在显著改善安全的同时，也面临计算复杂度高（当迭代次数很大时）以及存储与传输开销大等缺点。特别是对于在无线传感网络等资源受限的环境下，这种缺陷更加明显。 所以，有学者提出分层单向密钥链机制。 分层单向哈希密钥链 分层单向哈希密钥链（Hierarchical One-Way Chains）：顾名思义，就是包含两层或更多哈希密钥链的密钥链。 第一层称为基本链或主要链（primary chain），它是其下一层（secondary chain）的基础或基准。 我们称由primary chain中第i个密钥生成的新链为 secondary chain 中的第i个链。不同层的链使用的单向函数可以相同也可以不同。 secondary chain中的第i个链的所有值的发布，必须在第i+1个链中任意一个值（肯定也包含基本链中的第i+1个值）发布之后。并且，primary chain中的第i个值的发布时机处于二者之间。 分层单向哈希密钥链 分层单向哈希密钥链 也称，secondary chain是低层链，primary chain是高层链。 低层链的作用是验证广播信息，而高层链则是起到分配和验证低层链的承诺（commitment）。 在高层链用足够长的时间间隔（这个时间间隔可以覆盖一个传感器网络的生命周期）分割时间线的同时，保证低层密钥链有足够短的时间间隔，使得接受与认证广播信息之间的时延在可以容忍的范围。 而传感器网络的生命周期被连续地分成n份，分别记为 ，高层链有 个元素（密钥） 分别为 。 分层单向哈希密钥链 分层单向哈希密钥链 每个密钥 应用在高级（high-level）时间间隔 内，而每个密钥 被用在低级（low-level）时间间隔 内。 和 是不同的伪随机函数。 每个承诺（commitment） 在时间间隔 内被分配。 分层单向哈希密钥链 每一个 与时间间隔 联系在一起。我们记 的起始时间为 ，因此高层链的起始时间就是 。 因为高层链的持续时间相对于网络时延、同步误差（clock discrepancie）很大，我们决定在时间段 公布 。假设节点在t时刻收到了密钥 ，当 ,说明还没有到达 时刻，也就是基站还没有公布 。基站是在 时刻才会公布密钥 。其中， 是基站与节点之间的最大的同步误差。 分层单向哈希密钥链 每一个 进一步被分成 ，如果需要，基站为每个 产生一个低级链，由 生成 ，其中 用于验证在时间段 内的广播消息，而密钥链 的开始时间已被设置为 为了使传感器在时间段 内使用低层链 ，必须对承诺（commitment） 进行验证。 分层单向哈希密钥链 分层单向哈希密钥链 其中， 下面没有子链，因为它代表整个分层哈希链的验证值（verification value）。 一个不足之处是，这种方案中的验证是分期的，而generator仅仅在主链的转换过程中发送的验证值（authentication value）。另一个明显不足是，对第二层（secondary chain）的终值的验证（通过承诺）比较繁琐。如果终值的承诺（commitment）发生丢失，验证者就不得不等到该低层链的生成密钥被修复后公布才能继续。所以一种折中方案是：在primary chain的少的转换（infrequent transitions）与小的认证时延（a short authentication delay）之间找到平衡。 Thank You！ 密钥公布时间表 * * * * * * * * * * * * * * * *