建议直接看离散数学及其应用第7版原文
文章目录
信息安全的需求
在通信中必须考虑信息的安全性，因此密码学应运而生
密码系统
一个密码系统是5元组
G = ( P , C , K , ϵ , D ) G=(P,C,K,\epsilon,D) G=(P,C,K,ϵ,D)
其中，P表示明文集合，即原信息，C表示密文集，即加密后的信息，K表示密钥（key）集合，即所有可能的密钥，epsilon表示加密函数，D表示解密函数，所谓K密钥，指的是加密或解密函数需要的参数，是加密或解密的关键，按照密钥的类型，可以分为私钥系统和公钥系统
几个概念
字符密码表示对信息的加密是一一对应的，字符密码的缺点是容易被分析字符频率而被破解
分组密码表示对信息加密是以组为单位
私钥系统
私钥系统指的是加密密钥等同于解密密钥，因此为了信息的安全和传达，密钥必须由私人保存，即沟通者之间。
几种私钥系统
移位密码
例如凯撒密码
仿射密码
换位密码
想要提高私钥密码的安全性，需要提高私钥密码的设计标准（不理解），书中例举美国复杂的加密标准，但是私钥密码的性质决定了存在通信密钥的过程
公钥系统
为了解决通信密钥导致的安全问题，设计出了公钥系统，该系统中，加密密钥属于公钥，解密密钥属于私钥，原理是依靠目前计算机计算性能的限制，使解密计算变为不可能，最早的公钥系统是RSA密码系统，同时公钥系统的设计可以实现安全的密钥交换和数字签名
数论
由于RSA的设计涉及数论，需要先了解一些数论知识（群、环）
群公理
群是二元组集合V，二元运算·构成
G = ( V , ⋅ ) G=(V,·) G=(V,⋅)
群满足群公理
1.集合V上的计算是封闭的，即任意的运算结果仍在集合V中
2.计算满足结合律
3.对于每个群，存在一个单位元e，并且满足
∀ a ∈ V , a ⋅ e = e ⋅ a = a \forall a \in V, \ a·e=e·a=a ∀a∈V, a⋅e=e⋅a=a
4.对于V中的任意元素
∀ a ∈ V , ∃ b → a ⋅ b = e \forall a \in V, \ \exist b \rightarrow a·b=e ∀a∈V, ∃b→a⋅b=e
对于接下来讨论的整除和模运算都是整数集上一个群
整除和模运算
整除讨论的是没有余数的除法
KaTeX parse error: Undefined control sequence: \and at position 14: if\ a \neq0 \̲a̲n̲d̲ ̲b=ka,k\in Z \lo…
而模运算则是不关心商的除法
KaTeX parse error: Undefined control sequence: \and at position 18: …f \ a = pm+q \ \̲a̲n̲d̲ ̲q\neq0 \longrig…
在证明接下里讨论的整除和模运算的基本运算性质时，基本是将mod或|形式转化为等式的形式进行讨论
整除基本运算性质
KaTeX parse error: Undefined control sequence: \and at position 19: …)\ if\ a | b \ \̲a̲n̲d̲ ̲\ a | c \ \long…
模运算的一些基本性质
( a + b ) m o d = ( a m o d m ) + ( b m o d m ) a b m o d m = ( ( a m o d m ) ∗ ( b m o d m ) ) m o d m 观 察 以 上 两 式 猜 测 m o d 是 线 性 算 子 (a + b) \ mod = (a\ mod\ m) + (b\ mod\ m) \\ ab\ mod\ m = ((a\ mod\ m)*(b\ mod\ m))\ mod\ m \\ 观察以上两式猜测\ mod\ 是线性算子 \\ (a+b) mod=(a mod m)+(b mod m)ab mod m=((a mod m)∗(b mod m)) mod m观察以上两式猜测 mod 是线性算子
同余的一些基本性质
KaTeX parse error: Undefined control sequence: \and at position 77: …equiv b\ mod\ m\̲a̲n̲d̲ ̲b\equiv c\ mod\…
模运算的一些应用
指数模运算
b n m o d m = b a k − 1 a k − 2 . . . a 0 m o d m b^n\ mod\ m = b^{a_{k-1}a_{k-2}...a_0}\ mod\ m bn mod m=bak−1ak−2...a0 mod m
在实际计算中，根据模运算的性质，在b累乘时直接mod
素数
算数基本定理
一个大于1的正整数可以被因式分解为唯一非递减素数因式序列积
i f n > 1 ⟶ n = Π i = 1 n p i k ， k ∈ Z + ， 其 中 p i 是 素 数 并 且 以 非 递 减 序 列 排 列 if\ n > 1\ \longrightarrow\ n=\Pi_{i=1}^{n}p_i^k，k\in Z^+，其中p_i是素数并且以非递减序列排列 if n>1 ⟶ n=Πi=1npik，k∈Z+，其中pi是素数并且以非递减序列排列
推论
一个合数必定有一个素数因子小于等于√n
反 证 法 , 假 设 没 有 一 个 因 子 小 于 等 于 n ， 考 虑 使 每 个 因 数 最 大 的 情 况 ， 即 因 数 个 数 最 少 ， 即 2 。 因 此 n 1 ∗ n 2 > n ， 与 题 目 矛 盾 反证法,假设没有一个因子小于等于 \sqrt{n}，考虑使每个因数最大的情况，即因数个数最少，即2。\\因此\sqrt{n_1}*\sqrt{n_2}>n，与题目矛盾 反证法,假设没有一个因子小于等于n，考虑使每个因数最大的情况，即因数个数最少，即2。因此n1∗n2>n，与题目矛盾
选取两个因子中小的一个讨论，根据算数基本定理，该因子存在一个素因子，因此对于该合数，存在一个素因子小于等于√n，证毕
欧拉定理
KaTeX parse error: Undefined control sequence: \and at position 18: …f\ gcd(i,m)=1\ \̲a̲n̲d̲ ̲m \geqslant 2 \…
证明属于群论知识，目前看不懂
费马小定理
当i为质数时，欧拉定理变为费马小定理
原根和离散对数
原根
原根就是生成元
离散对数
最大公约数和最小公倍数
欧几里得算法
$$
对于a=pm+q\ 现在证明\ gcd(a,m)=gcd(m,q) \
证明策略，接下来试证明\
\forall s\in cd(a,m)\longrightarrow s\in cd(m,q) \
\forall t\in cd(m,q)\longrightarrow t\in cd(a,m) \
proof\ \ \ \ \ if \ s\in cd(a,m)\ \longrightarrow s|a\ \and s|m\ (1)\
\because a=pm+q\ \
\therefore s|(pm+q)\ i.e.k_1s=pm+q\
\because s | m\ \ i.e.k_2s =m\
\therefore (k_1-pk_2)s=q \
\therefore s|q\
同理证明第二条式子 \
因此gcd(a,m)\in cd(m,q) \and gdc(m,q)\in cd(a,m)，最大公约数相同
$$
贝祖定理
∀ g c d ( a , b ) = m ⟶ ∃ s , t ∈ Z → m = s a + t b \forall gcd(a,b)=m\longrightarrow \exists s,t\in Z\rightarrow m=sa+tb ∀gcd(a,b)=m⟶∃s,t∈Z→m=sa+tb
贝祖定理求逆元
i f g c d ( a , m ) = 1 ∃ s , t ∈ Z ⟶ s a + t m = 1 ∴ s a + t m ≡ 1 ( m o d m ) ∵ t m ≡ 0 ( m o d m ) ∴ s a ≡ 1 ( m o d m ) if\ gcd(a,m)=1 \\ \exist s,t\in Z\longrightarrow sa+tm=1 \\ \therefore sa+tm\equiv1\ (mod\ m) \\ \because tm\equiv0\ (mod\ m) \\ \therefore sa\equiv1\ (mod\ m) if gcd(a,m)=1∃s,t∈Z⟶sa+tm=1∴sa+tm≡1 (mod m)∵tm≡0 (mod m)∴sa≡1 (mod m)
即s是a关于模m的逆元（群，1是单位元）
扩展欧几里得算法
扩展欧几里得法就是将欧几里得算法的每层（除倒数第二层和倒数第一层）转为余数的表达式，带入下一层消去余数，最后得到只含gcd(a，b)和a、b的关系式
中国剩余定理
此定理用于解线性同余方程组，其中
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲ \left\{ …
求解逆元就需要用到上面贝祖定理的推论
中国剩余定理的一些应用
实现计算机大数存储和运算
理由是中国剩余定理的另一种表述是
对 于 n 元 组 ( a m o d m 1 , a m o d m 2 , . . . a m o d m n ) 可 以 唯 一 确 定 整 数 a ， 相 当 于 解 这 个 线 性 同 于 方 程 组 其 中 m = ∏ i = 1 n m i , 且 两 两 互 质 a ∈ { 1 , 2 , m − 1 } 对于n元组(a\ mod\ m_1,a\ mod\ m_2,...a\ mod\ m_n)可以唯一确定整数a，相当于解这个线性同于方程组\\ 其中m=\prod_{i=1}^nm_i, 且两两互质\\ a\in \{1,2,m-1\} 对于n元组(a mod m1,a mod m2,...a mod mn)可以唯一确定整数a，相当于解这个线性同于方程组其中m=i=1∏nmi,且两两互质a∈{
1,2,m−1}
RSA公钥系统
RSA公钥
G = ( P , C , K , ϵ , D ) G=(P,C,K,\epsilon,D) G=(P,C,K,ϵ,D)
对于RSA系统
集合P明文需要按分组密码进行转化
集合K中包含公钥K(N,e)、密钥K(N,d)，其中N=p*q（pq为互质素数），e和d互为模N系统中的逆元，其中e与(p-1)(q-1)互质
epsilon加密函数为
ϵ = p e m o d N \epsilon=p^emod\ N ϵ=pemod N
D解密函数为
D = C d m o d N D=C^dmod\ N D=Cdmod N
构造一个RSA密码的顺序是
1.寻找两个大素数，计算N，大素数是为了增加破译的难度
2.寻找一个e与(p-1)(q-1)互质，得到公钥K(N,e)，这里的(p-1)(q-1)是通过欧拉函数选取的，不太理解为什么选这个式子
3.计算e在模(p-1)(q-1)群中的逆元，得到密钥K(N,d)
假设我们为一个破译者，我们已经知道了RSA密码系统的构成，现在我们需要通过公钥K(N,e)找到那对大素数p和q，我们需要对N做因式分解，然后找到与e互质的(p-1)(q-1)组合，问题就出在这里，书中说这一步是十分费时的，现有的计算速度和算法不能很好的解决这个查找的过程，因此构造RSA时只要负责找更大的素数，破译者就束手无策（量子计算机能不能算出来呢）
安全密钥传递
构造方法
1.确定质数p和原根a
2.双方通过原根选择生成a^i和a^t，同时将a^i mod p 和a^t mod p传递给对方
3.新密钥a^it mod p
整个流程中，只有i和t是私有的，其他全是公开信息
若作为一个破解者，需要找出i和t，即问题转变成求离散对数i和t，目前无法在短时间计算出大数的p和a
数字签名
基于RSA公钥，数字签名就是将所谓的加密函数和解密函数的实际使用改变
数字签名的公开信息
因为每个的公钥匙是公开的，因此别人知道A的公钥，如果能使用A的公钥来解密，那么就表示签名的是A，即A用自己的解密函数加密
数字签名的私人信息
如果想点对点发送消息，那么必然要让唯一的目标对象的获得信息，因此最后解密的必然要用目标对象的公钥加密，这样只有对方用自己的私钥才能解密，然后在用A的公钥解密，这样就能代表A签名，当然调换顺序先用A的公钥解密也行