El cifrado XOR

Hace algún tiempo, se me ocurrió el siguiente problema:

Diseñar un cifrado recíproco con contraseña, en el que la función para encriptar y desencriptar sea la misma.

El resultado está aquí. Sigue leyendo si quieres saber cómo funciona.

Cifrado ROT-13

Los cifrados recíprocos existen desde hace mucho. Un buen ejemplo es el Cifrado ROT-13, que consiste en coger una letra del alfabeto, y rotarla 13 posiciones. Como el alfabeto (sin ñ) tiene 26 posiciones, si realizamos esta operación dos veces volvemos a la letra anterior: A -> N y N -> A.

Dial de cifrado ROT13

Cifrado XOR

Mi intención es disponer de un cifrado algo más seguro, que necesite una contraseña para encriptar/desencriptar. Y ahí es donde entra en juego el Cifrado XOR. Se basa en la operación lógica XOR (⊕), eXclusive OR:

ABA⊕B
000
011
101
110

Podemos realizar esta operación con un número si se la aplicamos a cada uno de sus bits. Por ejemplo, 220 ⊕ 153 = 69.

La magia del operador XOR es su reciprocidad: del mismo modo que 220 ⊕ 153 = 69, podemos observar que 220 ⊕ 69 = 153. Dado cualquier número A, la operación A ⊕ P = B y B ⊕ P = A. De este modo, podemos definir una contraseña P, que nos permita encriptar de forma reversible cualquier cadena, asignando un número a cada letra.

Así, si nuestra cadena es "HOLA MUNDO", nuestra constraseña es "CONTRASEÑA", y asignamos a cada letra la posición que ocupa en el abecedario reservando el 0 para el espacio; obtendremos la cadena encriptada "K BSRLBKKP".

Aplicando la operación de nuevo, con la contraseña "CONTRASEÑA" y la cadena "K BSRLBKKP", obtendríamos nuestra cadena tal y como queremos. Sin embargo, seguimos teniendo dos problemas:

Cadenas de distinta longitud

Una solución bastante simple es rellenar la contraseña con espacios hasta que tenga la longitud del texto. Sin embargo, esto no cambiaría nada, ya que A ⊕ 0 = A. Por ejemplo, con el texto "HOLA MUNDO ESTO ES UNA PRUEBA", la cadena que obtenemos es "K BSRLBKKP ESTO ES UNA PRUEBA".

Otra opción es rellenar la contraseña con algún símbolo que no sea un espacio. O para que sea menos predecible, repetir la contraseña en bucle. De este modo, para el texto anterior, usamos como contraseña "CONTRASEÑACONTRASEÑ", y el resultado de la encriptación es "K BSRLBKKPCTY CAPPÑ".

Gráfico de barras de la frecuencia (%) de las letras en castellano

Sin embargo, esta solución tampoco es segura, ya que al encriptar textos largos, sería fácil ver combinaciones de letras que se repiten mucho, y adivinar la contraseña mediante análisis de frecuencia. Pero todavía nos queda un recurso.

Funciones de hash

En criptografía, las funciones de hash son técnicas que permiten encriptar una cadena con un bajo coste, pero un coste altísimo de desencriptación, en ocasiones de milenios.

Este es el caso de la función SHA-256. Mediante esta función, podemos encriptar la contraseña y usarla para aplicar el cifrado XOR de forma segura. Para tener una contraseña más larga, tendremos una lista de salts que aplicaremos a la contraseña. No voy a entrar en detalle en esto último para que no quede un post demasiado largo, pero si tenéis interés podéis preguntar más en los comentarios.

Conclusiones

Después de todo esto hemos conseguido un cifrado recíproco medianamente seguro, y sobre todo, aprender un poco sobre criptografía.

Si lo deseas, puedes probar tú mismo este cifrado en esta página. Es una versión a la que he añadido un mayor número de caracteres.

1 comentario

La mayor secuencia de palabras encadenadas

Aunque todos conocéis este juego, existen varias modalidades distintas en función de la forma de encadenar palabras, y qué palabras son válidas. Para esta prueba, vamos a considerar estas reglas:

  1. El primer jugador dice una palabra cualquiera.
  2. Los siguientes jugadores deben decir una palabra que empiece por la última sílaba de la palabra anterior, ignorando los acentos.
  3. No se puede repetir una misma palabra 2 veces.
  4. Sólo son válidas palabras que figuren en el diccionario. Aunque figuren en el diccionario, nombres propios, siglas y monosílabos tampoco son válidos.
  5. Al encadenar las palabras, se ignoran sus acentos.
Datos

En primer lugar, necesitamos obtener todas las palabras del diccionario de la lengua española. Aunque la RAE no proporciona un listado completo de palabras, Giusseppe Domínguez nos lo facilita.

Tras esto, necesitamos la descomposición silábica de todas las palabras del diccionario. Puede parecer trivial, pero es una tarea bastante compleja, ya que hay un gran número de reglas y excepciones. Por suerte, la librería Pyphen hace ese trabajo decentemente por nosotros.

Finalmente, tenemos una lista de 86993 palabras válidas separadas por sílabas.

Palabras por número de sílabas en español

Secuencia más larga

Para calcular la mayor secuencia posible, construimos un grafo dirigido cuyos nodos son las palabras en cuestión, y las aristas comunican dos palabras que puedan ser encadenadas.

Ejemplo de grafo de palabras encadenadas

De esta manera, el problema se reduce a encontrar el camino dirigido más largo de este grafo. A diferencia del camino más corto, encontrar el camino más largo en un grafo es un problema NP-completo. Con un grafo de 86993 nodos y 43053416 aristas, tardaríamos 1.82 × 101012 años en encontrar la solución perfecta a este problema, así que debemos probar soluciones aproximadas.

Camino aleatorio

Escogiendo caminos de forma aleatoria, el camino más largo obtenido es de tan sólo 92 palabras:

sopa -> pantalla -> llaneza -> [...] -> ramuja -> jagüel -> güeldrés

Esto se debe a que es fácil llegar a un sumidero, es decir, una palabra a la que es posible llegar, pero no es posible salir de ella, como es el caso de güeldrés.

Otras aproximaciones

Existen otras formas de resolver este problema, como:

¿Se te ocurren más formas de resolver este problema? ¿Cuál es la cadena más larga que has sido capaz de encontrar? Si lo deseas, puedes dejar un comentario con tus resultados.

No hay comentarios

< RecientesAntiguas >