Criptografía (CCLIV): Cálculo de la Entropía (H) en python

Continúo poniendo scripts de programación en python para automatizar tareas que tengan relación con la criptografía.

En este post incluyo y comento un script en python para el cálculo de la Entropía (H).

De lo que nos cuenta wikipedia sobre la Entropía (H) en el ámbito de la información, entiendo que ésta mide la incertidumbre de una fuente de información y puede ser considerada como la cantidad de información promedio que contienen los símbolos usados.

Aplicando lo anterior a un mensaje sin cifrar o texto en claro y considerando los caracteres del alfabeto como los símbolos empleados, se puede decir que la cantidad de información (I) de un carácter del alfabeto se define como:

Donde:
I: cantidad de información.
A: carácter "A" del alfabeto.
P(A): probabilidad de aparición del carácter "A" en el mensaje sin cifrar o texto en claro.

Es decir, cuanto más alta sea la probabilidad de aparición de un carácter concreto, menos cantidad de información nos aporta (si su probabilidad de aparición fuera la máxima, 1, la cantidad de información que nos aportaría sería 0), y cuanto más improbable sea la aparición del carácter más información nos aporta (si su probabilidad de aparición se acercara a 0, la cantidad de información que nos aportaría tendería a +∞).

Y, ¿para qué sirve esto? La Entropía (H) tiene diversas aplicaciones en la criptología y, en concreto, en el criptoanálisis, ya que, como he dicho antes, puede ser considerada como la cantidad de información promedio que contienen los caracteres en el mensaje sin cifrar o texto en claro y, al igual que el Índice de Coincidencia (IC), es como la "huella" del idioma en el que se escribió el mensaje sin cifrar o texto en claro; una característica propia que tiende a cierto valor característico. Por tanto, también al igual que el IC, la Entropía (H) se puede utilizar para calcular la longitud de la clave con la que se cifró el mensaje en el caso de cifrados de sustitución polialfabética con clave periódica (ver este post donde explico el ataque mediante el IC al cifrado de Vigenère).

Para el español la entropía está en torno a 4,04 y la entropía de un mensaje M, denotado por H(M), es el valor medio ponderado de la cantidad de información de los diversos caracteres del mensaje:

Donde:

H: Entropía.

M: mensaje sin cifrar o texto en claro.

mi: carácter i-ésimo del mensaje sin cifrar o texto en claro.

p(mi): probabilidad de aparición del carácter i-ésimo en el mensaje sin cifrar o texto en claro.

n: número de caracteres o tamaño del mensaje sin cifrar o texto en claro.

En el script este cálculo se implementa de la siguiente manera:

- alfabeto.index(caracter): el método index() devuelve la posición de la primera ocurrencia del valor especificado.

En el script, devuelve la posición de cada carácter del alfabeto.

- texto.count(caracter): el método count() devuelve el número de veces que aparece el valor especificado.

En el script, devuelve el número de veces que aparece cada carácter del alfabeto en el texto.

- frecuencia_relativa[alfabeto.index(caracter)]=texto.count(caracter): en el script, calcula la frecuencia relativa de cada carácter del alfabeto en el texto y deja el resultado en la posición que corresponde a cada uno de ellos en la lista frecuencia_relativa.

- Y finalmente, la Entropía (H) se calcula mediante la fórmula indicada anteriormente.

- Script python para el cálculo de la Entropía (H):

El script es el siguiente:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# ENTROPÍA:
#
# Cálculo de la entropía de un texto.
#
# http://mikelgarcialarragan.blogspot.com/

import re
from unicodedata import normalize
from math import log2

def main():
    # ALFABETO:
    alfabeto = "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ"
    print ("")
    print ("[+] Alfabeto:", alfabeto)

    # Se introduce el texto del que se desea calcular la Entropía (H).
    # Se convierten los caracteres a mayúsculas y se eliminan los espacios,
    # las tildes, diéresis, etc.
    texto = "*"
    while not texto.isalpha():
        print ("")
        texto = input('Texto del que se desea hallar la Entropía (H): ').upper()
        texto = texto.replace(' ','')
        texto = re.sub(r"([^n\u0300-\u036f]|n(?!\u0303(?![\u0300-\u036f])))[\u0300-\u036f]+",
                    r"\1", normalize("NFD", texto), 0, re.I)
        texto = normalize("NFC", texto)
        if not texto.isalpha():
            print ("*** ERROR: El texto sólo debe contener caracteres alfabéticos.")

    # CÁLCULO DE LA ENTROPÍA(H):
    # Cálculo de la frecuencia relativa de cada uno de los caracteres del alfabeto en el texto.
    frecuencia_relativa=[0 for caracter in alfabeto]
    for caracter in alfabeto:
        frecuencia_relativa[alfabeto.index(caracter)]=texto.count(caracter)

    # Cálculo de H.
    h = 0
    for caracter in range(0, len(frecuencia_relativa)):
        if frecuencia_relativa[caracter] != 0:
            h+= frecuencia_relativa[caracter]/len(texto) * log2(len(texto)/frecuencia_relativa[caracter])
    print ("")
    print("[+] La Entropía (H) es:", h)

if __name__ == '__main__':
    main()

Lo ejecuto:

Quizás también te interese: