Algorithme d'attribution d'une série unique de bits pour chaque utilisateur?

Question

Le problème semble simple au début: il suffit d'attribuer un identifiant et de le représenter en binaire.

Le problème se pose parce que l'utilisateur est capable de changer autant de 0 bits en 1 bit. Pour clarifier, le hachage pourrait aller de 0011 à 0111 ou 1111 mais jamais 1010. Chaque bit a une chance égale d'être changé et est indépendant des autres changements.

Qu'auriez-vous à stocker pour passer du hachage -> utilisateur supposant un faible pourcentage de falsification des bits par l'utilisateur? Je suppose également un échec dans certains cas, donc la solution correcte devrait avoir un taux d'erreur acceptable.

Je voudrais une estimation du nombre maximum de bits falsifiés serait d'environ 30% de l'ensemble total.

Je suppose que le taux d'erreur acceptable dépend du nombre de hachages nécessaires et du nombre de bits qui sont définis par hachage.

Je suis inquiet avec une manipulation suffisante de l'ID ne peut pas être reconstruit à partir du hachage. La question que je pose, je suppose, est ce que les gardes de sécurité ou les systèmes de positionnement uniques que je peux utiliser pour assurer que cela se produise.

Answer 1

Votre question n'est pas entièrement claire pour moi. Êtes-vous en train de dire que vous voulez valider un utilisateur sur la base d'un hash de l'ID utilisateur, mais que vous craignez que l'utilisateur change certains des bits du hachage? Si telle est la question, alors tant que vous utilisez un algorithme de hachage éprouvé (tel que MD5), il y a un très faible risque qu'un utilisateur manipule les bits de son hachage pour obtenir l'ID d'un autre utilisateur.

Si ce n'est pas ce que vous recherchez, pourriez-vous clarifier votre question?

EDIT

Après avoir lu ces précisions, il semble que vous pourriez être après Forward Error Correction, une famille d'algorithmes qui vous permettent de reconstituer les données modifiées. Essentiellement avec FEC, vous codez chaque bit comme une série de 3 bits et appliquez le principe «major wins» lors du décodage à nouveau. Lors de l'encodage, vous représentez "1" comme "111" et "0" comme "000". Lors du décodage, si la plupart des 3 bits codés sont à zéro, vous décoderez cela pour zéro. Si la plupart des 3 bits codés valent 1, vous devez le décoder.

Answer 2

Vous essayez donc d'attribuer un "identifiant unique" qui restera un identifiant unique même s'il a été changé en quelque chose d'autre? Si le seul "falsification" est en train de changer 0 à 1 (mais pas vice-versa) (ce qui semble assez artificiel), alors vous pouvez obtenir un "ID" efficace en attribuant à chaque utilisateur une position de bit particulière, définir ce bit à zéro dans l'identifiant de cet utilisateur, et à un dans l'identifiant de chaque autre utilisateur.

Ainsi, tout piratage par l'utilisateur entraînera la corruption de son propre identifiant, mais ne permettra pas l'usurpation d'identité de quelqu'un d'autre.

Answer 3

Affectez à chaque utilisateur un ID avec le même nombre de bits défini. De cette façon, vous pouvez détecter immédiatement si une altération a eu lieu.Si vous créez en outre Hamming distance entre deux ID au moins 2n, vous pourrez alors reconstruire l'ID d'origine dans les cas où moins de n bits ont été définis.

Answer 4

La distance entre deux identifiants, (le nombre de bits que vous devez changer pour passer d'un mot à l'autre) est appelée la distance de Hamming. Les codes de correction d'erreur peuvent corriger jusqu'à la moitié de cette distance et vous donnent toujours le mot d'origine. Si vous supposez que 30% des bits peuvent être altérés, cela signifie que la distance entre 2 mots doit être de 60% des bits. Cela laisse 40% de cet espace à utiliser pour les ID. Tant que vous générez aléatoirement jusqu'à 40% des ID que vous pourriez pour un nombre donné de bits (inclure également la partie de correction d'erreur), vous devriez être en mesure de récupérer l'ID d'origine.