文档介绍：安全协议与标准
******@sdu.
2007, 11
高级密码协议
密码协议和数学难解问题↓
D-H、RSA、秘密分享、门限密码↓
比特承诺和网络棋牌游戏↓
安全多方计算↓
ECC ↓
量子计算与密码学↓
侧信道攻击↓
协议
(算法)
协议是一系列步骤,它包括两方或多方,设计它的目的是要完成一项任务。
(1)协议中的每人都必须了解协议,并且预先知道所要完成的所有步骤。
(2)协议中的每人都必须同意遵循它。
(3)协议必须是无歧意的,每一步必须明确定义,并且不会引起误解。
(4)协议必须是完整的,对每种可能的情况必须规定具体的动作。
密码学算法和协议的背景:某些数学难解问题
大数分解难题
IFP - Integer factorization problem
离散对数难题
DLP - Discrete logarithm problem
ECDLP
Diffie-Hellman密钥交换协议
DH76,Diffie-Hellman
基于DLP问题
步骤
选取大素数q和它的一个生成元g,这些参数公开
A选择随机数Xa,B选择随机数Xb
A计算Ya=g^Xa mod q,B计算Yb=g^Xb mod q
交换Ya,Yb
A计算K=Yb^Xa mod q,B计算K'=Ya^Xb mod q
事实上,K=K'
RSA算法
找素数,选取两个512bit的随机素数p,q
计算模n =pq,Euler函数φ(n) =(p-1)(q-1)
找ed≡1 mod φ(n)
选取数e,用扩展Euclid算法求数d
发布公钥(e,n),保密私钥(d, n)
加密明文分组m(视为整数须小于n)
c=me mod n
解密 m=cd mod n
RSA problem
RSA问题
The RSA problem is to find integer P such that P e ≡ C (mod N), given integers N, e and C such that N is the product of two large primes, 2 < e < N is coprime to φ(N), and 0 <= C < N.
开e次方
e=3,65537
Diffie-Hellman problem
Given an element g and the values of gx and gy, what is the value of gxy ?
Computational Diffie-Hellman assumption
It is an open problem to determine whether the discrete log assumption is equivalent to CDH, though in certain special cases this can be shown to be the case.
Decisional Diffie-Hellman assumption
(ga, gb, gab) ? (ga, gb, gc)
秘密(密钥)分割
秘密分割(多人共同持有秘密)
0. 秘密K需要t个人联合打开
1. 产生随机数R1、R2、…、Rt-1、 Rt=K⊕R1⊕R2…⊕Rt-1
2. t个人分别持有Ri
3. 恢复秘密
K=R1⊕R2…⊕Rt-1⊕Rt
秘密的门限共享
(m,n)门限方案
秘密的恢复需要n个人中的m个参与即可
Lagrange插值方案
以(3,n)门限方案为例:
取多项式f(x)=ax2+bx+K,a、b是随机数,K是秘密对于成员i=1…n,给予f(xi)=axi2+bxi+K,一般取xi=i恢复秘密时只需n中的三个(x、y)点即重构f(x)