cerhu > comp.* > comp.algorithmes

Etienne (05/10/2010, 12h24)
Salut.

Je cherche un algorithme de hachage permettant de créer une clé sur 12 bits.

Quelqu'un aurait il les connaissances suffisantes pour réduire une clé
SHA-1 a 12 bits par exemple. (enfin sauf que l'idée c'est d'aller assez
vite lors de la production de la clé)
Ou simplement un algo qui ferai ca de maniere assez équilibré !

Merci
Etienne
Fabien LE LEZ (05/10/2010, 13h13)
On Tue, 05 Oct 2010 12:24:18 +0200, Etienne <etienne>:

>Je cherche un algorithme de hachage permettant de créer une clé sur 12 bits.


J'imagine que c'est juste pour vérifier qu'il n'y a pas eu de
corruption accidentelle. Dans ce cas, un CRC-12 ira très bien.

Tu ne peux pas te servir d'un hash si court pour une signature
cryptographique, puisqu'il suffit de 1000 essais en moyenne pour
trouver une collision.
Fabien LE LEZ (05/10/2010, 13h14)
J'ai bafouillé :

>puisqu'il suffit de 1000 essais en moyenne


2000, pardon.
Etienne (05/10/2010, 13h41)
Le 05/10/2010 13:13, Fabien LE LEZ a écrit :
> On Tue, 05 Oct 2010 12:24:18 +0200, Etienne<etienne>:
>> Je cherche un algorithme de hachage permettant de créer une clé sur 12 bits.

> J'imagine que c'est juste pour vérifier qu'il n'y a pas eu de
> corruption accidentelle. Dans ce cas, un CRC-12 ira très bien.


non, c'est pour implémenter une table de Hash en assembleur :)
Etienne
Etienne (05/10/2010, 13h52)
Le 05/10/2010 13:13, Fabien LE LEZ a écrit :
> Dans ce cas, un CRC-12 ira très bien.


Bon j'ai regardé les CRC
Hum je pense que c'est un peu trop complexe à calculer...

Je vias devoir trouver une fonction de hashage plus simple
Etienne
Etienne (05/10/2010, 14h13)
Le 05/10/2010 13:13, Fabien LE LEZ a écrit :
> On Tue, 05 Oct 2010 12:24:18 +0200, Etienne<etienne>:


En fait, sur le net on trouve pas mal de fois cette fonction

while (*s)
{
hash = hash * 53 + *s++;
}

ou 101 peut être n'importe quel nombre premier.
Mais ca ne colle pas dans mon cas puisque forcément apres quelques
itérations les premières valeurs vont sortir des 12 bits...

je pense donc faire un truc dans ce genre

while (*s)
{
hash = hash * 53 + *s++ + (hash >> 12);
}

bon ben reste plusqu'à tester..
comment teste t on le taux de collision d'une fonction de hash ???

Etienne
Etienne (05/10/2010, 14h47)
Le 05/10/2010 14:13, Etienne a écrit :
> bon ben reste plusqu'à tester..
> comment teste t on le taux de collision d'une fonction de hash ???


Alors...
C'est tres byzarre...

j'ai donc écrit un petit script PHP pour voir la performance de la fonction.

$TotalCount = 0;
for($t = 0 ; $t < 1024 ; $t++)
{
$tHash = array();
$hash = 0;
$nbHash = 0;
for (;;)
{
$l = rand(2, 24);
$str = '123456789012345678901234';
for ($c = 0 ; $c < $l ; $c++)
$str{$c} = chr(rand(33, 125));
$str = substr($str, 0, $l);

// Debut Hash
$hash = 0;
for ($c = 0 ; $c < $l ; $c++)
{
$hash = $hash * 101 + ord($str{$c});
$offset = $hash >> 12;
$hash = $hash + $offset;
$hash = $hash & 4095;
}
// Fin Hash

$nbHash++;
echo "$t $nbHash $str : $hash\n";

if (isset($tHash[$hash])) break;
$tHash[$hash] = 1;
$TotalCount++;
}
}
echo "Moyenne = " . ($TotalCount >> 10) . "\n";

Verdict.
il faut calculer 83 clé pour avoir collision.
Au début je trouvais ça pas terrible.

J'ai donc remplacé mon petit calcul par une clé md5
$hash = substr(md5($str), 10, 3);
donc je prend 12 bit au milieu de la chaine.

Et là j'obtient un score inférieure de 77

j'ai tésté aussi
$hash = substr(sha1($str), 10, 3);

et là j'ai 78.

bon les scores peuvent varier de 1 ou 2 mais globalement ca reste dans
cet ordre de grandeur.

Bon ben le résultat étant meilleur que les sha1 je suppose qu'on peut
estimer que le fonction de hash fera l'affaire.

Etienne
Fabien LE LEZ (05/10/2010, 15h04)
On Tue, 05 Oct 2010 14:13:53 +0200, Etienne <etienne>:

>comment teste t on le taux de collision d'une fonction de hash ?


Vérifier qu'un tel hash est sans biais, c'est très facile : génère
4096000 (par exemple) chaînes aléatoires (mais ressemblant assez à tes
données réelles), et calcule ces 4096000 hashs. Logiquement, tu dois
avoir à peu près 1000 de chaque (mille 0, mille 1, ..., mille 4095).

Si ton hash est effectivement sans biais, la probabilité de collision
est donnée par le paradoxe des anniversaires.
Etienne (05/10/2010, 16h23)
Le 05/10/2010 15:04, Fabien LE LEZ a écrit :
> On Tue, 05 Oct 2010 14:13:53 +0200, Etienne<etienne>:
> Vérifier qu'un tel hash est sans biais, c'est très facile : génère
> 4096000 (par exemple) chaînes aléatoires (mais ressemblant assez à tes
> données réelles), et calcule ces 4096000 hashs. Logiquement, tu dois
> avoir à peu près 1000 de chaque (mille 0, mille 1, ..., mille 4095).
> Si ton hash est effectivement sans biais, la probabilité de collision
> est donnée par le paradoxe des anniversaires.


Aussitot dit aussitot fait.

Alors j'ai fais 4096000 tests.
et tout est dans la définition du a peu pres :)
En gros les résultats vont de 884 à 1121

Si j'enlève les 5 % d'enregistrements les plus déviants (donc j'enleve
204 enregistrements de chaque coté)
Les résultats vont de 945 à 1057

Le test SHA1 donne
Entre 867 et 1187
et en enlevant 5%
on est entre 931 et 1076

Bon ben semblerai que mon algo tout bete soit un peu meilleur que le
sha1. c'est plutot cool...

Etienne
Fabien LE LEZ (06/10/2010, 21h23)
On Tue, 05 Oct 2010 16:23:16 +0200, Etienne <etienne>:

>En gros les résultats vont de 884 à 1121


Ce qui est très bon.
Si tu avais du 100 ou du 10000, tu pourrais t'inquiéter.

>Bon ben semblerai que mon algo tout bete soit un peu meilleur que le
>sha1.


Faut dire aussi que SHA1 n'a pas été prévu pour être réduit à 12
bits...
WebShaker (06/10/2010, 22h02)
Le 06/10/2010 21:23, Fabien LE LEZ a écrit :
> Faut dire aussi que SHA1 n'a pas été prévu pour être réduit à 12
> bits...


Sans doute.
J'imagine vaguement qu'ils ne se sont pas lancé dans un truc aussi
compliqué pour faire moins bien qu'une pauvre fonction a 2 balles :)

bon ben il n'y a plus qu'a comme on dit.
Etienne
Discussions similaires
Fonction retournant une formule

Fonction retournant un pointeur...

Fonction retournant 2 valeurs

Fonction retournant une valeur constante


Fuseau horaire GMT +2. Il est actuellement 04h22. | Privacy Policy