lunes, 6 de octubre de 2014

D-H


Diffie–Hellman key exchange (D–H) is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.
Of course there is a problem at the time encryption require two parties to first share a secret random number know as a “key”, so how could two people who have never met agree on a secret shared key without letting eve who is always listen also obtain a copy of the key?.
In 1976 Whitfield Diffie and Martin Helmand devised an amazing trip to do this, first lets explore how this trick is done using colors, how could Alice and Bob agree on a secret color without Eve finding it out; the trick is based on two facts: 1)it’s easy to mix two colors together and 2) given a mix color it’s hard to reverse it in order to find the exact original colors, this is the basics for a lock, easy in one direction hard in the reverse direction, this is known as a one-way function.
Now the solution works as follows:
First they agree publicly on a starting color, lets says yellow, next Alice and Bob both randomly select private colors and mix them into the public yellow, in order to disguise their private colors, now Alice keeps her private color and sends her mixture to Bob and Bob keeps his private color and sends his mixture to Alice, now the part of the trick, Alice and Bob add their private colors to the other person mixture and arrived on a shared secret color, notice how eve is unable to determine this exact color since she needs one of their private colors to do so.
Now to do this with numbers we needed numerical procedure which is easy in one direction and hard in the other, this brings us to modular arithmetic also known as clock arithmetic, for example to find 46 mod 12, we could take a rope a blank 46 units and wrap it around the clock of 12 units which is called the module, and where the rope ends is the solution, so we say 46 mod 12= 10. 
Now to make this work we use a prime modulus such as 17, then we find a primitive route of 17 in this case 3 which has this important property that, when raise to different exponents the solution distribute uniformly around the clock
, 3 is known as the generator, if we raise 3 to any exponent “x” then the solution Is equally likely to be any integer between 0 and 17; now the reverse procedure is hard: say given 12 find the exponent 3 needs to be raised to (3^(?) mod 17 = 12 ), this is called the discrete logarithm problem, and now we have our one-way function easy to perform but hard to reverse
.
Given 12 we would have to resort to trial and aired to find matching exponents, how hard is this?, 

well with small numbers its easy but if we use a prime modulus of hundreds of digits long, it becomes impractical to solve even if you had access to all computational power on earth, it could take thousands of years to run through all the possibilities, so the strength of a one-way function is based on the time needed to reverse it.

now this is our solution: first Alice and Bob agree publicly on a prime modulus and a generator (in this case 3 mod 17), then Alice select a private random number say 15 and calculates 3^(15) mod 17 = 6
and sends this result publicly to Bob, then Bob selects his private random number say 13 and calculates 3^(13) mod 17 = 12, and sends this result publicly to Alice, and now the heart of the trick, Alice takes Bob’s public result and raise it to the power up her private number (12 ^(15) mod 17 = 10) to obtain the shared secret which in this case is “10”, Bob takes Alice’s public result and raise it to the power of his private number (6^(13) mod 17=10 ) resulting in the same shared secret, notice they did the same calculation though it may not look like it at first 12^(15) mod 17 = 6^(13) mod 17 ), consider Alice equation (12=3^(13) mod 17) so her calculation was the same as (3^(13^15) mod 17 ), now consider Bob equation (6= 3^(15) mod 17) so his calculation was the same as (3^(15^13) mod 17)  notice they did the same calculation with the exponents in a different orders, so they both calculated 3 raised to the power up their private numbers, without one of this private numbers (15 or 13) Eve will not be able to find a solution, and this is how its don

bibligraphy : https://www.youtube.com/watch?v=YEBfamv-_do
khan Academy : https://www.khanacademy.org/

viernes, 12 de septiembre de 2014

Pseudoaleatoridad


Aleatoriedad vs pseudoaleatoridad

 
Se puede generar números verdaderamente aleatorios mediante la medición de las fluctuaciones aleatorias conocidas como “ruido”, cuando medimos este ruido como muestreo, se pueden obtener números, por ejemplo si se miden la corriente eléctrica de la televisión estática con el tiempo, se generara una secuencia de números realmente aleatoria,  esta secuencia aleatoria se puede visualizar si se grafica como un camino, que va desde su número anterior hacia su siguiente número, en este camino podremos observar que este no tiene un patrón en específico y la ruta es verdaderamente “aleatoria” (gif de ejemplo) http://makeagif.com/CHrZ6d


Los procesos aleatorios como este son No Deterministas ya que es imposible determinar cuál sería el siguiente número aleatorio, mientras que una computadora son deterministas, porque su funcionamiento es predecible y repetitivo.
 En 1946 John von Neumann desarrolló un algoritmo para simular mecánicamente los números aleatorios, primero se seleccionaba un número realmente aleatorio llamado “semilla” (seed en inglés) este puede provenir de los ruidos del ambiente, o de la hora especifica (no es tan importante el cómo se obtenga este número, lo importante es que sea de una fuente realmente aleatoria), después esta “semilla” se introduce como entrada a una simple ecuación en donde se multiplicaba por sí mismo y el resultado era la mitad de este nuevo número (ejemplo 121*121= 14641 à nuevo número= 464), después este nuevo número se usa como semilla y se repite el proceso tantas veces sea necesario, a este algoritmo se le conoce como el método de los cuadrados medios y es un algoritmo de pseudoaleatoriedad ; es uno de muchos métodos de este tipo (en su gran mayoría se usa una forma similar para generar números aleatorios) .
El problema con este tipo de algoritmos es que la aleatoriedad de la secuencia depende de la aleatoriedad de la semilla; es decir misma semilla, misma secuencia.
Las diferencias entre un generador de números realmente aleatorios (como el ruido) y un generador de pseudoaleatoriedad, si las dos las representamos gráficamente (como el ejemplo anterior) al principio parecen similares, pero si seguimos generando números aleatorios de formar pseudoaleatoria esta eventualmente se va a repetir, esto sucede porque el algoritmo eventualmente llegara a una semilla que ya había utilizado anteriormente y el ciclo se repetirá (en el siguiente gif se representa el camino blanco como una fuente realmente aleatoria y el camino azul por una fuente pseudoaleatoria) http://makeagif.com/tXv0lU


La longitud antes de que un algoritmo pseudoaleatorio se repita se llama “periodo”, este se limita única y exclusivamente por la semilla inicial, por ejemplo si se usa una semilla de 2 digitos este algoritmo podrá producir máximo 100 números antes de que se repita esta misma semilla y se repita el ciclo, una semilla de 3 dígitos puede producir máximo 1000 números antes de generar la misma semilla y repetir el ciclo.
Así con forme aumentamos la longitud de la semilla se aumentan la seguridad de que alguien no pueda adivinar el siguiente número, es claro que con el tiempo sería posible para una computadora calcular millones de posibilidades para poder dar con esa semilla, pero entre más grande el numero asumimos que es relativamente seguro debido a la cantidad de tiempo que tendría que pasar una computadora calculando con las semillas, un ejemplo para que se entienda mejor, es como si dejamos nuestra bicicleta con un candado de combinación de 4 dígitos 



sabemos que si alguien tiene el suficiente tiempo eventualmente podrá probar todas las posibles combinaciones de la contraseña hasta que la adivine, pero se puede asumir que para un lapso de un par de horas esta estará segura, porque no hay muchas probabilidades que alguien adivine la contraseña en tan corta cantidad de tiempo, algo similar sucede con los algoritmos pseudoaleatorios ,pero mientras las computadoras sigan siendo cada vez más rápidas es importante que la cantidad de bits que se dedican a generar las semillas también incrementen.
Bibliografías:

miércoles, 20 de agosto de 2014

One time pad

Tarea 1


En el codigo anterior se hace un pequeño cifrado de una palabra que proporcione el usuario asi como la llave y despues se realiza un XOR con la llave y la palabra para obtener de resultado un mensaje cifrado