¿Qué tiene de especial en criptografía?

En el algoritmo de cifrado minúsculo :

Se usan diferentes múltiplos de una constante mágica para evitar ataques simples basados en la simetría de las rondas. La constante mágica, 2654435769 o 9E3779B9 ₁₆ se elige para ser , donde ϕ es la proporción áurea. $2^{32}/ \phi$

¿Qué propiedades tiene $2^{32}/ \phi$ que lo hace útil en este contexto?

cr.crypto-security MS Dousti
fuente

Posiblemente relevante: en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

Charles

Respuestas:

AFAIK, tales valores "mágicos" tienen las siguientes dos propiedades:

De alguna manera son únicos y parecen aleatorios.
Pueden participar en operaciones algebraicas repetidamente; es decir, incluso después de aplicar alguna operación específica (por ejemplo, multiplicación o exponenciación) muchas veces, el valor "mágico" aún puede generar nuevos valores.

Puede encontrar un caso similar en el MD5 . Considere la siguiente línea:

k[i] := floor(abs(sin(i + 1)) × (2 pow 32))

Aquí, sin(i + 1)está destinado a generar valores mágicos; que son únicos, de aspecto aleatorio y pueden funcionar para muchos i. (En realidad, ivaría en 0..63).

Editar: Al leer el documento original sobre TEA , uno entiende que la respuesta dada por "Steven Stadnicki" es correcta. Tenga en cuenta que la constante mágica es el nombre delta:

Se utiliza un múltiplo diferente de delta en cada ronda para que ningún bit del múltiplo no cambie con frecuencia. Sospechamos que el algoritmo no es muy sensible al valor de delta y simplemente necesitamos evitar un valor incorrecto. Se notará que el delta resulta ser extraño con el truncamiento o el redondeo más cercano, por lo que no se necesitan precauciones adicionales para garantizar que cambien todos los dígitos de la suma.

Como solo se usan 32 múltiplos de delta (uno por cada ronda), no es extraño que el algoritmo no sea muy sensible a ningún delta específico. (Vea la respuesta de Steven Stadnicki para más información).

Edición 2: Incidentalmente, MD4 usa raíces cuadradas de 2 (0x5a827999) y 3 (0x6ed9eba1) como constantes "mágicas" en sus operaciones. La sección 5.4.4 del libro Seguridad de la red: comunicación privada en un mundo público explica esto bien:

Para mostrar que los diseñadores no eligieron a propósito un valor diabólico de la constante, la constante se basa en la raíz cuadrada de 2.

Esta explicación es la misma que se señala a continuación en un comentario de Gilles.

MS Dousti
fuente

Suena razonable. ¿Entonces 2 ^ 32 / pi o 2 ^ 32 / sqrt (2) habrían funcionado igual de bien?

@Tim: Supongo que sí, pero es fundamental verificar los nuevos números mágicos en el contexto de las operaciones internas de TEA.

MS Dousti

Además, una razón para elegir una constante matemática como 2 ^ 32 / phi, en lugar de un valor generado aleatoriamente con propiedades aceptables, es dar una pizca de confianza de que este no es un valor elegido para propiedades adicionales no reveladas: un valor de puerta trasera .

Gilles 'SO- deja de ser malvado'

@Gilles, de hecho, incluso se les llama "nada en la manga" por esa razón, ver en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

Henno Brandsma

Una razón por la que hace un 'número mágico' particularmente útil en este contexto es que se garantiza que los múltiplos están 'máximamente lejos' de los enteros (esto tiene que ver con la falta de términos grandes en la fracción continua para ) y, por lo tanto, la secuencia (o más exactamente, sus segmentos iniciales) se distribuye de manera más uniforme mod 1 que la secuencia para cualquier otro irracional . $\varphi$ $n\varphi$ $\varphi$ $\{n\varphi\}$ $\{n\alpha\}$ $\alpha$

Para dar un ejemplo: supongamos que elegimos una constante mágica . Entonces , un resultado inesperadamente pequeño para un múltiplo tan pequeño de nuestra constante mágica. Por el contrario, si usamos la constante mágica , entonces la más pequeña para la cual (abusando un poco de la notación) es . En la práctica, esto puede conducir a cosas como correlaciones inesperadamente grandes entre los valores y de un generador lineal de números aleatorios congruentes para algunos pequeños $C_\pi = \lfloor {2^{32}/\pi}\rfloor = 1367130551$ $(355C_\pi)\mod {2^{32}} = 41157$ $C_\varphi = \lfloor {2^{32}/\varphi}\rfloor = 2654435769$ $n$ $|(nC_\varphi)\mod {2^{32}}| \leq 2^{16}$ $n=28657$ $X_n$ $X_{n+k}$ $k$ ; en su mayor parte, sin embargo, es magia negra folclórica, basada más en la intuición de que 'pequeños múltiplos de este número siendo pequeños mod serán malos' que en cualquier resultado teórico específico. $2^{32}$

Steven Stadnicki
fuente

Sadeq: 'mod 1' se refiere a la parte fraccionaria de los múltiplos; en este caso, serían [.62, .24, .85, .47, .09, .71, .33, .94, .56,. 18] La equidistribución en el límite significa que cualquier subintervalo [a, b] de [0, 1] contiene la proporción esperada (ba) de estos valores; Si bien resulta que las partes fraccionarias de los múltiplos de cualquier número irracional se distribuyen uniformemente en [0, 1], las del enfoque de la proporción áurea se distribuyen incluso más rápido que cualquier otro número; no se "agrupan" en el intervalo de la unidad.

Steven Stadnicki

π

$\pi$ La aproximación cercana de en 355/113, por ejemplo, significa que estará mucho más cerca de un número entero de lo que 'debería estar' y esto se muestra como una agrupación de las partes fraccionarias de sus valores; estará excepcionalmente cerca de . Sin embargo, la proporción áurea no tiene tan buenas aproximaciones; todas sus aproximaciones están 'máximamente lejos' de él. ( en.wikipedia.org/wiki/… cubre esto)

113 π

$113\pi$

{(n + 113) π}

$\{(n+113)\pi\}$

{n π}

$\{n\pi\}$

Steven Stadnicki

esa es una propiedad muy clara de la proporción áurea

Suresh Venkat

Gracias por la gran descripción. ¡Fué realmente bueno! ¿Tiene algún comentario sobre k[i], como se define en MD5? (Vea mi respuesta más arriba.)

MS Dousti

Lamentablemente no. - Lo único que viene a la mente es que pueden elegirse para una independencia lineal aproximada, ya que las funciones son linealmente independientes sobre , pero no sé ninguna razón para creer que este conjunto particular de valores debería conducir a valores relativamente grandes para en cualquier relación lineal .

\sin (n x)

$\sin(nx)$

x

$x$

a_{i}

$a_i$

Σ a_{i} k [i] = 0

$\Sigma a_i k[i] = 0$

Steven Stadnicki