密码学需要的数学基础_密码学涉及到的数学

密码学（一）：基础数学知识与密码学的简单介绍　　这篇文章用来整理密码学知识，从数论和抽象代数的基础知识开始：　　数论部分：　　1. 整除的定义：　　
$a=bc (a,b,c\in Z)$ , 那么
b |a 。　　2. 整除的几条基本性质：　　2.1：若
$b\ | \ a，a\ | \ c$ ，则
$b\ |\ c$ 　　2.2：若
$b\ | \ a，a\ | \ b$ ，则
$a=\pm b$ 　　2.3: 若
$b\ | \ a，b\ | \ c$ ，则
$b\ |\ (a+c)$ 　　3. 素数的定义：　　一个数
被称为素数，当且仅当它仅有
和
两个正约数。　　若
$p\ |\ a_{1}a_{2}$ ，那么
$p\ |\ a_{1}$ 或
$p\ |\ a_{2}$ 　　4. 最大公约数（General common divisor) 的定义：　　整数
与
的最大公约数是满足如下条件的最大正整数
：
$d\ | \ a$ 且
$d\ |\ b$ 。表示为
　　5. 辗转相除法（Euclidean algorithm）：　　
$a=bq+r_{1}, 0\leq r_{1}\leq b-1$ 　　
$b=r_{1}q_{1}+r_{2}, 0\leq r_{2}\leq r_{1}-1$ 　　
$r_{1}=r_{2}q_{2}+r_{3}, 0\leq r_{3}\leq r_{2}-1$ 　　
　　
$r_{n-1}=r_{n}q_{n}$ 　　则
$r_{n}=gcd(a,b)$ 　　6. 裴蜀定理（Bezout algorithm）又名广义欧氏算法（extended Euclidean algorithm）　　存在整数
u, v 使得
　　7. 模运算（modulo）的定义：　　若
$m\ |\ (b-a)$ ，则称
与
对
同余，或者
模
等于
，记作
$a\equiv b (mod \ m)$ 　　8. 模运算的几条基本性质：　　7.1：若
$a_{1}\equiv a_{2} (mod\ m), \ b_{1}\equiv b_{2} (mod\ m)$ ,则
$a_{1}+b_{1}\equiv a_{2} +b_{2}(mod\ m)$ ，
$a_{1}b_{1}\equiv a_{2} b_{2}(mod\ m)$ 　　7.2：当且仅当
时，存在
使得
$ab\equiv 1 (mod\ m)$ ，此时称
为
关于
的逆（Inverse）　　9. 完全剩余系：　　先定义一个符号
$Z/mZ=\{0,1,2...\ m-1\}$ 。称作模
的环　　
$(Z/mZ)^{*}=\{a\in Z/mZ:gcd(a,m)=1\}$ , 称作
的一个完全剩余系。　　
$(Z/mZ)^{*}$ 的素个数用欧拉函数
$\varphi(m)$ 表示。　　10. 算术基本定理（Fundamental Theorem of Arithmetic): 　　大于等于
的正整数
只有唯一一种素因数分解方式：　　
$a=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{n}^{a_{n}}$ 　　11. 费马小定理（Fermat Little Theorem）：　　若
，则
$a^{p-1}\equiv 1(mod\ p)$ 　　若
$p\ |\ a$ ，则
$a^{p-1}\equiv 0(mod\ p)$ 　　12. 欧拉定理（Euler Theorem）：　　
为整数，
$\varphi(m)$ 为欧拉函数。　　若
，则
$a^{\varphi(m)}\equiv 1(mod\ m)$ 　　13. 威尔逊定理（Wilson’s Theorem): 　　对素数
，
$(p-1)!\equiv-1 \ (mod\ p)$ 　　14. 阶(Order)的定义：　　当
是最小的满足如下条件的正整数时：
$a^{k}\equiv 1 (mod\ m)$ ，将
称作
模
的阶。　　15. 原根（Primitive Root）的定义：　　
是一个素数，
$g\in F_{p}$ ,若
$F_{p}=\{1,g,g^{2}...g^{p-2}\}$ ，称
是
的一个原根。　　换言之，当
模
的阶为
p-1 时，
为
的原根。　　16. 中国剩余定理（Chinese Remainder Theorem）: 　　若
$x\equiv a_{1}(mod\ m_{1}),x\equiv a_{2}(mod\ m_{2}),... x\equiv a_{n}(mod\ m_{n})$ 　　记
$M=\prod_{1}^{n}m_{i}$ ，
$M_{i}=\frac{M}{m_{i}},i\in \{1,2...n \}$ 　　则
$x\equiv \sum_{i=1}^{n}{M_{i}a_{i}}\ (mod\ M)$ 　　17. 二次剩余(Quadratic Residue) ：　　
是一个奇素数，
$p \nmid a$ 。若存在整数
使得
$x^{2}\equiv a(mod\ p)$ ，称
为
的一个二次剩余　　18. 勒让德符号（Legedre Symbol）：　　对于奇素数
与正整数
，勒让德符号
$(\frac{a}{p})$ 意为：　　

$\ (\frac{a}{p})=1,\ \ \ \ \ \ a是二次剩余 \\ \ (\frac{a}{p})=-1,\ \ \ a不是二次剩余 \\ \ (\frac{a}{p})=0, \ \ \ \ \ \ p\ |\ a$ 　　几个有关二次剩余的结论：若
$a\equiv b (mod \ p)$ ，则
$(\frac{a}{p})=(\frac{b}{p})$ 　　2.
$(\frac{a}{p})(\frac{b}{p})=(\frac{ab}{p})$ 　　3. 当
为奇素数时，
$\left(\frac{-1}{p} \right)=(-1)^{\frac{p-1}{2}}$ ，
$\left(\frac{2}{p} \right)=(-1)^{\frac{p^{2}-1}{8}}$ 　　19. 二次互反律：　　当
与
都是奇素数时，
$(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ 　　抽象代数部分：　　1.群（Group）公理：　　群由一个集合
与一个二运算规则
组成，对于
$a,b\in G$ ，有
$a*b\in G$ 。　　这个二运算
还需满足如下条件：　　1.1 单位(Identity Law)：
中存在单位
使得
　　1.2 逆（Inverse Law)：对任意
$a\in G$ 有
$a^{-1}\in G$ ，使得
$a*a^{-1}=a^{-1}*a=e$ 　　1.3 结合律（Associatative Law) ：
　　如果一个群满足如下的交换律，称其为交换群(Commutative Group) ，或阿贝尔群（Abelian Group) 　　交换律（Commutative Law) ：
a*b=b*a 　　2. 有限群与群阶数：　　包含有限个素的群为有限群　　定义
$g^{x}=g*g*...*g$ ，共计
个
。若
$g^{x}=e$ 。称
为
的阶数。　　3. 环（Ring）的定义：　　环由一个集合
，以及两种运算
与
组成。其中
与
构成一个交换群。
需满足如下条件：　　3.1 单位（Identity Law）：
　　3.2 结合律（Associative Law）：
　　3.3 分配律（Distributive Law）：
$a*(b+c)=a*b+a*c\ ,\ (b+c)*a=b*a+c*a$ 　　带有交换律
a*b=b*a 的环被称作交换环（Commutative Ring）　　易于验证所有整系数多项式构成一个交换环。　　4. 域（Field）和有限域　　我们先定义“除环”：若环中的任意非零在
运算下都有逆存在，那么这个环称作除环（Division Ring) 　　可交换的除环即为域。　　或者采取直接定义的方式：　　一个集合
中有两种运算
与
。它们都满足结合律，交换律，每个素都具有对应运算下的单位，每个素都有对应运算下的逆。同时满足
$a*(b+c)=a*b+a*c\ ,\ (b+c)*a=b*a+c*a$ 的分配律。那么
就称为一个域。　　具有有限个素的域即为有限域。　　密码学的简单介绍：　　1.古早时代的密码：　　最早在罗马时代，凯撒就用过这样一种密码，这就是大名鼎鼎的凯撒密码，举例：　　Alice想向Bob发送一条消息’I want bread’，但是她不想让别人（这里用Eva来代表）知道她具体发送了什么消息，那么她可以做如下操作：　　随便挑选一个数字，例如挑了数字3，把每个子母按照拉丁字母表的顺序向后移动3位，那么原信息就变成了‘L zdqw euhdg’接下来她把这串字符和数字3一并发给Bob。如果Alice之前与Bob约定好编码方式的话，那么Bob就可以把每个字母向前移动3位获得原始信息。而Eva只能对着密文干瞪眼。　　那么如果挑选的这个数字大于26该怎么办呢？注意到英文字母只有26个，那么对这个数字模26，得到的新数字就是字母移动的位数了。　　这个方法在文艺复兴时代得到了加强，形成了一种新的密码体系 ‘Vigenère cipher’：　　方法如下：　　原文依旧是’I want bread’，但是这时的密钥不再是3了，而是一个单词 ‘water’。那么该怎么用新密钥对原文加密呢？　　这里我们将字母与原文设定一个对应关系，例如a对应1，b对应2，… z对应26。那么I对应的字母是w，I就会向后移动23位，由于字母是循环的，那么I就会向前移动3位变成F，w对应的字母是a，w就会向后移动1位变成x。对于前五个字母 ‘Iwant’ 可以密钥water的五个字母全用一遍，到下一个字母b的时候，再重新从water的开头字母 ‘w’ 开始就可以了。　　我想过汉字是否也可以按照这个方法来玩，不过要覆盖常用汉字的范围，这个表的素数量起码在4000以上。　　2. 密码学的数学表示：　　我们假定Alice和Bob都知道用来加密密文的密钥
，这种类型的密文被称作对称密钥加密（Symmetric Ciphers）我们定义密钥集合为
，
$k\in K$ 。原文集合为
，密文集合为
。　　那么加密过程（Encryption）可以表示为：　　
$e:\ K\times M=C$ ，
$K\times M=\{ (k,m)|k\in K,m\in M\}$ 　　解密过程（Decryption}可以表示为：　　
$d:\ K\times C=M$ ，
$K\times C=\{ (k,c)|k\in K,c\in C\}$ 　　对于
与
中所有素，
成立。　　对于特定密钥
$k\in K$ ，有加密过程：
$e_{k}:M\rightarrow C$ ，解密过程：
$d_{k}:C\rightarrow M$ 。其中对于任意
$m \in M$ ，有
$d_{k}(e_{k}(m))=m$ 。　　这是为了保证解密结果是单一的，防止用一个密钥解出多种原文的情况出现。　　我们把这套密码体系记作
。其中Alice和Bob知道
K,e,d 。Alice将
加密为
后将
发送给Bob，Bob可以得到原文
。但对于Eva来说，假定她知道加密与解密过程
e,d 。但她不知道密钥
（这正是现实世界中的情况！）。那么如果她想攻破这个密码体系，她仅仅需要知道密钥就可以了。这也就是说密码体系的安全性仅仅依赖于密钥
。这个特性被称作 “Kerckhoff准则”。　　如果一个密码系统是成功的话，那么它必须满足以下三条准则：对任意
$k\in K, \ m\in M$ ，
$e_{k}(m)$ 容易计算。对任意
$k\in K, \ c\in C$ ，
$d_{k}(C)$ 容易计算。对于用
加密后的密文
$c_{1},c_{2},...c_{n}\in C$ ，在不知道密钥
的情况下，
$d_{k}(c_{1}),d_{k}(c_{2}),...d_{k}(c_{n})$ 是非常难计算的　　接下来是一个加强条件：　　即使知道了一些原文与密文的对应关系
$(m_{1},c_{1}),(m_{2},c_{2}),(m_{n},c_{n})$ ，对于任意
$c\ne c_{i} ，i\notin\{1,2,...,n\}$ ，
$d_{k}(c)$ 依旧非常难计算。　　这一条是为了防备选择明文攻击（Chosen Plaintext Attack）　　一些程序实践：　　我用的语言是Python3.10.7。代码可以在我的Github GitHub – Summer-worm/Cryptography: Some works I do when I study cryptography 中的Homework1与Homework2中找到编写一个返回值为两个整数a，b最大公约数的函数fastGCD(a,b)：对于裴蜀定理
,编写一个返回值为
的函数extendedGCD(a,b) 　　试将如下四个数组代入以上函数中求值：　　
　　
　　
　　
　　3. 编写一个返回值为a关于p的乘法逆的函数，即
$a^{-1}$ ，
$aa^{-1}\equiv1(mod \ p)$ 　　代入以下数组求值　　(a)
$7^{-1} (mod \ 53)$ 　　(b)
$1066^{-1} (mod \ 2027)$ 　　(c)
$72161726471264212144^{-1} (mod \ 217264871624871628472652659)$ 　　4. 编写一个返回值为
的
次方模
的值的函数fastPower(a,n,m)：　　（注意，这里最好把次数
用二进制表示，这个方法名为’Fast Power Algorithm’）

密码学需要的数学基础_密码学涉及到的数学

相关推荐