【总结笔记】crypto

工具：

cyberchef魔法棒
轩禹RSA

密码：

维吉尼亚密码计算密钥–>维吉尼亚密钥只能由字母组成

def find_vigenere_key(plaintext, ciphertext):
    """
    根据维吉尼亚密码的明文和密文推导密钥

    参数:
        plaintext (str): 明文，可以包含字母、数字和其他字符
        ciphertext (str): 密文，可以包含字母、数字和其他字符

    返回:
        str: 推导得到的密钥，大小写与明文保持一致
    """
    # 确保输入的明文和密文长度相同
    if len(plaintext) != len(ciphertext):
        raise ValueError("明文和密文的长度必须相同")

    key = []
    # 遍历每个字符对，计算对应的密钥字符
    for p, c in zip(plaintext, ciphertext):
        # 检查是否都为字母或都为非字母
        if p.isalpha() and c.isalpha():
            # 都是字母，计算密钥
            is_upper = p.isupper()  # 确定大小写，与明文保持一致

            # 转换为0-25的数值 (A=0, B=1, ..., Z=25)
            p_val = ord(p.upper()) - ord('A')
            c_val = ord(c.upper()) - ord('A')

            # 计算密钥值: 密钥 = (密文 - 明文) mod 26
            k_val = (c_val - p_val) % 26

            # 转换回字母，并保持原大小写
            key_char = chr(k_val + ord('A'))
            if not is_upper:
                key_char = key_char.lower()

            key.append(key_char)
        elif not p.isalpha() and not c.isalpha():
            # 都不是字母，密钥保持与明文一致
            key.append(p)
        else:
            # 一个是字母，一个不是字母，不匹配
            raise ValueError(f"明文和密文在位置 {len(key)} 处不匹配（一个是字母，一个是非字母）")

    return ''.join(key)


def main():
    print("维吉尼亚密码密钥推导工具")
    print("-------------------------")

    # 获取用户输入
    plaintext = input("请输入明文: ")
    ciphertext = input("请输入密文: ")

    try:
        # 推导密钥
        key = find_vigenere_key(plaintext, ciphertext)
        print(f"\n推导得到的密钥是: {key}")

        # 验证密钥是否正确
        # 维吉尼亚加密函数用于验证
        def vigenere_encrypt(text, key):
            encrypted = []
            key_len = len(key)
            for i, char in enumerate(text):
                k_char = key[i % key_len]

                if char.isalpha() and k_char.isalpha():
                    # 都是字母，进行加密
                    is_upper = char.isupper()

                    t_val = ord(char.upper()) - ord('A')
                    k_val = ord(k_char.upper()) - ord('A')
                    c_val = (t_val + k_val) % 26

                    encrypted_char = chr(c_val + ord('A'))
                    if not is_upper:
                        encrypted_char = encrypted_char.lower()

                    encrypted.append(encrypted_char)
                elif not char.isalpha() and not k_char.isalpha():
                    # 都不是字母，保持不变
                    encrypted.append(char)
                else:
                    # 一个是字母，一个不是字母，无法加密
                    raise ValueError(f"明文和密钥在位置 {i} 处不匹配（一个是字母，一个是非字母）")

            return ''.join(encrypted)

        # 使用推导出的密钥加密明文，检查是否与密文一致
        verified_ciphertext = vigenere_encrypt(plaintext, key)
        if verified_ciphertext == ciphertext:
            print("验证成功: 使用该密钥加密明文得到的结果与输入的密文一致")
        else:
            print(f"验证失败: 使用该密钥加密得到 {verified_ciphertext}，与输入的密文不一致")

    except ValueError as e:
        print(f"错误: {e}")


if __name__ == "__main__":
    main()
"""
维吉尼亚密码密钥推导工具
-------------------------
请输入明文: 0xGame
请输入密文: 0lCcop

推导得到的密钥是: 0oWccl
验证成功: 使用该密钥加密明文得到的结果与输入的密文一致

进程已结束，退出代码为 0
"""

RSA

RSA 算法原理

基于大整数分解难题（IFP），是目前最广泛使用的非对称加密算法。
生成公私钥

选取大素数：选择两个不同大素数 $p$ 和 $q$ ，计算 $N = p \cdot q$ 。
欧拉函数：计算 $\varphi(N) = (p-1)(q-1)$ 。若 $p$ 为素数，则 $\varphi(p) = p-1$ 。
$\varphi(N)$ 表示小于 $N$ 且与 $N$ 互质的数的个数。
选择公钥指数：选整数 $e$ 满足 $1 < e < \varphi(N)$ 且 $\gcd(e, \varphi(N)) = 1$ 。
计算私钥指数：求 $e$ 在模 $\varphi(N)$ 下的乘法逆元 $d$ ，即 $e \cdot d \equiv 1 \pmod{\varphi(N)}$ 。
乘法逆元：若 $a \cdot b \equiv 1 \pmod{m}$ ，则 $b$ 是 $a$ 在模 $m$ 下的逆元。
销毁中间变量：删除 $p$ 和 $q$ ，保留 $(N, e)$ 为公钥， $(N, d)$ 为私钥。

加解密过程
- 加密：将明文 $m$ 转为数字，计算密文 $c \equiv m^e \pmod{N}$ 。
- 解密：使用私钥计算明文 $m \equiv c^d \pmod{N}$ $m \equiv c^{d} (m o d N)$ 。
  - 常见过程：—>求d—>求欧拉函数—>求大素数–>如何得到素数

补充：欧拉函数及其性质

多因子计算欧拉函数
高阶的pq计算欧拉函数

补充：模的性质

题目类型

基础RSA

RSA常见脚本：

from Crypto.Util.number import *

n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

分解N

本地工具（yafu打开cmd使用，
- 分解因数n：.\yafu-x64.exe “factor(n)”
在线网站
- 注意！！！点数字后就到上方框里了可以复制！！！（有点愚蠢但愚蠢的人没发现

pq相邻素数

特征：

p = getPrime(512)
q = gmpy2.next_prime(p)

解法：

from Crypto.Util.number import *
from gmpy2 import *



sn = isqrt(n)
q = next_prime(sn)
p = n // q

phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)
print(long_to_bytes(m))

pq相近

特征：

q = gmpy2.next_prime(p - getPrime(128)+getPrime(128)-getPrime(256)+getPrime(256))

解法：费马分解

from Crypto.Util.number import *
from gmpy2 import *

def fermat_attack(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q

p, q = fermat_attack(n)
phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)
print(long_to_bytes(m))

共享素数

例题：

from Crypto.Util.number import *
flag = b'***********'

p1 = getPrime(512)
q = getPrime(512)
p2 = getPrime(512)

n1 = p1*q
n2 = p2*q

e = 65537

m = bytes_to_long(flag)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'e = {e}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')

"""
n1 = 
n2 = 
e = 65537
c1 = 
c2 =

解法：求最小公因数

from Crypto.Util.number import *
from gmpy2 import *

q = gcd(n1, n2)
p1 = n1 // q
phi = (p1-1)*(q-1)
d = invert(e, phi)

m = pow(c1, d, n1)
print(long_to_bytes(m))

多个素数

特征：

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p*q*r
e = 65537
phi = (p-1)*(q-1)*(r-1)

解法：

from Crypto.Util.number import *

n=p*q*r
phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

素数中有高阶次方

思路：素数中有高阶次方求欧拉

alt text

解法：

from Crypto.Util.number import *

n = (p**7)*q # 特征

phi = (p**6)*(p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

dpdq泄露

特征：

from Crypto.Util.number import *

flag = b'flag{easy_RSA888888888888}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e = getPrime(128)
d = inverse(e, (p-1)*(q-1))

dp = d % (p-1)
dq = d % (q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'c = {c}')
print(f'dp = {dp}') # 特征
print(f'dq = {dq}')

思路：存脚本

alt text

from Crypto.Util.number import *
from gmpy2 import *

p = 
q = 
c = 
dp = 
dq = 

invp = invert(p, q)
m1 = powmod(c, dp, p)
m2 = powmod(c, dq, q)
m = (((m2 - m1)*invp) % q)*p + m1
print(long_to_bytes(m))

共模攻击

特征

e1 = getPrime(16)
e2 = getPrime(16)

c1 = pow(m, e1, n)
c2 = pow(m, e2, n)

思路：存脚本

from Crypto.Util.number import *
from gmpy2 import *

n = 
e1 = 55313
e2 = 44647
c1 = 
c2 = 
_, s1, s2 = gmpy2.gcdext(e1, e2)

m = gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2, s2, n) % n
print(long_to_bytes(m))

知识补充

getPrime() 函数
- 在Python中通常来自 Crypto.Util.number 模块，用于生成指定位数的随机质数
python中invert和inverse函数在ctf crypto题目应用区别
- gmpy2.invert (通常更快)
- 当逆元不存在时（gcd(a, n) != 1）

# gmpy2.invert 返回 None
result1 = invert(4, 8)  # gcd(4,8)=4 != 1
print(f"gmpy2.invert(4,8) = {result1}")  # None

# Crypto.Util.number.inverse 抛出异常
try:
    result2 = inverse(4, 8)
except ValueError as e:
    print(f"Crypto.inverse(4,8) 错误: {e}")