离散数学初等数论和离散概率的应用.pptVIP

第13章 初等数论和离散概率的应用 第13章 初等数论和离散概率的应用 13.1 密码学 13.2 产生伪随机数的方法 13.3 算法的平均复杂度分析 13.4 随机算法 13.1 密码学 13.1.1恺撒密码 明文, 密文, 加密, 解密, 密钥 13.1.2 RSA公钥密码 私钥密码与公钥密码 恺撒(Caesar)密码 加密方法: ABCDEFGH I J KLMNOPQRS TUVWXYZ DEFGH I JKLMNO PQRS TUVWXYZ ABC 明文: SEE YOU TOMORROW 密文: VHH BRX WRPRUURZ 18 4 4 24 14 20 19 14 12 14 17 17 14 22 21 7 7 1 17 23 22 17 15 17 20 20 17 25 加密算法 E(i)=(i+k)mod 26, i=0, 1,…,25, 解密算法 D(i)=(i?k)mod 26, i=0, 1,…,25 其中密钥k是一取定的整数, 这里取k=3. 加密算法 线性同余加密算法 E(i)=(ai+b)mod 26, i=0, 1,…,25, 其中a与26互素. 维吉利亚(Vigenere)密码 把明文分成若干段, 每一段有n个数字, 密钥k=k1k2…kn, 加密算法 E(i1i2…in)=c1c2…cn, 其中cj=(ij+kj)mod 26, ij=0,1,…,25, j=1, 2,…, n. RSA公钥密码 私钥密码:加密密钥和解密密钥都必须严格必威体育官网网址 公钥密码 (W.Diffie,M.Hellman,1976 ):加密密钥公开,解密密钥必威体育官网网址 RSA公钥密码(R. Rivest, A. Shamir, L. Adleeman,1978) 取2个大素数p和q(p≠q), 记n=pq, ?(n)=(p?1)(q?1). 选择正 整数w, w与?(n)互素, 设d=w?1(mod?(n)). 将明文数字化, 分成若干段, 每一个明文段mn. 加密算法 c=E(m)=mwmod n, 解密算法 D(c)=cdmod n, 其中加密密钥w和n是公开的, 而p,q, ?(n)和d是必威体育官网网址的. 解密算法正确性证明 要证m=cdmod n, 即cd≡m(mod n), 亦即mdw≡m(mod n). 由dw≡1(mod?(n)), 存在k使得dw=k?(n)+1. 有两种可能: (1) m与n互素. 由欧拉定理 m?(n)≡1(mod n), 得 mdw≡mk?(n)+1 ≡m(mod n). (2) m与n不互素. 不妨设m=cp且q不整除m. 由费马小定理 mq?1≡1(mod q). 于是, mk?(n)≡mk(p?1)(q?1)≡1k(p?1)≡1 (mod q). 解密算法正确性证明(续) 从而存在h使得 mk?(n)=hq+1, 两边同乘以m, 并注意到m=cp, mk?(n)+1=hcpq+m=hcn+m, 得证 mk?(n)+1≡m(mod n), 即 mdw≡m(mod n). 模幂乘运算 实例 例1 p=43,q=59, n=43×59=2537,?(n)=42×58=2436, w=13. A, B,…, Z依次用00, 01,…,25表示, 各占2位. 设明文段m=2106, 即VG, 密文c=210613mod 2537. 计算如下: 13=(1101)2, 即13=1+22+23. A0=2106≡?431(mod 2537), A1≡(?431)2≡560(mod 2537), A2≡5602≡?988(mod 2537), A3≡(?988)2≡?601(mod 2537), 210613≡(?431)×(?988)×(?601)≡2321(mod 2537), 得密文c=2321. 实例(续) 设密文c=0981. d=13?1≡937(mod 2436), 明文m=981937(mod 2537). 计算如下: 937=(1110101001)2, A0=981, A1≡9812≡838(mod 2537), A2≡8