CRIPTOGRAFÍA

Los cifrados en bloque BEAR y LION fueron inventados por Ross Anderson y Eli Biham mediante la combinación de un cifrado de flujo y una función de cifrado hash . Los algoritmos utilizan un tamaño de bloque variable muy grande , del orden de 2 ¹³ a 2 ²³ bits o más ^{[ aclarar ]} . Ambos son cifrados Feistel generalizados (alternos) de 3 rondas , ^[1] utilizando la función hash y el cifrado de flujo como funciones redondas. BEAR usa la función hash dos veces con teclas independientes, y el cifrado de flujo una vez. LION usa el cifrado de flujo dos veces y la función hash una vez. Los inventores demostraron que un ataque contra BEAR o LION que recupera la clave rompería tanto el cifrado de flujo como el hash.









El cifrado Beaufort, creado por Sir Francis Beaufort , es un cifrado de sustitución similar al cifrado Vigenère , con un mecanismo de cifrado y un cuadro ligeramente modificados . ^[1] Su aplicación más famosa fue en una máquina de cifrado basada en rotor, la Hagelin M-209 . ^[2] El cifrado de Beaufort se basa en el cuadrado de Beaufort, que es esencialmente el mismo que un cuadrado de Vigenère pero en orden inverso, comenzando con la letra "Z" en la primera fila, ^[3] donde la primera fila y la última columna sirven al mismo propósito .

Usando el cifrado [ editar ]

Para cifrar, primero elija el carácter de texto sin formato de la fila superior del cuadro; llame a esta columna P. En segundo lugar, baje la columna P hasta la letra clave correspondiente K. Finalmente, muévase directamente a la izquierda desde la letra clave hasta el borde izquierdo del cuadro, el cifrado de texto cifrado del texto plano P con la tecla K estará allí.

Por ejemplo, si se encripta el carácter de texto plano "d" con la clave "m", los pasos serían:

1. encuentra la columna con "d" en la parte superior,
2. viaja por esa columna para encontrar la clave "m",
3. viaje al borde izquierdo del cuadro para encontrar la letra de texto cifrado ("J" en este caso).

Para descifrar, el proceso se invierte. El cifrado Beaufort es un cifrado recíproco , es decir, los algoritmos de descifrado y cifrado son los mismos.

Descripción algebraica [ editar ]

El cifrado de Beaufort se puede describir algebraicamente. Por ejemplo, usando una codificación de las letras A - Z como los números 0–25 y usando el módulo de suma 26, dejemos$${\ displaystyle M = M_ {1} \ puntos M_ {n}} ser los personajes del mensaje $${\ displaystyle C = C_ {1} \ puntos C_ {n}} ser los caracteres del texto cifrado y $${\ displaystyle K = K_ {1} \ puntos K_ {n}}ser los caracteres de la clave, repetidos si es necesario. Luego el cifrado Beaufort$${\ displaystyle E} puede ser escrito,

$${\ displaystyle C_ {i} = E_ {K} (M_ {i}) = (K_ {i} -M_ {i}) \ mod {26}}.

Del mismo modo, descifrado $${\ displaystyle D} usando la llave $${\ displaystyle K},

$${\ displaystyle M_ {i} = D_ {K} (C_ {i}) = (K_ {i} -C_ {i}) \ mod {26}}.

Descifrar como un cifrado de Vigenere [ editar ]

Debido a las similitudes entre el cifrado Beaufort y el cifrado Vigenère , es posible, después de aplicar una transformación, resolverlo como un cifrado Vigenère . Al reemplazar cada letra en el texto cifrado y el texto clave con su letra opuesta (de modo que 'a' se convierte en 'z', 'b' se convierte en 'y', etc.) se puede resolver como un cifrado Vigenère .

Distinguido de 'variante Beaufort' [ editar ]

El cifrado Beaufort no debe confundirse con el cifrado "variante Beaufort". En la variante Beaufort, el cifrado se realiza realizando el paso de descifrado del cifrado Vigenère estándar, y del mismo modo el descifrado se realiza mediante el cifrado Vigenère.

De Wikipedia, la enciclopedia libre

Saltar a navegaciónSaltar a búsqueda

Las cuatro funciones booleanas de 2 arios con peso de Hamming 1 están dobladas; es decir, su no linealidad es 1 (que es lo que muestra este diagrama) .

La siguiente fórmula muestra que una función de 2 arios se dobla cuando su no linealidad es 1:

$${\ displaystyle 2 ^ {2-1} -2 ^ {{\ frac {2} {2}} - 1} = 2-1 = 1}

La función booleana $${\ displaystyle x_ {1} x_ {2} \ oplus x_ {3} x_ {4}}está doblado; es decir, su no linealidad es 6 (que es lo que muestra este diagrama) .

La siguiente fórmula muestra que una función de 4 arios se dobla cuando su no linealidad es 6:

$${\ displaystyle 2 ^ {4-1} -2 ^ {{\ frac {4} {2}} - 1} = 8-2 = 6}

En el campo matemático de la combinatoria , una función doblada es un tipo especial de función booleana ; llamados así porque son lo más diferentes posible de todas las funciones lineales y de todas las funciones afines . Esto hace que las funciones dobladas sean naturalmente difíciles de aproximar. Las funciones dobladas fueron definidas y nombradas en la década de 1960 por Oscar Rothaus en una investigación no publicada hasta 1976. ^[1] Se han estudiado ampliamente para sus aplicaciones en criptografía , pero también se han aplicado al espectro extendido , la teoría de codificación y el diseño combinatorio.. La definición se puede ampliar de varias maneras, lo que lleva a diferentes clases de funciones dobladas generalizadas que comparten muchas de las propiedades útiles del original.

Se sabe que VA Eliseev y OP Stepchenkov estudiaron funciones dobladas, que llamaron funciones mínimas , en la URSS en 1962. ^[2] Sin embargo, sus resultados aún no se han desclasificado.

Transformación de Walsh [ editar ]

Las funciones dobladas se definen en términos de la transformación de Walsh . La transformación de Walsh de una función booleana$${\ displaystyle f: \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2}} es la función $${\ displaystyle {\ hat {f}}: \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z}} dada por

$${\ displaystyle {\ hat {f}} (a) = \ sum _ {\ scriptstyle {x \ in \ mathbb {Z} _ {2} ^ {n}}} (- 1) ^ {f (x) + a \ cdot x}}

donde a · x = a ₁ x ₁ + a ₂ x ₂ +… + a _n x _n (mod 2) es el producto escalar en Z n
2 . ^[3] Alternativamente, deje S ₀ ( a ) = { x ∈ Z n
2  : f ( x ) = a · x } y S ₁ ( a ) = { x∈ Z n
2  : f ( x ) ≠ a · x } . Entonces | S ₀ ( a ) | + | S ₁ ( a ) | = 2 ^ny por lo tanto

$${\ displaystyle {\ hat {f}} (a) = \ left | S_ {0} (a) \ right | - \ left | S_ {1} (a) \ right | = 2 \ left | S_ {0} (a) \ right | -2 ^ {n}.}

Para cualquier función booleana f y un ∈ Z n
2 la mentiras transformar en el intervalo

$${\ displaystyle -2 ^ {n} \ leq {\ hat {f}} (a) \ leq 2 ^ {n}.}

Además, la función lineal f ₀ ( x ) = a · x y la función afín f ₁ ( x ) = a · x + 1 corresponden a los dos casos extremos, ya que

$${\ displaystyle {\ hat {f}} _ {0} (a) = 2 ^ {n}, ~ {\ hat {f}} _ {1} (a) = - 2 ^ {n}.}

Por lo tanto, para cada a ∈ Z n
2, el valor de$${\ displaystyle {\ hat {f}} (a)}caracteriza dónde se encuentra la función f ( x ) en el rango de f ₀ ( x ) a f ₁ ( x ).

Definición y propiedades [ editar ]

Rothaus definió una función doblada como una función booleana$${\ displaystyle f: \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2}}cuya transformación de Walsh tiene un valor absoluto constante . Las funciones dobladas son, en cierto sentido, equidistantes de todas las funciones afines, por lo que son igualmente difíciles de aproximar con cualquier función afín.

Los ejemplos más simples de funciones dobladas, escritas en forma normal algebraica , son F ( x ₁ , x ₂ ) = x ₁ x ₂ y G ( x ₁ , x ₂ , x ₃ , x ₄ ) = x ₁ x ₂ ⊕ x ₃ x ₄ . Este patrón continúa: x ₁ x ₂ ⊕ x ₃ x ₄ ⊕… ⊕ x _n−1 x _n es una función doblada$${\ displaystyle \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2}}para cada par n , pero hay una gran variedad de otras funciones dobladas a medida que aumenta n . ^[4] La secuencia de valores (−1) ^f ( x ) , con x ∈ Z n
2 tomada en orden lexicográfico , se denomina secuencia doblada ; Las funciones dobladas y las secuencias dobladas tienen propiedades equivalentes. En esta forma ± 1, la transformación de Walsh se calcula fácilmente como

$${\ displaystyle {\ hat {f}} (a) = W \ left (2 ^ {n} \ right) (- 1) ^ {f (a)},}

donde W (2 ⁿ ) es la matriz de Walsh de orden natural y la secuencia se trata como un vector de columna . ^[5]

Rothaus demostró que las funciones dobladas solo existen para n , y que para una función doblada f ,$${\ displaystyle \ left | {\ hat {f}} (a) \ right | = 2 ^ {\ frac {n} {2}}}para todo a ∈ Z n
2 . ^[3] De hecho,$${\ displaystyle {\ hat {f}} (a) = 2 ^ {\ frac {n} {2}} (- 1) ^ {g (a)}}, donde g también está doblado. En este caso,$${\ displaystyle {\ hat {g}} (a) = 2 ^ {\ frac {n} {2}} (- 1) ^ {f (a)}}, entonces f y g se consideran funciones duales . ^[5]

Cada función doblada tiene un peso Hamming (número de veces que toma el valor 1) de 2 ^n -1 ± 2 ^{n / ₂ -1} , y de hecho está de acuerdo con cualquier función afín en uno de esos dos números de puntos. Así que la no linealidad de f (número mínimo de veces que es igual a cualquier función afín) es 2 ^n -1 - 2 ^{n / ₂ -1} , el máximo posible. A la inversa, cualquier función booleana con no linealidad 2 ^n -1 - 2 ^{n / ₂ -1} está doblada.^[3] El grado de f en forma normal algebraica (llamada la orden no lineal de f ) es como máximo ⁿ / ₂ (para n > 2 ). ^[4]

Aunque las funciones dobladas son muy raras entre las funciones booleanas de muchas variables, vienen en muchos tipos diferentes. Se han realizado investigaciones detalladas en clases especiales de funciones dobladas, como los homogéneos los ^[6] o las derivadas de un monomio sobre un campo finito , ^[7] pero hasta ahora las funciones dobladas han desafiado todos los intentos de una enumeración completa o clasificación .

Construcciones [ editar ]

Hay varios tipos de construcciones para funciones dobladas. ^[2]

• construcciones combinatorias: construcciones iterativas, construcción Maiorana-McFarland, diferenciales parciales, funciones dobladas de Dillon y Dobbertin, funciones dobladas a corto plazo, funciones iterativas dobladas
• construcciones algebraicas: funciones dobladas monomiales con exponentes de Gold, Dillon, Kasami, Canteaut-Leander y Canteaut-Charpin-Kuyreghyan; Funciones dobladas de Niho, etc.

Aplicaciones [ editar ]

Ya en 1982 se descubrió que las secuencias de longitud máxima basadas en funciones dobladas tienen propiedades de correlación cruzada y autocorrelación que rivalizan con las de los códigos Gold y Kasami para su uso en CDMA . ^[8] Estas secuencias tienen varias aplicaciones en técnicas de amplio espectro .

Las propiedades de las funciones dobladas son de interés natural en la criptografía digital moderna , que busca oscurecer las relaciones entre entrada y salida. Para 1988 Forré reconoció que la transformación de Walsh de una función se puede utilizar para demostrar que satisface el estricto criterio de avalancha (SAC) y las generalizaciones de orden superior, y recomendó esta herramienta para seleccionar candidatos para buenas cajas S que logren una difusión casi perfecta . ^[9] De hecho, las funciones que satisfacen el SAC en el orden más alto posible siempre están dobladas. ^[10] Además, las funciones dobladas están lo más lejos posible de tener lo que se llama estructuras lineales , vectores distintos de cero a tal que f( x + a ) + f ( x ) es una constante. En el lenguaje del criptoanálisis diferencial (introducido después de descubrir esta propiedad), la derivada de una función doblada f en cada punto distinto de cero a (es decir, f _a ( x ) = f ( x + a ) + f ( x )) es a función booleana equilibrada , tomando cada valor exactamente la mitad del tiempo. Esta propiedad se llama perfecta no linealidad . ^[4]

Dadas tan buenas propiedades de difusión, resistencia aparentemente perfecta al criptoanálisis diferencial y resistencia por definición al criptoanálisis lineal , las funciones dobladas pueden parecer al principio la opción ideal para funciones criptográficas seguras, como las cajas S Su defecto fatal es que no pueden ser equilibrados. En particular, una caja S invertible no puede construirse directamente a partir de funciones dobladas, y un cifrado de flujo que utiliza una función de combinación doblada es vulnerable a un ataque de correlación . En cambio, uno podría comenzar con una función doblada y complementar aleatoriamente los valores apropiados hasta que el resultado sea equilibrado. La función modificada todavía tiene una alta no linealidad, y como tales funciones son muy raras, el proceso debería ser mucho más rápido que una búsqueda de fuerza bruta. ^[4]Pero las funciones producidas de esta manera pueden perder otras propiedades deseables, incluso si no satisfacen el SAC, por lo que es necesario realizar pruebas cuidadosas. ^[10] Varios criptógrafos han trabajado en técnicas para generar funciones equilibradas que preserven la mayor cantidad posible de las buenas cualidades criptográficas de las funciones dobladas. ^{[11] [12] [13]}

Parte de esta investigación teórica se ha incorporado a algoritmos criptográficos reales. El procedimiento de diseño CAST , utilizado por Carlisle Adams y Stafford Tavares para construir las cajas S para los cifrados de bloque CAST-128 y CAST-256 , hace uso de funciones dobladas. ^[13] La función hash criptográfica HAVAL utiliza funciones booleanas creadas a partir de representantes de las cuatro clases de equivalencia de funciones dobladas en seis variables. ^[14] El cifrado de flujo Grain usa un NLFSRcuyo polinomio de retroalimentación no lineal es, por diseño, la suma de una función doblada y una función lineal. ^[15]

Las aplicaciones de funciones dobladas se enumeran en una monografía de 2015 de N. Tokareva, Funciones dobladas : resultados y aplicaciones a la criptografía . ^[2]

Generalizaciones [ editar ]

En la monografía de Tokareva 2015 se describen más de 25 generalizaciones diferentes de funciones dobladas. ^[2]Hay generalizaciones algebraicas (funciones dobladas con valor q, funciones dobladas p-arias, funciones dobladas sobre un campo finito, funciones dobladas booleanas generalizadas de Schmidt, funciones dobladas de un grupo abeliano finito en el conjunto de números complejos en el círculo unitario, dobladas funciones de un grupo abeliano finito en un grupo abeliano finito, funciones dobladas no abelianas, funciones dobladas G vectoriales, funciones dobladas multidimensionales en un grupo abeliano finito, generalizaciones combinatorias (funciones dobladas simétricas, funciones dobladas homogéneas, funciones dobladas simétricas de rotación, normales funciones dobladas, funciones dobladas auto dual y anti dual, funciones dobladas parcialmente definidas, funciones plateadas, funciones dobladas en Z y funciones dobladas cuánticas) y generalizaciones criptográficas (funciones semi dobladas, funciones dobladas balanceadas, funciones parcialmente dobladas,funciones hiper-dobladas, funciones dobladas de orden superior, funciones k-dobladas).

La clase más común de funciones dobladas generalizadas es el tipo mod m ,$${\ displaystyle f: \ mathbb {Z} _ {m} ^ {n} \ to \ mathbb {Z} _ {m}} tal que

$${\ displaystyle {\ hat {f}} (a) = \ sum _ {x \ in \ mathbb {Z} _ {m} ^ {n}} e ^ {{\ frac {2 \ pi i} {m} } (f (x) -a \ cdot x)}}

tiene un valor absoluto constante m ^{n / 2} . Funciones no lineales perfectas$${\ displaystyle f: \ mathbb {Z} _ {m} ^ {n} \ to \ mathbb {Z} _ {m}}, aquellos que para todos los valores distintos de cero a , f ( x + a ) - f ( a ) adquieren cada valor m ^{n - 1} veces, se doblan de forma generalizada. Si m es primo , lo contrario es cierto. En la mayoría de los casos solo se consideran los primos m . Para la m prima impar , hay funciones dobladas generalizadas para cada n positiva , par e impar. Tienen muchas de las mismas buenas propiedades criptográficas que las funciones dobladas binarias. ^[16] [17]

Las funciones semi dobladas son una contraparte de orden impar para las funciones dobladas. Una función semi doblada es$${\ displaystyle f: \ mathbb {Z} _ {m} ^ {n} \ to \ mathbb {Z} _ {m}}con n impar, tal que$${\ displaystyle \ left | {\ hat {f}} \ right |}toma solo los valores 0 ym ^{( n +1) / 2} . También tienen buenas características criptográficas, y algunas de ellas son equilibradas y adoptan todos los valores posibles con la misma frecuencia. ^[18]

Las funciones parcialmente dobladas forman una gran clase definida por una condición en las funciones de transformación y autocorrelación de Walsh. Todas las funciones afines y dobladas están parcialmente dobladas. Esto es a su vez una subclase adecuada de las funciones en meseta . ^[19]

La idea detrás de las funciones hiper-doblada es maximizar la distancia mínima para todas las funciones de Boole procedentes de biyectivas monomios en el campo finito GF (2 ⁿ ), no sólo las funciones afines. Para estas funciones, esta distancia es constante, lo que puede hacerlas resistentes a un ataque de interpolación .

Se han dado otros nombres relacionados a clases de funciones criptográficamente importantes. $${\ displaystyle f: \ mathbb {Z} _ {2} ^ {n} \ to \ mathbb {Z} _ {2} ^ {n}}, como funciones casi dobladas y funciones torcidas . Si bien no son funciones dobladas en sí mismas (ni siquiera son funciones booleanas), están estrechamente relacionadas con las funciones dobladas y tienen buenas propiedades de no linealidad.