CS547A Homework set #4

Due Tuesday November, 21 2000 in class at 14:30 SHARP

Exercises (from Stinson’s book)

• 4.5 •

Suppose that n = pq, where p and q are distinct odd primes and where a,b satisfy ab __=__ 1 (mod (p-1)(q-1)). The RSA encryption operation is e(x) = x^{b} mod n and the decryption operation is d(y) = y^{a} mod n. We proved that d(e(x)) = x if x in Z_{n}*. Prove that the same statement is true for any x in Z_{n}.

( NOTE: Z_{n }= { 0,1,2,…,n-1 } and Z_{n}* = { a in Z_{n} | gcd(a,n)=1 } )

HINT

Use the fact that x_{1} __=__ x_{2} (mod pq) if and only if x_{1} __=__ x_{2} (mod p) and

x_{1} __=__ x_{2} (mod q).This follows from the Chinese remainder theorem.

• 4.9 •

We give (yet another) protocol failure involving RSA. Suppose that three users in a network, say Bob, Bart and Bert, all have public encryption exponents b=3. Let their moduli be denoted by n_{1}, n_{2}, n_{3}. Now suppose Alice encrypts the same plaintext x to send to Bob, Bart and Bert. That is, Alice computes y_{i} = x^{3} mod n_{i}, i=1,2,3. Describe how Oscar can compute x, given y_{1}, y_{2} and y_{3}, without factoring any of the moduli. (!!!)

• 4.10 •

A plaintext x is said to be *fixed* if e_{K}(x) = x. Show that, for the RSA Cryptosystem,

the number of fixed plaintexts x Œ Z_{n}* is equal to gcd(b-1,p-1) x gcd(b-1,q-1).

HINT

Consider the system of two congruences e_{K} (x) __=__ x (mod p), e_{K} (x) __=__ x (mod q).

Other Exercises

Factoring

- Let
**n=p*q**, the product of two primes, such that**p>q**. - Deduce from (a) an efficient algorithm to factor RSA modulus for which
- Generalize this factoring method using products of the form
**ceiling((kn)**^{1/2}**) =(ap+bq)/2**for**n=p*q**and**k=a*b**for known**a,b**.

Show that if **p ^{1/2} **

**p ^{1/2} - q^{1/2} < 2^{1/2}**.

THE GREAT 2000 FACTORING CONTEST

Let

n:=999430920515432992637631559244159438923894644938854254750633464761577

15072060225693482667938136036447921189861080976495804134141569599326167

05066279005364723047157382432633314821460193215501784480779

find two primes **p,q** such that **n=p*q** and** |p|=|q|=100 **digits.

Pseudo-Random Permutation Generator

We say that { p_{k} : {0,1}^{n} -> {0,1}^{n} }_{k} is a *Pseudo-Random Permutation Generator* (PR**P**G) if it is a PR**F**G and each p_{k} is a permutation (a one-to-one function). Consider the following family of permutations { p_{k} : {0,1}^{2n} -> {0,1}^{2n} }_{k} defined from a Pseudo-Random Function Generator { f_{k} : {0,1}^{n} -> {0,1}^{n} }_{k }:

p_{k}(x,y) = [ y , x** xor **f_{k}(y) ]

- Show that p
_{k}(x,y) is indeed a permutation (a one-to-one function). - Show that { p
_{k}: {0,1}^{2n}-> {0,1}^{2n}}_{k}is not a PR**P**G. - Show that { p
_{k1,k2 }: {0,1}^{2n}-> {0,1}^{2n}}_{k1,k2}is not a PR**P**G. - Explain the relationship between these permutations and DES.
- Show how to compute their inverses p
^{-1}_{k}(x,y), p^{-1}_{k1,k2}(x,y), p^{-1}_{k1,k2,k3}(x,y). - Explain how Alice and Bob could share a secret key k1,k2,k3
_{ }and use both p_{k1,k2,k3 }and

Define similarly

p_{k1,k2}(x,y) = p_{k1}(p_{k2}(x,y))

p_{k1,k2,k3}(x,y) = p_{k1}(p_{k2}(p_{k3}(x,y))

It has been proven that { p_{k1,k2,k3}(x,y): {0,1}^{2n} -> {0,1}^{2n} }_{k1,k2,k3} is a PR**P**G.

(I am not asking you to prove this because it is too difficult…)

p^{-1}_{k1,k2,k3}(x,y) to do encryption/decryption of bit-strings of size 2n. What would be the security properties of such a system ?

(Make the strongest possible statement).