输入：a, b（非负整数，a ≥ b）
输出：gcd(a, b)

while b ≠ 0:
    r = a mod b
    a = b
    b = r
return a

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return g, x, y

def modular_exponentiation(base, exp, mod):
    result = 1
    base = base % mod
    
    while exp > 0:
        if exp % 2 == 1:  # 如果当前位为1
            result = (result * base) % mod
        exp = exp >> 1  # 右移一位
        base = (base * base) % mod
    
    return result

# Python字典内部使用哈希表
my_dict = {"key": "value"}

# 不安全！
import random
secret_key = random.randint(0, 2**128)

# 安全
import secrets
secret_key = secrets.randbits(128)

# 不安全：可能在第一个不匹配字符处提前返回
if user_hash == correct_hash:
    ...

# 安全：恒定时间比较
import hmac
if hmac.compare_digest(user_hash, correct_hash):
    ...

"""
欧几里得算法及其扩展版本的实现
"""


def gcd(a, b):
    """
    计算最大公约数
    
    时间复杂度: O(log(min(a, b)))
    """
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """计算最小公倍数"""
    return abs(a * b) // gcd(a, b)


def extended_gcd(a, b):
    """
    扩展欧几里得算法
    
    返回: (g, x, y) 使得 ax + by = g = gcd(a, b)
    """
    if a == 0:
        return b, 0, 1
    
    g, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    
    return g, x, y


def modular_inverse(a, m):
    """
    计算a模m的逆元
    
    前提: gcd(a, m) = 1
    
    返回: a^(-1) mod m
    """
    g, x, _ = extended_gcd(a % m, m)
    
    if g != 1:
        raise ValueError(f"模逆元不存在 (gcd({a}, {m}) = {g})")
    
    return x % m


def demonstrate_euclidean():
    """演示欧几里得算法"""
    
    print("=== 欧几里得算法 ===")
    
    test_cases = [
        (48, 18),
        (1071, 462),
        (123456789, 987654321),
    ]
    
    for a, b in test_cases:
        g = gcd(a, b)
        l = lcm(a, b)
        print(f"gcd({a}, {b}) = {g}")
        print(f"lcm({a}, {b}) = {l}")
        print()
    
    print("=== 扩展欧几里得算法 ===")
    
    a, b = 35, 15
    g, x, y = extended_gcd(a, b)
    print(f"{a}×{x} + {b}×{y} = {g}")
    print(f"验证: {a*x + b*y} = {g}")
    print()
    
    print("=== 模逆元 ===")
    
    a, m = 3, 11
    inv = modular_inverse(a, m)
    print(f"{a}^(-1) mod {m} = {inv}")
    print(f"验证: {a} × {inv} mod {m} = {(a * inv) % m}")


if __name__ == "__main__":
    demonstrate_euclidean()

"""
RSA加密算法的简化实现（用于教学目的）

注意：这不是生产级实现！实际应用中应使用经过审计的库。
"""

import random
import math


def is_prime_miller_rabin(n, k=10):
    """
    米勒-拉宾素性测试
    
    返回: True（可能是素数）或 False（一定是合数）
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    
    # 将 n-1 写为 2^r × d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # 进行k轮测试
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True


def generate_prime(bits):
    """生成指定比特数的随机素数"""
    while True:
        candidate = random.getrandbits(bits)
        candidate |= (1 << bits - 1) | 1  # 确保最高位和最低位为1
        if is_prime_miller_rabin(candidate):
            return candidate


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y


def modular_inverse(a, m):
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError("模逆元不存在")
    return x % m


class RSACipher:
    """RSA加密解密类"""
    
    def __init__(self, key_bits=512):
        """生成密钥对"""
        # 生成两个大素数
        self.p = generate_prime(key_bits // 2)
        self.q = generate_prime(key_bits // 2)
        
        # 计算n和φ(n)
        self.n = self.p * self.q
        self.phi_n = (self.p - 1) * (self.q - 1)
        
        # 选择公钥指数e
        self.e = 65537  # 常用值，是素数且二进制只有两个1
        
        # 确保e与φ(n)互质
        while gcd(self.e, self.phi_n) != 1:
            self.e += 2
        
        # 计算私钥指数d
        self.d = modular_inverse(self.e, self.phi_n)
        
        self.public_key = (self.e, self.n)
        self.private_key = (self.d, self.n)
    
    def encrypt(self, message):
        """
        加密消息
        
        参数: message (int) < n
        返回: ciphertext (int)
        """
        if message >= self.n:
            raise ValueError("消息太大")
        return pow(message, self.e, self.n)
    
    def decrypt(self, ciphertext):
        """
        解密密文
        
        参数: ciphertext (int)
        返回: message (int)
        """
        return pow(ciphertext, self.d, self.n)
    
    def encrypt_string(self, text):
        """将字符串转换为整数并加密"""
        # 简单编码：每个字符转为ASCII值拼接
        message_int = int.from_bytes(text.encode('utf-8'), 'big')
        if message_int >= self.n:
            raise ValueError("文本太长，需要更大的密钥")
        ciphertext = self.encrypt(message_int)
        return ciphertext
    
    def decrypt_string(self, ciphertext):
        """解密并还原为字符串"""
        message_int = self.decrypt(ciphertext)
        # 计算需要的字节数
        byte_length = (message_int.bit_length() + 7) // 8
        message_bytes = message_int.to_bytes(byte_length, 'big')
        return message_bytes.decode('utf-8')


def demonstrate_rsa():
    """演示RSA加密解密"""
    
    print("=== RSA密钥生成 ===")
    rsa = RSACipher(key_bits=64)  # 小密钥用于演示
    
    print(f"p = {rsa.p}")
    print(f"q = {rsa.q}")
    print(f"n = {rsa.n}")
    print(f"φ(n) = {rsa.phi_n}")
    print(f"公钥 (e, n) = ({rsa.e}, {rsa.n})")
    print(f"私钥 (d, n) = ({rsa.d}, {rsa.n})")
    print()
    
    print("=== 整数加密解密 ===")
    message = 42
    print(f"原始消息: {message}")
    
    ciphertext = rsa.encrypt(message)
    print(f"密文: {ciphertext}")
    
    decrypted = rsa.decrypt(ciphertext)
    print(f"解密消息: {decrypted}")
    print(f"验证: {message == decrypted}")
    print()
    
    print("=== 字符串加密解密 ===")
    text = "Hello RSA!"
    print(f"原始文本: {text}")
    
    try:
        ct = rsa.encrypt_string(text)
        print(f"密文: {ct}")
        
        dt = rsa.decrypt_string(ct)
        print(f"解密文本: {dt}")
        print(f"验证: {text == dt}")
    except ValueError as e:
        print(f"错误: {e}")


if __name__ == "__main__":
    demonstrate_rsa()

"""
哈希函数应用：数据完整性验证和密码存储
"""

import hashlib
import os
import json


def compute_sha256(data):
    """计算SHA-256哈希值"""
    if isinstance(data, str):
        data = data.encode('utf-8')
    return hashlib.sha256(data).hexdigest()


def verify_file_integrity(file_path, expected_hash):
    """
    验证文件完整性
    
    返回: True如果哈希匹配，False否则
    """
    with open(file_path, 'rb') as f:
        file_hash = hashlib.sha256(f.read()).hexdigest()
    return file_hash == expected_hash


class PasswordHasher:
    """
    安全的密码哈希类
    
    使用PBKDF2-HMAC-SHA256进行密钥派生
    """
    
    def __init__(self, iterations=100000):
        self.iterations = iterations
    
    def hash_password(self, password):
        """
        哈希密码，生成随机盐
        
        返回: (salt_hex, hash_hex)
        """
        salt = os.urandom(32)  # 256位盐
        hash_value = hashlib.pbkdf2_hmac(
            'sha256',
            password.encode('utf-8'),
            salt,
            self.iterations
        )
        return salt.hex(), hash_value.hex()
    
    def verify_password(self, password, salt_hex, hash_hex):
        """
        验证密码
        
        返回: True如果密码正确
        """
        salt = bytes.fromhex(salt_hex)
        expected_hash = bytes.fromhex(hash_hex)
        
        computed_hash = hashlib.pbkdf2_hmac(
            'sha256',
            password.encode('utf-8'),
            salt,
            self.iterations
        )
        
        return hashlib.compare_digest(computed_hash, expected_hash)


def demonstrate_hashing():
    """演示哈希函数应用"""
    
    print("=== SHA-256哈希 ===")
    
    messages = [
        "Hello, World!",
        "Hello, World",
        "",
        "a" * 1000,
    ]
    
    for msg in messages:
        hash_val = compute_sha256(msg)
        print(f"'{msg[:30]}{'...' if len(msg) > 30 else ''}' -> {hash_val[:16]}...")
    
    print("\n=== 雪崩效应 ===")
    
    msg1 = "password"
    msg2 = "passwore"  # 只改变一个字符
    
    hash1 = compute_sha256(msg1)
    hash2 = compute_sha256(msg2)
    
    print(f"'{msg1}' -> {hash1}")
    print(f"'{msg2}' -> {hash2}")
    
    # 计算哈希值的差异位数
    diff_bits = sum(
        bin(int(a, 16) ^ int(b, 16)).count('1')
        for a, b in zip(hash1, hash2)
    )
    total_bits = len(hash1) * 4
    print(f"差异位数: {diff_bits}/{total_bits} ({100*diff_bits/total_bits:.1f}%)")
    
    print("\n=== 密码哈希 ===")
    
    hasher = PasswordHasher(iterations=10000)  # 减少迭代次数以加快演示
    
    password = "MySecurePassword123!"
    salt, hash_val = hasher.hash_password(password)
    
    print(f"盐: {salt[:16]}...")
    print(f"哈希: {hash_val[:16]}...")
    
    # 验证正确密码
    correct = hasher.verify_password(password, salt, hash_val)
    print(f"正确密码验证: {correct}")
    
    # 验证错误密码
    wrong = hasher.verify_password("WrongPassword", salt, hash_val)
    print(f"错误密码验证: {wrong}")


if __name__ == "__main__":
    demonstrate_hashing()