O que há de especial em

12

No algoritmo de criptografia minúscula :

Diferentes múltiplos de uma constante mágica são usados ​​para evitar ataques simples com base na simetria das rodadas. A constante mágica, 2654435769 ou 9E3779B9 16 é escolhida como , onde ϕ é a razão áurea.232/ϕ

Que propriedades possui que o tornam útil nesse contexto?232/ϕ

MS Dousti
fonte
1
Possivelmente relevante: en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
Charles

Respostas:

11

AFAIK, esses valores "mágicos" têm as duas propriedades a seguir:

  1. Eles são únicos e parecem aleatórios.
  2. Eles podem participar de operações algébricas repetidamente; ou seja, mesmo depois de aplicar alguma operação específica (por exemplo, multiplicação ou exponenciação) muitas vezes, o valor "mágico" ainda é capaz de gerar novos valores.

Você pode encontrar um caso semelhante no MD5 . Considere a seguinte linha:

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

Aqui, sin(i + 1)pretende-se gerar valores mágicos; que são únicos, de aparência aleatória e podem funcionar para muitos i. (Na verdade, ivaria de 0 a 63).

Edit: Ao ler o artigo original no TEA , entende-se que a resposta dada por "Steven Stadnicki" está correta. Observe que a constante mágica é nome delta:

Um múltiplo de delta diferente é usado em cada rodada, para que nenhum bit do múltiplo não mude com frequência. Suspeitamos que o algoritmo não seja muito sensível ao valor do delta e apenas precisamos evitar um valor ruim. Deve-se observar que o delta é ímpar com truncamento ou arredondamento mais próximo, portanto, não são necessárias precauções extras para garantir que todos os dígitos da soma sejam alterados.

Como apenas 32 múltiplos de delta são usados ​​(um por cada rodada), não é estranho que o algoritmo não seja muito sensível a nenhum delta específico. (Veja a resposta de Steven Stadnicki para mais informações.)

Editar 2: Aliás, o MD4 usa raízes quadradas de 2 (0x5a827999) e 3 (0x6ed9eba1) como constantes "mágicas" em suas operações. A seção 5.4.4 do livro Segurança de rede: comunicação privada em um mundo público explica isso bem:

Para mostrar que os designers não escolheram propositalmente um valor diabólico da constante, a constante é baseada na raiz quadrada de 2.

Essa explicação é a mesma do argumento abaixo, em um comentário de Gilles.

MS Dousti
fonte
Parece razoável. 2 ^ 32 / pi ou 2 ^ 32 / sqrt (2) funcionariam tão bem quanto então?
@ Tim: Acho que sim, mas é fundamental verificar novamente os novos números mágicos no contexto das operações internas da TEA.
MS Dousti
5
Além disso, um motivo para escolher uma constante matemática como 2 ^ 32 / phi, em vez de um valor gerado aleatoriamente com propriedades aceitáveis, é dar um pouquinho de confiança de que esse não é um valor escolhido para propriedades não reveladas adicionais - um valor de backdoor .
Gilles 'SO- stop be evil'
2
@Gilles, na verdade, eles são mesmo chamados de "nada o meu número de manga", por essa razão, ver en.wikipedia.org/wiki/Nothing_up_my_sleeve_number
Henno Brandsma
12

φnφφ{nφ}{nα}α

Cπ=232/π=1367130551(355Cπ)mod232=41157Cφ=232/φ=2654435769n|(nCφ)mod232|216n=28657XnXn+kk232

Steven Stadnicki
fonte
1
Sadeq: 'mod 1' refere-se à parte fracionária dos múltiplos - nesse caso, eles seriam [0,62; 0,24; 0,85; 0,47; 0; 09; 0,71; 0,33; 0,94; 18] Equidistribuição no limite significa que qualquer subintervalo [a, b] de [0, 1] contém a proporção esperada (ba) desses valores; embora aconteça que as partes fracionárias dos múltiplos de qualquer número irracional sejam distribuídas igualmente em [0, 1], as da proporção áurea aproximam-se dessa distribuição uniforme mais rapidamente do que qualquer outro número; eles não se agrupam no intervalo da unidade.
Steven Stadnicki
8
π113π{(n+113)π}{nπ}
8
isso é uma propriedade muito elegante da proporção áurea
Suresh Venkat
2
Obrigado pela ótima descrição. Foi realmente bom! Você tem algum comentário k[i], conforme definido no MD5? (Veja minha resposta acima.)
MS Dousti
2
sin(nx)xaiΣaik[i]=0