Aunque no parezca que esto tiene mucho que ver con la temática del blog, la tiene.
La Universidad de Valladolid tiene una web en la que propone unos problemas a resolver programando en cualquier lenguaje (o eso creo) de programación, para luego enviárselo y una vez revisado aparecer en un ranking según bien o mal tu solución.
No deja de ser curioso que la mayoría de los problemas que he visto (he visto pocos) son matemáticos, incluso muchos de ellos los hemos visto en este blog.
Yo creo que me voy a apuntar a ver si hago algunos, aunque cada vez que pienso lo que desaprovecho el tiempo y lo que luego me quejo de tener poco tiempo (viva la procrastinación).
(Vía meneame, encontrado de casualidad haciendo una búsqueda un tanto absurda)
(Para quién no lo sepa, el blog está un tanto abandonado por la falta de tiempo comentada y sí este tema salió en meneáme hace ya cuatro meses)
Autor: Fran | Publicado el 21 de February de 2007
Comments Off
Categorías: Informática, Matemáticas
Para cerrar totalmente la serie de posts sobre criptografía, voy a realizaros una especie de índice desde el cual podáis acceder a cada post.
Autor: Fran | Publicado el 29 de January de 2007
Comments Off
Categorías: Criptografía, Informática
El cifrado de Vernam
El protocolo de cifrado que se usa en criptografía cuántica es posiblemente el más sencillo de todos y hasta ahora, el único que se ha demostrado que es irrompible, el cifrado de Vernam, o One Time Pad. Como ya se ha explicado anteriormente, no me extenderé demasiado, solamente diré que consiste en una clave 100% aleatoria (no vale pseudoaleatoria) de igual longitud que el mensaje y que lo único que hay que hacer para cifrar es un XOR con el mensaje y la clave. ¿Cuál es el problema? Que solo se puede usar una vez, porque si usáramos dos veces la misma clave, el problema de encontrar el texto en claro sería trivial para cualquier criptoanalista. Entonces, si no podemos usar la misma clave dos veces, tendremos que hacer llegar la clave al receptor de alguna manera, o bien quedando con él antes o a través de un canal seguro. La idea del canal seguro es inútil, porque si de verdad exisitiera no tendríamos ni que cifrar el mensaje, respecto a lo de quedar antes en persona, es lo que se solía hacer para usar este cifrado, como los cuadernos con claves de un solo uso que se usaban en la Segunda Guerra Mundial y que Stephenson narra perfectamente en su Criptonomicón. Pero hoy día, la opción de los cuadernos de un solo uso queda totalmente fuera de uso y es poco útil en comunicaciones industriales y operaciones que se realizan a diario.
En definitiva, tenemos el sistema ideal de cifrado, sencillo y eficaz, pero no podemos usarlo por un pequeño problema técnico a la hora de distribuir la clave. La mecánica cuántica viene a solucionar este problema proponiendo un método para distribuir una clave binaria, tan larga como se quiera, totalmente aleatoria y asegurándose de que solo el emisor y el receptor la poseen, justo lo que necesitamos.
(Leer el resto del post)
Autor: Fran | Publicado el 17 de January de 2007
Comments Off
Categorías: Ciencia, Criptografía, Informática
Project Euler es una web donde podemos encontrar muchos desafíos que involucran matemáticas y programación. Se trata de una serie de problemas matemáticos que requieren casi obligatoriamente la creación de un programa para resolverlos. Por ejemplo:
Si el 2 es el primer número primo, el 3 el segundo, el 5 el tercero…encuentra el primo número 10001.
Podemos verlos todos sin necesidad de registrarnos, pero si nos registramos podemos ir sumando puntos conforme vamos resolviendo las cuestiones. Cada uno de los problemas comienza con 20 puntos cuando es propuesto y va bajando de puntuación conforme los usuarios van resolviéndolo. Yo he estado mirando unos cuantos, pero como mi nivel de programación es nulo no he podido hacer mucho. He resuelto uno, el problema número 9 en estos momentos:
Encuentra una terna pitagórica (a,b,c) tal que a+b+c=1000
Ese también lo podéis resolver vosotros. Buscad en este blog y encontraréis la información suficiente.
Y si vais resolviendo problemas podéis usar lo comentarios para informarnos y para dar o pedir ayuda. Seguro que los informáticos del blog estarán encantados.
Autor: ^DiAmOnD^ | Publicado el 4 de January de 2007
Comments Off
Categorías: Informática, Juegos
Cifrado RSA
El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (la sigla RSA es Rivest Shamir Adleman) en el MIT.
El cifrado RSA es un algoritmo de cifrado de clave pública (o asimétrico) por bloques, que como todos los cifrados de clave pública tiene dos claves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la clave pública de cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.
El algoritmo sigue los siguientes pasos:
- Se construye un número “N”, que resulta del producto de dos primos “p” y “q” (normalmente son números muy grandes). Teniendo N = p · q y Φ(N) = (p-1) · (q-1)
- Se selecciona un número “e”,1 < e < Φ(N), tal que MCD (e, Φ(N)) = 1 (“e” y Φ(N) son primos relativos).
- Se calcula el inverso de “e”, denotado por “d”, tal que e · d = 1 (mod Φ(N))
- Con esto se consiguen las claves (e, d), siendo la clave pública (e, N) y la clave privada (d, N).
Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:
- Cifrado: C = Me (mod N) con MCD (M, N) = 1 y M < N
- Descifrado: M = Cd (mod N)
La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.
(Más información en Wikipedia)
(Leer el resto del post)
Autor: Fran | Publicado el 20 de December de 2006
Comments Off
Categorías: Criptografía, Informática, Matemáticas discreta, Números primos
¿Qué es el cifrado de clave pública?
Un cifrado de clave pública (o asimétrica), es aquel cifrado que se basa en el uso de una pareja de claves, pública y privada, de las cuales una se usa para cifrar y la otra para descifrar.
Ambas claves están relacionadas por una función trampa, suele ser una función matemática. Las claves se calculan usando la función y la inversa de ésta, siendo la función inversa la función trampa al ser muy difícil o imposible de calcular.
-
Función irreversible
x ∈ A, f(x) fácil de calcular
y ∈ f(A), x = f-1(y) difícil de calcular
-
Función trampa
x = f-1(y) Es calculable conociendo la trampa de la función. Pero sin conocer dicha trampa, y = f(x) es unidireccional.
Además la trampa sólo se puede calcular con la clave privada.
(Leer el resto del post)
Autor: Fran | Publicado el 15 de December de 2006
Comments Off
Categorías: Criptografía, Informática, Matemáticas discreta
Lo que hoy os voy a contar es una paradoja (por llamarlo de alguna manera), que se da en las redes informáticas.
Una de las formas más comunes para transportar datos es usar medios de almacenamiento como cintas magnéticas, DVDs, … Estos medios, obviamente, se transportan físicamente, es decir, con camiones/aviones/barcos. Y aunque este método de transporte de datos parece anticuado respecto a las redes actuales con frecuencia es rentable, como para apliaciones con anchos de banda enormes o en el que el coste por bit transportado es un factor clave.
Y es que esto se demuestra con un cálculo sencillo:
- Una cinta magnética estándar puede contener 200 Gigabits de información.
- Una caja de 60x60x60 cm, puede contener aproximadamente 1000 cintas. Teniendo así cada caja, una capacidad total de 200 Terabytes, o 1600 Terabits.
- Una caja de cintas puede enviarse a cualquier parte de EEUU en 24 horas por FedEx.
Con estos datos tenemos que el ancho de banda de esta transmisión es de 1600 Terabits/86400 seg, o lo que es lo mismo 19 Gigabits/seg. Si el destino estuviera a una hora el ancho de banda se incrementa a casi 400 Gigabits/seg. A este ancho de banda no llega ninguna red todavía, que yo sepa, aunque como es obvio la velocidad de las redes aumenta, pero también la de las cintas y discos duros, y la de los transportes.
Y con el coste ocurre igual:
- Una cinta magnética cuesta aproxidamente 40$ (comprada al mayorista) y se puede usar 10 veces.
- Cada caja cuesta, entonces, 4000$ por uso.
- El envío cuesta 1000$, seguramente menos.
Y conseguimos un coste de 5000$ por 200 TB, o lo que es igual a 3 centavos por cada Gigabyte.
(Sacado del libro Redes de computadoras)
(Los datos pueden estar desfasados, ya que mi edición del libro es del 2003)
Autor: Fran | Publicado el 24 de November de 2006
Comments Off
Categorías: Curiosidades, Informática
¿Qué es un cifrado de clave privada?
Un cifrado de clave privada (o simétrico), se basa en un algoritmo/método/cifrado que usa una única clave para cifrar/descifrar los mensajes/criptogramas.
Como ya os comenté existe un principio, el llamado principio de Kerkhoff, que dice que todos los algorítmos de cifrados y descifrados deben ser públicos y conocidos por todos, por tanto lo único secreto es la clave del algorítmo, esta clave se convierte en la piedra angular del algorítmo.
En este principio se basan todos los cifrados de clave privada, en mantener secreta la clave bajo cualquier medio, ya que es lo único que no permite a los usuarios malintencionados descifrar nuestros mensajes. Para ello la clave se comparte por canales seguros (ya veis que este es su punto débil, ya que si tenemos un canal seguro no necesitamos un cifrado) entre los interlocutores del mensaje.
(Leer el resto del post)
Autor: Fran | Publicado el 17 de November de 2006
Comments Off
Categorías: Criptografía, Informática
Cifrado por transposición o permutación
Cada letra (o carácter) se intercambia por otra del mensaje, reordenando de algún modo las letras, pero no disfrazándolas. Para este tipo de cifrado se usan múltitud de métodos, como colocar las letras en una matriz de una manera y sacarlas de otra manera diferente.
Cifrado Vernam
Según el principio de Kerkhoff todos los algorítmos de cifrados y descifrados deben ser públicos y conocidos por todos, lo único secreto es la clave del algorítmo, esta clave se convierte en la piedra angular del algorítmo.
Basándose en este principio, el cifrado perfecto (el cifrado Vernam) debe ser público con su clave en secreto y ésta debe tener la misma longitud del mensaje, ser generada aleatoriamente y solamente puede ser usada una sóla vez.
Para cifrar el mensaje se realiza una operación XOR (or exclusivo) entre el mensaje y la clave.
Como se puede observar este método sería perfecto de no ser porque cada clave generada aleatoriamente debería ser generada también aleatoriamente e idéntica a la del emisor, por el receptor del mensaje, algo que en principio es muy díficil.
(Más información en Wikipedia)
Post anterior: Cifrado por sustitución II
Autor: Fran | Publicado el 8 de November de 2006
Comments Off
Categorías: Criptografía, Informática
Seguimos con la criptografía, y más concretamente con más algoritmos de cifrado por sustitución.
Cifrado de Vigènere
Se escoge una clave que usaremos para que al cifrar el mensaje cada letra tenga un diferente cifrado, así evitamos la repetición de carácteres en el criptograma.
Así, se usa una clave que en realidad es un trozo de texto, puede ser cualquier palabra o conjuntos de letras desordenado, por ejemplo GATO, siempre es mejor coger una clave más corta que el mensaje a cifrar.
Y se realiza el siguiente método:
Mensaje: AUTOESCUELA
Clave: GATO
Se van asignando los carácteres uno a uno del mensaje a la clave formando pares de carácter del mensaje y carácter de la clave, si llegamos al final de la clave se empieza de nuevo por el primer carácter de ésta o se puede usar el mensaje (lo explicaré más detalladamente después), de modo que tendríamos:
(A, G) (U, A), (T, T), (O, O), (E, G), (S, A), ….
Ahora vamos a usar una tabla, llamada la tabla de Vigenère (¿a qué no os lo esperabáis?), al igual que se hacía en el cifrado Polybios, para cifrar cada par de carácteres anterior. De modo que tenemos:
(A, G) = G
(U, A) = U
(T, T) = M
(O, O) = C
….
Y el mensaje cifrado es: GUMCKSVJKLT
Como decía anteriormente, se puede usar una versión un tanto diferente de este cifrado que se basa en un método llamado autoclave, este método consiste en que si alguna vez llegamos al fin de la clave no pasaríamos al principio de ésta, en su lugar usaríamos el mensaje que tengamos como clave. Así con el ejemplo anterior, tendríamos:
(A, G) (U, A), (T, T), (O, O), En lugar de comenzar la clave de nuevo usaríamos el mensaje. (E, A), (S, U), ….
Corregido gracias a Papá Oso
Para descifrar, se haría completamente al revés, cogiendo carácter a carácter del mensaje cifrado y con la clave buscando la posición que ocupe en la tabla dicho par.
(Más información en Wikipedia en inglés)
(Leer el resto del post)
Autor: Fran | Publicado el 3 de November de 2006
Comments Off
Categorías: Criptografía, Informática
