CS547A 2001 Homework set #3

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

 

Exercises (from Stinson’s book)

Information theory: Stinson Ex 2.1, 2.4, 2.10, 2.12

 


Exercises (home-made)

 

Consider the Blum-Blum and Shub generator (mod N=pq) where we output L bits obtained from all the bits computed in each iteration :

BBS*(s0)

L:=length/|N|

FOR i:=1 TO L DO

si := (si-1)2 mod N

RETURN s1 || s2 || ... || sL

Show how to distinguish the output of BBS* from a truly random source, even without knowing N nor its length |N|.

Write a Maple™ program to implement your distinguisher and run it on the following examples. Find which of W0 and W1 (on back) is generated by BBS*.

 

W0=

001000101100111001101010110111111110110110000110000101111011011000010101101000001100101111111110100101111010011010011110011001101001100111011010100100100111010011000000101111101000000110011010111000000110110010001010010111101011111010100111001100001110110110101011110001010110010110010100110000101000001110100111100001100001000010111101100010000011001010100011100011101011001001010100111010000011110110011010110111101110111101011100100010001111000110010001011110000110110001001111100010111101000000101010100111111011001010101011001010100000101101111100100000111111001101001011101101011011011100001010111010000011010010000000110001001011001000110100100000110110010011001010010010000111001110101100001011111011011100111100101100110011100011111100010011100101011111000010100100000100001001110100001011100011010000011000110110001010110011110111010001001010000100010110100100001011011010011101110010011001101010010011101101110111000000100000111011100001111110101010100011001000111010000000000101111010001100000011110110101101111101110110000011000010010111110111110100100001110010010011101101001100100100001111001000010000001010011000110100100101101110011010101100011111011110001010101100001110

W1=

010010100110100000110001110000110110001111111001100101110011111010111100000110100000001011010111110111000000001101100110010000111000110011010010110101101100000101100111110101010110010101111110101010001010110011010111100001000111001101000100011100000010010000101000101111010010011110101011100111010000101101011111001010100011110001111001100101111101110100001000001100010111100110010010101001110101111110010010011111101111011101001100000011011100110101110100010101101110101011100010000010011110111001000100100010101110110000101010011001010001101100110010011111110100011000100010000000111110001101001100011000010101001001011001100010001001000100001010100110011001000111111011001000000011111000011010101100110110000110100111010101011111000011101000010111100100010010011101001010010100111000011101111110101011000111101000011001111000100101111000110101111011111101111001011100110110010001110110101001010000000010100111010000000001011110000001001110001100010100000001100111110101011110000110011101100110100010011011011111011011001010010110111011011010101100111111000011010011000100011011111111011111011111101001000000111111010100101011001001011011000000010011100011100100011011010100100111010101