Mathematical Codes Essay, Research Paper

Mathematical Codes

Mathematical codes are used by millions everyday for a variety reasons, but all intending to keep something private. The coding theory has actual applications in consumer electronics and with other areas of mathematics. Encryption, which involves enciphering and encoding, is used to protect data against organized crime, government and multinational institutions. A use of arithmetic, prime numbers, and prime factorization is used within coding theory.

The study of enciphering and encoding, and deciphering and decoding is called cryptography (Gardner 17). Encryption is encoding or enciphering a message so that the contents are hidden from outsiders (Fr?sen 10). Strong encryption is not a technical standard, it means that current known methods within feasible time without the data being outdated cannot break the encryption. Strong encryption is used to protect data against organized crime, government and multinational institutions. Strong encryption brings possible applications into daily life. Electric money, secure communications, passwords, and others are among many. Applications that require privacy, trust and access control should all use strong encryption methods when possible. It is suggested that people?s legal, medical, personal data about themselves should stay confidential to the instances that have a permit to collect the databases.

Encryption is not a new concept. Militaries and diplomatic forces have been using it for thousand of years, trying to keep information from the enemy. Given, it was more simplistic back then, but it was still used during War. For example, the Americans have used Morse code for years.

There is a distinct difference between ciphers and codes. Substituting one word for another word or sentence is using a code (Gardner 18). Mixing up or substituting existing letters for one word or sentence is using a cipher (18). The majority of encryptions use ciphers versus codes. The algorithm is the method used to encipher the original message, known as the plaintext (20). A key is used with the algorithm to allow the plaintext to be both enciphered and deciphered (20).

Ciphers are broken into two main categories: substitution ciphers and transportation ciphers. Substitution ciphers replace letters in the plaintext with other letters or symbols, keeping the order in which the symbols fall the same (25). By definition, substitution ciphers could be, in most cases, called codes. Transposition ciphers keep all of the original letters intact, but mix up the order (25). The resulting text is referred to as the ciphertext.

Some cryptographic methods rely on the secrecy of algorithms used in the cipher, security by obscurity (Fr?sen 2). All modern algorithms use a key to control the encryption and decryption. The message can only be decrypted if the key matches the on it was encrypted with. The key used for decryption can be different from the key used in encryption, and this divides the algorithms in symmetric and asymmetric classes (2).

Symmetric cryptosystems use the same key, the secret key, to encrypt and decrypt a message. Since it uses the same key for both encryption and decryption, the key should be changed often and be sufficiently random (2). Symmetric algorithms use different length keys, which usually means higher security. Symmetric algorithms can be divided into two categories: stream ciphers, which take and encrypt one bit of the original data at a time, and block ciphers, which take a number of bits and encrypt them as a single block (2). The majority of ciphers belong to the block cipher class. Symmetric algorithms are generally faster and use a much shorter key than asymmetric ones.

DES, Data Encryption Standard, is the notorious symmetric cryptosystem. It has been certified by NIST, National Institution of Standards and Technology, for use as an official US Government encryption standard for less-than-top-secret secret material (2). DES was first certified for government use in 1977 (2). DES is a strong cipher, which encrypts a block of 64 bits at a time. DES encryption consists of many rounds of different transformations and permutations, which are linear and easy to reverse (3). Performing a permutation involves arranging elements in different arrangements, where order does matter. The critical encryption is done using S-boxes. S-boxes, or substitution boxes, are sets of highly non-linear functions, implemented in DES as a set of lookup tables (3). After the S-boxes, the results are still permutated (3).

There are two known ways to decode DES. The first way consists of a search of the keyspace, which consists of 2^56 possible keys (3). If one could test one million keys every second, it would take about two thousand years to go through the keyspace. With special hardware, a chip could be designed that does a billion tests per second, reducing the time to two years (3). The more recent method of decoding DES is differential cryptanalysis. This method reduces the number of keys that must be tested, but it requires 2^47 chosen plaintexts encrypted with the key that is trying to be recovered. Since it is unlikely that anyone would agree to encrypt 2^47 chosen plaintexts with their secret DES key, this attack is impracticable in practice (3).

When used properly, DES is secure against all but the most powerful organizations. Proper use means avoiding weak keys. Weak keys are a result of the key being split to sixteen pieces, one for each round of encryption (4). Using simple DES for top-secret data is not a good idea with today’s technology; however, it is sufficient of everyday use (4).

Asymmetric cryptosystems, also known as public key cryptosystems, use one key, the public key, to encrypt a message and a different key, the private key, to decrypt it.

An efficient and reliable solution is a public key cryptosystem is RSA. Ron Rivest, Adi Shamir, and Leonard Adleman invented the RSA algorithm in 1978. RSA is the most widely used public key cryptosystem today and has often been called a de facto standard (6). RSA involves using prime and relatively prime numbers. The study of primes and divisibility goes back to Euclid. In Elements, Euclid proves there are infinitely many prime numbers. If one number divides into the number evenly, then that is a factor, if there are no factors, the number is prime. If the number, n, is composite, it must have at least one prime factor less than the square root of n. The math behind RSA public key encryption goes as follow:

1) Find P and Q, two large prime numbers.

2) Choose E such that E is less than PQ, and such that E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can’t be prime because it’s an even number.

3) Compute D such that (DE – 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E.

4) The encryption function is encrypt(T) = (T^E) mod PQ, where T is the plaintext (a positive integer) and ^ indicates exponentiation.

5) The decryption function is decrypt(C) = (C^D) mod PQ, where C is the ciphertext (a positive integer) and ^ indicates exponentiation. (Litterio http://world.std.com/~franl/crypto/rsa-guts.html)

The public key is the pair (PQ, E), and the private key is the number D. The product PQ is the modulus. E is the public exponent, while D is the private exponent. It is difficult to obtain the private key D from the public key (PQ, E) (Fr?sen 6). If one could factor PQ into P and Q, then once could obtain the private key D (6-7). Thus the entire security of RSA is predicted on the assumption that factoring is difficult; an easy factoring method would break RSA (7).

Encryption and authentication take place without any sharing of private keys: each person uses only other people?s public keys and his or her own private key (7). Anyone can send an encrypted message or verify a signed message, using only public keys, but only someone in possession of the correct private key can decrypt or sign a message.

RSA operations are all based on prime numbers and a series of multiplications. It is easier to do a multiplication than to undo it. In practical applications, it is common to choose a small public exponent for the public key. Entire groups of users can use the same public exponent. This makes encryption faster than decryption and verification faster and signing.

According to RSA Laboratories, when implemented entirely in software, DES is at least a hundred times faster than RSA (3). Implemented in hardware, it may outperform the RSA algorithm by a thousand or even ten thousand times (3). This is primarily due to the fact that the DES S-boxes are simple table-lookup functions, while RSA depends on large-integer arithmetic (3).

Encryption is used more now than ever before, for sole purposes to keep data private. It has been used by military and diplomatic forces for years, and now is used by everyday people.

Bibliography

Fr?sen, Janne. Practical Cryptosystems and their Strength. Proceedings of HUT Seminar on Network Security Helsinki University of Technology, February 1996.

Gardner, Martin. Codes, Ciphers and Secret Writing. NY: Dover, 1972.

Litterio, Francis. ?The Mathematical Guts of RSA Encryption.? Cryptography.

http://world.std.com/~franl/crypto/rsa-guts.html

(15 Nov. 2000)