编码与加解密

概念和作用

概念

加密解密 是一种信息安全技术，用于保护数据免受未经授权的访问。加密是将原始数据（明文）转换为无法被轻易读懂的格式（密文）的过程。解密则是将密文还原为原始数据的过程。加密和解密确保只有拥有正确密钥的人可以访问和理解这些数据。

作用

加密解密技术在网络信息传输安全中起着至关重要的作用，主要涉及以下三个方面：

**保密性(Confidentiality)**：确保信息在传输过程中不被未授权的人员窥视或窃取。
**完整性(Integrity)**：确保信息在传输过程中未被修改或篡改。
**有效性(Availability)**：确保信息的接收者是合法且被授权的。

常用加密方式

数据加密方式	描述	主要解决的问题	常用算法
对称加密	使用同一个密钥进行数据的加密和解密。加密和解密速度快，适合大量数据的处理，但密钥的分发和管理是一个挑战。	数据的机密性	DES, AES
非对称加密	使用一对密钥，即公钥和私钥。公钥用于加密数据，私钥用于解密。公钥可以公开，而私钥必须保密。非对称加密通常用于密钥交换和数字签名，提供身份验证和数据机密性。	身份验证、数据机密性	DSA，RSA
单向加密	仅提供单向加密过程，不能被逆转。通常用于存储敏感信息，如密码哈希。	数据的完整性、验证数据未被篡改	MD5，SHA系列算法

对称加密 的例子包括 DES（数据加密标准）和 AES（高级加密标准）。AES是现代最常用的对称加密算法，广泛用于WiFi安全、VPN以及许多其他应用中。
非对称加密 的知名算法包括 RSA（由Rivest、Shamir和Adleman开发）和 DSA（数字签名算法）。RSA不仅用于加密，也用于数字签名，而DSA主要用于数字签名。
单向加密（哈希） 通常用于验证数据完整性。MD5（消息摘要算法第5版）虽然在许多应用中仍在使用，但由于安全性问题，现在更推荐使用SHA系列（安全哈希算法），如SHA-256。

字符编码

进制

在计算机中，所有信息最终都是以二进制形式存储的。字符编码就是字符（如字母、数字和符号）与二进制数之间的映射规则。不同的字符编码系统可以支持不同的字符集和语言。

常见的字符编码

ASCII（美国标准信息交换码）:
- 最初设计用于表示英文字符。
- 使用7位二进制数来表示一个字符（128个可能的字符）。
Unicode:
- 为了包含全球所有语言的字符，Unicode被设计出来。
- 最常用的形式是UTF-8，它是一种变长编码，可以用1到4个字节表示一个字符。
UTF-8:
- 在UTF-8编码中，ASCII字符只需一个字节，而其他字符可能需要多达四个字节。
- 由于其对ASCII的兼容性和对多字节字符的支持，UTF-8成为了互联网上最常用的编码方式。

二进制（Base-2）: 只使用0和1。每一位的值是2的幂。
十进制（Base-10）: 我们平常使用的数系统，使用0到9。每一位的值是10的幂。
十六进制（Base-16）: 使用0到9和A到F。十六进制广泛用于计算机系统中，因为它可以更简洁地表示二进制数。每一位的值是16的幂。

十进制	十六进制	二进制
0	0	0000 0000
1	1	0000 0001
2	2	0000 0010
3	3	0000 0011
4	4	0000 0100 = 2^2
5	5	0000 0101
6	6	0000 0110
7	7	0000 0111
8	8	0000 1000 = 2^3
9	9	0000 1001=2^3+2^0
10	A	0000 1010=2^3+2^1
11	B	0000 1011
12	C	0000 1100
13	D	0000 1101=2^3+2^2+2^0
14	E	0000 1110=2^3+2^2+2^1
15	F	0000 1111=2^3+2^2+2^1+2^0

进制间转换方法

Python中的进制转换

十进制与二进制

在Python中，可以使用 bin() 函数将十进制数转换为二进制字符串，int() 函数用于将二进制字符串转换回十进制数。

# 十进制转二进制
print(bin(255))  # 输出: '0b11111111'

# 二进制转十进制
print(int("0b11111111", 2))  # 输出: 255

十进制与十六进制

类似地，hex() 函数用于将十进制数转换为十六进制字符串，int() 函数也可以用于将十六进制字符串转换回十进制数。

# 十进制转十六进制
print(hex(255))  # 输出: '0xff'

# 十六进制转十进制
print(int("0xff", 16))  # 输出: 255

Unicode 与字符编码

Unicode是一个国际标准，它为世界上大多数的文字系统提供了唯一的码位。不同的编码方式（如UTF-8、UTF-16、UTF-32、GBK等）可以用来表示这些码位。

字符与Unicode码位：
- 使用 ord() 函数可以获取字符的Unicode码位。
- chr() 函数则可以将Unicode码位转换回对应的字符。
字符编码：
- 字符串的 encode() 方法用于将Unicode字符串编码为特定编码格式的字节串。
- 相对地，字节串的 decode() 方法用于将字节串解码为Unicode字符串。

# Unicode码位
print(ord("中"))  # 输出: 20013
print(chr(20013))  # 输出: '中'

# 编码为字节串
print("中".encode("utf-8"))  # 输出: b'\xe4\xb8\xad'
print("中".encode("gbk"))    # 输出: b'\xd6\xd0'

UTF-8编码：
- UTF-8是一种变长的编码方式，可以使用1到4个字节来表示一个Unicode字符。
- 对于ASCII字符（U+0000到U+007F），UTF-8与ASCII编码完全相同，使用单个字节表示。
GBK编码：
- GBK是用于简体中文的扩展编码集，是在GB2312基础上扩展而来。
- 在GBK编码中，汉字通常使用两个字节表示。

Base64编码原理

概念

Base64编码是一种编码方法，用于将二进制数据转换成ASCII字符串。Base64编码主要用于在不支持二进制数据的系统上存储和传输数据，例如在网页中嵌入图像数据或在电子邮件中发送二进制文件。Base64不是加密方法，它不提供任何安全性或数据保护。Base64是一种基于64个可打印字符来表示二进制数据的编码方法。这些字符包括26个大写字母、26个小写字母、10个数字，以及+和/，共计64个字符。

作用

处理非ASCII字符：最初设计用于电子邮件系统，后来被广泛用于处理包含非ASCII字符的情况，例如中文、日文等。
网络传输：在网络上传输数据时，特别是需要通过文本格式传输的二进制数据（如图片、加密数据等），Base64能将这些数据转换成由可打印字符组成的字符串。
数据表示：在一些应用中，如电子邮件附件、证书、网页内嵌资源等，Base64用于表示和传输数据。

Base64编码表

Base64编码表是将二进制数据按6位一组划分，每组对应一个可打印字符。

文本到base64格式的转换

转换过程通常包括以下步骤：

将文本转换为ASCII码：每个字符转换为其对应的ASCII值。
将ASCII码转换为二进制：每个ASCII值转换为8位二进制数。
划分6位一组：将二进制串划分为每组6位。
映射到Base64字符：每组二进制数映射到Base64编码表中对应的字符。

ASCII码转换

首先，文本字符转换为它们对应的ASCII码：

>>> ord("M")
77
>>> ord("a")
97
>>> ord("n")
110

ASCII转二进制

然后，ASCII码转换为8位的二进制表示：

>>> bin(77)
'0b1001101'  # 实际上应该是 01001101
>>> bin(97)
'0b1100001'  # 实际上应该是 01100001
>>> bin(110)
'0b1101110'  # 实际上应该是 01101110

请注意，为了确保每个ASCII码都是8位二进制，通常需要在前面补0。

组合二进制并划分

接着，将这些二进制串连起来，并每6位分为一组：

010011 010110 000101 101110

二进制转Base64编码

每组二进制数转换为Base64编码表中对应的字符：

>>> int("010011", 2)
19  # 对应Base64表中的 'T'
>>> int("010110", 2)
22  # 对应Base64表中的 'W'
>>> int("000101", 2)
5   # 对应Base64表中的 'F'
>>> int("101110", 2)
46  # 对应Base64表中的 'u'

因此，”Man” 这个字符串在Base64编码中表示为 "TWFu"。

Base64编码：Base64编码是一种二进制到文本的编码方法，用于在文本格式中表示二进制数据。每个6位二进制数映射到Base64编码表中的一个字符。
补码：在Base64编码中，如果最后一组不足6位，则用0补足6位，并在编码结果末尾添加一个或两个等号（=）作为填充。

BASE64编码补码

在Base64编码中，如果二进制数据的位数不是6的倍数，将使用补码=来填充，以保证编码后的字符串长度是4的倍数。

编码与加密的区别：Base64编码并不是加密过程。它不提供数据保护，只是一种编码方案，任何人都可以使用Base64算法将编码后的字符串解码回原始数据。
使用场景：虽然Base64主要用于在需要以文本格式传输二进制数据的场合，但它并不限于此。例如，Base64也常用于在Web应用中嵌入小的图像或其他类型的文件。

信息

凯撒密码（Caesar Cipher）是一种最简单和最广为人知的加密技术。它是一种替换密码，其中每个字母在明文中被移动了一定数目的位置。例如，当偏移量是3的时候，所有的字母都将向前移动三个位置，因此 ‘A’ 变成了 ‘D’，’B’ 变成了 ‘E’，以此类推。这种密码得名于朱利叶斯·凯撒（Julius Caesar），他用它来保护重要的军事信息。

工作原理

加密过程：在凯撒密码中，字母表中的每个字母都被向右或向左移动一定的固定数目。例如，如果我们选择向右移动3个位置，那么’A’就变成了’D’，’B’变成了’E’，依此类推。
解密过程：解密是加密过程的逆过程。如果我们知道了位移的数目，我们可以通过反方向移动同样数目的位置来还原原文。

示例

假设我们有一个明文 “HELLO”，我们使用向右位移3的凯撒密码加密：

‘H’ -> ‘K’
‘E’ -> ‘H’
‘L’ -> ‘O’
‘L’ -> ‘O’
‘O’ -> ‘R’

因此，加密后的密文是 “KHOOR”。

Python实现

以下是凯撒密码的一个简单Python实现：

def caesar_cipher(text, shift):
    result = ""

    for i in range(len(text)):
        char = text[i]

        # 加密大写字母
        if char.isupper():
            result += chr((ord(char) + shift - 65) % 26 + 65)

        # 加密小写字母
        elif char.islower():
            result += chr((ord(char) + shift - 97) % 26 + 97)

        else:
            result += char

    return result

# 测试加密
text = "HELLO"
shift = 3
print("Plain Text : " + text)
print("Shift pattern : " + str(shift))
print("Cipher: " + caesar_cipher(text, shift))

安全性

凯撒密码是一种非常基础的加密方法，由于其算法简单且容易破解（特别是在现代计算技术的帮助下），因此它不适合用于保护重要的信息。凯撒密码的主要用途在于教育和娱乐。在实际的安全应用中，需要使用更为复杂和安全的加密算法。

单向加密

概念

单向加密，也被称为哈希（Hashing），是一种加密过程，其中明文数据被转换成固定长度的唯一散列值，但这个过程是不可逆的。这意味着从散列值无法还原回原始数据。单向加密常用于存储密码、验证数据完整性和安全性。

常见方法

两种常见的单向加密算法是MD5（Message-Digest Algorithm）和SHA（Secure Hash Algorithm）。

MD5：
- MD5生成的散列值长度为128位（即16字节）。
- 通常以32个十六进制字符表示（因为每4位二进制可以表示为1位十六进制，所以128位二进制等于32位十六进制）。
SHA：
- SHA家族包括多种算法，如SHA-1、SHA-256、SHA-512等，其中SHA-256生成的散列值长度为256位。
- SHA-256的结果通常表示为64个十六进制字符。
更新哈希值：
- update() 方法用于向哈希对象添加数据。如果同一个哈希对象被多次调用 update()，则新增的数据会被附加到原有数据后面，最终的哈希值是所有数据的总和。

MD5加密

from hashlib import md5

md5_obj = md5()  # 创建MD5算法加密对象
md5_obj.update("加密数据".encode())  # 添加要加密的数据
print(md5_obj.hexdigest())  # 获取十六进制表示的散列值

SHA加密

from hashlib import sha256

sha256_obj = sha256()  # 创建SHA-256算法加密对象
sha256_obj.update("加密数据".encode())  # 添加要加密的数据
print(sha256_obj.hexdigest())  # 获取十六进制表示的散列值

安全性：
- MD5和SHA-1由于存在安全漏洞，不再推荐用于安全敏感的场合。
- SHA-256是更安全的选择，广泛用于加密货币、SSL证书等。
用途：
- 单向加密主要用于密码存储、数据完整性校验和数字签名等。
不可逆性：
- 哈希函数的一个关键特性是它们是单向的，无法逆转。这意味着无法从散列值推算出原始输入。

对称加密

概念与简介

概念: 对称加密是一种加密方法，其中加密和解密使用相同的密钥。

简介:

对称加密算法通常速度较快，适合加密大量数据。常用的对称加密算法包括 DES（Data Encryption Standard）、3DES（Triple DES）和 AES（Advanced Encryption Standard）。
- **DES (Data Encryption Standard)**：是最初的对称加密标准，使用56位密钥。尽管存在8位校验位，但实际上只用到了56位。DES由于密钥长度较短，容易受到暴力破解攻击。
- **3DES (Triple DES)**：是DES的改进版本，通过使用三重DES加密过程提高安全性。它使用两个或三个密钥，有效长度为112或168位。
- AES 是一种更现代的对称加密标准，提供多种密钥长度（128、192和256位）。被认为是DES的继任者，提供了更高的安全性和更好的性能。AES在现代加密应用中非常普遍。

特点：

相同密钥：加密和解密使用相同的密钥，因此密钥的保密性极为重要。
密钥长度：一般较短，通常小于256位。密钥越长，安全性越高，但性能可能受影响。
对称加密的应用：对称加密算法通常用于加密大量数据，如文件加密、数据库加密等。

DES

概念

DES是一种经典的对称加密算法，尽管由于其较短的密钥长度（56位有效长度），在现代计算能力下已不再安全。

DES加密原理

DES的加密过程包括初始置换、16轮迭代运算和逆初始置换。每轮迭代运算包括扩展置换、S盒置换和P盒置换，以及与子密钥的混合。初始置换（Initial Permutation, IP）和逆初始置换（Final Permutation, FP）是DES加密过程中的第一步和最后一步，它们是固定的非加密置换。

初始置换：打乱明文数据的顺序。
16轮迭代运算：每轮使用不同的密钥进行加密。
逆初始置换：恢复数据到最终加密状态。

初始IP置换表

58	50	12	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

逆置置换表

40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25

Python实现DES加密

使用Python进行DES加密需要安装pycryptodomex或pycryptodome库。

from Cryptodome.Cipher import DES

key = b'1234abcd'  # 8字节密钥
des = DES.new(key, DES.MODE_ECB)  # 创建DES加密对象，ECB模式
content = "加密内容"  
# 确保内容长度是8的倍数
padding = (8 - len(content) % 8) * "-"
en_data = content + padding
en_data = des.encrypt(en_data.encode())  # 加密
print(en_data)
de_data = des.decrypt(en_data)  # 解密
print(de_data.decode())

密钥管理：对称加密的一个挑战是密钥的安全传输和管理，因为密钥必须在通信双方之间共享。
加密模式：除了ECB（Electronic Codebook）模式，还有其他几种模式，如CBC（Cipher Block Chaining）和CFB（Cipher Feedback），每种模式有其特点和用途。
安全性考量：随着计算能力的提高，DES由于其较短的密钥长度而变得不够安全，AES由于其更长的密钥和更高效的算法成为更好的选择。

3DES

概念

3DES（或称为Triple DES）是三重数据加密算法（TDEA，Triple Data Encryption Algorithm）块密码的通称。它相当于是对每个数据块应用三次DES加密算法。

由于计算机运算能力的增强，原版DES密码的密钥长度变得容易被暴力破解。3DES即是设计用来提供一种相对简单的方法，即通过增加DES的密钥长度来避免类似的攻击，而不是设计一种全新的块密码算法。

3DES加密原理

3DES（即Triple DES）是DES向AES过渡的加密算法（1999年，NIST将3-DES指定为过渡的加密标准），加密算法，其具体实现如下：设Ek()和Dk()代表DES算法的加密和解密过程，K代表DES算法使用的密钥，M代表明文，

加密过程：C = Ek3(Dk2(Ek1(M)))
- 其中，Ek() 表示用密钥 k 进行DES加密，Dk() 表示用密钥 k 进行DES解密。
- M 代表明文，C 代表密文。
- k1、k2 和 k3 是三个不同的密钥。
解密过程：M = Dk1(Ek2(Dk3(C)))
- 解密过程是加密过程的逆过程。

Python实现3DES加密

实际上，3DES有几种不同的实现方式，包括使用三个不同密钥的3-key模式（最安全，但也最慢），以及使用两个不同密钥的2-key模式。

from Cryptodome.Cipher import DES3

key = b'12345678abcdefgh'  # 16字节密钥用于2-key模式，24字节密钥用于3-key模式
des = DES3.new(key, DES3.MODE_ECB)  # 创建3DES加密对象，ECB模式
content = "加密内容"  
# 确保内容长度是8的倍数
padding = (8 - len(content) % 8) * "-"
en_data = content + padding
en_data = des.encrypt(en_data.encode())  # 加密
print(en_data)
de_data = des.decrypt(en_data)  # 解密
print(de_data.decode())

性能：由于3DES使用了三次DES加密过程，它在相同硬件上比单次DES加密慢三倍左右。
安全性：虽然3DES比原始的DES更安全，但它的速度和效率不及更现代的算法，如AES。
用途：3DES通常用于需要与旧系统兼容的场景，但新的系统和应用更倾向于使用AES。

AES

概念

AES（Advanced Encryption Standard），又称Rijndael加密法，是一种区块加密标准，用于替代原来的DES。AES是美国国家标准技术研究所（NIST）于2001年采纳的加密标准，并被广泛使用。

加密过程

分组密码：AES将明文分为固定大小的数据块进行加密，每个数据块的大小为128位，即16个字节。
密钥长度：AES支持三种长度的密钥：128位、192位和256位。不同的密钥长度会影响加密的轮数。
加密轮数

：根据密钥长度的不同，AES有不同的加密轮数：
- AES-128：10轮
- AES-192：12轮
- AES-256：14轮
每轮加密操作：每一轮包括若干步骤，如字节代换、行移位、列混淆和轮密钥加。

AES	密钥长度（32位比特字)	分组长度(32位比特字)	加密轮数
AES-128	4	4	10
AES-192	6	4	12
AES-256	8	4	14

Python实现AES加密

在Python中使用AES加密时，可以选择不同的加密模式，如CBC（Cipher Block Chaining）模式。CBC模式需要一个初始化向量（IV）来提高安全性。

from Cryptodome.Cipher import AES

key = b'abcdefghijklnmop'  # 16字节密钥
iv = b'1234567890abcdef'   # 初始化向量

# 创建AES加密器实例
aes = AES.new(key, AES.MODE_CBC, iv)

content = "我爱你"
b_content = content.encode()
# 补足到16的倍数
bytes_content = content + (16 - len(b_content) % 16) * "*"
en_data = aes.encrypt(bytes_content.encode())
print(en_data)  # 加密后的数据

# 解密
aes_decrypt = AES.new(key, AES.MODE_CBC, iv)
de_data = aes_decrypt.decrypt(en_data)
print(de_data.decode().rstrip('*'))  # 解密后的数据，去除填充的'*'

非对称加密

概念与简介

非对称加密是一种加密方法，其中使用一对密钥：一个公钥和一个私钥。公钥用于加密数据，而私钥用于解密。这种方法的关键优势在于，公钥可以公开共享，而私钥则保持私密，从而确保了信息的安全传输。

主要特点

安全性：非对称加密提供了高度的安全性，因为即使公钥是公开的，没有相应的私钥也无法解密信息。
密钥传输：不需要安全地传输密钥，因为公钥可以公开。
效率：相较于对称加密，非对称加密过程速度较慢，尤其是在处理大量数据时。

使用场景

常用于加密少量重要数据，如加密会话密钥。
广泛应用于数字签名和身份验证。

RSA加密算法

数论基础

素数 (Prime Numbers)

素数，也称为质数，指的是一个大于1的自然数，它除了1和其自身外，不能被其他自然数整除。

模运算 (Modulo Operation)

模运算，即求余运算，在数学中通常用”mod”表示。它与”同余”的概念密切相关。如果两个整数除以同一个正整数得到相同的余数，那么这两个整数是同余的。

例如，若两个整数$a$和$b$，除以正整数$m$得到的余数相等，则$a \equiv b \ (\text{mod} \ m)$，即$a$同余于$b$模$m$。如：$26 \equiv 14 \ (\text{mod} \ 12)$。

互质关系（Coprime）

互质关系是指两个正整数$a$和$b$之间的关系，它们除了1以外没有其他共同的正因子。互质关系表示为$\text{gcd}(a, b) = 1$，其中$\text{gcd}(a, b)$表示$a$和$b$的最大公因子。

性质和应用：

任意两个质数互质。
如果一个数是质数，另一个数不是它的倍数，它们互质。
如果两数中较大的那个是质数，则它们互质。
1和任意自然数互质。
对于大于1的整数$p$，$p$和$p-1$互质。
对于大于1的奇数$p$，$p$和$p-2$互质。

欧拉函数 (Euler’s Totient Function)

欧拉函数，记作$\phi(n)$，是一个数论中的重要函数。它的定义是：对于任意正整数$n$，欧拉函数$\phi(n)$表示在$1$到$n$之间与$n$互质的正整数的数量。

定义

对于正整数$n$，欧拉函数$\phi(n)$被定义为：

$$ \phi(n) = \text{数量}{k \in \mathbb{N} : 1 \leq k \leq n, \text{gcd}(k, n) = 1} $$

这里，$\text{gcd}(k, n)$表示$k$和$n$的最大公因数。

性质

对于质数$p$:

因为一个质数除了自身和 $1$ 以外，没有其他因子。因此，除了自身之外，所有小于 $p$ 的正整数都与 $p$ 互质。

$$ \phi(p) = p - 1 $$

推导

对于质数 $p$，它没有除 $1$ 和自身以外的因子。

因此，$1, 2, …, p-1$ 都是与 $p$ 互质的。

这意味着与 $p$ 互质的正整数的数量是 $p-1$。
两个不同质数的乘积:

当 $n$ 是两个不同质数 $p$ 和 $q$ 的乘积时，欧拉函数的计算变得稍微复杂一点

$$ \phi(pq) = (p - 1)(q - 1) $$

推导

首先，由于 $p$ 和 $q$ 是质数，所以除了 $1$ 和它们自身外，它们没有其他因子。

任何小于 $pq$ 且不是 $p$ 或 $q$ 的倍数的数都与 $pq$ 互质。

在 $1$ 到 $pq$ 的数中，有 $q$ 个数是 $p$ 的倍数，有 $p$ 个数是 $q$ 的倍数，但 $pq$ 被算了两次。

因此，与 $pq$ 互质的数的数量是 $pq - p - q + 1$。 - 这可以重写为 $(p - 1)(q - 1)$。
对于质数$p$的幂$p^n$:

当 $n$ 是质数 $p$ 的幂，即 $n = p^k$（其中 $k > 1$）时，欧拉函数的计算方式如下：

$$ \phi(p^k) = p^k - p^{k-1} $$

推导

在 $1$ 到 $p^k$ 的数中，与 $p^k$ 不互质的数是 $p$ 的倍数。

这些数是 $p, 2p, 3p, \ldots, p^{k-1}p$，总共有 $p^{k-1}$ 个。

因此，与 $p^k$ 互质的数的数量是 $p^k - p^{k-1}$。

示例

计算 $\phi(10)$:
- 由于 $10 = 2 \times 5$，且 $2$ 和 $5$ 是质数，$\phi(10) = (2-1)(5-1) = 4$。
- 与 $10$ 互质的数有 $1, 3, 7, 9$。

应用

欧拉函数在密码学和数论中有着重要的应用，例如在RSA加密算法中，它被用来选择密钥。

模反元素/模逆元（Modular Multiplicative Inverse）

模反元素是数论和代数中的一个重要概念。当两个正整数$a$和$n$互质时（即它们的最大公因数为$1$），$a$在模$n$下的模反元素是指一个整数$b$，使得$a$乘以$b$在模$n$下的结果等于$1$。

定义

对于给定的正整数$a$和$n$，如果存在整数$b$满足以下等式，则$b$是$a$的模反元素：

$$ ab \equiv 1 \pmod{n} $$
这里的$\equiv$表示同余，而$\pmod{n}$表示对$n$取模。

计算方法

要找到$a$在模$n$下的模反元素$b$，可以使用扩展欧几里得算法或费马小定理（如果$n$是质数）。

示例

假设$a = 3$和$n = 11$，那么$3$和$11$互质。
要找到一个数$b$，使得$3b \equiv 1 \pmod{11}$。
在这个例子中，$b = 4$是$3$的模反元素，因为$3 \cdot 4 = 12$，且$12 \equiv 1 \pmod{11}$。

应用

模反元素在密码学中非常重要，尤其是在公钥加密和数字签名算法中。
它也用于计算机科学中的某些算法，如模算术和散列函数。

概念

RSA是一种广泛使用的非对称加密算法，由Rivest、Shamir和Adleman三位数学家提出。RSA的安全性基于大数分解的难题。在RSA中，加密密钥（公钥）是公开的，而解密密钥（私钥）则必须保密。由于RSA计算量大，通常用于加密小量数据或加密对称加密的密钥。常见的做法是使用RSA加密对称密钥，然后用该对称密钥进行实际数据的加密和解密，这样结合了两者的优点：RSA的安全性和对称加密的效率。

RSA加密原理

RSA加密的基本步骤可以分为三个阶段：密钥生成、加密和解密。

密钥生成过程

选择两个大的质数 $p$ 和 $q$。这些质数需要足够大，以确保加密的安全性。
计算它们的乘积 $n = p \times q$。这个乘积 $n$ 用于公钥和私钥，且其长度决定了密钥长度。
计算欧拉函数 $\phi(n) = (p-1)(q-1)$。这是公钥和私钥生成的关键部分。
选择一个公钥指数 $e$。$e$ 是一个小于 $\phi(n)$ 的正整数，并且 $e$ 和 $\phi(n)$ 互质。常见的选择是 $e = 65537$，但确保 $e < \phi(n)$。
计算私钥 $d$。$d$ 是 $e$ 相对于 $\phi(n)$ 的模逆元，即找到一个整数 $d$ 使得 $ed \equiv 1 \mod \phi(n)$。这可以通过扩展欧几里得算法来实现。

信息

扩展欧几里得算法及其在RSA加密中的应用

扩展欧几里得算法是一种用于求解两个整数 a 和 b 的最大公因数（GCD）的同时，找到整数 x 和 y 使得 ax + by = gcd(a, b) 的算法。

算法描述

基本思想:
- 扩展欧几里得算法基于欧几里得算法的原理，通过反复应用除法原理，直到余数为0。
- 在每一步中，算法维护着等式 ax + by = gcd(a, b) 的一个解。
算法步骤:
- 如果 b = 0，则 gcd(a, b) = a，且 x = 1, y = 0。
- 否则，递归调用扩展欧几里得算法：gcd(b, a % b)。
- 通过回溯的方式，计算出 x 和 y 的值。

在RSA加密中的应用

在RSA加密中，扩展欧几里得算法用于计算私钥 d，这是公钥指数 e 的模逆元相对于 φ(n)。

公钥和私钥的生成:
- 已知公钥指数 e 和 φ(n)（其中 n = pq 是两个质数 p 和 q 的乘积）。
- 需要找到一个整数 d 使得 ed ≡ 1 (mod φ(n))。
- 这意味着需要找到 x 和 y 使得 ex + φ(n)y = 1。
使用扩展欧几里得算法:
- 应用扩展欧几里得算法于 e 和 φ(n)。
- 算法将产生 x 和 y，其中 x 就是所求的 d。
- 即使 x 是负数，也可以通过加上 φ(n) 来得到正的模逆元。

示例

假设 e = 17 和 φ(n) = 3120，使用扩展欧几里得算法找到 d，使得 17d ≡ 1 (mod 3120)。算法将返回 d 的值，这是私钥的一部分。

这种方法确保了RSA加密算法中私钥的生成既安全又有效率。

加密过程

加密过程是将明文消息 $M$ 转换成密文 $C$。这通过以下公式完成：

$$ C = M^e \mod n $$

使用公钥 $(n, e)$ 对明文 $M$ 进行加密。

解密过程

解密过程是将密文 $C$ 还原回原始明文 $M$。这通过以下公式完成：

$$ M = C^d \mod n $$

使用私钥 $(n, d)$，可以将密文 $C$ 解密回明文 $M$。

信息

在RSA加密算法中，公钥指数 e 的选择对于加密的效率和安全性都至关重要。e = 65537 是一个广泛使用的值，其原因如下：

安全性: e 应该是一个与 $\phi(n)$ 互质的大质数。65537 是一个质数，且大多数情况下不会与 $\phi(n)$ 有共同因子。
效率: 65537 在二进制表示中只有两个 1（即 10000000000000001）。这使得进行模幂运算（用于加密和解密）时更加高效。较少的 1 位意味着需要更少的乘法操作。
历史原因: 在RSA的早期，较小的值如 3 和 17 也被作为公钥指数使用。然而，随着对RSA安全性的更深入理解，这些较小的值被认为在某些情况下不够安全。65537 提供了良好的安全性，同时保持了计算效率。
平衡性: 65537 是一个在保持计算效率和确保足够安全性之间的良好平衡。它足够大，可以避免某些已知的攻击方法，同时又不会像更大的数那样使计算量过大。
总结来说，e = 65537 是RSA加密中的一个标准选择，因为它在安全性和计算效率之间提供了一个很好的平衡点。

RSA加密算法的安全性

RSA加密算法的安全性主要基于大数分解的难度。当选择的两个大素数p和q足够大时，它们的乘积n = p * q难以分解，这是RSA算法的核心安全基础。

大素数分解难题：目前，没有已知的高效算法可以在合理时间内分解非常大的数。这个数学难题是RSA安全性的基石。

RSA加密算法的缺点

尽管RSA加密算法被广泛使用，但它确实有一些缺点：

密钥生成困难：生成大素数需要特定的算法和足够的计算资源。在某些环境下，这可能是一个限制。
计算效率低：由于涉及大数运算，RSA加密和解密过程相对较慢，尤其是当使用较长的密钥时。
理论安全性未证明：尽管大数分解被认为是困难的，但尚无理论证明表明破解RSA加密的难度与大数分解的难度等价。

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

# 生成密钥对
key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

# 明文
message = "Hello RSA!"

# 使用公钥加密
public_key = RSA.import_key(public_key)
cipher = PKCS1_OAEP.new(public_key)
encrypted_message = cipher.encrypt(message.encode())

# 使用私钥解密
private_key = RSA.import_key(private_key)
cipher = PKCS1_OAEP.new(private_key)
decrypted_message = cipher.decrypt(encrypted_message)

print("Original Message:", message)
print("Encrypted Message:", binascii.hexlify(encrypted_message))
print("Decrypted Message:", decrypted_message.decode())

58	50	12	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25

58	50	12	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25

角灯随笔

编码与加解密

概念和作用

概念

作用

常用加密方式

字符编码

进制

常见的字符编码

进制间转换方法

Python中的进制转换

Unicode 与字符编码

Base64编码原理

概念

作用

Base64编码表

文本到base64格式的转换

ASCII码转换

ASCII转二进制

组合二进制并划分

二进制转Base64编码

BASE64编码补码

单向加密

概念

常见方法

MD5加密

SHA加密

对称加密

概念与简介

DES

概念

DES加密原理

Python实现DES加密

3DES

概念

3DES加密原理

Python实现3DES加密

AES

概念

加密过程

Python实现AES加密

非对称加密

概念与简介

主要特点

使用场景

RSA加密算法

数论基础

素数 (Prime Numbers)

模运算 (Modulo Operation)

互质关系（Coprime）

欧拉函数 (Euler’s Totient Function)

模反元素/模逆元（Modular Multiplicative Inverse）

概念

RSA加密原理

密钥生成过程

加密过程

解密过程

RSA加密算法的安全性

RSA加密算法的缺点

58	50	12	34	26	18	10	2	60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6	64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1	59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5	63	55	47	39	31	23	15	7

40	8	48	16	56	24	64	32	39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30	37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28	35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26	33	1	41	9	49	17	57	25