3.3,
3.5, 3.6. (you
may use Maple if you like)
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(+)fk(y) ]
(a)
Show that pk(x,y) is indeed
a permutation (a one-to-one function).
Define
similarly
pk1,k2(x,y) = pk1(pk2(x,y)) AND 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…)
(b)
Show that
{ pk : {0,1}2n -> {0,1}2n }k is not a PRPG.
(c)
Show that
{ pk1,k2 : {0,1}2n -> {0,1}2n }k1,k2
is not a PRPG.
(d)
Explain the relationship between these permutations
and DES.
(e)
Show how to compute their inverses p-1k(x,y), p-1k1,k2 (x,y), p-1k1,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 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.
[2,7182818, 2845904523, 53,
6028, 747135, 2662, 497757,51]