公共密钥加密,又称非对称加密,是一种密码学算法类型,这种算法需要两个密钥,一个是私人密钥,另一个则是公开密钥。我们将公钥公之于众进行加密,而保存私钥用于解密。这种算法的优点是不需要经过安全渠道传递密钥,简化了密钥管理过程

1976 年,Whitfield Diffie 和 Martin Hellman 发表的论文 New directions in cryptography 展示了一种算法,表明非对称加密或是公共密钥加密是可行的;整个学界哗然,划时代的密码体制就此诞生了。现代密码学的溯源其实反反复复也最终还是追随到 Diffie and Hellman 这两位人身上。可以说,称 Diffie-Hellman 密钥交换算法为密码学史上的革命也丝毫不为过。新生的现代密码学,为我们个人通信、商业机密的传送提供了强有力的保障。比如 Https 协议的 TSL (Transport Layer Security) 以 DH 算法作为密钥交换算法。

Diffie-Hellman 算法原理

手上保存私钥,公开公钥;在离散对数中,由 K 求出 k 很难,通过公钥解出私钥几乎是不可行的。也就是说算法的安全性是基于离散对数的复杂度

K=kbamodn=(gbmodn)amodn=gbamodn=(gamodn)bmodn=kabmodn=KK=k_b^amodn=(g^bmodn)^amodn=g^{ba}modn=(g^amodn)^bmodn=k_a^bmodn=K

通过下面这张图或许能更直白地理解数学概述的抽象原理:

该算法的唯一目的是为了让用户能够安全交换密钥得到一个共享的会话密钥,算法本身不具备加密解密的功能。

由于 DH 在传输 n,g 时并无身份验证,如果攻击者可以在信道的中央窜改两边收发的消息,就可以假扮身份完成两次 Diffie-Hellman 密钥交换。这样攻击者就可以解密全部的信息。所以在替换双方传输时的数据有机会被实施中间人攻击

应运而生的是 Oakley 算法 —— 对 Diffie-Hellman 密钥交换算法的优化,它保留了后者的优点,同时克服了其弱点。

Oakley 算法具有五个重要特征:

  1. 它采用称为 cookie 程序的机制来对抗阻塞攻击。

  2. 它使得双方能够协商一个全局参数集合。

  3. 它使用了现时来保证抵抗重演攻击。

  4. 它能够交换 Diffie-Hellman 公开密钥。

  5. 它对 Diffie-Hellman 交换进行鉴别以对抗中间人的攻击。

Oakley 可以使用三个不同的鉴别方法:

  1. 数字签名:通过签署一个相互可以获得的散列代码来对交换进行鉴别;每一方都使用自己的私钥对散列代码加密。散列代码是在一些重要参数上生成的,如用户 ID 和现时。

  2. 公开密钥加密:通过使用发送者的私钥对诸如 ID 和现时等参数进行加密来鉴别交换。

  3. 对称密钥加密:通过使用某种共享密钥对交换参数进行对称加密,实现交换的鉴别。

与 RSA 的区别

每次会话时都产生随机的(a,b)值,未来的密钥泄漏并不会破解之前的会话密钥。这也说明了迪菲 - 赫尔曼密钥交换是支持前向保密的

Elgamal 公钥加密算法

基于迪菲 - 赫尔曼密钥交换演化出来的 ElGamal 加密算法,可以用来加密 / 解密消息,但是由于一些历史原因以及 RSA 公钥加密算法的巨大商业成功,ElGamal 加密算法并不流行。

Alice选取一对(g,p),a作为【私钥】,然后计算出A=ga作为【公钥】。Alice(g,p,A)公布给所有人。Bob现在想给Alice传送一条信息m.于是Bob选取一个随机数k,计算出c1=gk,c2=mAkSENDAlice(c1,c2)Alice 选取一对 (g,p), a作为【私钥】,然后计算出 A=g^a 作为【公钥】。\\ Alice 将 (g,p,A)公布给所有人。\\Bob 现在想给 Alice 传送一条信息 m. 于是 Bob 选取一个随机数 k, 计算出c_1=g^k, \quad c_2=mA^k \quad \\SEND Alice(c_1,c_2)

Alice's operation

calculatec1ac2=gkamgak=mcalculate \quad c_1^{-a}·c_2=g^{-ka}·m·g^{ak}=m

Alice 成功获取 m

Elgamal 的安全性与 DH 是一致的

产生密钥

首先选择一个素数p和两个小于p的随机数gx,计算ygxmodp.(y,g,p)作为公钥,x作为私钥首先选择一个素数p和两个小于p的随机数g和x,计算y\equiv g^xmodp.以(y,g,p)作为公钥,x作为私钥

加密明文 M

首先选择一个和p1互素的整数k,计算C1gkmodp,C2ykmodp,密文C=(C1,C2)首先选择一个和p-1互素的整数k,计算C_1 \equiv g^kmodp,C_2 \equiv y^kmod p,密文C=(C_1,C_2)

解密

M=C2C1Xmodp=ykMgkxmodp=ykMykmodp=MmodpM= \frac{C_2}{C_1^X}modp=\frac{y^kM}{g^{kx}}modp=\frac {y^kM}{y^{k}}modp=Mmodp

基于椭圆曲线的 Diffie-Hellman 密钥交换

首先约定好一个Abel群构成的Ep(a,b),Ep(a,b)的一个生成元G(x1,y1)G的阶要满足素数并且nG=On最小正整数)Ep(a,b)G作为公开参数。首先约定好一个Abel群构成的E_p(a,b),E_p(a,b)的一个生成元G(x_1,y_1)\\G的阶要满足素数并且nG=O(n\in最小正整数)E_p(a,b)和G作为公开参数。

Alice保存nA,Bob保存nBP=npG产生Ep(a,b)上的一点作为公开钥计算AliceK=nAPB,BobK=nBPA令Alice保存n_A,Bob保存n_B\quad P=n_pG产生E_p(a,b)上的一点作为公开钥\\计算Alice的K=n_AP_B,Bob的 K=n_BP_A

例如

E = EllipticCurve(GF(3851), [324, 1287])
G = E(920, 303)
nA = 1194
PA = nA * G
nB = 1759
PB = nB * G
KA.xy(), KB.xy()
# ((2067, 2178), (3684, 3125))

PAPB,butKA=KBP_A\neq P_B,\quad but\quad K_A=K_B

#密钥协商 共享密钥
print((nA * PB).xy())
# (3347, 1242)
print((nB * PA).xy())
# (3347, 1242)

椭圆曲线 上的 Elgamal 公钥密码体制

首先约定好一个Ep(a,b),将明文m嵌入曲线点pm,做加密变换;Ep(a,b)的一个生成元G(x1,y1),Ep(a,b)G作为公开参数。首先约定好一个E_p(a,b),将明文m嵌入曲线点p_m,做加密变换;\\取E_p(a,b)的一个生成元G(x_1,y_1),E_p(a,b)和G作为公开参数。

Alice选取nA,P=nAG为公开钥,Bob选取随机数k,生成密文Cm={kG,Pm+kPA}Alice选取n_A,P=n_AG为公开钥,Bob选取随机数k,生成密文C_m=\lbrace kG,P_m+kP_A\rbrace

C1=kG,C2=M+kPAC_1=k·G, \quad C_2=M+k·P_A

Alice 受到后解密

C2nAC1=M+kPAnAkG=MC_2-n_AC_1=M+k·P_A-n_AkG=M

举个梨子

# ----- Alice 公开公钥 -----
E = EllipticCurve(GF(3851), [324, 1287])
G = E(920, 303)
nA = 1194
PA = nA * G
print(PA.xy())
# (2067, 2178)
# ----- Bob 发送信息 -----
M = E.lift_x(233)
k = 123
C1 = k * G
C2 = M + k * PA
C1.xy(), C2.xy()
# ((2525, 1772), (255, 2423))
# ----- Alice 接受信息 -----
msg = C2 - nA * C1
msg.xy()
# (233, 495)

椭圆曲线密码体制的优点

与基于有限域于上离散对数体系相比

  1. 安全性高

    攻击有限域上的离散对数问题是有指数积分法,运算复杂度为O(exp(logp)(loglogp)23),p是模素数攻击有限域上的离散对数问题是有指数积分法,运算复杂度为O(exp\sqrt[3]{(logp)(loglogp)^2}),p是模素数

    目前攻击椭圆曲线上的离散对数问题只适合攻击任何循环群上离散对数问题的大步小步法,运算复杂度为O(exp(logpmax))pmax是椭圆曲线上Abel群的阶的最大素因子目前攻击椭圆曲线上的离散对数问题只适合攻击任何循环群上离散对数问题的大步小步法,\\运算复杂度为O(exp(log\sqrt {p_{max}})) \quad p_{max}是椭圆曲线上Abel群的阶的最大素因子

  2. 密钥量小

    复杂度对比,椭圆曲线所需密钥长度更短

  3. 灵活性好

    椭圆曲线可以通过更改曲线参数实现不同的曲线,形成不同的循环群,比有限域上固定好的循环群更加丰富且多选择

ECC 和 RSA/DSA 在保持同等安全性的情况下密钥长度对比 (bits)

RSA/DSA5127681024204821000
ECC106132160211600

Diffie-Hellman 算法主要是实现密钥交换,并没有加密解密的算法,理解起来可能有些抽象,不过不抽象也就不是数学了。椭圆曲线上的密码体系目前也只是潦草掌握,毕竟 ECC 和离散一样也是一座数学大山。怎么说呢,学无止境吧。

如果你读的还算尽兴的话给个赞哦👍

更新于

请我喝[茶]~( ̄▽ ̄)~*

1sme 微信支付

微信支付