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/2t
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 = memod N
Decryption m= Cd 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.