Cryptosystem built using DNA cryptography and the Mealy automaton

Cryptography is one of the oldest sciences dealing with the study of methods for protecting data from unauthorized actions with them. Cryptosystems can be divided into two large classes: symmetric and asymmetric. In symmetric cryptosystems, the parties exchanging information use the same session key. In asymmetric cryptosystems, two different keys are used for encryption and decryption, public (available to everyone) and private (known only to the owner).

One of the promising trends in modern cryptography is DNA cryptography. Usually, DNA cryptography means either the direct use of DNA chains for the presentation and transmission of information, which requires high-tech equipment, or the use of an alphabet of DNA nucleotides (A, T, C, G) in the encryption process.

The relevance of cryptosystems, in one form or another, including DNA chains, is also associated with active research in the field of memory devices using DNA. Such devices will be able to store the amount of information several orders of magnitude larger (with more compact sizes) than modern technologies allow. In addition, the lifespan of such storage devices is noticeably longer.

This article discusses the cryptographic system [1]using DNA cryptography and the Mealy automaton.

Briefly about DNA and the Miles machine

DNA (deoxyribonucleic acid) is a macromolecule composed of a sequence of nucleotides. A nucleotide is determined by its base (nitrogenous base), of which there can be four types in DNA: adenine (A), cytosine (C), guanine (G), and thymine (T). Thus, in DNA cryptography, the alphabet {A, T, C, G} can be used to store data instead of the usual 0 and 1, and the message itself is represented as a certain DNA chain.

A Mealy automaton is a finite automaton in which the elements of the output sequence depend on the current state of the automaton and the current element of the input sequence. The Mealy automaton is defined by a set of functions and sets M = {S, X, Y, δ, λ}:

  • S is the set of states of the automaton: {1, 2, 3, 4};

  • X is a set of elements of the input sequence: {A, T, C, G};

  • Y is a set of elements of the output sequence: {A, T, C, G};

  • δ is a transition function that maps a pair (state, input) to the next state;

  • λ is an output function that maps a pair (state, input) to an element of the output sequence.

The structure of the Mealy automaton can be completely specified by two tables: the transition table (implements the function δ) and the table of outputs (implements the function λ). In the scheme under consideration, for each transfer, a new Mealy automaton is randomly created, which is used to transform one DNA strand into another. Examples of these tables for the cryptosystem under consideration are given below.

Example of a jump table

State of the machine

At the entrance “A”, next state.

At the entrance “T”, next state.

At the entrance “C”, next state.

At the entrance “G”, next state.

0

one

2

0

3

one

3

one

2

0

2

0

3

one

2

3

2

0

3

one

Example of a table of outputs

State of the machine

At the entrance “A”, at the exit

At the entrance “T”, at the exit

At the entrance “C”, at the exit

At the entrance “G”, at the exit

0

T

A

G

C

one

C

T

A

G

2

G

C

T

A

3

A

G

C

T

Considered cryptosystem

Three objects interact in a cryptosystem: a key pair generator (CCP), a sender (hereinafter referred to as Alice), and a recipient (hereinafter referred to as Bob). The work cycle consists of several stages and is shown in the diagram. Let’s take a closer look at each of the stages.

Scheme "working cycle" cryptosystems
Scheme of the “working cycle” of the cryptosystem
  1. Registration on the server. Alice and Bob request a pair of keys from the GPK. The GPC generates two key pairs and sends them, while Alice’s public key is sent to Bob and vice versa (steps 1-4);

  2. Session establishment. Bob sends Alice a request to establish a session along with some information: personal number (PN), email ID and MAC address (step 5). Alice authenticates the sender by requesting the server (steps 6-7) and confirms the establishment of the session (step 8). Bob can then request data (step 9);

  3. Key generation. Alice decrypts the data (PN, email ID, MAC) received from Bob using her private key and Bob’s public key, and on their basis generates a session key: first, the received data is concatenated into one line, then each character is replaced by its value from the table ASCII in binary 8-bit notation (for example, “0” → 4810→ 001100002 ). If the resulting binary string is less than 256 characters long, then it is padded with zeros, otherwise, the last bits are discarded;

  4. Generation of the Miles machine. Alice generates a jump table and an output table at random. The values ​​from the tables are written in a row in a row, while the characters {A, T, C, G} are replaced by {0, 1, 2, 3}, respectively. Each of 32 numbers (16 numbers from each table) in the line is replaced with its 8-bit binary representation according to some translation table. This table is generated randomly so that the binary representation of numbers contains the same number of zeros and ones, see the example below. As a result of the described manipulations, a 256-bit number is obtained. Then, every two bits are again converted into characters {A, T, C, G} according to a randomly selected string (we denote its number as R1) from the encoding table for DNA bases. The resulting sequence (let’s call it DNAMM, DNA Mealy machine) and the number R1 will then be transferred to Bob so that he can decrypt the message.

  5. Data encryption. Alice translates each character in her message into an 8-bit binary representation according to a regular ASCII table. The resulting binary string is split into blocks of 256 bits. Then, an XOR (exclusive OR) operation is performed between the session key from clause 3 and each block. After that, every two bits of the resulting string are converted into characters {A, T, C, G} according to a randomly selected string (we denote its number as R2) from the already familiar encoding table for DNA bases. The resulting chain (let’s call it dnaD1) is fed by Alice to the input of the Mealy automaton, and the output is a new chain dnaD2. The final ciphertext is obtained by writing in reverse order of the dnaD2 chain. For example, if the plaintext contains 100 characters, then after encryption you get a chain of length 400 with elements from the alphabet {A, T, C, G}.

  6. Sending data. Alice sends Bob the ciphertext, DNAMM, the binary translation table {0, 1, 2, 3} and parameters R1 and R2 using her private key and Bob’s public key (step 10).

  7. Decryption of data. Bob, using his private key and Alice’s public key, recovers the ciphertext, DNAMM, translation table, and parameters R1 and R2. First, Bob rewrites the ciphertext in reverse order, resulting in the dnaD2 chain. Then, performing step 4 in reverse order, Bob restores the structure of the Mealy machine. By applying the jump table rules in reverse order to the dnaD2 chain, Bob reconstructs the dnaD1 chain. Next, performing step 5 in reverse order, Bob reconstructs Alice’s original message.

An example of a table for translating characters {0, 1, 2, 3} into a binary code

Symbol

Binary representation

0

10011010

one

01101001

2

01010110

3

10011010

Encoding table for DNA bases

String (R1 or R2)

00

01

10

eleven

0

A

T

C

G

one

A

T

G

C

31

G

A

T

C

Security analysis

Let’s move on to considering the stability of the described system to various attacks.

  1. A brute-force attack. Since a 256-bit session key is used for encryption, it is necessary to iterate over 2256 options that are computationally impossible;

  2. Plaintext and ciphertext-based attacks, differential cryptanalysis. In these types of cryptanalysis, the attacker tries to guess the bits of the secret key using known pairs (plain text, ciphertext) or decrypt subsequent messages. In the cryptosystem under consideration, a session key is used to encrypt messages, and a new Mealy automaton is generated for each transmission, due to which two similar plaintext is converted into two completely different ciphertext, and vice versa – two similar ciphertext upon decryption are transformed into completely different plaintext. That is, the cryptosystem is resistant to such attacks.

  3. Man-in-the-middle attack. In the cryptosystem under consideration, all transmissions between Alice and Bob are encrypted using public and private keys, the generation and distribution of which is the responsibility of the GPC. That is, it is believed that third parties do not have access to the keys, so reading or subtly changing any messages in the channel between Alice and Bob is impossible.

  4. Phishing. In this type of attack, an attacker tries to obtain the recipient’s personal information, which can then be used to read data from the sender. In the considered scheme, Alice and Bob must first register on the server (GPC), and then, before sending the data, Alice first verifies the authenticity of the information received from Bob using the server, so unauthorized obtaining of personal information is impossible.

Also in work [1] analysis of various characteristics (encryption / decryption time, session key generation time, etc.) of the proposed cryptosystem is carried out and their comparison with the characteristics of similar schemes using DNA cryptography is carried out. Of the most interesting results, it is worth noting the following: the frequency of characters in the DNA basis in the ciphertext, when the plain text is 100 identical elements of the DNA basis and the avalanche effect. It can be seen from the histograms that all symbols of the DNA basis have approximately the same frequency. If now we replace one bit of the session key, then an avalanche effect is observed, see the table below.

The frequency of characters of the DNA basis in the ciphertext, if the plaintext contains (a) 100 "A" (b) 100 "T" (c) 100 "G" (d) 100 C, [1]
The frequency of characters of the DNA basis in the ciphertext, if the plaintext contains (a) 100 “A” (b) 100 “T” (c) 100 “G” (d) 100 C, [1]

Avalanche effect: changing the ciphertext when changing
one bit of the session key

Plain text

Change of ciphertext,%

100 “A”

72

100 “T”

85

100 “G”

82

100 “C”

79

Conclusion

In this article, a cryptosystem was considered, in which elements of DNA cryptography and the Mealy automaton are used for encryption. An analysis of this cryptosystem for resistance to various crypto attacks is also given.

From a practical point of view, the considered scheme is an addition to the classical asymmetric cryptosystem with a dedicated object that manages the keys. Thus, the described cryptosystem can be used to improve the security of asymmetric cryptosystems.

List of sources

  1. Pavithran, Pramod, et al. “A novel cryptosystem based on DNA cryptography and randomly generated Mealy machine.” Computers & Security 104 (2021): 102160.

  2. Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. “Introduction to automata theory, languages, and computation.” Acm Sigact News 32.1 (2001): 60-65.

  3. https://ru.wikipedia.org/?curid=10889&oldid=117159287

  4. https://ru.wikipedia.org/?curid=7709336&oldid=106283042

  5. https://ru.wikipedia.org/?curid=355613&oldid=116680835

  6. https://ru.wikipedia.org/?curid=30212&oldid=117810591

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *