checkin - Writeup by AI

一、题目信息

• 题目来源：BugKU
• 题目类别：Crypto（古典密码）
• 题目类型：仿射密码（Affine Cipher）
• 密文：oclz{loovyd_vb_l_bvnucd_hqpumj}
• 提示：(11x + 11) mod 26

二、考点分析

核心知识点

1. 仿射密码原理：

   • 加密函数：$E(x)=(ax+b)\mathrm{mod}26$
   • 解密函数：$D(x)=a^{-1}(x-b)\mathrm{mod}26$
   • 其中 $a^{-1}$ 是 $a$ 在模 26 下的乘法逆元

2. 数学要求：

   • $a$ 必须与 26 互素（$\gcd (a,26)=1$），否则不存在逆元
   • 本题中 $a=11$，$\gcd (11,26)=1$，满足条件

3. 逆元计算：

   • 使用扩展欧几里得算法求解
   • $11\times 19\equiv 1(\mathrm{mod}26)$，所以 $11^{-1}\equiv 19(\mathrm{mod}26)$

三、解题思路

1. 识别加密类型

从提示 (11x + 11) mod 26 可以看出这是仿射密码的标准形式 $ax+b\mathrm{mod}26$，其中：

• $a=11$
• $b=11$

2. 确定解密策略

仿射密码的解密需要：

1. 计算 $a$ 的乘法逆元 $a^{-1}$
2. 应用解密公式：$D(x)=a^{-1}(x-b)\mathrm{mod}26$

3. 实现步骤

• 使用扩展欧几里得算法求逆元
• 对每个字母字符应用解密公式
• 保持非字母字符（如 {、}、_）不变

四、详细步骤

步骤 1：计算乘法逆元

通过扩展欧几里得算法：

11 × 19 ≡ 1 (mod 26)

验证：$11\times 19=209=8\times 26+1\equiv 1(\mathrm{mod}26)$

所以 $a^{-1}=19$

步骤 2：解密过程示例

以第一个字母 o 为例：

• o 对应数字：$14$（a=0, b=1, ..., o=14）
• 解密：$19\times (14-11)\mathrm{mod}26=19\times 3\mathrm{mod}26=57\mathrm{mod}26=5$
• $5$ 对应字母：f

同理解密所有字符。

步骤 3：编写解密脚本

def extended_gcd(a, b):
    """扩展欧几里得算法求逆元"""
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a) * y, y

def mod_inverse(a, m):
    """求 a 在模 m 下的乘法逆元"""
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def affine_decrypt(ciphertext, a, b):
    """仿射密码解密"""
    a_inv = mod_inverse(a, 26)
    plaintext = ""
    for char in ciphertext:
        if char.isalpha():
            base = ord('a') if char.islower() else ord('A')
            x = ord(char) - base
            decrypted_x = (a_inv * (x - b)) % 26
            plaintext += chr(base + decrypted_x)
        else:
            plaintext += char
    return plaintext

五、运行结果

执行解密脚本：

密文：oclz{loovyd_vb_l_bvnucd_hqpumj}
密钥：a=11, b=11
明文：flag{affine_is_a_simple_crypto}

验证：a * a^(-1) mod 26 = 11 * 19 mod 26 = 1

Flag：flag{affine_is_a_simple_crypto}