公钥密码

数学基础

基本概念

公钥密码体制采用两个相关密钥将加密解密能力分开；一个是公开密钥，用于加密，另一个是保密密钥，用于解密；

公钥体制加解密流程

• 信息接收者产生一对密钥，然后将公开密钥公开

• 信息发送者使用公开密钥将信息进行加密，发送在公开信道上

• 信息接收者捕获加密后的信息，使用保密密钥进行解密

进一步地，接收方也可以要求信息发送方产生公私密钥，对信息发送方进行身份认证

为了保证发送方发送的信息只由希望的接收方接收，而不由第三方窃听，可以采取这样的手段

发送者和接收者都产生一对公私钥，发送方首先使用自己的保密密钥进行第一次加密，然后使用接收方的公开密钥对信息进行第二次加密

解密时接收方使用自身的保密密钥进行第一次解密，再通过发送方的公开密钥进行第二次解密；这样就同时保证了信息的认证功能和保密性

RSA算法

算法描述

• 选取两个保密的大素数p、q

• n=p*q;φ(n)=(p-1)(q-1)

• 1 < e < φ(n),gcd(φ(n),e)=1

• d*e ≡ 1 mod φ(n)

• 密文c ≡ m^e mod n

• 明文m ≡ c^d mod n

攻击方法

• 共模攻击：用户使用的密钥不同，但模数n相同时;攻击者分别截获同一明文加密的不同密文c₁、c₂;
  于是有：
  c₁ ≡ m^e₁ mod n
  c₂ ≡ m^e₂ mod n
  使用推广的Euclid算法求出满足
  re₁+se₂=1
  的两个整数r、s，然后求出c₁^-1得
  (c₁^-1)^-rc₂^s ≡ m mod n

ElGamal公钥加密体制

• 选取一个大素数p，使离散对数问题在有限域GF(p)上是难解的，选取g∈Z是一个本原元。

• 随机选取整数x，1≤x≤p-2,计算y=g^x(mod p); y是公开的加密密钥，而x是保密的脱密密钥。

• 明文空间为Z，密文空间为Z×Z。

• 加密变换：对任意明文m∈Z，秘密地随机选取一个整数k，1≤k≤p-2，于是可得密文为：c=(c1,c2)其中c1=g^k(mod p), c2=my^k(mod p)

• 脱密变换：对任意密文c=(c1,c2)∈Z×Z，明文为：m=c2×(c1^x)^-1(mod p)

ElGamal数字签名方案

1. 生成乘法群Z中的一个生成元g，p,g公开。

2. 随机选取整数x，1≤x≤p-2,计算y=g^x(mod p)，y是公开密钥，而x是保密密钥。

3. 签名算法：设m∈Z是待签名的消息，秘密随机选取一个整数k，1≤k≤p-2，且(k,p-1)=1，计算

r=g^k(mod p)

s=k^-1(m-rx)(mod p-1)

则(m,r,s)为对消息m的数字签名。

4. 验证算法：对方收到对消息m的数字签名(m,r,s)后，利用签名者的公开密钥y,g,p可对签名进行以下验证：

(y^r)(r^s)=g^m(mod p)

如果上式成立，则接受该签名，否则拒绝该签名。

椭圆曲线密码体制

椭圆曲线并不是椭圆，一般方程为y²+axy+by=x³+cx²+dx+e

• 椭圆曲线的加法：如P+Q=R,表示在满足方程的曲线中过PQ两点作直线与椭圆曲线交与R点

设P(x₁,y₁),Q=(x₂,y₂),P≠-Q;R=P+Q=(x₃,y₃)
x₃ ≡ λ² - x₁ - x₂ (mod p)
y₃ ≡ λ (x₁ - x₃) - y₃(mod p)
λ = ( y₂ - y₁ ) / ( x₂ - x₁ )

密码体制实现

• 嵌入消息m：选取k,30<=k<=50,令x=k*m+j;j=0,1,2···,验证是否存在以x为横坐标落在曲线上的整数点

• 密钥生成：设E_p(a,b)是曲线上的整数点集;取生成元G，接收者选取x_A作为秘密密钥，P_A = x_A * G 作为公开密钥

• 加密运算：发送者向接收者发送信息P_m,选取正整数k，密文C_m={k * G , P_m+k * P_A}

• 解密运算：P_m = P_m + k * P_A - n_A * k * G