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$ 的正整数,那么:$a^{p-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, 10^17]$ 之间有$585,355$ 个卡迈克尔数,这使得费马测试变得不可靠,于是就有了Miller-Rabin算法。

Miller-Rabin算法基于如下定理:

若 $p$ 是素数,$a$ 是小于 $p$ 的正整数,且 $a^2\ mod\ p = 1$,那么要么 $a=1$,要么 $a=p-1$。

证明: $a^2\ mod\ p = 1$,则说明 $a^2 - 1 = (a+1)(a-1)$ 能够整除 $p$,由于 $p$ 是素数,能够整除它的只有 $1$ 和 $p$ 本身,因此 $a$ 的解只能是 $a=1$ 或 $a=p-1$。

基于上面的定理我们来检验最小的卡迈克尔数 $561$:首先 $2^{560}\ mod\ 561 = 1$,通过了费马测试;进而考虑到 $2^{560} = (2^{280})^2$,根据规律 $[1]$:

$$ \begin{align} if, &\ a\ mod\ p = k \\
then, &\ a^2\ mod\ p = k^2\ mod\ p
\end{align} $$

结合上面的定理,那么 $2^{280}\ mod\ 561$ 也应该是 $1$ 或 $560$,经验证 $2^{280}\ mod\ 561 = 1$;继续我们发现 $2^{140}\ mod\ 561 = 67$,于是马上可以得到 $67^2\ mod\ 561 = 1$,违反了上面的定理,由此可以判断 $561$ 不是质数。

在Miller-Rabin算法中,我们将 $p-1$ (一定是偶数)不断提取因子2,最终分解为:$2^sd$(其中 $d$ 是奇数),对于所有的 $r \in [0, s-1]$,只要存在 $r$ 使得 $a^d\ mod\ p = 1$ 或 $a^{2^rd}\ mod\ p = p-1$,即可推断 $p$ 有可能为素数;反之则一定为合数。

有趣的是在上面Scheme实现的费马测试算法中,计算 $a^{n-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$,欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数量。特别的,如果 $n$ 是素数,$\varphi (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位二进制)时,对其进行因数分解在当下看来几乎是不可能实现的。这也是密码学中的一个基本原理,如果解密所需的成本高于该信息的价值,那么这种加密就被认为是安全的。

参考

SICP, Scheme, 算法

- END -



侧栏导航