__3.3,
3.5, 3.6.__ **(you
may use Maple if you like)****
**

__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**(+)**f_{k}(y) ]

(a)
Show that p_{k}(x,y) is indeed
a permutation (a one-to-one function).

Define
similarly

p_{k1,k2}(x,y) = p_{k1}(p_{k2}(x,y)) AND 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…)__

(b)
Show that
{ p_{k} : {0,1}^{2n} -> {0,1}^{2n} }_{k} is not a PR**P**G.

(c)
Show that
{ p_{k1,k2 }: {0,1}^{2n} -> {0,1}^{2n} }_{k1,k2}
is not a PR**P**G.

(d)
Explain the relationship between these permutations
and DES.

(e)
Show how to compute their inverses p^{-1}_{k}(x,y), p^{-1}_{k1,k2} (x,y), p^{-1}_{k1,k2,k3}(x,y).

(f)
Explain how Alice and Bob could share a secret
key and use both p_{ }and
p^{-1} 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
and justify it: 1.ciphertext only, 2.known plaintext, 3.chosen plaintext,
4.known ciphertext, 5.chosen ciphertext. Possible answers are “not even 1.”,
“1. but not 2.”, “2. but not 3.”, “3. but not 4.”, “4. but not 5.”, or “5.”).

(g) Show
that if the plaintext messages contain some redundancy then the messages
encrypted by this system are automatically authenticated.

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

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

(2)
Deduce from (a) 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**.

Let

**n:=****201223196302292169219622984830563133506987435557014293342327257253033500165495588126167411221999207374847277768347836982576494308943649386406827140946534939546238280382935139467793871942808135660010991754505516234522619322318024162533378893717**

** **

**a)** find two primes **p,q** such that **n=p*q** and** |p|≈|q|≈120 **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+1000027);

>
e:=16755434444356788983;

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

**[2,7182818, 2845904523, 53,
6028, 747135, 2662, 497757,51]**