Obsažnost jazyka R_N

(Průměrná entropie)

  • Pro daný jazyk uvažujme množinu všech -znakových zpráv

  • Obsažnost jazyka pro zprávy délky znaků definujeme jako výraz

  • tj. průměrnou entropii na 1 znak (průměrný počet bitů informace v 1 znaku)

  • Kolik bitů potřebujeme pro zakódování 1 znaku

  • U přirozených jazyků výraz pro zvyšující se klesá

  • (např. pro text "Zítra odpoled" bude další znak určitě "n")

  • Z toho plyne

  • = obsažnost jazyka vzhledem k jednomu písmenu

  • Pro hovorovou angličtinu je až bitů/znak

Absolutní obsažnost jazyka ()

  • Mějme stejně pravděpodobné zprávy tvořené v jazyce s stejně pravděpodobnými znaky (pro angličtinu )

  • = absolutní obsažnost jazyka

  • Absolutní obsažnosti dosahuje takový znak, který poskytuje generátor náhodných znaků

  • Je to maximální neurčitost, kterou přirozené jazyky nemohou dosáhnout

Nadbytečnost jazyka ()

  • Nadbytečnost jazyka vzhledem k jednomu písmenu

  • Redundance

  • Vyjadřuje, kolik bitů je v jednom znaku daného jazyka nadbytečných

  • (redundance)

  • (kolik bitů je nadbytečných procentuálně)

  • Příklad pro AJ:

    • bitů/písmeno
    • bitů/písmeno
    • nadbytečných bitů/písmeno
    • nadbytečných bitů/písmeno
    • Tedy v anglickém textu je schováno 68% gramatických pravidel, které můžeme využít na prolomení

Konfúze a difúze

  • Základní techniky k potlačení redundance, abychom ji nebyli schopni využít

Konfúze

  • Maří vztahy mezi ŠT a OT
  • Ztěžuje studium redundance a statistických struktur OT
  • Např. substituce

Difúze

Vzdálenost jednoznačnosti ()

  • = neurčitost klíče

  • = redundance jazyka OT

  • Příklad pro AJ:

    • V šifrovaném textu o 28 znacích je dostatečné množství informace na to, aby zbýval průměru jediný možný OT
    • K rozluštění jednoduché substituce v AJ postačí v průměru 28 písmen ŠT

  • Další příklad:

    • Jaká bude vzdálenost jednoznačnosti pro text AES-192 při kódování UTF-32?
    • AES-192 entropie klíče
    • UTF-32 absolutní obsažnost jazyka , tedy redundance
Upozornění

Vzdálenost jednoznačnosti je odhad množství informace, nutného k vyluštění dané úlohy. Neříká však nic o složitosti takové úlohy.
(Tedy např. pro prolomení můžeme potřebovat delší text.)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 17. 3. 2025, 17:09