Jak DES może mieć S-Box 6x4 i nadal być odwracalny?

Czy dane nie zostaną utracone podczas mapowania wartości 6-bitowych na wartości 4-bitowe w S-Boxach DES? Jeśli tak, to w jaki sposób możemy to odwrócić, aby pojawił się prawidłowy wynik?

cr.crypto-security
źródło

To prawdopodobnie bardzo interesujące pytanie, ale postaram się uczynić je bardziej samowystarczalnym, abyś mógł uzyskać przyzwoitą odpowiedź. Spróbuj podać więcej podstawowych informacji.

Dave Clarke

Chociaż Sadeq ma odpowiedź, nadal przydatne byłoby wyjaśnienie pytania. Po pierwsze, czym jest S-Box w DES?

Suresh Venkat

Szyfr oparty na Feistelu dzieli dane wejściowe na dwa ciągi bitów

jednakowej długości (32 bity w DES), a następnie wielokrotnie stosuje operację opisaną poniżej przez Sadeq (w DES, jest iterowana 16 razy). Des An

-box jest 6-bitowym do 4 bitów funkcji, która jest elementem realizacji

. Do

-boxes miał kilka ciekawych właściwości statystyczne, których celem pozostawały niejasne przez piętnaście lat. Wiele osób podejrzewało, że łatwiej było złamać DES. W końcu odkryto, że te właściwości S-boxów sprawiają, że DES jest odporny na różnicową kryptoanalizę.

L

$L$

R

$R$

S

$S$

F

$F$

S

$S$

Peter Shor,

@Suresh: Szyfry klasyczne dzielą się na dwa typy: szyfry podstawienia (jak Cezar) i szyfry permutacyjne (jak transpozycja kolumnowa). Później stało się oczywiste, że żaden typ nie zapewnia wystarczającego bezpieczeństwa. Nowoczesne szyfry blokowe wykorzystują obie transformacje. W szczególności mają skrzynki typu P (= skrzynki permutacji) i skrzynki typu S (= skrzynki podstawiania).

MS Dousti

@Suresh: Absolutnie się z tobą zgadzam. Chociaż S-Boxy są znane z kryptografii, uważam, że OP powinien zadać pytanie w taki sposób, aby przyniosło to korzyści wszystkim, a nie niewielkiej części społeczności.

MS Dousti

Odpowiedzi:

$\rm F$

W każdej rundzie stosowana jest następująca operacja:

$i =0,1,\dots,n$

$L_{i+1} = R_i$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$

Deszyfrowanie odbywa się w następujący sposób:

$R_{i} = L_{i+1}$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$

Jak widać, deszyfracja nie potrzebuje być odwracalna. (Ponieważ deszyfrowanie nie wymaga obliczenia .) $\rm F$ $\rm F^{-1}$

MS Dousti
źródło

Zobacz rozdział 5 podręcznika „Wprowadzenie do współczesnej kryptografii” autorstwa Katza i Lindella.

użytkownik686
źródło

Bez wchodzenia w matematyczne mumbo-jumbo dotyczące Feistela (którego jeszcze nie rozumiem w 100%), jeśli spojrzysz na ten obraz z Wikipedii:

Krok szyfrowania DES

Widać, że chociaż 8 s-boxów faktycznie kompresuje 48 bitów do 32, tylko 32 bity entropii pochodzą z tekstu jawnego , dlatego podczas dekodowania można uzyskać pozostałe 16 bitów z klucza, co jest magią wykonywaną przez wcześniej wspomniane funkcje Feistela.

Sophistifunk
źródło