密码学基础知识

发表于 更新于 分类于 Valine： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

密码学预备数学知识

数论知识和markdown数学符号

  • 欧拉函数
  • 欧拉定理
  • 模逆
  • 指数
  • 合数
  • 有限域等
  • 预备pyCrypto和gmpy2知识

$$
x^2+y_3\
Z^+\
\sqrt{x}\

\frac{a}{b} \times\frac{b}{c}\

\sqrt[n]{y}\

\vec{a}\cdot\vec{b}=0\

\overline{x}\

\lim_{n\to+\infty}n or \lim n\

\int_0^nf(x)dx or \int f(x)dx\

\sum_{i=1}^n a_i or \sum a_i\

\begin{bmatrix}
6&2&10&3\
7&5&4&9\
\end{bmatrix}\

\begin{matrix}
1&2&3\
4&5&6\
7&8&9\
\end{matrix}
\tag{2}\
$$

$$
a\cdot b\
c \times d\
f \div e\
a \approx 5\
a\pm5\
a\leq b\
a\geq d\
\forall\
\infty\
\emptyset\
\exists\
\nabla\
\bot\
\angle\
\because\
\therefore\
\alpha(n)\
\beta\
\chi\
\delta\
\eta\
\gamma\
\gamma =\quad \eta\
a \ mod \ b
$$

数学基础

整数和同余

  • 整除：设$a,b,m\in Z,\exists m$使得$a=mb$成立，则称非零整数$b$整除$a$，记作$b \mid a$，此时称$b$是$a$的因子，$a$是$b$的倍数。例：$2\mid6,3 \mid 6$等。

除数与被除数

需要熟知一个容易混淆的概念：被除数$\div$除数=余数……商，因此整除描述了除数整除被除数的情况，比如$6\div3=2……0$，描述了3整除6的情况，要注意除和除以是不同的概念

在上面，假设$m\mid a,m\mid b$说明$m$是$a$的因子，也是$b$的因子，因此称$m$是$a$和$b$的公因子。

  • 最大公因子，设$a,b,m\in Z，而且m\mid a,m\mid b,若m是整除a和b的最大整数，那么m称为a和b的最大公因子，记作m=gcd(a,b)$

互素

​ 利用最大公因子可以定义一个常用的概念，即互素：称整数$a,b$是互素的，当且仅当$gcd(a,b)=1$

求解最大公因子有非常有效的算法——欧几里得算法(辗转相除法)。在介绍欧几里得算法前，先介绍一下余数的概念

  • 带余除法：$\forall n \in Z^+$和$\forall a\in Z$，$\exists q,r\in Z$且$0\leq r<n$使得$a=qn+r$，其中$q=[a/n]$，[]为向下取整。

可以看到，其中q为商，r为余数，按照上面的公式有$r=a-[a/n]\times n$，在这里用一个更加简洁的符号表示$r$，那就是模运算符号$mod$，记作$r=a \ mod \ n$，这里$n$是模数，该运算称为模$n$运算

回到求解最大公因子，对于任意整数$a$和$b$可以通过下面的方式计算$gcd(a,b)$，不断使用带余数除法，直至余数为0，此时的除数为最大公因子

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

$$
gcd(a,b)=gcd(b,a\ mod\ b)
$$

以上的式子不停迭代直至余数为0

1
2
3
4
5
6
7
8
9
10
11
int gcd(int a,int b)
{
    int r=a%b;
    while(r>0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b; 
}
  • 模$n$同余：若$a \ mod\ n=b \ mod\ n$那么称整数$a$和$b$是同余的，记作$a \equiv b(mod\ n)$。

同余运算中，最重要的是模数$n$，比如6和11模5同余，而模三就不同余了。因此考虑一般情况，对于模$n$运算，考察所有整数$Z= \left{0,\pm1,\pm2,\pm3,\cdots \right},\forall\ a\in Z$，根据$a\ mod \ n \in \left{0,1,2,3,\cdots,n-1\right}$，因此对于任何整数只要进行模$n$运算后，所有整数都被限制到有限的集合中，那么必然会出现同余的情况，依据此可以定义下面两个概念：

  • 剩余类集：模$n$运算的所有余数的集合，记作$Z_n=\left{ 0,1,2,3,\cdots,n-1\right}$
  • 剩余类：所有模$n$同余的整数的集合，一般用最小的非负整数作为代表，记作$[0],[1],[2],\cdots,[n-1]$

例子

  • 模运算：称二元运算$a\ mod \ n=r$是模$n$运算，$r$是$a$模$n$的值，且$0\leq r <n$，可以证明对于任意两个整数$a$和$b$有下面的结论

消去律的成立与否与逆元的存在与否有很大关系，下面是加法逆元和乘法逆元的定义

  • 加法逆元：$a,b\in Z_n$，若$(a+b)\ mod\ n=0$，则$a$和$b$互为加法逆元，记$a$的加法逆元为$-a$
  • 乘法逆元：$a,b\in Z_n$，若$(a+b)\ mod\ n=1$，则$a$和$b$互为乘法逆元，记$a$的乘法逆元为$a^{-1}$

由于加法逆元一定存在，故加法消去律一定成立，而当且仅当$gcd(a,n)=1$时，$a$才在模$n$运算中存在逆元，故乘法消去律在该条件下才成立。

素数及其定理

  • 素数：正因子只有1和它本身的正整数称为素数，而且规定1不是素数，常记作$\rho$
  • 合数：合数是指正整数中不是素数的数

合数有一个非常重要的性质，称之为算术基本定理

  • 算术基本定理：任何合数都可以唯一分解为若干个素数的乘积，即对于任何整数$a>1$可以唯一分解为$a=\rho_1{a_1}\rho_2{a_2}\cdots \rho_n^{a_n},\forall i\in \left{1,2,\cdots n \right}$有$\rho_i$是素数($\rho_1<\rho_2<\cdots<\rho_n$)，$a_i$是正整数
  • 费马小定理：