信息与网络安全
以下链接是基于老师给的重点整理的笔记，同学们可以参考重点笔记
文章目录
第一章 概述
1.1 基本概念
信息安全是指信息网络中的硬件、软件及其系统中的数据受到保护，不受偶然的或者恶意的原因而遭到破坏、更改、泄露、否认等，系统连续可靠正常的运行，信息服务不中断。
信息安全威胁是指某些因素（人、物、事件、方法等）对信息系统的安全使用可能构成的危害。
1.2 攻击
概念
攻击：仅仅发生在入侵行为完全完成，且入侵者已进入目标网络内的行为称为攻击。但更为积极的观点是：所有可能使一个网络受到破坏的行为都称为攻击。即从一个入侵者开始在目标机上工作的那个时刻起，攻击就开始了。
分类
- 泄漏信息：指敏感数据在有意或无意中被泄漏出去或丢失。
- 破坏信息：以非法手段窃得对数据的使用权，删除、修改、插入或重发某些重要信息，以取得有益于攻击者的响应； 恶意添加，修改数据，以干扰用户的正常使用。
- 拒绝服务：它不断对网络服务系统进行干扰，影响正常用户的使用，甚至使合法用户被排斥而不能进入计算机网络系统或不能得到相应的服务。
常用手段
- 口令入侵
- 后门软件手段
- 监听法
- E-mail技术
- 电子欺骗
- DoS攻击（拒绝服务攻击）
1.3 信息安全的目的
信息安全核心三要素（也称CIA三要素）
信息安全典型技术
- 信息加密技术（基于密码学）
- 防火墙技术
- 漏洞扫描技术
- 入侵检测技术
- 防病毒技术
- 网络安全隧道技术（VPN）
第二章 信息加密技术
2.1 信息安全与密码学
密码学基本概念
密码学（Cryptology）是结合数学、计算机科学、电子与通信等学科于一体的交叉学科，研究信息系统安全的科学。起源于保密通信技术。具体来讲，研究信息系统安全保密和认证的一门科学。
密码学是信息安全的核心和关键技术
密码学发展历史
- 古典密码
- 近代密码
1976年提出公钥加密体制
- 现代密码
2.2 密码学经典例子
古典密码
置换密码：根据一定的规则重新排列明文，打破明文的结构特性。其特点是保持明文的所有字符不变，只是打乱了明文字符的位置和次序。
典型例子：
- Caesar（凯撒密码）
原理 ¶
凯撒密码（Caesar）加密时会将明文中的 每个字母 都按照其在字母表中的顺序向后（或向前）移动固定数目（循环移动）作为密文。例如，当偏移量是左移 3 的时候（解密时的密钥就是 3）：
- 明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
- 密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
- 明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
- 密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
- 已知密文为vzsx，位移量为3，求明文？
- 解：第一步，写出密文中字母对应的位置（下标），比如说a在字母表中为第一位，就记作1（记作0也可以,最后一个字母z = 25）
- 所以我们可以写出v = 22,z = 26,s = 19,x = 24
- 第二步，因为位移量为3，所以我们将以上数字都减3，即19,23,16,21
- 第三步，将以上数字还原为字母，19对应s,23对应w,16对应p,21对应u,我们就解出了明文swpu.
代换密码：代换，就是将明文中的一个字母由其它字母、数字或者符号替代的一种方法。
常见代换密码
- 单表代换（caesar，仿射密码（考试不要求））
- 多表代换（PlayFair,vigenere(维吉尼亚密码),Hill(希尔密码)）
典型例子：
原理 ¶
Playfair 密码（Playfair cipher or Playfair square）是一种替换密码，1854 年由英国人查尔斯 · 惠斯通（Charles Wheatstone）发明，基本算法如下：
- 选取一串英文字母，除去重复出现的字母，将剩下的字母逐个逐个加入 5 × 5 的矩阵内，剩下的空间由未加入的英文字母依 a-z 的顺序加入。注意，将 q 去除，或将 i 和 j 视作同一字。
- 将要加密的明文分成两个一组。若组内的字母相同，将 X（或 Q）加到该组的第一个字母后，重新分组。若剩下一个字，也加入 X 。
- 在每组中，找出两个字母在矩阵中的地方。
- 若两个字母不同行也不同列，在矩阵中找出另外两个字母（第一个字母对应行优先），使这四个字母成为一个长方形的四个角。
- 若两个字母同行，取这两个字母右方的字母（若字母在最右方则取最左方的字母）。
- 若两个字母同列，取这两个字母下方的字母（若字母在最下方则取最上方的字母）。
新找到的两个字母就是原本的两个字母加密的结果。
以 playfair example 为密匙，得
- P L A Y F
- I R E X M
- B C D G H
- K N O Q S
- T U V W Z
- HI DE TH EG OL DI NT HE TR EX ES TU MP
- BM OD ZB XD NA BE KU DM UI XM MO UV IF
- 先选一个密钥,比如说密钥是NSSCTF，然后我们把这个密钥填进一个5x5的表格里面，重复的字母不要。
NSCTF
- 剩下的格子怎么填呢？按字母表A-Z依次填，还是老规矩，重复的字母不要。还要满足一个要求：要么不要Q这个字母，要么把I/J写在一起，选一个就行。
NSCTFABDEGHI/JKLMOPQRUVWXYZ这样就填好了
- 比如说我们要加密的句子是：“Reach the highest City”，我们把它两两分组
- RE AC HT HE HI GH ES TC IT Y
- 我们来看第二组字母的相对位置
A和C既不在同一行也不在同一列对吧？这个时候我们就要找两个字母让他们连起来是一个长方形，这里显然是N,D两个字母，但是先后顺序是什么呢？因为这一组字母中A在前面，所以我们以A这一行优先，跟R同一行的是D，所以第一组密文为DN
- 再来看一组同行的例子HI
对于这种情况，我们就去找他后面的那个字母，H -> I/J ，I/J -K ,所以密文是 I/J K
- 再来看一组同列的例子RE
还是去找他后面的字母 R -> Y,E -> L，密文为YL
- 这就是PlayFair的加密过程
Playfair密码的优点（非重点）
Playfair密码与简单的单一字母替代法密码相比有了很大的进步
虽然仅有26个字母，但有26×26＝676种字母对，因此，识别字母对要比单个字母要困难得多。
一个明文字母有多种可能的代换密文字母，使得频率分析困难的多(hs成为BP,hq成为YP)
Playfair密码过去长期被认为是不可破的。
- vigenere（维吉尼亚密码）
原理 ¶
维吉尼亚密码（Vigenere）是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。
下面给出一个例子
- 明文：come greatwall
- 密钥：crypto
明文comegreatwall密钥cryptocryptoc其次，查表得密文
- 明文：come greatwall
- 密钥：crypto密文：efkt zferrltzn
和凯撒密码差不多，先把字母转化为下标的形式（a = 0,b = 1…）
比如说明文是NSSCTF,密钥是SWPU，怎么加密呢？
- 先将字母转为对应下标。(引用老师的一张图)
NSSCTF -> 13 18 18 2 19 5
SWPU -> 18 22 15 20
- 我们将密钥写在明文下面，填满为止
- 满足以下公式
加 密 ： c i = p i + k i ( m o d 26 ) 解 密 ： p i = c i − k i ( m o d 26 ) 加密：c_i = p_i + k_i (mod26)\\ 解密：p_i = c_i - k_i(mod 26) 加密：ci=pi+ki(mod26)解密：pi=ci−ki(mod26)
什么意思呢，我们刚刚不是将字母转成数字了吗，我们来运算一下，密文的第一个字母为(13 + 18) % 26 = 5 -> F
第二个字母为 （18 + 22） % 26 = 14 -> O
…
最终的密文为FOHWLB
- 怎么解密呢，我们用解密公式演算一下。
明文的第一个字母为（5 - 18）% 26 = 13 -> N,第二个字母为(14 - 22) % 26 = 18 -> S
…
最终明文为NSSCTF
- Hill（希尔密码）
原理 ¶
希尔密码（Hill）使用每个字母在字母表中的顺序作为其对应的数字，即 A=0，B=1，C=2 等，然后将明文转化为 n 维向量，跟一个 n × n 的矩阵相乘，再将得出的结果模 26。注意用作加密的矩阵（即密匙）在 Zn26
必须是可逆的，否则就不可能解码。只有矩阵的行列式和 26 互质，才是可逆的。下面举一个例子
将明文化为矩阵。
[ 0 2 19 ] \begin{bmatrix} 0\\ 2\\ 19\\ \end{bmatrix} ⎣⎡0219⎦⎤
假设密钥为：
[ 6 24 1 13 16 10 20 17 15 ] \begin{bmatrix} 6 & 24 & 1\\ 13 & 16&10\\ 20 & 17 & 15\\ \end{bmatrix} ⎣⎡6132024161711015⎦⎤
加密过程为：
[ 6 24 1 13 16 10 20 17 15 ] [ 0 2 19 ] = [ 67 222 319 ] ( m o d 26 ) = [ 15 14 7 ] \begin{bmatrix} 6 & 24 & 1\\ 13 & 16&10\\ 20 & 17 & 15\\ \end{bmatrix} \begin{bmatrix} 0\\ 2\\ 19\\ \end{bmatrix} = \begin{bmatrix} 67\\ 222\\ 319\\ \end{bmatrix} (mod 26) = \begin{bmatrix} 15\\ 14\\ 7\\ \end{bmatrix} ⎣⎡6132024161711015⎦⎤⎣⎡0219⎦⎤=⎣⎡67222319⎦⎤(mod26)=⎣⎡15147⎦⎤
密文即为
可能有些同学忘记线性代数怎么算了，我们这里来算一遍
- 我们用密钥矩阵的第一行乘明文矩阵，就是6*0 + 24*2 + 1*19 = 67
- 第二行乘明文矩阵：13*0 + 16*2 + 10*19 = 222
- 第三行乘明文矩阵：20*0 + 17*2 + 15*19 = 319
- 该矩阵是3 * 3 X 3 * 1 = 3 * 1
- 所以最后得到的矩阵是三行一列的矩阵，然后再对26取模得到的数字就是该字母的下标。
2.3 密码学基本概念
密码技术
- 密码技术的基本思想是伪装信息。
- 伪装就是对数据施加一种可逆的数学变换，伪装前的数据称为明文，伪装后的数据称为密文，伪装的过程称为加密，去掉伪装恢复明文的过程称为解密。加密和解密的过程要在密钥的控制下进行。
- 密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支：
密码学中一些术语的解释
一个密码（加密）系统是由明文、密文、加密算法、解密算法、密钥五部分组成。
- 明文M：作为加密输入的原始信息，即消息的原始形式
- 密文C：明文经加密变换后的结果，即消息被加密处理后的形式
- 密钥K：是参与密码变换的参数
- 加密算法E：是将明文变换为密文的变换函数，相应的变换过程称为加密，即编码的过程
- 解密算法D：是将密文恢复为明文的变换函数，相应的变换过程称为解密
数据安全基于密钥而不是算法的保密 （这句话是重点）
对于一个密码体制，其算法是可以公开的，让所有人来使用、研究。但具体对于某次加密过程中所使用的密钥，则是保密的。
按密钥的使用方式分类
- 非对称加密（公钥密码体制）
用于加密的密钥与用于解密的密钥是不同的，而且从加密的密钥无法推导出解密的密钥。
用公钥KP对明文加密可表示为：EKP(M)=C
用相应的私钥KS对密文解密可表示为：DKS©=M
- 对称加密
用于加密数据的密钥和用于解密数据的密钥相同，或者二者之间存在着某种明确的数学关系。
加密：EK(M)=C
解密：DK©=M
2.4 对称密码体制
概念
说白了就是加密的密钥和解密的密钥是一样的。
安全性
- 加密算法足够安全
- 密钥的安全性（如果密钥太简单，可以轻易被计算机爆破出来）
优缺点
优点：加解密速度快、保密度高
缺点：如何安全传递密钥（如果密钥在网络上被截获了就GG）、多人分发需要的密钥数量会急速增加
分类
- 序列密码
对明文的单个位（或字节）进行运算的算法，也称流密码
需要注意的是，流加密目前来说都是对称加密。
伪随机数生成算法生成的序列的随机性越强，明文中的统计特征被覆盖的更好。
流密码加解密非常简单，在已知明文的情况下，可以非常容易地获取密钥流。
流密码的关键在于设计好的伪随机数生成器。一般来说，伪随机数生成器的基本构造模块为反馈移位寄存器。当然，也有一些特殊设计的流密码，比如 RC4。
- 分组密码
把明文信息划分成不同的块（或小组）结构，分别对每个块（或小组）进行加密和解密
其实，我们也可以把块加密理解一种特殊的替代密码，但是其每次替代的是一大块。而正是由于一大块，明文空间巨大，而且对于不同的密钥，我们无法做一个表进行对应相应的密文，因此必须得有 复杂 的加解密算法来加解密明密文。
而与此同时，明文往往可能很长也可能很短，因此在块加密时往往需要两个辅助
- padding，即 padding 到指定分组长度
- 分组加密模式，即明文分组加密的方式。
所以分组密码有以下要求
- 分组长度足够大
- 密钥量空间足够大
- 加密变换足够复杂
- 加密和解密运算简单，一般采用加法、乘法、异或和移位等简单的运算
- 加密和解密的逻辑结构最好一致。
2.5 对称加密算法
DES、AES
太难了我不会。。
2.6 非对称（公钥）加密算法
基本原理
基于单向陷门函数
什么是单向陷门函数呢？拿RSA算法举例，给你两个质数，你要计算他们的乘积是很容易的吧，但是如果给你一个数让你计算他的两个质因数就是很困难的，可以自己写代码实现一下，这就是单向陷门函数，正向计算很容易，反过来就困难了，公钥密码的安全性正是基于这样的数学难题
具体的实现步骤在下文以RSA算法为例
应用场景
- 保护数据机密性
- 实现认证性/消息完整性（数字签名算法）
- 解决密钥分配问题
RSA
介绍
RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。
基本原理
公钥与私钥的产生 ¶
- 随机选择两个不同大质数 p和 q，计算 N=p×q
- 根据欧拉函数，求得 φ(N)=φ§φ(q)=(p−1)(q−1)
- 选择一个小于 φ(N)的整数 e，使 e 和 φ(N) 互质。并求得 e 关于 φ(N) 的模反元素，命名为 d，有 ed≡1(modφ(N))
- 将 p和 q的记录销毁,此时，(N,e)是公钥，(N,d) 是私钥。
消息加密
c = m^e mod N
m = c^d mod N
一些数学名词的解释
- 质数（素数）：就是它只能被1和它本身整除的数
- 欧拉函数φ(N)：就等于(p-1)*(q-1)
- 模运算
- 模运算与基本四则运算有些相似，但是除法除外。其规则如下：
- (a + b) % p = (a % p + b % p) % p
- (a - b) % p = (a % p - b % p) % p
- (a * b) % p = (a % p * b % p) % p
- a ^ b % p = ((a % p) ^ b) % p
- 结合律
- ((a + b) % p + c) = (a + (b + c) % p) % p
- ((a * b) % p * c) = (a * (b * c) % p) % p
- 交换律
- (a + b) % p = (b + a) % p
- (a * b) % p = (b * a) % p
- 分配律
- (a + b) % p = (a % p + b % p) % p
- ((a + b) % p * c) % p = ((a * c) % p + (b * c) % p
- 模逆元
逆元是指在数学领域群G中任意一个元 a，都在G中有唯一的逆元a’，具有性质 a · a’ = a’ · a = e ( · 为该群中定义的运算)。其中，e为该群的单位元。逆元其实是加法中的相反数以及乘法中的倒数的拓展思想。
在模运算中，单位元便是1。
a mod p的逆元便是可以使 a * a’ mod p = 1 的最小a’。
因为 b’ 为 b 的逆元，b * b’ mod p = 1；
所以 (a / b) mod p = (a * b’) mod p ，但要求a | b；
这样我们便可以应用 (a * b) % p = (a % p * b % p) % p 这一条性质缩小中间运算结果了。
以代码举例
我们用python来实现一遍加解密过程
- from Crypto.Util.number import *
- import gmpy2
- # 选取两个大素数p,q
- p = getPrime(128)
- q = getPrime(128)
- # 计算出N
- N = p * q
- # 计算欧拉函数phiN
- phiN = (p - 1) * (q - 1)
- # 选取一个质数e，要求e和phiN互质(phiN不能整除e)
- e = 17
- # 计算私钥d,这里实际是用到了扩展欧几里得算法求模逆元，后面讲
- d = gmpy2.invert(e, phiN)
- # 这是我们要加密的明文
- m = 'this is a test'
- # 我们先将明文转成字节类型，再转化成十进制数字
- m = bytes_to_long(m.encode())
- # 进行加密 c = m^e mod N
- c = pow(m, e, N)
- print(c)
- # 进行解密 m = c^d mod N
- m = pow(c, d, N)
- # 此时明文是十进制数字类型，转成字节类型
- m = long_to_bytes(m)
- print(m)
d怎么求？
我们前面已经知道d的求解是基于这个公式：ed≡1(modφ(N)),首先≡这个符号是什么意思？这是数论中的同余符号，意思是两个整数除以同一个整数，若得相同余数，则二整数同余，这个公式如果要转化为人能看懂的东西，怎么转化呢？对于数字较小的场景，可以用这个公式ed + phiNy = 1,其中y为负整数，d为正整数，可以从y = -1开始，来解d是否为正整数，以上次的作业为例
- 设通信双方使用RSA加密体制，接收方的公开钥是(n, e) = (35，5)，接收到的密文是C = 10，求明文M。
- n = 35 ,分解为两个素数相乘的结果为5*7，计算欧拉函数phiN = （5-1）*（4-1） = 24，此时用我们上面的公式解d
- 即ed+phiNy = 1 -> 5*d + 24*y = 1
- 取y = -1，z则方程变成5*d - 24 = 1 -> d = 5
- d刚好是正整数5，然后根据公式m = c^d mod N -> M = 10^5 mod 35 = 5
扩展欧几里得算法
以老师ppt上的例子为例
- e = 1234 ,phiN = 11111,求d=？
- 首先，如果这个d存在的话，我们用phiN除以e（保留余数） 即11111 / 1234 = 9 ...5 -> 11111 = 9*1234 + 5
- 再算1234 / 上一次的余数5 = 246 ...4 -> 1234 = 246*5 + 4
- 5 / 4 = 1...1 -> 5 = 4*1 + 1
- 算到除数为1就结束了，然后我们倒过来写这串表达式
- 1 = 5-1*4
- 4 = 1234-246*5
- 5 = 11111-9*1234
- 带进去就得到了1 = (5-1*(1234-246*5))
- 根据ed = 1 mod phin
- 即1234*d = (5-1*(1234-246*5)) mod phin
- 化简一下
1234 ∗ d = ( 5 − 1 ∗ ( 1234 − 246 ∗ 5 ) ) m o d p h i n = ( 5 − 1234 + 246 ∗ 5 ) m o d p h i n = ( 247 ∗ 5 − 1234 ) m o d p h i n = [ 247 ∗ ( 11111 − 9 ∗ 1234 ) − 1234 ] m o d p h i n = ( 11111 ∗ 247 − 9 ∗ 247 ∗ 1234 − 1234 ) m o d p h i n = ( 11111 ∗ 247 − 2224 ∗ 1234 ) m o d p h i n ∵ p h i n = 11111 , 11111 ∗ 247 m o d 11111 = 0 ∴ 1234 ∗ d = − 2224 ∗ 1234 m o d 11111 这 里 我 写 错 了 兄 弟 们 ！ ！ 最 后 一 步 是 对 − 2224 取 模 d = 2224 是 错 的 ！ ！ \begin{aligned} 1234*d &= (5-1*(1234-246*5))\ mod \ phin\\ &=(5-1234+246*5)\ mod \ phin\\ &=(247*5 - 1234) \ mod \ phin\\ &=[247*(11111-9*1234) - 1234] \ mod \ phin\\ &=(11111*247-9*247*1234-1234) \ mod \ phin\\ &=(11111*247 - 2224*1234) \ mod \ phin\\ &\because phin\ = 11111,11111*247 \ mod \ 11111 = 0\\ &\therefore \ 1234*d= -2224*1234 \ mod \ 11111\\ &这里我写错了兄弟们！！\\ &最后一步是对-2224取模\\ d &=2224是错的！！ \end{aligned} 1234∗dd=(5−1∗(1234−246∗5)) mod phin=(5−1234+246∗5) mod phin=(247∗5−1234) mod phin=[247∗(11111−9∗1234)−1234] mod phin=(11111∗247−9∗247∗1234−1234) mod phin=(11111∗247−2224∗1234) mod phin∵phin =11111,11111∗247 mod 11111=0∴ 1234∗d=−2224∗1234 mod 11111这里我写错了兄弟们！！最后一步是对−2224取模=2224是错的！！
负数取模
x m o d y = x − y ∗ [ x y ] ( 向 下 取 整 ) = − 2224 − 11111 ∗ ( − 2224 11111 ) = − 2224 + 11111 = 8887 ∴ d = 8887 \begin{aligned} x \ mod \ y &= x - y * [\frac{x}{y}](向下取整)\\ &= -2224 - 11111 * (\frac{-2224}{11111})\\ &= -2224 + 11111\\ &= 8887\\ \therefore d&=8887 \end{aligned} x mod y∴d=x−y∗[yx](向下取整)=−2224−11111∗(11111−2224)=−2224+11111=8887=8887
感谢同学指出的错误
如何计算m^emod n
使用快速幂取模算法，原理我没研究过，就不班门弄斧了，以老师ppt上的例子为例
- 采用快速取模指数算法求c1=m1^e(mod n) =104^13 mod 2537 的值？
第一轮代码
t = 0 ， c = 1 , i = 3 t = t ∗ 2 ( t = 0 ) c = c ∗ c m o d 2537 ( c = 1 ) i f b 3 = = 1 ( 满 足 ) : t = t + 1 ( t = 1 ) c = 1 ∗ 104 m o d 2537 ( c = 104 ) \begin{aligned} &t=0，c=1,i=3\\ &t = t*2\ (t=0)\\ &c = c*c \ mod \ 2537 \ (c=1)\\ &if \ b_3 == 1(满足):\\ &t = t+1 \ (t=1)\\ &c = 1*104\ mod\ 2537\ (c=104)\\ \end{aligned} t=0，c=1,i=3t=t∗2 (t=0)c=c∗c mod 2537 (c=1)if b3==1(满足):t=t+1 (t=1)c=1∗104 mod 2537 (c=104)
第二轮代码
t = 1 ， c = 104 , i = 2 t = t ∗ 2 ( t = 2 ) c = c ∗ c m o d 2537 ( c = 668 ) i f b 2 = = 1 ( 满 足 ) : t = t + 1 ( t = 3 ) c = 668 ∗ 104 m o d 2537 ( c = 973 ) \begin{aligned} &t=1，c=104,i=2\\ &t = t*2\ (t=2)\\ &c = c*c \ mod \ 2537 \ (c=668)\\ &if \ b_2 == 1(满足):\\ &t = t+1 \ (t=3)\\ &c = 668*104\ mod\ 2537\ (c=973)\\ \end{aligned} t=1，c=104,i=2t=t∗2 (t=2)c=c∗c mod 2537 (c=668)if b2==1(满足):t=t+1 (t=3)c=668∗104 mod 2537 (c=973)
第三轮代码
t = 3 ， c = 973 , i = 1 t = t ∗ 2 ( t = 6 ) c = c ∗ c m o d 2537 ( c = 428 ) i f b 1 = = 1 ( 不 满 足 ) : \begin{aligned} &t=3，c=973,i=1\\ &t = t*2\ (t=6)\\ &c = c*c \ mod \ 2537 \ (c=428)\\ &if \ b_1 == 1(不满足):\\ \end{aligned} t=3，c=973,i=1t=t∗2 (t=6)c=c∗c mod 2537 (c=428)if b1==1(不满足):
第四轮代码
t = 6 ， c = 428 , i = 1 t = t ∗ 2 ( t = 12 ) c = c ∗ c m o d 2537 ( c = 520 ) i f b 1 = = 1 ( 满 足 ) : t = t + 1 ( t = 13 ) c = 520 ∗ 104 m o d 2537 ( c = 803 ) \begin{aligned} &t=6，c=428,i=1\\ &t = t*2\ (t=12)\\ &c = c*c \ mod \ 2537 \ (c=520)\\ &if \ b_1 == 1(满足):\\ &t = t+1 \ (t=13)\\ &c = 520*104\ mod\ 2537\ (c=803)\\ \end{aligned} t=6，c=428,i=1t=t∗2 (t=12)c=c∗c mod 2537 (c=520)if b1==1(满足):t=t+1 (t=13)c=520∗104 mod 2537 (c=803)
此时代码运行完毕，c就是我们最终的结果803，我们用python验证一下
正确的。
RSA算法的安全性
RSA算法的安全性是基于大整数分解的难题，所以攻击方式也很简单粗暴，因为公钥是公开的，n = p*q,e已知，e * d = 1 mod phiN,所以我们只要能分解N为两个素数p,q,就能破解出d，以下介绍几种常见的攻击方式（考试应该不会考，感兴趣的同学可以看看）
<ol> 暴力分解
可以使用yafu这款工具，使用方式如下：
factor()函数，参数是你要分解的数，
分解结果
共模攻击
攻击条件 ¶
当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。
攻击原理 ¶
设两个用户的公钥分别为 e1 和 e2，且两者互质。明文消息为 m，密文分别为：
c1=m^e1modN
c2=m^e2modN
当攻击者截获 c1和 c2 后，就可以恢复出明文。用扩展欧几里得算法求出 re1+se2=1modn 的两个整数 r 和 s，由此可得：
cr1cs2≡mre1mse2modn
≡m(re1+se2)modn
≡mmodn
代码实现
- import gmpy2
- from Crypto.Util.number import *
- import sys
- import binascii
- sys.setrecursionlimit(1000000)
- def egcd(a, b):
- if a == 0:
- return b, 0, 1
- else:
- g, y, x = egcd(b % a, a)
- return g, x - (b // a) * y, y
- def modinv(a, m):
- g, x, y = egcd(a, m)
- if g != 1:
- raise Exception('modular inverse does not exist')
- else:
- return x % m
- e1=11085119
- e2=9190891
- c1=95802654515220808092268214474187396521084451096344242384608341887872702782290828816410697000941719590683107309925626046620976811737721800675450679405244429986569795481605454039209952126809031130572473139930816538229894404952230488471032140646478701800056893148667212842612771202600961005473843628543807576281789895225835535784697736508073945719275038557487868878529515390772120147529559169015697350455629223009240723598393858545457969371930544199690993535334876475403150437839542800975521617422860338848091674741969911523078015503201576312728495586541524742813914511874800249782937376857844116922101278519019905656
- c2=3416491037051012037012939467509239901806773704813403690354665798385393352563464881951974370241490158340518054254272653945115953885714558484209218930263157351532115665285897349811123032115674114898665575574766463243374363257317681664993192800007993550862200779683771913077545068424882032234253291268535634268961963331194864584762384909221320182259740507346013284854960761334127762166029934217852574313390086250095835456562558784241431962078316429891165585256316059135820341820577055463538905611710942258927193841136883208222189378113731075034150942645682604044709019188371375927920059650896388569726047796473642120516
- n=14129293489067735497835891913264472598235466604403612336006623107595438847067174121647397164285682966224208717924641463649550121959767200641904319708499428189547128930841593746541543006588640663582633284897803861765348725014771273881669308132805898675778540187033021154036594235144466199756659779020003038086388668345228666342476638806787610903886102447352152686433249208463728111915471444774767068270174477504938000592014963263451887545807532838102764510144961264142596092689778866428703620285541772740910077089202507682976490982442688834900108765694679294561760962915865812857912066376963510711262436193703892095683
- s = egcd(e1, e2)
- s1 = s[1]
- s2 = s[2]
- if s1 < 0:
- s1 = - s1
- c1 = modinv(c1, n)
- elif s2 < 0:
- s2 = - s2
- c2 = modinv(c2, n)
- m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
- print(long_to_bytes(m))
- m = gmpy2.iroot(m, 9)[0]
- print(long_to_bytes(m))
p和q相差过大或过小
就是暴力分解的那个例子，p和q十分接近
小明文攻击
如果明文过小的话，导致明文的e次方仍然小于n，这时模数n就没有任何作用了，我们直接对c开e次方就能得到明文m
代码实现
- from Crypto.Util.number import *
- import gmpy2
- while True:
- try:
- p = getPrime(128)
- q = getPrime(128)
- m = 'abc'
- e = 3
- n = p * q
- phin = (p - 1) * (q - 1)
- d = gmpy2.invert(e, phin)
- break
- except:
- pass
- m = bytes_to_long(m.encode())
- c = pow(m, e, n)
- # 破解
- m = gmpy2.iroot(c, e)[0]
- print(long_to_bytes(m))
低加密指数广播攻击
跟上面差不多，e取得太小导致m的e次方仍然小于n
Coppersmith partial information attack
已知p的高位或低位，使用Coppersmith破解出低位达到攻击目的
以下是一款数学工具sage的代码
[code]n=113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147p4=7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902#已知P的高位e=65537pbits=512 #P原本的位数kbits=pbits - p4.nbits()print (p4.nbits())p4 = p4 |
