数论与信息安全

数论与信息安全内容摘要：

53 m o d 1 1xxxx  4. 求解 联立的线性同余式 : 欧拉定理和费尔玛定理 模 m的完全剩余集 : (1) 欧拉函数 设 m0为一正整数 , 记  (m)为小于 m且与 m互素的正整数的个数 , 并称其为 m的欧拉函数 . 定理 若 m1， m2互素，则  (m1m2)= (m1)  (m2) 若kkpppm2121, 则 )())(()(kpppmm11111121  定理 (2) 欧拉定理 定理 (Euler) 若 a与 m互素，则 a(m) 1 mod m 推论 (Fermat) 若 p是素数， (a, p)=1, 则 ap1 1 mod p 定理 (Fermat) 若 p是素数，则 apa mod p 故当 p是素数，则 a1ap2 mod p 例 3 .8 求解 3 102  ? mo d 1 1 . 例子： 例 3 .10 若 a , b 是正整数， p 是素数，则 pbax m od 的解是 pbaxpm od2 例 求 21 mod 11. 同余类方程 mbax m o d 有解的充分必要条件为 gcd{ a, m } | b ，并且解为 mbax m o d 其中， a 为 a 模 m 的逆 . (3) 应用 例 解方程： 7x22 mod 31 习题 1. 解方程： 7x5 mod 23 2. 求 31 mod 13. 3. 7 威尔森定理 定理 (Wilson) 若 p是素数，则 (p1)! 1 mod p 反之，如果整数 p满足上式， 则 p是素数 . 平方剩余 例子 设有下列同余式 : x21, x22, x23, x24 mod 5 求解 ? 引理 若 p是奇素数 , p与 a互素 , 则 x2a mod p 或无解 , 或有两个模 p不同余的解 . 并且 , 如果1xp是一解 , 则 另一解为 px. 定理 若 p是奇素数 , 则 1, 2, . . ., p1正好有 (p1)/2个是模 p的平方剩余 . 即为： 1, 2, . . ., p1中模 p与 12, 22, …, [1/2( p1)]2同余的数 . 例如 ：取 p=11，求模 11的平方剩余 (1ap). 4. 公钥密码 引言 公开密钥密码学是密码学历史上最大的而且也 是唯一真正的革命 . 传统密码编码技术 (包括分组密码 )建立在替代 和置换基础之上 . 它们的加密和解密是对称的 . 1976年， Diffie 和 Hellman 在这方面取得了惊人的突破：他们开创的公钥密码技术同时解决了这两个问题 . 但常规的密码存在两个重大问题 :  密钥管理和分配问题  数字签名问题 原理 ： 加密密钥和解密密钥不同，而且加密密钥公开，解密密钥保密 . 例如：  甲和乙同时选用同一个公钥密码系统；  乙将公开密钥传送给甲；  甲用此公钥加密他的信息并传送给乙；  乙用他自己的私人密钥解密甲传来的加密文件 . 需要澄清的问题：  不要误认为公钥密码加密在防止密码攻击方面 更安全可靠（任何加密方案的安全性都依赖于密 钥的长度和加密算法的计算复杂度）；  不要误认为公钥密码加密使得常规加密技 术过时 （ 公钥密码加密开销更大 ， 所以公认 为仅用于密钥管理和数字签名 ） ；  不要误认为公钥密码技术使得密钥管理非 常简单 ， 事实上 ， 仍需要一个代理中心 ， 而 且整个过程既不简单 ， 也不是更有效 . 采用的技术的核心： 基于单向陷门函数 : 加密容易 , 但解密却相当难 . 其中 , 陷门就是解密密钥 . 例如利用求 mod p (素数 ) 的离散对数的困难度 :  甲和乙在 {1， 2， 3， … ， p1}各中选取一 数作为 x甲 和 x乙 并计算 pbypby xx m o d m o d 乙甲 乙甲 和   乙将 y乙 通知甲 , 而且甲将 y甲 通知乙。  双方得到通信密钥 : pbkxx m o d 乙甲甲乙 （ Rivest, Shamir amp。 Adleman） 基于：数论中的 Euler 定理和因子分解问题是计算上困难的问题 . RSA公钥密码 RSA 加密算法 操作过程： 1. 取两个充分大的素数 p, q。 2. 计算 n=pq (公开 ), 和 (n)=(p1)(q1) (保密 )； 3. 随机选取整数 e (公开 )， 满足 gcd(e, (n))=1； 4. 计算 d (保密 ), 满足 de 1 mod (n) RSA 加密算法 对明文的加密过程： 1. 将明文 (二进制数串 )按长度不大于 log2n分组； 2. 对每一组 (设为 mn)加密： 加密算法 : c=E(m) me mod n 对明文的解密过程： 解密算法 : m=D(c) cd mod n 例 取 p=43, q=59， 并取 e=13. 则 n=pq=2537， (n)=4258=2436. 解方程： de 1 mod 2436 得 d=937. 取 m=73, 则 7e =713 =78747 2172=c mod 2436 RSA 的安全性 关键： 在于数 n的因子分解 )2(O 222 l o gl o g)( l o g nn 目前最快的因子分解算法的计算复杂度为： 即 ， 如果数 n=pq的因子分解被破 ， 则可得 (n)=(p1)(q1), 从而由加密密钥 e可由下式解 得解密密钥： de1 mod (n) 从而 ， RSA建议： 1． p, q为 100位的十进制数 (2332), 从而n=pq为 200位 的十进制数； 2． p, q的差应较大 (差几位 )； 3． p1, q1有较大的素因子。 4． gcd(p1, q1)很小 . 这样的 p, q 称为 安全素数 . 此外 , 如果 en, 并且 dn1/4, 则 d 很容易确定 . 注： 1. 知道 n与 (n) 容易破解 p, q: 2. 如果 pq=k 较小 , 容易破解 p, q: (n)=(p1)(q1)=pq(p+q)+1=n (p+q) (。