Calcul de checksum

Version imprimable

22/07/2009, 11h46
Carlito78

Calcul de checksum

Bonjour à tous,

voilà je cherche comment calculer un checksum d'une trame d'octet du type:

11 FF C5 00 0E 95 00 28 01 05 98 22 81 00 0E F7 FC FD

dont le checksum devrait être : F9 C4

Pour simple indication, on me dit: "somme de la trame complémentée + 1"

Mais mes cours de réseaux sont bien loin, et j'ai beau essayer plusieurs solutions je ne retombe pas sur mes pattes...

Si quelqu'un à une idée, çà m'enlèverai une sacré épine du pied =)

Par avance: Merci !

ps: pour info le langage cible est le C# avec un tableau de byte[] en entrée...
24/07/2009, 12h05
Mac LAK

Moi, je trouve F921 en checksum... Ce qui me fait dire qu'il doit te manquer un octet, ou qu'il y a un problème de propagation de retenue qui n'est pas indiqué dans ta "formule". En pratique, j'ai l'impression plutôt que tu as des octets en trop... Il y a une différence de 0xA3 en trop pour retomber sur ses pattes.

Mais la formule normale, c'est "NOT ( Somme(i=1..n)(Trame[i] ) + 1", le "not" étant le complément à un (ou négation binaire).

Peux-tu nous dire de quel protocole exactement il s'agit ? Si c'est un protocole "connu", ça aidera pas mal à trouver le problème.

Citation:

Envoyé par Mac LAK

Moi, je trouve F921 en checksum...

pareil.

Code:

1
2
3
4
5
6
7
8
9
int[] data ={
	0x11 ,0xFF ,0xC5 ,0x00 ,0x0E ,0x95 ,0x00 ,0x28 ,0x01 ,0x05 ,0x98 ,0x22 ,0x81 ,0x00 ,0x0E ,0xF7 ,0xFC ,0xFD
};
 
int checksum=0;
for(int i : data) checksum += i;
checksum = (~checksum + 1) & 0xFFFF; 
 
System.out.println(Integer.toHexString(checksum));

24/07/2009, 12h19
jabbounet

le principe du checksum repose sur une division polynomiale

le resultat de ton checksum va dépendre du polynome utilisé...

http://www.cs.jhu.edu/~scheideler/co...4_S02/CRC.html
24/07/2009, 13h29
Mac LAK

Citation:

Envoyé par jabbounet

le principe du checksum repose sur une division polynomiale

le resultat de ton checksum va dépendre du polynome utilisé...

http://www.cs.jhu.edu/~scheideler/co...4_S02/CRC.html

C'est vrai pour un CRC16, mais là, c'est une simple somme tout comme les checksums UDP et IP par exemple. Il n'y a pas de polynôme, mais plutôt des règles d'arithmétique binaire à connaître à l'avance.

Notamment, il peut manquer des octets dans le tableau, ou l'algorithme peut sommer des octets en dehors de la trame utile : UDP, par exemple, ajoute les deux adresses IP (qui ne font pas partie de la zone UDP de la trame !!!) à son checksum.
24/07/2009, 14h25
Carlito78

Bonjour à tous et tout d'abord merci pour vos réponses.

Le type de protocole utilisé, est un protocole propriétaire, et donc il ne s'agit pas de protocole "connu".

Je vais vérifier de mon coté s'il ne s'agit tout simplement pas d'une erreur, dans l'exemple énoncé.

Je vous tiens au courant...
24/07/2009, 15h05
jabbounet

Citation:

Envoyé par Mac LAK

C'est vrai pour un CRC16, mais là, c'est une simple somme tout comme les checksums UDP et IP par exemple. Il n'y a pas de polynôme, mais plutôt des règles d'arithmétique binaire à connaître à l'avance.

Notamment, il peut manquer des octets dans le tableau, ou l'algorithme peut sommer des octets en dehors de la trame utile : UDP, par exemple, ajoute les deux adresses IP (qui ne font pas partie de la zone UDP de la trame !!!) à son checksum.

ce n'est effectivement pas un polynome pour TCP/UDP,
Mais on retrouve des polynômes dans pas mal d'endroit ailleurs (dans les couches plus basse) quelque soit la méthode il y'a toujours un concept mathématique derrière.

En divergeant un peu
quelques liens intéressant pour ceux qui veulent se cultiver sur le sujet
http://ram-0000.developpez.com/tutor...e/?page=page_6
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
http://www.ross.net/crc/download/crc_v3.txt

Et une source sur md4/5....
http://www.faqs.org/rfcs/rfc1320.html
http://www.faqs.org/rfcs/rfc1321.html

http://www.opensource.apple.com/sour...bsum/sum-md5.c
24/07/2009, 15h17
pseudocode

Citation:

Envoyé par jabbounet

ce n'est effectivement pas un polynome pour TCP/UDP,
Mais on le retrouve des polynômes dans pas mal d'endroit ailleurs (dans les couches plus basse) quelque soit la méthode il y'a toujours un concept mathématique derrière.

J'ai testé la plupart des chercksum 16-bits usuels, et aucun ne se rapproche plus du résultat que celui qu'on a donné.
24/07/2009, 15h44
Mac LAK

Je reste vraiment persuadé qu'il manque des données, ou qu'il y en a trop...

L'énoncé de la méthode est clair, c'est proche du checksum BIOS (aussi appelé "sum16"), et le fait que l'on trouve une valeur très proche en l'appliquant plaide encore en la faveur de cet algo : avec un CRC, on aurait eu une dispersion bien plus élevée et on serait tombés sur un résultat très éloigné.
24/07/2009, 15h52
pseudocode

Citation:

Envoyé par Mac LAK

L'énoncé de la méthode est clair, c'est proche du checksum BIOS (aussi appelé "sum16")

Hum... y a un complément a 2 dans le "sum16" ? :koi:
24/07/2009, 16h00
Mac LAK

Citation:

Envoyé par pseudocode

Hum... y a un complément a 2 dans le "sum16" ? :koi:

Tacitement, vu que la somme des données et du checksum doit être nulle... Donc, le checksum doit être le complément à deux de la somme afin d'arriver à zéro, bien entendu.

Pour ceux qui ne comprennent pas de quoi on parle : Le complément à deux (égal au complément à un [ou NOT binaire] augmenté de un) est, justement, l'opposé binaire d'un nombre quelconque.
Il y a propagation d'un bit au passage lorsque l'on additionne les deux, mais une fois remis à la plage d'origine sur N bits (16 ici), on obtient bien zéro.
24/07/2009, 16h03
pseudocode

Citation:

Envoyé par Mac LAK

Tacitement, vu que la somme des données et du checksum doit être nulle...

Vu comme ca effectivement. :ccool:

Effectivement, il y avait tout simplement une erreur dans la trame d'exemple qui nous a été fournie... (merci le client ! °\o/°)

L'algorithme a appliquer en C# est bien:

Code:

1
2
3
4
5
6
7
8
 
        public static byte[] CalculateCS(byte[] data)
        {
              short cs = 0; 
              foreach (byte b in data)  cs += b; //Somme des octets
              cs = (short)((~cs) + 1); //Complément à 2 
              return System.BitConverter.GetBytes(cs); 
        }

Merci à vous en tout cas !

24/07/2009, 16h16
Mac LAK

Citation:

Envoyé par Carlito78

Effectivement, il y avait tout simplement une erreur dans la trame d'exemple qui nous a été fournie... (merci le client ! °\o/°)

Pendons le dernier client avec les tripes du dernier commercial !! :mouarf:
De rien, bonne continuation et merci pour le :resolu: !