这一章是第三部分密码算法的第一章:数学背景,终于看完了这最难的一章,之所以说难,是因为都是些数学理论,而我的数学基础是薄弱的,因此只吸收了大概60%。也可以了,有个印象就好,以后不懂再查。

概念

  • 信息论
  • 信息量(amount of information)
    假设所有消息是等可能的,对消息中所有可能的值进行编码所需要的最少位数。例如数据库中有关“一周中的一天”这一字段包含不超过3位的信息。
  • 熵(entropy):终于知道熵是什么了
    形式化地,一条消息M的信息量可通过它的熵来度量,表示为H(M)。一条表示性别消息的熵是1位;一条表示一周天数的熵稍少于3位。通常,一条消息的熵是log2n,其中n是消息所有可能的值。此处假设每一个值是等可能的。

  • 一条消息的熵也表示了它的不确定性(uncertainty),即消息被加密成密文时,为了获取明文,需要解密的明文的位数。例如,如果密文“QHP*5M”要么是“男”,要么是“女”,那么此消息的不确定性是1.密码分析者为了恢复此消息,仅需选择1位。

  • 语言信息率(rate of language)

    1. r = H(M)/N
    2. 其中,N是消息的长度。
    3. 在N相当大时,标准英语的语言信息率(r值)在1.0位/字母与1.5位/字母之间。Shanon指出信息率与文本的长度有关。
  • 语言绝对信息率(absolute rate)
    1. 假定每一个字符串是等可能的,对每一个字母而言可被编码的最大位数。如果在一种语言中有L个字母,其绝对信息率是
    2. R = log2L
    3. 这就是单个字母的最大熵。英语的实际信息率大大低于绝对信息率,因为自然语言具有高冗余度。
  • 冗余度(redundancy):D = R - r
  • 密码系统的安全性

  • 完全保密(perfect secrecy)
    Shannon从理论上证明,仅当可能的密钥数目至少与可能的消息数目一样多时,它(完全保密)才是有可能的。换句话说,密钥必须至少与消息本身一样长,并且不重复使用。简而言之,仅有一次一密乱码本的密码系统才能获得完全保密。

  • 压缩可以降低消息的冗余度

  • 密钥空间大小K

    1. H(K) = log2K
    2. 密码系统的熵由此来衡量,64位密钥的密码系统的熵是64,同样,56位密钥密码系统的熵是56。一般来说,密码系统的熵越大,破译它就越困难。
  • 唯一解距离(unidty distance):U
    1. 对一个长度为n的消息而言,将一个密文消息解密为同一语言中某个有意义的明文,不同密钥的数目由下式给出:
    2. 2^(H(k)-nD) - 1 (H(K)是密钥空间大小,D是冗余度,n是消息长度)
    3. Shannon定义唯一解距离U(也称为唯一解点)为:使得对应明文的实际信息(熵)与加密密钥的熵之和等于所用的密文位数的渐进密文量。
    4. U = H(K)/D
    5. 只能给出可能的结果,不能给出肯定预测
  • 可变密钥长度的ASCII码文本加密算法的唯一解距离
密钥长度(位) 唯一解距离(字符)
40 5.9
56 8.2
64 9.4
80 11.8
128 18.8
256 37.6
  • 理想保密(ideal secrecy)

    1. 唯一解距离不是对密码分析需要多少密文的度量,而是对存在唯一合理的密码分析所需要的密文数量的指标。
    2. Shannon把唯一解距离为无穷大(冗余度接近于0时)的密码系统定义为理想保密的。
    3. 一个完全保密的密码系统必须是一个理想保密的密码系统
    4. 一个理想保密的密码系统不一定是一个完全保密的密码系统
    5. 如果一个密码系统具有理想保密性,即使成功的密码分析者也不能确定解的明文是否是真正的明文
  • 信息论的运用
    1. 密码分析者很少沿这个方向工作
    2. 唯一解距离可以保证当其太小时,密码系统是不安全的,但并不能保证当其较大时,密码系统就是安全的。
    3. 不幸的是,大多数有关信息论在密码分析上的应用文献仍然是保密的,包括Alan Turing 1940年的最初成果 -- 所以图灵的最初成果是?
  • 混乱(confusion)
    1. 扩散一起,为隐蔽明文消息冗余度的基本技术
    2. 用于掩盖明文和密文之间的关系。这可以挫败通过研究密文以获取冗余度和统计模式的企图。
    3. 做到这点最容易的方法是通过代替
    4. 有代替也不能保证安全,德国的恩尼格码是一个复杂的代替算法,但在二战期间就被破译
  • 扩散(diffusion)
    1. 通过将明文冗余度分散到密文中使之分散开来。密码分析者寻求这些冗余度将会更难。
    2. 产生扩散最简单的方法是通过换位,也称为置换。
  • 复杂性理论
    复杂性理论提供了一种分析不同密码技术和算法的计算复杂性(computational complexity)的方法。它对密码算法和技术进行比较,然后确定它们的安全性。信息论告诉我们,所有的密码算法(除了一次一密乱码本)都能被破译。
  • 时间复杂性(time complexity)

  • 空间复杂性(space complexity)
  • 常数的(constant):O(1)
  • 线性的(linear):O(n)
  • 二次方的(quadratic)
  • 三次方的(cubic)
  • 多项式的(polynomial)
  • 多项式时间(polynomial-time)
  • 指数的(exponential): O(t^f(n))
  • 超多项式(superpdynomial)
    复杂性为O(c^f(n))的指数算法的子集,c是一个常数,f(n)是大于常数而小于线性的函数

  • 问题的复杂性

  • 图灵机(Turing machine)
    一种有无限读-写存储的有限状态机,一个实际的计算模型

  • 易处理的(intractable)

  • 难解的(hard)
  • P问题(Polynomial problems): 能用多项式时间解决的问题
  • NP问题(Non-Deterministic Polynomial Complete Problems):包括所有在非确定型图灵机上可以用多项式解决的问题。
  • 非确定型图灵机:标准图灵机的变型,它能进行猜测。此机器通过“幸运测试”或平行尝试猜测所有可能问题的解,然后在多项式时间内检查它的猜测。
  • NP问题与密码学的关系

    1. 许多对称算法和所有公开密钥算法能够用非确定性的多项式时间(算法)进行攻击。
    2. 如果已知密文C,密码分析者简单地猜测一个明文X和一个密钥K,然后再输入X和K的基础上,以多项式时间运行加密算法,然后检查结果是否等于C。
    3. NP类包括P类,因为任何在确定性图灵机上用多项式时间算法可解决的问题,在非确定性图灵机上用多项式时间算法也是可解决的,因为猜测阶段可以简单地省略。
  • P=NP(P!=NP)的含义
    1. 如果所有NP问题在确定性图灵机上用多项式时间(算法)是可解决的,那么P=NP。
    2. 一些NP问题看上去显然比另一些困难得多(如穷举攻击与加密明文的一个随机分组明文),但P!=NP还未被证明
    3. 在复杂性理论领域内进行研究的每一个人都猜想它们是不相等的。
  • NP完全(NP-complete)
    1. 更奇特的是,在NP中有些特殊的问题被证明与此类中的任何问题一样困难。Steven Cook证明了可满足性问题(给出一个命题的布尔公式,有对变量赋值,使公式为真的方法吗?)是NP完全(NP-complete)问题。
    2. 这意味着,如果可满足性问题在多项式时间内是可解决的,那么P=NP。相反,如果NP中的任何问题都能够被证明没有一个确定的多项式时间算法,此证明就将给出可满足性问题也没有一个确定的多项式时间算法。因此,可满足性问题在NP中是最难的问题。
    3. 旅行商问题
    4. 三方匹配问题
    5. 三方满足性问题
  • PSPACE
  • PSPACE完全(PSPACE complete)

    1. 如果它们中任何一个在NP中,那么PSPACE=NP
    2. 如果它们中任何一个在P中,那么PSPACE=P
  • EXPTIME问题:在指数时间内可以解决
  • EXPTEME完全(EXPTEME complete):在确定的多项式时间内是不可解的,即P!=EXPTIME得到证明。
  • 数论
  • 模运算:可交换、结合、分配,分解大数求模时可以用到
  • 余数(residue)
  • 同余(congruent):三元等号
  • 完全剩余集(complete set of residue):所以可能余数的集合,就是完全余数集??
  • 模变换(modular reduction)
  • 加法链(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&l) s = (s* t)%n;
        u>>=1;
        t = (t* t) %n;
    }
    return(s);
}
// 递归算法
unsigned long fast_exp(unsigned longx, 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);
    }
}
  • Montgomery方法
  • Barrett算法
  • 离散对数(discrete logarithm)
  • 素数:比1大,其因子只有1和其本身,没有其他数可以整除它
  • 最大公因子(greatest common divisor): gcd(a,n)=1即a与n互素
  • 互素(relatively prime)
  • 欧几里得算法(Euclid's algorithm)
// 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)
        ERROR;
    g = y;
    while (x > 0) {
        g = x;
        x = y % x;
        y = g;
    }
    return g;
}
// returns 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;
}
  • 逆元(inverse):4的乘法逆元是1/4,因为4 * 1/4 = 1
  • 求模逆元

    1. 在模运算领域的逆元 4 * x <三元等号> 1(mod 7)
    2. 等价于寻找一组x和k,使得: 4x = 7k + 1, x与k为整数,4--a;7--n;
    3. 一般地,寻找一个x,使得 1 = (a * x)mod n
    4. 若a与n互素,则以上问题有唯一解;如果a和n不是互素,则没有解。
    5. 如果n是素数,那么从1~n-1的每一个数与n都是互素的,且在这个范围内恰好有一个逆元
  • 扩展欧几里得算法(extended Euclidean algorithm)
#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(*3)) {
                if (isOdd(*u1) || isOdd(*u2)) {
                    *u1 += *v;
                    *u2 += *u;
                }
                *u1 >>= 1; *u2 >>= 1; *u3 >>= 1;
            }
            if (isEven(t3) || *u3 < t3) {
                swap(*u1,ti); 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;
}// 看不懂,先抄一遍。。。
main (int argc, char **argv) {
    int a, b, gcd;

    if (argc < 3) {
        cerr << "Usage: xeuclid u v" << endl;
        return -1;
    }
    int u = atoi(argv[1]);
    int v = atoi(argv[2]);
    if (u <= 0 || v <= 0) {
        cerr << "Arguments must be positive!" << endl;
        return -2;
    }
    // warning: u and v will be swapped if u < v
    ExtBinEuclid(&u, &v, &a, &b, &gcd);
    count << a << " * " << u << " + (-"
    << b << ") * " << v << " = " << gcd << endl;
    if (gcd == 1)
        cout << "the inverse of " << v << " mod " << u << " is: "
        << u - b << endl;
    return 0;
}
  • 求系数:欧几里得算法可用于解决下面的一类问题,给出一个包含m个变量x1,x2,...,xm的数组,求一个包含m个系数u1,u2,...,um的数组,使得 u1 * x1 + ... + um * xm = 1

  • 费尔马小定理(Fermat's little theorem)
    如果m是一个素数,且a不是m的倍数,那么,根据费尔马小定理有 a^(m-1) <三元等号> 1(mod m) 左部是模的逆元的意思不是次幂

  • Pierre de Fermat 1601-1665 法国数学家,译为“费尔马”

  • Leonhard Euler 1707-1783 瑞士数学家,译作“欧拉”
  • 余数化简集(reduced set of residues)是余数完全集合(是什么?)的子集,与n互素。
  • 欧拉函数(Euler totient function)

    1. 表示模n的余数化简集中元素的数目,【符号不会打,用f代替】f(n)表示与n互素的小于n的正整数的数目(n>1)
    2. 如果n是素数,那么f(n)=n-1;如果n=pq,且p和q互素,那么f(n)=(p-1)(q-1)
    3. 根据费尔马小定理的欧拉推广,如果gcd(a,n)=1,那么a^(f(n))mod n = 1,计算a模n很容易:x = a^(f(n)-1) mod n
    4. 例如,求5模7的逆元是多少?既然7是素数,f(7)=7-1=6。因此,5模7的逆元是5^(6-1)mod 7 = 5^5 mod 7 = 3
    5. 即:35 = 72 + 1 == 5x = 1mod(k*7) 其中x=3, k=2
    6. 计算逆元的两种方法(扩展欧几里得算法费尔马小定理的欧拉推广)都可以推广到一般性的问题中求解x(如果gcd(a,n)=1):
      a. (a*x)mod n = b
      b. 用欧拉推广公式,解: x = (b * a^(f(n)-1)) mod n
      c. 用欧几里得算法,解: x = (b * (a^(-1)mod n)) mod n
    7. 通常,欧几里得算法在计算逆元方面比欧拉推广得更快,特别是对于500位范围内的数。如果gcd(a,n)!=1,并非一切都没用,这种情况一般而言,(a * x)mod n = b,可能有多个解或无解。
  • 中国剩余定理(Chinese remainder theorem)
    1. 由1世纪的中国数学家孙子发现(联想到数学是发明还是发现的哲学问题?)
    2. 一般而言,如果n的素因子可分解为n=p1 * p2 * p3 * ... * pi,那么方程组(x mod pi) = ai, i = 1,2,...,t有唯一解,这里x<n(注意,有些素数可能不止出现一次,即p1可能等于p2)。
    3. 一个数(小于一些素数之积)被它的余数模这些素数唯一确定。
    4. 例:取素数3和5,取一个数14,那么14 mod 3 = 2, 14 mod 5 = 4. 则小于3*5=15且具有上述余数的数只有14,即由这两个余数唯一地确定了数14.
    5. 如果对于任意a<p和b<q(p和q都是素数),那么,当x<p*q时,存在一个唯一的x,使得:x<三元等号>a(mod p) 且x<三元等号>b(mod q)
    6. ....(太繁琐了掠过)
/* 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]); // totient 欧拉函数
        n %= modulus;
    }
    return n;
}
  • 二次剩余(quadratic residue)
    1. 如果p是素数,且a<p,如果x^2 <三元等号> a(mod p) 对某些x成立,那么称a是对模p的二次剩余
    2. 不是所以的a的值都满足这个特性。如果a是对模n的一个二次剩余,那么它必定是对模n的所有素因子的二次剩余。例如,如果p=7,那么二次剩余是1、2和4:
      a. 1^2 = 1 === 1(mod 7)
      b. 2^2 = 4 === 4(mod 7)
      c. 3^2 = 9 === 2(mod 7)
      d. 4^2 = 16 === 2(mod 7)
      e. 5^2 = 25 === 4(mod 7)
      f. 6^2 = 36 === 1(mod 7)
    3. 注意每一个二次剩余都在上面出现了两次。(加粗数字)
    4. 非二次剩余(quadratic nonresidue)
    5. 容易证明,当p为奇数时,对模p的二次剩余数目恰好是(p-1)/2,且与其二次非剩余的数目相同。而且,如果x^2等于二次剩余模p,那么x^2恰好有两个平方根:其中一个在1~(p-1)/2之间;另一个在(p+1)/2~(p-1)之间。这两个平方根的一个也是模p的二次剩余,成为主平方根(pricipal square root)
    6. 如果n是两个素数p和q之积,那么模n恰好有(p-1)(q-1)/4个二次剩余。模n的一个二次剩余是模n的一个完全平方。
  • 勒让德符号(Legendre symbol),L(a, p)
    1. 当a为任意整数且p是一个大于2的素数时,它等于0、1或-1
    2. L(a,p) = 0, a能被p整除
    3. L(a,p) = 1,a是二次剩余
    4. L(a,p) = -1,a是非二次剩余
  • 雅可比符号(Jacobi symbol),J(a,n)
    1. 是让勒让德符号的合数模的一般化表示
/* this algorithm computes the Jacobi symbol recursively */
int jacobi(int a, int b) {
    int g;
    assert(odd(b));
    if (a >= b) a %= b; // by Rule 4
    if (a == 0) return 0;
    if (a == 1) return 1;
    if (a < 0)
        return jacobi(-a,b);
    else
        return -jacobi(-a,b);
    if (a % 2 == 0) // a is even
        if (((b*b -1)/8) % 2 == 0)
            return +jacobi(a/2, b)
        else
            return -jacobi(a/2, b) 
        g - gcd(a,b);
    assert(odd(a)); // this is guaranteed by the (a % 2 == 0) test
    if (g == a) // a exactly divdes b
        return 0;
    else if (g != 1)
        return jacobi(g,b) * jacobi(a/g, b);
    else if (((a-1)*(b-1)/4) % 2 == 0)
        return +jacobi(b,a);
    else
        return -jacobi(b,a);
}
  • Blum整数(Blum integar):p和q是素数,且都与3模4同余,则n=p*q叫做Blum整数
  • 生成元(generator)---本原元(primitive):p是一个素数,g小于p,对于从0~p-1的每一个b,都存在某个a,使得g^a===b(mod p),那么g是模p的生成元,g是p的本原元。
  • 伽罗瓦域(Galosi field)中的计算:如果n是一个素数或一个大素数的幂,那么久存在数学家称之为有限域的东西,用GF(p)表示。
  • Evariste Galois,19世纪早期的法国数学家,在20岁死于一次决斗中。233333
  • 不可约(irreducible)--素数的代替词。
  • 有限域(finite field)
  • 因子分解
  • 数域筛选法(Number Field Sieve,NFS)
  • 二次筛选法(Quadratic Sieve,QS)
  • 椭圆曲线法(Elliptic Curve Method,ECM)
  • Pollard的蒙特卡洛算法(Pollard's Monte Carlo algorithm)--Alpha Go?
  • 连分式算法(continued fraction algorithm)
  • 试除法(trial division)
  • 模n的平方根:如果n是两个素数的乘积,那么计算模n的平方根在计算上等价于对n进行因子分解。
  • 素数的产生
    1. 512位的数中,素数超过10^151个,不会被用完
    2. 极其小的概率会有两人选到同样的素数(比中福利彩票头奖的同时电脑烧掉的概率还低)
    3. 不可能建立起素数数据库,10亿字节信息在1g设备上,512位的所有素数将超过Chandrasekhar限,导致进入黑洞
    4. 工业级素数测试
  • Solovag-Strassen 一种使用雅可比函数测试p是否为素数概率的基本测试算法(不祥究)
  • 证据(wimess)
  • Lehmann 同样是一直测试
  • Rabin-Miller 同上
  • 实际考虑
  • 强素数(strong prime):定义是什么?作者认为有必要采取
  • 有限域上的离散对数
  • 计算有限群中的离散对数

    1. 素数域的乘法群:GF(p)
    2. 特征为2的有限域上的乘法群:GF(2^n)
    3. 有限域F上的椭圆曲线群:EC(F)
  • 素数域上计算离散对数的方法
    1. 线性筛选法(linear sieve)
    2. 高斯整数法(Gaussian integer scheme)
    3. NFS
  • Coppersmith算法

问题

  • 博多机(BAUDOT)
  • 图灵在1940年的信息论最初成果是什么?这些秘密该如何得到?
  • 素因子是什么?