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 { f_{k}
: {0,1}^{n} -> {0,1}^{n} }_{
k }:

π_{k}(x,y) = [ y , x**
(+)**f_{k}(y) ]

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

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…)

(Make the strongest possible statement).

__Factoring__

- Let
**n=p*q**, the product of two primes, such that**p>q**. - Deduce from 1. an efficient algorithm to factor
RSA modulus
**(n=p*q)**for which**√p-√q < √2**. - 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**.

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

__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 2^{64}-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]