Cryptology Problems

To be discussed Wednesday, April 10, 1996.

1. Do problems 8.3 and 8.5 in the textbook. (You don’t need to know the MTI protocol; just the statement of the MTI problem as given on page 282.)

2. Factor 4386607, given ϕ(n) = 4382136.

3. (From Salomaa’s textbook) Let f(x) and g(x) be one-way functions. Give arguments to show that none of the functions f(x) + g(x), f(x) · g(x) and f(g(x)) is necessarily one-way. You may assume that specific function, which we have used in this course and assumed were one-way, are one-way functions.