October 14, 2012 by Nakul
Encryption and decryption plays a vital role in today’s digital world. So we thought of implementing an encrypting and decrypting device using only 74xx logic chips. The encryption algorithm is based on cellular automaton. Rule 30 of the cellular automaton produces can be used as a random number generator. A cellular automaton is basically an array containing 1s and 0s whose next value depends on the previous value of the array based on a particular rule. You can read more about cellular automaton here.
Here we take an 8-bit array. The initial state of the array will be stored in a parallel-load parallel-out register. The next state of the register is also stored in a parallel-load parallel-out register. The next state is derived from the initial state. So between the registers, we have the logic section that implements the rule. Since this is an iterative process, there will be feedback from the next state register to the initial state register.
Before the feedback begins, we must input the required key into the initial state register. This describes the key generation circuit. For the actual encryption we decided to go for the XOR operation. Data has to be fed in terms of its ASCII values and this data is XORed with the sequence obtained from the key generation circuit. The key generation circuit produces a new sequence for every clock cycle.
Rule no. 30 can be represented as a truth table
Out = (~In1)(~In2)(In3) + (~In1)(In2)(~In3) + (~In1)(In2)(In3) + (In1)(~In2)(~In3)
Out = (~In1)(In2) + (~In1)(In3) + (In1)(~In2)(~In3)
For the logic section that is used to enforce the rule, we had two options. Either implement the above truth table using basic gates and universal gates or implement it using 8 multiplexer chips (8:1). We favored the latter as we figured that it will be much simpler to implement.
For giving the initial key, we use 2:1 MUXs to switch between the two paths, the feedback and the initial key.
For the initial state and next state registers we used two 4-bit registers each due to non-availability of 8-bit registers. Also, we want to reduce the number of components. So, instead of storing the key and the data in registers, they are directly given to the respective input pins.
So, finally here is the component list
- 8:1 MUX (74151) – 8
- 2:1 MUX (74157) – 2
- 4-bit universal shift register (7495) – 4
- 2-i/p XOR gate (7486) – 2
Here is the final circuit diagram that was actually implemented.
The entire circuit was implemented on breadboards. Due to lack of time and resources we were unable to transfer it onto a PCB. We observed the output (which is the ciphertext) on a trainer kit.
To input the key, select line of the 2:1 MUX is held low. This brings the key onto the input pins of the register. Now a single pulse of clock is given to the initial state register which loads the initial state register with the key. The select line of the 2:1 MUX is now made high which connects the input of the initial state register to the output of the next state register. Now a single pulse of clock is given to the next state register which loads the next state of the cellular automaton on to the next state register. The output of this register is XORed with the data sequence to get the encrypted sequence. By applying clocks to the initial state register and the next state register one by one; different sequences of the key are generated.
Input Output Sequences Observed
- Key given to the initial state register => 00011110.
- The content of the next state register => 00110001.
- Data given => 11010010.
- Output obtained => 11100011.
For decryption, we need the same setup that was used for encryption. The key given to the key generation circuit must be the same key that was given during the encryption process. The key generation circuit produces the suitable key for every clock pulse. For decryption, the ciphertext is given at the data input i.e. at the input of the XOR gates. The sequence in which the ciphertext is given to the system is very important. The order must be same as that got during the encryption procedure. Also, the clock has to be perfectly synchronized so that the data and the ciphertext are XORed with the same key sequence.
- Input given to decryption system => 1110011
- Output observed => 11010010
We do not have any claims regarding the strength of this algorithm that we have implemented. It would probably be very easy to write a program to break this algorithm. The fact that the registers are only 8-bits wide is a weakness in the system. But it can be scaled to greater register widths which would make the algorithm much more secure. If you are wondering how such algorithms are broken, you can read more about cryptanalysis here.
Project Members: Nakul Rao I, Nikilesh, Nischal Rao
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.