信息安全数学复习
初等数论复习
-
整除
1.1 整除
1.2 带余除法
1.3 最大公因数（最小公倍数）
1.3.1 辗转相除法 gcd()
1.3.2 欧几里得算法 ax+by=gcd(a,b)
1.4 素数
1.4.1 算数基本定理 任何一个数都可以由若干个素数的乘积表示出来
1.4.2 大整数分解，是非常困难的
-
同余
2.1 等价关系 +，-，×， (÷ 只有转化为×逆元，用扩展欧几里得算法寻找逆元)
2.2 剩余类 (比如mod N )
2.2.1 完全剩余系 Zn |Zn|=n
2.2.1.1 x,(a,m) 构造 ax+b
2.2.1.2 m1->x m2->y, 构造 m1y+m2x (m1m2)
2.2.2 简化剩余系 Zn |Z n|= φ(n)
2.2.2.1 x,(a,m) 构造 ax
2.2.2.2 和 2.2.1.2类似
也就能够推出 φ(nm) = φ(n) φ(m)
以及 欧拉定理 a∈Zn, (a,N)＝1 a^φ(N) = 1
2.2.3 RSA算法（查看ppt）
了解rsa的加密和解密的步骤就ok了
2.2.3.1 密钥生成
p q n = p*q
φ(n) = Z = (p-1)(q-1)
(e,φ(n))=1 e*d=1(mod(φ(n)))
(n,e) 是私钥 (n,d)是公钥 ，利用扩展欧几里得算法算出
2.3 同余方程
一次同余方程 ax =b (mod m)
一次同余方程组
中国剩余定理 模数m的拆分
抽象（近世）代数
群
-
定义： 给定一个集合，这个集合封闭，结合，有单位元，逆元 (Zn,+) (Z*n, ×)
-
指数运算
n*g = g+g+g++g+g
g^n = g g ... * g
-
子群
(Z*7 mod(7)) {1,2,4} {1,6} {1,2,3,4,5,6,7}
证明方法 ab^-1 ∈ H
-
正规子群、陪集、商群、群同态基本定理
4.1 正规子群 可以交换
4.2 陪集 aH
1 {1,6} = {1,6} = 6 {1,6}
2 {1,6} = {2,5} = 5 {1,6}
3 {1,6} = {3,4} = 4 {1,6}
4.3 商群 所有陪集里面一个元素作为单位元，其他陪集之间都存在互为逆元的关系
4.4 群同态的基本定理
利用核和原群 可形成商群 G/N 与G‘ 同构 ，要学会举例并证明
f(x) = 3^x (mod 7) ，3是一个生成元，构成满射
x =0 f(x) = 1
x = 6,12, 18.... f(x) = 1
6Z 就是核
Z/6Z 形成的商群 ，与 {Z*7 , ×(mod 7)} 同构
-
循环群
第一个生成元、其他生成元、子群推生成元
{Zn , ×mod(n)} |Z n| = 10 = 2 *5
先找到第一个生成元（怎么找？） a a^n是生成元 (n,k) = 1 就可找出所有生成元 要会证明并且应用
2^0=1 2^1=2 2^3 = 8 2^4 = 5 2^5 =10 2^6 = 9 2^7 = 7 2^8 = 3 2^9 =6
2^k ，找与n(10) 互素的 k
找子群
10的因子有 1,2,5,10 ，那么就有四个子群，这四个子群的元素个数分别为1，2，5，10
(拉格朗日定理 |G| = |H| [G:H])
-
(g,h)->x g^x = h 离散对数问题，是困难的
6. el-gammel算法
p, Z*p ,g , x, h = g^x
c1 = g^k c2 = m 异或 h^k
c2 异或 c1^x
m 异或 h ^k 异或 g^kx
g^xk = g^kx
环和域
- 环的定义：集合 交换加群，封闭，结合，满足分配律 ，整环
零因子 {Z12,+,×} 3 != 0, 4!=0 但3*4=0
除环： 有单位元、非零元、非零元能找到逆元（即交换加群、成群、分配律）
整环：单位元、交换、无零因子 {Z,+,×}可以， 但是{2Z,+,×}不行，因为没有单位元
域：交换除环， {Zp,+,×}，p为素数的时候可以形成域
有限整环
-
子环、理想、商环
{Z12, +, ×}
子环 {0,3,6,9} ，它还是一个理想，因为其他所有的子环×它的元素都被他吸收到这个环中了
商环
多项式环与有限域
多项式的除法求余
辗转相除法求多项式的最大公因式
GF(2)[x] mod (x^2 + x + 1) 形成一个有限域，共包含 2^3 个数,{0,1,x,x+1,x^2+1, x^2+x+1, x^2 +x}
同样的，寻找子域
ECC
-
实数域上的椭圆曲线
y^2 = x^3 + ax + b
P(x1,y1) Q(x2,y2) P + Q (x3,y3)
λ = (y2-y1)/(x2-x1) P!=Q
(3 x1^2 + a) / (2 y1) P = Q
x3 = λ² - x1 - x2
y3 = λ(x1-x3) -y1
-
有限域
以上所有的运算mod p
-
ECC
算法步骤
Comments | NOTHING