1.1 Part 1: Analyzing the generator
- a) We’ve been given the generator g = 18 and we are working in Z23∗. The group which it generates is the set < g >= S = {gi|0 ≤ i ≤ 21}.
A table for the calculations that find this set:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | … |
| g^i | 1 | 18 | 2 | 13 | 4 | 3 | 8 | 6 | 16 | 12 | 1 | 18 | 2 | 13 | 4 | 3 | 8 | 6 | … |
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}.
- 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 ∈ Zp∗ and has the property gq = 1 then {gi|0 ≤ i < q} is closed under scalar multiplication.
Proof We want to show that for given any a,b ∈ S = {gi|0 ≤ i < q} then a · b ∈ S.
Let a = gk1 and b = gk2, then a·b = gk1+k2. Let us distinguish between two cases that can happen. Case 1: k1+ k2 < q, then the result is clear that a · b ∈ S by definition of S.
Case 2: k1+k2 ≥ q. Note that k1+k2 < 2q from defintion of S and hence we can write k1+k2 = q+s where we know 0 ≤ s < q. gk1+k2 = gq+s = gq · gs = 1 · gs = gs ∈ 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 = gx 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 = (c1,c2).
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 = 137 = 9 in , where k−1 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 = gx = 189 = 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 = 139 = 3 (mod 23), k−1 = 8 since 3 · 8 = 1 (mod 23). We then get m = 11 ∗ 8 = 19 (mod 23). This letter is ’S’.
k = 129 = 4 (mod 23), k−1 = 6 since 4 · 6 = 1 (mod 23). We then get m = 15 ∗ 6 = 21 (mod 23). This letter is ’U’.
k = 99 = 2 (mod 23), k−1 = 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−1. 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−1 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
