Как вычислить приблизительную энтропию битовой строки?

Question

Есть ли стандартный способ сделать это?

Googling - биты "приблизительной энтропии" - раскрывает несколько научных статей, но я хотел бы просто найти кусок псевдокода, определяющего приблизительную энтропию для данной строки битов произвольной длины.

(Если это легче сказать, чем сделать, и это зависит от приложения, мое приложение включает в себя 16 320 бит зашифрованных данных (зашифрованный текст). Но зашифровано как головоломка и не должно быть невозможно взломать. Я думал, что сначала проверьте энтропию, но не можете легко найти хорошее определение такого. Так что это похоже на вопрос, который должен быть в StackOverflow! Идеи для того, с чего начать с дешифрования 16-битных случайных битов, также приветствуются ...)

Смотрите также этот связанный вопрос:
Что такое энтропия в компьютерных науках?

Answer 1

Энтропия - это не свойство полученной вами строки, а строки, которые вы могли бы получить вместо этого. Другими словами, он квалифицирует процесс , с помощью которого была сгенерирована строка.

В простом случае вы получаете одну строку из набора N возможных строк, где каждая строка имеет одинаковую вероятность выбора, чем все остальные, т.е. 1 / N, В этой ситуации говорят, что строка имеет энтропию N . Энтропия часто выражается в битах, что представляет собой логарифмическую шкалу: энтропия « n бит» представляет собой энтропию, равную 2 ⁿ .

Например: мне нравится генерировать мои пароли в виде двух строчных букв, затем двух цифр, затем двух строчных букв и, наконец, двух цифр (например, va85mw24). Буквы и цифры выбираются случайным образом, равномерно и независимо друг от друга. Этот процесс может создать 26 * 26 * 10 * 10 * 26 * 26 * 10 * 10 = 4569760000 различных паролей, и все эти пароли имеют равные шансы на выбор. Тогда энтропия такого пароля составляет 4569760000, что означает около 32,1 бит.

Answer 2

Уравнение энтропии Шеннона является стандартным методом расчета. Вот простая реализация в Python, беззастенчиво скопированная из кодовой базы Revelation и, следовательно, лицензированная по лицензии GPL:

import math


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)

Обратите внимание, что эта реализация предполагает, что ваш входной поток битов лучше всего представлен в байтах. Это может или не может иметь место в вашей проблемной области. То, что вы действительно хотите, это ваш битовый поток, преобразованный в строку чисел. То, как вы решите, что это за числа, зависит от домена. Если ваши числа на самом деле только один и нули, то преобразуйте поток битов в массив единиц и нулей. Однако выбранный вами метод конвертации повлияет на результаты, которые вы получите.

Answer 3

Я считаю, что ответом является Колмогоровская сложность строки. Мало того, что это не ответственно с порцией псевдокода, сложность Колмогорова не является вычислимой функцией !

Одна вещь, которую вы можете сделать на практике, - это сжатие битовой строки с наилучшим доступным алгоритмом сжатия данных . Чем больше он сжимает, тем ниже энтропия.

Answer 4

Нет однозначного ответа. Энтропия всегда относительно некоторой модели. Когда кто-то говорит о пароле с ограниченной энтропией, он означает «относительно способности интеллектуального злоумышленника предсказывать», и это всегда верхняя граница.

Ваша проблема в том, что вы пытаетесь измерить энтропию, чтобы помочь вам найти модель, а это невозможно; что измерение энтропии может сказать вам, насколько хороша модель.

Сказав это, есть несколько довольно общих моделей, которые вы можете попробовать; они называются алгоритмами сжатия. Если gzip может хорошо сжать ваши данные, вы нашли по крайней мере одну модель, которая может хорошо ее предсказать. А gzip, например, в основном нечувствителен к простой замене. Он может обрабатывать «wkh» часто в тексте так же легко, как и «».

Answer 5

Извините, что так долго отвечаю на этот вопрос.

Взгляните на мою недавнюю работу:

"BiEntropy - Примерная энтропия конечной двоичной строки"

http://arxiv.org/abs/1305.0954

"Мы разрабатываем, внедряем и тестируем простой алгоритм, который вычисляет приблизительную энтропию конечной двоичной строки произвольной длины. Алгоритм использует средневзвешенное значение энтропий Шеннона для строки и всех, кромепоследняя двоичная производная строки. Мы успешно проверили алгоритм в полях теории простых чисел (где мы явно доказываем, что последовательность простых чисел не является периодической), человеческого зрения, криптографии, генерации случайных чисел и количественных финансов "

Answer 6

В инструменте оценки генератора случайных чисел NIST есть способ вычисления "Приблизительной энтропии". Вот краткое описание:

Приблизительный энтропийный тест Описание: Фокус этого теста Частота каждого перекрывающегося m-битового шаблона. Цель тест состоит в том, чтобы сравнить частоту перекрывающихся блоков двух последовательные / смежные длины (m и m + 1) в зависимости от ожидаемого результата для случайной последовательности.

Более подробное объяснение можно найти в PDF на этой странице:

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

Answer 7

Вот реализация на Python (я также добавил ее на вики-страницу):

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)

Пример:

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

Вышеприведенный пример соответствует примеру, приведенному в Википедии .

Answer 8

Использование энтропии Шеннона слова по формуле: http://imgur.com/a/DpcIH

Вот алгоритм O (n), который его вычисляет:

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