1. 激活谷首页
  2. 激活谷笔记

密码学和数学的关系_密码学涉及到的数学

• 激活谷笔记

密码学和数学的关系_密码学涉及到的数学密码学（一）：基础数学知识与密码学的简单介绍这篇文章用来整理密码学知识，从数论和抽象代数的基础知识开始：数论部分：1. 整除的定义：, 那么 。2. 整除的几条基本性质：2.1：若 ，则2.2：若 ，则2.3: 若 ，则3. 素数的定义：一个数 被称为素

密码学（一）：基础数学知识与密码学的简单介绍 　　这篇文章用来整理密码学知识，从数论和抽象代数的基础知识开始： 　　数论部分： 　　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 被称为素数，当且仅当它仅有
1 和
p 两个正约数。 　　若
p\ |\ a_{1}a_{2} ，那么
p\ |\ a_{1} 或
p\ |\ a_{2} 　　4. 最大公约数（General common divisor) 的定义： 　　整数
a 与
b 的最大公约数是满足如下条件的最大正整数
d ：
d\ | \ a 且
d\ |\ b 。表示为
d=gcd(a,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 使得
au+bv=gcd(a,b) 　　7. 模运算（modulo）的定义： 　　若
m\ |\ (b-a) ，则称
a 与
b 对
m 同余，或者
a 模
m 等于
b ，记作
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：当且仅当
gcd(a,m)=1 时，存在
b 使得
ab\equiv 1 (mod\ m) ，此时称
b 为
a 关于
m 的逆（Inverse） 　　9. 完全剩余系： 　　先定义一个符号
Z/mZ=\{0,1,2...\ m-1\} 。称作模
m 的环 　　
(Z/mZ)^{*}=\{a\in Z/mZ:gcd(a,m)=1\} , 称作
m 的一个完全剩余系。 　　
(Z/mZ)^{*} 的素个数用欧拉函数
\varphi(m) 表示。 　　10. 算术基本定理（Fundamental Theorem of Arithmetic): 　　大于等于
2 的正整数
a 只有唯一一种素因数分解方式： 　　
a=p_{1}^{a_{1}}p_{2}^{a_{2}}...p_{n}^{a_{n}} 　　11. 费马小定理（Fermat Little Theorem）： 　　若
gcd(a,p)=1，则
a^{p-1}\equiv 1(mod\ p) 　　若
p\ |\ a ，则
a^{p-1}\equiv 0(mod\ p) 　　12. 欧拉定理（Euler Theorem）： 　　
m 为整数，
\varphi(m) 为欧拉函数。 　　若
gcd(a,m)=1 ，则
a^{\varphi(m)}\equiv 1(mod\ m) 　　13. 威尔逊定理（Wilson’s Theorem): 　　对素数
p ，
(p-1)!\equiv-1 \ (mod\ p) 　　14. 阶(Order)的定义： 　　当
k 是最小的满足如下条件的正整数时：
a^{k}\equiv 1 (mod\ m) ，将
k 称作
a 模
m 的阶。 　　15. 原根（Primitive Root）的定义： 　　
p 是一个素数，
g\in F_{p} ,若
F_{p}=\{1,g,g^{2}...g^{p-2}\} ，称
g 是
p 的一个原根。 　　换言之，当
g 模
p 的阶为
p-1 时，
g 为
p 的原根。 　　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 是一个奇素数，
p \nmid a 。若存在整数
x 使得
x^{2}\equiv a(mod\ p) ，称
a 为
p 的一个二次剩余 　　18. 勒让德符号（Legedre Symbol）： 　　对于奇素数
p 与正整数
a ，勒让德符号
(\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. 当
p 为奇素数时，
\left(\frac{-1}{p} \right)=(-1)^{\frac{p-1}{2}} ，
\left(\frac{2}{p} \right)=(-1)^{\frac{p^{2}-1}{8}} 　　19. 二次互反律： 　　当
p 与
q 都是奇素数时，
(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}} 　　抽象代数部分： 　　1.群（Group）公理： 　　群由一个集合
G 与一个二运算规则
* 组成，对于
a,b\in G ，有
a*b\in G 。 　　这个二运算
* 还需满足如下条件： 　　1.1 单位(Identity Law)：
G 中存在单位
e 使得
a*e=e*a=a 　　1.2 逆（Inverse Law)：对任意
a\in G 有
a^{-1}\in G ，使得
a*a^{-1}=a^{-1}*a=e 　　1.3 结合律（Associatative Law) ：
a*(b*c)=(a*b)*c 　　如果一个群满足如下的交换律，称其为交换群(Commutative Group) ，或阿贝尔群（Abelian Group) 　　交换律（Commutative Law) ：
a*b=b*a 　　2. 有限群与群阶数： 　　包含有限个素的群为有限群 　　定义
g^{x}=g*g*...*g ，共计
x 个
g 。若
g^{x}=e 。称
x 为
g 的阶数。 　　3. 环（Ring）的定义： 　　环由一个集合
R ，以及两种运算
+ 与
* 组成。其中
R 与
+ 构成一个交换群。
* 需满足如下条件： 　　3.1 单位（Identity Law）：
a*1=1*a=a 　　3.2 结合律（Associative Law）：
a*(b*c)=(a*b)*c 　　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) 　　可交换的除环即为域。 　　或者采取直接定义的方式： 　　一个集合
G 中有两种运算
+ 与
* 。它们都满足结合律，交换律，每个素都具有对应运算下的单位，每个素都有对应运算下的逆。同时满足
a*(b+c)=a*b+a*c\ ,\ (b+c)*a=b*a+c*a 的分配律。那么
G 就称为一个域。 　　具有有限个素的域即为有限域。 　　密码学的简单介绍： 　　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都知道用来加密密文的密钥
k ，这种类型的密文被称作对称密钥加密（Symmetric Ciphers）我们定义密钥集合为
K ，
k\in K 。原文集合为
M ，密文集合为
C。 　　那么加密过程（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 与
M 中所有素，
d(k,e(k,m))=m 成立。 　　对于特定密钥
k\in K ，有加密过程：
e_{k}:M\rightarrow C ，解密过程：
d_{k}:C\rightarrow M 。其中对于任意
m \in M ，有
d_{k}(e_{k}(m))=m 。 　　这是为了保证解密结果是单一的，防止用一个密钥解出多种原文的情况出现。 　　我们把这套密码体系记作
(K,M,C,e,d) 。其中Alice和Bob知道
K,e,d 。Alice将
M 加密为
C 后将
C 发送给Bob，Bob可以得到原文
M 。但对于Eva来说，假定她知道加密与解密过程
e,d 。但她不知道密钥
K （这正是现实世界中的情况！）。那么如果她想攻破这个密码体系，她仅仅需要知道密钥就可以了。这也就是说密码体系的安全性仅仅依赖于密钥
K 。这个特性被称作 “Kerckhoff准则”。 　　如果一个密码系统是成功的话，那么它必须满足以下三条准则：对任意
k\in K, \ m\in M ，
e_{k}(m) 容易计算。对任意
k\in K, \ c\in C ，
d_{k}(C) 容易计算。对于用
k 加密后的密文
c_{1},c_{2},...c_{n}\in C ，在不知道密钥
k 的情况下，
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)：对于裴蜀定理
ax+by=gcd(a,b) ,编写一个返回值为
[gcd(a,b),x,y] 的函数extendedGCD(a,b) 　　试将如下四个数组代入以上函数中求值： 　　
(a.b)=(543, 705) 　　
(a.b)=(173676, 818645) 　　
(a.b)=(98748791589859238764602, 785168804371787933116521) 　　
(a.b)=(3107289384021020334845112174217281, 4356355227969236398381420990623887) 　　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. 编写一个返回值为
a 的
m 次方模
n 的值的函数fastPower(a,n,m)： 　　（注意，这里最好把次数
m 用二进制表示，这个方法名为’Fast Power Algorithm’）

2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/25933.html

赞 (0)
0
上一篇 2024年 9月 13日 下午6:21
下一篇 2024年 9月 13日 下午6:24

相关推荐

关注微信