【REPO】公钥密码算法-入门to弃坑

一篇关于5月30日Tover的密码学从入门到弃坑的repo

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

0.前置知识

0.1.加密与解密

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

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

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

密钥通常是(伪)随机数

明文和密钥是输入

将其投入到密码算法中

得到输出:密文

解密就是反过来


最近在0xffff.one的某个密码学帖子中看到了一个很有见地的想法,感觉可以增进读者对加解密的概念认识,特此截图:


以下截图来自0xffff.one 背包加密与称重问题


一些术语:

M: 明文

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

Enc:Encrypt,加密

Dec:同理,解密

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.2.密码学中的一些“反常识”

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


4.Lattices

格密码

不太会,鸽了

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