Computer Exercise 6

Let's find out the time to crack the 4-digit code:

(timed crack-public-key pk-ex-5)
;Value: (.2300000000000182 (19079 362 107 6843))

Now let's run it a few more times and compute an average time to break a 4-digit code:

(timed crack-public-key (key-system->public-key (generate-key-system 4)))
;Value: (4.160000000000025 (7727 7516 1245 7162))

(timed crack-public-key (key-system->public-key (generate-key-system 4)))
;Value: (8.689999999999998 (17027 10018 2184 3365))

(timed crack-public-key (key-system->public-key (generate-key-system 4)))
;Value: (15.850000000000023 (6779 273 4374 4566))

(timed crack-public-key (key-system->public-key (generate-key-system 4)))
;Value: (7.600000000000023 (3203 1766 2371 1475))

(timed crack-public-key (key-system->public-key (generate-key-system 4)))
;Value: (4.400000000000034 (13163 11261 1224 13125))

(/ (+ .23 4.16 8.68 15.85 7.6 4.4) 
   6)
;Value: 6.819999999999999

So it looks like, on average it takes about 7 seconds to crack a 4-digit key. For the purpose of simplying our math, let's assume it takes about 10 seconds to crack a 4-digit key. As discussed on page 6 of the problem set, for every digit added to the key, we can expect the time to crack it to increase by a factor of 10. So a key of 5 digits will take 10 times longer a 4-digit key, and a key of 6 digits will take 10 * 10, or 100, times longer to crack, and so on.

Extrapolating, we can compute the factor increases for a 50- and 100-digit key as

(define 50-digit-factor (expt 10 (- 50 4)))
(define 100-digit-factor (expt 10 (- 100 4)))

Now, defining some other constants,

(define 4-digit-seconds 10)
(define computation-speedup 1000000)
(define seconds-in-a-year (* 365 24 60 60))

..the number to years to crack 50- and 100-digit keys can be computed as:

(define years-to-crack-50-digits (/ (* 4-digit-seconds 50-digit-factor)
                                    computation-speedup
                                    seconds-in-a-year))

years-to-crack-50-digits
;Value: 3.170979198376459e33


(define years-to-crack-100-digits (/ (* 4-digit-seconds 100-digit-factor)
                                     computation-speedup
                                     seconds-in-a-year))

years-to-crack-100-digits
;Value: 3.170979198376459e83

Let's compare these years in terms of the age of the universe, which is 15 billion years:

(define age-of-universe (* 15 (expt 10 9)))

(/ years-to-crack-50-digits age-of-universe)
;Value: 2.1139861322509725e23

(/ years-to-crack-100-digits age-of-universe)
;Value: 2.1139861322509726e73

Wow!