Comment calculer l'entropie approximative d'une chaîne de bits?

entropie n'est pas une propriété de la corde que vous avez, mais des cordes que vous auriez pu obtenir à la place. En d'autres termes, il qualifie le processus par lequel la chaîne a été générée.

dans le cas simple, vous obtenez une chaîne parmi un ensemble de N chaînes possibles, où chaque chaîne a la même probabilité d'être choisi que chaque autre, i.e. 1/n . Dans la situation, on dit que la corde avoir une entropie de N . L'entropie est souvent exprimée en bits, ce qui est une échelle logarithmique: une entropie de " n bits" est une entropie égale à 2 ⁿ .

par exemple: j'aime générer mes mots de passe en deux lettres minuscules, puis deux chiffres, puis deux lettres minuscules, et enfin deux chiffres (par exemple va85mw24 ). Les lettres et les chiffres sont choisis aléatoirement, uniformément, et indépendamment les uns des autres. Ce processus peut produire: 26*26*10*10*26*26*10*10 = 4569760000 mots de passe distincts, et tous ces mots de passe ont des chances égales d'être sélectionnés. L'entropie d'un tel mot de passe est alors 4569760000, ce qui signifie environ 32.1 bits.

l'équation d'entropie de Shannon est la méthode de calcul standard. Voici une implémentation simple en Python, sans vergogne copiée de la révélation codebase, et donc sous licence GPL:

def entropy(string):
        "Calculates the Shannon entropy of a string"

        # get probability of chars in string
        prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ]

        # calculate the entropy
        entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ])

        return entropy


def entropy_ideal(length):
        "Calculates the ideal Shannon entropy of a string with given length"

        prob = 1.0 / length

        return -1.0 * length * prob * math.log(prob) / math.log(2.0)

notez que cette implémentation suppose que votre flux de bits d'entrée est mieux représenté en octets. Cela peut ou peut ne pas être le cas pour votre problème de domaine. Ce que vous voulez vraiment est votre bitstream converti en une chaîne de nombres. Juste comment vous décidez sur ce que ces nombres sont EST domaine spécifique. Si vos nombres sont vraiment juste un et des zéros, alors convertissez votre bitstream en un tableau de uns et de zéros. La méthode de conversion que vous choisissez affectera les résultats que vous obtenez, cependant.

Il n'y a pas de réponse unique. L'entropie est toujours relative à un modèle. Quand quelqu'un parle d'un mot de passe ayant une entropie limitée, cela signifie "par rapport à la capacité d'un attaquant intelligent de prédire", et c'est toujours une limite supérieure.

Votre problème, c'est que vous essayez de mesurer l'entropie afin de vous aider à trouver un modèle, et c'est impossible; ce que l'entropie mesure de vous dire est la qualité d'un modèle.

ayant dit que, il existe des modèles assez génériques que vous pouvez essayer; ils sont appelés algorithmes de compression. Si gzip peut compresser vos données correctement, vous avez trouvé au moins un modèle qui peut les prédire correctement. Et gzip est, par exemple, la plupart du temps insensible à la simple substitution. Il peut gérer "od" fréquemment dans le texte aussi facilement qu'il peut gérer "les".

désolé de prendre autant de temps pour répondre à cette question.

Regardez mon récent article:

"BiEntropy - L'entropie approximative d'une durée de chaîne binaire"

http://arxiv.org/abs/1305.0954

" nous concevons, mettons en œuvre et testons un algorithme simple qui calcule l'entropie approximative d'une chaîne binaire finie de longueur arbitraire. L'algorithme utilise une moyenne pondérée des Entropies de Shannon de la chaîne et tous sauf le dernier dérivé binaire de la chaîne. Nous avons testé avec succès l'algorithme dans les domaines de la théorie des nombres premiers (où nous prouvons explicitement que la séquence des nombres premiers n'est pas périodique), la Vision humaine, la cryptographie, la génération de nombres aléatoires et la Finance Quantitative"

Le NIST Générateur de Nombre Aléatoire outils d'évaluation a un moyen de calcul de "se rapprocher de l'Entropie."Voici la courte description:

description approximative de L'essai D'entropie: l'objet de cet essai est le fréquence de chaque motif m-bit se chevauchant. Le but de le test consiste à comparer la fréquence de chevauchement des blocs de deux longueurs consécutives / adjacentes (m et m+1) par rapport au résultat escompté pour une séquence aléatoire.

et une explication plus détaillée est disponible à partir du PDF sur cette page:

http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

Voici une implémentation en Python (je l'ai aussi ajouté à la page Wiki):

import numpy as np

def ApEn(U, m, r):

    def _maxdist(x_i, x_j):
        return max([abs(ua - va) for ua, va in zip(x_i, x_j)])

    def _phi(m):
        x = [[U[j] for j in range(i, i + m - 1 + 1)] for i in range(N - m + 1)]
        C = [len([1 for x_j in x if _maxdist(x_i, x_j) <= r]) / (N - m + 1.0) for x_i in x]
        return -(N - m + 1.0)**(-1) * sum(np.log(C))

    N = len(U)

    return _phi(m) - _phi(m + 1)

exemple:

>>> U = np.array([85, 80, 89] * 17)
>>> ApEn(U, 2, 3)
-1.0996541105257052e-05

l'exemple ci-dessus est compatible avec l'exemple donné sur Wikipedia .

utilisant L'entropie de Boltzmann d'un mot avec cette formule: http://imgur.com/a/DpcIH

voici un algorithme O (n) qui le calcule:

import math
from collections import Counter


def entropy(s):
    l = float(len(s))
    return -sum(map(lambda a: (a/l)*math.log2(a/l), Counter(s).values()))