CS 526 Fall 2004
Assignment 1 Solutions
Note:
The points add to 8.0 for a correct
homework.
Please see Ferit Erin for any questions about
grading and answers first.
Q1)
9.8.11
a)
If p is a prime, Φ (p) = p1.
The
residue set Zp = {0, 1,
, p-1}
Note
that except for 0, p is relatively prime to
each element in Zp.
Hence Φ (p) = p1
b)
If p and q are primes, Φ (pq) = (p-1)(q-1).
The
residue set is Zpq = {0, 1,
, pq-1}
A
number that is a multiple of p or q is not relatively prime to pq. Hence, elements of sets
{p, 2p, 3p, .., (q -1)p}
and {q, 2q, 3q,
, (p -1)q} are not
relatively prime to pq. Also
note that 0 is not relatively prime to pq.
Hence
Φ(pq) = pq
[(q-1) + (p-1) + 1]
= pq q + 1 p
+ 1 1
= pq q p
+ 1
= p(q-1)
(p-1)
= (p-1)(q-1)
Any answer in those lines is acceptable.
Part a) is 0.5 points.
Part b) is 1 point.
Note from TA: Many students used the
theorem Φ(pq)= Φ(p) Φ(q) without giving
the proof of it. What we wanted you to do were giving a full proof. Using some
other theorems without proving them caused you to lose points.
Q2)
a. k0 Є Zm*and gcd(k1,26)=1. Hence number of possible a values is Φ(m)
Φ(m) = Φ(26) = Φ(2*13) = (2-1) * (13-1) = 12
Number of possible keys = m Φ(m) = 26 * 12
b. f(a) = (k1a+k0) mod 26
f(8) = 21 -> 8k1+ k0 ≡ 21 mod 26 (eq1)
f(1) = 7 -> k1+ k0 ≡ 7 mod 26 (eq2)
-
7k1 = 14 mod 26 -> k1 = 2 mod 26
Setting k1 into eq2 we get:
2 + k0 = 7 mod 26
k0 = 5 mod 26
->f(m) = (2m+ 5) mod 26
OR
f(a) = (k1a+k0) mod 26
f(8) = 21 -> 8k1+ k0 ≡ 21 mod 26 (eq1)
f(0) = 7 -> k0 ≡ 7 mod 26 (eq2)
Setting k0 into eq1 we get:
8k1 + 7 = 21 mod 26
8k1 = 14 mod 26
k1 = 5 mod 26
-> f(m) = (5m+ 7) mod 26
Any answer in those lines is acceptable.
Part a) is 0.5 points.
Part
b) is 1 point.
Q3)
Assume ab ≡ 1 mod (LCM(p-1,q-1))
Since LCM (p-1,q-1) is k(p-1) and l(q-1) for some k,l Є N.
ab = k*d*(p-1) + 1 and ab = l*f*(q-1) + 1 for some d,f Є Z
Xab = Xk*d*(p-1)+ 1≡ X mod p .
and
Xab = Xl*f*(q-1)+ 1≡ X mod q by Eulers Thm
-> Xab ≡ X mod p
and
Xab ≡ X mod q
->Xab ≡
sp + X = tq + X for some s,t Є N, where sp=tq
p | tq and gcd(p,q)=1 -> p | t -> t = zp for some z Є N
Hence
Xab ≡ tq
+ X ≡ zpq + X -> Xab
≡ X mod pq
Any answer in those lines is acceptable.
1,5 points
Q4)
Verification Protocol
Protocol. A and B verify that they possess a common key K, using a public one-way function h.
|
i.
A sends h(h(K))
to B. ii.
B verifies that the received value is correct. iii.
B sends h(K) to
A. iv.
A verifies that the received value is correct. |
|
|
a.Why not have A send h(K) to B and then have B send h(h(K)) to A?
Then C (Carlos) could pretend to be B: since h is public, C could calculate h(h(K)) and send this to A.
b.What keeps C from intercepting A's transmission of h(h(K)) and then sending h(K) back to A (assuming C doesn't know K)?
If C doesn't know K, then a knowledge of h(h(K)) does not allow one to calculate h(K), because h is a
one-way function.
Any answer in those lines is acceptable.
1 point each
Q5)
a)
m = 0
c = 0e
mod n = 0
\m = c
b)
m = 1
c = 1e
mod n = 1
\m = c
c)
m = n
1
Use
induction to show that for all odd e the result holds.
Basis:
for e = 1
c = (n-1)1
mod n
c = (n-1)
for e = 3
c =
(n-1)3 mod n
c =
(n3-3n2 +3n-1) mod n
c =
0 0 + 0 + (-1 mod n) [because: (any power of n) mod n =
0]
c =
(-1) mod n
c =
n -1
Hypothesis:
true for e, where e is odd
i.e. m = (n-1)
c = (n-1)e mod n = (n-1)
Show,
it is true for e + 2 (next odd value!)
m =
(n-1)
c =
(n-1)e * (n-1)2
mod n
c =
[((n-1)e mod n) * ((n-1)2
mod n)] mod n
c =
[((n-1) mod n) * ((n-1)2 mod n)] mod n
c = (n-1)3
mod n
c = (n-1)
Another
approach is to use expansion of (n-1)e
= ne + c1ne-1
+
. + cmn
+ (-1)e
for some constants c1, c2,
, cm.
It is
important to understand that e is odd. Here is how:
Note:
n = pq is
odd, as p and q are prime numbers (hence odd numbers)
Hence,
Φ(n) = (p-1) (q-1)
is an even number, as both (p-1) and (q-1) are even numbers.
e <
n is chosen to be relatively prime to f (n), and hence, e
is odd!!
Any answer in those lines is acceptable.
Part a) 0.35 points
Part b) 0.35 points
Part c) 0.8 points