David Golombek
10:00 Tutorial
daveg@mit.edu

------------------------------------------------------------------------------

Lab Exercise 1:

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

------------------------------------------------------------------------------

Lab Exercise 2:

(define signed-message cons)
(define encrypted-part car)
(define signature-part cdr)

(define (encrypt-and-sign string priv-key pub-key)
  (let ((enc-message (RSA-encrypt string pub-key)))
  (signed-message enc-message
		  (RSA-transform (compress enc-message) priv-key))))

(define (authenticate-and-decrypt signed-message pub-key priv-key)
  (let ((message (RSA-decrypt (encrypted-part signed-message) priv-key)))
    (if (= (RSA-transform (signature-part signed-message) pub-key)
	       (compress (encrypted-part signed-message)))
	message
	"Message doesn't match hash")))


>  (define result2 
>    (encrypt-and-sign "Test message from user 1 to user 2"
>                      test-private-key1
>                      test-public-key2))
>  ;Value: result2
>
>  (authenticate-and-decrypt result2 test-public-key1 test-private-key2)
>  ;Value 29: "Test message from user 1 to user 2  "
                                                    ^
                                                    ^
>  (authenticate-and-decrypt result2 test-public-key2 test-private-key2)
>  ;Value 30: "Message doesn't match hash"


------------------------------------------------------------------------------

Lab Exercise 3:


(define signed-mystery (signed-message received-mystery-message received-mystery-signature))
;Value: signed-mystery

After getting several:

(authenticate-and-decrypt signed-mystery chuck-vest-public-key newt-gingrich-private-key)
;Value 30: "Message doesn't match hash"

You find:

(authenticate-and-decrypt signed-mystery  rupert-murdoch-public-key newt-gingrich-private-key)
;Value 31: "The time has come for the Pineapple to stir up the Whitewater.  "

------------------------------------------------------------------------------

Lab Exercise 4:

(define (solve-ax+by=1 a b)
  (if (= b 1)
      (cons 1 (- 1 a))
      (let ((solve (solve-ax+by=1 b (remainder a b))))
        (cons (cdr solve) (- (car solve) (* (quotient a b) (cdr solve)))))))


>  (solve-ax+by=1 233987973 41111687)
;Value 3: (29283862 . -166669675)

Note:  I looked at the mail sent out by Trevor and talked to Don Lee,
donlee@mit.edu

------------------------------------------------------------------------------

Lab Exercise 5:

(define (crack-rsa pub-key)
  (let ((n (key-modulus pub-key))
        (e (key-exponent pub-key)))
    (let ((p (smallest-divisor n)))
      (let ((q (/ n p)))
	(let ((m (* (- p 1) (- q 1))))
	  (let ((d (invert-modulo e m)))
	    (make-key n d)))))))

(crack-rsa (key-pair-public test-key-pair1))
;Value 6: (816898139 . 301956869)
 (make-key 816898139 301956869)))

(crack-rsa (key-pair-public test-key-pair2))
;Value 7: (513756253 . 462557987)
 (make-key 513756253 462557987)))
------------------------------------------------------------------------------

Lab Exercise 6:

>  (define bill-clinton-private-key (crack-rsa bill-clinton-public-key))
>  (define al-gore-private-key (crack-rsa al-gore-public-key))

Original Message:
----------------
Al, I'm in trouble!  My financial projections were way off!  We need to generate some more revenue quick.  Please hold a press conference to announce an upcoming tax hike on people with salaries greater than $100,000.  Bill.

>  (define fake-message (encrypt-and-sign "Al, I'm in trouble!  My financial projections were way off!  We need to generate some more revenue quick.  Please hold a press conference to announce an upcoming tax hike on people with salaries greater than $100,000.  Bill." bill-clinton-private-key al-gore-public-key))

>  fake-message
Encryption: ((419594824 531639709 368450264 500016787 100655086
			151048089 182863504 334479488 205855240
			377887600 160489034 555957106 242591029
			571197822 17439078 42996144 422230052
			368771625 424963857 148966975 409364125
			417535620 533589620 366579123 609117572
			6105268 297629734 422386083 481086830
			293783979 364247332 427205481 318186651
			506693961 97390162 633599267 499469783
			602476062 20130687 383083024 361572721
			527951024 229487548 12421082 307336318
			496581990 316059500 143433110 114576603
			408545082 568223762 340514829 294575374
			636441786 527505633 445631358)

Signature: 499380253)

>  (authenticate-and-decrypt fake-message bill-clinton-public-key al-gore-private-key)
;Value 5: "Al, I'm in trouble!  My financial projections were way off!  We need to generate some more revenue quick.  Please hold a press conference to announce an upcoming tax hike on people with salaries greater than $100,000.  Bill."

------------------------------------------------------------------------------

Lab Exercise 7:

(define al-gore-private-key (crack-rsa al-gore-public-key))
(define ross-perot-private-key (crack-rsa ross-perot-public-key))
(define newt-gingrich-private-key (crack-rsa newt-gingrich-public-key))

Message faked by Al Gore to Ross Perot
(define msg-to-ross (encrypt-and-sign "Hi Ross, this is Newt.  I was wondering if you might be interested in having tariffs raised on, say, a few of your competitors products?" newt-gingrich-private-key ross-perot-public-key))

>  (authenticate-and-decrypt msg-to-ross newt-gingrich-public-key ross-perot-private-key)
;Value 8: "Hi Ross, this is Newt.  I was wondering if you might be interested in having tariffs raised on, say, a few of your competitors products?"

Real Message from Ross to Al
(define msg-to-al (encrypt-and-sign "Hi Al, this is Ross.  I just got a highly illegal offer from Newt about some illegal maneuverings in Congress, presumeably for help in some campaign later on" ross-perot-private-key al-gore-public-key))

>  (authenticate-and-decrypt msg-to-al ross-perot-public-key al-gore-private-key)
;Value 9: "Hi Al, this is Ross.  I just got a highly illegal offer from Newt about some illegal maneuverings in Congress, presumeably for help in some campaign later on   "

Faked message from Al to Newt
(define msg-to-newt (encrypt-and-sign "Hi Newt, this is Ross.  I'm very interested in such a deal.  Of course, in return I'd be perfectly willing to maybe lend a hand in upcoming elections.  Quid pro pro." ross-perot-private-key newt-gingrich-public-key))

>  (authenticate-and-decrypt msg-to-newt ross-perot-public-key newt-gingrich-private-key)
;Value 10: "Hi Newt, this is Ross.  I'm very interested in such a deal.  Of course, in return I'd be perfectly willing to maybe lend a hand in upcoming elections.  Quid pro pro.   "

Message from Al Gore to media:
In a press-briefing today, the National Security Agency, breaking a
long history of remaining out of the national spot-light, announced
that it had broken the encryption on a set of messages between Newt
Gingrich and Ross Perot in which they agreed to exchange Congressional
favors for aid in future elections.  Both leaders have denied any
knowledge of the deal

-------------------------------------------------------------------------------

Lab Exercise 8:

Note:  I did this problem set on an RS/6000, and so times will be
slower than those recorded on the snakes.

For example:
(timed smallest-divisor 780450379)
;Value: 25057

(define (new-generate-RSA-key-pair val)
  (let ((size (expt 2 val)))
    (let ((p (choose-prime size size))
          (q (choose-prime size size)))
    (if (= p q)       ;check that we haven't chosen the same prime twice
        (generate-RSA-key-pair)     ;(VERY unlikely)
        (let ((n (* p q))
              (m (* (- p 1) (- q 1))))
          (let ((e (select-exponent m)))
            (let ((d (invert-modulo e m)))
              (make-key-pair (make-key n e) (make-key n d)))))))))

>  (define test (key-modulus (key-pair-public (new-generate-RSA-key-pair 10))))
>  test
;Value: 1327103
>  (timed smallest-divisor test)
(time: .539999999999992)

>  (define test (key-modulus (key-pair-public (new-generate-RSA-key-pair 14))))
>  test
;Value: 703128869
>  (timed smallest-divisor test)
(time: 16.019999999999982)

>  (define test (key-modulus (key-pair-public (new-generate-RSA-key-pair 16))))
>  test
;Value: 13533028079
>  (timed smallest-divisor test)
(time: 71.62)

>  (define test (key-modulus (key-pair-public (new-generate-RSA-key-pair 20))))
>  test
;Value: 2396184814259
>  (timed smallest-divisor test)
(time: 1063.6599999999999)

Time for 50 digit key:
An increase of one digit brings about a two time speed increase.
Therefore, 50 digits takes about 2^30 times longer than 2^20.
This comes out to about 10^12 seconds, or about 36,000 years, on an IBM
workstation.  

Time for 100 digit key:
Multiplying this result by 2^50, you get 4x10^19 years.  This is an
insane time, far longer than the universe has been in existence.

However, there exist computers today with over 4,000 times more
processing power than the IBM I was working on, using far more
advanced algorithms.  The reccomended secure key length is currently
128 digits for most cryptography systems.  It is considered extremely
unsafe to use anything less than 32 digit keys, as these apparently
can be broken in near real-time.

