[Solved] DIT250-TDA352 Home assignment 2

1.1 Part 1: Analyzing the generator

1. a) Weve been given the generator g = 18 and we are working in Z₂₃. The group which it generates is the set < g >= S = {gⁱ|0 i 21}.

A table for the calculations that find this set:

where the represent that the calculations continue, however in the same cyclical pattern as previously. The set S = {1,2,3,4,6,8,9,12,13,16,18}.

1. b) We note 2 3 = 6 S,

2 4 = 8 S,

4 6 (mod 23) = 1 S,

3 4 = 12, S

3 16 (mod 23) = 2 S.

Proposition 1. Let q > 0 and g Z_p and has the property g^q = 1 then {gⁱ|0 i < q} is closed under scalar multiplication.

Proof We want to show that for given any a,b S = {gⁱ|0 i < q} then a b S.

Let a = g^k1 and b = g^k2, then ab = g^k1+k2. Let us distinguish between two cases that can happen. Case 1: k₁+ k₂ < q, then the result is clear that a b S by definition of S.

Case 2: k₁+k₂ q. Note that k₁+k₂ < 2q from defintion of S and hence we can write k₁+k₂ = q+s where we know 0 s < q. g^k1+k2 = g^q+s = g^q g^s = 1 g^s = g^s S.

In both cases we conclude that a b S and this concludes the proof.

1.2 Part 2: Encrypting a message

We know that the public key is 6 = g^x and the message m = 17. By looking at our table from previous part we note that x = 7. To encrypt m we choose a random , in this case we choose k = 3. We encrypt by calculating c = (c₁,c₂).

Calculate . Hence c = (13,15).

To assure ourselves that we have encrypted the correct way we can try to decrypt the message in this case. We can do this since we know the fact that x = 7. We start with calculating k = 13⁷ = 9 in , where k¹ can be found using the extended euclidean algorithm and in this case we get since , that . Performing this calculation gives us then that and we obtain the original message.

1.3 Part 3: Decrypting a message

What is public is that we are using the group G = (the order of the generated set), and also h = g^x = 18⁹ = 12 (mod 23). So we can write public key pk = (G,g,q,h)

We have the message (13,11)(12,15)(9,10) and the private key x = 9. Since we have the private key we can follow the steps to decipher this message.

We use the formula that and . These calculations in our case when p = 23 and we essentially have three different messages we wish to decrypt and then concatenate these into the secret message.

k = 13⁹ = 3 (mod 23), k¹ = 8 since 3 8 = 1 (mod 23). We then get m = 11 8 = 19 (mod 23). This letter is S.

k = 12⁹ = 4 (mod 23), k¹ = 6 since 4 6 = 1 (mod 23). We then get m = 15 6 = 21 (mod 23). This letter is U.

k = 9⁹ = 2 (mod 23), k¹ = 12 since 2 12 = 1 (mod 23).We then get m = 10 12 = 5 (mod 23). This letter is E.

The concatenated decrypted word is then: SUE.

In this example finding the inverses were quite straightforward and the solution were seen. In the general way one would use the extended euclidean algorithm to find k¹. This is how these calculations would look for the first case, i.e the letter S using the extended euclidean algorithm.

3

k = 3, and we wish to find k¹ in (mod 23).

23 = 3 7+2

3 = 2 1+1

2 = 1 2+0

Then we move backwards

1 = 3 2 1

1 = 3 (23 3 7) = 3 8 23

Which gives us that if we take (mod 23) on both sides, we obtain that 3 8 = 1 (mod 23)

Written in python-like code (where % is modulus and // is integer division) we can write the EEA algorithm recursively as follows

Algorithm 1 EEA(a, b)

1: if a == 0 then

2: return (b,0,1)

3: else

4: gcd, x, y = EEA(b % a, a)

5: return (gcd, y (b//a) * x, x)

I believe the steps in calculation is easier to show by example as we did above but the algorithm can also be used.

4