CS547A Homework set #4

Due Monday November, 19 2001 in class at 13:00

Exercises (from Stinson’s book)

3.2, 3.3.

Other Exercises

Pseudo-Random Permutation Generator

We say that { πk : {0,1}n -> {0,1}n }k is a Pseudo-Random Permutation Generator (PR∏G) if it is a PRØG and each πk is a permutation (a one-to-one function). Consider the following family of permutations { πk : {0,1}2n -> {0,1}2n }k defined from a Pseudo-Random Function Generator { fk : {0,1}n -> {0,1}n } k :

πk(x,y) = [ y , x (+)fk(y) ]

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

    2. Define similarly

    πk1,k2(x,y) = π k1(πk2(x,y))

    πk1,k2,k3(x,y) = πk1(π k2(πk3(x,y))

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

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

  2. Show that { πk : {0,1} 2n -> {0,1}2n }k is not a PR∏G.
  3. Show that { πk1,k2 : {0,1} 2n -> {0,1}2n }k1,k2 is not a PR∏G either.
  4. Explain the relationship between these permutations and DES.
  5. Show how to compute their inverses π -1k(x,y), π-1k1,k2 (x,y), π-1k1,k2,k3(x,y).
  6. Explain how Alice and Bob could share a secret key k1,k2,k3 and use both πk1,k2,k3 and π-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).

Factoring

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

    2. Show that if √p-√q < √2 then ceiling( √n) = (p+q)/2 .

  2. Deduce from 1. an efficient algorithm to factor RSA modulus (n=p*q) for which √p-√q < √2.
  3. Generalize this factoring method using products of the form ceiling(√kn) =(ap+bq)/2 for n=p*q and k=a*b for known a,b.

MAPLE™ 7.

THE GREAT 2001 FACTORING CONTEST

Let

n:=197231911163405286921718012015270678856664391043447215378019862312897011307409748734917597781968509676778724262856819100913019204008258985296451859025201181910853794528687688143772625302729068927631941

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

Block Cipher Modes of Operations

Consider the following pieces of MAPLE™ code that define an encryption function "enc" and a decryption function "dec" for messages of 64 bits:

> with(numtheory):

> enc:= (p,e,m) -> m&^e mod p;

> dec:= (p,e,c) -> c&^(e^(-1) mod (p-1)) mod p;

> p:=nextprime(2^64+1030027);

> e:=16755434234356788983;

b) Use the above statements as a block cipher and implement three MAPLE™ procedures to encrypt/decrypt/authenticate lists of messages using the CBC mode of operation:

> CBC_enc:=proc(IV,LIST)…

> CBC_dec:=proc(IV,LIST)…

> CBC_mac:=proc(IV,LIST)…

Where LIST is a MAPLE™ list of numbers, and IV is an integer between 0 and 264-1. Note that in the CBC_enc mode, you are encouraged to use a random first plaintext block to randomnize the encryption of the entire list. You may ignore this block at decryption.

c) Encrypt, Encrypt and Authenticate, Encrypt and Decrypt, the following list using your student number as IV.

[3,14159,2653589793,23,8462,643383,27950,288419716939937,51]