信息安全数学基础 第四章 原根与指数.ppt

练习 类似于解对数方程： 5ind3x ?ind33 ?1(mod 6) 为什么是6? ind3x ?5(mod 6) 查表 x?5(mod 7) 注意：模又恢复为7 当然也可以利用 ind5x 5ind5x ?ind53 ?5(mod 6) ind5x ?1(mod 6) 直接 x?5(mod 7) 作业（4）85页第8题 解方程 x5 ? 3 (mod 7) a 1 2 3 4 5 6 ind3a 0 2 1 4 5 3 练习 法一： 6-1 ? -1 (mod 7)，所以原方程化简为 3x ? -5 ? 2(mod 7)，所以xind33 ?ind32(mod 6) x?2(mod 6) 仍然是6 法二：ind36+xind33 ?ind35(mod 6) 3+x?5(mod 6) x?2(mod 6) 仍然是6 指数模指数，底数模m 解方程 6*3x ? 5 (mod 7) a 1 2 3 4 5 6 ind3a 0 2 1 4 5 3 4.5 应用 三大难题之一：离散对数问题 gr ? a (mod m)，已知g,a,m，求r困难 EIGamal公钥密码体制 (1)选取大素数p和p的一个原根a，(a,p)=1,1ap (2)选取整数d，1dp-1，计算b ? ad (mod p)；p,a,b为公钥，d为私钥 (3)加密：对0mp，秘密的随机选取整数k,1kp-1,加密后密文为c=(c1 ， c2 ), c1 ? ak (mod p), c2 ? mbk (mod p) (4)解密：明文m ? c2 ( c1 d) -1 (mod p) 分析： c2 ( c1 ) -d ? mbk (ak d) -1 ? m adk (ak d) -1 ? m (mod p) 应用 密钥交换 对称加密需要 Diffie-Hellman密钥交换 素数p与其原根a为公开整数 设A,B希望交换密钥，则A选择随机数XAp，计算YA ? aXA(mod p)；类似的B选择随机数XBp，计算YB ? aXB(mod p)，X私有，Y公开 A计算KA?(YB)XA(mod p)将其作为自身密钥 B计算KB?(YA)XB(mod p)将其作为自身密钥 KA= KB实现了密钥的交换 应用 RSA定点攻击 第三者截获密文C后，反复计算e次幂 ce ≡ me^2 ce^2 ≡me^3 ……（mod n）一旦 ce^t≡ c ≡ me（mod n） =〉 m ≡ ce^(t-1) （mod n） t不是很大时这种攻击可行 如何避免？如何让t很大？ 若m模n的指数为k，t可取的最小值为e模k的指数 这个指数为φ(k)的因子，所以φ(k)应有大素因子 而k是φ(n)=(p-1)(q-1)的因子 所以p-1,q-1应有大素因子?强素数 总结 原根 缩系中指数与欧拉函数相等的数 模m有原根的必要条件是m = 2，4，p?或2p?，其中p是奇素数，? ? 1 指数： ak ? 1 (mod m)成立的最小正整数k,写作ordm(a) 或?m(a) 若指数与欧拉函数不等，指数也整除欧拉函数 等指数：同余、互逆数的指数相同 如何计算指数？ 幂从小到大取欧拉函数的因数试算，直到≡1 如何计算原根 计算出的指数等于欧拉函数 练习 计算ord11(3) 首先计算φ(11)=10，所以指数可能为1,2,5,10 从小到大依次试算 31?3, 32?9, 35?1(mod 11)，所以ord11(3)=5 根据这个结论可以推出 ord11(14)=5=ord11(4) 可以推出ord11(-3)= ord11(-1)* ord11(3)=10 所以-3?8是原根，原根一共φ(10)=4个 所以8?23，83?29 ?72?6， 87?221?21?2， 89?227?27?7，即2、6、7、8是原根 总结 寻找一个原根的技巧: ordm(a) |φ(m) (m, n) = 1，(a, mn) = 1，则ordmn(a)= [ordm(a),ordn(a)] (ab, m) =1， (ordm(a),ordm(b))=1则ordm(ab)=ordm(a)ordm(b) 奇素数p，p-1= 练习 求模41的原根情况 φ(11)=40,现在只要考察x8, x20 从2开始,因为 28?10, 220?1(mod 41); 38?1, 320?-1(mod 41); 48?20, 420?1(mod 41); 58?18, 520?1(mod 41); 68?10, 620?-1(mod 41); 所以6是模41的原根 练习 求模41的原根情况 因为:62?36