Deadline 04.10.2023 08:00

Files (1.bin, 2.bin, 3.bin, 4.bin, 5.bin) were generated using following commands:
	python3 LCG.py -m 2**31 -a 1103515245  -c 12345 -l 0  -u 31 -n 10000 --file 4.bin				
	python3 LCG.py -m 2**48 -a 25214903917 -c 11    -l 16 -u 47 -n 10000 --file 1.bin
	dd if=/dev/urandom of=3.bin bs=4 count=10000
	openssl rand -out 2.bin 40000
	rand_file.c =>  compile => ./a.out 5.bin    (HINT: https://www.mathstat.dal.ca/~selinger/random/) 

Identify the generator and provide the mapping:
1.bin <=> name2
2.bin <=> name4
3.bin <=> name3
4.bin <=> name1
5.bin <=> name5


Explain how you identified the files. If it is not possible to identify the source explain why.


How to identify the sources: 
1. Sources openssl rand, dev/urandom are cryptographically secure TRNG and do not (if implemented properly) produce patterns. Hence these sources are indistinguishable and can not be identified. 
2. Based on provided hint, the source rand_file.c can be identified using the linearity: o_i = o_{i-31} + o_{i-3} mod 2^{31} or  o_i = o_{i-31} + o_{i-3} + 1 mod 2^{31}.
3. The first LCG produces easily identifieable pattern - msb bit in 32-bit blocks is always 0 since this generator produce only 31 bit blocks. 
4. The second source (c = 1, ...) can be identified by brutte-force. The internal state has 48 bits but generated values consists of only 32 bits. In the brutte-force attack we can iterate through all possible 16 bits and try to reconstruct internal state - for correct state next random values will correspond.

Other approach for all PRNG is to brute-force the seed. In order to optimize the computation one should start with the time when the assignment was published and go backward. Also, many of you computed the entropy of the files and realized that 5.bin has different entropy than 2.bin and 3.bin.   

Thank to my mistake (:)) LCG uses the same fixed seed  (not the time) hence it suffices to repeat generation process, hash the files and find the pairing directly.