计算机程序的构造和解释(SICP) Assignment 5 RSA encryption

这次回顾Assignment 5 RSA encryption。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

作业地址：

https://mitpress.mit.edu/sites/default/files/sicp/psets/index.html

2. Exercises

Exercise 1

没有区别。

Exercise 2

略过。

Exercise 3

先加密更好；因为如果先sign，相当于只加密了一次，但是先加密再sign相当于加密了多次。

Exercise 4

代码：

(define (RSA-encrypt intlist key1)
    (map (lambda (int) (RSA-transform int key1))
         intlist))

(define (RSA-decrypt intlist key1)
    (map (lambda (int) (RSA-transform int key1))
         intlist))

3. Programming assignment

Exercise 1

计算公式：

encrypt:

$$\begin{aligned} x_0'&= \text{RSA-transform}(x_0\bmod n, \text{private key}) \\ x_i' &= \text{RSA-transform}((x_{i}-x_{i-1}')\bmod n, \text{private key}) \end{aligned}$$

decrypt:

$$\begin{aligned} x_0'&= \text{RSA-transform}(x_0, \text{public key}) \bmod n \\ x_i' &= (\text{RSA-transform}(x_i, \text{private key}) + x_{i}')\bmod n \end{aligned}$$

代码：

(define (RSA-unconvert-list intlist key)
  (let ((n (key-modulus key)))
    (define (unconvert l sum)
      (if (null? l)
          '()
          (let ((x (modulo (+ (RSA-transform (car l) key)
                           sum) n)))
            (cons x (unconvert (cdr l) (car l))))))
    (unconvert intlist 0)))
    
(load "rsa.scm")

(define result1 (rsa-encrypt "This is a test message." test-public-key1))
(display result1)
(RSA-decrypt result1 test-private-key1)

(define result2 (rsa-encrypt "This is a another test message." test-public-key2))
(display result2)
(RSA-decrypt result2 test-private-key2)

运行结果：

1 ]=> (display result1)(209185193 793765302 124842465 169313344 117194397 237972864)
;Unspecified return value

1 ]=> (RSA-decrypt result1 test-private-key1)
;Value 13: "This is a test message. "

1 ]=> (define result2 (rsa-encrypt "This is a another test message." test-public-key2))
;Value: result2

1 ]=> (display result2)(102436216 322617498 188506539 149103786 325444552 190854590 397182031 313797695)
;Unspecified return value

1 ]=> (RSA-decrypt result2 test-private-key2)
;Value 14: "This is a another test message. "

Exercise 2

代码：

; e2
(define signed-message cons)
(define message car)
(define signature cdr)

(define (encrypt-and-sign message sender-private-key recip-public-key)
  (let ((encry-message (RSA-encrypt message recip-public-key)))
    (let ((unencry-signature (list (compress encry-message))))
      (let ((encry-signature (car (RSA-convert-list unencry-signature sender-private-key))))
           (signed-message message encry-signature)))))

(load "rsa.scm")

(define result2
    (encrypt-and-sign "Test message from user 1 to user 2"
                      test-private-key1
                      test-public-key2))

(message result2)
(signature result2)

实验结果：

1 ]=> (message result2)
;Value 13: "Test message from user 1 to user 2"

1 ]=> (signature result2)
;Value: 15378444

Exercise 3

流程：

$$\text{encry-message} \overset{\text{rec-private-key}}{\to} \text{decry-message} \\ \text{encry-message}\overset{\text{hash}}{\to} \text{unencry-signature} \\ \text{encry-signature}\overset{\text{send-public-key}}{\to}\text{unencry-signature}$$

遍历pulic-key，来找到对应的发送者。

代码：

(load "rsa.scm")

(define message (intlist->string received-mystery-message))
(display message)

(define unencry-message (RSA-decrypt received-mystery-message newt-gingrich-private-key))
(display unencry-message)

(define encry-message (rsa-encrypt unencry-message newt-gingrich-public-key))

(define unencrypted-signature (compress encry-message))
(display unencrypted-signature)

(define (encry-to-unencry encrypted-signature public-key)
    (car (RSA-convert-list (list encrypted-signature) public-key)))

(define public-keys (list 
                   (list 'bill-clinton bill-clinton-public-key)
                   (list 'al-gore al-gore-public-key )
                   (list 'bob-dole bob-dole-public-key )
                   (list 'ross-perot ross-perot-public-key )
                   (list 'hillary-clinton hillary-clinton-public-key )
                   (list 'tipper-gore tipper-gore-public-key )
                   (list 'chuck-vest chuck-vest-public-key)
                   (list 'rupert-murdoch rupert-murdoch-public-key)
                   (list 'newt-gingrich newt-gingrich-public-key)))

(define (get-res unencrypted-signature encrypted-signature public-keys)
    (cond ((null? public-keys) "No result!")
          ((= (encry-to-unencry encrypted-signature (cadar public-keys)) unencrypted-signature)
           (caar public-keys))
          (else (get-res unencrypted-signature encrypted-signature (cdr public-keys)))))

(get-res unencrypted-signature received-mystery-signature public-keys)

实验结果：

1 ]=> (get-res unencrypted-signature received-mystery-signature public-keys)
;Value: rupert-murdoch

Exercise 4

为了求解：

$$\begin{aligned} ax+by&=1\\ \end{aligned}$$

假设：

$$a=bq+r$$

那么：

$$\begin{aligned} (bq+r)x + by& =1\\ b(qx+y) + rx&= 1 \end{aligned}$$

记

$$\begin{aligned} \bar x &=qx+y\\ \bar y &=x \end{aligned}$$

那么

$$\begin{aligned} x&=\bar y\\ y&= \bar x - qx\\ &=\bar x - q\bar y \end{aligned}$$

此时新方程为

$$b\bar x + r\bar y= 1$$

注意到

$$0\le | r|<|b|$$

所以经过有限步后一定有$r=0$，此时

$$\begin{aligned} \bar x &= 1/ b=\pm 1 \\ \bar y &\in\mathbb Z \\ \end{aligned}$$

特别的，这里取

$$(\bar x ,\bar y) = (1, 0)$$

代码：

(define (solve-ax+by=1 a b)
  (if (= b 0)
      (cons 1 0)
      (let ((q (quotient a b))
            (r (remainder a b)))
           (let ((x1y1 (solve-ax+by=1 b r)))
                (cons (cdr x1y1) (- (car x1y1) (* q (cdr x1y1))))))))
                
(load "rsa.scm")

(define a 233987973)
(define b 41111687)

(define (test a b)
    (let ((xy (solve-ax+by=1 a b)))
          (let ((x (car xy))
                (y (cdr xy)))
                (if (= (+ (* a x) (* b y)) 1)
                    (display "Pass test!")
                    (display "Fail test!")))))

(test a b)

(solve-ax+by=1 a b)

; test
(define key-pair (generate-RSA-key-pair))
(define public-key (key-pair-public key-pair))
(define private-key (key-pair-private key-pair))

(define result (rsa-encrypt "This is a test message." public-key))
(RSA-decrypt result private-key)

实验结果：

1 ]=> (test a b)Pass test!
;Unspecified return value

1 ]=> (solve-ax+by=1 a b)
;Value 13: (-11827825 . 67318298)

1 ]=> ; test
(define key-pair (generate-RSA-key-pair))
;Value: key-pair

1 ]=> (define public-key (key-pair-public key-pair))
;Value: public-key

1 ]=> (define private-key (key-pair-private key-pair))
;Value: private-key

1 ]=> (define result (rsa-encrypt "This is a test message." public-key))
;Value: result

1 ]=> (RSA-decrypt result private-key)
;Value 14: "This is a test message. "

Exercise 5

要通过公钥$(n,e)$求出私钥$(n,d)$，只要求出$e$，满足下式即可：

$$de=1\bmod m$$

即

$$de+my = 1$$

其中

$$\begin{aligned} n&=pq\\ m&=(p-1)(q-1) \end{aligned}$$

所以一个可行的算法是枚举小于$n$的素数，找到整除$n$的素数$p$，然后求出

$$q= n /p$$

由此计算出$m$，最后通过Exercise 5的算法求出$e$即可，完整的代码如下：

(load "rsa.scm")

; n, e
; n = pq, m = (p - 1) * (q - 1)
; de = 1 mod m
; n, d
(define (crack-rsa public-key)
    (let ((n (key-modulus public-key))
          (e (key-exponent public-key)))
         (let ((p (smallest-divisor n)))
              (let ((q (/ n p)))
                   (let ((m (* (- p 1) (- q 1))))
                        (let ((xy (solve-ax+by=1 m e)))
                            (make-key-pair n (modulo (cdr xy) m))))))))

(define (key-eq? k1 k2)
    (and (eq? (car k1) (car k2))
         (eq? (cdr k1) (cdr k2))))

(define (test-crack public-key private-key)
    (let ((crack-private-key (crack-rsa public-key)))
         (cond ((key-eq? crack-private-key private-key)
                (newline)
                (display "Crack succeed"))
               (else (newline) (display "Crack fail")))))

(test-crack test-public-key1 test-private-key1)
(test-crack test-public-key2 test-private-key2)

实验结果：

1 ]=> (test-crack test-public-key1 test-private-key1)
Crack succeed
;Unspecified return value

1 ]=> (test-crack test-public-key2 test-private-key2)
Crack succeed
;Unspecified return value

Exercise 6

代码：

(load "rsa.scm")

(define fake-message "fake message")
(define bill-clinton-private-key (crack-rsa bill-clinton-public-key))
(define al-gore-private-key (crack-rsa al-gore-public-key))

(define encrypt-and-sign-msg (encrypt-and-sign fake-message bill-clinton-private-key al-gore-public-key))
(display encrypt-and-sign-msg)

; message
(define encry-message (rsa-encrypt fake-message al-gore-public-key))
(define decry-message (rsa-decrypt encry-message al-gore-private-key))

(display encry-message)
(display decry-message)

; signature
(define unencry-signature (compress encry-message))
(define unencry-signature-v1 (car (rsa-convert-list (list (cdr encrypt-and-sign-msg)) bill-clinton-public-key)))

(display unencry-signature)
(display unencry-signature-v1)

实验结果：

1 ]=> (display encrypt-and-sign-msg)(fake message . 219078547)
;Unspecified return value

1 ]=> ; message
(define encry-message (rsa-encrypt fake-message al-gore-public-key))
;Value: encry-message

1 ]=> (define decry-message (rsa-decrypt encry-message al-gore-private-key))
;Value: decry-message

1 ]=> (display encry-message)(314791012 219982518 198773833)
;Unspecified return value

1 ]=> (display decry-message)fake message
;Unspecified return value

1 ]=> ; signature
(define unencry-signature (compress encry-message))
;Value: unencry-signature

1 ]=> (define unencry-signature-v1 (car (rsa-convert-list (list (cdr encrypt-and-sign-msg)) bill-clinton-public-key)))
;Value: unencry-signature-v1

1 ]=> (display unencry-signature)196676451
;Unspecified return value

1 ]=> (display unencry-signature-v1)196676451
;Unspecified return value

Exercise 7

同6，略过。

Exercise 8

参考资料：

https://zh.wikipedia.org/wiki/%E8%B3%AA%E6%95%B8%E5%88%97%E8%A1%A8

代码：

(load "rsa.scm")

(define n1 (*  2971 3529))
(define n2 780450379)
(define n3 (* 39916801 479001599))

(display n1)
(display n2)
(display n3)

(timed smallest-divisor n1)

(timed smallest-divisor n2)

(timed smallest-divisor n3)

指数时间复杂度：

1 ]=> (display n1)10484659
;Unspecified return value

1 ]=> (display n2)780450379
;Unspecified return value

1 ]=> (display n3)19120211505964799
;Unspecified return value

1 ]=> (timed smallest-divisor n1)(time: 0.)
;Value: 2971

1 ]=> (timed smallest-divisor n2)(time: 1.0000000000000002e-2)
;Value: 25057

1 ]=> (timed smallest-divisor n3)(time: 17.86)
;Value: 39916801