第4章：公钥密码

公钥密码的基本原理

公钥密码的基本概念

  • 历史背景
    • 1976年，Diffie和Hellman在”密码学的新方向”一文中首次提出了公钥密码体制的思想。

公钥密码的基本概念

  • 公钥密码体制与对称密码体制完全不同，使用数学函数而不是代替和置换。
  • 公钥密码算法是非对称的，使用两个独立的密钥：公钥和私钥。
  • 公钥密码体制在消息的机密性、密钥分配和认证方面具有重要意义。

优势

  • 密钥分配：公钥可以通过公开信道传输，而对称密码体制需要通过安全的秘密通道共享密钥，代价较大。
  • 密钥管理：在N个用户的系统中，每个用户只需安全保管自己的私钥和N-1个其他用户的公钥，整个系统仅需维护N个公钥；而对称密码体制中，每个用户需使用n-1个密钥，总密钥数量为n(n-1)/2。
  • 数字签名：提供类似书面手写签名的方法，确保数字签名出自某特定人，并且各方对此无异议。对称密码体制中难以解决陌生人之间的身份认证问题。

原理

  • 公钥密码体制在加密和解密时使用不同的密钥：公钥用于加密，私钥用于解密。公钥是公开信息，不需要保密，私钥需保密。
  • 给定公钥，要计算出私钥在计算上是不可行的。
  • 这样的通信无需双方预先交换密钥就可以建立保密通信。

公钥密码体制的模型

  • 加密模型：接收者B生成一对密钥(pkB, skB)，其中pkB是公钥，skB是私钥。发送者用pkB加密要发送的消息m，接收者用skB解密收到的加密消息c。
  • 认证模型：A用自己的私钥skA对m加密（实际上为签名），然后发送c给B。B收到c后，利用A的公钥pkA对c解密（实际上为验证），获得对消息来源的认证和数据完整性的保护。

安全性要求

  • 接收者$B$产生一对密钥在计算上是容易的。
  • 发送者$A$产生相应的密文$c=E(pkB, m)$在计算上是容易的。
  • 对密文解密以恢复出明文$m=D(skB, c)$在计算上是容易的。
  • 已知公钥$pkB$，敌手要求解私钥$skB$在计算上是不可行的。
  • 已知公钥$pkB$和密文$c$，敌手要恢复出明文$m$在计算上是不可行的。

陷门单向函数

  • 陷门单向函数是满足下列条件的可逆函数f：
    1. 对于任意的$x$，计算$y=f(x)$是容易的。
    2. 对于任意的$y$，计算x使得$y=f(x)$是困难的。
    3. 存在陷门$t$，已知$t$，对于任意的$y$，计算$x$使得$y=f(x)$是容易的。

常见的陷门单向函数

  1. 大整数分解问题：已知两个大素数$p$和$q$，求$n=pq$是容易的，而由$n$求$p$和$q$则是困难的。
  2. 离散对数问题：给定一个大素数$p$，已知$x$，求$y≡gx \mod p$是容易的，而已知$y$, $g$, $p$，求$x$使得$y≡gx \mod p$成立则是困难的。
  3. 多项式求根问题：有限域$GF(p)$上的一个多项式已知$a0$, $a_1$, $…$, $a{n-1}$ ,$p$和$x$，求$y$是容易的，而已知$y$, $a0$, $a_1$, …, $a{n-1}$，求$x$则是困难的。
  4. 决策性$Diffie-Hellman$问题：给定素数$p$，令$g$是$𝒁𝒑∗$的一个生成元。已知$a=gx$, $b=gy$, $c=gz$，判断等式$z ≡ xy \mod p$是否成立。
  5. 二次剩余问题：给定一个合数$n$和整数$a$，判断$a$是否为$\mod n$的二次剩余。
  6. 背包问题：给定向量$A$和$x$，求和式$S=f(x)$是容易的，而由 $A$ 和 $S$ 求 $x$ 则是困难的。
RSA密码

RSA算法描述

  • RSA由Ron Rivest、Adi Shamir和Leonard Adleman于1978年提出。

密钥生成

  1. 选取两个互异大素数$p$和$q$。
  2. 计算 $n=p×q$ 及其欧拉函数值$φ(n)=(p-1)(q-1)$。
  3. 选择一个整数$e$，$1 < e<φ(n)$，使得$gcd(φ(n), e)=1$。
  4. 计算$e$的逆元$d$，使得$ed≡1 \mod φ(n)$。
  5. 公钥为$(e, n)$，私钥为$d$。

RSA加密

  • 给定明文$m$，$0≤m<n$，计算$c≡me \mod n$。

RSA解密

  • 对于密文$c$，计算$m≡cd \mod n$。

RSA解密的正确性

  • 由加密过程知$c≡me \mod n$，又$de≡1 \mod φ(n)$，故$cd \mod n≡med \mod n≡m \cdot 1+rφ(n) \mod n$。

RSA的安全性

  • 数学攻击：主要途径包括分解4为两个素因子、直接确定$φ(n)$以及直接确定$d$。对$RSA$的密码分析主要集中于分解$n$为两个素因子。
  • 大素数的素因子分解：随着计算能力的提高，模数长度为1024bits存在安全缺陷，建议模数长度应大于1024bits。
  • 参数p和q的限制条件：$p$和$q$的长度应该相差仅几位，$(p-1)$和$(q-1)$应有一个大的素因子，$gcd(p-1, q-1)$应较小。
  • 穷举攻击：使用大的密钥空间抗穷举攻击，但密钥越大，系统运行速度越慢。
  • 计时攻击：通过记录计算机解密消息所用的时间来确定私钥。
  • 选择密文攻击：敌手通过计算得到明文$m$。
椭圆曲线密码

基本概念

  • 椭圆曲线的方程是以下形式的三次方程：$y² + axy + by = x³ + cx² + dx + e$，其中a，b，c，d，e是满足某些条件的实数。

椭圆曲线密码体制

  • 椭圆曲线密码体制是基于椭圆曲线离散对数问题（ECDLP）的困难性来设计的。

  • 密钥生成：在椭圆曲线$Ep(a, b)$上选取一个生成元P，随机选取整数$x$，计算$Q=xP$。公钥为$Q$，私钥为$x$。

  • 加密：随机选取整数k，计算$C1=kP$,$ C2=Pm+kQ$，密文为$(C1, C2)$。

  • 解密：计算
    $C2-xC1=Pm+kQ-xkP=Pm$

优点

  • 安全性高：相同的密钥长度下，椭圆曲线密码体制比RSA或DSA更安全。
  • 密钥长度小：在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥长度远小于基于有限域上的离散对数问题或大整数分解问题的公钥密码体制的密钥长度。
  • 算法灵活性好：椭圆曲线具有丰富的群结构和多选择性。