信息安全数学基础复习提纲

发布于 2020-01-04  1402 次阅读


信息安全数学复习

初等数论复习

  1. 整除

    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. 同余

    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的拆分

    抽象(近世)代数

    1. 定义: 给定一个集合,这个集合封闭,结合,有单位元,逆元 (Zn,+) (Z*n, ×)

    2. 指数运算

      n*g = g+g+g++g+g

      g^n = g g ... * g

    3. 子群

      (Z*7 mod(7)) {1,2,4} {1,6} {1,2,3,4,5,6,7}

      证明方法 ab^-1 ∈ H

    4. 正规子群、陪集、商群、群同态基本定理

      ​ 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)} 同构

    5. ​ 循环群

      第一个生成元、其他生成元、子群推生成元

      {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

环和域

  1. 环的定义:集合 交换加群,封闭,结合,满足分配律 ,整环

​ 零因子 {Z12,+,×} 3 != 0, 4!=0 但3*4=0

​ 除环: 有单位元、非零元、非零元能找到逆元(即交换加群、成群、分配律)

​ 整环:单位元、交换、无零因子 {Z,+,×}可以, 但是{2Z,+,×}不行,因为没有单位元

​ 域:交换除环, {Zp,+,×},p为素数的时候可以形成域

​ 有限整环

  1. 子环、理想、商环

    ​ {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

  1. 实数域上的椭圆曲线

    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

  2. 有限域

    以上所有的运算mod p

  3. ECC

    算法步骤


CTFer|NOIPer|CSGO|摸鱼|菜鸡