翻译:中国科学技术大学信息安全专业老师 费尔马小定理对于每一个a≠0modp,p是素数,有ap≡ I mod p 这个定理表示,任何一个以p为模的非零元素的乘法阶必定是p-1的因子。这个事实 被用于构造相当多的密码算法。这些算法的安全性常常是相关的,在少数场合是等价的,来 自数论中的下述问题中的任何一个都是难解的 离散对数问题(DLP):给定一个作为模的素数p,基数a和值y,根据等式 y≡a3modp,求出y的离散对数x n次方根问题:给定一个整数m,n和a,求出一个整数b,使它满足 a=b"modm。解b就叫做q模m的n次方根 因式分解问题:给定一个整数(合数)n,找出它的素数因子 在参数的正确选择情况下,这些问题是许多密码算法的合适的基础。然而,并不是这些 问题的所有实例都是难解的。很明显,如果p或者n是比较小的整数,那么这些问题就可 以在合理的时间范围内采用穷举搜索来求解。目前,二进制512位的整数已被认为是位数较 短的整数了,一般都推荐使用1024位整数,当然,如果你能够容忍由于算术运算占用更长 的时间而引起性能的下降,你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些 问题的难度也依赖于p和n的结构。(为了进一步追究这个课题,你必须放下这本书,而寻 找一些更专业化的数学方面的书籍来阅读。) 122密码机制 密码机制是密码方案的最基本的构造模块。它们被用在密码协议中,且依赖于好的密钥 管理来提供有效的保护。最频繁应用于计算机安全的密码机制是 加密( encryption)算法 数字签名( digital signature)方案 ·完整性检查功能(密码散列函数,即hash函数)。 为了舍弃传统密码,我们将以相反的顺序来介绍这些概念。 12.2.1完整性检查功能 依赖于特殊应用的需求,对密码散列函数的要求也有一些微妙的差别。我们列出了散列 函数h的一些基本性质,由此来展开这一节的讨论 容易计算:给定x,容易计算h(x)。 ·压缩:对于任意输入长度的x,函数h最后都生成固定长度n的输出h(x)。 预映射抗拒性(单向性):给定一个值y,为了找到x满足h(x)=y,通常在计算 上是不可行的。 第2次预映射抗拒性(弱冲突抗拒性):给定输入x和h(x),求出另外一个x',且 第4页共19页 创建时间:2003/7/91446:00翻译：中国科学技术大学信息安全专业老师 第 4 页 共 19 页 创建时间：2003/7/19 14:46:00 费尔马小定理 对于每一个 a  0mod p ， p 是素数，有 a p p 1mod 1  − 。 这个定理表示，任何一个以 p 为模的非零元素的乘法阶必定是 p −1 的因子。这个事实 被用于构造相当多的密码算法。这些算法的安全性常常是相关的，在少数场合是等价的，来 自数论中的下述问题中的任何一个都是难解的： ·离散对数问题（DLP）： 给定一个作为模的素数 p ，基数 a 和值 y ，根据等式 y a p x  mod ，求出 y 的离散对数 x 。 · n 次方根问题： 给定一个整数 m ， n 和 a ，求出一个整数 b ，使它满足 a b m n  mod 。解 b 就叫做 a 模 m 的 n 次方根。 ·因式分解问题： 给定一个整数（合数） n ，找出它的素数因子。 在参数的正确选择情况下，这些问题是许多密码算法的合适的基础。然而，并不是这些 问题的所有实例都是难解的。很明显，如果 p 或者 n 是比较小的整数，那么这些问题就可 以在合理的时间范围内采用穷举搜索来求解。目前，二进制 512 位的整数已被认为是位数较 短的整数了，一般都推荐使用 1024 位整数，当然，如果你能够容忍由于算术运算占用更长 的时间而引起性能的下降，你可以使用更长的整数。长度不是你必须考虑的唯一方面。这些 问题的难度也依赖于 p 和 n 的结构。（为了进一步追究这个课题，你必须放下这本书，而寻 找一些更专业化的数学方面的书籍来阅读。） 12.2 密码机制 密码机制是密码方案的最基本的构造模块。它们被用在密码协议中，且依赖于好的密钥 管理来提供有效的保护。最频繁应用于计算机安全的密码机制是： ·加密（encryption）算法， ·数字签名（digital signature）方案， ·完整性检查功能（密码散列函数，即 hash 函数）。 为了舍弃传统密码，我们将以相反的顺序来介绍这些概念。 12.2.1 完整性检查功能 依赖于特殊应用的需求，对密码散列函数的要求也有一些微妙的差别。我们列出了散列 函数 h 的一些基本性质，由此来展开这一节的讨论： ·容易计算： 给定 x ，容易计算 h(x) 。 ·压缩：对于任意输入长度的 x ，函数 h 最后都生成固定长度 n 的输出 h(x) 。 ·预映射抗拒性（单向性）： 给定一个值 y ，为了找到 x 满足 h(x) = y ，通常在计算 上是不可行的。 ·第 2 次预映射抗拒性（弱冲突抗拒性）： 给定输入 x 和 h(x) ，求出另外一个 x' ，且