浅谈非对称加密

课程作业要求，简单的归纳关于Diffie-Hellman密钥交换技术、RSA加密以及椭圆曲线的一些基本知识点。

对称加密与非对称加密

密码学发展至今是有一个过程的，从最基本的隐写术开始，到古典密码，再到近现代密码。在过去人们主要研究的是对称加密，即在密码算法足够强大的基础上，通过对密钥的保密实现加密交流。比如DES、AES等密码都属于对称密码。

对称密码有如下特点：

优点：加解密处理速度快、保密度高。

缺点：

  • 如何安全的传输密钥到收信方是一个问题。
  • 多人通信时密钥组合的数量会出现爆炸性膨胀。
  • 双方必须统一密钥，如果收信人与发信人素不相识，就无法向对方发送加密信息
  • 存在数字签名困难问题，即消息可能被伪造

于是我们引入了非对称加密，非对称加密给密码学注入了新的活力，开辟出了一片富有探索价值的新区域。非对称加密即发信方与收信方不共享同一密钥，而是分别保存各自的私钥，用对方的公钥进行通信。

非对称加密有如下特点：

优点：

  • 网络中的每一个用户只需要保存自己的私钥，密钥少，便于管理
  • 密钥分配简单，不需要秘密的通道和复杂的协议来传送密钥
  • 可以实现数字签名

缺点：加密、解密的速度相对较慢，同等安全强度下所要求的密钥位数多一些

一般来说，我们在密钥分发时采取非对称加密交换密钥，建立起加密通信通道后就采用对称加密进行通信。这样既解决了对称加密密钥分发的问题，又解决了非对称加密速度慢的问题。

非对称加密和对称加密的区别整理如下表：

分类 对称密码体制 非对称密码体制
运行条件 加密和解密使用同一个密钥和同一个算法；发送方和接受方必须共享密钥和算法 用同一个算法进行加解密，但是密钥有一对，其中一个用于加密，一个用于解密；发送方和接受方每个使用一对相互匹配而彼此互异的密钥中的一个。
安全条件 密钥必须保密；仅根据密文解密明文是不可能或不现实的；已知算法和密文无法确定密钥 密钥对中的私钥必须保密；仅根据密文解密明文是不可能或不现实的；已知算法、密文和公钥无法确定私钥
保密方式 基于发送方和接受方共享的密钥 基于接收方个人的私钥
基本变换 面向符号（字符或位）的代替或换位 面向数字的数学函数变换
适用范围 消息的保密 用于短消息的保密（如对称加密中的密钥交换），或认证、数字签名等

Diffie-Hellman密钥交换

Alice Bob
秘密信息 公开信息 公开信息 秘密信息
A和B首先约定两个公开的整数p和a p, a p, a
A、B各自随机产生两个数XA、XB，作为自己的私钥 XA XB
A、B各自计算自己的公钥YA、YB 计算 YA YB 计算
YA=a^XA mod p YB=a^XB mod p
交换公钥YA、YB YB YA
计算出加密用的密钥K 计算 计算
K=(YB)^XA mod p K=(YA)^XBmod p

也即：K=(YB)XA mod p=(aXB mod p)XA mod p=(aXB)XA mod p=(aXA)XB mod p=(YA)XB mod pK=\left(Y_{\mathrm{B}}\right)^{X_{\mathrm{A}}} \bmod p=\left(a^{X_{\mathrm{B}}} \bmod p\right)^{X_{\mathrm{A}}} \bmod p=\left(a^{X_{\mathrm{B}}}\right)^{X_{\mathrm{A}}} \bmod p=\left(a^{X_{\mathrm{A}}}\right)^{X_{\mathrm{B}}} \bmod p=\left(Y_{\mathrm{A}}\right)^{X_{\mathrm{B}}} \bmod p

用此算法可以安全的交换通信密钥，但是有可能遭受中间人攻击篡改Bob发送的信息。

例题

image-20240605203507296

RSA加密

密钥生成

  1. 首先选择互异的大素数p,q，计算n=p*q，由欧拉定理计算大素数乘积的欧拉数φ(n)=(p-1)(q-1)。
  2. 选择整数e使得gcd(φ(n),e)=1，其中1<e<φ(n)。
  3. 计算d=e-1mod φ(n)。
  4. 此时公钥KU={e,n}
  5. 私钥={d,φ(n)}

算法描述

  1. 加密(用e, n)：对明文进行分组，使得每个分组对应的十进制数小于𝑛。对每个明文分组𝑚做加密运算：

    c≡me mod nc \equiv m^{e} \bmod n

  2. 解密(用d，n)

    m≡cd mod nm \equiv c^{d} \bmod n

证明

我们仅验证gcd(a,n)=1的情况

对于加解密过程，我们尝试证明me≡ced mod nm^{e} \equiv c^{ed} \bmod n是否能推出me≡c mod nm^{e} \equiv c \bmod n

因为de≡1 mod φ(n)de \equiv 1 \bmod φ(n)，即de≡k⋅φ(n)+1de \equiv k·φ(n)+1

故有ced=ck⋅φ(n)+1=ck⋅φ(n)⋅cc^{ed}=c^{k·φ(n)+1}=c^{k·φ(n)}·c

欧拉定理：若n,a为正整数，且n,a互质，则:a^φ(n)≡1 (mod n)其中φ(n)是欧拉函数

由欧拉定理，ck⋅φ(n)≡1 mod nc^{k·φ(n)} \equiv 1 \bmod n，故有ck⋅φ(n)+1≡c mod nc^{k·φ(n)+1} \equiv c \bmod n

也就是ced≡c mod nc^{ed} \equiv c \bmod n

即me≡c mod nm^{e} \equiv c \bmod n

得证

特点

密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出𝜑(n)＝(p-1)(q-1)，然后由公开的e，解出秘密的d 。

若使RSA安全，p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择p和q至少是1024比特的素数，模n的长度至少是2048比特。

例题

image-20240605205243297

椭圆曲线密码体制ECC

这是目前已知公钥密码体制中每位提供加密强度最高的一种体制

定义

椭圆曲线是一个具有两个变元x和y的三次方程，它是满足：

y2+axy+by=x3+cx2+dx+ey^2+axy+by=x^3+cx^2+dx+e

的所有点的集合，外加一个无穷远点O

实数域上的椭圆曲线是对于固定的a、b值，满足形如方程：

y2=x3+ax+by^2=x^3+ax+b

的所有点(x, y)的集合，外加一个无穷远点O。其中a**、**b是实数，满足4a2+27b3≠0。x和y在实数域上取值。

有限域GF(p)上的椭圆曲线

有限域GF(p)上的椭圆曲线是对于固定的a、b值，满足形如方程：

y2≡x3+ax+b( mod p)y^2\equiv x^3+ax+b (\bmod p)

的所有点(x, y)的集合，外加一个无穷远点O

其中a、b、x和y均在有限域GF(p)即{0,1,…,p-1}上取值，且满足4a2+27b3≠0，p是大素数。

接下来我们讨论有限域GF(p)上的椭圆曲线。

  • 该曲线由p、a和b完全决定，故一般可记为Ep(a,b)

  • 该椭圆曲线只有有限个点数N（称为椭圆曲线的阶，包括无穷远点）。它与安全性相关，N越大安全性越高

  • 粗略估计时，N近似等于p；更精确的范围由Hasse定理确定

image-20240605210619155
计算

GF(23)上的一个椭圆曲线：y2≡x3+x( mod 23)y^2\equiv x^3+x(\bmod 23)​，该椭圆曲线方程在GF(23)上的解为：

image-20240605210458949 image-20240605210520001

对Ep(a,b)的计算过程如下：

  1. 对每一𝑥（0 ≤ 𝑥 < 𝑝且𝑥为整数），计算x3+ax+b (mod p)
  2. 决定（1） 中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一𝑥相对应的点。如果有，则求出两个平方根（y=0时只有一个平方根）

决定是否有平方根涉及到平方剩余定理。

平方剩余

定理：设p是素数，a是一正整数，a是p的平方剩余的充要条件是：

a(p−1)/2≡1 mod pa^{(p-1)/2}\equiv 1 \bmod p

a是p的非平方剩余的充要条件是：

a(p−1)/2≡−1 mod pa^{(p-1)/2}\equiv -1 \bmod p

例：p=23，a=5， 𝑎(𝑝−1)/2 ≡ 5^11 mod 23 = −1

所以，5不是模23的平方剩余。

有限域GF(2m)上的椭圆曲线

是对于固定的a、b值，满足形如方程：

y2+xy=x3+ax2+by^2+xy=x^3+ax^2+b

的所有点(x, y)的集合，外加一个无穷远点O。其中a、b、x和y均在有限域GF(2m)上取值

  • 这类椭圆曲线通常也可用𝐸2^𝑚(a,b)来表示。
  • 该椭圆曲线只有有限个点，域GF(2m)上的元素是m位的二进制串
计算
image-20240606084648275 image-20240606084652100

运算规则

  • 加法规则1：O+O=O
  • 加法规则2：对于曲线上的所有点P满足P+O=P
  • 加法规则3：对于每一个点P有一个特殊点Q满足：P+Q=O，称这个特殊点为-P。如果P=(x, y)，则-P=(x, -y)
    • GF(2m)域加法规则3：如果P=(x, y)，则-P=(x, x+y)
  • 加法规则4：加法交换律P+Q=Q+P
  • 加法规则5：加法结合律P+(Q+R)=(P+Q)+R
image-20240606083935459 image-20240606083953668

以上加法规则在复数、实数、有理数和有限域GF(p)上均有效。对于有限域GF(p)的情形，上述加法规则得到的应是mod p的结果。

对于GF(2m)域的椭圆曲线，有规则6’，7’：

image-20240606084329142 image-20240606084344567

加密

椭圆曲线密码体制的依据就是利用定义在椭圆曲线点群上的离散对数问题的难解性。

椭圆曲线𝐸上的交换群上考虑方程𝑃 = 𝑑𝐺，其中𝑃, 𝐺 ∈ 𝐸，𝑑为整数，则由𝑑和𝐺易求𝑃，但由𝑃、𝐺求 𝑑是计算上不可行的

ECELG——椭圆曲线ElGamal密码体制

  1. 系统建立

    选择一个有限域GF(p)，和定义在GF(p)上的一条椭圆曲线Ep(a,b)，和Ep(a,b)上的一个阶为大素数n的点G（称为基点）。椭圆曲线Ep(a,b)、基点G和阶n作为系统公开参数

  2. 生成密钥

    用户A通过如下计算产生自己的公私钥对
    （1）在区间[1,n-1]中随机选取一个整数dA作为私钥
    （2）计算PA=dA×G
    则用户A的公钥为PA ，私钥为dA

  3. 加密

    当用户B要将消息m保密发送给用户A时，用户B进行如下操作：

    1. 通过某种方式将明文消息m通过编码映射到曲线Ep(a,b)上的点Pm
    2. 在区间[1,n-1]中随机选取一个整数dB作为私钥
    3. 计算PB=dB×G，并向用户A发送密文(PB, Pm + dB× PA)

  4. 解密

    用户A收到密文进行解密，过程如下：
    (Pm + dB× PA) - dA× PB

验证：(Pm+dB×PA)−dA×PB=Pm+dB×dA×G−dA×dB×G=Pm\left(P_{m}+d_{\mathrm{B}} \times P_{\mathrm{A}}\right)-d_{\mathrm{A}} \times P_{\mathrm{B}}=P_{m}+d_{\mathrm{B}} \times d_{\mathrm{A}} \times G-d_{\mathrm{A}} \times d_{\mathrm{B}} \times G=P_{m}

关于明文到椭圆曲线上的嵌入：

image-20240605213121828

例题

image-20240606084509649

常见加密算法及其数学基础

加密算法 类型 数学基础 描述
AES 对称加密 有限域上的代数操作 使用字节替代、行移位、列混淆和轮密钥加的多轮变换。
DES 对称加密 Feistel 网络和置换操作 基于 Feistel 结构，通过多轮置换和替换操作来加密数据。
RSA 非对称加密 大整数的质因数分解 基于两个大质数的乘积构成的模数和一个公开的指数。
ECC 非对称加密 椭圆曲线上的离散对数问题 使用椭圆曲线上的点和曲线方程来生成公钥和私钥。
DSA 非对称加密 离散对数问题 使用一组公开参数和一个私钥来生成和验证签名。
ElGamal 非对称加密 离散对数问题 基于离散对数问题，通过使用一个随机数和一个公钥来加密消息。
SHA-256 哈希函数 位操作和逻辑运算 通过多个复杂的位操作、替换和压缩函数生成固定长度的散列值。
MD5 哈希函数 位操作和逻辑运算 使用多个固定的位操作和压缩函数生成固定长度的散列值。
Diffie-Hellman 密钥交换 离散对数问题 基于离散对数问题，允许两个通信方生成共享的秘密密钥。
zk-SNARKs 零知识证明 多项式承诺和同态加密 允许一个方证明其拥有某个秘密信息而不透露该信息本身。

116586172_p0