Dead XOR Alive

Dead XOR Alive

Hace unos años un buen e inquieto amigo (Maese Curro) me escribió un correo acerca de esta historia, la leí y me encantó. Hace unos días jugando con puertas XOR, me acordé de ella y como no, decidí contarla en este lugar de relatos.

Un carcelero le propone el siguiente juego a dos convictos para que puedan salvar su vida. Si aciertan el cuadrado mágico, se salvan, si no, mueren. Explico las normas del malévolo juego.

Participan, un maligno y despiadado carcelero, un convicto que observa y participa en el juego y el convicto adivino.

El carcelero distribuye monedas con caras o cruz aleatoriamente en un tablero de ajedrez, posteriormente elige una moneda como cuadro mágico; en este momento, el convicto participante que ha visto el cuadro mágico, debe cambiar una moneda de cara a cruz o de cruz a cara. Si el penado que acompaña al carcelero que ha visto la distribución, el cuadro mágico y la moneda que él mismo ha cambiado, dijese algo al convicto adivino, mueren ambos. Solo esto.

El reo participante pasa a una habitación aislada y con todo esto y nada, el convicto adivino entra en la sala del tablero de ajedrez y observando este sin saber nada sobre distribuciones, cuadro mágico y moneda cambiada, debe acertar el cuadro mágico elegido por el carcelero. Ohhhhhhhhhh!

Está claro que el convicto adivino, de adivino nada, simplemente debe acordar una estrategia previa con el convicto participante y … hablemos del sistema binario y de paridad.

Lo primero de todo, un tablero tiene 64 casillas y los presos deciden darle un valor de 0 a la primera casilla empezando de izquierda a derecha y de arriba hacia abajo, un 1 a la siguiente y así hasta llegar hasta la última casilla que valdrá 63 tal y como se muestra en la figura de la izquierda, a posteriori convierten sus valores decimales al sistema binario quedando como el tablero de la derecha.

tableto decimal.png

Para los que no recuerden como se convierte de decimal a binario y viceversa, el número 36 por ejemplo equivale en el sistema decimal 3.101+6.100=30+6 y en binario le corresponde el número 100100 1.25+0.24+0.23+1.22+0.21+0.20=1.32+0.16+0.8+1.4+0.2+0.1=36

Para convertir un número de decimal a binario dividimos continuamente por la base guardando los restos de la división, pero al reves; en el ejemplo 36 es dividido entre 2 continuamente y los restos son almacenados como dígitos del número en sistema binario. Recordemos que D = d . C + r, donde el cociente es la base del sistema numérico el divisor es el dividendo de la siguiente división y el resto el dígito. En el post sobre sistemas de numeración posicional en Arithmos, hablo algo más sobre el tema en cuestión.

36=18.2+0, 18=9.2+0, 9=4.2+1, 4=2.2+0, 2=1.2+0, 1=2.0+1, por tanto 36 equivale a 100100

Bueno, ya tenemos un tablero de ajedrez donde podemos determinar mediante un valor binario el cuadro mágico elegido por el carcelero; si este selecciona la casilla 36, el convicto adivino tendrá que adivinar la casilla 100100. ¿Y como? siguiente paso la paridad.

Un tablero de ajedrez tiene 64 casillas, potencia de 2, concretamente 25, de modo que los convictos decidieron dividir el tablero de tantas formas como dígitos tiene el mayor número de este en binario, es decir de 6 formas distintas, para así poder determinar la paridad de caras y cruces en cada una de estas zonas; si existe en cada zona sombreada un número impar de caras, se le asigna un 1 y si es par, un 0 de modo que cuando el carcelero distribuya las monedas, el participante pueda obtener un valor significativo de la paridad del tablero y de este modo cada distribución de paridad, identifica únicamente cada reparto, al cambiar una moneda el valor de paridad es totalmente distinto. Estas eran las zonas de recuento de caras y su peso posicional.

PARIDAD03

El convicto participante debería encargarse de contar las caras de cada tablero que coincidían con la zona sombreada, si el número de caras era impar, un 1, si era par, un 0, y para entenderlo mejor, lo veremos con un ejemplo sencillo donde los asteriscos simulan la cara de una moneda y donde no hay nada, debería albergar una moneda con cruz.

PARIDAD02.png

Este tablero tendría una paridad 011101.

  • El primer tablero tiene dos monedas con cara en la zona sombreada, 2 es par, un 0.
  • El segundo tiene tres caras sobre la zona sombreada, 3 es impar, un 1
  • El tercero tiene tres caras sobre la zona sombreada, 3 es impar, un 1
  • El cuarto tiene una cara sobre la zona sombreada, 1 es impar, un 1
  • El quinto tiene dos caras sobre la zona sombreada, 2 es par, un 0
  • Por último, el sexto, tiene tres caras sobre la zona sombreada, 3 es impar, un 1

No es difícil ¿verdad? pero, en realidad, para el que quiera comprobarlo es una operación XOR de cada posición. Abrimos la calculadora de Windows, menú programador y realizamos la operación XOR sobre las posiciones 0, 9, 18, 25, 27, 32 y 36 que son las casillas del tablero donde existen caras, con resultado 29 que es 011101->29 = 0.32+1.16+1.8+1.4+0.2+1.1.

¿Y que es la operación XOR?, es una operación lógica con la siguiente tabla que equivale a la expresión algebraica (algebra de Boole)

xor.png

xor

si sus valores son iguales, resultado 0, si son distintos, un 1. Tiene la siguiente propiedad, si al resultado de la operación le volvemos a realizar la operación inversa, obtenemos el valor inicial. Nota 1

xor8

(Esto por ejemplo con la suma o con otras operaciones no ocurre, 4+5=9 y 4+9≠5)

fantástico ¿no? 011 XOR 101 = 110 y 110 XOR 101=011, o

XOR04.png

Y ya que conocemos como se realiza una operación lógica XOR es cuando estamos dispuestos a resolver el enigma. El carcelero elige el cuadro mágico, por ejemplo la casilla 7 de nuestro sencillo ejemplo que equivale a 000111, de modo que el convicto participante realiza la operación XOR sobre la paridad del tablero y el valor del cuadro mágico 011101 XOR 000111=011010 que equivale al número 26!!!! pues entonces el convicto participante ya sabe que la moneda de la casilla 26 debe darle la vuelta para cambiar la paridad del tablero, quedando la paridad de nuevo en el valor 000111 que es… TACHÁN! EL CUADRO MÁGICO, el número 7 en binario.

XOR05.png

De este modo, el convicto adivino solo debe salir, contar las caras en cada zona, calcular la paridad y convertir el número binario a decimal, determinando que la casilla 7 es la elegida por el carcelero.

¿Que ha pasado? Por una parte tenemos la paridad del tablero que es única (operación XOR de los elementos del tablero con cara), llamaremos P1 a la paridad del tablero inicial y cn a las casillas con caras

paridad1

el carcelero selecciona el cuadro mágico que llamaremos M y el convicto calcula de nuevo XOR para obtener la moneda cambiante C. Al hacer XOR con el cuadro mágico estamos creando un nuevo tablero con una nueva paridad P2 que es igual a la moneda que debe cambiar

paridad2.png

El convicto participante cambia la moneda C de cara a cruz o viceversa y ya tenemos un nuevo tablero con una paridad distinta y aquí es cuando la característica de XOR hace su efecto, ¿que dijimos en la nota 1? que si al resultado de una operación XOR se le realiza con uno de los elementos de la operación, obtenemos el otro valor de la operación.

xor8

El convicto adivino, sale al escenario y se encuentra un nuevo tablero con una paridad distinta, la calcula y esto es lo mismo que realizar una operación XOR de la primera paridad sobre el valor de la casilla C que cambió y si la primera paridad con el cuadro da como resultado la casilla de cambio, la operación XOR de la paridad inicial con la casilla que cambió debe dar… pues el cuadro mágico.

paridad3.png

¿No son preciosas las matemáticas? ¿No es fantástica el algebra de Boole? Pues gracias a esto, puedo escribir este post desde mi ordenador. Los convictos dejaron de serlo y actualmente están trabajando en Google y JetBrains.

Os dejo el enlace a la página que leí hace unos años que además tiene unos tableros interactivos para adivinar y jugar con el cuadro mágico.

Además he creado en C# y WPF un pequeño simulador para windows que podréis encontrar en el siguiente enlace. Descargar el rar y correr el ejecutable (libre de virus y demás, os adjunto el hash) El mio es diferente de la página WEB, pero a mi me gusta más. 😉

El hash SHA-512 del archivo WinRar del enlace es CADC5728F7C59C67B31FB7EA1D7D7F6B694F8390BF308667A937709D3D1D2DBFE5D5C4013800A1CDC36A6486A267C996D01DAA98EE92F007A3138DEB7417B353.

DeadXORAlive.png

Simulador de DeadXORAlive

Si alguien desea ver el código de la app, en wakicode puede hacerlo.

Pd: El correo de mi buen amigo Curro no tiene desperdicio. Cada vez que veo un correo suyo, lleno el candil de aceite para pasar ratos de lectura, como siempre Paco, gracias por tus letrillas.

Maese Joaquín, le emborrono estas letrillas, confiando en que a vuesa merced, no le va a hacer falta utilizarlo, pero creo de justicia el proporcionarle el lugar del que extraje el demoníaco acertijo, del tablero de ajedrez y de los dos prisioneros.

Tenga cuidado no estruje el caletre en demasía, que también Alonso Quijano lo fizo con los libros de caballería y mire donde acabó su triste figura.

Recuerde que siempre hay más de una solución, seguro que la suya, es diferente.

http://datagenetics.com/blog/december12014/index.html

De un viejo fisgoneador de papeles y avaro de relatos.

 

Algoritmos HASH

Algoritmos HASH

Un hash es un algoritmo matemático el cual obtiene de un archivo, un texto, un número, un lo que sea, una secuencia de caracteres con una longitud fija, es decir mediante un valor de entrada de longitud indefinida, obtenemos como salida una secuencia con una longitud fija de caracteres. Por ejemplo la palabra “Arithmos” le corresponde un hash con el algoritmo md5 de “fc79f1497d77cefc60ddde4345ea7437″ y a estas dos palabras “Joaquín Martínez” le corresponde el hash md5 “80e3ac98136b907181702294c9a7b0a4″.Lo importante de un algoritmo hash es que es muy fácil transformar los datos de entrada en los de salida, pero muy difícil, por no decir imposible, hacerlo al contrario, es decir con el hash obtener el valor de entrada, de modo que estamos representando unívocamente un conjunto de datos.

función hash(mensaje)= hash

hash-flow.png

Su uso varía desde la aseguración de la integridad de mensajería, se genera un hash antes de su envío y se compara con otro hash generado cuando se ha recibido, si ambos hash son iguales, el mensaje no ha variado, validación de documentos comprobando que su hash inicial coincide a posteriori validando que el documento no se ha modificado, firma, autenticación y validación de contraseñas, un servidor guarda el hash de la contraseña y cuando el usuario introduce la contraseña, se genera su hash y se compara con el almacenado en el servidor de modo que no se guardan contraseñas en los servidores evitando su robo, si todavía existe alguno que no lo hace … 😦

Con todo esto ya nos podemos hacer una idea de cuáles pueden ser sus características.

  • Imposibilidad de obtener el elemento de entrada a partir del hash
  • Imposibilidad de encontrar un conjunto de datos diferentes con el mismo hash (matemáticamente es improbable pero puede ocurrir)
  • Transformación de un elemento de tamaño indefinido en otro de tamaño fijo
  • Facilidad de cálculo

Los algoritmos de generación hash más conocidos son el MD5, SHA-1 y SHA-2 aunque hay unos pocos más ;-).

MD5. Es un algoritmo de 128 bits el cual no es seguro actualmente y no se usa a no ser para usos donde no sea necesaria mucha seguridad. El código hash se genera en 64 pasos y al final obtendremos un texto de 32 caracteres.

Existen páginas con millones de hash y su asociación hash y en cuestión de segundos, estaría al descubierto la palabra. He realizado una prueba en md5online.es y el hash F81AA6CEBB7F4B382F153383DD15695D de la palabra “palíndromo” ha sido descifrado en un par de segundos.

Arithmos -> FC79F1497D77CEFC60DDDE4345EA7437

SHA-1. Parecido al MD5 pero con 160 bits y necesita 80 pasos para obtener un hash de 40 caracteres. Como el algoritmo MD5, se han encontrado colisiones y no es seguro utilizarlo.

Arithmos -> SHA-1 -> 40 caracteres -> A58A0B92E639465AE50F4D14B4578CA5355087A5

SHA-2. Basado en SHA-1 pero su diseño es diferente y el rango de salida es mayor. De este, existen variedades como el SHA-224, SHA-256, SAH-384 o el SHA-512. Este último con 80 rondas y una palabra de 160 bits y 128 caracteres de longitud

Arithmos -> SHA-256 -> 64 caracteres -> 9F0C067C868304FF6BEA9F087DFCE52E4A4ADB433AA72AA0536388BFF52B4BC4

Arithmos -> SHA-512 -> 128 caracteres ->

C27460343460AF645D0731498BF69F85A63635F80A260A667A6DB72596F8E602CF8A9894889B0F9F9FAC4B3441CAD73D9F69D2A05924CEC2E46C8BCAD2C75893

Desde la WEB passwordsgenerator.net podréis genera cuantos hash queráis.

En hashtoolkit.com he realizado la obtención de la entrada mediante el hash con la palabra “palíndromo” mediante bases de datos de palabra y hash para md5, SHA-1, SHA-256, SHA-384 y SHA-512 con resultado positivo, es decir tienen un conocimiento previo de la palabra y su hash de ahí que se pueda comparar y encontrarla.

Pd: Existen bases de datos de hash de contenidos maliciosos para su consulta, lo guardamos todo!

Algoritmo de Luhn

Algoritmo de Luhn

El algoritmo de Luhn fue ideado por Hans Peter Luhn, informático alemán de los primeros, el cual trabajó para IBM y cuyo ingenio nos ha dejado un legado todavía en uso.

hans-peter-luhn-ibm-1958.jpg

El algoritmo de Luhn es el utilizado por las tarjetas de crédito o por el IMEI de nuestros teléfonos para ser validados y otras múltiples aplicaciones, donde podemos verlo en la publicación sobre dígitos de control II de ARITHMOS, aunque en este post, le dedicaremos una líneas exclusivas a él ¿Cómo se calcula el algoritmo de Luhn?

Lo que pretende esencialmente el algoritmo, no es otra cosa que validar que los números de una secuencia son correctos y que no existe ningún error, de modo que su objetivo en este caso es crear un dígito de verificación final que permita indicar si esa secuencia es válida o no. Bien, pues este dígito de verificación se añade al final de secuencia numérica y su cálculo es sencillo siguiendo las siguientes instrucciones.

    1. Multiplicar por 2 desde la izquierda a la derecha los números impares
    2. Si cualquiera de estos números multiplicados por 2 es mayor de 9, le calculamos el módulo o resto de 9 para obligar a que tenga solo un dígito.
    3. Efectuamos la suma de estos números impares multiplicados por 2 y simplificados y le llamaremos Si.
    4. Sumamos los pares y le llamaremos Sp.
    5. Sumamos Sp y Si y a esta suma le calculamos el módulo o resto de 10
    6. Por último, el resultado obtenido en el paso anterior, se lo restamos a 10 obteniendo el dígito de verificación.

Lo vemos en un ejemplo. Tarjeta de crédito con número 416881884444712X y X es el número de verificación.

      1. Multiplicamos por 2 de izquierda a derecha los dígitos impares. 4×2=8, 6×2=12, 8×2=16, 8×2=16, 4×2=8, 4×2=8, 7×2=14, 2×2=4 obteniendo la lista (8, 12, 16, 16, 8, 8, 14, 4)
      2. Reducimos los mayores de 9 calculando el módulo de 9. Para los que no lo recuerden, el módulo de 9 es el resto obtenido al dividir un número entre otro, por ejemplo 20 mod 9 = 2 porque como D=d.c+r 20=9×2+2, así que a los números mayores de 9 les calculamos el módulo de 9 quedando la lista (8, 12 mod 9, 16 mod 9, 16 mod 9, 8, 8, 14 mod 9, 2) = (8, 3, 7, 7, 8, 8, 5, 4)
      3. Calculamos Si=8+3+7+7+8+5+4=50
      4. Sobre los dígitos pares (1, 8, 1, 8, 4, 4, 1) Calculamos Si=1+8+1+8+4+4+1=27
      5. Sumamos ambas sumas y le calculamos el módulo de 10. (50+27)=77. 77 mod 10 = 7.
      6. Por último le restamos a 10 el resultado del módulo X=10-7=3 quedando el número final de la tarjeta 4168818844447123.

De este modo cuando realizamos un pago y nos equivocamos al introducir el número de la tarjeta, la aplicación nos avisa de que el número no es un número válido de tarjeta.
Su cálculo es muy sencillo y como muestra de ello he aquí una sencilla función para su cálculo bajo el lenguaje Kotlin del que actualmente estoy enamorado.


fun main (args:Array) {
    val number= "416881884444712"
    val luhn= checkDigitLuhn(number)
    println("El código de verificación es $luhn")
    println("El número final es $number$luhn")
}

fun checkDigitLuhn(numbers:String): Int {
    val list = numbers.map{ e-> e.toString().toInt()}
    return 10 - ((list.filterIndexed { index, i -> index % 2 == 0 }
        .map { (it*2) % 9 }.sum() + 
        list.filterIndexed { index, i -> index % 2 ==1 }.sum()) % 10)
}

daría como resultado…


El código de verificación es 3
El número final es 4168818844447113