Miller-Rabin 算法与 RSA 算法
Miller-Rabin算法是目前主流的基于概率的素数测试算法）RSA加密算法是计算机世界中最重要的一种非对称加密算法。本文从SICP 习题1.28出发，主要介绍两种算法的数学原理以及Scheme的简单实现，代码保存在 Gist。
1. Miller-Rabin 素数检验算法
一个数是素数（也叫质数），当且仅当它的约数只有1和它本身。为了检验 n 是否为素数，最直接的方法就是逐一检验 [2,n−1] 能否整除 n：
(define (prime-iter n i) (cond ((= i n) #t) ((= (remainder n i) 0) #f) (else (prime-iter n (+ i 1))))) (define (prime? n) (prime-iter n 2))
但是当数字较大的时候，这一算法的效率非常低下。于是就有了基于费马小定理的概率算法：
费马小定理：如果 p 是素数，a 是小于 p 的正整数，那么：ap−1 mod p=1。
所有素数都满足费马小定理的条件，因此从小于p的整数中随机抽取a，只要有一个a不满足上述条件则p为合数，抽取次数越多，全部通过费马小定理之后我们准确判定p为质数的概率越高：
(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (cond ((= times 0) #t) ((fermat-test n) (fast-prime? n (- times 1))) (else #f)))
然而费马小定理只是质数的必要而非充分条件，有些数字每一个比它小的整数都能通过费马测试，但却是合数，这种数字称为卡迈克尔数（Carmichael numbers）。最小的卡迈克尔数是 561，[1,1017] 之间有585,355 个卡迈克尔数，这使得费马测试变得不可靠，于是就有了Miller-Rabin算法。
Miller-Rabin算法基于如下定理：
若 p 是素数，a 是小于 p 的正整数，且 a2 mod p=1，那么要么 a=1，要么 a=p−1。
证明： a2 mod p=1，则说明 a2−1=(a+1)(a−1) 能够整除 p，由于 p 是素数，能够整除它的只有 1 和 p 本身，因此 a 的解只能是 a=1 或 a=p−1。
基于上面的定理我们来检验最小的卡迈克尔数 561：首先 2560 mod 561=1，通过了费马测试；进而考虑到 2560=(2280)2，根据规律 [1]：
结合上面的定理，那么 2280 mod 561 也应该是 1 或 560，经验证 2280 mod 561=1；继续我们发现 2140 mod 561=67，于是马上可以得到 672 mod 561=1，违反了上面的定理，由此可以判断 561 不是质数。
在Miller-Rabin算法中，我们将 p−1 （一定是偶数）不断提取因子2，最终分解为：2sd（其中 d 是奇数），对于所有的 r∈[0,s−1]，只要存在 r 使得 ad mod p=1 或 a2rd mod p=p−1，即可推断 p 有可能为素数；反之则一定为合数。
有趣的是在上面Scheme实现的费马测试算法中，计算 an−1 所用的正是类似将指数不断除2的递归方法，因此我们只需要对(expmod base exp n)方法中的递归调用(remainder (square (expmod base (/ exp 2) m)) m)（恰好是规律 [1]）进行检验：
;; miller-rabin algorithm (define (remainder-square a n) (cond ((or (= a 1) (= a (- n 1))) 1) ((= (remainder (square a) n) 1) 0) (else (remainder (square a) n)))) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder-square (expmod base (/ exp 2) m) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (mr-test n a) (= (expmod a (- n 1) n) 1)) (define (miller-rabin n t) (cond ((= t 0) #t) ((mr-test n (+ 2 (random (- n 2)))) (miller-rabin n (- t 1))) (else #f))) (miller-rabin 561 20) ;;=> #f
2. RSA 加密算法
RSA 算法被评为真正统治世界的十大算法之一，虽然并非经过严格的权威性论证与投票表决，但大部分人应该不会对此存在异议。RSA 算法的数学原理简而言之就是：利用对大数进行因数分解的困难，实现以公开密钥对明文进行加密，而只能以私有密钥进行解密。具体的数学推导过程可以参考文章最后的链接深入了解，这里我们需要了解一个新的数学定理：欧拉函数。
对整数 n，欧拉函数 φ(n) 是小于或等于 n 的正整数中与 n 互质的数的数量。特别的，如果 n 是素数，φ(n)=n−1。
下面我们来看Scheme简单实现的 RSA 算法及加密解密过程的实例：
;; 1. 随意选择两个大的质数p和q，p不等于q (define p 61) (define q 53) ;; 计算N=pq (define N (* p q)) ;; 2. 根据欧拉函数，求得r=(p-1)(q-1) (define r (* (- p 1) (- q 1))) ;; 3. 选择一个小于r的整数e，e与r互质 (define e 17) ;; 求得e关于r的模反元素 (define d (modular-multiplicative-inverse e r)) ;; 模反元素计算过程 (define (dividable? x y) (= (remainder x y) 0)) (define (mmii a m k) (if (dividable? (+ (* k m) 1) a) (/ (+ (* k m) 1) a) (mmii a m (+ k 1)))) (define (modular-multiplicative-inverse a m) (mmii a m 1)) ;; RSA 加密需要公钥(N, e) ;; RSA 解密需要私钥(N, d) (define (rsa m KNN Ked) (expmod m Ked KNN)) ;; 4. 利用公钥对明文m进行加密 (define m 1990) (display "PlaintText: ") (display m) (newline) (display "Encrypted: ") (define cipher (rsa m N e)) (display cipher) (newline) ;;=> PlaintText: 1990 ;;=> Encrypted: 1806 ;; 5. 根据私钥对密文进行解密 (display "Decrypted: ") (display (rsa cipher N d)) ;;=> Decrypted: 1990
想要根据公钥 (N,e) 推算出私钥 (N,d) ，需要对 N 进行因数分解，推导出原始的 p 和 q。上例中用到的 p=61,q=53 很容易就可以从 N=3233 推导出来，然而当 N 非常大（1024或2048位二进制）时，对其进行因数分解在当下看来几乎是不可能实现的。这也是密码学中的一个基本原理，如果解密所需的成本高于该信息的价值，那么这种加密就被认为是安全的。