密码学 离散对数

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

2、ohlig-Hellman算法,针对p-1只有小素数情形,问题：求解 其中,解决：,用中国剩余定理确定x.,例3：求解,解：,求,设,确定,两边幂 得,所以,确定,原方程转化为,两边幂 得,所以,确定,原方程转化为,两边幂 得,所以,故,求,其中,原方程两边幂 得,设,其中,将,代入检验，得,因此，得,由中国剩余定理得，,故,7.3 位提取,预备：计算离散对数mod 4的值：,设x为 b0是非常容易确定的； 如果p mod 4=1，由Pohlig-Hellman算法， b1也是 非常容易确定的； 如果p mod 4=3，b1的确定 也就是说， b1非常难确定的。,的解，,将之用二进制表示：,求

3、解方程,位提交,赛事 Alice:能预测赛果； Bob:好赌。 希望合作获利 Alice希望通过预售赛果获利; Bob希望预知赛果获利; Bob担心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的本原根

4、根.,发送给Bob.,使得x的,合理性分析 Alice不能窜改结果。 因为x与为1-1对应的。 Bob不能在赛前根据计 算出b1。 思考：在约定中， 为什么“p为模4余3的素 数”？ 将之改为“p为模4余1的 素数”行吗？,7.4 Diffie-Hellman密钥交换,问题：对于对称密钥系统，如何发送密钥？,RSA利用大素数分解的困难性，提供了一种密钥发送的 方案。 Diffie和Hellman利用离散对数求值的困难性，也提供了 另一种密钥发送的方案。,Diffie-Hellman密钥交换的算法,Step1. 公开 Step2. Alice选择私钥a Bob选择私钥b Step3. Alice计算 Bob计算,发送Bob:,发送Alice:,得会话密钥K;,也得会话密钥K.,7.5 EIGamal公钥密码系统,EIGamal在1985年给出一个公钥密码系统,假设 Bob公钥 Alice要发送消息m给Bob其中 EIGamal公钥密码系统算法: Step1. Alice选取秘密随机数a，计算 Step2. Alice计算 Step3. Alice发送(A,c)给Bob. Step4. Bob解密,私