Skip to content

Instantly share code, notes, and snippets.

@rainyear
Last active March 12, 2021 13:20
Show Gist options
  • Save rainyear/15d23b044861d211ce52 to your computer and use it in GitHub Desktop.
Save rainyear/15d23b044861d211ce52 to your computer and use it in GitHub Desktop.
Miller-Rabin & RSA in Scheme.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; 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
;; 求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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment