Co jest specjalnego

W małym algorytmie szyfrowania :

Różne wielokrotności stałej magicznej służą do zapobiegania prostym atakom opartym na symetrii rund. Stała magiczna, 2654435769 lub 9E3779B9 _16, jest wybrana jako , gdzie ϕ jest złotym współczynnikiem.$2^{32}/ \phi$

Jakie właściwości ma , dzięki czemu jest przydatny w tym kontekście?$2^{32}/ \phi$

AFAIK, takie „magiczne” wartości mają następujące dwie właściwości:

1. Są w jakiś sposób wyjątkowe i wyglądają losowo.
2. Mogą wielokrotnie brać udział w operacjach algebraicznych; tzn. nawet po wielokrotnym zastosowaniu określonej operacji (powiedzmy mnożenie lub potęgowanie), wartość „magii” wciąż jest w stanie wygenerować nowe wartości.

Podobny przypadek możesz znaleźć w MD5 . Rozważ następującą linię:

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

Tutaj sin(i + 1)ma generować magiczne wartości; które są wyjątkowe, wyglądają losowo i mogą działać na wiele isposobów. (Właściwie iwynosi 0..63).

Edycja: Czytając oryginalny artykuł na temat TEA , rozumie się, że odpowiedź udzielona przez „Stevena Stadnickiego” jest poprawna. Zauważ, że stała magiczna to nazwa delta:

W każdej rundzie używana jest inna wielokrotność delta, więc żaden fragment wielokrotności nie zmienia się często. Podejrzewamy, że algorytm nie jest bardzo wrażliwy na wartość delta i musimy jedynie unikać złej wartości. Należy zauważyć, że delta okazuje się nieparzysta z obcięciem lub najbliższym zaokrągleniem, więc nie są potrzebne żadne dodatkowe środki ostrożności, aby zapewnić zmianę wszystkich cyfr sumy.

Ponieważ stosuje się tylko 32 wielokrotności delta (po jednej na każdą rundę), nie jest dziwne, że algorytm nie jest bardzo wrażliwy na jakąkolwiek konkretną deltę. (Aby uzyskać więcej informacji, zobacz odpowiedź Stevena Stadnickiego).

Edycja 2: Nawiasem mówiąc, MD4 używa pierwiastków kwadratowych z 2 (0x5a827999) i 3 (0x6ed9eba1) jako stałych „magicznych” w swoich operacjach. Sekcja 5.4.4 książki Bezpieczeństwo sieci: prywatna komunikacja w publicznym świecie dobrze to wyjaśnia:

Aby pokazać, że projektanci nie wybrali celowo diabolicznej wartości stałej, stała jest oparta na pierwiastku kwadratowym z 2.

To wyjaśnienie jest takie samo, jak punkt przedstawiony poniżej w komentarzu Gillesa.

$\varphi$$n\varphi$$\varphi$$\{n\varphi\}$$\{n\alpha\}$$\alpha$

$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$$2^{32}$