密钥交换协议:

设计密钥交换协议的目的是在多个用户之间安全地协商出一个共享的会话密钥(用于对称加密协议).

博主注:该类协议要求保证在可窃听信道的通信中密钥的安全,而在可篡改信道的通信中,密钥被篡改时可以被识别.

Diffie-Hellman密钥交换协议:

通信双方Alice,Bob约定素数阶有限域$F_p$(可以理解为$[0,p-1]$)和乘法循环群$F_p^*$(可以理解为$[0,p-1]$与模$p$乘法构成的代数结构)的任意生成元$g$(可以理解为$[0,p-1]$上的任意整数),然后执行如下运算:

(博主注:$g$的值是多少应当是公开的)

1. Alice在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$a$,计算$g_a=g^a \mod p$,将$g_a$发送给Bob
2. Bob也在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$b$,计算$g_b=g^b \mod p$,将$g_b$发送给Alice
3. Alice计算$(g_b)^a \mod p$,Bob计算$(g_a)^b \mod p$,由于$(g_b)^a=g^{ab}=(g_a)^b$,这两个计算出来的值相同,因此可以作为协商出来的密钥.

该密钥交换协议在可窃听信道上是安全的,虽然$p,g$是公开的,但即使窃听者监听了$g_a,g_b$,要以此还原秘密值$a,b$或者求解$(g_b)^a \mod p$意味着需要计算离散对数,这在计算复杂度上是不可行的.

但该协议在可篡改信道上是不安全的,因为会面临中间人攻击的威胁.

针对Diffie-Hellman密钥交换协议的中间人攻击:

1. Alice在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$a$,计算$g_a=g^a \mod p$,将$g_a$发送给Bob
2. 但发送的中途被Hacker截获,Hacker则选择了一个$h_1 \in [1,p-2]$,并将$g_a'=g^{h_1}$假装成Alice发送的信息,转发给Bob
3. Bob也在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$b$,计算$g_b=g^b \mod p$,将$g_b$发送给Alice
4. 同样被Hacker截获,Hacker选择了一个$h_2 \in [1,p-2]$,将$g_b'=g^{h_2}$假装成Bob发送的信息,转发给Alice
5. 收到"Alice"信息的Bob计算$(g_a')^b=g^{h_1b}$
6. 收到"Bob"信息的Alice计算$(g_b')^a=g^{h_2a}$
7. Hacker同样能够计算出$g^{h_1b},g^{h_2a}$,用于分别和Bob和Alice进行通信的密钥,此后,Hacker便可在两人之间充当"中间人",随意监听,拦截,篡改消息

注意,Hacker并不知道$a,b$分别是多少,但这不影响它对此协议的攻击,它只需要在可篡改信道上篡改消息即可

要避免这种攻击,就需要引入数字签名与证书

端-端协议:

1. 该算法需要有一个可信中心Torrent,Torrent拥有:
1. 自己的私钥$sk_T$,用于签名算法$Sign_T(\cdot)$
2. 公钥$pk_T$,任何人都可用此公钥验证Torrent的签名的有效性
2. Torrent若要为Alice背书,应当做如下几件事:
1. 生成Alice的私钥$sk_A$,公钥$pk_A$
2. 使用自己的私钥$sk_T$为$pk_A$和Alice的ID签名:$Sign_T(ID_A,pk_A)$
3. 将$Cert_A=(ID_A,pk_A,Sign_T(ID_A,pk_A))$作为证书,连同私钥$sk_A$,内置在Alice的系统中
3. 同理,Torrent若要为Alice背书,应当做如下几件事:
1. 生成Bob的私钥$sk_B$,公钥$pk_B$
2. 使用自己的私钥$sk_T$为$pk_B$和Bob的ID签名:$Sign_T(ID_B,pk_B)$
3. 将$Cert_B=(ID_B,pk_B,Sign_T(ID_B,pk_B))$作为证书,连同私钥$sk_B$内置在Bob的系统中.
4. 之后的过程就类似于Diffie-Hellman密钥交换协议了,Alice想要与Bob协商密钥,应当:
1. 在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$a$
2. 计算$g_a=g^a \mod p$,
3. 将$g_a$发送给Bob
5. Bob在收到Alice的信息后,做类似的事:
1. 在$[1,p-2]=\{1,2,\cdots,p-2\}$中随机选择$b$,
2. 计算$g_b=g^b \mod p$
除此以外,他还需要做额外的事,获得Alice的信任:
3. 使用自己的私钥$sk_B$对$g_a,g_b$进行签名
4. 将$g_b$,$Sign_B(g_a,g_b)$,连同和自己的证书$Cert_B$一同发送给Alice
6. Alice要做如下的事确保对面的人是可信的:
1. 使用$pk_T$验证签名$Sign_T(ID_B,pk_B)$是否真的由$sk_T$签署 (若是,则说明Torrent认可$pk_B$,$sk_B$签署的签名也是可信的)
2. 使用$pk_B$验证签名$Sign_B(g_a,g_b)$是否真的由$sk_B$签署 (若是,则说明$sk_B$的持有者真的拿到了自己的$g_a$,发来的$g_b$也是由它本人认可的)
至此,Alice相信了自己对面的人真的是Bob,也相信Bob正确地收到了自己的$g_a$,接下来,他要做类似的事情获取Bob的信任:
3. 使用自己的私钥$sk_A$对$g_a,g_b$进行签名
4. 将$Sign_A(g_a,g_b)$,连同和自己的证书$Cert_A$一同发送给Bob
7. Bob也要做如下的事确保对面是可信的:
1. 使用$pk_T$验证签名$Sign_T(ID_A,pk_a)$是否真的由$sk_T$签署
2. 使用$pk_A$验证签名$Sign_A(g_a,g_b)$是否真的由$sk_A$签署
8. 做完这些后,Alice和Bob互相确认了对方的身份,接下来,他们只要分别计算$(g_b)^a,(g_a)^b$就可以作为双方通信的密钥了

如果中间人Hacker在第4,5步之间截获了$g_a$并将之篡改为$g_h$发送给Bob的话,Bob只会对$g_h$签名,得到$Sign_B(g_b,g_h)$,Hacker不持有$sk_B$,因此它无法伪造$Sign_B(g_a)$.

而Hacker若尝试伪造证书,换用其他的密钥$sk_H$,则因为它不持有Torrent的私钥$sk_T$,因此无法伪造$Sign_T(ID_B,pk_H)$来谎称$pk_H$属于Bob.

Matsumoto-Takashima-Imai (MTI)密钥交换协议:

这是一种不需要通信双方计算签名的密钥交换协议,取而代之使用一对数$x\in [1,p-2],y=g^x \mod p$,$x$由拥有者秘密保留,而$y$则公开

1. Torrent为Alice的ID和公开指数$y_A=g^{x_A}$签名,将$Cert_A=(ID_A,y_A,Sign_T(ID_A,y_A))$作为证书,连同私有指数$x_A$内置在Alice的系统中
2. Torrent为Bob的ID和公开指数$y_B=g^{x_B}$签名,将$Cert_B=(ID_B,y_B,Sign_T(ID_B,y_B))$作为证书,连同私有指数$x_B$内置在Bob的系统中
3. Alice若要与Bob协商密钥,选择$r_A\in[1,p-2]$,计算$g_A=g^{r_A} \mod p$,将$Cert_A=(ID_A,y_A,Sign_T(ID_A,y_A))$和$g_A$发送给Bob.
4. Bob选择$r_B\in[1,p-2]$,计算$g_B=g^{r_B} \mod p$,将$Cert_B=(ID_B,y_B,Sign_T(ID_B,y_B))$和$g_B$发送给Alice.
5. Alice计算$K=g_B^{x_A}y_B^{r_A} \mod p$
6. Bob计算$K=g_A^{x_B}y_A^{r_B} \mod p$

最终的共享密钥值$K=g^{r_Ax_B+r_Bx_A}$.

此时如果存在一个Hacker,截获并篡改了信息,试图进行中间人攻击,则会出现这样的情况:

对MTI协议的中间人攻击:

1. Alice将$Cert_A=(ID_A,y_A,Sign_T(ID_A,y_A))$和$g_A=g^{r_A}$发送给Bob.
2. Hacker截获此信息,将$g_A=g^{r_A}$篡改为$g_A'=g^{r_{h_1}}$发送给Bob.(因为不知道Torrent的私钥,攻击者是没法对证书动手脚的)
3. Bob将$Cert_B=(ID_B,y_B,Sign_T(ID_B,y_B))$和$g_B=g^{r_B}$发送给Alice.
4. Hacker同样截获此信息,将$g_B=g^{r_B}$篡改为$g_B'=g^{r_{h_2}}$发送给Alice.
5. Alice计算$K'=g_B'^{x_A}y_B^{r_A} = g^{r_Ax_B+r_{H_1}x_A} \mod p$
6. Bob计算$K''=g_A'^{x_B}y_A^{r_B}  = g^{r_{H_2}x_B+r_Bx_A}$
7. 然而,Hacker因为不知道秘密指数$x_A,x_B$,因此无法计算出$K',K''$中的任何一个,从而无法充当"中间人"

ECQMV密钥交换:

(TODO)

自证明公钥的密钥交换:

该协议的特点是不需要证书,公钥中隐含了ID

步骤1:从可信中心获取自证明公钥

这样,当其他用户需要使用Alice的公钥时,只需计算$(pub_A^e+ID_A) \mod n$,Bob同理

尽管$pub$的计算不需要$x$,但用户仍需要将$x$发送给Torrent,以向Torrent证明自己确实知道$x$(博主注:与Torrent通信的消息被截获了怎么办?可能的解决方案:买电脑时内置与Torrent通信的专用密钥)

步骤2:用户之间交换密钥

正确性:

$$\begin{aligned}
(pub_B^e+ID_B)=& (((y_B-ID_B)^d)^e)+ID_B \\
              =& (y_B-ID_B)+ID_B \qquad \text{RSA解密运算} \\
              =&y_B \\
\end{aligned}$$

$$\begin{aligned}
K=&g_B^{x_A}(pub_B^e+ID_B)^{k_A} \\
=&g_B^{x_A}y_B^{k_A}\\
=&(g^{k_B})^{x_A}(g^{x_B})^{k_A}\\
=&g^{k_Bx_A+x_Bk_A}
\end{aligned}$$

Bob的计算过程同理.

对(弱化的)自证明公钥体系的攻击:

如果Torrent不要求用户提交$x$就颁发$pub$,则攻击者可用以下方式进行中间人攻击

为描述简便,以下示例中Hacker只在会话中试图拦截Bob发送的消息

步骤1:伪造并冒领$pub$

步骤2:拦截篡改Alice与Bob的通信 

Bob计算出的密钥:

$$\begin{aligned}
 K'=&(g_A')^{x_B}((pub_A')^e+ID_A)^{k_B} \\
   =&(g^{k_A'})^{x_B}(g^{x_A'})^{k_B}\\
   =&g^{k_A'x_B+x_A'k_B}
\end{aligned}$$

Hacker计算出的密钥:

$$\begin{aligned}
 K'=&(g_B)^{x_A'}((pub_B)^e+ID_B)^{k_A'} \\
   =&(g^{k_B})^{x_A'}(g^{x_B})^{k_A'}\\
   =&g^{k_A'x_B+x_A'k_B}
\end{aligned}$$

Hacker可以用同样的手段让Alice也计算得出伪造的密钥,这个例子说明了,向Torrent提交秘密指数$x$对于该协议的安全是关键的.

基于身份的密钥协商:

在该类协议中,ID就是公钥,而私钥是由系统中的TA(trusted authority)通过私钥生成器(private key generator,PKG)生成的

双线性映射:

设$q$为大素数,$G_1=([0,q-1],+)$是加法循环群,$P\in G_1$是生成元,$G_2$是与$G_1$同阶的乘法循环群

将存在如下性质的函数$e:G_1 \times G_1 \to G_2$称为双线性映射

1. 双线性性 $\forall Q,R \in G_1,a,b\in Z_q,e(aQ,bR)=e(Q,R)^{ab}$
2. 非退化性 $e(P,P)\neq 1$
3. 计算有效性 $\forall Q,R$,存在有效算法计算$e(Q,R)^{ab}$

(博主注:一个构造双线性映射的可行思路是,若$2^q-1$是素数,则可令$G_2=(\{1,2,4,\cdots,2^{q-1}\}, * \mod (2^q-1) )$,$e(Q,R)$=2^{Q+R} \mod q)

基于身份的非交互密钥分配:

设$q$为大素数,$G_1=([0,q-1],+)$是加法循环群,$P\in G_1$是生成元,$G_2$是与$G_1$同阶的乘法循环群,$e:G_1 \times G_1 \to G_2$是双线性映射,$H_1:\{0,1\}^* \to G_1$是一个哈希函数,可将任意字符串映射至$G_1$.

Alice,Bob的身份$ID_A,ID_B$以及身份的哈希值$Q_A=H_1(ID_A),Q_B=H_1(ID_B)$是公开的.

TA选取主密钥$s\in[1,p-1]$,计算$S_A=sQ_A,S_B=sQ_B$分别分发给Alice,Bob

然后Alice计算$K_AB=e(S_A,Q_B)$,Bob计算$K_AB=e(S_B,Q_A)$(实际上,这两个值均等于$e(Q_A,Q_B)^s$)便得到了会话密钥.

问题:

1. 会话密钥是静态的
2. 必须提前在系统中注册

基于身份的双方密钥交换:

设$q$为大素数,$G_1=([0,q-1],+)$是加法循环群,$P\in G_1$是生成元,$G_2$是与$G_1$同阶的乘法循环群,$e:G_1 \times G_1 \to G_2$是双线性映射,$H_1:\{0,1\}^* \to G_1$是一个哈希函数,可将任意字符串映射至$G_1$.

Alice,Bob双方的身份$ID_A,ID_B$以及身份的哈希值$Q_A=H_1(ID_A),Q_B=H_1(ID_B)$是公开的

TA选取主密钥$s\in[1,p-1]$,计算$S_A=sQ_A,S_B=sQ_B$分别分发给Alice,Bob

当Alice和Bob要会话时,按如下步骤交换会话密钥:

$$\begin{aligned}
K_A=&e(S_A,W_B+aQ_B) \\
   =&e(sQ_A,bQ_B+aQ_B) \\
   =&e(Q_A,Q_B)^{s(a+b)}
\end{aligned}$$

$$\begin{aligned}
K_B=&e(W_A+bQ_A,S_B) \\
   =&e(aQ_A+bQ_A,sQ_B) \\
   =&e(Q_A,Q_B)^{s(a+b)}
\end{aligned}$$

三方密钥交换: 

Alice,Bob,Charlie三方为了会话要协商出一个相同的密钥

三方Diffie-Hellman密钥交换:

很明显,容易遭到中间人攻击.

基于双线性配对的密钥交换:

公开信息:模数$q$,加法循环群$G_1$,乘法循环群$G_2$,生成元$P$,双线性映射$e$

将生成的值直接广播即可.

显然,$k=e(P,P)^{abc}$

该方案只需要一轮通信便可得到会话密钥.

但仍然无法抵抗中间人攻击.

多方密钥交换:

最简单的思路:$n$个参与者就使用$n-1$轮Diffie-Hellman密钥交换.

Burmester-Desmedt多方密钥交换:

只需要两轮交互的密钥交换

公开信息:模数$q$,生成元$g$

1. 对于每个用户$U_i$,选择$x_i$,计算$Z_i=g^{x_i}$并发送给上下家.
2. 获取自己上家,下家的广播信息,计算$X_i=(\frac{Z_{i+1}}{Z_{i-1}})^{x_i}$,并广播
3. 计算$K=Z_{i-1}^{nx_i}X_i^{n-1}X_{i+1}^{n-2}\cdots X_{i+n-2}$

即,将自己$X$值的$n-1$次方,自己下家$X$值的$n-2$次方......乘在一起,然后乘上自己上家的$Z$值的$nx_i$次方,便得到了会话密钥$K$

以4个用户的密钥交换举例:

$$X_1=(\frac{g^{x_2}}{g^{x_4}})^{x_1}$$

$$X_2=(\frac{g^{x_3}}{g^{x_1}})^{x_2}$$

$$X_3=(\frac{g^{x_4}}{g^{x_2}})^{x_3}$$

$$X_4=(\frac{g^{x_1}}{g^{x_3}})^{x_4}$$

然后观察$U_1$计算出的$K$

$$\begin{aligned}
K=&Z_4^{4x_1}X_1^3X_2^2X_3\\
 =&(g^{x_4})^{4x_1}(\frac{g^{x_2}}{g^{x_4}} )^{3x_1} (\frac{g^{x_3}}{g^{x_1}} )^{2x_2} (\frac{g^{x_4}}{g^{x_2}} )^{x_3}\\
 =&g^{4x_1x_4}\cdot \frac{g^{3x_1x_2}}{g^{3x_1x_4}} \cdot \frac{g^{2x_2x_3}}{g^{2x_1x_2}}\cdot \frac{g^{x_3x_4}}{g^{x_2x_3}} \\
 =&g^{x_1x_2+x_2x_3+x_3x_4+x_4x_1}  \end{aligned}$$

还是没有考虑中间人攻击.