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

密码学需要的数学基础_密码学涉及到的数学密码学(一):基础数学知识与密码学的简单介绍这篇文章用来整理密码学知识,从数论和抽象代数的基础知识开始:数论部分: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/58780.html

(0)
上一篇 2024年 8月 30日 下午4:39
下一篇 2024年 8月 30日 下午4:43

相关推荐

关注微信