09数论的应用(编辑修改稿)

09数论的应用(编辑修改稿)内容摘要：

由式 (2)定义的仿射加密方法，只要知道两对（不同的）相对应的明文和密文 P1， E1与 P2， E2，就可以求出解密方法。 事实上，由式 (2)及已知的对应关系，得到 E1  aP1  b (mod M)， E2  aP2  b (mod M)， （ 4） 所以 E2  E1  a(P2  P1) (mod M)。 以 x  ai (mod M)， 0  ai M， 1  i  r 表示同余方程 x(P2  P1)  E2  E1 (mod M) 的全部解，并且记 bi  E1 – aiP1 (mod M)， 0  bi M， 则 ai与 bi（ 1  i  r）就可能是式 (2)中所使用的 a 和 b。 当 (P2  P1, M) = 1 时，这样的 ai与 bi只有一组，当 (P2  P1, M) 1时，为了确定出正确的 a 与 b，首先，利用 (a， M) = 1 删去某些 ai与bi，其次，用它们验证式（ 4）是否成立，并用它们试译部分密文，就可以确定正确的 a 与 b。 将确定的 a， b代入式 (3)，就得到解密公式。 在现实生活中，无论使用什么语言符号传送信息，各个符号的出现频率总是有差别的。 例如，有统计数字表明，在报刊文章中，英语的 26 个字母中，出现频率较高的，依次是 e， t， a， o等；较低的，依次是 z， q， j， x等。 这样，在对密文中的每个字母的出现频率进行统计之后，可以对于明文字母和密文字母之 间的对应关系作出猜测，然后试行解密。 例 3 已知明文由 26个英文字母 a， b，  ， y， z（分别与 00， 01， ， 24， 25对应）及符号“。 ”和“。 ”（分别与 26 和 27 对应）组成，用这 28 个符号写成的正常英文中，出现频率最高的依次是。 ， e 与 t。 在对一组密文做了统计分析之后，发现密文中出现频率最高的三个符 189 号依次是 b， ?与 i， 试求解密公式。 解 设解密公式为 P  a E  b  (mod 28)， 0  P 28， 则由已知的符号与数字的对应关系，比较出现频率的高低，可以假定“ !”与“ e”分别对应 着“ b”与“ ?”，于是 26  a 1  b  (mod 28)， 4  a 27  b  (mod 28)， 将两式相减，得到 26a  22 (mod 28)。 这个同余方程有两个解： a1  11 (mod 28)， a2  25 (mod 28)， 相应的，b1  15 (mod 28)， b2  1 (mod 28)。 这样，得到了两个可能的解密方法： (ⅰ ) P  11E  15 (mod 28)， 0  P 28， (ⅱ ) P  25E  1 (mod 28)， 0  P 28。 再通过比较出现频率，又可假定 i与 t 对应（它们对应的数字分别是 8 与 19），将这两个数字分别代入 (ⅰ )与 (ⅱ )进行验证，可知解密方法 (ⅰ )是正确的。 习 题 三 1. 利用例 1 中的加密方法，将“ ICOMETODAY”加密。 2. 已知字母 a， b，  ， y， z，它们分别与整数 00， 01，  ， 24，25 对应，又已知明文 h 与 p分别与密文 e 与 g对应，试求出密解公式： P  a E  b  (mod 26)， 并破译下面的密文：“ IRQXREFRXLGXEPQVEP”。 第四节 RSA 加密方法 对信息进行加密的目的，当然是希望这个信息的内容不被某一部分人（以后，我们称他们为“敌方”）了解；同时，这个信息的内容应该能够被另一部分人（以后，我们称他们为“友方”）很容易地了解。 190 上一节所介绍的仿射加密方法具有计算方便的优点，其中，参数 a 和b 是两个关键的数据。 我们已经看到，利用统计的方法，能够很容易地确定这两个数据，此外，为了提高保密性，即增加敌方从密文得到密文的困难程度，需要经常更换 a 和 b 的数值，于是，就要随时把这些数值及时通知友方，这就增加了敌方获取 a 和 b 的数值的可能性。 因 此，仿射加密方法的保密性（安全性）是不好的。 在这一节，我们介绍一种加密方法，在很大程度上克服了上述缺点。 从实用的观点来看，保密是有时间性的。 如果加密后的文件在一个足够长的时间内不被敌方了解，就可以认为这个加密是安全的。 当我们谈论“把某一份文件加密，使它不被敌方了解”的时候，其实是包含着一个时间界限的。 就是说，这里指的是，在某一个时期内，加密后的文件不被敌方了解。 例如，一个发动某次战役的具体时间，在战役开始之前是绝对要保密的，但是，战役结束之后，就不存在保密的必要了。 用 P 和 E 分别表示明文和密文，从数学的观 点来看文件加密的问题，加密方法和解密方法其实就是两个满足下述条件的函数 f(P)和g(E)： (ⅰ ) 对于某个整数集合中的数 P，有确定的函数值 E = f(P)与之对应，同时，计算 f(P)是容易的： (ⅱ ) 对于某个整数集合中的数 E，有确定的函数值 P = g(E)与之对应，同时，计算 g(E)是困难的； (ⅲ ) 如果掌握了关于函数 g(E)的某种条件（信息），计算 g(E)是容易的。 在这一节，我们要介绍满足上述三个条件的一个加密方法，它以下面的命题为基础。 命题 已知两个素数，计算它们的的乘积是容易的；但 是，已知两个大素数的乘积，求这两个素数却是非常困难的。 从这一个命题出发， R. L. Rivest 与 A. Shamir， L. M. Adleman 提出了下面的加密方法。 RSA 加密方法 Ⅰ 参数的选取 随机地选取大素数 p， q，计算 n = pq， (n) = (p  1)(q  1)， 191 再随机地取正整数 e， (e, (n)) = 1， 并计算 d， 使得 ed  1 (mod (n))。 (1) 公开 n， e，供加密使用（称它们为 RSA加密钥）；将 p， q， (n)和 d 保密（称它们为保密钥）。 Ⅱ 加密 设明文是 P， 0  P n， 则与之相应的密文是 E  P e (mod n)， 0  E n。 (2) Ⅲ 解密 已知密文 E 时，明文 P 由下式确定： P  E d (mod n)， 0  P n。 (3) 我们将以上设计的 RSA加密方法简记为 RSA(n, e)。 下面的定理给出了解密方法的依据。 定理 1 设 n = p1p2 pk 是 k 个不同的素数之积， e 与 d是正整数，(e, (n)) = 1， 并且式 (1)成立 ， 则对于任意的 aN，有 a ed  a (mod n)。 证明 对于任意的 pi（ 1  i  k） ， 若 (a, pi) = 1， 则由 Euler 定理可知 1ipa  1 (mod pi )。 由式 (1)， ed = r(n)  1 = r (p1  1)  (pk  1)  1，其中 r是非负整数，所以， a ed  a (mod pi )， i = 1, 2,  , k。 (4) 当 (a, pi) 1 时，这个 同余式当然也成立。 由于 p1, p2,  , pk 是互不相同的素数，由式 (4)及同余式的性质即可证得定理。 证毕。 一般来说，从密文求明文，有许多可能的方法，例如： (ⅰ ) 将 n分解因数，求出 p 和 q， 使得 n = pq， 然后计算 (n) = (p  1)(q  1)， 利用辗转相除法求出 d，使得式 (1)成立。 再利用式 (3)从密文 E计算明文 P。 容易看出，用这种方法从密文求出明文的难度，就是将大整数分解因数的难度。 (ⅱ ) 如果能用某种方法（不是先将 n分解因数）求出 (n)，则也可以从密文 E 求出明文 P。 因为， 利用辗转相除法，由 e 可以求出 d使得式 (1)成立，于是，由式 (3)可以从密文 E 计算明文 P。 但是，如果(n) = (p  1)(q  1)是已知的，那么，有 pq = n 以及 192 p  q = pq  (n)  1 = n  (n)  1。 由此，可以利用一元二次方程的求解公式求出 p 和 q。 这说明，这种方法的难度不会低于将大整数分解因数的难度。 除此之外，还有一些别的方法。 对于这些方法的分析，有兴趣的读者可以查阅关于密码学的文献。 总的来说， RSA加密方法被认为有较好的安全性。 RSA加密方法的特点， 在于加密方法是公开的，而且加密时所使用的参数也是公开的。 这是它与仿射加密方法的重要区别。 通常，称具有这种特点的加密方法为公钥加密方法。 公钥加密方法使得信息的加密传送更为方便。 例如，每个单位或个人可以像公布电话号码一样公布自己的 RSA加密钥。 于是，凡是要向它或他发送加密信息的单位或个人都可以使用这些参数发送加密信息。 此外， RSA加密方法还有更广泛的用途。 下面介绍的数字签名的方法就是一个例子。 数字签名 在社会生活中，在处理具体事件时，常需要当事人进行签证（签名），以保证他做出的许诺或送出的信息的可靠性与合法 性。 例如，在签署文件时，由当事人签名，盖章，签署日期以及重要的特殊记号，常是不可少的环节。 这样的签证，应该满足一定的要求。 假设 A 签证一个文件给 B，那么， (ⅰ ) B 应该能够确定这是否 A 的签证 ； (ⅱ ) 任何其他人，无法伪造 A 的签证，即 A 有其独特的签证方式 ； (ⅲ ) 有一个仲裁签证是否由 A 发出的方法，例如，当 A 否认这个签证时，这样的方法可以鉴定签证的真伪。 下面我们说明， RSA加密方法可以用来进行签证，不需要当事人到场。