Skip to main content
Fix
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition, as most authors do.

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition, as most authors do.

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition.

Add missing indices
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

As to decryption, DES uses the same round equations for encryption and decryption except for the numbering of subkeys, that is for $1\le n<m$: $$\begin{align} L_n&\gets R_{n-1}&&&L_m&\gets L\oplus f(R_{m-1},K_1)\\ R_n&\gets L\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1} \end{align}$$$$\begin{align} L_n&\gets R_{n-1}&&&L_m&\gets L_{m-1}\oplus f(R_{m-1},K_1)\\ R_n&\gets L_{n-1}\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1} \end{align}$$ with the decryption's $L_0\mathbin\|R_0$ defined as the encryption's $L_n\mathbin\|R_n$, from which it follows that for $1\le n<m$, the decryption's $L_n\mathbin\|R_n$ is the encryption's $R_{m-n}\mathbin\|L_{m-n}$ (notice the inversion), and the decryption's $L_m\mathbin\|R_m$ is the encryption's $L_0\mathbin\|R_0$.

As to decryption, DES uses the same round equations for encryption and decryption except for the numbering of subkeys, that is for $1\le n<m$: $$\begin{align} L_n&\gets R_{n-1}&&&L_m&\gets L\oplus f(R_{m-1},K_1)\\ R_n&\gets L\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1} \end{align}$$ with the decryption's $L_0\mathbin\|R_0$ defined as the encryption's $L_n\mathbin\|R_n$, from which it follows that for $1\le n<m$, the decryption's $L_n\mathbin\|R_n$ is the encryption's $R_{m-n}\mathbin\|L_{m-n}$ (notice the inversion), and the decryption's $L_m\mathbin\|R_m$ is the encryption's $L_0\mathbin\|R_0$.

As to decryption, DES uses the same round equations for encryption and decryption except for the numbering of subkeys, that is for $1\le n<m$: $$\begin{align} L_n&\gets R_{n-1}&&&L_m&\gets L_{m-1}\oplus f(R_{m-1},K_1)\\ R_n&\gets L_{n-1}\oplus f(R_{n-1},K_{16-n})&&&R_m&\gets R_{m-1} \end{align}$$ with the decryption's $L_0\mathbin\|R_0$ defined as the encryption's $L_n\mathbin\|R_n$, from which it follows that for $1\le n<m$, the decryption's $L_n\mathbin\|R_n$ is the encryption's $R_{m-n}\mathbin\|L_{m-n}$ (notice the inversion), and the decryption's $L_m\mathbin\|R_m$ is the encryption's $L_0\mathbin\|R_0$.

Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

DES encryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_1\,,\,S\,,\,g_2\,,\,S\,,\,\ldots\,,\,S\,,\,g_{15}\,,\,S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$$$\mathsf{IP}\,,\,g_1\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$ where $S$$\mathsf S$ is the "swap" involution defined by $S(L\mathbin\|R)=R\mathbin\|L$$\mathsf S(L\mathbin\|R)=R\mathbin\|L$, function $\mathsf{IP}$ is some permutation of bits, and $\mathsf{IP}^{-1}$ is the inverse permutation.

DES decryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_{16}\,,\,S\,,\,g_{15}\,,\,S\,,\,\ldots\,,\,S\,,\,g_2\,,\,S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$$$\mathsf{IP}\,,\,g_{16}\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$

  • For $j=33$, because $\mathsf{IP}$ cancels $\mathsf{IP}^{-1}$.
  • For $j=1$, because $\mathsf{IP}^{-1}$ cancels $\mathsf{IP}$.
  • For other even $j$, because $g_{j/2}$ is an involution.
  • For other (odd) $j$, because $S$$\mathsf S$ is an involution.

The usual definition of a round of a Feistel cipher includes the swap $S$$\mathsf S$: $$\begin{align} g'_n(L\mathbin\|R)&=S\bigl(g_n(L\mathbin\|R)\bigr)\\ &=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr) \end{align}$$$$\begin{align} g'_n(L\mathbin\|R)&=\mathsf S\bigl(g_n(L\mathbin\|R)\bigr)\\ &=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr) \end{align}$$ and this function is not its own inverse per the sense in the question.

With that notation, DES encryption and decryption are the 18 operations $$\mathsf{IP}\,,\,g'_1\,,\,g'_2\,,\,\ldots\,,\,g'_{15}\,,\,g_{16}\,,\,\mathsf{IP}^{-1}\\ \mathsf{IP}\,,\,g'_{16}\,,\,g'_{15}\,,\,\ldots\,,\,g'_2\,,\,g_1\,,\,\mathsf{IP}^{-1}$$ In that presentation, it is less apparent that decryption undoes encryption. But that still holds, and becomes obvious again if we expand the $g'_n$ into $g_n$ followed by $S$$\mathsf S$.

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes onin the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we do notexclude include the swap as part of its definition, as most authors do.

DES encryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_1\,,\,S\,,\,g_2\,,\,S\,,\,\ldots\,,\,S\,,\,g_{15}\,,\,S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$ where $S$ is the "swap" involution defined by $S(L\mathbin\|R)=R\mathbin\|L$, function $\mathsf{IP}$ is some permutation of bits, and $\mathsf{IP}^{-1}$ is the inverse permutation.

DES decryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_{16}\,,\,S\,,\,g_{15}\,,\,S\,,\,\ldots\,,\,S\,,\,g_2\,,\,S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$

  • For $j=33$, because $\mathsf{IP}$ cancels $\mathsf{IP}^{-1}$.
  • For $j=1$, because $\mathsf{IP}^{-1}$ cancels $\mathsf{IP}$.
  • For other even $j$, because $g_{j/2}$ is an involution.
  • For other (odd) $j$, because $S$ is an involution.

The usual definition of a round of a Feistel cipher includes the swap $S$: $$\begin{align} g'_n(L\mathbin\|R)&=S\bigl(g_n(L\mathbin\|R)\bigr)\\ &=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr) \end{align}$$ and this function is not its own inverse per the sense in the question.

With that notation, DES encryption and decryption are the 18 operations $$\mathsf{IP}\,,\,g'_1\,,\,g'_2\,,\,\ldots\,,\,g'_{15}\,,\,g_{16}\,,\,\mathsf{IP}^{-1}\\ \mathsf{IP}\,,\,g'_{16}\,,\,g'_{15}\,,\,\ldots\,,\,g'_2\,,\,g_1\,,\,\mathsf{IP}^{-1}$$ In that presentation, it is less apparent that decryption undoes encryption. But that still holds, and becomes obvious again if we expand the $g'_n$ into $g_n$ followed by $S$.

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes on the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we do not include the swap as part of its definition, as most authors do.

DES encryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_1\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,g_{16}\,,\,\mathsf{IP}^{-1}$$ where $\mathsf S$ is the "swap" involution defined by $\mathsf S(L\mathbin\|R)=R\mathbin\|L$, function $\mathsf{IP}$ is some permutation of bits, and $\mathsf{IP}^{-1}$ is the inverse permutation.

DES decryption chains these 33 operations on 64-bit quantities: $$\mathsf{IP}\,,\,g_{16}\,,\,\mathsf S\,,\,g_{15}\,,\,\mathsf S\,,\,\ldots\,,\,\mathsf S\,,\,g_2\,,\,\mathsf S\,,\,g_1\,,\,\mathsf{IP}^{-1}$$

  • For $j=33$, because $\mathsf{IP}$ cancels $\mathsf{IP}^{-1}$.
  • For $j=1$, because $\mathsf{IP}^{-1}$ cancels $\mathsf{IP}$.
  • For other even $j$, because $g_{j/2}$ is an involution.
  • For other (odd) $j$, because $\mathsf S$ is an involution.

The usual definition of a round of a Feistel cipher includes the swap $\mathsf S$: $$\begin{align} g'_n(L\mathbin\|R)&=\mathsf S\bigl(g_n(L\mathbin\|R)\bigr)\\ &=R\mathbin\|\bigl(L\oplus f(R,K_n)\bigr) \end{align}$$ and this function is not its own inverse per the sense in the question.

With that notation, DES encryption and decryption are the 18 operations $$\mathsf{IP}\,,\,g'_1\,,\,g'_2\,,\,\ldots\,,\,g'_{15}\,,\,g_{16}\,,\,\mathsf{IP}^{-1}\\ \mathsf{IP}\,,\,g'_{16}\,,\,g'_{15}\,,\,\ldots\,,\,g'_2\,,\,g_1\,,\,\mathsf{IP}^{-1}$$ In that presentation, it is less apparent that decryption undoes encryption. But that still holds, and becomes obvious again if we expand the $g'_n$ into $g_n$ followed by $\mathsf S$.

Footnote per comment: There is always some form of swap between rounds of a Feistel cipher, so that the fraction of the state that did not change in a round changes in the next round. That's essential for security (not for decryption to work). A round is its own inverse only if we exclude the swap as part of its definition, as most authors do.

Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Footnote
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Simplify
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Fix
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Fix
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Simplify
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611
Loading