0%

密码学系列:非对称加密

非对称加密有两个密钥:公钥和私钥,公钥用来加密数据,私钥用于解密

他们都源于一个公共原理:单向函数

单向函数的定义:

函数 f() 是一个单向函数,当且仅当:

  1. y = f(x) 计算比较容易
  2. x = f’ (y) 计算是不可行的(需要的时间太长)

目前的公钥方案中主要使用了两个主流的单向函数:

  1. 大整数的因式分解
  2. 离散对数问题(DLP问题)

本文主要介绍 RSA 跟 ECC 这两种非对称加密算法

RSA

安全建立在基于大整数的因数分解问题(即对 N 的质因数分解求 p、q)

密文 = 明文^E (mod N)

对明文的加密过程就是明文的 E 次方对 N 求余,知道了 E 和 N 就可以对明文进行加密了,所以 E 和 N 的组合就是公钥

明文 = 密文^D (mode N)

对密文的解密过程就是密文的 D 次方对 N 求余,知道了 D 和 N 就可以对密文解密了,所以 D 和 N 的组合就是私钥

生成密钥对过程:

  1. 生成 N
    N = p * q ( p和q为质数 )
    L = lcm(p-1,q-1) ( lcm 为求最小公倍数 )
  2. 生成 E
    1 < E < L
    gcd(E,L)=1 ( gcd 为求最大公约数 )
  3. 生成 D
    1 < D < L
    E * D (mod L) = 1

ECC

基础知识

模运算

a = r (mod m) , r为余数,m为模数,r<m

例:42= 6 (mod 9)

群指的是一个元素集合 G 以及 两个元素值之间的操作 o 的集合,即 (G,o):

  1. 群操作 o 是封闭的,即对所有的 a b,a b 属于G, a o b = c,c 也属于 G。
  2. 群操作 o 是可结合的,即 ao(boc) = (aob)oc。
  3. 存在一个元素 1 ,对所有的 a ,a 属于 G,均满足 a o 1 = 1 o a = a ,这个元素叫中性元或单位元
  4. a o a’ = a’ o a = 1,a’叫做 a 的逆元
  5. 如果 a o b = b o a,则群 G 为阿贝尔群或可交换群

有限群:

一个群 (G,o) 是有限的,仅当他拥有有限个元素,G 的基或阶可以表示为 |G|

密码学中使用的一般就是有限群

群的基或阶其实就是群元素的个数

例如:(Zn,+)Zn 的基为 |Zn|=n,因为 Zn = {0,1,2,… ,n-1}

元素的阶:

是指满足以下条件的最小正整数 k:
ord(a) = a^k = a o a o a …..a = 1 ,1 是单位元

循环群:

如果群 G 包含一个拥有最大阶 ord(x) = |G| 的元素 x,则这个群是个循环群,拥有最大阶的元素成为生成元。

这个 x 的幂值可以表示整个群

例:Z11 = {1,2,3,4,5,6,7,8,9,10}

x = 2 为生成元

基为 |Z11| = 10

2^10 = 1 (mod 11), 2的阶为10,即ord(2) = |Z11|

2 的幂值生成了所有元素

定理:

每个素数 p,( Zp,* )都是一个阿贝尔有限循环群

该定理说明每个素数域的乘法群都是循环群,对于构建离散对数密码体制非常重要

Hasse’s定理:
给定一个曲线E mod p ,曲线上的点的个数表示为 #E 则:
p+1-2√p<=#E<=p+1+2√p

离散对数问题

基于Zp的离散对数问题(DLP):

给定一个阶为 p-1 的有限循环群Zp,生成元为 a,b为另一个元素,DLP问题就是确定满足以下条件的整数 x( 1 <= x <= p-1 )的问题:
a^x = b (mod p)

当参数非常大的时候,求解 x 非常困难

推广的离散对数问题:

给定一个基为 n 的有限循环群 G,群操作为 o。生成元为a,b为另一个元素,DLP问题就是找到x(1 <= x <= n)使得:
a^x = a o a o a …. o a = b

椭圆曲线离散对数问题:

给定一个椭圆曲线E,群操作为+,生成元 G,T为另一个元素,dl问题就是找到 k(1 <= k <= #E) 使得:
kG = G + G + G +…+G = T

公钥密码体制正是找到了这样的一个群是的DLP问题成为了一个单向函数

应用在密码学中的椭圆曲线

基于椭圆曲线的非对称加密,跟 rsa 相比,密钥更短,强度更高

安全建立在基于椭圆曲线的离散对数问题,是一种推广的离散对数问题

  1. 二元三次曲线 y^2 = x^3 + a * x + b (mod p) (其中p为大质数)
  2. 定义的运算 P + Q = R,都是曲线上的点

循环群为椭圆曲线上的点,群操作为 +

抽象的无穷的点 0 为单位元,满足 P+0 = P

逆元 P+(-P) = 0,满足 -P = (Xp,p-Yp)

secp256k1曲线

基本参数:

  • 离散曲线: y^2 = (x^3 + 7) mod p(其中x和y都是整形保证了离散)
    p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    a=0
    b=7

  • 基点 G
    G(“0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798”,
    “483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8”)

  • 点的集合 {G,2G,3G,… ,nG},nG=O,O 为抽象的无穷点即单位元
    n=”0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141”

私钥生成公钥原理:

在上边的离散的椭圆曲线上,定义一套运算规则:

加法:P+Q = R
乘法: K=kG

k 为私钥,K 为公钥{r,s},G为曲线上一点。

由 k、G 算 K 简单,由 K、G 推出 k 极难。