Projetos de sistemas criptográficos utilizando códigos lineares

Abstract

This work aims to study and develop classical and public key cryptographic systems, using algebraic theory of linear codes, in order to better understand the subject and verify the viability of such systems in relation to DES [Luc, 1986] and RSA [Sal, 1990], The interest in this topic comes from the fact that I am a professor and economist and work with disciplines and tasks that require knowledge related to data security; there are several applications of cryptographic systems, both in computer science and in engineering, and, mainly, in several other areas such as military, diplomatic, electronic commerce, with regard to data security. Cryptographic protection techniques are necessary for the transmission and storage of information that travels in data communications environments. To develop such cryptographic systems essential theoretical bases will be exposed for their production and understanding, having as reference the works cited in the bibliography, as well as the orientations of the guiding teachers. The word Cryptography comes from the Greek (kryptós = hidden + grapho = spelling) - it is, therefore, the art or science of writing in cipher or in code, in order to make a2 written message understandable only to its recipient, to decipher it, almost always requires the knowledge of a key, secret information. It is one of the most widely used security mechanisms today and arose from the need to send “sensitive” information through unreliable media [Sal, 1990] and [Luc, 1986]. But, through art or science called cryptanalysis, from the Greek kryptós + análysis = decomposition; third parties can break the system and determine the original text, even without knowing the key - in possession of the encrypted message. From the union between cryptography and cryptanalysis came cryptology (from the Greek kryptós = occult + logos = study) which has been used since the hieroglyphic writing of the Egyptians - for almost four thousand years, it has been widely used, mainly for military purposes and diplomatic, as an example, its use in the Second War, and the consequent breaking of the German and Japanese codes, which was fundamental for the success of the Allies [Luc, 1986]. Regarding the type, the encryption can be: * Secret key - which uses the same key to encrypt (secret method of writing, through which the original text is transformed into a code) and decrypt (reverse process of encrypting) a message. In this case, sender and recipient combine the secret key to be used in the transmission, as a result of which there is a great possibility of violation. * Public key - designed by Diffie and Hellman [Sal, 1990], it makes it difficult to break through two keys: the public key - known to everyone; and the private one - known only to its owner. Then, the sender uses the recipient's public key to encrypt the message and sends it, the recipient, in turn, uses his private key to decrypt the message. Public key cryptography has many advantages over key3 including verification of signatures using authentication methods. However, speed is a major disadvantage, since encryption and decryption operations require calculations with very large numbers. The concept of private key cryptosystems, based on error correction codes, has attracted the interest of researchers working in the area of ​​Information Theory and, since the emergence of the first cryptosystem of this type, in 1978 [Van, 1988], until the today, important contributions have been made to cryptography through the design of new encryption schemes that employ code theory1. s Code theory started in 1940 with the work of Golay, Hamming and Shannon [Hol, 1992], although the problem dealt with was engineering, it developed through more sophisticated mathematical techniques, giving rise to code families - for example, codes Hamming, Cyclic and BCH codes, as well as more advanced codes, such as Golay, Goppa, Altemant, Kerdock and Preparata codes [Hol, 1992]. Codes were invented to correct errors on the communication channel with noise [Hol, 1992]. The transmission / storage of data on a communication channel occurs only in one direction, from source to destination. Therefore, error controls for this type of system must be performed using an error correction code that automatically corrects errors detected at the destination. As for the type, the codes can be: block codes and convolutional codes. Linear block codes (linear codes) are a subclass of the block codes - the object of the present study. * Block codes - the coding of a block code divides the information sequence into k bit message blocks. A message block is represented by the binary utuple u = [u \, u2, ..., wk) called message. Coding transforms each message u into a zz-tuple v = (vb v2, ..., vn) of discrete symbols, called a code word. Therefore, corresponding to 2 different possible messages, there are 2 different possible code words. This set of 2k code words of size n is called a block code (n, k). The R = k / n ratio is called the code ratio and can be interpreted as the number of bits of information entering the coding channel by transmitted symbol. In a binary block code (binary code), each code word v is also binary. Consequently, for a binary code to be useful (that is, to have a different code word associated with each message), k <n or R <1. When k <n, nk bits of redundancy can be added to each message to form a word code. These redundancy bits allow, eventually, the correction of errors caused by the channel. * Linear codes - A block code of size n and 2k code words is called a linear code (n, k \ se and only if, these 2k code words form a ^ -space subspace of the vector space of all / z-tuples on the body GF (2) [Lin, 1983j. A binary block code is linear, if and only if, the sum of two code words in module-2 is also a code word. A linear code C is called cyclic, if for every code word v = (v0, U. ■■■, bi-2, v „. |) EC, there is also a code word v <n = (v„ .i, v0, vi ..., v „.2) eC [Wic, 1995], 5 It must be considered as the basis of the theory of information linked to communications and transmissions with confidentiality: in communications, noise must be eliminated, restoring the original information; in cryptography, noise introduced through encryption must be eliminated in order to restore the original information.