cis 428/628 - introduction to cryptography - spring 2009

background for quiz 2

i. terminology

1. asymmetric cryptosystem
2. birthday attack
3. bit commitment
4. cipher block chaining
5. cipher block feed back
6. Chinese Remainder Theorem
7. chosen plaintext attack
8. collision-free
9. congruence class
10. discrete log
11. double encryption
12. electronic codebook
13. Euler's Theorem
14. Euler's phi function
15. extended g.c.d.
16. existential forgery
17. Fermat's Little Lemma
18. finite field
19. hash function
20. index of coincidence
21. message digest
22. one-time pad
23. one-way function
24. prime number theorem
25. primitive root
26. pseudoprime
27. RSA signature

ii. number theory

Here are some sample problems.

1. Suppose p is a prime and a and b are numbers such that a * b == 0 (mod p). Show that a == 0 (mod p) or b == 0 (mod p).
   
   
2. Suppose p is an odd prime. Show that the only solutions to x² == 1 (mod p) are 1 and p-1. (Hint: consider (x+1)(x-1) == 0 (mod p) and use the previous problem.)
   
   
3. Let p be a prime. Show that a^p == a (mod p) for all a.
   
   
4. Andrews exercise 5 on page 64.
   
   
5. Andrews exercise 6 on page 64.
   
   
6. Andrews exercise 8 on page 64.
   
   
7. Suppose Alice's public RSA key is (n,e). Also suppose that instead of choosing n=p*q (where p and q are prime), Alice goofs and chooses n = p (where p is some prime). Show that Eve can easily decrypt Alice's messages.

questions from a previous year's quiz 2

Problem 1 (9 points)

a. birthday attack

b. discrete log

c. message digest

[show answer]

Problem 2 (3 points)

[show answer]

Problem 3 (8 points)

1. (4 points) Show that a^p-2 = a^-1 (mod p), where p is an odd prime.
2. (4 points) Show that n⁵ and n have the same ending decimal digit, where n>0.
3. (4 points) Suppose (n,p,q,e,d) is Alice's RSA key, so

   encrypt_A(m) = m^e (mod n)

   is Alice's public encryption function. Show that

   encrypt_A( (m1 * m2) mod n )   ≡   (encrypt_A(m1)*encrypt_A(m2))   (mod n).

   for every m1 and m2 in Z_n^*.

[show answer]

number theory and crypto facts given on the quiz

The binomial theorem. For n>0 and x,y in Z:

(x+y)ⁿ = xⁿ + C(n,1) * x^n-1y¹ + C(n,2) * x^n-2y² + … + C(n,n-1) * x¹y^n-1 + yⁿ,

Theorem. For each a,b>0 we have that gcd(a,b) = min {xa+yb | x,y in Z & xa+yb>0 }.

Fermat's little lemma. Suppose p is a prime. Then for each integer a,   a^p-1 ≅ 1 (mod p).

Euler's theorem. Suppose n>1. Then for each a in Z_n^*,   a^phi(n) ≅ 1 (mod n).

Euler's corollary. Suppose n=p * q, where p and q are distinct primes. Then, for each integer a,   a^phi(n)+1 ≅ a (mod n).

The multiplication table for Z₁₁^*.

  *    1    2    3    4    5    6    7    8    9   10
  1    1    2    3    4    5    6    7    8    9   10
  2    2    4    6    8   10    1    3    5    7    9
  3    3    6    9    1    4    7   10    2    5    8
  4    4    8    1    5    9    2    6   10    3    7
  5    5   10    4    9    3    8    2    7    1    6
  6    6    1    7    2    8    3    9    4   10    5
  7    7    3   10    6    2    9    5    1    8    4
  8    8    5    2   10    7    4    1    9    6    3
  9    9    7    5    3    1   10    8    6    4    2
 10   10    9    8    7    6    5    4    3    2    1

Some values of phi(n)

  n       1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 
  phi(n)  1  1  2  2  4  2  6  4  6   4  10   4  12   6   8   8

The RSA algorithm: Each user does the following.

• Picks to large, distinct primes p & q.
• Computes n=p * q and phi(n) = (p-1) * (q-1).
• Picks a random e in {1,…,phi(n)-1} with gcd(e,phi(n))=1.
• Computes d in {1,…,phi(n)-1} with d * e ≅ 1 (mod phi(n)).
• Publishes e and n.
• The values p, q, and d are kept private.

encrypt(m) = m^e (mod n) [public]
decrypt(c) = c^d (mod n) [private]