Introduction

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. (Wikipedia)

The state of a system is described by the cumulative state of its component cells, and the following rules govern them:

1. Underpopulation: Each cell (alive in the current generation) with fewer than two neighbors alive dies in the next generation.
2. Live Cell Continuity: Each cell (alive in the current generation) with two or three neighbors alive will survive to the next generation
3. Overpopulation: Each cell (alive in the current generation) with more than three neighbors alive dies in the next generation.
4. Creation: A dead cell with exactly three neighbors alive will come to life in the next generation.
5. Dead Cell Continuity: Any other dead cell that doesn't meet the creation rule remains dead.

The neighbors of a cell are considered to be the eight surrounding cells in a two-dimensional matrix:

a00	a01	a02
a10	cell	a12
a20	a21	a22

For cells located on the first row, first column, last row, and last column, extension to 8 neighbors is considered. This extension includes cells that are not within the matrix, treating them as dead cells. Let ⁺S be the extended matrix.

Consider below the initial configuration of a system. Let it be S₀:

0	1	1	0
1	0	0	0
0	0	1	1

Also consider below the extended matrix ⁺S₀

0	0	0	0	0	0
0	0	1	1	0	0
0	1	0	0	0	0
0	0	0	1	1	0
0	0	0	0	0	0

We define the state of a system at generation n as a matrix S_n ∈ M_m×n({0, 1}) (where m is the number of rows and n is the number of columns), where 0 represents a dead cell, and 1 represents a live cell (in the current generation). A k-evolution (k ≥ 0) of the system is an iteration S₀ → S₁ → · · · → S_k, where each S_i+1 is obtained from S_i by applying the five rules mentioned above.

Symmetric Encryption Schema

We define an encryption key (starting from an initial configuration S₀ and a k-evolution) as the operation < S0, k >. This represents the one-dimensional array of data (understood as a bit string) obtained by concatenating the lines of ⁺S_k.

Using previous declared system configuration, for < S0, 1 > will result in: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 = ⁺S₁

Consider the message m as a plaintext (a string of characters without spaces). The encryption {m}_{< S0, k >} involves XOR-ing the plaintext message m with the result obtained from < S0, k >. The following cases apply:

• If the message and the key have the same length, XOR each element one by one until the result is obtained.
• If the message is shorter than the key, use only the first part of the key corresponding to the length of the message.
• If the message is longer than the key, replicate the key as many times as necessary to encrypt the entire message.

Encryption

Consider m=text and use ⁺S₁ as the key, where S₀ is the initial configuration described earlier. We have seen that the obtained result is the bit string: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0. To do the encryption m must be transformed also in a bit string: 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0

Since bit string length of ⁺S₁ is less than the bit string of the message m, the first 2 bits of ⁺S₁ must be concatenated at the end of the string:

0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0+0 0. Let this string be A
0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 = m

Now since the lengths are all equal, the encryption can be done:

A	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
m	0	1	1	1	0	1	0	0	1	1	0	0	1	0	1	0	1	1	1	1	0	0	0	0	1	1	1	0	1	0	0
R=(A^m)	0	1	1	1	0	1	0	0	1	1	1	0	0	1	0	1	1	1	1	1	0	0	0	0	1	1	1	0	1	0	0

The result R is transformed in a string with hexadecimal characters taking every 4-bit sequence: 0x74E5F874

Decryption

For decryption are applied the same rules as for encryption, because m ^ < S0, 1 > ^ < S0, 1 > = m

Input

Below is an example of how an input should look like

3 // lines

4 // columns

5 // number of alive cells

0 // x1

1 // y1

0 // x2

2 // y2

1 // x3

0 // y3

2 // x4

2 // y4

2 // x5

3 // y5

1 // number of evolutions

0 // or 1 (0 - encryption, 1 - decryption)

text // text=anything for encryption | text=0x{HEXADECIMAL CHARS} for decryption (e.g. text=0x74E5F874)

Compilation

You can compile the source using gcc -m32 game_of_life.s -o game_of_life

Run the program using ./game_of_life

Additional: You can create a text file with an input and redirect the program to read the input from that file running the executable as following: ./game_of_life < whatever_file_name.txt

Yoy may expect the following warnings after compilation: /usr/bin/ld: /tmp/ccNhjtjD.o: warning: relocation in read-only section `.text' and /usr/bin/ld: warning: creating DT_TEXTREL in a PIE. You can hide these warnings adding -no-pie at the end of the compilation command: gcc -m32 game_of_life -o game_of_life -no-pie