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) = xb mod n and the decryption operation is d(y) = ya mod n. We proved that d(e(x)) = x if x in Zn*. Prove that the same statement is true for any x in Zn.

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

HINT

Use the fact that x1 = x2 (mod pq) if and only if x1 = x2 (mod p) and

x1 = x2 (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 n1, n2, n3. Now suppose Alice encrypts the same plaintext x to send to Bob, Bart and Bert. That is, Alice computes yi = x3 mod ni, i=1,2,3. Describe how Oscar can compute x, given y1, y2 and y3, without factoring any of the moduli. (!!!)

• 4.10 •

A plaintext x is said to be fixed if eK(x) = x. Show that, for the RSA Cryptosystem,

the number of fixed plaintexts x ΠZn* is equal to gcd(b-1,p-1) x gcd(b-1,q-1).

HINT

Consider the system of two congruences eK (x) = x (mod p), eK (x) = x (mod q).

Other Exercises

Factoring

  1. Let n=p*q, the product of two primes, such that p>q.

    2. Show that if p1/2 - q1/2 < 21/2 then ceiling(n1/2) = (p+q)/2.

  2. Deduce from (a) an efficient algorithm to factor RSA modulus for which

    3. p1/2 - q1/2 < 21/2.

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

 

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 { pk : {0,1}n -> {0,1}n }k is a Pseudo-Random Permutation Generator (PRPG) if it is a PRFG and each pk is a permutation (a one-to-one function). Consider the following family of permutations { pk : {0,1}2n -> {0,1}2n }k defined from a Pseudo-Random Function Generator { fk : {0,1}n -> {0,1}n }k :

pk(x,y) = [ y , x xor fk(y) ]

  1. Show that pk(x,y) is indeed a permutation (a one-to-one function).

    2. Define similarly

    pk1,k2(x,y) = pk1(pk2(x,y))

    pk1,k2,k3(x,y) = pk1(pk2(pk3(x,y))

    It has been proven that { pk1,k2,k3(x,y): {0,1}2n -> {0,1}2n }k1,k2,k3 is a PRPG.

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

  2. Show that { pk : {0,1}2n -> {0,1}2n }k is not a PRPG.
  3. Show that { pk1,k2 : {0,1}2n -> {0,1}2n }k1,k2 is not a PRPG.
  4. Explain the relationship between these permutations and DES.
  5. Show how to compute their inverses p-1k(x,y), p-1k1,k2 (x,y), p-1k1,k2,k3(x,y).
  6. Explain how Alice and Bob could share a secret key k1,k2,k3 and use both pk1,k2,k3 and

p-1k1,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).