密碼分析技術與應用

def kasiski_examination(ciphertext):
    """Kasiski 檢驗法實作"""
    sequence_distances = {}
    for i in range(len(ciphertext) - 3):
        seq = ciphertext[i:i+3]
        if seq in sequence_distances:
            sequence_distances[seq].append(i)
        else:
            sequence_distances[seq] = [i]
    
    factors = []
    for seq, positions in sequence_distances.items():
        if len(positions) > 1:
            for i in range(len(positions) - 1):
                distance = positions[i+1] - positions[i]
                factors.extend([d for d in range(2, distance+1) if distance % d == 0])
    
    factor_counts = {}
    for factor in factors:
        factor_counts[factor] = factor_counts.get(factor, 0) + 1
    
    return sorted(factor_counts.items(), key=lambda x: x[1], reverse=True)

# 分析密鑰
ciphertext = "LXFOPVEFRNHRKASSISKDLX..."
key_length_candidates = kasiski_examination(ciphertext)

def frequency_analysis(text):
    """頻率分析函式"""
    frequency = {}
    for char in text:
        if char.isalpha():
            char = char.upper()
            frequency[char] = frequency.get(char, 0) + 1
    return frequency

def decrypt_vigenere(ciphertext, key):
    """維吉尼亞密碼解密函式"""
    plaintext = ""
    key_index = 0
    for char in ciphertext:
        if char.isalpha():
            shift = ord(key[key_index % len(key)].upper()) - ord('A')
            if char.isupper():
                plaintext += chr((ord(char) - shift - ord('A')) % 26 + ord('A'))
            else:
                plaintext += chr((ord(char.lower()) - shift - ord('a')) % 26 + ord('a'))
            key_index += 1
        else:
            plaintext += char
    return plaintext

# 使用頻率分析重建金鑰
for key_length, _ in key_length_candidates:
    key = ""
    for i in range(key_length):
        segment = "".join([ciphertext[j] for j in range(i, len(ciphertext), key_length)])
        freq = frequency_analysis(segment)
        # 根據頻率分析結果推測金鑰字元
    # 使用推測的金鑰進行解密
    plaintext = decrypt_vigenere(ciphertext, key)

import secrets

def generate_otp_key(length):
    """生成OTP金鑰"""
    return secrets.token_bytes(length)

def otp_encrypt(plaintext, key):
    """OTP加密函式"""
    if len(plaintext) != len(key):
        raise ValueError("明文和金鑰長度必須相同")
    return bytes([p ^ k for p, k in zip(plaintext, key)])

def otp_decrypt(ciphertext, key):
    """OTP解密函式"""
    return otp_encrypt(ciphertext, key)

# 使用範例
plaintext = b"Secret Message"
key = generate_otp_key(len(plaintext))
ciphertext = otp_encrypt(plaintext, key)
decrypted = otp_decrypt(ciphertext, key)

def sieve_of_eratosthenes(n):
    """埃拉託斯特尼篩法實作"""
    prime = [True] * (n + 1)
    prime[0] = prime[1] = False
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    return [p for p in range(2, n) if prime[p]]

# 找出1000以內的所有質數
primes = sieve_of_eratosthenes(1000)

import random

def rabin_miller(n, k=5):
    """拉賓-米勒質數測試"""
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    
    # 找到r和s使得n-1 = 2^s * r
    s = 0
    r = n - 1
    while r & 1 == 0:
        s += 1
        r //= 2
    
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, r, n)
        if x != 1 and x != n - 1:
            j = 1
            while j < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    return False
                j += 1
            if x != n - 1:
                return False
    return True

# 測試大數是否為質數
is_prime = rabin_miller(104729)

def prime_sieve(sieve_size):
 """
 高效生成指定範圍內的所有質數
 """
 # 初始化篩子，預設所有數為質數
 sieve = [True] * sieve_size
 sieve[0] = sieve[1] = False # 明確標記0和1為非質數

 # 迭代標記合數
 for i in range(2, int(sieve_size ** 0.5) + 1):
 if sieve[i]: # 若i為質數
 # 從i*i開始標記倍數
 for j in range(i * i, sieve_size, i):
 sieve[j] = False

 # 編譯質數列表
 return [i for i, is_prime in enumerate(sieve) if is_prime]

# 測試函式效能
print(prime_sieve(100))

import math

def is_prime(num):
 """
 檢查給定數字是否為質數
 """
 # 基本邊界條件判斷
 if num < 2:
 return False

 # 迭代檢查可能的因數
 for i in range(2, int(math.sqrt(num)) + 1):
 if num % i == 0: # 發現因數，立即傳回
 return False

 # 無因數，確認為質數
 return True

# 測試函式正確性
print(is_prime(29)) # True
print(is_prime(30)) # False