To verify the MAC of a message-MAC-pair, compute the MAC directly from the message and the shared-key and compare it to the MAC that is contained in the message-MAC-pair.
(define (verify-MAC message-MAC-pair shared-key)
(let ((MACsent (get-MAC message-MAC-pair)))
(= MACsent
(compute-MAC (get-message message-MAC-pair) shared-key))))
(verify-MAC mMAC1-ex-1 skey-ex-1)
;Value: #t
(verify-MAC mMAC2-ex-1 skey-ex-1)
;Value: #f
Thus, the first message-MAC-pair is the correct one.
There are two problems with this code, and the debugger has the following complaints:
(define (recursive-compute-MAC string key times)
(if (= 1 times)
(compute-MAC string key)
(compute-MAC (recursive-compute-MAC string key (- times 1))
key)))
(recursive-compute-MAC "I hope this works" 87193 2)
;Value: 163054733316285507945076193372690511037
The iterative code is as follows:
(define (iterative-compute-MAC string key times)
(define (helper sofar count)
(if (= 1 count)
(compute-MAC sofar key)
(helper (compute-MAC sofar key) (- count 1))))
(helper string times))
(iterative-compute-MAC "I hope this works" 87193 2)
;Value: 163054733316285507945076193372690511037
Let's looks at what happens when we trace these procedures:
(trace recursive-compute-MAC)
;Value: #[unspecified-return-value]
(recursive-compute-MAC "Just having fun.." 314159 4)
[Entering #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
4]
[Entering #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
3]
[Entering #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
2]
[Entering #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
1]
[91088909492190335021912655447401122364
<== #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
1]
[91061232049483883016432832413067093292
<== #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
2]
[131360175029680226814359560572131099429
<== #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
3]
[103890457811107377179587624154361699571
<== #[compound-procedure 6 recursive-compute-mac]
Args: "Just having fun.."
314159
4]
;Value: 103890457811107377179587624154361699571
Here, recursive calls are made, but no computation is performed until
the base case is reached, at which point all the deferred compute-MAC
operations are calculated. The results of these deferred operatinos
appear in the last four traced entries above. (Note: don't be
confused by the "shape" of the trace output; it doesn't display the
characteristic "expand" and "contract" shape because, unlike the
examples using the substitution model in lecture, the deferred
operations are not explicitly displayed.)
(trace iterative-compute-MAC)
(trace iterative-compute-MAC '(helper))
;Value: #[unspecified-return-value]
(iterative-compute-MAC "Just having fun.." 314159 4)
[Entering #[compound-procedure 3 helper]
Args: "Just having fun.."
4]
[Entering #[compound-procedure 3 helper]
Args: 91088909492190335021912655447401122364
3]
[Entering #[compound-procedure 3 helper]
Args: 91061232049483883016432832413067093292
2]
[Entering #[compound-procedure 3 helper]
Args: 131360175029680226814359560572131099429
1]
[103890457811107377179587624154361699571
<== #[compound-procedure 3 helper]
Args: 131360175029680226814359560572131099429
1]
[103890457811107377179587624154361699571
<== #[compound-procedure 3 helper]
Args: 91061232049483883016432832413067093292
2]
[103890457811107377179587624154361699571
<== #[compound-procedure 3 helper]
Args: 91088909492190335021912655447401122364
3]
[103890457811107377179587624154361699571
<== #[compound-procedure 3 helper]
Args: "Just having fun.."
4]
;Value: 103890457811107377179587624154361699571
Notice that in the iterative case, the MAC is computed
immediately (look at the Args value), and when the base
case is reached, the final value (103890...) is already
known. What do the last four traced entries in the
iterative case above tell you?
To find a safe prime, first find a prime q (note that digits is in actuality the size of q, so p is actually of size digits or digits+1), then compute the corresponding p. If p is prime, then we're all set. If it is not, recurse.
;; notice that we used a nested let
(define (choose-safe-prime digits)
(let (( possibleq (choose-prime digits) ))
(let (( possiblep (+ (* 2 possibleq) 1)))
(if (fast-prime? possiblep 2)
possiblep
(choose-safe-prime digits)))))
Given a safe prime, pick random valid values for g and test
if g is a generator (as specified on page 7 of the problem set).
;; why is a nested let not necessary here?
(define (find-generator safeprime)
(let ((possibleg (choose-random safeprime))
(q (/ (- safeprime 1) 2)))
(if (and (not (= 1 (expmod possibleg 2 safeprime)))
(not (= 1 (expmod possibleg q safeprime))))
possibleg
(find-generator safeprime))))
Here we show how to generate system parameters, key systems for Alyssa and Ben, and a shared secret key. Without loss of generality, Alyssa chooses p and g (Ben could have done so, it doesn't matter as long as both parties know what p and g are).
;; generate the p and g (define alyssa-key-system (generate-key-system-parameters 5)) ;Value: alyssa-key-system alyssa-key-system ;Value: (50147 40186 33371 1329) ;; alyssa then publishes the values of p and g so that they are globally known ;; (particularly since ben needs them!) (define p (get-key-system-p alyssa-key-system)) ;Value: p (define g (get-key-system-g alyssa-key-system)) ;Value: g (define ben-key-system (create-key-system p g)) ;Value: ben-key-system ben-key-system ;Value: (50147 40186 22583 40327)To complete the Diffie Hellman key exchange, we need to implement the compute-shared-secret-key, which calculates the shared key.
(define (compute-shared-secret-key ksystem published-ksystem)
(let ((partner-y (get-published-key-y published-ksystem))
(p (get-key-system-p ksystem))
(x (get-key-system-x ksystem)))
(expmod partner-y x p)))
Here, we test it for both Alyssa and Ben just to make sure they
arrive at the same value for K.
(compute-shared-secret-key alyssa-key-system (key-system->published-key ben-key-system)) ;Value: 4711 (compute-shared-secret-key ben-key-system (key-system->published-key alyssa-key-system)) ;Value: 4711
(verify-MAC seq1-poss1-ex-5 skey-ex-5) (verify-MAC seq1-poss2-ex-5 skey-ex-5) (verify-MAC seq1-poss3-ex-5 skey-ex-5) (verify-MAC seq2-poss1-ex-5 skey-ex-5) (verify-MAC seq2-poss2-ex-5 skey-ex-5) (verify-MAC seq2-poss3-ex-5 skey-ex-5) (verify-MAC seq3-poss1-ex-5 skey-ex-5) (verify-MAC seq3-poss2-ex-5 skey-ex-5) (verify-MAC seq3-poss3-ex-5 skey-ex-5) (verify-MAC seq4-poss1-ex-5 skey-ex-5) (verify-MAC seq4-poss2-ex-5 skey-ex-5) (verify-MAC seq4-poss3-ex-5 skey-ex-5) (verify-MAC seq5-poss1-ex-5 skey-ex-5) (verify-MAC seq5-poss2-ex-5 skey-ex-5) (verify-MAC seq5-poss3-ex-5 skey-ex-5)(a) The phrase to be: "Who said that Athena would be good for you"
(b) For the first sequence number, there are s possibilities; for the second and so forth all the way to the rth sequence number, there are s possibilities, so there are a total of s^r possibilties if you didn't know K and you wanted to enumerate all possible combinations.
(c) If you had no sequence numbers and did not know K, this adds another degree of complexity, since potentially any fragment could be have any sequence number, if you enumerated all possibilities that would be ((rs)!/ ( r! (rs-r)!))! = "rs choose r" and then compute the factorial of that (basically, choose the r fragments, and then consider how these r can then be ordered). That's a whole lot.
(d) If you knew K, you could run verify-MAC on each message-MAC-pair
to identify all r pairs that are authentic. And now you just have
to consider all the ways to permute these r messages, so there are
r! possibilties.
Computer Exercise 6:
Find the value of x by "brute-force" -- trying all possible valid x, 2<=x<=p-2.
(define (find-discrete-log y g p)
(define (try x)
(cond ((> x (- p 2)) false)
((= (expmod g x p) (modulo y p)) x)
(else (try (+ 1 x)))))
(try 2))
;Value: find-discrete-log
(crack-published-key pk-ex-6)
;Value: (19079 362 107 6843)
(timed crack-published-key pk-ex-6)
;Value: (.240000000000002 (19079 362 107 6843))
So to crack pk-ex-6, it takes about .24 seconds..! Let's run it a few more times to compute an average time to break a 4-digit published key.
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (16.629999999999995 (6779 273 4374 4566))
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (8.389999999999986 (3203 1766 2371 1475))
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (4.609999999999957 (13163 11261 1224 13125))
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (4.319999999999993 (6659 2951 1303 4193))
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (8.440000000000055 (16547 2424 2180 14086))
(timed crack-published-key
(key-system->published-key (generate-key-system-parameters 4)))
;Value: (8.180000000000064 (11423 2041 2175 3451))
;; average time
(/ (+ 16.63 8.39 4.61 4.32 8.44 8.18) 6)
;Value: 8.428333333333333
So the average time is about 8.4 seconds. To simplify the math,
assume it takes about 10 seconds to crack a 4-digit key.
As mentioned in the problem set,
for every digit added to the key, we can expect that the time
to crack will increase by a factor of 10. So a 5-digit key
will take 100 seconds,a 6-digit key 1000 seconds... a 50-digit
key should take about (expt 10 47) seconds and a 100-digit key about
(expt 10 97) seconds.
Let's do some quick calculations:
(define seconds-in-a-year (* 365 24 60 60)) ;Value: "seconds-in-a-year --> 31536000" (define resources 1000000) ;Value: "resources --> 1000000" (define years-to-crack-50-digits (/ (expt 10 47) seconds-in-a-year resources)) ;Value: "years-to-crack-50-digits --> 3.170979198376459e33" (define years-to-crack-100-digits (/ (expt 10 97) seconds-in-a-year resources)) ;Value: "years-to-crack-100-digits --> 3.170979198376459e83"Compared to the estimated age of the universe, which is a mere 15 billion years (1.5e10), it can take an extremely long time to crack a 50-digit key.