Madryga

Madryga
Madryga
Résumé
Concepteur(s) W. E. Madryga
Première publication 1984
Dérivé de Aucun
Chiffrement(s) basé(s) sur cet algorithme Aucun
Caractéristiques
Taille(s) du bloc 24 bits
Longueur(s) de la clé quelconque
Structure série de rotations
Nombre de tours variable (8 dans les spécifications)
Meilleure cryptanalyse
cryptanalyse différentielle

Madryga est un algorithme de chiffrement par bloc conçu en 1984 par W. E. Madryga. Destiné à une implémentation logicielle efficace et simple à mettre en œuvre, l'algorithme souffre cependant d'importantes faiblesses. Il a toutefois posé les bases algorithmiques et mathématiques concernant les rotations dépendantes des données. Celles-ci seront reprises dans d'autres chiffrements comme RC5 et RC6.

Dans sa proposition, Madryga met en avant 12 objectifs qui doivent être considérés lors de la réalisation d'un bon chiffrement par bloc. DES remplissait 9 d'entre eux. Les 3 critères restants étaient :

  1. toute clé doit produire un chiffrement robuste (ie. pas de clés faibles)
  2. la longueur de la clé et du texte doivent être ajustables selon la sécurité désirée
  3. l'algorithme doit pouvoir être implémenté facilement sur les ordinateurs et la logique discrète (DES utilise des opérations sur les bits comme les permutations qui sont très inefficaces dans une implémentation logicielle).

Sommaire

Fonctionnement

Madryga a rempli ses objectifs d'efficacité dans une implémentation logicielle : les seules opérations utilisées sont des XOR et des rotations. Les deux travaillent sur des octets. Madryga a une clé de taille variable, sans limite supérieure.

La spécification de Madryga prévoit huit tours mais ce nombre peut être incrémenté pour plus de sécurité si nécessaire. Il utilise un bloc de 24 bits et procède à un XOR entre un octet de la clé et l'octet de poids faible du bloc. Les deux autres octets du bloc subissent une rotation. Celle-ci dépend de la sortie du XOR. Ensuite, l'algorithme effectue une rotation vers la droite de un octet. De cette façon si Madryga travaille sur les octets 2,3 et 4, il s'occuperait des octets 3,4 et 5 après avoir effectué les rotations et les XOR.

Le key schedule est très simple. Un XOR entre la clé et une constante aléatoire de la même taille est effectué. Une rotation vers la gauche de 3 bits est appliquée. Après chaque tour, cette rotation sur le résultat clé/constante est appliquée à nouveau. La clé intermédiaire de chaque tour est obtenue grâce à l'octet de poids faible de cette combinaison. Le chiffrement s'effectue ainsi via un XOR entre l'octet de poids faible du bloc et l'octet de poids faible du registre circulaire contenant la clé.

Le déchiffrement consiste simplement en une utilisation inverse des opérations. Ceci est rendu possible grâce aux propriétés d'inversibilité du XOR.

Cryptanalyse

A première vue, Madryga semble plus faible que DES. Toutes les opérations de Madryga sont linéaires. DES utilise au moins des S-Boxes, composants non-linéaires dans le chiffrement qui furent mis à mal par la cryptanalyse linéaire et différentielle. Malgré la présence de rotations qui dépendent en partie des données, Madryga est toujours linéaire.

Le plus gros problème de Madryga est l'absence d'un effet avalanche (une modification en entrée ne va pas influencer tous les bits à la sortie). Ce défaut est provoqué par une taille de bloc insuffisante.

Eli Biham a procédé à une analyse informelle de l'algorithme. Il a remarqué que la « parité de tous les bits du texte clair et du texte chiffré est une constante qui dépend seulement de la clé. De cette façon, étant donné un texte en clair, vous pouvez établir la parité du texte chiffré ». La parité correspond ici à un XOR entre tous les bits d'une séquence.,

En 1995, Ken Shirrif présente une attaque différentielle qui nécessite 5 000 textes clairs choisis. Biryukov et Kushilevitz publient en 1998 une attaque différentielle améliorée qui ne nécessite que 16 textes clairs choisis. Leur démonstration va plus loin et montre que l'attaque peut être convertie entre une attaque par texte chiffré avec 212 textes chiffrés, sous des hypothèses favorables (redondances, par exemple du texte en français). Ce type d'attaque anéantit définitivement Madryga.

Liens externes

Références

  • Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998: 72-88
  • W. E. Madryga, « A High Performance Encryption Algorithm », Computer Security: À Global Challenge, Elsevier Science Publishers, 1984, p. 557-570.
  • Ken Shirriff, Differential Cryptanalysis of Madryga, unpublished manuscript, October 1995. [1]

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Madryga de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • MADRYGA — (в честь автора W. E. Madryga)  блочный алгоритм шифрования, созданный В. Е. Мадрига в 1984 году. Содержание 1 Свойства 2 Описание алгоритма 3 Криптоанализ MADRYGA …   Википедия

  • Madryga — In cryptography, Madryga is a block cipher created in 1984 by W. E. Madryga. It was designed to be easy and efficient for implementation in software. Serious weaknesses have since been found in the algorithm, but it was one of the first… …   Wikipedia

  • Mark Madryga — MK Mark Madryga Born 1963 Kamloops, British Columbia Occupation Meteorologist, Global Television Ne …   Wikipedia

  • Block cipher — In cryptography, a block cipher is a symmetric key cipher operating on fixed length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take (for example) a 128 bit block of plaintext as… …   Wikipedia

  • Cryptanalysis — Close up of the rotors in a Fialka cipher machine Cryptanalysis (from the Greek kryptós, hidden , and analýein, to loosen or to untie ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret… …   Wikipedia

  • Data Encryption Standard — The Feistel function (F function) of DES General Designers IBM First publis …   Wikipedia

  • Differential cryptanalysis — is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at… …   Wikipedia

  • International Data Encryption Algorithm — IDEA An encryption round of IDEA General Designers Xuejia Lai and James Massey …   Wikipedia

  • Triple DES — Triple Data Encryption Algorithm General First published 1998 (ANS X9.52) Derived from DES Cipher detail Key sizes 168, 112 or 56 bits (Keying option 1, 2, 3 respectively) Block sizes …   Wikipedia

  • RC5 — Infobox block cipher name = RC5 caption = One round (two half rounds) of the RC5 block cipher designers = Ron Rivest publish date = 1994 derived from = derived to = RC6, Akelarre key size = 0 to 2040 bits (128 suggested) block size = 32, 64 or… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”