Miller-Rabin 算法与 RSA 算法

jopen 4年前

Miller-Rabin算法是目前主流的基于概率的素数测试算法)RSA加密算法是计算机世界中最重要的一种非对称加密算法。本文从SICP 习题1.28出发,主要介绍两种算法的数学原理以及Scheme的简单实现,代码保存在 Gist

1. Miller-Rabin 素数检验算法

 一个数是素数(也叫质数),当且仅当它的约数只有1和它本身。为了检验 n 是否为素数,最直接的方法就是逐一检验 [2,n1] 能否整除 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 的正整数,那么:ap1 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=p1

证明: a2 mod p=1,则说明 a21=(a+1)(a1) 能够整除 p,由于 p 是素数,能够整除它的只有 1p 本身,因此 a 的解只能是 a=1a=p1

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

if,then, a mod p=k a2 mod p=k2 mod p

结合上面的定理,那么 2280 mod 561 也应该是 1560,经验证 2280 mod 561=1;继续我们发现 2140 mod 561=67,于是马上可以得到 672 mod 561=1,违反了上面的定理,由此可以判断 561 不是质数。

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

有趣的是在上面Scheme实现的费马测试算法中,计算 an1 所用的正是类似将指数不断除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)=n1

下面我们来看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 进行因数分解,推导出原始的 pq。上例中用到的 p=61,q=53 很容易就可以从 N=3233 推导出来,然而当 N 非常大(1024或2048位二进制)时,对其进行因数分解在当下看来几乎是不可能实现的。这也是密码学中的一个基本原理,如果解密所需的成本高于该信息的价值,那么这种加密就被认为是安全的。

参考

原文网址:http://blog.rainy.im/2015/08/27/miller-rabin-n-rsa/