密码学是计算机科学中一个迷人的领域，它保护着我们的数字通信安全。在 Exercism 的 “affine-cipher” 练习中，我们将探索一种经典的替换密码——仿射密码(Affine Cipher)，并学习如何在 Rust 中实现它。这不仅能帮助我们理解密码学基础知识，还能深入掌握 Rust 中的错误处理和数论运算。

什么是仿射密码？

仿射密码是一种 monoalphabetic substitution cipher（单表替换密码），它使用数学函数来加密字母。对于字母表中的每个字母，我们首先确定其在字母表中的位置（A=0, B=1, …, Z=25），然后使用以下公式进行加密：

E(x) = (ax + b) mod m

其中：

  • x 是字母在字母表中的位置
  • a 和 b 是密钥
  • m 是字母表的大小（对于英文是26）

解密使用相反的运算：
D(x) = a⁻¹(x - b) mod m

其中 a⁻¹ 是 a 的模逆元。

问题描述

让我们先看看练习提供的函数签名：

/// While the problem description indicates a return status of 1 should be returned on errors,
/// it is much more common to return a `Result`, so we provide an error type for the result here.
#[derive(Debug, Eq, PartialEq)]
pub enum AffineCipherError {
    NotCoprime(i32),
}

/// Encodes the plaintext using the affine cipher with key (`a`, `b`). Note that, rather than
/// returning a return code, the more common convention in Rust is to return a `Result`.
pub fn encode(plaintext: &str, a: i32, b: i32) -> Result<String, AffineCipherError> {
    unimplemented!("Encode {} with the key ({}, {})", plaintext, a, b);
}

/// Decodes the ciphertext using the affine cipher with key (`a`, `b`). Note that, rather than
/// returning a return code, the more common convention in Rust is to return a `Result`.
pub fn decode(ciphertext: &str, a: i32, b: i32) -> Result<String, AffineCipherError> {
    unimplemented!("Decode {} with the key ({}, {})", ciphertext, a, b);
}

我们需要实现这两个函数，它们应该：

  1. 对输入文本进行加密或解密
  2. 在参数不符合要求时返回适当的错误

关键概念：互质数和模逆元

仿射密码有一个重要要求：密钥 a 必须与字母表大小 m 互质（即 gcd(a, m) = 1）。对于英文，m=26，与26互质的数有：1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25。

我们需要一个函数来计算两个数的最大公约数：

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a % b)
    }
}

我们还需要计算模逆元的函数。a 的模逆元 a⁻¹ 是满足 (a * a⁻¹) ≡ 1 (mod m) 的数：

fn mod_inverse(a: i32, m: i32) -> i32 {
    // 扩展欧几里得算法
    let mut lm = 1;
    let mut hm = 0;
    let mut low = a % m;
    let mut high = m;
    
    while low > 1 {
        let ratio = high / low;
        let nm = hm - lm * ratio;
        let new = high - low * ratio;
        hm = lm;
        lm = nm;
        high = low;
        low = new;
    }
    
    lm % m
}

完整实现

现在让我们实现完整的仿射密码：

/// While the problem description indicates a return status of 1 should be returned on errors,
/// it is much more common to return a `Result`, so we provide an error type for the result here.
#[derive(Debug, Eq, PartialEq)]
pub enum AffineCipherError {
    NotCoprime(i32),
}

const M: i32 = 26; // 字母表大小

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a % b)
    }
}

fn mod_inverse(a: i32, m: i32) -> i32 {
    let mut lm = 1;
    let mut hm = 0;
    let mut low = a % m;
    let mut high = m;
    
    while low > 1 {
        let ratio = high / low;
        let nm = hm - lm * ratio;
        let new = high - low * ratio;
        hm = lm;
        lm = nm;
        high = low;
        low = new;
    }
    
    lm % m
}

/// Encodes the plaintext using the affine cipher with key (`a`, `b`). Note that, rather than
/// returning a return code, the more common convention in Rust is to return a `Result`.
pub fn encode(plaintext: &str, a: i32, b: i32) -> Result<String, AffineCipherError> {
    // 检查 a 是否与 M 互质
    if gcd(a, M) != 1 {
        return Err(AffineCipherError::NotCoprime(a));
    }
    
    let mut result = String::new();
    let mut char_count = 0;
    
    for c in plaintext.chars() {
        if c.is_ascii_alphabetic() {
            // 每5个字符添加一个空格
            if char_count > 0 && char_count % 5 == 0 {
                result.push(' ');
            }
            
            let x = (c.to_ascii_lowercase() as i32) - ('a' as i32);
            let encoded = (a * x + b).rem_euclid(M);
            result.push((encoded as u8 + b'a') as char);
            char_count += 1;
        } else if c.is_ascii_digit() {
            // 数字保持不变
            if char_count > 0 && char_count % 5 == 0 {
                result.push(' ');
            }
            result.push(c);
            char_count += 1;
        }
    }
    
    Ok(result)
}

/// Decodes the ciphertext using the affine cipher with key (`a`, `b`). Note that, rather than
/// returning a return code, the more common convention in Rust is to return a `Result`.
pub fn decode(ciphertext: &str, a: i32, b: i32) -> Result<String, AffineCipherError> {
    // 检查 a 是否与 M 互质
    if gcd(a, M) != 1 {
        return Err(AffineCipherError::NotCoprime(a));
    }
    
    let a_inv = mod_inverse(a, M);
    let mut result = String::new();
    
    for c in ciphertext.chars() {
        if c.is_ascii_alphabetic() {
            let y = (c as i32) - ('a' as i32);
            let decoded = (a_inv * (y - b)).rem_euclid(M);
            result.push((decoded as u8 + b'a') as char);
        } else if c.is_ascii_digit() {
            // 数字保持不变
            result.push(c);
        }
        // 忽略空格和其他字符
    }
    
    Ok(result)
}

测试用例分析

通过查看测试用例，我们可以更好地理解实现细节：

#[test]
fn encode_yes() {
    assert_eq!(encode("yes", 5, 7).unwrap(), "xbt")
}

这个测试展示了基本的加密过程。

#[test]
fn encode_mindblowingly() {
    assert_eq!(encode("mindblowingly", 11, 15).unwrap(), "rzcwa gnxzc dgt")
}

注意输出中包含空格，每5个字符后添加一个空格。

#[test]
fn encode_numbers() {
    assert_eq!(
        encode("Testing,1 2 3, testing.", 3, 4).unwrap(),
        "jqgjc rw123 jqgjc rw"
    )
}

这个测试表明标点符号会被忽略，而数字会被保留。

#[test]
fn encode_with_a_not_coprime_to_m() {
    const EXPECTED_ERROR: AffineCipherError = AffineCipherError::NotCoprime(6);
    match encode("This is a test.", 6, 17) {
        Err(EXPECTED_ERROR) => (),
        Err(err) => panic!(
            "Incorrect error: expected: {:?}, actual: {:?}.",
            EXPECTED_ERROR, err
        ),
        Ok(r) => panic!(
            "Cannot encode/decode when a is coprime to m: expected: {:?}, actual: {:?}.",
            EXPECTED_ERROR, r
        ),
    }
}

当 a 与字母表大小不互质时，函数应该返回错误。

解密示例

解密过程同样重要，我们可以通过测试用例来验证：

#[test]
fn decode_exercism() {
    assert_eq!(decode("tytgn fjr", 3, 7).unwrap(), "exercism")
}

#[test]
fn decode_all_the_letters() {
    assert_eq!(
        decode("swxtj npvyk lruol iejdc blaxk swxmh qzglf", 17, 33).unwrap(),
        "thequickbrownfoxjumpsoverthelazydog"
    )
}

错误处理的重要性

这个练习很好地展示了 Rust 中错误处理的实践：

#[derive(Debug, Eq, PartialEq)]
pub enum AffineCipherError {
    NotCoprime(i32),
}

使用 Result 类型而不是返回错误码是 Rust 中的惯用法。这种做法强制调用者处理可能的错误情况，从而编写出更健壮的代码。

性能和优化考虑

在实现仿射密码时，我们需要注意以下几点：

  1. 模运算：使用 rem_euclid 而不是 % 来处理负数
  2. 字符处理：只处理字母和数字，忽略其他字符
  3. 内存分配：合理使用 String 和 &str

总结

通过仿射密码练习，我们学到了：

  1. 密码学基础：了解了替换密码和模运算在加密中的应用
  2. 数论知识：掌握了最大公约数和模逆元的计算方法
  3. 错误处理：学会了如何在 Rust 中使用 Result 类型处理错误
  4. 字符处理：熟悉了 Rust 中字符和字符串的处理方法
  5. 算法实现：实践了扩展欧几里得算法等经典算法

这些技能不仅在密码学中有用，在许多其他领域也会派上用场。仿射密码虽然是一个简单的加密系统，但它包含了现代密码学的许多基本概念，是学习更高级加密技术的良好起点。

# rust # python # 算法
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

OpenClaw Browser：浏览器控制入门

avatar AtomGit开源社区

最新PPOCRv5模型训练教程。文字检测+文字识别（自用）

最新的ppocrv5模型训练过程，搭配上一个环境配置的文章使用。训练之前我已经用paddlelabel标注好了五百多张图片，我训练模型是为了识别书脊的文字。

avatar AtomGit开源社区

Linux 网络虚拟化深度解析：从 veth 设备对到容器网络实战

veth（Virtual Ethernet）设备对，可以理解为软件模拟的一对 "虚拟网卡"，它们总是成对出现，就像用一根虚拟的 "网线" 把两个网络接口连在一起。物理世界类比：想象两台电脑，用一根网线直连它们的网卡，数据就能互相传输。虚拟世界实现：veth pair 就是软件实现的这种 "直连网线"，一端叫 veth0，另一端叫 veth1，数据从 veth0 发出，必然从 veth1 收到，反之

avatar AtomGit开源社区