Online Assignment Service

Menu
WhatsApp

Practical Cryptology, IT754A, 7,5hp

Home-take Examination 1

Instruction

This home-exam must be done individually. Copying others complete or partial work is strictly prohibited. You may, of course, discuss the problems with fellow students,

  • but you should work on the solutions independently.

 

The solutions should be written in a word processor program or a program like LaTeX and your work should be submitted as a PDF le. Your work should be well-structured and justi ed, as well as they should be easy to read.

 

If you use a computer program to solve some tasks, a program listing together with

  • the documentation of the program code should be provided as Appendix.

 

You need to make an own e ort to solve the tasks. Utilizing online available tools or algorithms as part of your work is strictly prohibited.

Examination tasks

  1. For this task, you will be doing some modular arithmetic. You may use a calculator or a computer program to simplify the computations. But you need to justify how

 

it is done.                                                                                                                                          (1 pts/task)

 

  • Suppose that a and b are integers such that a 34 (mod 83) and b 21 (mod 83). Find an integer c such that 0 c < 83 such that

 

47c    (53a 2 + b5)    (mod 83)

 

  • Determine the greatest common divisor of 12852 and 30576.

 

  • Solve the congruence equation 33x + 47 = 21 in F59.

 

  • Find an x such that 0 x < 126 and x   22022  (mod 127).
  1. One approach to increase the security of a symmetric algorithm is to apply the same cipher several times. One example is considering how 3DES is obtained from DES and o ers a considerably secured cryptographic system. For this task, we shall test this approach on A ne cipher. All computation is is done modulo 26 and standard

 

ordering of the English alphabets where A $ 0; B $ 1; ; z $ 25 are used. (2 pts/task)

 

Assume that we have three a  ne ciphers

 

ek1(x) = a1x + b1      ek2(x) = a2x + b2        ek3(x) = a3x + b3:

 

There is a single a ne cipher ek(x) = ax + b which performs exactly the same encryption (and decryption) as the combination ek3(ek2(ek1(x))).

 

  • Choose appropriate key for the a ne ciphers ek1; ek2 and ek3 from the key space of f0; 1; 2; : : : ; 25g. Justify your choice of the key. Find the key k = (a; b) that corresponds to the a ne cipher ek(x) = ax + b.

 

  • Encrypt your initials in two ways:

 

  1. rst using the a ne cipher ek1; the result with ek2; and the result with ek3.
  2. using the a ne cipher ek.

 

  • Find a formula for the key pair (a; b) based on the keys (a1; b1), (a2; b2) and (a3; b3).

 

  • Does this encryption system enhances the security of the a ne cipher? Justify your motivation.
  1. For this task you are going to generate a key and use stream cipher. (2 pts/task)

 

  • Use the quadratic residue pseudorandom generator (BBS)on the prime numbers p and q of your choice, where 5000 < p; q < 9000, to generate the rst ve bits of your key k0; k1; k2; k3 and k4.

 

  • Generate a key sequence of length 40 by using the recurrence relation

 

xn+5 = xn+4 + xn+2 + xn+1 + xn       (mod 2);       n       0

 

where the initial values are the key generated in (a).

  • Encode your last name by using the ASCII code. Use the stream cipher and the key you generated above to encrypt your last name.
  1. We want to perform an attack on an LFSR-based stream cipher. English letters and the numbers 0; 1; 2; 3; 4; 5 are represented by a 5-bit vector according to the following mapping:

 

0$0=00000

 

1$1=00001

 

2$2=00010

...

 

5$5=00101

 

a $ 6 = 00110

 

b $ 7 = 00111

...

 

z $ 31 = 11111

 

We happen to know the following fact about the system.

 

The degree of the LFSR is m = 4.

 

  • The message starts with the string weh. We obtained the following ciphertext:

 

m1zugjca3fa0jzremxm

 

Answer the following tasks.                                                                                                  (2pts/task)

 

  • Determine the initialization vector.

 

  • Determine the feedback coe cients for the LFSR.

 

  • Decrypt the ciphertext.
  1. We may generalize the A ne cipher to a Hill cipher, in which the plaintext x, the cipher text y, and the second part of the key b are column vectors consisting of m numbers modulo n. The rst part of the key a is an invertible matrix of size m m. The encryption and decryption algorithm for Hill cipher is similar to that of the a ne cipher:

 

ek(x) = ax + b                (mod n)             and     dk(y) = a 1(y  b)           (mod n):

 

For this task, Bob and Alice wants exchange message over eld Z29 by using the standard ordering of English alphabets, where a $ 0; b $ 1; : : : ; z $ 25 followed by

 

 

0

 

!$26;

;$ 27

and

?$28:

1

 

 

5

6

17

7

23

1

 

 

 

0

15

 

 

B

3

12

7

0

11

C

 

 

 

B

8

C

 

Use the key  =

9

3

2

11

8

and

 

=

9

.

 

B

 

 

 

 

 

C

 

 

 

B

 

C

 

a

B

1

12

4

5

19

C

 

b

 

B

10

C

 

 

12

1

0

21

27

 

 

 

23

 

 

B

 

 

 

 

 

C

 

 

 

B

 

C

 

 

@

 

 

 

 

 

A

 

 

 

@

 

A

 

 



  • Encrypt the message: Hi, Can we meet tonight? Only the letters and symbols should be encrypted.

 

  • Determine the matrix a 1 used for decryption.

 

(c) Decrypt the ciphertext: miyslfdubrqdivxin?qs.                                             (2pts/task)