【从0到0.1】公钥密码随缘笔记

本文涉及:非对称密码、抽象代数、数论

第一次更新:2021.09.26

第二次更新:2021.10.26

第三次更新:2022.02.26

0.前置知识

0.1.代数结构、模运算、群

大家都知道C语言中的bool值,异或,以及模运算:

0,1 (false,true)

^ (xor)

% (mod)

把异或运算作用在{0,1}上,很明显

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

其实,这是一种模2加法运算

(0 + 0) mod 2 = 0

(0 + 1) mod 2 = 1

(1 + 0) mod 2 = 1

(1 + 1) mod 2 = 0


不难发现,在{0,1}上的异或运算是唯一且封闭的。

像这样,有一个非空集合S = {0,1}以及作用在集合元素上的运算符(异或/模2加),称作一个代数系统(简称代数)

设 G = <S,+>是代数系统 (满足封闭性)

(1)如果+是可结合的,则称V为半群

(2)如果存在e ∈ S ,对于 aS\forall a ∈ S ,有 ea = ae = a ,则称e是S上的单位元

(3)如果G是半群且拥有单位元,即G = <S,+,e>,若aS\forall a \in S , 有 a1Sa^{-1} \in S ,则称G是群


总结一下,群的性质其实很简单:

一个集合,附带一个运算符

然后拥有封闭性,结合律,单位元,逆元

**P.S.**交换律不是构成一个群的必要条件,满足交换律的群称作交换群/阿贝尔群


0.2.加密与解密

加密就是让明文变成密文,

加密通常需要密码算法和密钥

密码算法就是一系列把明文变成密文的(复杂)步骤(或者说方法/函数)

密钥通常是(伪)随机数

明文和密钥是输入

将其投入到密码算法中

得到输出:密文

解密就是反过来


一些术语:

M: 明文

KeyGen:KeyGenerate,密钥生成,字面意思不解释了

Enc:Encrypt,加密

Dec:Decrypt,解密

pk:public key,非对称密码中的公钥,用来加密

sk:secret key,非对称密码中的私钥,用来解密

ϕ\phi:欧拉函数,习惯上也使用ϕ(N)\phi(N)phiphi表示

P.S. 对欧拉函数不是很了解的可以阅读:欧拉函数一个小的证明 | luo’s Blog


欧拉定理:

设 n 和 a 为正整数,且gcd(a,n) = 1,则:

aϕ(n)1 (mod n)a^{\phi(n)} \equiv 1\ (mod\ n)

其中gcd(a,n) 输出a与n的最大公因子,等于1时a与n互素


0.3.密码学中的一些“反常识”

to be continue


1.RSA

1.1.RSA构造公钥和私钥

KeyGen:

两个大素数p≠q,N = p*q ,ϕ=(p1)(q1)\phi = (p-1)(q-1),找到一个与ϕ\phi互素的元素ee计算出dd

使得de1 (mod ϕ)d*e \equiv 1\ (mod\ \phi)

pk = (N,e)

sk = d


对于de1 (mod ϕ)d*e \equiv 1\ (mod\ \phi)

我们很容易能想到,e是d关于ZϕZ_\phi^*的乘法逆元

关于乘法逆元的具体求法,请看luo41:乘法逆元求法总结

至于为什么要构造逆元,在下面的证明中会看到。


Enc(pk,M):CMe(modN)Enc(pk,M) :C \equiv M^e ( mod N )

输出CC

Dec(sk,M):MCd (mod N)Dec(sk,M) :M' \equiv C^d\ (mod\ N)

输出MM'


下面证明MM (mod N)M' \equiv M\ (mod\ N)

de1 (mod ϕ)∵ d*e \equiv 1\ (mod\ \phi)

de=kϕ+1∴ d*e = k\phi + 1

由欧拉定理得:

Mϕ1 (mod N)M^\phi \equiv 1\ (mod\ N)

MCdMedMkϕ+1MkϕMM (mod N)∴M' \equiv C^d \equiv M^{ed} \equiv M^{k\phi + 1} \equiv M^{k\phi}*M \equiv M\ (mod\ N)

当N>M时,M’ = M (这就是要求p和q是两个大素数的原因)



1.2. r-prime RSA

RSA的推广:其中 rZr∈Zr1r≥1

KeyGen:

r个不等的大素数,N=r1r2rnN = r_1*r_2*…*r_nϕ=(r11)(r21)(rn1)\phi = (r_1-1)*(r_2-1)*…*(r_n-1)

其余步骤一致


2.ELGamal

2.1.通过Diffie-Hellman密钥交换实现密钥配送问题

Alice和Bob是通信的双方

为了使加解密过程顺利且正确,所以无论用什么密码算法,Alice和Bob总是(至少)要交换密钥K

而在信道中交换K,不免得要考虑窃听的问题

P.S. 虽然这种方法的名字叫“密钥交换”,但实际上双方并没有真正交换密钥,而是通过计算生成出了一个相同的共享密钥。因此,这种方法也成为Diffie-Hellman密钥协商


运用以下方法使得K的交换顺利且窃听者无所获:

Alice或Bob任意一方生成大素数p和生成元g并告诉对方(不需要保密)


Alice拥有自己的随机数a,Bob拥有自己的随机数b (保密)

a,b[1,p2]a,b ∈ [1,p-2]


分别计算

A=ga mod pA = g^a\ mod\ p

B=gb mod pB = g^b\ mod\ p


Alice和Bob交换A和B

Alice计算 KBagba mod pK \equiv B^a \equiv g^{ba}\ mod\ p

Bob计算 KAbgab mod pK \equiv A^b \equiv g^{ab}\ mod\ p

显然相等

简单的计算实现了K的交换,而此时窃听者(有可能)得到了什么?

A、B和p、g

知道A和B不能求K,这是CDH(计算性Diffie-Hellman)问题。

知道gx mod pg^x\ mod\ p不能求xx,这是DLP(离散对数)问题。

P.S. 还有个决策性Diffie-Hellman问题(DDH),Tover说他读研再看,反正我不会


总而言之,窃听者想破解密码是困难的。


2.2. 基于Diffie-Hellman的ELGamal加密

KeyGen :

该步骤由Ailce完成

1ap11 \leq a \leq p-1 ; Aga(mod p)A \equiv g^a (mod\ p)

pk = A ; sk = a


Enc(pk,M):Enc(pk,M):

该步骤由Bob完成

随机数r;

C1gr (mod p)C_1 \equiv g^r\ (mod\ p)

C2MAr (mod p)C_2 \equiv M*A^r\ (mod\ p)

输出:C=(C1,C2)C = (C_1,C_2)


Dec(sk,C):Dec(sk,C):

该步骤由Alice完成

M(C1a)1C2(mod p)M' \equiv (C_1^a)^{-1} * C_2 (mod\ p),其中C1aArK (mod p)C_1^a \equiv A^r \equiv K\ (mod\ p)

输出:MM'


下面证明MM (mod p)M' \equiv M\ (mod\ p)

M(C1a)1C2(gra)1MAr(Ar)1MArM (mod p)M' \equiv (C_1^a)^{-1} * C_2 \equiv (g^{ra})^{-1}*M*A^r \equiv (A^r)^{-1}*M*A^r \equiv M\ (mod\ p)


当p>M时,M’ = M


2.3. Hash ELGamal

KeyGen:

1ap11 \leq a \leq p-1; Aga (mod p)A \equiv g^a\ (mod\ p)

pk = A ; sk = a


Enc(pk,M):Enc(pk,M):

随机数r ; C1gr (mod p)C_1 \equiv g^r\ (mod\ p) ; C2MH(Ar)(mod p)C_2 \equiv M \oplus H(A^r)(mod\ p)

输出:C=(C1,C2)C = (C_1,C_2)


Dec(sk,C):Dec(sk,C):

MH(C1a)C2 (mod p)M' \equiv H(C_1^a) \oplus C_2\ (mod\ p);

输出: MM'


3.椭圆曲线

3.0.about EC

沿用一下CINTA的定义

椭圆曲线:

F\mathbb{F} 为域,a,bFa, b ∈ \mathbb{F} 为常数,它们使得 Δ=4a3+27b20\Delta = 4a^3 + 27b^2 \neq 0。非奇异椭圆曲线 E(F)E(\mathbb{F}) 是满足方程 y2=x3+ax+by^2 = x^3 + ax + b 上的解集合 (x,y)F×F{(x, y) ∈ \mathbb{F} × \mathbb{F}} 加上一个称为无穷远点 (Point at infinity) 的特殊点 O ,并且 EE 在加法上形成一个有限交换群。


简单而言,所谓椭圆曲线(EC)就是满足以下方程的解,即序对 (x, y) 形成的集合:

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

其中,要求 Δ=4a3+27b20\Delta = 4a^3 + 27b^2 \neq 0


单位元:无穷远处的点O

逆元:当Q=P1Q = P^{-1}时,P与Q关于x轴对称且PQ连线相交于无穷远处(P + Q = O)

群加法:R=P+QR = P + Q

P=(xp,yp),Q=(xq,yq)EP = (x_p,y_p),Q = (x_q,y_q) \in E 表示椭圆曲线E上两点

所谓的加法就是作P和Q的连线,该直线与E相交于某个点,把这个点沿X轴翻转就得到了点R

P=Q时,P和Q的连线即为椭圆曲线的切线


P.S. 椭圆曲线不一定是“曲线”,详情请看CINTA


3.1 ECC

ECC: 椭圆曲线加密


KeyGen:

GE(Fp)G \leftarrow E(\mathbb{F_p});

选择一个整数n和群G内元素P(xp,yp)P(x_p,y_p)使得Q = n*P

pk = (Q,P);sk = n


Enc(pk,M):Enc(pk,M):

生成随机数r;

C1=rPC_1 = r*P;

C2=M+rQC_2 = M + r * Q

输出:C = (C_1,C_2)


Dec(sk,C):Dec(sk,C):

M=C2nC1M' = C_2 - n*C_1

输出:M’

显然 M’ = M


3.2 SM2

SM2、SM9是我国颁布的商用密码标准算法中的公钥密码算法,下面介绍SM2

Alice与Bob事先协商好相同的公开参数,包括p,n,E and G

其中p是大素数,E是定义在GF§上的椭圆曲线群,G是E的生成元

3.2.1 SM2数字签名算法

①密钥生成

a) 随机数 d[1,n2]d \in [1,n-2]

b) 计算 P=dGP = dG,并将 P 作为公钥公开,d 作为私钥保存

②签名

a) Alice 选取随机数 k[1,n1]k \in [1,n-1],计算 kG=(x1,y1)kG = (x_1,y_1)

b) 计算 r=(H(M)+x1) mod nr = (H(M)+x_1)\ mod\ n,其中 M=ZAmM = Z_A || m ,Z_A 是关于用户的可辨别标识、部分椭圆曲线系统参数和用户的公钥hash值,m是待签名信息,H为国家密码管理局核准的杂凑函数,如SM3;若 r=0 mod nr = 0\ mod\ nr+k=0 mod nr + k = 0\ mod\ n,则重新选取随机数 kk

c) 计算 s=(1+d)1(krd) mod ns = (1+d)^{-1}(k-rd)\ mod\ n ; 若 s0s \equiv 0,则重新选取随机数 kk ,否则,将 (r,s)(r,s) 作为签名结果


③验签

a) Bob 收到 MM(r,s)(r,s) 后,先检查 r,s[1,n1]r,s \in [1,n-1]r+s0 mod nr + s \neq 0\ mod\ n ;然后计算 (x1,y1)=sG+(r+s)P(x_1’,y_1’) = sG + (r+s)P

b) 计算 r=(H(M)+x1) mod nr' = (H(M)+x_1')\ mod\ n ;判断 r’ 与 r 是否相等,若相等则签名验证通过。


3.2.2 SM2密钥交换协议

Alice Bob
pk PAP_A PBP_B
sk dAd_A dBd_B
唯一标识 ZAZ_A ZBZ_B

Alice:

1)选取随机数 rA[1,n1]r_A \in [1,n-1],计算RA=rAG=(x2,y2)R_A = r_AG = (x_2,y_2) 并发送给Bob


Bob:

1)选取随机数 rB[1,n1]r_B \in [1,n-1] ,计算 RB=rBG=(x3,y3)R_B = r_BG = (x_3,y_3) 并发送给Alice

2)计算 xB=2w+(x3(2w1))x_B = 2^w + (x_3 \land (2^w-1))tB=(dB+xBrB) mod nt_B = (d_B + x_Br_B)\ mod\ n

3)验证接收到的 RAR_A 是椭圆曲线 EE 上的点,验证通过后计算 xA=2w+(x2(2w1))x_A = 2^w + (x_2 \land (2^w-1))

4)计算 V=tB(PA+xARA)=(xV,yV)V = t_B(P_A + x_AR_A) = (x_V,y_V);若 V 是椭圆曲线 E 上的无穷远点,则重新选取 rBr_B

5)计算 KB=KDF(xVyVZAZB,klen)K_B = KDF(x_V||y_V||Z_A||Z_B,klen)


Alice:

2)计算 xA=2w+(x2(2w1))x_A = 2^w + (x_2 \land (2^w-1))tA=(dA+xArA) mod nt_A = (d_A+x_Ar_A)\ mod\ n

3)验证接收到的 RBR_B 是椭圆曲线上的点,验证通过后计算 xB=2w+(x3(2w1))x_B = 2^w + (x_3 \land (2^w-1))

4)计算 U=tA(PB+xBRB)=(xU,yU)U = t_A(P_B+x_BR_B) = (x_U,y_U) ; 若 U 是椭圆曲线 E 上的无穷远点,则重新选取 rAr_A,重新协商。

5)计算 KA=KDF(xUyUZAZB,klen)K_A = KDF(x_U||y_U||Z_A||Z_B,klen)


经过以上协商,Alice与Bob共享密钥 KA=KBK_A = K_B


3.2.3 SM2公钥加密算法

M:比特长度为mlen的明文


EncEnc

1)选取随机数 l[1,n1]l \in [1,n-1] , 分别计算 C1=lG=(x4,y4) and lP=(x5,y5)C_1 = lG = (x_4,y_4)\ and\ lP = (x_5,y_5)

2)计算 e=KDF(x5y5,mlen)e = KDF(x_5||y_5,mlen)

3)计算 C2=MeC_2 = M \oplus eC3=H(x5My5)C_3 = H(x_5||M||y_5)

4)输出密文 C=C1C3C2C = C_1||C_3||C_2


DecDec

1)验证 C1C_1 是否在椭圆曲线上,计算 dC1=(x5,y5)d*C_1 = (x_5,y_5)

2)计算 e=KDF(x5y5,mlen)e = KDF(x_5||y_5,mlen)

3)计算 M=C2eM = C_2 \oplus e

4)计算 C3=H(x5My5)C_3' = H(x_5||M||y_5) ,并验证 C3=C3C_3' = C_3 是否成立

输出明文 M



3.-1. 圆锥曲线公钥加密算法

圆锥曲线不是椭圆曲线!详情自行百度。

那为什么这篇blog我要把它归在ec名下呢?

——故意让读者混淆的:)

4.Lattices

4.0 格是什么


一种代数结构。

P.S. 离散数学领域中格的概念不止一种,请注意此格非彼格。


4.1 同余公钥加密系统(NTRU简化版)

KeyGen:

很大的数字q,

数字 f,g 使得 f<q/2f < \sqrt{q/2} , q/4<g<q/2\sqrt{q/4} < g < \sqrt{q/2} , gcd(f,qg)=1gcd(f,q*g) = 1

gcd(f,qg)=1∵gcd(f,q*g) = 1

gcd(f,g)=1=gcd(f,q)∴gcd(f,g) = 1 = gcd(f,q)

mod gmod\ gmod qmod\ qff 都有乘法逆元


hf1g (mod q),0<h<qh \equiv f^{-1}g\ (mod\ q) , 0 < h < q

pk = (q,h)

sk = (f,g)


Enc(pk,M)Enc(pk,M)

0<M<q/40 < M < \sqrt{q/4}

生成随机数rr , $ 0 < r < \sqrt{q/2}$

erh+m (mod q)e \equiv r*h+m\ (mod\ q) , $ 0 < e < q$

输出:e


Dec(sk,e)Dec(sk,e)

afe (mod q)a \equiv f*e\ (mod\ q) , $ 0 < a < q$

bf1a (mod g)b \equiv f^{-1}*a\ (mod\ g) , $ 0 < b < g$

输出:b


下面证明 b = M

afef(rh+m)frf1g+fmrg+fm (mod q)a \equiv f*e \equiv f*(r*h+m) \equiv frf^{-1}g+fm \equiv rg+fm\ (mod\ q)

rg+fm<q/2+q/2<q∵ rg + fm < \sqrt{q/2}+\sqrt{q/2} < q

a=rg+fm∴a = rg+fm

bf1af1(rg+fm)f1fmm (mod g)∴ b \equiv f^{-1}a \equiv f^{-1}(rg+fm) \equiv f^{-1}fm \equiv m\ (mod\ g)

m<q/4<g∵ m < \sqrt{q/4} < g

b=m∴ b = m


4.2 背包加密

超递增序列:

r={r1,r2,...,rn}r = \{r_1,r_2,...,r_n\} , 使得 ri+12rir_{i+1} ≥ 2r_i

rk>rk1+...+r2+r1\therefore r_k > r_{k-1}+...+r_2+r_1


KeyGen:

大数 A,B , gcd(A,B) = 1 , B > 2r_n

构造新数列M使得:M_i \equiv Ar_i (mod B)

pk = M , sk = r,A

明文:x


Enc(pk,x)Enc(pk,x)

S=XM=i=1nxiMiS = X*M = \sum_{i=1}^nx_iM_i

输出:S


Dec(sk,S)Dec(sk,S)

SA1SA1i=1nxiMiA1i=1nxiArii=1nxiri (mod B)S' \equiv A^{-1}S \equiv A^{-1} \sum_{i=1}^n x_iM_i \equiv A^{-1} \sum_{i=1}^nx_iAr_i \equiv \sum_{i=1}^nx_ir_i\ (mod\ B)

B>2rn∵ B > 2r_n

i=1nxirii=1nri<2rn<B∴ \sum_{i=1}^nx_ir_i ≤ \sum_{i=1}^nr_i < 2r_n < B

S=xiri∴ S' = \sum{}x_ir_i

利用下述伪代码

1
2
3
4
5
6
7
8
9
10
11
Loop i from n down to 1:

​ If S' ≥ r_i:

​ x_i = 1

​ S' = S' - r_i

​ Else x_i = 0

End Loop

从而求出X=(x1,x2,...,xn)X = (x_1,x_2,...,x_n)

4.3 GGH

公共参数生成:

选择一个好基 V={v1,...,vn}V = \{v_1,...,v_n\}

一个整数矩阵 U 满足 det(U)=±1det(U) = \pm 1

计算 W = UV , 得到坏基 W={w1,...wn}W = \{w_1,...w_n\} (W的行向量)


加密:

公钥: W

私钥: (U,V)

选择小的明文向量 m

小的随机向量 r

计算 e=x1w1+...+xnwn+re = x_1*w_1 + ... + x_n*w_n + r

发送密文 e


解密:

Babai’s Algorithm 计算 CVP:

与 e 最近的向量 vLv \in L

计算 vw1vw^{-1} 还原 m


4.4. NTRU

公共参数生成:

(N,p,q,d)(N,p,q,d)

其中N和p是素数,q>(6d+1)p , gcd(p,q)=gcd(N,p)=1q>(6d+1)p\ ,\ gcd(p,q) = gcd(N,p) = 1


密钥生成:

×\times :模(xN1)(x^N - 1)

fT(d+1,d)f \in T(d+1,d) , 且 ffRpR_pRqR_q 均可逆

gT(d,d)g \in T(d,d)

Fqf1 mod RqF_q * f \equiv 1\ mod\ R_q

Fpf1 mod RpF_p * f \equiv 1\ mod\ R_p

公钥 hFq×g mod qh \equiv F_q \times g\ mod\ q

私钥 (f,g)(f,g)


加密:

明文 mRpm \in R_p

随机数 rT(d,d)r \in T(d,d)

epr×h+m mod qe \equiv pr \times h + m\ mod\ q


解密:

f×epg×r+f×m mod qf \times e \equiv pg \times r + f \times m\ mod\ q

center-lift:

a=pg×r+f×ma = pg \times r + f \times m

mFq×a mod pm \equiv F_q \times a\ mod\ p

5.Goldwasser-Micali probabilistic public key cryptosystem

怎么对一个比特进行加密?

明文空间太小怎么办?

to be continue……


参考

An Introduction to Mathematical Cryptography

【Crypto培训】公钥密码算法 - 入门to弃坑——Tover

文章作者: 莫折眉
文章链接: https://m0d1.top/2021/05/31/crypto-from-0-to-1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 M0D1.TOP