密码学备忘录-公钥密码

1. 对称密码体制的局限性

  • 密钥分发问题
    • 可信信道
  • 密钥量问题
    • 密钥量太大
    • n个用户n(n-1)/2个密钥
  • 数字签名问题
    • 通信双方共享一个密钥，用该密钥进行加密生成签名，无法防止通信双方的抵赖和欺骗行为
  • 无法解决陌生人之间的身份认证和交易信息认证问题

2. 公钥密码设计要求

  • 计算是容易的
  • 分析是不可行的
  • 加密变换和解密变换可以互换顺序

核心：单向陷门函数

从一个方向求值是容易的，而其逆向计算却很困难，以至于在实际上是不可行的。

3. 算法分类

  • RSA
    • 基于大整数因子分解的公钥密码
  • ElGamal
    • 基于有限域乘法群上的离散对数问题的公钥密码
  • ECC
    • 基于椭圆曲线上的离散对数问题的公钥密码

3.1. RSA

欧拉函数

性质

性质三的延展

其他性质

  • 对于每个能够整除n的正整数d，其欧拉函数之和恰好为n。或者说，n的所有因子的欧拉函数之和等于n

欧拉定理

Let a and m be two integers that are coprime互质. Then

  • $a^{φ(m)}≡1(\bmod{m})$

费马小定理则是欧拉函数的弱化版，结论不变，但条件从a,m互质变成m为质数

  • 但总之都有$gcd(a,m)=1$

3.1.1. RSA密钥的产生

寻找大素数时一般是先随机选取一个大的奇数(例如用伪随机数产生器)，然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。

应用

  • 密钥长度太大会使得密钥产生和加解密运算太慢
  • 因而，公钥密码体制目前主要用于密钥管理和数字签名

防御

  • RSA1024如今也已经被认为是不安全的了

3.1.2. 步骤

  • 纠正，p，d应当被销毁，私钥为{n, d}

3.2. Diffie-Hellman

Diffie和Hellman提出了一个公钥分发系统，该系统基于在有限域GF(p)上计算对数的明显困难，p为素数。

set-up:

  • All participants share as system parameters a prime number p and a primitive element q in GF(p).
  • Each participant P chooses an integer A, 1<A<=p-2, at random, computes y=q^A mod p and puts y in the public key book. Participant P keeps A secret.
    • (?)公钥就是(Ya、Yb、p、q)

3.3. ElGamal public key cryptosystem

基于迪菲-赫尔曼密钥交换的非对称加密算法

  • 它的安全性取决于G上的离散对数难题（同diffie-hellman）

3.3.1. ElGamal’s Secrecy System

  • 建立在diffie-hellman的set-up上：
    • 公有有p、q、Yb，Bob私有B
    • Alice想要送x，且 x in {0,1,...,p-1}
    • 随机整数r，计算R=q^r、S=u*Yb^r.
      • 为了减小计算一般将R与S分别Mod p
    • Alice传递(R,S)
  • 解密：
    • ${S}/{R^B}={u*Y_b^r}/{q^{rB}}=u=x$

3.3.2. 共同点

  • Two public-key systems are described that are based on the discrete logarithm problem
  • In both systems the transmitted text is longer than the plaintext.

3.4. Elliptic Curve cryptography

  • 椭圆曲线密码学（ECC）的主要优势是它相比RSA加密算法使用较小的密钥长度并提供相当等级的安全性
    • 美国国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA和DSA是最小2048位，ECC是最小224位，相应的对称密钥加密的密钥长度是最小128位，这样的组合在2030年以前是安全的
  • 解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群

数学

  • 维尔斯特拉斯（Weierstrass）通用式：$y^2=x^3+ax+b$
  • 为了让椭圆曲线没有奇异点，即处处光滑可导，需要满足其判别式不为零
    • ${\Delta}=4a^3+27b^2{\neq}0$
  • 对椭圆曲线群作如下定义
    • 单位元为无穷远点O
    • 某点的相反数为该点在椭圆曲线上关于X轴对称的点，即点P有相反数-P
    • 随机取椭圆曲线上两点P和Q，经过这两点的直线与椭圆曲线相交于第三点R，这里定义加法规则：P+Q+R=0
      • 交换律和结合律都存在，故椭圆曲线群为阿尔贝群，可以直接使用其性质，如有n个P点相加，可以表示为nP
    • 如果只有两个交点：
      • 其中一点是切点的情况下（切线），P=Q，这种情况下，加法规则P+Q+R=0仍旧成立（形式上可能会变成P+P+R=0或者P+R+R=0、Q+Q+R=0）
      • 所取两点正好是相反数（垂直于X轴的线），P和-P，其相加自然为0。当然，换成另一种说法，也可以说第三个交点在无穷远处，即P+(-P)+0=0
    • 如果只有一个焦点
      • 三重点，在这点上，切线与椭圆曲线的交点仍为本身，即P+P+P=0。一般来说y>0时，切线斜率最小处的点就是该三重点

抽象理解

简化步骤：

  • 定义一个曲线
  • 求解椭圆曲线上的点集${E_p}(a,b)$
  • 定义加法、倍乘运算法则

椭圆曲线离散对数问题（ECDLP）就是给定点P和Q，确定整数k使 $k ∗ P = Q$ – 一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）并不等价；ECDLP比DLP要困难的多。

阶计算

3.4.1. EC ElGamal

  • 椭圆曲线上的离散对数问题
  • 是ECC的一种，把ElGamal移植到椭圆曲线上来实现

4. 参考