密码学专题 - 数学知识

2. 数论

这里仅列出一些对密码学有用的思想，关于数论更详细的知识请参考专业文献。

2.1 模运算

本质上，如果 $a = b + kn$ 对某些整数 $k$ 成立，那么 $a \equiv b \ (mod \ n)$ 。如果 $a$ 为正， $b$ 为 0 ~ n，那么你可将 $b$ 看做 $a$ 被 $n$ 整除后的余数。有时 $b$ 叫做 $a$ 模 $n$ 的余数 (residue)。有时 $a$ 叫做与 $b$ 模 $n$ 同余 (congruent) (三元等号 $\equiv$ 表示同余)。

从 $0 \sim n-1$ 的整数组成的集合构成了模 $n$ 的完全剩余集 (complete set of residue)。这意味着，对于每一个整数 $a$ ，它的模 $n$ 的余项是从 $0 \sim n-1$ 的某个数。

$a$ 模 $n$ 的运算给出了 $a$ 的余数，余数是从 $0 \sim n-1$ 的某个整数，这种运算称为模变换 (modular reduction)。例如， $5 \ mod \ 3 \ = 2$ 。

模运算就像普通运算一样，它是可交换的、可结合的和可分配的。而且，简化每一个中间结果的模 $n$ 运算，其作用与先进行全部运算再简化模 $n$ 运算是一样的。
$(a+b) mod \ n = ((a \ mod \ n) + (b \ mod \ n)) mod \ n$

$(a-b) mod \ n = ((a \ mod \ n) - (b \ mod \ n)) mod \ n$

$(a \times b) mod \ n = ((a \ mod \ n) \times (b \ mod \ n)) mod \ n$

密码学用了许多模 $n$ 运算，因为像计算离散对数和平方根这样的问题很困难，而模运算可将所有中间结果和最后结果限制在一个范围内，所以用它进行计算比较容易。对一个 $k$ 位的模数 $n$ ，任何加、减、乘的中间结果将不会超过 $2k$ 位长。因此可以用模运算进行指数运算而又不会产生巨大的中间结果。虽然计算某数的乘方并对其取模的运算
$a^x \ mod \ n$

将导致一系列的乘法和除法运算，但有加速运算的方法：一种方法指在最小化模乘法运算的数量；另一种旨在优化单个模乘法运算。因为操作步骤划分后，当完成一串乘法，并且每次都进行模运算后，指数运算就更快，这样就与一般取幂没有多大差别，但当用 200 位的数字进行运行时，情况就不同了。

例如，如果要计算 $a^8 \ mod \ n$ ，不要直接进行七次乘法和一个大数的模化简：
$(a \times a \times a \times a \times a \times a \times a \times a) mod \ n$

相反，应进行三次较小的乘法和三次较小的模化简：
$((a^2 mod \ n)^2 mod \ n)^2 mod \ n$

以此类推，
$a^{16} mod \ n = (((a^2 mod \ n)^2 mod \ n)^2 mod \ n)^2 mod \ n$

当 $x$ 不是 2 的幂次方时，计算 $a^x \ mod \ n$ 稍微要难些。可将 $x$ 表示成 2 的幂次方之和：在二进制中，25 是 11001，因此 $25=2^4 + 2^3 + 2^0$ 。故：
$a^25 \ mod \ n = (a \times a^{24})mod \ n = (a \times a^8 \times a^{16})mod \ n = (a \times ((a^2)^2)^2) \times (((a^2)^2)^2)^2) mod \ n = ((((a^2 \times a)^2)^2)^2 \times a) mod \ n$

注意，上面的公式利用了， $x^n \times y^n = (xy)^n$ 。

适当利用存储的中间结果，只需要 6 次乘法：
$(((((((a^2 \ mod \ n) \times a)mod \ n)^2 mod \ n)^2 mod \ n)^2 mod \ n) \times a) mod \ n$

这种算法称为加法链 (addition chaining)，或二进制平方和乘法方法。它用二进制表示了一个简单明了的加法链。算法的 C 语言描述如下：

unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {
    unsigned long s, t, u;
    int i;

    s = 1; t = x; u = y;
    while (u)
    {
        if (u&1) s = (s * t) % n;
        u >>= 1;
        t = (t * t) % n;
    }
    
    return s;
}

另一种递归算法为：

unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) {
    unsigned long tmp;
    if (y == 1) return (x % N);

    if ((y & 1) == 0) {
        tmp = fast_exp(x, y/2, N);
        return ((tmp * tmp) % N);
    }
    else {
        tmp = fast_exp(x, (y-1) / 2, N);
        tmp = (tmp * tmp) % N;
        tmp = (tmp * x) % N;
        return (tmp);
    }
}

对应的 python 实现如下。

def qe2(x, y, n):
    s = 1
    t = x
    u = y

    while (u):
        if (u&1):
            s = (s * t) % n
        u >>= 1
        t = (t * t) % n
    
    return s

另一种递归算法为：

def fast_exp(x, y, N):
    if (y == 1):
        return (x % N)

    if ((y & 1) == 0):
        tmp = fast_exp(x, y/2, N)
        return ((tmp * tmp) % N)
    else:
        tmp = fast_exp(x, (y-1) / 2, N)
        tmp = (tmp * tmp) % N
        tmp = (tmp * x) % N
        return (tmp)

如果用 $k$ 表示数 $x$ 中位数的长度，这项技术平均可减少 $1.5k$ 次操作。

2.2 整除性与素数

素数是这样一种数：比 1 大，其因子只有 1 和它本身，没有其他数可以整除它。2 是一个素数，其他的素数如 73、2521、2365347734399 和 $2^{756839}-1$ 等。素数是无限的。密码学，特别是公开密钥密码学常用大的素数 (512 位，甚至更大)。

如果 $b$ 除以 $a$ 余数为 0，则称 $a$ 是 $b$ 的一个因子 (记叙 $a|b$ ，读作 “a整除b”)。比如，7 是 35 的一个因子，记作 $7|35$ 。如果一个数只有 1 和它自身两个正因子，我们就称这个数是素数。比如，13 是素数，两个因子为 1 和 13。最初几个素数很容易找到：2、3、5、7、11、13...... 如果一个整数大于 1 且不为素数，我们就称为合数。1 既不是素数也不是合数。

下面是关于整除性的一个简单的引理。

引理 1：如果 $a|b$ 且 $b|c$ ，那么 $a|c$ 。

证明：如果 $a|b$ ，那么存在整数 $s$ 使得 $as = b$ (由 $b$ 能被 $a$ 整除可知 $b$ 是 $a$ 的倍数)；如果 $b|c$ ，同样存在整数 $t$ 使得 $bt=c$ 。综上可知， $c=bt=(as)t=a(st)$ ，所以 $a$ 为 $c$ 的一个因子。

引理 2：如果 $n$ 为大于 1 的正整数且 $d$ 为 $n$ 除 1 之外最小的因子，那么 $d$ 是素数。

证明：首先，我们必须保证 $d$ 是被明确定义的。(如果对于某个 $n$ ，除 1 之外不存在一个最小的因子，那么 $d$ 的定义就不恰当，引理 2 就毫无意义。) 由于 $n$ 也是 $n$ 的一个因子，而 $n>1$ ，所以 $n$ 至少有一个大于 1 的因子，也必然有一个大于 1 的最小因子。

为证明 $d$ 是素数，我们使用一种标准的数学技巧，称为反证法。为证明结论 X，反证法的一般思路是假设 X 不成立，接着从这个假设推出矛盾；如果假设 X 不成立能够推出矛盾，那么 X 必须是正确的。

在这个例子中，我们假设 $d$ 不是素数，那么 $d$ 肯定存在满足 $1<e<d$ 的因子 $e$ 。但是从引理 1 可知，如果 $e|d$ 且 $d|n$ ，那么 $e|n$ ，即 $e$ 也是 $n$ 的一个因子且 $e<d$ 。这样就产生了矛盾，因为 $d$ 被定义为 $n$ 除 1 之外最小的因子，因此我们的假设是错误的，从而 $d$ 是素数。

定理 3 (殴几里得)：素数有无穷多个。

证明：我们仍然使用反证法来证明。假设素数的个数是有限的，那么一个包含所有素数的列表也是有限的，记为 $p_1,p_2,p_3,...,p_k$ ，这里 $k$ 表示素数的个数。定义 $n = p_1p_2p_3...p_k+1$ ，即 $n$ 为所有素数的乘积加上 1。

考虑 $n$ 除 1 之外的最小因子，我们仍用 $d$ 来表示这个因子。由引理 2 可知， $d$ 为素数且 $d|n$ ；但是在那个有限的素数列表中，没有一个素数是 $n$ 的因子，因为它们都是 $n-1$ 的因子， $n$ 除以列表中任何一个素数 $p_i$ 都会有余数 1，所以 $d$ 为素数且不在列表中。而列表在定义时就包含了所有素数的，这样就出现了矛盾，所以素数的个数是有限的这个假设是错误的，从而可知素数有无穷多个。

2.3 最大公因子

两个数互素 (relatively prime) 是指：当它们除了 1 外没有共同的因子。换句话说，如果 $a$ 和 $n$ 的最大公因子 (greatest common divisor) 等于 1，那么可写作：
$gcd(a,n) = 1$

数 15 和 28 是互素的，15 和 27 不是，而 13 和 500 是。一个素数与它的倍数以外的任何其他数都是互素的。

计算两个数的最大公因子最容易的方法是用殴几里得算法 (Euclid's algorithm)。殴几里德在公元前 300 年所写的《Elements》中描述了这个算法。这个算法并非由他发明，历史学家相信这个算法在当时已有 200 年历史。它是幸存到现在最古老的非凡的算法，至今它仍是完好的。

算法的 C 语言描述如下：

/* returns gcd of x and y */
int gcd(int x, int y) {
    int g;

    if (x < 0)
        x = -x;
    
    if (y < 0)
        y = -y;

    if (x + y == 0)
        exit(1);

    g = y;

    while (x > 0)
    {
        g = x;
        x = y % x;
        y = g;
    }
    
    return g;
}

这个算法可以推广为返回由 m 个数组成的 gcd 数组。

/* return the gcd of x1, x2, ..., xm */
int multiple_gcd(int m, int *x) {
    size_t i;
    int g;

    if (m < 1)
        return 0;
    
    g = x[0];

    for (i = 1; i < m; ++i) {
        g = gcd(g, x[i]);

        /* optimization, since for random x(i), g==1 60% of the time: */
        if (g == 1)
            return 1;
    }

    return g;
}

对应的 python 实现如下。

# returns gcd of x and y
def gcd(x, y):
    if (x < 0):
        x = -x
    
    if (y < 0):
        y = -y

    if (x + y == 0):
        exit(1)

    g = y

    while (x > 0):
        g = x
        x = y % x
        y = g
    
    return g

这个算法可以推广为返回由 m 个数组成的 gcd 数组。

# return the gcd of x1, x2, ..., xm
def multiple_gcd(m, x):
    if (m < 1):
        return 0
    
    g = x[0]

    for i in range(m):
        g = gcd(g, x[i])

        # optimization, since for random x(i), g==1 60% of the time:
        if (g == 1):
            return 1

    return g

2.4 殴几里得算法

求最大公因子 (GCD) 的算法。

2.5 求模逆元

记得逆元 (inverse) 吗？4 的乘法逆元是 1/4，因为 $4 \times 1 / 4 = 1$ 。在模运算的领域，这个问题更复杂：
$4 \times x \equiv 1 (mod \ 7)$

这个方程等价于寻找一组 $x$ 和 $k$ ，以使：
$4x = 7k + 1$

这里 $x$ 和 $k$ 均为整数。

更为一般的问题是寻找一个 $x$ ，使得：
$1 = (a \times x) mod \ n$

也可写作：
$a^{-1} \equiv x (mod \ n)$

解决模的逆元问题很困难。有时候有一个方案，有时候没有。例如，5 模 14 的逆元是 3： $5 \times 3 = 15 \equiv 1 (mod \ 14)$ 。2 模 14 却没有逆元。

一般而论，如果 $a$ 和 $n$ 是互素的，那么 $a^{-1} \equiv x (mod \ n)$ 有唯一解；如果 $a$ 和 $n$ 不是互素的，那么 $a^{-1} \equiv x (mod \ n)$ 没有解。如果 $n$ 是素数，那么从 $1 \thicksim n-1$ 的每一个数与 $n$ 都是互素的，且在这个范围内恰好有一个逆元。

一切顺利。现在，怎样找出 $a$ 模 $n$ 的逆元呢？有一系列的方法。殴几里得算法也能计算 $a$ 模 $n$ 的逆元，有时候这叫做扩展殴几里得算法 (extended Euclidean algorithm)。

下面是用 C++ 写的算法：

#include <stdlib.h>

#include <iostream>

using namespace std;

#define isEven(x)       ((x & 0x01) == 0)
#define isOdd(x)        (x & 0x01)
#define swap(x,y)       (x ^= y, y ^= x, x ^= y)

void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3) {
    // warning: u and v will be swapped if u < v
    int k, t1, t2, t3;

    if (*u < *v) swap(*u, *v);

    for (k = 0; isEven(*u) && isEven(*v); ++k) {
        *u >>= 1; *v >>= 1;
    }

    *u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u - 1; t3 = *v;
    
    do {
        do {
            if (isEven(*u3)) {
                if (isOdd(*u1) || isOdd(*u2)) {
                    *u1 += *v; *u2 += *u;
                }

                *u1 >>= 1; *u2 >>= 1; *u3 >>= 1;
            }

            if (isEven(t3) || *u3 < t3) {
                swap(*u1, t1); swap(*u2, t2); swap(*u3, t3);
            }
        } while (isEven(*u3));
        
        while (*u1 < t1 || *u2 < t2) {
            *u1 += *v; *u2 += *u;
        }

        *u1 -= t1; *u2 -= t2; *u3 -= t3;
    } while (t3 > 0);
    
    while (*u1 >= *v && *u2 >= *u) {
        *u1 -= *v; *u2 -= *u;
    }
    
    *u1 <<= k; *u2 <<= k; *u3 <<= k;
}

int main(int argc, char **argv) {
    int a, b, gcd;

    if (argc < 3) {
        std::cerr << "Usage: xeuclid u v" << std::endl;
        
        return -1;
    }

    int u = atoi(argv[1]);
    int v = atoi(argv[2]);

    if (u <= 0 || v <= 0) {
        std::cerr << "Arguments must be positive!" << std::endl;

        return -2;
    }

    // warning: u and v will be swapped if u < v
    ExtBinEuclid(&u, &v, &a, &b, &gcd);

    std::cout << a << " * " << u << " + (-"
            << b << ") * " << v << " = " << gcd << std::endl;

    if (gcd == 1)
        std::cout << "the inverse of " << v << " mod " << u << " is: " << u - b << std::endl;
    
    return 0;
}

此算法通过迭代运算来实现，对于大的整数，其运行可能较慢。Knuth 指出这个算法完成的除法的平均数目是
$0.843 \times log_2(n) + 1.47$

2.6 求系数

殴几里得算法可用于解决下面的一类问题：给出一个包含 $m$ 个变量 $x_1, x_2, ..., x_m$ 的数组，求一个包含 $m$ 个系数 $u_1, u_2, ..., u_m$ 的数组，使得
$u_1 \times x_1 + ... + u_m \times x_m = 1$

2.7 费马小定理

如果 $m$ 是一个素数，且 $a$ 不是 $m$ 的倍数，那么，根据费马小定理 (Fermat's little theorem) 有：
$a^{m-1} \equiv 1 \ (mod \ m)$

2.8 欧拉函数

还有另一种方法计算模 $n$ 的逆元，但不是在任何情况下都能使用。模 $n$ 的余数化简集 (reduced set of residues) 是余数完全集合的子集，与 $n$ 互素。例如，模 12 的余数化简集是 ${1, 5, 7, 11}$ 。如果 $n$ 是素数，那么模 $n$ 的余数化简集是从 $1 \thicksim n-1$ 的所有整数集合。对 $n$ 不等于 1 的数，数 0 不是余数化简集的元素。

欧拉函数 (Euler totient fuction)，也称为欧拉 $\varphi$ 函数，写作 $\phi(n)$ ，它表示模 $n$ 的余数化简集中元素的数目。换句话说， $\phi(n)$ 表示与 $n$ 互素的小于 $n$ 的正整数的数目 ( $n>1$ )。

如果 $n$ 是素数，那么 $\phi(n)=n-1$ ；如果 $n=pq$ ，且 $p$ 和 $q$ 互素，那么 $\phi(n)=(p-1)(q-1)$ 。这些数字在随后谈到的公开密钥系统中将再次出现，它们都来自于此。

根据费马小定理的欧拉推广，如果 $gcd(a,n)=1$ ，那么
$a^{\phi(n)} \ mod \ n = 1$

现在计算 $a$ 模 $n$ 很容易：
$x = a^{\phi(n)-1} \ mod \ n$

证明：
$(a \times x)mod \ n = (a \times a^{\phi(n)-1})mod \ n = a^{\phi(n)} \ mod \ n = 1$

例如，求 5 模 7 的逆元是多少？既然 7 是素数， $\phi(7)=7-1=6$ 。因此，5 模 7 的逆元是
$5^{6-1} mod \ 7 = 5^5 mod \ 7 = 3$

计算逆元的两种方法都推广到在一般性的问题中求解 $x$ (如果 $gcd(a,n)=1$ )：
$(a \times x) mod \ n = b$

用欧拉推广公式，解：
$x = (b \times a^{\phi(n)-1}) mod \ n$

用殴几里得算法，解：
$x = (b \times (a^{-1} mod \ n)) mod \ n$

通常，殴几里得算法在计算逆元方面比欧拉推广更快，特别是对于 500 位范围内的数。如果 $gcd(a, n) \neq 1$ ，并非一切都没用了。这种一般情况而言， $(a \times x) \ mod \ n = b$ ，可能有多个解或无解。

2.9 中国剩余定理

如果已知 $n$ 的素因子，那么就能利用中国剩余定理 (Chinese remainder theorem) 求解整个方程组，这个定理的最初形式是由 1 世纪的中国数学家孙子发现的。

一般而言，如果 $n$ 的素因子可分解为 $n = p_1 \times p_2 \times ... \times p_t$ ，那么方程组
$(x \ mod \ p_i) = a_i \qquad i=1,2,...,t$

有唯一解，这里 $x<n$ (注意，有些素数可能不止一次地出现。例如，p_1 可能等于 p_2)。换句话说，一个数 (小于一些素数之积) 被它的余数模这些素数唯一确定。

例如，取素数 3 和 5，取一个数 14，那么 $14 \ mod \ 3 = 2, \quad 14 \ mod \ 5 = 4$ 。则小于 $3 \times 5 = 15$ 且具有上述余数的数只有 14，即由这两个余数唯一地确定了数 14。

如果对任意 $a<p$ 和 $b<q$ ( $p$ 和 $q$ 都是素数)，那么，当 $x < p \times q$ 时，存在一个唯一的 $x$ ，使得
$x \equiv a (mod \ p) 且 x \equiv b (mod \ q)$

为求出这个 $x$ ，首先用殴几里得算法找到 $u$ ，使得
$u \times q \equiv 1 (mod \ p)$

然后计算：
$x = (((a - b) \times u) mod \ p) \times q + b$

用 C 语言所写的中国剩余定理如下：

/* r is the number of elements in arrays m and u;
m is the array of (pairwise relatively prime) moduli
u is the array of coefficients
return value is n such than n == u[k]%m[k] (k=0..r-1) and
    n < m[0]*m[1]*...*m[r-1]
*/

/* totient() is left as an exercise to the reader. */

int chinese_remainder(size_t r, int *m, int *u) {
    size_t i;
    int modulus;
    int n;
    modulus = 1;
    for (i = 0; i < r; ++i)
        modulus *= m[i];
    n = 0;
    for (i = 0; i < r; ++i) {
        n += u[i] * modexp(modulus / m[i], totient(m[i]), m[i]);
        n %= modulus;
    }
    
    return n;
}

中国剩余定理的一个推论可用于求出一个类似问题的解：如果 $p$ 和 $q$ 都是素数，且 $p < q$ ，那么存在一个唯一的 $x < p \times q$ ，使得
$a \equiv x (mod \ p) 且 b \equiv x (mod \ q)$

如果 $a \geq b \ mod \ p$ ，那么
$x = (((a - (b \ mod \ p)) \times u) mod \ p) \times q + b$

如果 $a < b \ mod \ p$ ，那么
$x = (((a + p - (b \ mod \ p)) \times u) mod \ p) \times q + b$

2.10 二次剩余

如果 $p$ 是素数，且 $a < p$ ，如果
$x^{2} \equiv a \ (mod \ p) \qquad 对某些 x 成立$

那么称 $a$ 是对模 $p$ 的二次剩余 (quadratic residue)。

不是所有的 $a$ 的值都满足这个特性。如果 $a$ 是对模 $n$ 的一个二次剩余，那么它必定是对模 $n$ 的所有素因子的二次剩余。例如，如果 $p = 7$ ，那么二次剩余是 1、2 和 4：
$1^2 = 1 \equiv 1(mod \ 7)$

$2^2 = 4 \equiv 4(mod \ 7)$

$3^2 = 9 \equiv 2(mod \ 7)$

$4^2 = 16 \equiv 2(mod \ 7)$

$5^2 = 25 \equiv 4(mod \ 7)$

$6^2 = 36 \equiv 1(mod \ 7)$

注意，每一个二次剩余在上面都出现了两次。

没有 $x$ 值可满足下列这些方程的任意一个：
$x^2 = 3 (mod \ 7)$

$x^2 = 5 (mod \ 7)$

$x^2 = 6 (mod \ 7)$

对模 7 的二次非剩余 (quadratic nonresidue) 是 3、5 和 6。

很容易证明，当 $p$ 为奇数时，对模 $p$ 的二次剩余数目恰好是 $(p-1)/2$ ，且与其二次非剩余的数目相同。而且，如果 $x^2$ 等于二次剩余模 $p$ ，那么 $x^2$ 恰好有两个平方根：其中一个在 $1 \thicksim (p-1)/2$ 之间；另一个在 $(p+1)/2 \thicksim (p-1)$ 之间。这两个平方根中的一个也是模 $p$ 的二次剩余，称为主平方根 (pricipal square root)。

如果 $n$ 是两个素数 $p$ 和 $q$ 之积，那么模 $n$ 恰好有 $(p-1)(q-1)/4$ 个二次剩余。模 $n$ 的一个二次剩余是模 $n$ 的一个完全平方。这是因为要成为模 $n$ 的平方，其余数必须有模 $p$ 的平方和模 $q$ 的平方。例如，模 35 有 11 个二次剩余：1、4、9、11、14、15、16、21、25、29、30。每一个二次剩余恰好有 4 个平方根。