encryption - quimica - entropía información

¿Cómo calculo la entropía aproximada de una cadena de bits?

Question

¿Hay una manera estándar de hacer esto?

Google - bits de "entropía aproximada" - descubre múltiples trabajos académicos, pero me gustaría encontrar un trozo de pseudocódigo que defina la entropía aproximada para una cadena de bits dada de longitud arbitraria.

(En caso de que sea más fácil decirlo que hacerlo, y depende de la aplicación, mi aplicación implica 16,320 bits de datos cifrados (texto cifrado). Pero cifrado como un rompecabezas y no pensado para ser imposible de descifrar. Pensé que primero verificaría el entropía pero no podía encontrar fácilmente una buena definición de tal. Así que parecía una pregunta que debería estar en StackOverflow. Ideas para donde comenzar con la eliminación de cifrado 16k bits aparentemente aleatorios también son bienvenidos ...)

Ver también esta pregunta relacionada:
¿Cuál es la definición de entropía de informática?

Answer 1

Aquí hay una implementación en Python (también lo agregué a la página 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)

Ejemplo:

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

El ejemplo anterior es consistente con el ejemplo dado en Wikipedia .

Answer 2

Creo que la respuesta es la Complejidad de Kolmogorov de la cuerda. No solo no se puede responder con un trozo de pseudocódigo, ¡la complejidad de Kolmogorov no es una función computable !

Una cosa que puedes hacer en la práctica es comprimir la cadena de bits con el mejor algoritmo de compresión de datos disponible. Cuanto más se comprime, menor es la entropía.

Answer 3

El kit de herramientas de evaluación NIST Random Number Generator tiene una forma de calcular "Entropy Approximate". Aquí está la breve descripción:

Descripción aproximada de la prueba de entropía: El enfoque de esta prueba es la frecuencia de cada patrón de m bits superpuesto. El propósito de la prueba es comparar la frecuencia de bloques superpuestos de dos longitudes consecutivas / adyacentes (my m + 1) contra el resultado esperado para una secuencia aleatoria.

Y una explicación más detallada está disponible en el PDF en esta página:

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

Answer 4

La entropía no es una propiedad de la cadena que obtuviste, sino de las cadenas que podrías haber obtenido en su lugar. En otras palabras, califica el proceso por el cual se generó la cadena.

En el caso simple, se obtiene una cadena entre un conjunto de N cadenas posibles, donde cada cadena tiene la misma probabilidad de ser elegida que cualquier otra, es decir, 1 / N. En la situación, se dice que la cuerda tiene una entropía de N. La entropía a menudo se expresa en bits, que es una escala logarítmica: una entropía de " n bits" es una entropía igual a 2 ⁿ .

Por ejemplo: me gusta generar mis contraseñas como dos letras minúsculas, luego dos dígitos, luego dos letras minúsculas, y finalmente dos dígitos (por ejemplo, va85mw24 ). Las letras y los dígitos se eligen de forma aleatoria, uniforme e independiente entre sí. Este proceso puede producir 26 * 26 * 10 * 10 * 26 * 26 * 10 * 10 = 4569760000 contraseñas distintas, y todas estas contraseñas tienen las mismas posibilidades de ser seleccionadas. La entropía de tal contraseña es entonces 4569760000, lo que significa aproximadamente 32.1 bits.

Answer 5

No hay una única respuesta. La entropía es siempre relativa a algún modelo. Cuando alguien habla de una contraseña que tiene entropía limitada, significa "relativa a la capacidad de un atacante inteligente para predecir", y siempre es un límite superior.

Tu problema es que estás tratando de medir la entropía para ayudarte a encontrar un modelo, y eso es imposible; lo que una medición de entropía puede decirle es qué tan bueno es un modelo.

Habiendo dicho eso, hay algunos modelos bastante genéricos que puedes probar; se llaman algoritmos de compresión. Si gzip puede comprimir bien tus datos, has encontrado al menos un modelo que puede predecirlo bien. Y gzip es, por ejemplo, en su mayoría insensible a la sustitución simple. Puede manejar "wkh" frecuentemente en el texto tan fácilmente como puede manejar "the".

Answer 6

Perdón por tomar tanto tiempo respondiendo esta pregunta.

Eche un vistazo a mi trabajo reciente:

"BiEntropy - La entropía aproximada de una cadena binaria finita"

http://arxiv.org/abs/1305.0954

"Diseñamos, implementamos y probamos un algoritmo simple que calcula la entropía aproximada de una cadena binaria finita de longitud arbitraria. El algoritmo usa un promedio ponderado de las entropías de Shannon de la cadena y todas menos la última derivada binaria de la cadena. probar el algoritmo en los campos de Teoría del número primo (donde demostramos explícitamente que la secuencia de los números primos no es periódica), visión humana, criptografía, generación de números aleatorios y finanzas cuantitativas "

Answer 7

Usando la entropía de Boltzmann de una palabra con esta fórmula: http://imgur.com/a/DpcIH

Aquí hay un algoritmo O (n) que lo calcula:

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()))

Answer 8

La ecuación de entropía de Shannon es el método estándar de cálculo. Aquí hay una implementación simple en Python, descaradamente copiada de la base de código de Revelation y, por lo tanto, licencia 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)

Tenga en cuenta que esta implementación asume que su flujo de bits de entrada se representa mejor como bytes. Este puede o no ser el caso para su dominio problemático. Lo que realmente quieres es que tu bitstream se convierta en una cadena de números. La forma en que decida cuáles son esos números es específico del dominio. Si sus números son solo uno y ceros, convierta su flujo de bits en una matriz de unos y ceros. Sin embargo, el método de conversión que elija afectará los resultados que obtenga.