Skip to content

Crypto

介绍

出题人给定一个有一定缺陷的加密算法，需要选手攻破该加密算法，得到解密后的文字，或者伪造加密信息

密码学入门书籍：An introduction to mathematical cryptography

概念：明文，密文，密码算法，密钥，对称加密（同一密钥），非对称加密（加密用公钥，解密用密钥），哈希函数（单向映射），数字签名。

数学不太好，就简单写吧。

RSA

RSA算法是一种非对称加密算法，其基于大数分解的数学难题，其安全性依赖于大整数分解的计算复杂性。

代码示例

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

# 生成大素数
def generate_large_prime(bits):
    while True:
        p = random.getrandbits(bits)
        if isprime(p):
            return p

# 密钥生成
def generate_keys(bits=1024):
    # 选择两个大素数 p 和 q
    p = generate_large_prime(bits)
    q = generate_large_prime(bits)

    # 计算它们的乘积 n
    n = p * q

    # 计算欧拉函数 φ(n)
    phi = (p - 1) * (q - 1)

    # 选择一个公钥指数 e，通常选择 65537
    e = 65537

    # 计算私钥指数 d，使得 d 是 e 关于 φ(n) 的模反元素
    d = mod_inverse(e, phi)

    # 返回公钥 (e, n) 和私钥 (d, n)
    return (e, n), (d, n)

# 加密
def encrypt(public_key, plaintext):
    e, n = public_key

    # 将明文转换为整数 m
    m = int.from_bytes(plaintext.encode(), 'big')

    # 计算密文 c = m^e mod n
    c = pow(m, e, n)

    return c

# 解密
def decrypt(private_key, ciphertext):
    d, n = private_key

    # 计算明文整数 m = c^d mod n
    m = pow(ciphertext, d, n)

    # 将整数 m 转换回明文
    plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()

    return plaintext

# 示例使用
public_key, private_key = generate_keys()
plaintext = "Hello, RSA!"

# 使用公钥加密明文
ciphertext = encrypt(public_key, plaintext)

# 使用私钥解密密文
decrypted_text = decrypt(private_key, ciphertext)

print("原文:", plaintext)
print("密文:", ciphertext)
print("解密后:", decrypted_text)

RSA攻击手段

最容易想到的攻击手段是素数因子分解攻击，然而大多数情况下都不可能分解出一个特别大的n。

除此以外还有低加密指数攻击（e比较小时），共模攻击（密钥用了相同的n，不同的e），选择明密文攻击（能够使用已知明文加密，或能随意解密密文）等等。

RSA数字签名和一般的RSA略有不同，因为签名是使用私钥加密，用公钥解密，但依旧可以用以上手段攻击。

AES

AES（Advanced Encryption Standard，高级加密标准）是一种对称加密算法，用于保护电子数据。

AES的基本特性

对称加密 ：AES使用相同的密钥进行加密和解密，这意味着加密和解密双方必须共享同一个密钥。

分组加密 ：AES是一种分组加密算法，它将数据分成固定长度的块进行加密。常见的块大小为128位（16字节）。

密钥长度 ：AES支持三种不同的密钥长度：128位、192位和256位。密钥长度越长，安全性越高，但加密和解密的速度也会稍慢。

AES攻击手段

AES有多种加密模式，因此攻击手段也十分丰富。

以CBC模式为例，常用的有Padding Oracle Attack（填充攻击）和Bit-Flipping Attack（字节反转攻击）。

ElGamal

ElGamal 是一种基于离散对数问题（DLP）的公钥加密算法，广泛用于加密和数字签名。

Wiki: ElGamal加密算法

破解的有些方法思维和RSA比较相似，但解决离散对数问题用的算法不同：BSGS算法、pohlig-hellman算法。