密码学 离散对数

1、7.1 1定义设 为模p的本原根。1) 指数函数为 到 的一一映射；2) 对数函数为 到 的一一映射。例1：012345123456例2：解方程解：x01234562x12485109所以性质：设 为模p的本原根。有：27.1 离散对数的计算3命题：设其中p为奇素数，则1) x为偶数；2) x为奇数.分析：1) 为p-1的倍数x为偶数例1:已知判断x的奇偶？解:所以x为偶数。事实上 x=6 (mod10).4例2求解解：所以设原方程转化为所以设原方程转化为所以设两边幂 得两边幂 得两边幂 得原方程转化为将代入检验，得所以5Pohlig-Hellman算法针对p-1只有小素数情形问题：求解 其中

2、解决：对每个因子求用中国剩余定理确定x.例3：求解解：求设 确定两边幂 得所以 确定原方程转化为两边幂 得所以 确定原方程转化为两边幂 得所以故求其中原方程两边幂 得设其中将代入检验，得因此，得由中国剩余定理得，故67.3 位提取7预备：计算离散对数mod 4的值：设x为b0是非常容易确定的；如果p mod 4=1，由Pohlig-Hellman算法， b1也是 非常容易确定的；如果p mod 4=3，b1的确定 也就是说， b1非常难确定的。的解，将之用二进制表示：求解方程8位提交赛事Alice:能预测赛果；Bob:好赌。希望合作获利Alice希望通过预售赛果获利;Bob希望预知赛果获利;B

3、ob担心Alice的准确度，希望 先验证;Alice不愿赛前就让Bob知道赛 果。方案1 假设Alice和Bob空间距离很近赛前：锁；赛后：开。方案2 假设Alice和Bob空间距离很远约定:0巴西赢；1巴西输赛前：Alice随机选择一个能够隐藏赛 果的二进制数x (p-1), 次低位b1为结果位。 例如：Alice预测巴西赢。 Alice计算赛后：Alice发送x给Bob；Bob验证结果。 其中p为模4余3的素数，为模p的本原根根.0发送给Bob.使得x的合理性分析Alice不能窜改结果。 因为x与为1-1对应的。Bob不能在赛前根据计 算出b1。思考：在约定中，为什么“p为模4余3的素 数

4、”？将之改为“p为模4余1的 素数”行吗？97.4 Diffie-Hellman密钥交换10问题：对于对称密钥系统，如何发送密钥？ RSA利用大素数分解的困难性，提供了一种密钥发送的 方案。Diffie和Hellman利用离散对数求值的困难性，也提供了 另一种密钥发送的方案。Diffie-Hellman密钥交换的算法Step1. 公开Step2. Alice选择私钥a Bob选择私钥bStep3. Alice计算 Bob计算发送Bob:发送Alice:得会话密钥K;也得会话密钥K.117.5 EIGamal公钥密码系统12EIGamal在1985年给出一个公钥密码系统假设Bob公钥Alice要发送消息m给Bob其中EIGamal公钥密码系统算法:Step1. Alice选取秘密随机数a，计算Step2. Alice计算Step3. Alice发送(A,c)给Bob.Step4. Bob解密私钥b.N