《密码学 离散对数》由会员分享，可在线阅读，更多相关《密码学 离散对数（13页珍藏版）》请在金锄头文库上搜索。
1、7.1 离散对数定义 设 为模p的本原根。 1) 指数函数为 到 的一一映射；2) 对数函数为 到 的一一映射。例1：0 1 2 3 4 51 2 3 4 5 6例2：解方程解：x0123456 2x12485109 所以性质：设 为模p的本原根。有：7.1 离散对数的计算命题：设其中p为奇素数，则1) x为偶数；2) x为奇数.分析：1) 为p-1的倍数x为偶数例1:已知 判断x的奇偶？解:所以x为偶数。事实上 x=6 (mod10).例2 求解解：所以设原方程转化为所以设原方程转化为所以设 两边幂 得 两边幂 得 两边幂 得原方程转化为 将 代入检验，得 所以Pohlig-Hellman算
2、法针对p-1只有小素数情形问题：求解 其中解决： 对每个因子求 用中国剩余定理确定x.例3：求解解： 求设 确定两边幂 得所以 确定 原方程转化为两边幂 得所以 确定原方程转化为两边幂 得所以故 求其中原方程两边幂 得设其中将代入检验，得 因此，得由中国剩余定理得，故7.3 位提取预备：计算离散对数mod 4的值：设x为b0是非常容易确定的；如果p mod 4=1，由Pohlig-Hellman算法， b1也是非常容易确定的；如果p mod 4=3，b1的确定也就是说， b1非常难确定的。的解，将之用二进制表示：求解方程位提交n赛事Alice:能预测赛果；Bob:好赌。n希望合作获利Alice
3、希望通过预售赛果获利;Bob希望预知赛果获利;Bob担心Alice的准确度，希望先验证;Alice不愿赛前就让Bob知道赛果。n方案1假设Alice和Bob空间距离很近赛前：锁；赛后：开。n方案2假设Alice和Bob空间距离很远约定:n0巴西赢；1巴西输赛前：nAlice随机选择一个能够隐藏赛果的二进制数x (p-1), 次低位b1为结果位。例如：Alice预测巴西赢。nAlice计算赛后：nAlice发送x给Bob；nBob验证结果。n 其中p为模4余3的素数，为模p的本原根根.0发送给Bob.使得x的n合理性分析Alice不能窜改结果。因为x与为1-1对应的。Bob不能在赛前根据计算出b
4、1。n思考：在约定中，为什么“p为模4余3的素数”？将之改为“p为模4余1的素数”行吗？7.4 Diffie-Hellman密钥交换问题：对于对称密钥系统，如何发送密钥？ nRSA利用大素数分解的困难性，提供了一种密钥发送的方案。nDiffie和Hellman利用离散对数求值的困难性，也提供了另一种密钥发送的方案。Diffie-Hellman密钥交换的算法Step1. 公开Step2. Alice选择私钥aBob选择私钥bStep3. Alice计算Bob计算发送Bob:发送Alice:得会话密钥K;也得会话密钥K.7.5 EIGamal公钥密码系统EIGamal在1985年给出一个公钥密码系统n假设Bob公钥Alice要发送消息m给Bob其中nEIGamal公钥密码系统算法:Step1. Alice选取秘密随机数a，计算Step2. Alice计算Step3. Alice发送(A,c)给Bob.Step4. Bob解密私钥b.Note: 1) Alice每次使用的秘密随机数要求不同.2) Diffie-Hellmam密钥交换和EIGamal公钥系统本质相同.
