加密算法-工具盒子

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

凯撒密码 {#凯撒密码}

凯撒密码是一种古代的加密方式，它是史上第一个广为使用的密码，得名于古罗马军事统帅凯撒。它的基本思想是对明文进行位移，即将明文中的每个字母都替换成字母表中靠它固定数量的字母。例如，若位移数为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）将每个块重新排列，生成对应的密文，如下所示。

|-----------|---------------------------------------------------------------------------------------------| | 1 | hljs pgsql The only limit to our realization of tomorrow will be our doubts of today |

|-----------|----------------------------------------------------------------------------------| | 1 | hljs ebnf 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-加密算法}

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

密钥生成过程：

选择两个大素数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)。

加密过程：

将明文"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"。

解密过程：

使用私钥(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算法是一种非常流行的公钥加密算法，其安全性取决于选取的参数。在实际应用中，需要采用足够长度的密钥和安全的参数，以保护数据的安全性。

证明题 {#证明题}

证明题一： φ （ n ) = n − 1 ， n 为质数 证明： φ （ n ) = n ∏ i = 1 k ( 1 − 1 P i ) , P i 为 n 的质因数 当 n 为质数时， n 的非 1 质因数为 n 那么 φ （ n ) = n ( 1 − 1 n ) = n − 1 证明题一： \\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

证明题一：φ（n)=n−1，n为质数证明：φ（n)=ni=1∏k(1−Pi1),Pi为n的质因数当n为质数时，n的非1质因数为n那么φ（n)=n(1−n1)=n−1

证明：当 m , n 互质时，令 P 1 ， ⋅ ⋅ ⋅ ， P k 为 m 的所有非 1 质因数 q 1 ， ⋅ ⋅ ⋅ ， q r 为 n 的所有非 1 质因数 则 P i ≠ q j ( i = 1 ， ⋅ ⋅ ⋅ , k , j = 1 , ⋅ ⋅ ⋅ , r ) 且 P 1 ， ⋅ ⋅ ⋅ P k , q 1 ， ⋅ ⋅ ⋅ , q r 为 m n 的所有质因数 则 φ （ m n ) = m n ∏ i = 1 k ( 1 − 1 P i ） ∏ j = 1 r ( 1 − 1 q j ) = m ∏ i = 1 k ( 1 − 1 P i ) n ∏ j = 1 r ( 1 − 1 q j ) = φ （ m ) φ （ n ) 证明：当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\*}

证明：当m,n互质时，令P1，⋅⋅⋅，Pk为m的所有非1质因数q1，⋅⋅⋅，qr为n的所有非1质因数则Pi=qj(i=1，⋅⋅⋅,k,j=1,⋅⋅⋅,r)且P1，⋅⋅⋅Pk,q1，⋅⋅⋅,qr为mn的所有质因数则φ（mn)=mni=1∏k(1−Pi1）j=1∏r(1−qj1)=mi=1∏k(1−Pi1)nj=1∏r(1−qj1)=φ（m)φ（n)