Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.03.2010, 17:36
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Инструмент для детектирования шифртекста
Доброго дня! Может кто подскажет...

Исходные данные - блок данных относительно небольшого размера - единицы/сотни килобайт
Задача - определить с высокой вероятностью, является ли данный блок шифртекстом.

Предполагаемое решение:
поскольку одним из требований к шифртексту является "вероятность появления 0 и 1 равны 0,5 , причём значение каждого последующего бита не зависит от предыдущих", отличить шифртекст от открытого текста можно по статистике появления 0 и 1, их пар, троек и т.д. Это все интуитивно понятно.

Вопрос:
Нужны ссылки на алгоритмы (может быть opensource реализации) подсчета битовой статистики, а также критерии, по которым принимать решение "открыто/зашифровано".

Заранее спасибо
  #2  
Старый 01.03.2010, 17:58
_persicum_

 
Сообщений: n/a

http://file.qip.ru/file/109465225/ed7e7ff/crc32.html

можешь поюзировать мою прогу с ключом -e
Выдает энтропию, хи-кавадрат и дюрбин-ватсон.
соответственно, можно различить три вида текста - непожатый, пожатый-нешифрованный, и шифрованный. Сам догадайся как.
Энтропия нормирована к 100%, остальные критерии к 1.000, так что думать много не придется
  #3  
Старый 01.03.2010, 18:18
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Спасибо! Интересующая меня функциональность в ДЛЛ или в ЕХЕ? Если в ДЛЛ, то можно описание интерфейса библиотеки? Дело в том, что решение мне нужно принимать программно, поэтому либо подключать ДЛЛ, либо сырцы )
  #4  
Старый 01.03.2010, 18:28
гость

 
Сообщений: n/a

Сообщение от _persicum_ Посмотреть сообщение
http://file.qip.ru/file/109465225/ed7e7ff/crc32.html

можешь поюзировать мою прогу с ключом -e
Выдает энтропию, хи-кавадрат и дюрбин-ватсон.
соответственно, можно различить три вида текста - непожатый, пожатый-нешифрованный, и шифрованный. Сам догадайся как.
Энтропия нормирована к 100%, остальные критерии к 1.000, так что думать много не придется
а что твоя прога на данных из /dev/random выдаст?
  #5  
Старый 02.03.2010, 09:17
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Сообщение от _persicum_
можешь поюзировать мою прогу с ключом -e
Выдает энтропию, хи-кавадрат и дюрбин-ватсон.
Спасибо, сегодня проведу тесты на небольшой выборке, результаты выложу
  #6  
Старый 02.03.2010, 11:23
_persicum_

 
Сообщений: n/a

Запрограммировать байтовый хи- квадрат весьма несложно самому, но подождем результаты тестов.
  #7  
Старый 02.03.2010, 11:56
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Итак, результат теста. В каждой группе - 5 файлов, 10 - 100 КБ каждый.

Первая группа файлов - открытые, нешифрованные (doc, html, txt)
Энтропия
62,6 59,6 66,8 63,1 66,3
хи2
90 345,9 44,3 615,7 92,1
Дюрбан-Ватсон
0,52 0,44 0,3 0,54 0,43

Вторая группа файлов - открытые, сжатые (zip, 7z, pdf, jpeg)
Энтропия
99.7 94.3 99.6 99.4 99.1
хи2
12.44 298 5.75 1.38 2.6
Дюрбан-Ватсон
0.998 0.77 0.98 0.95 1.02

Третья группа файлов - шифрованные, сжатые (zip, 7z, rar, pgd без заголовка)
Энтропия
99.5 99.7 99.6 99.7 99.7
хи2
1.03 1.35 1.8 0.92 1.1
Дюрбан-Ватсон
0.98 0.97 1.004 0.98 0.98

Выводы:
1 - высокая энтропия говорит о низкой избыточности, т.е. наличии сжатия/шифрования
2 - значение критерия хи2 близко к 1 для шифрованного текста и может быть близко к 1 с некоторой вероятностью для сжатого текста
3 - значение критерия ДВ близко к 1 для шифрованного текста и может быть близко к 1 с некоторой вероятностью для сжатого текста

Будьте добры, поправьте или уточните мои выводы
  #8  
Старый 02.03.2010, 16:48
гость

 
Сообщений: n/a

Не забывайте только, что критерий ДВ был принудительно поделен на два для экономии мышления. по науке он должен быть равен 2.00 для случайных данных.
  #9  
Старый 02.03.2010, 17:23
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Сообщение от гость
Не забывайте только, что критерий ДВ был принудительно поделен на два для экономии мышления. по науке он должен быть равен 2.00 для случайных данных.
Допустим d = 2(1-p), где d - значение критерия, p — коэффициент автокорреляции первого порядка.

То при p = 0 (отсутствия автокорреляции) получаем d = 2. В случае нормирования к 1, критерий ДВ для шифртекста должен стремится к 1.
Я прав? Если да, то эксперимент подтвердил теорию
  #10  
Старый 02.03.2010, 18:18
Новичок

Отправить личное сообщение для astramax Посмотреть профиль Найти все сообщения от astramax
 
Регистрация: 01.03.2010
Сообщений: 8

Итак, чтобы определить шифртекст, нужно оценить (1) вероятность появления 0 и 1 и (2) степень зависимости последующего бита от предыдущих.
(1) оцениваем величиной энтропии (чем выше энтропия, тем выше вероятность зашифрованности данных)
(2) оцениваем уровнем автокорелляции битовой последовательности с помощью критерия ДВ.

Вопрос: как правильно использовать хи2? Ведь (далее из Вики) критерий хи2 - статистический критерий для проверки гипотезы H_0, что наблюдаемая случайная величина подчиняется некому теоретическому закону распределения. Для шифрованных данных распределение битов 0 и 1 должно быть подчинено дискретному равномерному распределению, насколько я понимаю. Как проверить фактическое распределение, опираясь на полученные результаты эксперимента?
В матстатистике, ТВ и прочих науках я не особо силен
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра