Practical

Objective: Understand Coding, RSA and related issues.

1. Implement the Extended Euclidean Algorithm using C/C++ or Java. The objective is to find the inverse modular for a number. The input is two numbers (a n) and the output is a number b satisfying

ab modn =1

if this number exists. Otherwise present an error information. (Hint: first implement the algorithm of finding the greatest common divisor for two numbers).

2. A smudge has obscured one of the digits of the ISBN code

0-8018-x 073-1.

Determine the unknown digit x.

3. Implement the following prime number test algorithm (Called Lehmann Algorithm) in C/C++ or Java. To test whether a number p is a prime number

Choose a random number a being less than p

- Calculate r = ap^-1/2 mod p

- If r is not 1 or -1 then p is definitely not a prime.

- If r=1 or -1 the likelihood that p is not prime is at most than 50 percent.

Repeat this algorithm t times, if the calculation equals to 1 or -1 but does not always equal to 1, then p is probably prime with an error rate of 1 in 1/2^t

4. The following is the description of RSA

Public Key

N=pq ( p q are prime numbers but keep secret), e is relative prime to (p-1)(q-1)

Private Key d = e^-1mod (p-1)(q-1)

Given message m

Encryption c = m^emod N

Decryption m= C^d mod N

If message m>n, we usually split m into several small blocks with each block less being than n.

In this algorithm, if we given p=47, q=71, e=79, m=682534127893. Solve d using question 1 in this practical and do encryption and decryption for m.