encryption - vernam - web xor
¿Por qué se usa XOR en criptografía? (12)
Consideremos los tres operadores lógicos bit a bit más comunes
Digamos que podemos elegir un número (llamémoslo la máscara) y combinarlo con un valor desconocido
- Y se trata de forzar algunos bits a cero (los que se establecen en cero en la máscara)
- O se trata de forzar algunos bits a uno (los que están configurados a uno en la máscara)
XOR es más sutil, no se puede saber con certeza el valor de ningún resultado, sea cual sea la máscara que elija. Pero si aplica su máscara dos veces , recupera su valor inicial.
En otras palabras, el propósito de AND y OR es eliminar cierta información, y eso definitivamente no es lo que desea en algoritmos criptográficos (cifrado simétrico o asimétrico, o firma digital). Si pierde información, no podrá recuperarla (descifrarla) o la firma tolerará algunos cambios de un minuto en el mensaje, lo que le hará perder su propósito.
Dicho todo eso, eso es cierto de los algoritmos criptográficos, no de sus implementaciones. La mayoría de las implementaciones de algoritmos criptográficos también usan muchos AND, generalmente para extraer bytes individuales de 32 o 64 registros internos.
Normalmente obtienes un código como este (este es un extracto casi aleatorio de aes_core.c)
rk[ 6] = rk[ 0] ^
(Te2[(temp >> 16) & 0xff] & 0xff000000) ^
(Te3[(temp >> 8) & 0xff] & 0x00ff0000) ^
(Te0[(temp ) & 0xff] & 0x0000ff00) ^
(Te1[(temp >> 24) ] & 0x000000ff) ^
rcon[i];
rk[ 7] = rk[ 1] ^ rk[ 6];
rk[ 8] = rk[ 2] ^ rk[ 7];
rk[ 9] = rk[ 3] ^ rk[ 8];
8 XOR y 7 AND si cuento bien
¿Por qué XOR solo se utiliza en los algoritmos criptográficos y no se utilizan otras compuertas lógicas como OR, AND y NOR?
Creo que es simplemente porque dado un conjunto aleatorio de números binarios, un gran número de operaciones "OR" tenderían hacia todos los "1", así mismo una gran cantidad de operaciones "Y" tenderían hacia todos los ceros. Donde un gran número de ''XOR produce una selección aleatoria de unos y ceros.
Esto no quiere decir que AND y OR no son útiles, solo que XOR es más útil.
La prevalencia de OR / AND y XOR en la criptografía se debe a dos motivos:
Una estas son instrucciones rápidas.
Dos son difíciles de modelar utilizando fórmulas matemáticas convencionales
Creo que porque XOR es reversible. Si desea crear hash, querrá evitar XOR.
La propiedad XOR (a xor b) xor b = a resulta útil para los cifrados de flujo: para cifrar un bit de datos de ancho, se genera una secuencia pseudoaleatoria de n bits utilizando la clave criptográfica y el algoritmo criptográfico.
Sender: Data: 0100 1010 (0x4A) pseudo random sequence: 1011 1001 (0xB9) ------------------ ciphered data 1111 0011 (0xF3) ------------------ Receiver: ciphered data 1111 0011 (0xF3) pseudo random sequence: 1011 1001 (0xB9) (receiver has key and computes same sequence) ------------------ 0100 1010 (0x4A) Data after decryption ------------------
La razón principal es que si una variable aleatoria con distribución desconocida R1 está XORed con una variable aleatoria R2 con distribución uniforme, el resultado es una variable aleatoria con distribución uniforme, por lo que básicamente puede aleatorizar fácilmente una entrada sesgada, lo que no es posible con otros operadores binarios.
La salida de XOR siempre depende de ambas entradas. Este no es el caso para las otras operaciones que mencionas.
No es exactamente cierto decir que la operación lógica XOR es la única utilizada en toda la criptografía, sin embargo, es la única encriptación bidireccional en la que se usa exclusivamente.
Aquí está eso explicado:
Imagine que tiene una cadena de dígitos binarios 10101 y XOR la cadena 10111 con la que obtiene 00010
ahora su cadena original está codificada y la segunda cadena se convierte en su clave. Si utiliza la cadena XOR en su cadena codificada, recuperará la cadena original.
XOR le permite cifrar y descifrar fácilmente una cadena, las otras operaciones lógicas no.
Si tiene una cadena más larga, puede repetirla hasta que sea lo suficientemente larga, por ejemplo, si su cadena fue 1010010011 entonces simplemente escribiría su clave dos veces y se convertiría en 1011110111 y XOR con la nueva cadena.
Aquí hay un enlace de wikipedia en el cifrado XOR.
Para la criptografía simétrica, las únicas operaciones de elección real que mezclan bits con el cifrado y no aumentan la longitud son operaciones agregadas con acarreo, agregar sin acarreo (XOR) y comparar (XNOR). Cualquier otra operación pierde bits, se expande o no está disponible en las CPU.
Puedo ver 2 razones:
1) (Motivo principal) XOR no pierde información sobre el texto original.
2) (razón de Niza para tener) XOR es una función involutoria , es decir, si aplica XOR dos veces, recupera el texto original (es decir, XOR(k, XOR(k, x)) = x , donde x es su texto plano k es su clave). El XOR interno es el cifrado y el XOR externo es el descifrado, es decir, la misma función XOR se puede usar para cifrado y descifrado.
Para ejemplificar el primer punto, considere las tablas de verdad de AND, OR y XOR:
Y
0 AND 0 = 0
0 y 1 = 0
1 Y 0 = 0
1 Y 1 = 1 (¡Fuga!)
O
0 O 0 = 0 (¡Fuga!)
0 OR 1 = 1
1 O 0 = 1
1 OR 1 = 1
XOR
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
Todo en la primera columna es nuestra entrada (es decir, el texto sin formato) . La segunda columna es nuestra clave y la última columna es el resultado de su entrada "mixta" (encriptada) con la tecla usando la operación específica (es decir, el texto cifrado) .
Ahora imagine que un atacante tiene acceso a un byte cifrado, digamos: 10010111 , y quiere obtener el byte original de texto sin formato.
Supongamos que se utilizó el operador AND para generar este byte cifrado del byte de texto sin formato original. Si se usó AND, entonces sabemos con certeza que cada vez que veamos el bit ''1'' en el byte cifrado, entonces la entrada (es decir, la primera columna, el texto sin formato) DEBE también ser ''1'' según la tabla de verdad de Y. Si el bit cifrado es un ''0'' en su lugar, no sabemos si la entrada (es decir, el texto sin formato) es un ''0'' o un ''1''. Por lo tanto, podemos concluir que el texto plano original es: 1 _ _ 1 _ 111. Por lo tanto, se filtraron 5 bits del texto plano original (es decir, se podía acceder sin la clave).
Aplicando la misma idea a O, vemos que cada vez que encontramos un ''0'' en el byte cifrado, sabemos que la entrada (es decir, el texto sin formato) también debe ser un ''0''. Si encontramos un ''1'', entonces no sabemos si la entrada es ''0'' o ''1''. Por lo tanto, podemos concluir que el texto simple de entrada es: _ 00 _ 0 _ _ _. Esta vez pudimos filtrar 3 bits del byte de texto plano original sin saber nada sobre la clave.
Finalmente, con XOR, no podemos obtener ningún bit del byte de texto claro original. Cada vez que vemos un ''1'' en el byte cifrado, ese ''1'' podría haberse generado desde ''0'' o desde ''1''. Lo mismo con un ''0'' (podría provenir de ''0'' o ''1''). Por lo tanto, no se ha filtrado un solo bit del byte de texto sin formato original.
XOR actúa como un interruptor de palanca donde puede activar y desactivar bits específicos. Si desea "codificar" un número (un patrón de bits), lo XOR con un número. Si toma ese número codificado y lo vuelve a XOR con el mismo número, recuperará su número original .
210 XOR 145 gives you 67 <-- Your "scrambled" result
67 XOR 145 gives you 210 <-- ...and back to your original number
Cuando "codifica" un número (o texto o cualquier patrón de bits) con XOR, tiene la base de gran parte de la criptografía.
XOR es la única puerta que se usa directamente porque, sin importar cuál sea la entrada, la otra entrada siempre tiene un efecto en la salida.
Sin embargo, no es la única puerta utilizada en algoritmos criptográficos. Eso podría ser cierto para la criptografía de la vieja escuela, del tipo que involucra miles de cambios aleatorios y XORs y búferes rotatorios, pero para la criptografía basada en números primos se necesitan todo tipo de matemática que no se implemente a través de XOR.
XOR utiliza menos transistores ( 4 compuertas NAND ) que las operaciones más complicadas (por ejemplo, ADD, MUL) lo que hace que sea bueno implementarlo en hardware cuando el conteo de compuertas es importante. Además, un XOR es su propia inversa que hace que sea bueno para aplicar material clave (el mismo código se puede utilizar para el cifrado y el descifrado). La bellamente simple operación AddRoundKey de AES es un ejemplo de esto.