加密-非对称技术

在公钥密码体制中，加密不用密钥，密钥仅在解密阶段使用，Diffie和Hellman描述了几个可能用来实现公钥密码的数学变换，它们称之为单向陷门函数。

单向陷门函数 单向陷门函数 ft(x):D→Rf_t(x):D\rarr R，是一个单向函数，即对任意的 x∈Dx\in D，容易计算，而对几乎所有的 x∈Dx\in D，求逆困难，但是如果知道陷门信息 tt ，则对所有的 y∈Ry \in R，容易计算满足 y=ft(x)y=f_t(x) 的 x∈Dx\in D。

Diffie-Hellman密钥交换协议

与对称密码体制相比，公钥密码体制的一个显著优点就是远程通信各方无需安全信道就能实现相互交换密钥。最早实现这一点的方案是Diffie-Hellman指数密钥交换协议。

首先，假设用户Alice和Bob约定有限域FqF_q和元素 g∈Fpg\in F_p，g生成一个群。为简化，我们考虑有限域 FpF_p，p为素数。协议如下：

协议：Diffie-Hellman密钥交换协议

共同输入 (p，g)：p为大素数，g为FqF_q 的生成元。

输出：Alice和Bob共享FpF_p 中的一个元素

  1. Alice选择 a∈[1,p−1)a \in [1,p-1)，计算 ga=ga(modp)g_a=g^a(modp)，发送gag_a给Bob

  2. Bob选择 b∈[1,p−1)b \in [1,p-1)，计算 gb=gb(modp)g_b=g^b(modp)，发送gbg_b给Alice

  3. Alice计算 k=gba(modp)k=g_b^a(modp)

  4. Bob计算 k=gba(modp)k=g_b^a(modp)

可以不难看出，对于Alice和Bob都有: k=gabmodpk=g^{ab}modp

中间人攻击

处于Alice和Bob通信中间的主动攻击者能够操纵这个协议的消息以达到成功的攻击，称为中间人攻击。

在对协议运行的攻击当中，Malice截获Alice发送给Bob的第一条消息gag_a，并伪装成Alice向Bob发送消息。

Malice发送给Bob：gm(modp)g_m(modp)

Bob将按照协议的规则回复gbg_b给Malice，这个发送的数值再一次被Malice截获，现在M和B写上了一个密钥gbm(modp)g^{bm}(modp)，而Bob以为这个密钥就是他和Alice所共享的密钥。

image-20230718191316520

  1. Alice选择 a∈[1,p−1)a \in [1,p-1)，计算 ga=ga(modp)g_a=g^a(modp)，发送gag_a给Malice(’“Bob”)

1`. M(“Alice”)对某个 m∈[1,p−1)m \in [1,p-1),计算gm=gm(modp)g_m=g^m(modp)

  1. Bob选择 b∈[1,p−1)b \in [1,p-1)，计算 gb=gb(modp)g_b=g^b(modp)，发送gbg_b给Malice(“Alice”)

2`. M(“B”)向A发送：gmg_m

  1. Alice计算 k1=gma(modp)k_1=g_m^a(modp)

  2. Bob计算k2=gmb(modp)k_2=g_m^b(modp)

Diffie-Hellman问题和离散对数问题

DH密钥交换协议中共享密钥的保密性就是已知ga,gbg_a,g_b，计算gab(modp)g^{ab}(modp)的问题，这个问题被称为CDH。

CDH 输入：Fq,g,ga,gbF_q,g,g^a,g^b，输出：gabg^{ab}

如果CDH问题是容易的，则gab(modp)g^{ab}(modp)可以由p,g,ga,gbp,g,g_a,g_b来计算得到，而这些参数是作为协议消息的一部分传送的。

进一步，CDH问题是基于**离散对数问题（DL）**的困难性。

DL 输入： Fq,g,hF_q,g,h，输出：唯一的整数a，满足h=gah=g^a，我们用 logghlog_gh来表示整数a

RSA密码体制

RSA是最熟悉的公钥密码体制，是基于DH所想象的单向陷门函数的定义，而给出的第一个公钥密码的实现。

RSA密码体制

密钥建立

为了生成用户的基本参数，A执行以下步骤：

  1. 随机选择两个素数p和q，p≈qp\approx q

  2. 计算N=pq

  3. 计算 ϕ(N)=(p−1)(q−1)\phi (N) =(p-1)(q-1)

  4. 随机选择整数 e<ϕ(N)e < \phi(N)，满足gcd(e,ϕ(N))=1gcd(e,\phi(N))=1，并计算整数d满足ed≡1(modϕ(N)ed \equiv1 (mod\phi(N)

  5. 公开公钥(N,e)(N,e)，安全销毁p,q,ϕ(N)p,q,\phi(N)，并保留dd作为私钥

加密

为了秘密的发送m给A，发送者B生成密文c如下：

c←me(modN)c \larr m^e(modN)

解密

为了解密密文c，A计算 m←cd(modN)m \larr c^d(modN)

公钥密码体制的分析

密码体制的安全性是根据攻击来定义的，

密码体制的主动攻击

选择明文攻击（CPA） 攻击者选择明文消息并得到加密服务，产生相应的密文。攻击者的任务是用所得到的明-密文来降低目标密码体制的安全性。

选择密文攻击（CCA） 攻击者选择密文消息并得到解密服务，产生相应的明文。攻击者的任务是用所得到的明-密文对来降低目标密码体制的安全性。在解密服务停止后，即在得到目标密文之后，解密服务立即停止，如果攻击者能够从“目标密文”中得到保密明文的信息，则就说明攻击是成功的。

适用性选择密文攻击（CCA2） 这是一个CCA，而且除了对“目标密文”解密外，永远能够得到解密服务。

我们可以用以下情形来想象上述攻击类型：

  • 在CPA中，攻击者有一个加密盒子
  • 在CCA中，攻击者可以有条件地使用解密盒子，在交给攻击者目标密文之前关闭解密盒子。
  • 在CCA2中，在攻击者得到目标密文之前或之后，只要攻击者不把目标密文输入解密盒子，他就可以一直使用这个解密盒子。

在所有的情况下，攻击者都不应该拥有相应的密钥。

RSA问题

抵抗CPA，RSA的安全性基于计算密文CC模合数nen^e的困难性，这就是RSA问题。

RSA问题

输入：n=pqn=pq，pq均是素数，e满足gcd(e,((p−1)(q−1)))=1gcd(e,((p-1)(q-1)))=1，c

输出：唯一的整数m，满足me≡c(modN)m^e \equiv c (modN)

RSA假设 RSA算法是一个PPT算法AA，对于一个概率ϵ>0\epsilon > 0满足：

ϵ=Prob[m←A(N,e,me(modN))]\epsilon = Prob[m\larr A(N,e,m^e(modN))]

令IgIg是一个RSA生成器，输入1k1^k，在k的多项式时间内输出（i）一个2k比特的模N=pq，其中p和q是两个不同的均匀分布的素数，长度均为k比特，（ii）e∈Z(p−1)(q−1)∗e\in Z^*_{(p-1)(q-1)}

我们说满足RSA假设，如果对于所有充分大的k，对于k不可忽略的概率ϵ>0\epsilon>0不存在Ig(1k)Ig(1^k)满足所产生的RSA问题的求解算法。

强RSA问题 对于某些奇数的加密指数e>1e>1，可能是根据算法的选择，已知这样的e，解RSA问题。普遍认为强RSA问题仍然是不可求解的，所以某些加密算法或者协议的安全性基于这个困难性。

整数分解问题

RSA问题的困难性依赖于整数分解问题的困难性

整数分解问题（IF） 输入：N，奇合数，至少有两个素因子

输出：素数p满足p∣Np|N

一个能解决IF问题的算法就能解决RSA问题，因为Alice知道了大整数N的分解，就能先计算出d≡e−1mod(p−1)(q−1)d\equiv e^{-1}mod(p-1)(q-1)，从而可准确地对RSA密文解密。