RC5 - RC5
 Un tour (deux demi-tours) du chiffrement par bloc RC5
| |
| Général | |
|---|---|
| Concepteurs | Ron Rivest |
| Première publication | 1994 |
| Successeurs | RC6 , Akélarre |
| Détail du chiffre | |
| Tailles de clé | 0 à 2040 bits (128 suggéré) |
| Tailles de bloc | 32, 64 ou 128 bits (64 suggérés) |
| Structure | Réseau de type Feistel |
| Les manches | 1-255 (12 suggéré à l'origine) |
| Meilleure cryptanalyse publique | |
| Le RC5 à 12 rondes (avec des blocs de 64 bits) est susceptible d'une attaque différentielle en utilisant 2 44 textes en clair choisis. | |
En cryptographie , RC5 est un chiffrement par bloc à clé symétrique remarquable pour sa simplicité. Conçu par Ronald Rivest en 1994, RC signifie "Rivest Cipher", ou encore "Ron's Code" (comparez RC2 et RC4 ). Le candidat RC6 à la norme de cryptage avancé (AES) était basé sur RC5.
La description
Contrairement à de nombreux schémas, RC5 a une taille de bloc variable (32, 64 ou 128 bits ), une taille de clé (0 à 2040 bits) et un nombre de tours (0 à 255). Le choix de paramètres suggéré à l'origine était une taille de bloc de 64 bits, une clé de 128 bits et 12 tours.
Une caractéristique clé de RC5 est l'utilisation de rotations dépendantes des données ; l'un des objectifs de RC5 était de susciter l'étude et l'évaluation de telles opérations en tant que primitive cryptographique . RC5 se compose également d'un certain nombre d' ajouts modulaires et de OU exclusifs (XOR) . La structure générale de l'algorithme est un réseau de type Feistel . Les routines de chiffrement et de déchiffrement peuvent être spécifiées en quelques lignes de code. Le calendrier des clés, cependant, est plus complexe, élargissant la clé en utilisant une fonction essentiellement à sens unique avec les expansions binaires à la fois de e et du nombre d' or comme sources de « rien dans ma manche ». La simplicité alléchante de l'algorithme ainsi que la nouveauté des rotations dépendantes des données ont fait de RC5 un objet d'étude attrayant pour les cryptanalystes. Le RC5 est fondamentalement noté RC5-w/r/b où w=taille du mot en bits, r=nombre de tours, b=nombre d'octets de 8 bits dans la clé.
Algorithme
Le chiffrement et le déchiffrement RC5 étendent tous deux la clé aléatoire en 2(r+1) mots qui seront utilisés séquentiellement (et une seule fois chacun) pendant les processus de chiffrement et de déchiffrement. Tout ce qui suit provient de l'article révisé de Rivest sur RC5.
Extension de clé
L'algorithme d'expansion de clé est illustré ci-dessous, d'abord en pseudocode, puis en exemple de code C copié directement à partir de l'annexe de l'article de référence.
Suivant le schéma de nommage de l'article, les noms de variables suivants sont utilisés :
- w - La longueur d'un mot en bits, généralement 16, 32 ou 64. Le chiffrement se fait par blocs de 2 mots.
- u = w/8 - La longueur d'un mot en octets.
- b - La longueur de la clé en octets.
- K[] - La clé, considérée comme un tableau d'octets (utilisant une indexation basée sur 0).
- c - La longueur de la clé en mots (ou 1, si b = 0).
- L[] - Un tableau de travail temporaire utilisé lors de la planification des clés. initialisé à la clé en mots.
- r - Le nombre de tours à utiliser lors du cryptage des données.
- t = 2(r+1) - le nombre de sous-clés rondes requises.
- S[] - Les sous-mots clés ronds.
- P w - La première constante magique, définie comme , où Odd est l'entier impair le plus proche de l'entrée donnée, e est la base du logarithme népérien et w est défini ci-dessus. Pour les valeurs communes de w , les valeurs associées de P w sont données ici en hexadécimal :
- Pour w = 16 : 0xB7E1
- Pour w = 32 : 0xB7E15163
- Pour w = 64 : 0xB7E151628AED2A6B
- Q w - La deuxième constante magique, définie comme , où Odd est l'entier impair le plus proche de l'entrée donnée, où est le nombre d' or , et w est défini ci-dessus. Pour les valeurs communes de w , les valeurs associées de Q w sont données ici en hexadécimal :
- Pour w = 16 : 0x9E37
- Pour w = 32 : 0x9E3779B9
- Pour w = 64 : 0x9E3779B97F4A7C15
# Break K into words
# u = w / 8
c = ceiling(max(b, 1) / u)
# L is initially a c-length list of 0-valued w-length words
for i = b-1 down to 0 do:
L[i / u] = (L[i / u] <<< 8) + K[i]
# Initialize key-independent pseudorandom S array
# S is initially a t=2(r+1) length list of undefined w-length words
S[0] = P_w
for i = 1 to t-1 do:
S[i] = S[i - 1] + Q_w
# The main key scheduling loop
i = j = 0
A = B = 0
do 3 * max(t, c) times:
A = S[i] = (S[i] + A + B) <<< 3
B = L[j] = (L[j] + A + B) <<< (A + B)
i = (i + 1) % t
j = (j + 1) % c
# return S
L'exemple de code source est fourni à partir de l'annexe de l'article de Rivest sur RC5. L'implémentation est conçue pour fonctionner avec w = 32, r = 12 et b = 16.
void RC5_SETUP(unsigned char *K)
{
// w = 32, r = 12, b = 16
// c = max(1, ceil(8 * b/w))
// t = 2 * (r+1)
WORD i, j, k, u = w/8, A, B, L[c];
for (i = b-1, L[c-1] = 0; i != -1; i--)
L[i/u] = (L[i/u] << 8) + K[i];
for (S[0] = P, i = 1; i < t; i++)
S[i] = S[i-1] + Q;
for (A = B = i = j = k = 0; k < 3 * t; k++, i = (i+1) % t, j = (j+1) % c)
{
A = S[i] = ROTL(S[i] + (A + B), 3);
B = L[j] = ROTL(L[j] + (A + B), (A + B));
}
}
Chiffrement
Le cryptage impliquait plusieurs tours d'une fonction simple. 12 ou 20 tours semblent être recommandés, en fonction des besoins de sécurité et des considérations de temps. Au-delà des variables utilisées ci-dessus, les variables suivantes sont utilisées dans cet algorithme :
- A, B - Les deux mots composant le bloc de texte clair à chiffrer.
A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A ^ B) <<< B) + S[2 * i]
B = ((B ^ A) <<< A) + S[2 * i + 1]
# The ciphertext block consists of the two-word wide block composed of A and B, in that order.
return A, B
L'exemple de code C donné par Rivest est le suivant.
void RC5_ENCRYPT(WORD *pt, WORD *ct)
{
WORD i, A = pt[0] + S[0], B = pt[1] + S[1];
for (i = 1; i <= r; i++)
{
A = ROTL(A ^ B, B) + S[2*i];
B = ROTL(B ^ A, A) + S[2*i + 1];
}
ct[0] = A; ct[1] = B;
}
Décryptage
Le déchiffrement est une inversion assez simple du processus de chiffrement. Le pseudo-code ci-dessous montre le processus.
for i = r down to 1 do:
B = ((B - S[2 * i + 1]) >>> A) ^ A
A = ((A - S[2 * i]) >>> B) ^ B
B = B - S[1]
A = A - S[0]
return A, B
L'exemple de code C donné par Rivest est le suivant.
void RC5_DECRYPT(WORD *ct, WORD *pt)
{
WORD i, B=ct[1], A=ct[0];
for (i = r; i > 0; i--)
{
B = ROTR(B - S[2*i + 1], A) ^ A;
A = ROTR(A - S[2*i], B) ^ B;
}
pt[1] = B - S[1]; pt[0] = A - S[0];
}
Cryptanalyse
Le RC5 à 12 rondes (avec blocs de 64 bits) est susceptible d'une attaque différentielle en utilisant 2 44 textes en clair choisis. 18 à 20 cartouches sont suggérées comme protection suffisante.
Un certain nombre de ces défis ont été résolus à l'aide de l' informatique distribuée , organisée par Distributed.net . Distributed.net contient des messages RC5 de force brute cryptés avec des clés 56 bits et 64 bits et travaille sur le craquage d'une clé 72 bits depuis le 3 novembre 2002. Au 6 août 2021, 7,900 % de l'espace de clés avait été recherché et sur la base du taux enregistré ce jour-là, il faudrait 127 ans pour compléter 100% de l'espace de clé. La tâche a inspiré de nombreux développements nouveaux et novateurs dans le domaine de l'informatique en grappe.
RSA Security , qui détenait un brevet sur l'algorithme, a offert une série de prix de 10 000 $ US pour la rupture de textes chiffrés cryptés avec RC5, mais ces concours ont été interrompus en mai 2007. En conséquence, Distributed.net a décidé de financer le prix monétaire. L'individu qui découvre la clé gagnante recevra 1 000 USD, son équipe (le cas échéant) recevra 1 000 USD et la Free Software Foundation recevra 2 000 USD.