《初等数论ppt(12)第六章指数与原根课件.ppt》由会员分享，可在线阅读，更多相关《初等数论ppt(12)第六章指数与原根课件.ppt（41页珍藏版）》请在三一办公上搜索。
1、初等数论 - 第六章 指数与原根,本章内容,1 指数,1 指数,2 原根,3 指标、二项同余方程,离散对数,Diffie 和Hellman在1976年提出的Diffie-Hellman密钥交换协议，是一个典型的密钥协商协议；允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程算法的安全性依赖于计算离散对数的难度,生成元,离散对数的概念,对于一个整数b和素数q的一个生成元a，可以找到一个唯一的指数i，使得： 成立，则指数i称为b的以a为底数的模q的离散对数。,离散对数的难解性,对于给定的a、i和q，容易计算出b，但给定b、a和q，计算出i一般非常困难。这就是包括DH密钥交换算法和DSA数字
2、签名算法等在内的许多公钥密码算法的基础。,Diffie-Hellman密钥交换算法,目的：用户A和用户B需要安全地交换一个密钥（即秘密共享一个密钥，这个密钥可以用于对称密码加密）步骤：（1）A和B都知道一个素数q和一个整数a（均公开）， a是q的一个原根（2）用户A选择一个随机数 XAq ，并计算 类似地，用户B选择一个随机数 XBq , 并计算,Diffie-Hellman密钥交换算法,（3）每一方都对X的值保密存放；使Y的值公开，另一方可以得到（4）用户A计算密钥： 用户B计算密钥：（5）这里双方计算出的K就是共享的密钥，双方以K作为加、解密密钥，以对称密钥算法进行保密通信。（6）整个系统
3、中，A、B双方各自的X值为各自的私钥，保密；各自的Y值为公钥，公开。,DH例子,素数q=97,它的一个本原元a=5A和B分别选择随机数Xa=36和Xb=58A计算公开密钥：Ya=536mod97=50mod97 B计算公开密钥：Yb=558mod97=44mod97 A计算会话密钥：K= 4436mod97=75mod97B计算会话密钥：K= 5058mod97=75mod97,DH算法的证明,下面证明A、B双方计算出的K是相同的：,由于攻击者不知道XA和XB，它可以利用的信息包括：素数q、整数a、中间值YA和YB，因此它若想求得XA和XB，据知，这是求离散对数的问题，因此，DH算法的安全性依
4、赖于离散对数的难解性。,攻击者,El Gamal Signature Scheme,存在一个相关的签名算法 安全性是基于计算离散对数的困难性方案的密钥生成是相同的: 有个共享的素数 p, 公开的本原根 a 每个用户选择一个随机数作为私钥 x 计算各自的公开密钥: y = ax mod p 公钥是 (y,a,p) 私钥是 (x),El Gamal 签名方案的使用,签名消息 M: 选择随机数 k, GCD(k,p-1)=1 计算 K = ak(mod p) 用 Euclidean (inverse) 扩展算法求S:M = xK + kS mod (p-1); 即求S = k-1(M - x.K)
5、mod (p-1) 签名是 (K,S) k 应该被销毁同ElGamal 加密方案， 签名信息也是消息的2倍验证 (K,S) 是 对M的签名: yK.KSmod p = aMmod p,ElGamal 签名方案举例,取 p=11, g=2 选择私钥 x=8 计算: y = ax mod p = 28 mod 11 = 3 公钥是: y=3,g=2,p=11 对 M=5 签名：选择随机数 k=9 确定 gcd(10,9)=1 计算: K = ak mod p = 29 mod 11 = 6 解: 5 = 8.6+9.S mod 10; nb 9-1 = 9 mod 10;因此 S = 9.(5-8.6) = 3 mod 10 签名是 (K=6,S=3) 要验证签名, 确认:36.63 = 25 mod 113.7 = 32 = 10 mod 11,作业10,试求模11,13,17,19,31,37,53,71的最小正原根试求一个g，它是模p的原根，但不是p2的原根：p=5,7,11,17,31.,
