ITN581 - Cryptographic Fundamentals and Applications

Semester 1 2002 - Assignment 2 (85 marks)

Gavin Longmuir (answers in red)

1. (10 marks)

Use the Lehmann-Peralta test to examine whether each of the following numbers are prime. In these tests use the five random numbers 7, 32, 101, 150, 360 for each test. Show all work.

k = 5, a {7, 32, 101, 150, 360}

calculate a_i^(p-1)/2 (mod p)

(i) 69301373

7^34650686 บ 1 mod 69301373

32^34650686 บ -1 mod 69301373

101^34650686 บ 1 mod 69301373

150^34650686 บ 1 mod 69301373

360^34650686 บ 1 mod 69301373

a_i^(p-1)/2 (mod p) บ 1 or บ -1 for aⁱ and at least one aⁱ บ -1 then p is prime

69301373 is prime with probability of 1-(.5)⁵ = 0.96875

(ii) 497025

7²⁴⁸⁵¹² บ 163096 mod 497025

32²⁴⁸⁵¹² บ 376726 mod 497025

101²⁴⁸⁵¹² บ 286126 mod 497025

150²⁴⁸⁵¹² บ 48600 mod 497025

360²⁴⁸⁵¹² บ 486900 mod 497025

a_i^(p-1)/2 (mod p) is not บ 1 or บ -1 for aⁱ for at least one value then p is composite

497025 is not prime

(iii) 3872150317295

7^{1936075158647} บ 432665620428 mod 3872150317295

32^{1936075158647} บ 1579613429288 mod 3872150317295

101^{1936075158647} บ 3743021638776 mod 3872150317295

150^{1936075158647} บ 1164820752890 mod 3872150317295

360^{1936075158647} บ 3105733254965 mod 3872150317295

a_i^(p-1)/2 (mod p) is not บ 1 or บ -1 for aⁱ for at least one value then p is composite

3872150317295 is not prime

(iv) 51921038173

7^25960519086 บ 1 mod 51921038173

32^25960519086 บ -1 mod 51921038173

101^25960519086 บ -1 mod 51921038173

150^25960519086 บ -1 mod 51921038173

360^25960519086 บ 1 mod 51921038173

a_i^(p-1)/2 (mod p) บ 1 or บ -1 for aⁱ and at least one aⁱ บ -1 then p is prime

51921038173 is prime with probability of 1-(.5)⁵ = 0.96875

(v) 7613991836111

7^25960519086 บ 1 mod 7613991836111

32^25960519086 บ 1 mod 7613991836111

101^25960519086 บ -1 mod 7613991836111

150^25960519086 บ 1 mod 7613991836111

360^25960519086 บ 1 mod 7613991836111

a_i^(p-1)/2 (mod p) บ 1 or บ -1 for aⁱ and at least one aⁱ บ -1 then p is prime

7613991836111 is prime with probability of 1-(.5)⁵ = 0.96875

2. (2 marks)

For the numbers examined in Question 1 which have been shown to be prime what is the probability that the number is prime using the Lehmann-Peralta test.

See workings including in answer to question 1 (i), (iv), and (v)

3. (2 marks)

Pepin's Theorem says that a necessary and sufficient condition for a Fermat number F_n = 2^r + 1 is prime (where r = 2ⁿ) is that

3^k บ-1 (mod F_n) where k =2^j-1 and j = 2ⁿ.

Use Pepin's Theorem to show that F₅ is not prime.

n = 5, r = j = 2⁵ = 32

F₅ = 2^r + 1 = 2³² + 1 = 4294967297

k = 2^32-1

3.k บ 2147483647 (mod 4294967297)

which is not บ -1 (mod 4294967297)

hence F₅ is not prime

4. (4 marks)

Use the Sieve of Eratoshenes to find a complete factorization of

(i) 389459 and

Members of φ(100) are: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,89,97

2,3,5,7,11 product ่ 1122660

13,17,19,23,29 product ่ 2800733

31,37,41,43,47 product ่ 95041567

53,59,61,67 product ่ 12780049

71,73,79,89,97 product ่ 3534842281

gcd(1122660,389459) = 7

gcd(2800733,389459) = 23

gcd(95041567,389459) = 41

gcd(12780049,389459) = 59

gcd(3534842281,389459) = 1

factors are: 7,23,41,59

(ii) 2826195

gcd(1122660,2826195) = 15 = 3.5

gcd(2800733,2826195) = 29

gcd(95041567,2826195) = 1

gcd(12780049,2826195) = 1

gcd(3534842281,2826195) = 6497 = 73.89

factors are: 3,5,29,73,89

given that all prime factors are less than 100.

Hint: List all the prime numbers less than 100: 2,3,5,7,.... Then divide the primes into groups of size 5 (say). Calculate the product of each group. Then find the gcd (using the software package) of the number to be factored (n) and the product of the first group. If the answer is one, then this means that none of the factors in that group is a factor of n. If the answer is not one, then this means that one or more of the factors in that group is a factor of n, and can be divided out of n before continuing on to the next group.

5(a) (2 marks)

Factor each of the following numbers using Fermat Factorization. Show all work.

(i) 17653

n = 17653, √17653 = approx 132.9, let t = 133

let z = t² – n

t = 133, z = 133² – 17653 = 36, which is a perfect square

√36 = 6, let s = z, n = t² – s² = (t + s)(t – s)

thus 17653 = 133² – 6² = (133 + 6)(133 – 6) = (139)(127)

factors are 139 and 127

(ii) 5392629

n = 5392629, √5392629 = approx 2322.2, let t = 2323

let z = t² – n

t = 2323, z = 2323² – 5392629 = 3700, not perfect

t = 2324, z = 2324² – 5392629 = 8347, not perfect

t = 2325, z = 2325² – 5392629 = 12996, perfect

√12996 = 114, let s = z, n = t² – s² = (t + s)(t – s)

thus 5392629 = 2325² – 114²

= (2325 + 114)(2325 – 114) = (2439)(2211)

factors are 2439 and 2211

5(b) (2 marks)

Show why the 35-bit integer 23364327887 is a particularly bad choice for n = pq (because the two prime factors are too close to one another); that is, show that n can easily be factored by Fermat factorization.

n = 23364327887, √23364327887 = approx 152853.9

let t = 152854, let z = t² – n

t = 152854, z = 152854² – 23364327887

= 17429, not perfect

t = 152855, z = 152855² – 23364327887

= 323138, not perfect

t = 152856, z = 152856² – 23364327887

= 628849, perfect

√628849 = 793, let s = z, n = t² – s² = (t + s)(t – s)

thus 23364327887 = 152856² – 793²

= (152856 + 793)(152856 – 793)

= (153649)(152063)

factors are 153649 and 152063

6. (4 marks)

Factor each of the following numbers using Pollard's Rho method using f(x) = x² + 1 with initial seed x₀ = 3.

x₀ = 3, f(x) = x² + 1

x_i+1 บ f(x_i) mod n

x_i+2 บ f(x_i+1) mod n

gcd(x_i+2 – x_(i+2)/2, n) = d

(i) 1271143

x₁ บ f(x₀) mod 1271143 บ 10 mod 1271143

x₂ บ f(x₁) mod 1271143 บ 101 mod 1271143

gcd(x₂ – x₁, 1271143) = gcd(101 – 10, 1271143) = 1

x₃ บ f(x₂) mod 1271143 บ 10202 mod 1271143

x₄ บ f(x₃) mod 1271143 บ 1118222 mod 1271143

gcd(x₄ – x₂, 1271143) = gcd(1118222 – 101, 1271143) = 1

x₅ บ f(x₄) mod 1271143 บ 885614 mod 1271143

x₆ บ f(x₅) mod 1271143 บ 401138 mod 1271143

gcd(x₆ – x₃, 1271143) = gcd(401138 – 10202, 1271143) = 1

x₇ บ f(x₆) mod 1271143 บ 244961 mod 1271143

x₈ บ f(x₇) mod 1271143 บ 315064 mod 1271143

gcd(x₈ – x₄, 1271143) = gcd(315064 – 1118222, 1271143) = 1

x₉ บ f(x₈) mod 1271143 บ 496084 mod 1271143

x₁₀ บ f(x₉) mod 1271143 บ 965685 mod 1271143

gcd(x₁₀ – x₅, 1271143) = gcd(965685 – 885614, 1271143) = 1

x₁₁ บ f(x₁₀) mod 1271143 บ 151279 mod 1271143

x₁₂ บ f(x₁₁) mod 1271143 บ 948413 mod 1271143

gcd(x₁₂ – x₆, 1271143) = gcd(948413 – 401138, 1271143) = 1

x₁₃ บ f(x₁₂) mod 1271143 บ 1008910 mod 1271143

x₁₄ บ f(x₁₃) mod 1271143 บ 1123419 mod 1271143

gcd(x₁₄ – x₇, 1271143) = gcd(1123419 – 244961, 1271143) = 1

x₁₅ บ f(x₁₄) mod 1271143 บ 668296 mod 1271143

x₁₆ บ f(x₁₅) mod 1271143 บ 908281 mod 1271143

gcd(x₁₆ – x₈, 1271143) = gcd(908281 – 315064, 1271143) = 127

thus 1271143 = 127 . b ่ b = 1271143 / 127 = 10009

่ factors are 127 and 10009

(ii) 1134407

x₁ บ f(x₀) mod 1134407 บ 10 mod 1134407

x₂ บ f(x₁) mod 1134407 บ 101 mod 1134407

gcd(x₂ – x₁, 1134407) = gcd(101 – 10, 1134407) = 1

x₃ บ f(x₂) mod 1134407 บ 10202 mod 1134407

x₄ บ f(x₃) mod 1134407 บ 1118222 mod 1134407

gcd(x₄ – x₂, 1134407) = gcd(1118222 – 101, 1134407) = 1

x₅ บ f(x₄) mod 1134407 บ 1040616 mod 1134407

x₆ บ f(x₅) mod 1134407 บ 559804 mod 1134407

gcd(x₆ – x₃, 1134407) = gcd(559804 – 10202, 1134407) = 1

x₇ บ f(x₆) mod 1134407 บ 584667 mod 1134407

x₈ บ f(x₇) mod 1134407 บ 101952 mod 1134407

gcd(x₈ – x₄, 1134407) = gcd(101952 – 1118222, 1134407) = 1

x₉ บ f(x₈) mod 1134407 บ 773371 mod 1134407

x₁₀ บ f(x₉) mod 1134407 บ 225776 mod 1134407

gcd(x₁₀ – x₅, 1134407) = gcd(225776 – 1040616, 1134407) = 1

x₁₁ บ f(x₁₀) mod 1134407 บ 223632 mod 1134407

x₁₂ บ f(x₁₁) mod 1134407 บ 938830 mod 1134407

gcd(x₁₂ – x₆, 1134407) = gcd(938830 – 559804, 1134407) = 1

x₁₃ บ f(x₁₂) mod 1134407 บ 427704 mod 1134407

x₁₄ บ f(x₁₃) mod 1134407 บ 776425 mod 1134407

gcd(x₁₄ – x₇, 1134407) = gcd(776425 – 584667, 1134407) = 1

x₁₅ บ f(x₁₄) mod 1134407 บ 556756 mod 1134407

x₁₆ บ f(x₁₅) mod 1134407 บ 530787 mod 1134407

gcd(x₁₆ – x₈, 1134407) = gcd(530787 – 101952, 1134407) = 113

thus 1134407 = 113 . b ่ b = 1134407 / 113 = 10039

่ factors are 113 and 10039

7. (3 marks)

It has been proposed in the future to use 300 digit prime numbers in Europe in the RSA cipher. Use the prime number theorem to estimate the probability of selecting a prime number of 300 decimal digits at random from odd 300 digit numbers.

π(x) represents number of primes between 1 and x

Prime number Theorem states that π(x) approaches x/ln(x) as x approaches ∞

[π(10³⁰⁰) – π(10²⁹⁹)] / [(10³⁰⁰ – 10²⁹⁹)/2]

= [(10³⁰⁰/ln 10³⁰⁰) – (10²⁹⁹/ln 10²⁹⁹)] / [(10³⁰⁰ – 10²⁹⁹)/2]

= [10²⁹⁹(10/300 ln(10) – (1/299 ln(10))] / [10²⁹⁹(10 – 1)/2]

= [(1/30 ln(10) – (1/299 ln(10))] / [9/2]

= (2/9) [1/ln(10)] [(1/30) – (1/299)]

= (2/9) [1/ln(10)] [269/8970]

= [538/80730] / ln(10)

= approx 1/346

8. (1 mark)

Given the Modulus N=33217, the public key e=13147, and the message M=25317, compute the cryptogram in the RSA cryptosystem. The factorisation of n = 33217 = 563 x 59. This will enable you to determine phi(n), and hence d, the decryption key. Verify your answer by decrypting the cryptogram and recovering the message.

p = 563, q = 59, n = pq = 33217

e = 13147

M = 25317

C = M^e mod n

= 25317¹³¹⁴⁷ mod 33217

= 21745

φ(n) = (p – 1)(q – 1)

φ(33217) = 562 . 58 = 32596

d = e^-1 mod φ(n)

= 13147^-1 mod 32596

= 22391

M = C^d mod n

= 21745²²³⁹¹ mod 33217

= 25317

9. (3 marks)

Consider the RSA system for N = 3551 (p = 53, q = 67). Compute numbers of unconcealable messages while applying the following public keys:

Number of unconcealable messages is given by:

(1 + gcd(K – 1, p – 1)) (1 + gcd(K – 1, q – 1))

(a) K = 701,

(1 + gcd(700,52)) (1 + gcd(700,66))

(1 + 4) (1 + 2) ่ 15 unconcealable messages

(b) K = 1392,

(1 + gcd(1391,52)) (1 + gcd(1391,66))

(1 + 13) (1 + 1) ่ 28 unconcealable messages

(c) K = 1210.

(1 + gcd(1209,52)) (1 + gcd(1209,66))

(1 + 13) (1 + 3) ่ 56 unconcealable messages

10. (6 marks)

For each of the following sequences and "volumes", decide whether the knapsack problem is superincreasing and how many solutions (if any) it has:

Superincreasing set members element e_j is greater than the sum of previous members e₁ to e_j-1
let set be denoted {e₁, e₂, e₃, e₄, e₅, e₆} and the solution
{m₁, m₂, m₃, m₄, m₅, m₆}

(a) {2,5,8,20,36,72}, V = 50,

superincreasing set

50 ≥ 72 ่ no m₆ = 0

50 ≥ 36 ่ yes m₅ = 1, 50 – 36 = 14

14 ≥ 20 ่ no m₄ = 0

14 ≥ 8 ่ yes m₃ = 1, 14 – 8 = 6

6 ≥ 5 ่ yes m₂ = 1, 6 – 5 = 1

1 ≥ 2 ่ no m₁ = 0

still remainder thus no solution

(b) {1,3,9,20,32,78}, V = 73,

not superincreasing set

m₆ must be zero as value larger than “volume”, sum of remainders doesn’t get close enough ่ thus no solution

(c) {5,9,19,39,75,159}, V = 125,

superincreasing set

125 ≥ 159 ่ no m₆ = 0

125 ≥ 75 ่ yes m₅ = 1, 125 – 75 = 50

50 ≥ 39 ่ yes m₄ = 1, 50 – 39 = 11

11 ≥ 19 ่ no m₃ = 0

11 ≥ 9 ่ yes m₂ = 1, 11 – 9 = 2

2 ≥ 5 ่ no m₁ = 0

still remainder thus no solution

(d) {2,3,6,11,23,55}, V = 34,

not superincreasing set

34 ≥ 55 ่ no m₆ = 0

34 ≥ 23 ่ yes m₅ = 1, 34 – 23 = 11

11 ≥ 11 ่ yes m₄ = 1, 11 – 11 = 0

all other values are zero, since values e₀, e₁, and e₂ also equal 11 two solutions exist.

(e) {3,8,12,18,42,89}, V = 119,

not superincreasing set

119 ≥ 89 ่ yes m₆ = 1, 119 – 89 = 30

30 ≥ 42 ่ no m₅ = 0

30 ≥ 18 ่ yes m₄ = 1, 30 – 18 = 12

12 ≥ 12 ่ yes m₃ = 1, 12 – 12 = 0

all other values are zero

one solution exists

(f) {2,6,7,20,45,100}, V = 65.

not superincreasing set

65 ≥ 100 ่ no m₆ = 0

65 ≥ 45 ่ yes m₅ = 1, 65 – 45 = 20

20 ≥ 20 ่ yes m₄ = 1, 20 – 20 = 0

all other values are zero

one solution exists

11. (4 marks)

Using a Knapsack cipher, suppose that plaintext message units are single letters in the usual 26-letter alphabet with A-Z corresponding to 0-25. You receive the sequence of ciphertext message units, 1317, 653, 3284, 1408, 1317, 653, 48, 2061, 1271, 2677, 2013, 1271, 2679, 653 The public key is the sequence {1269, 1271, 653, 48, 1360} and the secret key is n=630,p=1889.

(a) Try to decipher the message without using the deciphering key. Check by

using the deciphering key and the algorithm for a superincreasing

knapsack problem.

Since the public key set is small an exhaustive search is possible

Let C = {1317, 653, 3284, 1408, 1317, 653, 48, 2061, 1271, 2677, 2013, 1271, 2679, 653}

= { ▲ ■ ∆ ♥ ▲ ■ ♫ € ♦ ∩ ☼ ♦ ☺■ }

= { S E ∆ ♥ S E ♫ € I ∩ ☼ I ☺ E }

n = 630, n^-1 = 3 mod 1889

S = {1269, 1271, 653, 48, 1360} = {e₁, e₂, e₃, e₄, e₅}

d_i บ e_i n^-1 mod p

d₁ บ e₁ n^-1 mod 1889 = 29

d₂ บ e₂ n^-1 mod 1889 = 35

d₃ บ e₃ n^-1 mod 1889 = 70

d₄ บ e₄ n^-1 mod 1889 = 144

d₅ บ e₅ n^-1 mod 1889 = 302

S ′ = {d₁, d₂, d₃, d₄, d₅} = {29, 35, 70, 144, 302}

Let j be current message unit ่ M_j = n^-1 C_j mod p

M₁ บ 1317 . 3 mod 1889 = 173

factoring 173 into S ′ ่ gives binary vector {1,0,0,1,0} = 18 ่ S

M₂ บ 653 . 3 mod 1889 = 70

factoring 70 into S ′ ่ gives binary vector {0,0,1,0,0} = 4 ่ E

M₃ บ 3284 . 3 mod 1889 = 407

factoring 407 into S ′ ่ gives binary vector {0,1,1,0,1} = 13 ่ N

M₄ บ 1408 . 3 mod 1889 = 446

factoring 446 into S ′ ่ gives binary vector {0,0,0,1,1} = 3 ่ D

M₅ บ 1317 . 3 mod 1889 = 173

factoring 173 into S ′ ่ gives binary vector {1,0,0,1,0} = 18 ่ S

M₆ บ 653 . 3 mod 1889 = 70

factoring 70 into S ′ ่ gives binary vector {0,0,1,0,0} = 4 ่ E

M₇ บ 48 . 3 mod 1889 = 144

factoring 144 into S ′ ่ gives binary vector {0,0,0,1,0} = 2 ่ C

M₈ บ 2061 . 3 mod 1889 = 516

factoring 516 into S ′ ่ gives binary vector {0,0,1,1,1} = 7 ่ H

M₉ บ 1271 . 3 mod 1889 = 35

factoring 35 into S ′ ่ gives binary vector {0,1,0,0,0} = 8 ่ I

M₁₀ บ 2677 . 3 mod 1889 = 475

factoring 475 into S ′ ่ gives binary vector {1,0,0,1,1} = 19 ่ T

M₁₁ บ 2013 . 3 mod 1889 = 372

factoring 372 into S ′ ่ gives binary vector {0,0,1,0,1} = 5 ่ F

M₁₂ บ 1271 . 3 mod 1889 = 35

factoring 35 into S ′ ่ gives binary vector {0,1,0,0,0} = 8 ่ I

M₁₃ บ 2679 . 3 mod 1889 = 481

factoring 481 into S ′ ่ gives binary vector {0,1,0,1,1} = 11 ่ L

M₁₄ บ 653 . 3 mod 1889 = 70

factoring 70 into S ′ ่ gives binary vector {0,0,1,0,0} = 4 ่ E

M ่ S E N D S E C H I T F I L E

(b) Use the above public key to send the message ONETHOUSAND.

S = {1269, 1271, 653, 48, 1360}

ONETHOUSAND ่ 14, 13, 4, 19, 7, 14, 20, 18, 0, 13, 3

่₂ 01110, 01101, 00100, 10011, 00111, 01110, 10100, 10010, 00000, 01101, 00011

่ 1972, 3284, 653, 2677, 2061, 1972, 1922, 1317, 0, 3284, 1408

12. (5 Marks)

An RSA cipher system has a modulus of n=71257651313, encryption key e=315479. A cryptogram C= 28193496995 was received by you.

Calculate the decryption key (d) and retrieve the message (m).

Hint: Use Fermat factorisation to determine p and q.

n = 71257651313, √71257651313 = approx 266941.3

let t = 266942, let z = t² – n

t = 266942, z = 266942² – 71257651313

= 380051, not perfect

t = 266943, z = 266943² – 71257651313

= 913936, perfect

√913936 = 956, let s = z, n = t² – s² = (t + s)(t – s)

thus 71257651313 = 266943² - 956²

= (266943 + 956)(266943 – 956)

= (267899)(265987)

factors are 267899 and 265987

p = 267899, q = 265987, n = pq = 71257651313

e = 315479

C = 28193496995

φ(n) = (p – 1)(q – 1)

φ(71257651313) = 267898 . 265986 = 71257117428

d = e^-1 mod φ(n)

= 315479^-1 mod 71257117428

= 31819832483

M = C^d mod n

= 28193496995^31819832483 mod 71257651313

= 315296

13. (6 marks)

Using an RSA cipher, suppose that both plaintexts and ciphertexts consist of trigraph message units, but while plaintexts are written in the 27-letter alphabet (consisting of A-Z and blank = 26), ciphertexts are written in the 28-letter alphabet obtained by adding the symbol "/" (with numberical equivalent 27) to the 27-letter alphabet. We require that each user A choose n_A between 27³ = 19683 and 28³ = 21952, so that a plaintext trigraph in the 27-letter alphabet corresponds to a ciphertext trigraph in the 28-letter alphabet.

(a) If your deciphering key is K_D = (n,d) = (21583,20787), decipher the

message "YSNAUOZHXXH " (one blank at the end).

n = 21583, d = 20787, display blank character as “_”

let C = C₁, C₂, C₃, C₄, where each C_i is a tuple of three characters

values C₁, C₂, C₃, C₄ are in a 28 character alphabet

RSA decryption m = c^d mod n

C₁ = YSN = 24 . 28² + 18 . 28 + 13 = 19333

M₁ = 19333²⁰⁷⁸⁷ mod 21583 = 13649

= m₁₍₁₎ 27² + m₁₍₂₎ 27 + m₁₍₃₎

= 18 . 27² + 19 . 27 + 14 = STO

C₂ = AUO = 0 . 28² + 20 . 28 + 14 = 574

M₂ = 574²⁰⁷⁸⁷ mod 21583 = 11652

= m₂₍₁₎ 27² + m₂₍₂₎ 27 + m₂₍₃₎

= 15 . 27² + 26 . 27 + 15 = P_P

C₃ = ZHX = 25 . 28² + 7 . 28 + 23 = 19819

M₃ = 19819²⁰⁷⁸⁷ mod 21583 = 660

= m₃₍₁₎ 27² + m₃₍₂₎ 27 + m₃₍₃₎

= 0 . 27² + 24 . 27 + 12 = AYM

C₄ = XH_ = 23 . 28² + 7 . 28 + 26 = 18254

M₄ = 18254²⁰⁷⁸⁷ mod 21583 = 3286

= m₄₍₁₎ 27² + m₄₍₂₎ 27 + m₄₍₃₎

= 4 . 27² + 13 . 27 + 19 = ENT

Message ่ STOP_PAYMENT

(b) If in part (a) you know that f(n) = 21280, find

(i) e = d^-1 mod f(n), and

e = 20787^-1 mod 21280

= 6043

(ii) the factorization of n.

n = 21583, √21583 = approx 146.9, let t = 147

let z = t² – n

t = 147, z = 147² – 21583 = 26, not perfect

t = 148, z = 148² – 21583 = 321, not perfect

t = 149, z = 149² – 21583 = 618, not perfect

t = 150, z = 150² – 21583 = 917, not perfect

t = 151, z = 151² – 21583 = 1218, not perfect

t = 152, z = 152² – 21583 = 1521, perfect

√1521 = 39, let s = z, n = t² – s² = (t + s)(t – s)

thus 21583 = 152² – 39²

= (152 + 39)(152 – 39) = (191)(113)

factors are 191 and 113

Note that the method for converting characters into numbers used in this question is

applied as follows:

Digraphs: C = c₀c₁ = n₀b + n₁ = N

Trigraphs: C = c₀c₁c₂ = n₀b² + n₁b + n₂ = N

where C is the character-tuple consisting of characters c_i , n_i is the numerical

representation of the character c_i , b is the size of the encoding alphabet, and N is the

resulting numerical value of the C character-tuple. For example, using a 40-letter

alphabet, to convert ABC to a number: C = ABC = 0 * 40² + 1 * 40 + 2 = 42 = N

14. (6 marks)

In the field Z₄₀₉ determine which of the following are generators of the multiplicative group:

p = 409, thus p – 1 is 408 = 2³ . 3 . 17, p₁ = 2, p₂ = 3, p₃ = 17

h(1) = (p – 1)/p₁ = 204

h(2) = (p – 1)/p₂ = 136

h(3) = (p – 1)/p₃ = 24

if x^h(i) บ 1 mod p for any i = 1..3 then x is NOT a generator in Z₄₀₉

(i) 2

2²⁰⁴ บ 1 mod 409

่ 2 is NOT a generator in Z₄₀₉

(ii) 7

7²⁰⁴ บ 408 mod 409

7¹³⁶ บ 53 mod 409

7²⁴ บ 1 mod 409

่ 7 is NOT a generator in Z₄₀₉

(ii) 29

29²⁰⁴ บ 408 mod 409

29¹³⁶ บ 53 mod 409

29²⁴ บ 216 mod 409

่ 29 is a generator in Z₄₀₉

15 (9 marks)

Let p be the prime 1058041.

(i) (2 marks)

Show that g=12 is not a generator of the nonzero integers

modulo 1058041 under multiplication.

Let g be a generator of the field Z_p

if {x^k : k is an integer} = Z_p-0

p = 1058041

ฎ p-1 = 1058040 = 2³.3².5.2939

ฎ h(1) = (p-1)/2 = 529020

h(2) = (p-1)/3 = 352680

h(3) = (p-1)/5 = 211608

h(4) = (p-1)/2939 = 360

Is 12 a generator?

12^h(1) บ 1 mod p

ฎ 12 is not a generator of Z_p

(ii) (4 marks)

Suppose that Alice and Bob select secret keys a=2783 and b=8059

respectively. Outline a procedure for Alice and Bob to exchange key g^ab

using the Diffie-Hellman discrete log cipher.

Public knowledge is:

large prime p = 1058041

g = generator of integers modulo p

Alice and Bob wish to generate a common key over an insecure channel

Alice generates a modulo p ่ 2783 mod 1058041

Bob generates b modulo p ่ 8059 mod 1058041

Alice calculates g^a ่ g²⁷⁸³ and sends value to Bob

Bob calculates g^b ่ g⁸⁰⁵⁹ and sends value to Alice

Alice determines secret common key

(g^b)^a mod p ่ (g⁸⁰⁵⁹)²⁷⁸³ mod 1058041 ่ g³⁴⁶⁰

Bob determines secret common key

(g^a)^b mod p ่ (g²⁷⁸³)⁸⁰⁵⁹ mod 1058041 ่ g³⁴⁶⁰

This procedure doesn’t prevent man-in-the-middle attack, additional authentication required to prevent such an event.

(iii) (3 marks)

Suppose that Bob and Alice decide to exchange messages using the

ElGamal cipher where Alice selects the same secret key, a, as given

in (ii) above and the public key g^a. Suppose Bob encrypts the

message m, which is an integer between 0 and p-1, using Alice's

public key g^a.

Suppose Alice receives the pair (mg^ak, g^k) = (477738, 88884).

Use Alice's private key, a, to decrypt (477738, 88884) to recover

the message m.

a = 2783

p = 1058041

(mg^ak,g^k) = (477738,88884)

g^ak = (g^k)^a = 88884^a บ 937112 mod p

m = mg^ak(g^ak)^-1 บ 477738 * 937112^-1 mod p

บ 766240 mod p

16. (4 marks)

Bob and Alice decide to set up a digital signature in a communications network using the ElGamal cipher over the integers modulo p=700001 with generator g=12. Alice selects the secret key a=13579. p and g^a=55058 are Alice's public keys.

Suppose Alice wants to send the message m=24680 to Bob. Alice selects k=57683.

Outline the protocol required for Alice to attach a signatures to the message which is being transmitted to Bob. Include Bob's verification.

p = 700001, g = 12, a = 13579, g^a = 55058

m = 24580, let hash function be trivial function such that h = f(m) = m

k = 57683

check that k is relatively prime to p – 1

gcd(k, (p – 1)) = 1

gcd(57683, 700000) = 1

Alice calculates r and s signature pair

r = g^k mod p

= 12⁵⁷⁶⁸³ mod 700001 = 583276

h = g^k . a + k . s mod (p – 1)

24680 = 12⁵⁷⁶⁸³ . 13579 + 57683 s mod 700000

24680 = 504804 + 57683 s mod 700000

219876 = 57683 s mod 700000

219876 (57683)^-1 = s mod 700000

219876 (48347) = s = 144972

Alice sends m,r,s to Bob

Bob verifies and accepts as valid if g^h mod p = (g^a)^r . r^s mod p

12²⁴⁶⁸⁰ mod 700001 = 55058⁵⁸³²⁷⁶ . 583276¹⁴⁴⁹⁷² mod 700001

94164 mod 700001 = 663126 . 387518 mod 700001

= 94164 mod 700001

17. (12 marks)

Let E denote the set of points (x,y) such that y² = x³ + x + 1 over the integers mod 19.

E(Z₁₉) = {(x,y): y² = x³ + x + 1} U {φ}, a = 1, b = 1, all calculations in Z₁₉

(i) Find all the distinct points on E. (2 marks)

look at all x ε Z₁₉, calculate z = x³ + x + 1 (mod 19), if it has a Quadratic Residue mod 19, then can solve for y

Quadratic Residue test z^(p-1)/2 บ 1 mod p ่ z⁹ บ 1 mod 19

let x = 0, z = 1, is Quadratic Residue mod 19, y = 1, 18

x = 1, z = 3, not QR

x = 2, z = 11, QR, y = 7, 12

x = 3, z = 9, QR, y = 3, 16

x = 4, z = 15, not QR

x = 5, z = 17, QR, y = 6, 13

x = 6, z = 14, not QR

x = 7, z = 9, QR, y = 3, 16

x = 8, z = 8, not QR

x = 9, z = 17, QR, y = 6, 13

x = 10, z = 4, QR, y = 2, 17

x = 11, z = 3, not QR

x = 12, z = 12, not QR

x = 13, z = 7, QR, y = 8, 11

x = 14, z = 4, QR, y = 2, 17

x = 15, z = 9, QR, y = 3, 16

x = 16, z = 9, QR, y = 3, 16

x = 17, z = 10, not QR

x = 18, z = 18, not QR

Points on E are: (0,1), (0,18), (2,7), (2,12), (3,3), (3,16), (5,6), (5,13), (7,3), (7,16), (9,6), (9,13), (10,2), (10,17), (13,8), (13,11), (14,2), (14,17), (15,3), (15,16), (16,3), (16,16), (φ)

(ii) Let P = (17,4) and Q = (11,3). Find 2P and P + Q. (6 marks)

let P = (17,4), x₁ = 17, y₁ = 4

2P = (x₂,y₂)

λ = (3x₁² + a)(2y₁)^-1

= (12 + 1)(12) = 4

x₂ = λ² – 2x₁

= 16 – 15 = 1

y₂ = λ (x₁ – x₂) – y₁

= 4 (17 – 1) – 4 = 3

Thus 2P = (1,3)

let P = (17,4), x₁ = 17, y₁ = 4

let Q = (11,3), x₂ = 11, y₂ = 3

P + Q = (x₃,y₃)

λ = (y₂ – y₁)(x₂ – x₁)^-1

= (3 – 4)(11 – 17)^-1 = 16

x₃ = λ² – x₁ – x₂

= 9 – 17 – 11 = 0

y₃ = λ (x₁ – x₃) – y₁

= 16 (17 – 0) – 4 = 2

Thus P + Q = (0,2)

(iii) For P defined above, find the set of all points H={ kP : k is a positive integer}

(4 marks)

P = (17,4), let x₁ = 17, y₁ = 4

2P = (1,3), let x₂ = 1, y₂ = 3

3P = P + 2P

λ = (y₂ – y₁)(x₂ – x₁)^-1

= (3 – 4)(1 – 17)^-1 = 6

x₃ = λ² – x₁ – x₂

= 17 – 17 – 1 = 18

y₃ = λ (x₁ – x₃) – y₁

= 6 (17 – 18) – 4 = 9

่ 3P = (18,9)

4P = P + 3P

λ = (y₃ – y₁)(x₃ – x₁)^-1

= (9 – 4)(18 – 17)^-1 = 5

x₄ = λ² – x₁ – x₃

= 6 – 17 – 18 = 9

y₄ = λ (x₁ – x₄) – y₁

= 5 (17 – 9) – 4 = 0

่ 4P = (9,0)

5P = P + 4P

λ = (y₄ – y₁)(x₄ – x₁)^-1

= (0 – 4)(9 – 17)^-1 = 10

x₅ = λ² – x₁ – x₄

= 5 – 17 – 9 = 17

y₅ = λ (x₁ – x₅) – y₁

= 10 (17 – 9) – 4 = 0

่ 5P = (17,0)

6P = P + 5P

λ = (y₅ – y₁)(x₅ – x₁)^-1

= (0 – 4)(17 – 17)^-1 = ?

0^-1 is not defined, P = (17,4) is not a generator in Z₁₉