Encryption algorithms

What is encryption?

All encryption is based on an algorithm, the function of this algorithm is basically encode the information to be indecipherable at first sight. An encryption algorithm can transform the letter "A" to "5x5mBwE" or to "xQE9fq" and the work of an encryption algorithm is precisely determine how information will be transformed from its original state to one that is difficult to decode. The encryption and decryption algorithms uses what is called key to encrypt or decrypt information. These keys are used to encrypt information, however, there is another key that the person who receives the message knows, and it is through this unique key that the message can be decrypted.




What function does the key have?

There are two types of keys ("keys"), but the Internet's most widely used is called "public key" or asymmetric algorithm. The name "public" comes from its operation: there is a public key that is made known to anyone (all Internet) who so desires, this public key is used to encrypt information, however, there is another key that the person who receives the message knows, and it is through this unique key that the message can be decrypted.


Digital Signatures 

A digital signature uses the same function as "public key" or asymmetric algorithm mentioned above.
As mentioned, there is a "public key" and a "secret key" in the case of digital signatures public key is widely known is able to identify whether the information comes from a reliable source. In other words, the public key will be able to recognize whether the information actually comes from the "secret key" in question.


Now we will talk about the algorithms that we saw in class




The RSA cryptosystem

Of all asymmetric algorithms, RSA is the most used and perhaps the easiest to understand and implement. A peculiarity of this algorithm is that two keys are used interchangeably for both encrypt and authenticate. It was named after its three inventors: Ron Rivest, Adi Shamir and Leonard Adleman, who first published in 1977, the RSA method. Patent has been under RSA Laboratories until September 20, 2000, so their commercial use was restricted to that date.

The RSA algorithm

Key pair generation
To generate a key pair (KP, KP), we first randomly choose two large prime numbers p and q (approximately 200 numbers each, for example). Then the product n = calculated p.q
Now choose a number e relatively prime to (p-1) and (q-1). This pair of numbers (e, n) can be known by anyone, and constitute the so-called public key
and therefore must have an inverse module (p-1) (q-1), which we call d. Of course it is true that ed ≡ 1 mod ((p-1) (q-1)), which is the same as saying that ed = 1 + k (p-1) (q-1) for some integer k. The private key is the pair (d, n). This number d is kept secret and will only be known by the owner of the key pair.


Encrypt the message with the public key
It should be noted that this algorithm the messages are encrypted and decrypted integers smaller than n, not individual letters as in the case of Caesar and Vigenere ciphers.
To obtain the encrypted message C from clear message M, it performs the following operation:
C = I (mod n)


Decrypt the message with the private key
To recover the original message from the encryption is performed the following operation:
M = Cd (mod n)


Justification of the method
Cd (mod n) = (I) d (mod n) = M1 + k (p-1) (q-1) (mod n) = (M (p-1) (q-1)) kM (mod n ) [i]
vou recall, the Euler function φ (n) = (p-1) (q-1), and in general, but unlikely chance, you will have that gcd (M, p) = gcd (M, q) = gcd (M, n) = 1. And therefore according to the Euler-Fermat theorem, Mφ (n) ≡ 1 (mod n) ⇒ (M (p-1) (q-1)) k ≡ 1 (mod n) [ii]

In [i] and [ii] we obtain that Cd (mod n) = 1.M (mod n) = M, for 0


Commutativity of RSA encryption and decryption
For the properties of modular exponentiation, encryption and decryption are commutative:
M = (I mod n) d mod n = Md.e mod n = (Md mod n) e mod n = M
This means that if encrypting M with public key e and then decrypting the result with the Private M d get back, we can also encrypt M with private key d to decrypt the result with the public key and, returning to obtain M. This property is important because it allows us not only to use RSA to encrypt a message, but also to authenticate the message, as discussed in the next topic.


Cryptanalysis of RSA
To break RSA encryption, you can try several ways. In addition to factor n, we know that is a computationally intractable problem in a reasonable time, we could try to calculate φ (n) directly, or try a brute force attack trying to find the private key d, systematically testing each possible numbers of the key space. Both attacks are, for large n, even more computationally expensive than factoring n. own


DES cryptosystem
The encryption algorithm DES (Data Encryption Standard) is the most used in the world. Although its strength has been weakened by the creation of a $ 220,000 machine that breaks this code, continue to be used for several years thanks to a version that extends the life of this algorithm: the "Triple DES." This work complements an implementation in C language, learn how the DES. The operation of the Triple DES is a simple variant of DES, so it does not fully explain its operation. The purpose of explaining this algorithm is that a lot of other encryption algorithms use the same principles as the DES. By understanding the changes that occur in the DES, it is easier to understand the latest algorithms.


Preliminary Example
DES works by encrypting groups of 64 bits, ie, over 16 hexadecimal numbers. To make the encryption, DES keys are apparently uses 64-bit. However, every eighth bit is ignored, so the key is 56 bits effective. In any

case, 64 bits are the number around which to organize the DES. Take this first example, if we encrypt the text "8787878787878787" with the DES key "0E329232EA6D0D73" get the encrypted text "0000000000000000". The reverse process (decrypt) with the same key result gives us the original text: "8787878787878787".


This example is simple because our text measures exactly 128 bits. But most of the messages will be measured in 64-bit or a multiple of this number. For these cases, you must fill with zeroes up to a multiple of 64 bits.


DES works in detail
DES is a block cipher, which means working in a given text block size (in this case 64 bits) and returns blocks of the same size. Thus DES results in a permutation of the 264 possible distributions of those 64 bits. Each block of 64 bits is divided into two blocks of 32 bits each, called L and R (left and right by the acronym in English.) This division is used in certain operations.
Let M be the main message M = 0123456789ABCDEF where M is in hex format. By changing M to binary we get the block of 64 bits:
M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
L = 0000 0001 0010 0011 0100 0101 0110 0111
R = 1000 1001 1010 1011 1100 1101 1110 1111

DES operates on the 64-bit blocks using 56-bit keys. Both keys are stored as if using 64-bit but every eighth bit is ignored. That is, bits 8, 16, 24, 32, 40, 48, 56 and 64. However, we will continue calling to bits 1 to 64. 

The remaining bits will be eliminated when we sub keys.

Suppose that K is the key K = 133457799BBCDFF1 hexadecimal. Transforming a binary notation (1 = 0001 3 = 0011, etc..) And grouping every 8 bits, we see that the last bit will not be used:
K = 00010011 00110100 10011011 10111100 01010111 01111001 11011111 11110001


Diffie Hellman Cryptosystem
The Diffie-Hellman algorithm was the first public key algorithm invented. This significant that their authors are also the owners of the idea. The algorithm can be used for key distribution, but not to encrypt or decrypt

messages. Your safety lies in the difficulty of computing discrete logarithms in a finite field compared to the ease of performing exponentiation is in the same field. If you were left confused by all this, do not worry.


The problem of key distribution.

The problem of key distribution is whether it was first the chicken or the egg. If two people want to exchange secret messages, they need to encrypt messages. To encrypt and decrypt, you need a secret key. As this key also needs to be transmitted should be encrypted with another key, and so on indefinitely.

A fairly simple way to solve the problem of the keys is to use locks. Say you want to send a message Antonio Belen. She places the message in a metal box, closes the box with a lock (only she holds the key to this lock) and sent them to Bethlehem. Belen also puts a lock on the box (only he has the key of the second lock) and returns the box to Antonio. Upon receiving the box, Antonio opens and removes his padlock and again sent the case to Belen. Now, Belen can remove your lock, open the box and read the message. Perfect scheme? Almost ...


Mathematical functions


If mathematical functions necessary to encrypt a message had to perform at the locks, the solution found by Belen and Antonio would be perfect. Unfortunately, this is not the case math functions need to be "retired" in the reverse order that they were "placed", which is not necessary when it comes to locks. Despite this, this was the starting point used by Diffie and Hellman. Most mathematical functions are easily reversible, and for this reason, function calls can be bidirectional. A multiplicative function is reversible, easy to solve and an excellent example. Say f (x) = 2x. In this case, if x = 3, then f (x) = 2 x 3 = 6. Knowing the function x can be calculated quickly, regardless of the size of the result of the function. For example, if f (x) = 1000, we can make the account and get head at x = 500. So far, nothing special. Diffie and Hellman happen that they were concentrating efforts on the search for a one-way function. We can define a one-way function as a function has no return (this would be the true one-way function) or whose turn it is so difficult or so slow that, in practice, the return is not feasible. At the beginning of 1976, Hellman was considering an axiom that has existed for several hundred years. The idea was to use the function in the form of g


Diffie-Hellman algorithm

x (mod n)

To make the magic work, there were some restrictions:

g (base) needs to be less than n (the module)
and g needs to be greater than 1.
To get the keys, Belen and Antonio can exchange information freely, without the slightest concern with someone who is present or will eventually be intercepting this information. In just 4 steps, the two have a secret key.


Cryptosystem Hill
This system is based on linear algebra and has been important in the history of cryptography. It was invented by Lester S. Hill in 1929 and was the first system that was practical cryptographic polyalphabetic to work with more than three symbols simultaneously.
This system is polyalphabetic because it might be that same character in a message to send is encrypted in


two different characters in the encrypted message. Assuming that we work with an alphabet of 26 characters. The letters are numbered in alphabetical order so that A = 0, B = 1, ... , Z = 25


They choose an integer d d blocks determines which elements are treated as a vector of dimensions.
It chooses a random d × d matrix elements which will be the key to use.
The elements of the matrix of d × d be an integer between 0 and 25, plus the matrix M must be invertible in.
For encryption, the text is divided into blocks of d elements which are multiplied by the matrix d × d
All arithmetic operations are performed in the form module 26, ie 26 = 0 27 = 1, 28 = 2and so on.
Given a message to encrypt the message we take blocks of "d" characters and apply:
Pi = M × C, where C is the encryption code for the message Pi cryptanalysis
Hill system poses many problems cryptanalysts greater than those posed 'CAESAR'. To start the key space is much greater in this case is 4C25, ie permutations of 4 elements taken from among 25 possible. And using a matrix larger the number of possible keys can be made ​​as large as necessary to make it impossible to brute force attack.

The best thing a cryptanalyst can do is try to get a code to know which part of the message. And see if both are able to find data which was the matrix used to encrypt the message.

If you want see more, check this links:

http://www.osmosislatina.com/aplicaciones/seguridad.htm

http://www.dma.fi.upm.es/java/matematicadiscreta/aritmeticamodular/rsa.html

http://www.arielorellana.net/des.htm

http://serdis.dis.ulpgc.es/~ii-cript/PAGINA%20WEB%20CLASICA/CRIPTPGRAFIA%20MODERNA/ALGORITMO%20DE%20DEFFI-HELLMAN.html

http://www.textoscientificos.com/criptografia/hill