пользователей: 21219
предметов: 10452
вопросов: 177398
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Надежность шифров. Энтропия и избыточность языка.

Шеннон называет криптографическую систему совершенно секретной, если, каким бы ни был зашифровываемый с её помощью открытый текст, знания, которые могут быть получены из соответствующего ему шифротекста, не раскрывают никакой информации об исходном тексте за исключением, возможно, его длины.

В зависимости от сложности взлома различают:

  • Безусловно (теоретически) стойкие алгоритмы. Создают шифротексты, в которых содержится недостаточное кол-во информации, для однозначного определения соответствующих им текстов. При этом никакой метод криптоанализа не позволяет определить ключ или открытый текст, а также получить некоторую информацию о них. Примером можно считать секретные системы «Одноразовые блокноты». Длина ключа=длине текста. Ключ используется один раз.
  • Доказуемо стойкие. Их стойкость определяется сложностью решения хорошо известной математической задачи (RSA, Рида-Маллера, ассиметричные системы с открытым ключом).
  • Предположительно стойкие основаны на сложности решения частной математической задачи (DES, ГОСТ). Доказуемость: +хорошая изученность задач; - малая гибкость (с трудом поддаются модификациям и изменениям). Предположительность: +обладают большей гибкостью; - малая изученность математической задачи.

Требования к абсолютной стойкости:

Полная случайность (равновероятность ключа). Т.е. ключ нельзя выбрать с помощью к-л детерминированного устройства; Равенство длины ключа и длины открытого текста; Однократность использования ключа

Энтропия:

Информационная энтропия — мера неопределённости источника сообщений, определяемая вероятностями появления тех или иных символов при их передаче.

H(x)=-E=pi*log(2)p, где pi=p(X=xi).

Свойства энтропии:

            1)H(x)>0; 2) H(x)=0 при pi=1; 3)H(x)=log(2)n, при p=1/n; 4) 0<=H(x)<=log(2)n

Совместная энтропия:

H(x,y)=p*log(2)p, где

Условная энтропия:

H(x/y)=p(y)p(x/y)*log(2)p(x/y).

H(P/K,C)=0 – при известном шифротексте и ключе, его можно расшифровать.

H(C/P,K)=0 – при известном тексте и ключе, его можно зашифровать.

Избыточность языка:

Среди других понятий, которыми оперирует Клод Шелдон, имеется понятие "избыточность языка". Смысл его состоит в том, что не каждое сочетание букв образует слово. Одни буквы и буквенные сочетания употребляются очень часто, другие гораздо реже; третьи вообще не употребляются. Все это накладывает на язык множество запретов и тем самым создается "избыточность" языка, используемая криптоаналитиками для дешифровки вражеских шифров. Лингвисты определили величину избыточности в самых разных языках мира. И везде она колеблется в пределах 70-80 %. То есть в любом тексте 2/3 букв определяется не субъективной волей писца, а жесткими правилами грамматики.

Rl=1- Hl/log(2)p, где p – число символов алфавита, Hl=lim H(p^n)/n – энтропия естественного языка.


29.01.2016; 05:37
хиты: 137
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь