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 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:

decrypt:

(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

(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

(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

(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 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