Problem E
Encrypted Chat App

Background

Persons of interested have been observed using a chat protocol they designed. We must figure out if there are any mistakes they made when implementing so we can decrypt their messages. The general algorithm is as follows:

1. User A creates a random number, user B creates a random number

2. The random numbers are traded using a public-key encryption and authentication scheme.

3. With the random numbers, each user creates a key stream for A and B

4. A/B encrypt/decrypt messages using an asymmetric encryption algorithm (in this case, AES256).

The following is the format of the resulting message:

[ID][to code][from code][start byte][encrypted message][end byte]

ID

- bytes of usrLETTER_#PACKETNUM

to code

- receiver username in base64

from code

- sender username in base64

start byte

- start of message byte code, 1f1f

encrypted message

- the actual encrypted message

end byte

- end of message byte code, 0f0f

This part of the algorithm appears secure, but we believe there is a mistake they made which we can use to decrypt the traffic.

Part 1: Implement the Random Number Generator (RNG)

The RNG the individuals are using is a pseudo-random number generator. We are providing you the pseudo-code, and asking you implement the RNG to aid in the decryption of these mysterious packets.

Each step consists of a 42 step RNG warm up, and after this, random numbers and the state of the register are returned. The RNG maintains a 16 bit internal register, and to step the register, the 1st, 4th, 10th, and 11th bit are XORed together (this is called the response bit). Then the register is shifted one bit to the right (right most bit falls off) and the response bit is put in the 12th bit position. This is one step of the register.

To generate a 16 bit random number, the register is stepped 16 times, and the response bits from each step are kept track of, this is our random number. The register is initialized by taking the second [0-60) from a user’s device and shifting it 6 bits to the right and then ORing with the same time. In code, this might look like TIME(left shift 6 bits) OR TIME.

Below is some pseudo-code to get you started.

rng
Args -
SEED              (time)
--
STATE             (12 bit state)
STATE = SEED(left shift 6) | SEED
RND = 0           (16 bit random number)
for i in {1,2,...,16} do
        response_bit = STATE[0th bit] XOR STATE[4th bit] XOR STATE[10th bit] XOR STATE[11th bit]
        STATE = STATE(right shift 1) OR response_bit(left shift 12)
        RND = RND(left shift 1) OR response_bit
return RND, STATE

Remember to warmup your RNG by computing 42 16-bit random numbers which are ultimately discarded. After this, keep track of your state to compute your next random number.

Input

Each line of input contains one seed number in decimal format.

Output

For each seed inputted, output the first 5 random numbers for each seed (after the warm up!)

17
19
41
43

28 46406 22081 56982 53644
39307 40295 28395 38242 64492
59464 30116 53538 63752 21151
29151 23941 59784 45820 30975