Introduction à l'Algorithme ZUC
L'algorithme ZUC est un chiffreur de flux conçu pour les communications mobiles sécurisées. Il a été adopté comme algorithme de chiffrement standard pour les réseaux LTE (4G) et 5G. Nommé en l'honneur du mathématicien chinois Zu Chongzhi, ZUC offre une combinaison d'efficacité, de simplicité et de sécurité élevée.
Ce tutoriel a pour objectif de vous guider à travers les concepts clés de l'algorithme ZUC, en fournissant des explications détaillées, des exemples concrets et des visualisations interactives pour faciliter votre compréhension.
Historique et Contexte
Développé par l'Université de Tsinghua et le Centre de Recherche sur les Codes de Chine, ZUC a été conçu pour répondre aux besoins croissants en matière de sécurité des communications mobiles. Son adoption par les normes 3GPP témoigne de sa robustesse et de sa fiabilité.
Comprendre ZUC est essentiel pour les ingénieurs en télécommunications et les professionnels de la sécurité, car il illustre l'application pratique des concepts cryptographiques avancés dans les systèmes modernes.
Structure Générale de l'Algorithme ZUC
Figure 1 : Diagramme de la structure générale de l'algorithme ZUC.
1. Registre à Décalage à Rétroaction Linéaire (LFSR)
Le LFSR de ZUC est un registre composé de 16 cellules, chacune contenant 31 bits. Les états du LFSR sont mis à jour à chaque itération en utilisant une fonction de rétroaction linéaire, assurant ainsi la génération d'une séquence pseudo-aléatoire.
Schéma Interactif du LFSR
Figure 2 : Schéma interactif du Registre à Décalage à Rétroaction Linéaire (LFSR).
L'équation de mise à jour du LFSR est la suivante :
$$ s^{(t+16)} = \left( \sum_{i=0}^{15} c_i \times s^{(t+i)} \right) \mod (2^{31} - 1) $$
Où :
- \( s^{(t+i)} \) représente l'état du registre à l'instant \( t+i \).
- \( c_i \) sont des coefficients constants définis par l'algorithme.
Exemple Concret
Supposons que nous ayons les états initiaux suivants pour les registres \( s^{(t)} \) à \( s^{(t+15)} \) (valeurs aléatoires pour l'exemple) :
| i | \( s^{(t+i)} \) (hexadécimal) |
|---|---|
| 0 | 0x1A2B3C4D |
| 1 | 0x2B3C4D5E |
| 2 | 0x3C4D5E6F |
| 3 | 0x4D5E6F70 |
| 4 | 0x5E6F7081 |
| 5 | 0x6F708192 |
| 6 | 0x708192A3 |
| 7 | 0x8192A3B4 |
| 8 | 0x92A3B4C5 |
| 9 | 0xA3B4C5D6 |
| 10 | 0xB4C5D6E7 |
| 11 | 0xC5D6E7F8 |
| 12 | 0xD6E7F809 |
| 13 | 0xE7F8091A |
| 14 | 0xF8091A2B |
| 15 | 0x091A2B3C |
Les coefficients \( c_i \) sont définis par l'algorithme (par exemple, \( c_0 = 1 \), \( c_{15} = 1 \), les autres étant zéro). En appliquant l'équation, nous calculons \( s^{(t+16)} \) en effectuant la somme pondérée des \( s^{(t+i)} \) par les \( c_i \), puis en prenant le modulo \( 2^{31} - 1 \).
Les étapes de calcul sont les suivantes :
- Calcul de chaque produit \( c_i \times s^{(t+i)} \). Dans notre exemple simplifié, seuls \( c_0 \) et \( c_{15} \) sont non nuls :
- \( c_0 \times s^{(t+0)} = 1 \times 0x1A2B3C4D \)
- \( c_{15} \times s^{(t+15)} = 1 \times 0x091A2B3C \)
- Somme des produits : $$ \text{Somme} = 0x1A2B3C4D + 0x091A2B3C $$ $$ \text{Somme} = 0x23655D89 $$
- Application du modulo \( 2^{31} - 1 \) :
$$ s^{(t+16)} = 0x23655D89 \mod (2^{31} - 1) $$
Comme \( 0x23655D89 \) est inférieur à \( 2^{31} - 1 \), la valeur reste inchangée :
$$ s^{(t+16)} = 0x23655D89 $$
Ainsi, la nouvelle valeur du registre \( s^{(t+16)} \) est \( 0x23655D89 \).
2. Réorganisation des Bits
Cette étape consiste à extraire et à combiner des bits spécifiques des registres du LFSR pour former quatre mots de 32 bits (\( X_0 \) à \( X_3 \)) utilisés par la fonction non linéaire F.
Schéma de la Réorganisation des Bits
Figure 3 : Illustration détaillée de la réorganisation des bits pour former \( X_0 \) à \( X_3 \).
Les mots sont formés comme suit :
- \( X_0 = \left( s^{15}_{15..0} \parallel s^{14}_{15..0} \right) \)
- \( X_1 = \left( s^{11}_{15..0} \parallel s^{9}_{30..16} \right) \)
- \( X_2 = \left( s^{7}_{15..0} \parallel s^{5}_{30..16} \right) \)
- \( X_3 = \left( s^{2}_{15..0} \parallel s^{0}_{30..16} \right) \)
Exemple Concret
Avec les valeurs des registres précédents :
- \( s^{15} = 0x091A2B3C \)
- \( s^{14} = 0xF8091A2B \)
- \( s^{11} = 0xC5D6E7F8 \)
- \( s^{9} = 0xA3B4C5D6 \)
- \( s^{7} = 0x8192A3B4 \)
- \( s^{5} = 0x6F708192 \)
- \( s^{2} = 0x3C4D5E6F \)
- \( s^{0} = 0x1A2B3C4D \)
Calcul de \( X_0 \) :
- Extraction des 16 bits de poids faible de \( s^{15} \) : $$ s^{15}_{15..0} = 0x2B3C $$
- Extraction des 16 bits de poids faible de \( s^{14} \) : $$ s^{14}_{15..0} = 0x1A2B $$
- Concaténation pour former \( X_0 \) : $$ X_0 = 0x2B3C1A2B $$
Le même processus est appliqué pour \( X_1 \), \( X_2 \) et \( X_3 \), en effectuant les extractions de bits correspondantes et les concaténations.
3. Fonction Non Linéaire F
La fonction F introduit de la non-linéarité dans l'algorithme, renforçant ainsi la sécurité. Elle utilise des S-boxes (boîtes de substitution) et des transformations linéaires pour transformer les entrées \( X_0 \) à \( X_2 \) en une sortie \( W \).
Schéma Détaillé de la Fonction F
Figure 4 : Schéma détaillé de la fonction non linéaire F.
Les étapes de la fonction F sont :
- Calcul de \( W = (X_0 \oplus R_1) + R_2 \), où \( R_1 \) et \( R_2 \) sont des registres internes.
- Calcul de \( W_1 = R_1 + X_1 \) et \( W_2 = R_2 \oplus X_2 \).
- Application des transformations linéaires \( L_1 \) et \( L_2 \) sur \( W_1 \) et \( W_2 \) respectivement :
- \( u = L_1(W_1) \)
- \( v = L_2(W_2) \)
- Utilisation des S-boxes pour substituer les résultats et mettre à jour \( R_1 \) et \( R_2 \).
Exemple Concret
Supposons que :
- \( R_1 = \text{0x11111111} \)
- \( R_2 = \text{0x22222222} \)
- \( X_0 = \text{0x2B3C1A2B} \)
- \( X_1 = \text{0x3D4E2B3C} \)
- \( X_2 = \text{0x4E5F3C4D} \)
1. **Calcul de \( W \)** : $$ W = (\text{0x2B3C1A2B} \oplus \text{0x11111111}) + \text{0x22222222} $$ $$ W = \text{0x3A2D0B3A} + \text{0x22222222} = \text{0x5C4F2D5C} $$
2. **Calcul de \( W_1 \) et \( W_2 \)** :
- \( W_1 = \text{0x11111111} + \text{0x3D4E2B3C} = \text{0x4E5F3C4D} \)
- \( W_2 = \text{0x22222222} \oplus \text{0x4E5F3C4D} = \text{0x6C7D1E6F} \)
3. **Application des transformations linéaires** :
- Transformation \( L_1 \) sur \( W_1 \) :
$$ u = L_1(\text{0x4E5F3C4D}) $$
Le calcul de \( L_1 \) implique des rotations et des XOR :
$$ u = W_1 \oplus \text{ROT}(W_1, 2) \oplus \text{ROT}(W_1, 10) \oplus \text{ROT}(W_1, 18) \oplus \text{ROT}(W_1, 24) $$(Les détails des calculs de rotation sont omis ici pour la brièveté.)
- Transformation \( L_2 \) sur \( W_2 \) :
$$ v = L_2(\text{0x6C7D1E6F}) $$
De même, \( L_2 \) implique des rotations et des XOR.
4. **Utilisation des S-boxes** :
- Découpage de \( u \) en octets et substitution via les S-boxes \( S_0 \) et \( S_1 \).
- Mise à jour de \( R_1 \) et \( R_2 \) avec les valeurs substituées.
Ces étapes montrent comment la fonction F introduit de la complexité et de la non-linéarité dans l'algorithme, rendant le chiffrement plus sécurisé.
4. Initialisation de l'Algorithme
L'initialisation est une étape cruciale où la clé secrète et le vecteur d'initialisation (IV) sont utilisés pour configurer l'état interne du LFSR. Cela garantit que le keystream généré est unique pour chaque paire clé-IV.
Diagramme du Processus d'Initialisation
Figure 5 : Processus détaillé d'initialisation de l'algorithme ZUC.
Les étapes d'initialisation sont :
- **Chargement initial** : La clé \( K \) et l'IV sont combinés avec des constantes \( D \) pour initialiser les registres du LFSR : $$ s_i = (k_i \ll 23) \oplus (D_i \ll 8) \oplus iv_i $$
- **Initialisation des registres internes** : Les registres \( R_1 \) et \( R_2 \) sont initialisés à zéro.
- **Itérations d'initialisation** : Exécution de 32 itérations de l'algorithme en mode initialisation, où la sortie \( W \) est utilisée pour rétroagir dans le LFSR.
5. Génération du Keystream
Après l'initialisation, l'algorithme passe en mode de travail pour générer le keystream utilisé pour le chiffrement ou le déchiffrement des données. Chaque mot du keystream est généré en combinant les sorties de la fonction F et les registres du LFSR.
Diagramme de la Génération du Keystream
Figure 6 : Processus détaillé de génération du keystream dans l'algorithme ZUC.
Les étapes pour chaque mot du keystream sont :
- **Réorganisation des bits** pour obtenir \( X_0 \) à \( X_3 \).
- **Calcul de la sortie de la fonction F** pour obtenir \( W \).
- **Calcul du mot de keystream** : $$ Z = W \oplus X_3 $$
- **Mise à jour du LFSR** en mode de travail (sans rétroaction du mot \( W \)).
Ce processus est répété pour générer autant de mots de keystream que nécessaire pour le chiffrement des données.
Implémentation Interactive
Vous pouvez entrer une clé et un vecteur d'initialisation (IV) pour voir comment l'algorithme génère le keystream et visualiser l'état interne du LFSR.
Paramètres de l'Algorithme
Résultats
Visualisation du LFSR
Le graphique ci-dessus montre l'évolution des registres du LFSR que vous avez sélectionnés au cours des itérations. Cela vous permet de visualiser comment l'état interne change au fil du temps de manière plus claire.
Visualisation de la Fonction Non Linéaire F
Ce graphique illustre les valeurs des registres internes \( R_1 \) et \( R_2 \) de la fonction F au fil des itérations, offrant un aperçu de la complexité introduite par la non-linéarité.
Conclusion
L'algorithme ZUC est un exemple puissant de l'application des principes cryptographiques pour sécuriser les communications modernes. En comprenant ses composants internes et leur interaction, vous êtes mieux équipé pour appréhender les défis de la cryptographie en temps réel.
N'hésitez pas à expérimenter avec l'implémentation interactive et à approfondir votre exploration de l'algorithme.
Glossaire des Termes Clés
- LFSR : Linear Feedback Shift Register (Registre à Décalage à Rétroaction Linéaire).
- S-box : Boîte de Substitution utilisée pour introduire de la non-linéarité.
- Keystream : Séquence de bits pseudo-aléatoires utilisée pour le chiffrement.
- IV : Initialization Vector (Vecteur d'Initialisation).
- ROT : Opération de rotation des bits.