Affine Cipher Demo - JieJiSS' Blog

0x00 背景知识

仿射密码（Affine Cipher）是对称加密的（非常简单的）一种，其本质是基于取模运算的替换密码。这种加密方式将明文的每一个字节依次替换成经过特定运算后得到的密文，从而破坏明文的可读性。这里给出其在明文为 a-z 时的定义：

设明文为 \(x\)，密文为 \(y\)，秘钥为 \(\mathrm{key} = \left(a,b\right)\)，其中 \(a,b\in\mathbb{Z}\cap \left[1,26\right]\)，则可以分别定义加密函数 \(enc\) 和解密函数 \(dec\) 为 \[ enc\left(x,\mathrm{key}\right) = y \equiv a\cdot x+b \mod{26} \]

\[ dec\left(y,\mathrm{key}\right) = x \equiv a^{-1}\cdot \left(y-b\right) \mod{26} \]

其中 \(a^{-1}\) 是模数为 26 时 \(a\) 的逆元，也即 \(a\cdot a^{-1}\equiv1\mod{26}\)；所以，为了能够求得 \(a^{-1}\)，\(a\) 显然应与 26 互质，也即 \(\gcd\left(a,26\right)=1\)。

0x01 具体实现

于是可以首先编写出工具函数 gcd 和 inv，用于计算最大公约数和逆元：

/*
 * Calculate the greatest common divisor.
 */
function gcd(x, y) {
    if(!Number.isInteger(x) || !Number.isInteger(y))
        throw new TypeError("gcd(...) only accepts two integer");
    if(y === 0) return x;
    return gcd(y, x % y);
}

/*
 * Calculate the invision of number a under modulo m
 */
function inv(a, m) {
    for(let i = 1; i < m; i++)
        if(a * i % m === 1) return i;
    throw new RangeError(`cannot get the inversion of ${a} under modulo ${m}`);
}

在正式编写加密函数之前，我们还需要思考一个事情：上文给出的 \(enc\) 函数是仅针对输入的明文 \(x\) 为英文字母 a-z 的情况。如果我们想要支持 ASCII 码范围内的所有可见字符，我们就得把模数放大到 \(126-31=95\)（126和31分别是最大和最小的 ASCII 可见字符的十进制表示）。

这样，我们就可以开始着手编写 \(enc\) 加密函数的具体实现了：

function enc(text, key, modulo) {
    if(gcd(key[0], modulo) !== 1) {
        throw new RangeError(`key[0] (${key[0]}) should be a coprime number of ${modulo}`);
    }
    const converted = [];
    for(let i = 0; i < text.length; i++) {
        const num = text.charCodeAt(i) - 32;  // for ASCII char, num \in [0, 94]
        converted.push(String.fromCharCode((num * key[0] + key[1]) % modulo + 32));
    }
    return converted.join("");
}

function encASCII(text, key) {
    return enc(text, key, 95);
}

同理可以实现 \(dec\) 解密函数：

function dec(crypt, key, modulo) {
    if(gcd(key[0], modulo) !== 1) {
        throw new RangeError(`key[0] (${key[0]}) is not a coprime number of modulo ${modulo}`);
    }
    const rev = inv(key[0], modulo);
    const converted = [];
    for(let i = 0; i < crypt.length; i++) {
        const num = crypt.charCodeAt(i) - 32;
        converted.push(String.fromCharCode(((num - key[1]) * rev % modulo + modulo) % modulo + 32));
    }
    return converted.join("");
}

function decASCII(crypt, key) {
    return dec(crypt, key, 95);
}

踩坑提示：dec 函数的第九行中的 + modulo ) % modulo 似乎与使用数学方法表示的 \(dec\) 定义不符。+ modulo 是因为 num - key[1] 很有可能是个负整数，而 JavaScript 中对负整数取模也会得到一个负数，然而我们想要的是该负数加上模数后得到的对应的正取模结果：
1
2
3
4
5
 5 % 3  //  2, ✔
-5 % 3  // -2, ✘

(( 5 % 3) + 3) % 3  // 2, ✔
((-5 % 3) + 3) % 3  // 1, ✔

最终效果：

// key = [23, 16], module = 95
encASCII("I'm JieJiSS, and I haven't finished my homework yet!", [23, 16]);
// encrypt result: )rm0@ps@pQQ'0v%\0)0Yv~s%rP0+p%p9Ys\0md0Y<ms6<"?G

decASCII(")rm0@ps@pQQ'0v%\\0)0Yv~s%rP0+p%p9Ys\\0md0Y<ms6<\"?G", [23, 16]);
// decrypt result: I'm JieJiSS, and I haven't finished my homework yet!

0x02 局限性

仿射加密的安全性其实非常差：

仿射加密的秘钥空间相对较小，可能的秘钥组合并不多，可以暴力破解；
字母与字母间一一对应，导致攻击者可以通过分析字母出现的频率来推测出明文。

一个合格的、安全的加密算法，无论是对称加密还是非对称加密，都必须要避免上述两个缺陷；由此可以看出，仿射加密作为一个年龄较大的对称加密算法，已经不适合继续使用了。

（当然了，自己玩的话没人拦着你（笑

来源：https://blog.jiejiss.com/

文章目录

0x00 背景知识

0x01 具体实现

0x02 局限性