前言

数学基础

群、环、域

可以参考另一篇博客《信息安全数学基础》

群、环、域都是代数系统

密码学中使用的群大多为循环群：存在一个元素 g ∈ G，对于每一个元素 a ∈ G，都有一个相应的 i ∈ I，能把 a 表示成 gⁱ，则称 G 为循环群，g 称为循环群的生成元

环的条件：设代数系统R

1. <R,+>是 Abel 群
2. <R,·>是半群
3. 乘法在加法上可分配

域的条件：设代数系统F

1. <F,+>是 Abel 群
2. <R-{0},·>是 Abel群，其中 0 是 + 的单位元
3. 乘法在加法上可分配

有限域：域中元素个数有限的域，元素个数称为域的阶

Galois域：q = p^r，则阶为q的域称为Galois域

不可约多项式：与整数中的素数概念相似，指在 F 上仅能被非0常数或自身的常数倍除尽，但不能被其他多项式除尽的多项式

素数和互素数

因子：a = mb，即b整除a，则 b 是 a 的因子

整数性质：

1. a | 1，那么a = ±1
2. a | b且b | a，则a = ±b
3. 对任一 b(b≠0)，b|0
4. b|g，b|h，则对任意整数m、n有b|(mg + nh)

素数：整数p，因子只有 ±1 和 ±p

最大公因子：c = gcd(a,b)

最小公倍数：c = lcm(a,b)

模运算

mod

模指数运算

Fermat定理（费马小定理）

若p是素数，a是正整数且 gcd(a , p) = 1，则 a^p-1 ≡ 1 mod p

欧拉函数

欧拉定理

求本原根

参考：https://www.cnblogs.com/pam-sh/p/16491643.html

1. 求本原根的个数
2. 求最小本原根
3. 利用已知最小的本原根求其他本原根

欧几里得（Euclid）算法

求最大公因子

设a，b是任意两个正整数，记 gcd(a,b) 为 (a,b)

有(a,b) = (b,a mod b)

算法：

EUCLID(a, b){
    X=a;Y=b;
	while(True){
    	if(Y=0){
            return X=(a,b);
            break;
        }
    	if(Y=1){return Y=(a,b);}
    	R=X mod Y;
    	X=Y;
    	Y=R;
    }
}

求乘法逆元

如果 (a , b) = 1，则 b 在 mod a 下有乘法逆元

即存在一个x（x<a），使得 bx ≡ 1 mod a

推广的欧几里得算法先求出 (a,b) ，当 (a,b) =1 时，则返回 b 的逆元

代码见：https://c1oudfl0w0.github.io/blog/2023/10/22/%E4%B8%80%E7%A7%8D%E5%9F%BA%E4%BA%8E%E3%80%8A%E4%BF%A1%E6%81%AF%E5%AE%89%E5%85%A8%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%80%E3%80%8B%E7%9A%84%E5%AF%86%E7%A0%81%E5%AD%A6%E5%AD%A6%E4%B9%A0%E6%96%B9%E6%B3%95%EF%BC%88%EF%BC%9F/#%E5%B9%BF%E4%B9%89%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E9%99%A4%E6%B3%95

算法：（我自己瞎写的不像代码又不像伪代码的东西）

EXTENDED EUCLID(a, b){	// 设 b < a
    (X1,X2,X3)=(1,0,a);(Y1,Y2,Y3)=(0,1,b);
	while(True){
    	if (Y3=0) {return X3=(a,b);no inverse;}
    	if (Y3=1){
    	    return Y3=(a,b);
    	    Y2=inverse(b) mod f;
    	    break;
    	}
    	Q = X3/Y3;	// 向下取整
    	(T1,T2,T3)=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3);
    	(X1,X2,X3)=(Y1,Y2,Y3);
    	(Y1,Y2,Y3)=(T1,T2,T3);
    }
}

中国剩余定理

平方剩余

x² ≡ a(mod n)

RSA算法

密钥产生

1. 选两个保密的大素数 p 和 q
2. 计算 n = p * q，φ(n) = (p - 1)(q - 1)
3. 选一整数 e，满足 1 < e < φ(n)，且 gcd(φ(n) , e) = 1
4. 求逆元 d，d * e ≡ 1 mod φ(n)
5. 以{e, n}为公钥，{d, n}为私钥

加密

c ≡ m^e mod n

解密

m ≡ c^d mod n

安全性

分解大整数的困难性

椭圆曲线密码（ECC）

椭圆曲线

ElGamal密码体制

选择一个素数 p 以及两个小于 p 的随机数 g 和 x，计算 y ≡ g^x mod p

以 (y, g, p)作为公钥，x作为私钥

• 加密：

  C₁ ≡ g^k mod p

  C₂ ≡ y^kM mod p

  密文为C=(C₁, C₂)

• 解密：

  M = (C₂ / C₁^x) mod p