CT30A8800 - Secured Communications Exercise
Weeks 37 - 42
Thursdays 1200 - 1400hrs
Location : ML 6325
Email : were.oyomno[at]lut.fi

# Exercises 2009 - 2010

Attempt the following questions before the exercise and be ready to present your solution. In the presentation emphasise parts of the solution you considered elemental for the result. On the programming questions, Python is the recommended programming language. Python is well documented with sufficient libraries that will prove beneficial later on.

### Exercise 1 : 15.09.2009

##### Maths
1. Find the greatest common divisor (GCD) for 18 and 30 using euclidean algorithm. ($\frac{1}{4}$ point)
2. Find inverse for the number 123 in mod 1003. ($\frac{1}{4}$ point)
3. Find all solutions for $12x\equiv28 mod 236$. ($\frac{1}{2}$ point)

($\frac{1}{2}$ point each)

1. Create a program that randomly selects two numbers that are between 19 - 99999 and then finds out their (GCD).
2. Create a program that randomly selects two numbers that are between 7 - 77777 and then finds out if the numbers are relatively prime.

### Exercise 2 : 17.09.2009

1. Using pen and paper find out whether 5 is primitive root for prime number 17? ($\frac{1}{2}$ point)
2. Using pen and paper find out if 5 is primitive to prime number 11? ($\frac{1}{2}$ point)
• Get familiar with using big numbers in programming.
1. Create a program that generates two random numbers that are between 0 and 2^63 and then finds their GCD. ($\frac{1}{2}$ point)
2. Create a program that generates random numbers that is between 0 and 2^63 and checks if the given number is prime. If the random number is not prime, your program should seek out the next prime number. ($\frac{1}{2}$ point)

### Exercise 3 : 24.09.2009

1. Create a program that randomly selects a number x between 7 - 7777777 and then returns the integer value of 4 lsb (least significant bits) of x ($\frac{1}{2}$ point)
2. Create a program that calculates inverse of 7 mod n by using both extended euclidean algorithm and then fermat's theorem. ($\frac{1}{2}$ point)
• Use a random function to get value for n
• Compare the speed of these two solutions for finding inverse when n is of size 2^8 and 2^32
3. Create a program that calculates 7P when P (1,3) is point at elliptic curve e $y^{2}\equiv_{}x^{3}+24x+13 (mod 29)$. ($1$ point)

### Exercise 4 : 01.09.2009

1. Familiarize yourself with different solutions to find out primitive (root) for certain number (for example searching algorithms from mathematics or looking source code of crypto software that requires primitive root). Create program that creates a random number p that is size of $2^{n}$ (i.e. p is n bit long) and finds primitive root mod p, when n is 10. Test how big value n can be, in order for your program to find the primitive root for p in less than 5 minutes. (e.g How many bits p can be) ($1$ point)
• Potential efficient solution for this task
2. Create a program that generates modulus n for RSA. P and Q should be random primes that are bigger than $2^{64}$. Let your application then read data from file and divide that data to proper size blocks for RSA. Print n, the size of block in bits and the numerical value of the block, when all bits in block are 1. (i.e. if the block is 4 bits long then you should print n, 4 and 15 (0b1111=15) ($1$ point)

### Exercise 5 : 08.10.2009

1. Create a very simple and insecure “block cipher”. The cipher takes in 64 bits and uses 64 bit key. The incoming block is first XOR:ed with the key. The result of XOR is put in to 8×8 matrix and then read column-wise starting from upper right corner (i.e. bit order is now 8,16,24,32,40,48,56,64,7,15,23,31…). the result is the output of the cipher. During decryption put the bits in an 8×8 matrix and read column-wise starting from lower left corner, then XOR with the key. ($2$ points)
• Combine/chain the blocks from previous cipher using
• CBC
• CFB

### Exercise 6 : 15.10.2009

1. Using existing implementation of hash algorithms (e.g. sha*, md5 etc) create a program that calculates at least 256 bit hash value from a random message. This program should calculates the MAC for random message. The key for MAC creation should be the ASCII word: “communication” ($2$ points)