加密算法

此文为我在校学习物联网安全课程的笔记~

凯撒密码

凯撒密码是一种古代的加密方式，它是史上第一个广为使用的密码，得名于古罗马军事统帅凯撒。它的基本思想是对明文进行位移，即将明文中的每个字母都替换成字母表中靠它固定数量的字母。例如，若位移数为3，则a变成d，b变成e，…，y变成b，z变成c。

下面是一个例子，对明文“HELLO WORLD”进行加密：
位移数 = 3

明文 ：

H	E	L	L	O		W	O	R	L	D
8	5	12	12	15		23	15	18	12	4

密文 ：

K	H	O	O	R		Z	R	U	O	G
11	8	15	15	18		26	18	21	15	7

可以看到，每个字母都向后移动了三个位置，得到了对应的密文。

置换密码

平移置换加密法

置换加密法的一种简单实现形式是平移置换加密法，这很像洗一副纸牌。在平移置换加密法中，将密文分成了固定长度的块。通常，块越大越不容易破译。设块大小为s，置换函数f用于从1到s中选取一个整数，每个块中的字母根据f重新排列。这种加密法的密钥就是（s，f）对应的具体数值。例如，设s为4，f给定为（2，4，1，3）。这意味着第1个字符移到位置3，第2个字符移到位置1，第3个字符移到位置4，第4个字符移到位置2。

例如，利用这种置换加密法将明文“The only limit to our realization of tomorrow will be our doubts of today”加密。首先，设置密钥（d，f），如将d设为7，则明文将被分成块，每块包含7个字母，不足的用空字符填满。然后，根据给定的函数f=（4，2，3，5，7，6，1）将每个块重新排列，生成对应的密文，如下所示。

The only limit to our realization of tomorrow will be our doubts of today

ohenyltiimtotlrurelaotzainoioftmroowowillrueorodbsbtotfuydazzzo

列位移置换函数

列置换加密法是将明文按行填写在一个矩形中，而密文则是以预定的顺序按列读取生成的。例如，如果矩形是4列5行，那么短语“encryption algorithms”可以如图6所示写入矩形中。

1	2	3	4
e	n	c	r
y	p	t	i
o	n	a	l
g	o	r	i
t	h	m	s

按一定的顺序读取列以生成密文。对于这个示例，如果读取顺序是4、1、2、3，那么密文就是“riliseyogtnpnohctarm”。这种加密法要求填满矩形，因此，如果明文的字母不够，可以添加“x”或“q”甚至空字符。
这种加密法的密钥是列数和读取列的顺序。如果列数很多，则记起来可能会比较闲难，因此可以将它表示成一个关键词，以方便记忆。该关键词的长度等于列数，而其字母顺序决定读取列的顺序。

栅栏式置换函数

对角线方式

使用了对角线方式。在这种加密法中，明文是按Z字形的方式填写在矩形的对角线上，而按行读取生成密文。

例如，如果矩形的高为3，长为11，那么明文“this is a test”在该矩形中的填写如图4所示。而按行读取所生成的密文就是“tiehsstsiat”。

t				i				e
	h		s		s		t		s
		i				a				t

三角加密

例如，在一个固定大小的矩形中，可以将明文填写成一个三角形，然后按列读取生成密文。图5所示的是将明文“you must do that now”填写在一个7x4的矩形中。按行读取生成的密文是“tuhosayuttmdnoow”。

			y
		o	u	m
	u	s	t	d	o
t	h	a	t	n	o	w

RSA 加密算法

RSA是一种非对称加密算法。假设需要将明文"MONEY"进行加密，并使用RSA算法保护数据的安全性。以下是RSA加密和解密的详细运算过程。

1. 密钥生成过程：

选择两个大素数p=11和q=17，计算n=pq=187，根据欧拉函数的定义φ(n)=(p-1)(q-1)=160，选择一个小于φ(n)且与φ(n)互质的整数e=7，计算e的模逆数d，使得(e*d) mod φ(n)=1，有d=23。公钥为(n,e)=(187,7)，私钥为(n,d)=(187,23)。

2. 加密过程：

将明文"MONEY"转换成相应的ASCII码数值"77 79 78 69 89"，然后使用公钥(n, e)对每个数字进行加密运算，并将得到的密文表示成16进制数。

• 明文"M"，对应的ASCII码为77，加密后的密文为：

  C = 77^7 mod 187 = 38

  密文位数不足2位，需要在前面补0，因此该密文表示成16进制为0x26。

• 明文"O"，对应的ASCII码为79，加密后的密文为：

  C = 79^7 mod 187 = 178

  该密文表示成16进制为0xB2。

• 明文"N"，对应的ASCII码为78，加密后的密文为：

  C = 78^7 mod 187 = 89

  密文位数不足2位，需要在前面补0，因此该密文表示成16进制为0x59。

• 明文"E"，对应的ASCII码为69，加密后的密文为：

  C = 69^7 mod 187 = 19

  密文位数不足2位，需要在前面补0，因此该密文表示成16进制为0x13。

• 明文"Y"，对应的ASCII码为89，加密后的密文为：

  C = 89^7 mod 187 = 157

  该密文表示成16进制为0x9D。

因此，明文"MONEY"加密后的密文为"0x26 0xB2 0x59 0x13 0x9D"。

3. 解密过程：

使用私钥(n, d)对上一步得到的密文进行解密。

• 密文"0x26"，解密后得到原文为：

  M = 38^23 mod 187 = 77

  解密后的原文为"M"。

• 密文"0xB2"，解密后得到原文为：

  M = 178^23 mod 187 = 79

  解密后的原文为"O"。

• 密文"0x59"，解密后得到原文为：

  M = 89^23 mod 187 = 78

  解密后的原文为"N"。

• 密文"0x13"，解密后得到原文为：

  M = 19^23 mod 187 = 69

  解密后的原文为"E"。

• 密文"0x9D"，解密后得到原文为：

  M = 157^23 mod 187 = 89

  解密后的原文为"Y"。

因此，RSA算法加密后再解密，得到的原文是"MONEY"。

以上就是RSA加密和解密的详细运算过程。RSA算法是一种非常流行的公钥加密算法，其安全性取决于选取的参数。在实际应用中，需要采用足够长度的密钥和安全的参数，以保护数据的安全性。

证明题

$$证明题一： \varphi（n) = n - 1，n 为质数\\ 证明：\varphi（n) = n\prod_{i=1}^k (1 - \frac{1}{P_i}),P_i为n的质因数 \\ 当n为质数时，n的非1质因数为n \\ 那么\varphi（n) = n(1-\frac{1}{n}) = n-1$$

$$证明：当m,n互质时， 令P_1，···，P_k为m的所有非1质因数\\ q_1，···，q_r为n的所有非1质因数\\ 则P_i\neq q_j(i=1，···,k,j=1,···,r)\\ 且P_1，···P_k,q_1，···,q_r为mn的所有质因数\\ \begin{equation*} \begin{split} 则\varphi（mn) &=mn\prod_{i=1}^k(1-\frac{1}{P_i}）\prod_{j=1}^r(1-\frac{1}{q_j})\\ &=m\prod_{i=1}^k(1-\frac{1}{P_i})n\prod_{j=1}^r(1-\frac{1}{q_j})\\ &=\varphi（m)\varphi（n)\\ \end{split} \end{equation*}$$