8.7.4:

>>> factoring.factor(899) # find p, q

[29, 31]

>>> 28*30 # (p-1)*(q-1)

840

>>> from xgcd import xgcd

>>> xgcd(11, 840) # find inverse of 11 mod (p-1)(q-1)

(1, -229, 3)

>>> -229 % 840 # positve representative for secret key

611

>>> pow(468, 611, 899) # decrypt

13

>>> pow(13, 11, 899) # check - OK

468

so the answer is 13

8.7.10: A bit of a challenge since the algorithm is not given to you. You know m to two powers, e1 = 3; e2 = 5,and you want the power 1. How to combine these exponents and get 1? sounds like xgcd in general: Hopefully 1 = a*e1 + b*e2 In this case it is easy:

1 = 2*3 - 5;

m

>>> from mod import Mod

>>> Mod(293, 493)**2/421

Mod(47, 493)

>>> pow(47, 3, 493) # check answer 47

293

>>> pow(47, 5, 493) # double check answer 47

421

Answer 47

8.7.20:

The book does not give Alice's public key, so I modified the problem statement to include it: A = 26. You still need her private key to decrypt. Since p = 43 is small, we can solve the discrete log problem by brute force:

>>> from PohligHellman import discreteLogModP

>>> g = 3

>>> p = 43

>>> B = 30

>>> c = 7

>>> A = 26

>>> discreteLogModP(g, A, p)

17

>>> a = 17

>>> c*pow(B, p-1-a, p) % p # calc message

23

>>> m=23 # this is the answer

>>> discreteLogModP(g, B, p) # check - need B's private key

11

>>> b = 11

>>> m*pow(A, b, p) % p # confirm get c

7

Requested answer for the message was 23

15.3.2:

a(x) = 3 + 2x; get

x f(x)

1 5

2 7

3 9

4 0

Extra Review problem solutions

1&2. Most elements of an elliptic group are paired, allowing (x, +y) and (x, -y), but the identity (point at infinity) is always an element, and it is not paired. It is also possible for y to be 0, and (x, 0) is not paired, since +0 = -0. A few tries for me with findE yielded a group with 6 elements. Continuing I get 7 elements for problem 2. I chose 7 as the modulus, since the number of group elements is on the order of the prime modulus:

Enter a prime modulus: 7

Enter polynomial modulus or just enter:

a b:1 3

6 elements:

0

(4, 6) (4, 1)

(5, 0)

(6, 6) (6, 1)

a b:3 5

7 elements:

0

(1, 3) (1, 4)

(4, 5) (4, 2)

(6, 6) (6, 1)

3. 21-1 = 20= 2*2*5 test powers d = 5 and 2*d

>>> a =13

>>> d = 5

>>> n = 21

>>> pow(a, d, n) # result neither 1 nor -1

13

>>> pow(a, 2*d, n) #result not -1

1

4.

- A to B: 1037; B to A: 0; A to B: 1000; 1000**2 % n = 1037 OK

- A to B: 381; B to A: 1; A to B: 434; 434**2 = 381*776 mod n OK

- A to B: 691; B to A: 1; A to B: 733; 733**2 = 691*776 mod n OK

- A to B: 711; B to A: 0; A to B: 304; 304**2 % n != 711 REJECT

- A to B: 879; B to A: 1; A to B: 55; 55**2 != 879*776 mod n REJECT