Voir la source de Contrôle de redondance cyclique

{{voir homonymes|CRC}}
En [[informatique]] et dans certains appareils [[numérique]]s, un '''contrôle de redondance cyclique''' ou '''CRC''' ({{lang|en|'''''c'''yclic '''r'''edundancy '''c'''heck''}}) est un outil logiciel permettant de détecter des erreurs de transmission ou de transfert par ajout, combinaison et comparaison de données [[Redondance#Informatique|redondantes]], obtenues grâce à une procédure de [[Fonction de hachage|hachage]]. Ainsi, une erreur peut être signalée à l'utilisateur lors de la copie d'un support ([[disque dur]], [[CD-Rom]], [[DVD-Rom]], clé [[USB]]{{etc.}}) vers un autre support de sauvegarde. Les CRC sont utilisés depuis le début des transmissions de donnée en informatique dès les bas niveaux. Les {{lang|en|''checksums''}} ([[somme de contrôle|sommes de contrôle]]) sont un mode de contrôle fonctionnant aussi par hachage, plus élaboré.

== Principe ==
Le CRC d'une trame (chaîne de donnée délimitée) est évalué (échantillonné puis calculé) avant  la transmission ou le transfert et inscrit sur quelques bits à la fin de la trame. Après transmission, il est recalculé et comparé au chiffre de fin de trame pour s’assurer que les données sont probablement identiques (probablement seulement car toutes les erreurs ne peuvent être détectées, c'est une détection statistique). Une différence conduit à une retransmission, parfois un code erreur.

Les calculs de CRC les plus utilisés sont conçus afin de pouvoir toujours détecter les erreurs de certains types, comme celles dues par exemple, aux interférences lors de la transmission.

On trouve des fonctions CRC dans différents logiciels comme ceux destinés à la sauvegarde, à la capture de données ([[Échantillonnage (signal)|échantillonnage]]) ainsi que dans les appareils et dispositifs de transmission de signaux numériques : [[DVB]], [[MPEG-2]] TS, [[Guichet automatique bancaire|DAB]]{{etc.}}

Le plus simple et largement répandu dans le transfert ordinateur /machine (commande numérique par exemple) est le CRC1, le bit de parité.

== Intégrité des données ==

Les CRC sont spécialement conçus pour protéger contre les types d'erreurs courants sur les canaux de communication, où ils peuvent fournir une assurance rapide et raisonnable de l'intégrité des messages livrés. Cependant, ils ne conviennent pas pour protéger contre l'altération intentionnelle des données.

Premièrement, comme il n'y a pas d'authentification, un attaquant peut éditer un message et recalculer le CRC sans que la substitution ne soit détectée. Lorsqu'ils sont stockés avec les données, les CRC et les fonctions de hachage cryptographique ne protègent pas en eux-mêmes contre la modification intentionnelle des données. Toute application nécessitant une protection contre de telles attaques doit utiliser des mécanismes d'authentification cryptographique, tels que des codes d'authentification de message ou des signatures numériques (qui sont généralement basés sur des fonctions de hachage cryptographiques).

Deuxièmement, contrairement aux fonctions de hachage cryptographiques, le CRC est une fonction facilement réversible, ce qui la rend inadaptée à une utilisation dans les signatures numériques<ref name="stigge-reversecrc">{{lien web|nom1=Stigge|prénom1=Martin|nom2=Plötz|prénom2=Henryk|nom3=Müller|prénom3=Wolf|nom4=Redlich|prénom4=Jens-Peter|titre=Reversing CRC – Theory and Practice|date=May 2006|page=17 |id=SAR-PR-2006-05 |éditeur=Humboldt University Berlin|url=http://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf|consulté le=4 février 2011|extrait=The presented methods offer a very easy and efficient way to modify your data so that it will compute to a CRC you want or at least know in advance.|archive-url=https://web.archive.org/web/20110719042902/http://sar.informatik.hu-berlin.de/research/publications/SAR-PR-2006-05/SAR-PR-2006-05_.pdf|archive-date=19 July 2011}}</ref>.

Troisièmement, CRC satisfait une relation similaire à celle d'une fonction linéaire (ou plus précisément, une fonction affine)<ref>{{lien web|titre=algorithm design — Why is CRC said to be linear? |url=https://crypto.stackexchange.com/a/34013 |website=Cryptography Stack Exchange |consulté le=5 mai 2019}}</ref> :

:<math>\operatorname{CRC}(x \oplus y) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y) \oplus c</math>,

où <math>c</math> dépend de la longueur de <math>x</math> et <math>y</math>. Cela peut également être indiqué comme suit, où <math>x</math>, <math>y</math> et <math>z</math> ont la même longueur

:<math>\operatorname{CRC}(x \oplus y \oplus z) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y) \oplus \operatorname{CRC}(z);</math>

par conséquent, même si le CRC est chiffré avec un [[chiffrement de flux]] qui utilise XOR comme opération de combinaison (ou un mode de [[chiffrement par bloc]] qui le transforme effectivement en un chiffrement de flux, tel que OFB ou CFB), le message et le CRC associé peut être manipulé sans connaître la clé de chiffrement ; c'était l'un des défauts de conception bien connus du protocole Wired Equivalent Privacy (WEP)<ref name="wep">{{article| nom1=Cam-Winget | prénom1=Nancy | nom2=Housley | prénom2=Russ | nom3=Wagner | prénom3=David | nom4=Walker | prénom4=Jesse | titre=Security Flaws in 802.11 Data Link Protocols | journal=Communications of the ACM | volume=46 | numéro=5 | pages=35–39 | date=May 2003 | doi=10.1145/769800.769823 | url=http://www.cs.berkeley.edu/~daw/papers/wireless-cacm.pdf | citeseerx=10.1.1.14.8775 | s2cid=3132937 | consulté le=1 novembre 2017 | archive-date=26 May 2013 | archive-url=https://web.archive.org/web/20130526173938/http://www.cs.berkeley.edu/~daw/papers/wireless-cacm.pdf }}</ref>.

== Implémentation ==
L’opération mathématique<ref>{{lien web|url=https://python.engineering/cyclic-redundancy-check-python/|titre=Cyclic redundancy check in Python|langue=en|website=python.engineering|date=2022-12-13}}</ref> essentielle dans le calcul d’un CRC est une division {{nobr|''modulo 2''}} dont le reste représente le CRC. Les CRC sont souvent appelés abusivement {{lang|en|''checksums''}} ([[somme de contrôle|sommes de contrôle]]), mais les sommes de contrôle proprement dites sont le résultat d'une addition. La partie principale de l’[[Algorithmique|algorithme]] est la suivante :

 '''fonction''' crc(''tableau de bits'' bitString[1..longueur], ''entier'' polynome)
 {
     shiftRegister := valeur_initiale '' // Généralement tous les bits à 0 ou 1''
     '''pour''' i '''de''' 1 '''à''' longueur
     {
         '''si''' bit de poids fort de shiftRegister [[XOR|xor]] bitString[i] vaut 1
         {
             // décaler d'1 bit vers la gauche équivaut à multiplier par 2
             shiftRegister := (shiftRegister décalé d'1 bit vers la gauche) [[XOR|xor]] polynome
         }
         '''sinon'''
         {
             shiftRegister := (shiftRegister décalé d'1 bit vers la gauche)
         }
     }
     '''retourne''' shiftRegister
 }

== Exemples d'implémentation ==

* {{en}} [http://www.simplycalc.com/crc32-source.php Implémentation de CRC-32 en JavaScript]

== Évolution ==
Les {{lang|en|''checksums''}} ([[somme de contrôle|sommes de contrôle]]) sont un mode de contrôle fonctionnant aussi par hachage, plus élaboré, portant sur des fichiers plus importants ([[transfert de fichier]], image disque etc.) très visibles dans le monde Linux.

Lors du téléchargement d'une distribution Linux, le MD5sum est disponible au téléchargement à côté de l'image disque. On télécharge les deux, puis un logiciel sur le pc recalcule le MD5sum pour le comparer à l'original pour valider l'intégrité du fichier téléchargé.

== Bibliographie ==
* Arvind M. Patel, ''{{Lang|en|A Multi-Channel CRC Register}}'', AFIPS'71 (printemps) {{Lang|en|Proceedings}}, {{date-|mai 1971}} {{doi|10.1145/1478786.1478789}}
* P. E. Boudreau, R. F. Steen, ''{{Lang|en|Cyclic Redundancy Checking by Program}}'', AFIPS'71 (automne) {{Lang|en|Proceedings}}, {{date-|novembre 1971}} {{doi|10.1145/1479064.1479067}}
* John R. Hill, ''{{Lang|en|A Table Driven Approach to Cyclic Redundancy Check Calculations}}'', ''{{Lang|en|ACM SIGCOMM Computer Communication Review}}'', Volume 9 Numéro 2, {{date-|avril 1979}} {{doi|10.1145/1015860.1015862}}
* Georgia Griffiths, G. Carlyle Stones, ''{{Lang|en|The Tea-Leaf Reader Algorithm: An Efficient Implementation of CRC-16 and CRC-32}}'', [[Communications of the ACM]], Volume 30 Numéro 7, {{date-|juillet 1987}} {{doi|10.1145/28569.28572}}
* Dilip V. Sarwate, ''{{Lang|en|Computation of Cyclic Redundancy Checks via Table Look-Up}}'', [[Communications of the ACM]], Volume 31 Numéro 8, {{date-|août 1988}} {{doi|10.1145/63030.63037}}
* Guido Duerinckx, ''{{Lang|en|Cyclic Redundancy Checks in Ada95}}'', ACM SIGAda Letters, Volume XVII Issue 1, janvier/{{date-|février 1997}} {{doi|10.1145/249984.249994}}
*{{lien web|langue=en |prénom1=Philip |nom1=Koopman |prénom2=Kevin |nom2=Driscoll |prénom3=Brendan |nom3=Hall |titre=Cyclic Redundancy Code and Checksum Algorithms to Ensure Critical Data Integrity |date=March 2015 |id=DOT/FAA/TC-14/49 |éditeur=[[Federal Aviation Administration]] |url=http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf |consulté le=9 mai 2015 |archive-date=18 May 2015 |archive-url=https://web.archive.org/web/20150518073214/http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf }}

== Liens externes ==
* {{en}} [http://www.simplycalc.com/crc32-text.php Calcul de CRC-32 en ligne], à partir [http://www.simplycalc.com/crc32-text.php de texte] ou [http://www.simplycalc.com/crc32-file.php d'un fichier], avec polynôme standard ou personnalisé, et le [http://www.simplycalc.com/crc32-source.php code source JavaScript] correspondant
* {{en}} [http://www.ross.net/crc/crcpaper.html {{lang|en|''A Painless Guide to CRC Error Detection Algorithms''}}]
* {{en}} [http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM {{lang|en|''The Great CRC Mystery - Terry Ritter''}}]
* [http://dvsoft.developpez.com/Articles/CRC/ Tutoriel sur le calcul des CRC - DVSoft]
* [https://www.lammertbies.nl/comm/info/crc-calculation.html Calcul du CRC 16]
*{{lien web|langue=en |prénom=Greg |nom=Cook |titre=Catalogue of parameterised CRC algorithms |site=CRC RevEng |url=https://reveng.sourceforge.io/crc-catalogue/all.htm |consulté le=18 septembre 2020 |archive-date=1 August 2020 |archive-url=https://web.archive.org/web/20200801122415/https://reveng.sourceforge.io/crc-catalogue/all.htm }}
*{{lien web|langue=en |nom=Koopman |prénom=Phil |titre=Blog: Checksum and CRC Central |url=http://checksumcrc.blogspot.com/ |consulté le=3 juin 2013 |archive-date=16 April 2013 |archive-url=https://web.archive.org/web/20130416070903/http://checksumcrc.blogspot.com/ }} — includes links to PDFs giving 16 and 32-bit CRC [[Distance de Hamming|Hamming distance]]s
*{{lien vidéo|langue=en |prénom1=Philip |nom1=Koopman |titre=Mechanics of Cyclic Redundancy Check Calculations  |date=January 2023 |via=YouTube |url=https://www.youtube.com/watch?v=qRqvdOAfxcA}}

== Notes et références ==
{{Références}}

{{Portail|informatique|mathématiques|télécommunications}}

[[Catégorie:Algorithme de hachage]]
[[Catégorie:Somme de contrôle]]