cis 428/628 - introduction to cryptography - spring 2009

background for quiz 3

i. terminology

1. asymmetric cryptosystem
2. bit commitment
3. collision-free
4. Chinese Remainder Theorem
5. congruence class
6. existential forgery
7. hash function
8. index of coincidence
9. key agreement
10. key distribution
11. key exchange
12. one-way function
13. primitive root
14. pseudoprime
15. RSA signature
16. threshold scheme

ii. number theory

questions from a previous year's quiz 3

(with answers)

Problem 1 (9 points)

1. birthday attack

2. existential forgery

3. key exchange

[show answer]

Problem 2 (2 points)

[show answer]

Problem 3 (3 points)

1. 6⁵² mod 11

2. L₆(3)

3. L₆(2)

[show answer]

---

Do one of problems 4 and 5. If you do both, tell me which you want graded. In the following suppose that p is a prime and a is a primitive element of Z_p^*.

---

Problem 4 (6 points)

1. If gcd(k,p-1)>1, then a^k is not a primitive element of Z_p^*.

2. If gcd(k,p-1)=1, then a^k is a primitive element of Z_p^*.

[show answer]

Problem 5 (6 points)

1. If x is in QR(p), then -x is not in QR(p).

2. If x is not in QR(p), then -x is in QR(p).

[show answer]

number theory and crypto facts given on the quiz

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).

Definition.

Suppose n>1. QR(n) = {x in Z_n^* | for some y, x = y² (mod n)}. The elements of QR(n) are the quadratic residues modulo n.

Definition.

Suppose p is a prime and a is in Z_n^*. We say that a is a primitive element of Z_n^* when Z_n^* = {a⁰,a¹, a²,…,a^p-2} (or, alternatively, when p-1=min{k>0 | a^k== 1 (mod p)}).

Definition.

Suppose p is a prime and a is a primitive element of Z_n^*. For each x in Z_n^*, define L_aa(x) = the unique y in {0,1,…,p-2} such that a^y == x (mod p). L_a(x) is called the discrete log of x to the base a (mod p).

Theorem.

Suppose p is a prime and a is a primitive element of Z_n^*. For each x in Z_n^*, x is in QR(p) if and only if L_a(x) is even.

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]