For this question we will be implementing the $($unauthenticated$)$ Diffie$-$Hellman key agreement algorithm and

briefly explore what can go wrong when we don't set it up correctly.

We have seen in class that Diffie$-$Hellman should be implemented in a prime$-$order subgroup $G$ of a multiplicative

group modulo $($another$)$ prime $p$; we've also seen why. In this question, we will use a less careful implementation

in the entire multiplicative group modp. This group, denoted $Z_p^{**},$ has order $(p)=p-1$ which is not prime

$($for one thing, $p-1$ is divisble by $2).$ Diffie$-$Hellman works the same way in a prime$-$order group as it does in

a composite$-$order group, but the latter has some security weakness which we will see how to exploit$\mathrm{.}1.($Z$*$p As shown in the picture$)$ Using p $=2027,($i$)$ find the order modulo p of each of the ten elements $1,2,...,10.$ Then, $($ii$)$ based on your findings, indicate for each of those ten elements whether it generates all of Z$$p

$,$ a $$large$$ prime$-$order subgroup of Z$$p $($where $$large$$ is of course in relation with our relatively small value of p$),$ or something else $($if so$,$ briefly describe$).$

$2.$Choose one of the generators of the whole group and one of the generators of a large prime subgroup that

you have identified above, and confirm your conclusions for those two by explicitly doing all necessary

test$($s$)$ based on Fermat$$s little theorem, as explained above. $($If you already performed those calculations

in the previous subquestion, e$.$g$.,$ using the calculator$-$based method, then all you need for this subquestion

is to show your work for one generator of each kind.$)$

Next part

Now fix p $=2027$ as above, and fix g to be the smallest integer amongst $1,2,...,10,$ that is a generator of the full

group Z

$$

p

$,$ that you should have found in the foregoing. Alice and Bob want to perform a basic Diffie$-$Hellman

key exchange agreement, and will use those p and g as the protocol$$s common parameters.

Alice and Bob will choose their respective secret keys, a and b$,$ based on$$what else?

ID is $4321$ the alice a$=842$ and bob is b$=931($ we get $42$ from the id anf $31$ from the ID$,$ id is wxyz where a $=8$wy and b $=9$xz$)$

$4.$ What messages do Alice and Bob send to each other? Explicitly do the calculations using the square$-$andmultiply algorith

$5.$What then is the session key that Alice and Bob would be agreeing on$?$ Show the calculation of the session

key from each of Alice$$s and Bob$$s point of view.

NEXT PART

Performing Diffie$-$Hellman in the whole group Z

$$

p

is generally fine, unless one is very unlucky$$or one of the

parties is deliberately trying to sabotage the security of the resulting shared secret with plausible deniability.

Let$$s say that Bob is now a malicious Bot, who $($probably with an ulterior motive$)$ always picks b$\text{'}=1013$ as its secret key. Alice keeps using a $=842$

$6.$Calculate the key$-$exchange message that Bot with private key b

$0=1013$ sends to Alice. $($Alice$$s message

to Bob will be unchanged from above.$)$ Then complete the key exchange, showing how Alice and Bot

obtain the session key, to verify they both get the same. No need to detail any calculations.

$7.$Now, let$$s see what happens when Alice varies her private key, which we$$ll call $\backslash$alpha $,$ first with honest Bob

with key b $=9$xz as above, then with malicious Bot with key b

$0=1013.$ For this, successively redo the

key exchange between Alice and Bob, and between Alice and Bot, for the following ten different values

of Alice$$s private key: $\backslash$alpha $=$ a$,$ a $+1,$ a $+2,...,$ a $+9$ respectively. No need to show any calculation for this

question, just present the results in a table with $10$ rows $($one for each value of Alice$$s private key$)$ and

four columns: $(1)$ Alice$$s private key $\backslash$alpha ; $(2)$ Alice$$s message to Bob or Bot; $(3)$ the resulting shared secret

between Alice and Bob; $(4)$ the resulting shared secret between Alice and Bot.

$8.$Based on what you see in your table, draw the obvious conclusion.