Discussion :

[Seb.26]

Bonjour à tous,

je suis à la recherche d'un algo (ou d'idée d'algos) pour signer un tableau de quelques octets (<128).

Le problème : cet algo doit pouvoir tourner sur un tout petit micro-contrôleur 8b à 8 MHz, et donc n'utiliser que des opérations sur des bytes (si possible) avec pas trop de multiplications (et encore moins de divisions ou de float !!!)

j'avais pensé à un truc tout bête genre une clef de 6 octets (6 octets, ça m'arrange) sur laquelle je XOR mes données, en pseudo-code/C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
fonction calcule_signature( byte data[], byte len_data )
{
  byte clef[6] = { ma clef secrète de 6 octets };
 
  for( i=0 ; i<len_data ; i++ )
  {
    clef[i%6] = clef[i%6] XOR data[i];
  }
 
  return clef;

Ou un truc dans le genre ...

Je ne cherche pas un algo hyper pointu, mais pas non plus un algo qui est cassé en 2 minutes avec un freeware trouvé sur le net ...

Par avance, merci de vos lumières.

[Edit] autre idée : un tableau de 256 octets aléatoires (en dur dans le code) qui me sert de germe pour la clef de 6 octets :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fonction calcule_signature( byte data[], byte len_data )
{
  byte dico[256] = { dico aléatoire ... };
 
  byte clef[6];
 
  for( i=0 ; i<6 ; i++ )
  {
    clef[i] = dico[ data[i] ];
  }
 
  for( i=0 ; i<len_data ; i++ )
  {
    clef[i%6] = clef[i%6] XOR data[i];
  }
 
  return clef;

C'est peut être déjà un poil mieux, non ?

[Seb.26]

NB: j'ai repensé à mon problème

En fait, peu importe la taille de la clef, disons 16 octets max

[Graffito]

Un CRC16 :
voir : http://dvsoft.developpez.com/Articles/CRC/

Un CRC16 tout simple ici:
http://coding.derkeiler.com/Archive/.../msg00256.html

Et si on utilise un CRC faisant l'objet d'une norme, on peut éviter d'être craké trop facilement ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Crc_de_ma_chaine=CRC_Normé(ma_chaine)
Crc_Final=Crc_Normé(ma_chaine+Crc_de_ma_chaine+Ma_Clé)

[pseudocode]

Tu peux aussi utiliser le checksum (16 octets) de l'algo MD2. Et si ca ne suffit pas, calculer complètement le message digest MD2.

http://tools.ietf.org/html/rfc1319

[Seb.26]

Merci à vous, ça a l'air bien tout ça !!!

Je vais regarder et tester un peu pour avoir une idée du temps d'exécution sur mon "veau" et voir la taille du code que cela demande aussi ...

J'espère pouvoir faire tenir tout ça dans les 256B de RAM !!! ( vive l'embarqué ! )

... encore quelques questions :

à propos du Checksum du MD2 : il utilise une table de 256B (issue de PI), elle doit être conservée ou je peux la changer par une autre sans perdre en efficacité ?
-> par exemple un tableau de 256 valeurs de 0 à 256, et ensuite je fais x permutations façon aléatoire.

En tout cas, le MD2 me plait bien !!!

Si ça passe pas, je me rabattrais sur un CRC plus simple .

Grand merci à vous !

[pseudocode]

à propos du Checksum du MD2 : il utilise une table de 256B (issue de PI), elle doit être conservée ou je peux la changer par une autre sans perdre en efficacité ?
-> par exemple un tableau de 256 valeurs de 0 à 256, et ensuite je fais x permutations façon aléatoire.

A mon avis, le choix des décimales de PI ne doit pas être anodin. Donc autant rester avec les décimales de PI mais en faire une autre permutation aléatoire.

[Graffito]

A mon avis, le choix des décimales de PI ne doit pas être anodin...faire une autre permutation aléatoire (après le calcul du checksum).

+1
Ce type de tables correspond en général à des "constantes" pré-calculées en fonction de l'algorithme pour permettre une optimisation du calcul.
Ainsi, des modifications de ces "constantes" pourraient être inopportunes.

[Seb.26]

Hello,

sauf si j'ai rien compris, mais il me semble que le tableau ne contient pas les décimales de PI mais toutes les valeurs 0..255 ?!

Les décimales de PI ont servies à faire les permutations dans le tableau (pour obtenir des permutations qui soient vraiment aléatoires)

Mais c'est vrai que je peux déjà partir de ce tableau ci, et refaire des permutations dessus ... car même si mes permutations ne sont pas parfaites, la source étant considérée comme tel, le résultat le sera, non ?

En fait, l'idée serait de ne calculer que le CRC du MD2, mais avec un tableau modifié (qui serait déjà un genre de clef secrète)

[pseudocode]

Hello,

sauf si j'ai rien compris, mais il me semble que le tableau ne contient pas les décimales de PI mais toutes les valeurs 0..255 ?!

Les décimales de PI ont servies à faire les permutations dans le tableau (pour obtenir des permutations qui soient vraiment aléatoires)

Oui, tout a fait, tu as raison. C'est moi qui me suis gouré dans mes explications.

[Seb.26]

Oui, tout a fait, tu as raison. C'est moi qui me suis gouré dans mes explications.

OK, je vais partir là dessus alors, merci bien.