Miller-Rabin & RSA in Scheme.

miller-rabin.scm

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Source codes of blog post:                             ;
; http://blog.rainy.im/2015/08/27/miller-rabin-rsa/      ;
; Scheme runtime: Calysto Scheme                         ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; math procedures
(define (square x) (* x x))
(define (even? x) (= (remainder x 2) 0))

;; helper procedures
(define (runtime) (current-time))

;; random procedure
(define R 1)
(define (seed i) (set! R i))

(define A 16807)
(define B 0)
(define M 2147483647)

(define (LCG)
  (begin
   (seed (remainder (+ (* A R) B) M))
      R))
(define (random n)
  (round (* (/ (LCG) (- M 1)) n) ))

;; set random SEED
(seed (round (current-time)))

;; 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)
  ; (newline)
  ; (display 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)))

;; test with prime and Carmichael numbers
;; (miller-rabin 1009 40) #t
;; (miller-rabin 561 40)  #f

rsa.scm

;; 求a关于m的模反元素
(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))

;; copyed from miller-rabin.scm
(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))))

;; RSA 加密需要公钥(N, e)
;; RSA 解密需要私钥(N, d)
(define (rsa m KNN Ked)
  (expmod m Ked KNN))

;; 随意选择两个大的质数p和q，p不等于q
(define p 61)
(define q 53)

;; 计算N=pq
(define N (* p q))

;; 根据欧拉函数，求得r=(p-1)(q-1)
(define r (* (- p 1) (- q 1)))

;; 选择一个小于r的整数e，e与r互质
(define e 17)

;; 求得e关于r的模反元素
(define d (modular-multiplicative-inverse e r))

;; 对明文m进行加密
(define m 1990)

(display "PlaintText: ")
(display m)
(newline)

(display "Encrypted: ")
(define cipher (rsa m N e))
(display cipher)
(newline)

(display "Decrypted: ")
(display (rsa cipher N d))