Comment DES peut-il avoir des S-Box 6x4 tout en étant réversible?

12

Les données ne seraient-elles pas perdues lors du mappage de valeurs 6 bits à des valeurs 4 bits dans les S-Box de DES? Si c'est le cas, comment pouvons-nous l'inverser pour que la sortie correcte apparaisse?

cr.crypto-security
la source
3
C'est probablement une question très intéressante, mais j'essaierais de la rendre plus autonome afin que vous puissiez obtenir une réponse décente. Essayez de fournir plus d'informations contextuelles.
Dave Clarke
2
Bien que Sadeq ait une réponse, il serait toujours utile de clarifier la question. Tout d'abord, qu'est-ce qu'une S-Box dans DES?
Suresh Venkat
5
Un chiffrement basé sur Feistel divise l'entrée en deux chaînes de bits de longueur égale et R (32 bits dans DES), puis applique à plusieurs reprises l'opération décrite par Sadeq ci-dessous (dans DES, elle est répétée 16 fois). Dans le DES, un S - BOX est un 6-bit à fonction 4-bit qui est un composant de l'application de F . Les S -boxes avaient des propriétés statistiques intéressantes, dont le but sont restés obscurs pendant quinze ans. De nombreuses personnes soupçonnaient d'avoir facilité la destruction du DES. Finalement, il a été découvert que ces propriétés des S-box rendaient le DES résistant à la cryptanalyse différentielle. LRSFS
Peter Shor
3
@Suresh: les chiffres classiques sont divisés en deux types: les chiffres de substitution (comme César) et les chiffres de permutation (comme la transposition en colonnes). Plus tard, il est devenu évident qu'aucun des deux types n'offrait suffisamment de sécurité. Les chiffrements par blocs modernes utilisent les deux transformations. En particulier, ils ont des boîtes P (= boîtes de permutation) et des boîtes S (= boîtes de substitution).
MS Dousti
3
@Suresh: Je suis absolument d'accord avec vous. Bien que les S-Box soient célèbres pour les cryptographes, je pense que le PO devrait poser la question d'une manière qui profite à tout le monde, pas à une petite partie de la communauté.
MS Dousti

Réponses:

25

F

À chaque tour, l'opération suivante est appliquée:

i=0,1,…,n

Li+1=Ri

Ri+1=Li⊕F(Ri,Ki)

Le déchiffrement est effectué comme suit:

Ri=Li+1

Li=Ri+1⊕F(Li+1,Ki)

FF−1

MS Dousti
la source
4

Voir le chapitre 5 du manuel "Introduction to Modern Cryptography" de Katz et Lindell.

user686
la source
1

Sans entrer dans tous les mumbo-jumbo mathématiques sur Feistel (que je ne comprends pas encore à 100%), si vous regardez cette image de Wikipedia:

Étape de cryptage DES

Vous pouvez voir que bien que les 8 s-box compressent en effet 48 bits jusqu'à 32, seuls 32 bits d'entropie proviennent du texte en clair , donc vous pouvez obtenir les 16 autres bits de la clé lors du décryptage, ce qui est la magie effectuée par fonctions Feistel mentionnées précédemment.

Sophistifunk
la source