Разработка и экспериментальные исследования алгоритмов тестирования случайных чисел и их приложения к некоторым задачам криптографии тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Стогниенко, Владимир Сергеевич

• Стогниенко, Владимир Сергеевич
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Стогниенко, Владимир Сергеевич

Введение

Глава 1. Основные понятия и методы.

1.1. Основные определения и понятия.

1.2. Описание адаптивного критерия х*.

1.3. Необходимые сведения из математической статистики и вспомогательные результаты.

1.4. Адаптивный критерий хи-квадрат. Описание и теоретическое рассмотрение.

Глава 2. Экспериментальные исследования эффективных генераторов криптографически стойких псевдослучайных последовательностей созданных на основе современных алгоритмов шифрования.

2.1. Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на криптографических алгоритмах

Ф ЯС5 и ЯС6.

2.2. Экспериментальные исследования эффективности генераторов псевдослучайных чисел базирующихся на современных криптографических алгоритмах.

Глава 3. Экспериментальные исследования статистических свойств зашифрованных текстов на естественных языках и их применение к одной из задач криптографии

3.1 Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей

3.2 Алгоритм различения зашифрованных текстов на естественных языках и случайных последовательностей на длинах выборки от 100 килобайт

Введение диссертации (часть автореферата) на тему «Разработка и экспериментальные исследования алгоритмов тестирования случайных чисел и их приложения к некоторым задачам криптографии»

Актуальность темы*. Случайные и псевдослучайные числа широко используются в самых различных областях науки и техники. Они очень важны в математическом моделировании, в разработке численных методов, в программировании, криптографии и т. п. И если раньше ученые, нуждающиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно "как следует трясли" [10], то сейчас генератор случайных чисел встроен в любой компилятор и процессор компьютера. Например, Intel использует генератор случайных чисел в процессорах со второго полугодия 1999 года [7]. Однако, такие генераторы, как правило, недостаточно надежны для криптографических приложений. На создание удовлетворительных псевдослучайных последовательностей с помощью численных методов затрачена масса усилий. В литературе можно найти множество работ по генераторам псевдослучайных чисел, а также различные тесты на случайность (например [4], [11], [35]). Тем не менее, проблема получения псевдослучайных чисел и их тестирования все еще актуальна, особенно для криптографии [31], и поэтому находится в центре внимания многих исследователей [20], [25], [26].

В научно-технической литературе числа, полученные с помощью компьютера, называются псевдослучайными, мы же, в дальнейшем для краткости, в некоторых случаях будем называть их просто случайными или случайными последовательностями. Каждую последовательность случайных чисел, перед использованием, необходимо тщательно проверить. Для приложений и задач, в которых требуются действительно Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (колы проектов: 99-01-00586, 03-01-00495) и 1МТА5-00-738 "Эффективное кодирование источников информации и связанные проблемы". качественные" случайные числа, они проверяются специальным набором тестов. Формально генератор псевдослучайных чисел можно считать эффективным, если он проходит все известные статистические тесты. В связи с этим, статистические тесты важны и необходимы, также как и сами генераторы. Более того, генератор случайных чисел может считаться "идеальным" только до тех пор, пока не появится тест, доказывающий обратное и "время жизни" генератора может на этом остановиться.

Необходимо отметить что, по сравнению с другими задачами, криптографические приложения предъявляют к генераторам случайных последовательностей намного более строгие требования, чем, скажем, вычислительные задачи. "Криптографическая" случайность — это не просто статистическая случайность, хотя и включает ее. Чтобы псевдослучайная последовательность была криптографически стойкой, она должна обладать следующими свойствами: генерируемые последовательности проходят все статистические тесты и их символы должны быть непредсказуемы. В то же время, как и любой криптографический алгоритм, генераторы криптографически стойких случайных последовательностей служат объектами "вскрытия" или "взлома". Поэтому, экспериментальные исследования генераторов криптографически стойких случайных последовательностей, разработка эффективных алгоритмов и методов их тестирования, их устойчивость к "взлому", т. е. проверка качества получаемых последовательностей - важная задача криптографии [10], [23], [31].

Среди задач тестирования последовательностей "на случайность" особый интерес представляет задача различения статистическими методами зашифрованных текстов и случайных последовательностей. Разработка эффективных алгоритмов и методов распознавания, или различения зашифрованных текстов хорошо известна в криптографии (см., например, [10], [16], [34]). Решение этой задачи позволяет определить сам факт передачи по сетям связи (или хранения в информационных базах данных) зашифрованных текстов и, в силу этого, представляет несомненный интерес для разработчиков и исследователей систем защиты информации. Вместе с тем, трудность заключается в том, что современные шифры должны преобразовывать данные в последовательности, неотличимые от случайных настолько, насколько это возможно. Причем это одно из обязательных требований, предъявляемых к современным блоковым шифрам, — неотличимость зашифрованной последовательности от случайной, даже тогда, когда шифруемые данные заведомо не случайны. В частности, если на вход алгоритма шифрования подается текст на естественном языке, то на выходе он должен выглядеть как случайная последовательность. Заметим, что это условие предъявлялось Национальным институтом стандартов и технологии США (NIST) к блоковому шифру при организации конкурса на блоковый шифр 21-го века.

Как известно, для создания и хранения текстовой информации используются различные цифровые форматы (такие как "txt", "tex", "html", "doc", rtf"pdf'). В связи с этим, возникает вопрос о зависимости результата шифрования текста от формата, в котором он был представлен. Решение этой задачи представляет несомненный интерес для практической криптографии, разработчиков и исследователей систем защиты информации. Поэтому исследование влияния исходного формата шифруемых данных на возможность их различения в зашифрованном виде от случайных последовательностей важно с практической точки зрения.

Генерация "истинно" случайных чисел - одна из главных проблем возникающих при реализации любой криптосистемы. Огромное количество приложений уязвимо из-за предсказуемости генерируемых чисел. Однако уже более двадцати лет назад было опубликовано множество научной литературы по датчикам случайных чисел (например, [И], [17]). Позднее Дж. Клейнен в [12] приходит, однако, к выводу, что "все еще нет высококачественного генератора псевдослучайных чисел". Одновременно с ним известные специалисты Льюис [5] и Марсалья [21] указывают: "Многие широко распространенные генераторы фактически непригодны". Предостережение о распространенности плохих генераторов делает также И.М.Соболь в [6].

Вместе с тем, любое тестирование генераторов криптографически стойких случайных последовательностей остается частичным. Поэтому Ермаков С. М. и Михайлов Г. А. в [1] отмечают, что кроме специального статистического тестирования ". чрезвычайно важна проверка с помощью решения типовых задач, допускающих независимую оценку результатов аналитическими или численными методами. Можно сказать, что представление о надежности псевдослучайных чисел создается в процессе их использования с тщательной проверкой результатов всегда, когда это возможно".

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

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

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

2. Разработка и исследование эффективных численных методов, и алгоритмов различения зашифрованных текстов на естественных языках от случайных последовательностей.

3. Экспериментальное исследование влияния формы представления данных на возможность их различения в зашифрованном виде.

Методы исследования. В работе были использованы вычислительные эксперименты на ЭВМ, моделирование, математическая статистика и теория построения эффективных алгоритмов и программ.

Научная новизна результатов работы. В диссертации получены следующие новые результаты:

1. Проведены экспериментальные исследования нового статил стического критерия - "адаптивный критерий % показана целесообразность его применения для статистической проверки случайных последовательностей и даны практические рекомендации по его применению.

2. Предложен эффективный алгоритм статистической проверки "качества" криптографически стойких псевдослучайных последовательностей с помощью разработанного комплекса программ.

3. Впервые предложен метод различения зашифрованных текстов на естественных языках от случайных последовательностей, позволяющий, с помощью разработанного комплекса программ, различать зашифрованные тексты при сравнительно небольших объемах данных (от 100 килобайт и выше). Отметим, что для популярного статистического критерия %2 требуется для решения этой задачи в тысячи раз больший объем данных.

4. Исследовано влияние формата цифровых текстов (txt, rtf, doc, pdf) и их предварительного сжатия на возможность различения в зашифрованном виде на русском, английском и итальянском языках.

Практическая ценность.

1. Разработаны алгоритмы и программы для тестирования случайных и псевдослучайных последовательностей, эффективность которых существенно выше, чем у ранее известных.

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

3. Исследовано влияние формата цифровых текстов на естественных языках на возможность их различения в зашифрованном виде.

Апробация работы. Основные результаты диссертации докладывались на международных научных мероприятиях: международная конференция по теории информации ISIT-2003 (Yokohama, Japan, 2003), Китайско-российский форум молодых ученых в Пекине - 2003 г. (Пекин, НаиьЦзин, У си, Шан Хай, Китай, 2003), международная конференция Вычислительные технологии и математическое моделирование в науке, технике и образовании ВТММ-2002 (Алматы, Казахстан, 2002), Четвертое международное совещание по электронным публикациям Е1-РиЬ-99 (Новосибирск, 1999), а также на объединенных семинарах института вычислительных технологий СО РАН, кафедры математического моделирования НГУ, кафедры вычислительных технологий НГТУ.

Публикации. По теме диссертации автором опубликованы работы [38] - [43].

На защиту выносятся результаты экспериментальных исследований и совокупность вычислительных алгоритмов тестирования псевдослучайных и случайных чисел, в том числе и предназначенных для различения зашифрованных текстов.

Объем и структура диссертации. Диссертационная работа изложена на 119 страницах и состоит из введения, трех глав и заключения. Иллюстрационный материал включает 10 рисунков. Список литературы состоит из 43 наименований.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Стогниенко, Владимир Сергеевич

Заключение

В диссертации рассмотрена задача разработки и экспериментальных исследований алгоритмов тестирования случайных чисел и их приложение к некоторым задачам криптографии. Сформулируем основные результаты работы.

Проведенные исследования статистического критерия - "адапл тивный критерий % " показали целесообразность его применения для статистической проверки случайных последовательностей. Показано, что мощность нового метода - адаптивный критерий существенно выше, чем у традиционного критерия Пирсона и, что он более эффективен во многих приложениях, в частности связанных с криптографией, где объем доступной выборки, может быть ограничен.

На основе статистического адаптивного критерия £ разработаны алгоритмы и программы тестирования случайных и псевдослучайных чисел.

В работе найдено решение актуальной задачи различения зашифрованных текстов от случайных последовательностей, передаваемых по сетям связи (или хранимых в информационных базах данных), а именно: - в диссертации разработан и исследован метод различения зашифрованных текстов на естественных языках от случайных последовательностей, при небольших объемах данных. По сравнению с существующими аналогами, предложенный метод и алгоритмы позволяют решить эту задачу при длине последовательности от 100 килобайт.

Исследовано влияние формата цифровых текстов (txt, rtf, doc, pdf) на возможность их различения в зашифрованном виде на русском, английском и итальянском языках.

Исследованы датчики псевдослучайных чисел созданные на базе современных криптографических алгоритмов шифрования AES, Mars, RC6 и RC5. Показано, что алгоритм шифрования RC5 (без подбора входных данных) нельзя использовать для получения псевдослучайных чисел. Остальные три алгоритма шифрования можно использовать как генераторы псевдослучайных чисел для получения "качественной" криптографически стойкой случайной последовательности.

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

Список литературы диссертационного исследования кандидат технических наук Стогниенко, Владимир Сергеевич, 2004 год

1. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. -М.: Наука, 2-е издание, 1982.-290 с.

2. Кендалл М. Дж., Стьюарт А. Статистические выводы и связи. -М.: Наука, 1973.-899 с.

3. Клейнен Дж. Статистические методы в имитационном моделировании. В 2-х т. - М.: Статистика, 1978. — 221 е., 335 с.

4. Кнут Д., Искусство программирования для ЭВМ. М.: Мир, 1977.-Т. 2.-725 с.

5. Льюис Кэрролл, Логическая игра. М.: Наука - 1991

6. Соболь И.М., Численные методы Монте-Карло. М.: Наука, 1973 - гл.7.

7. Спунер Джон (John G. Spooner). Intel выдвигает комплексный план защиты ПК // PC Week Online, 28 января 1999 г.

8. Ферапонтов M. М. Моделирование случайных воздействий на ЭВМ. М.: Изд-во МТУ, 1995.

9. Шеннон К. Математическая теория связи // сб., Работы по теории информации и кибернетики. ИЛ., М:.

10. Шнайр Брюс, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2002.-816 е.: ил.

11. Beker H., Piper F. Cipher Systems: The Protection of Communications. London Northwood Books, 1982.

12. Cover T. M. and King R. C. A Convergent Gambling Estimate of the Entropy of English // IEEE Transactions on Information Theory. v. IT-24, n. 4.-Jul 1978.-pp. 413-421.

13. Cover T.M., Thomas J.A. Elements of Information Theory. Wiley. -New York, 1991.

14. Devroye L., Gyorfi L., Lugosi G. A probabilistic theory of pattern recognition. — New York : Springer, 1996.

15. Kendall M.G., Stuart A. The advanced theory of statistics; Vol.2: Inference and relationship. London, 1961.

16. Knudsen L. R., Meier W. Correlations in RC6. // 1999. -http://www.ii.uib.no/~larsr/papers/rc6.ps

17. Knuth D.E. The art of computer programming. // Vol.2. — Addison Wesley, 1981.

18. Lehmann E.L. Testing Statistical Hypotheses. Wiley. - New York, 1959.

19. L'Ecuyer P., Simard R. Beware of linear congruential generators with multipliers of the form a = ±28 ± 2r. ACM Trans. Model. Comput. Simul. 25(3), 1999. - pp.367-374.

20. Marsaglia George, The Marsaglia Random Number CDROM // http://stat.fsu.edu/~geo/

21. Marsaglia G., Bray C., On-Line Random Number Generators and their Use in Combinations. Communications of the ACM, v. 11, m 11, 1968-pp. 757-759.

22. Maurer U. A universal statistical test for random bit generators // Journal of Cryptology. v.5, n.2, 1992. - pp. 89-105.

23. Menezes A., P. van Oorshot, Vanstone S. Handbook of Applied Cryptography. CRC Press. - 1997. - P. 780.

24. Nechvatal J. and others. Report on the Development of the Advanced Encryption Standart (AES). 2000. // http://csrc.nist.gov/encryption/aes/round2/r2report.pdf

25. Park S. K., Miller K. W. Random Number Generators: Good Ones Are Hard to Find. // Communications of the ACM. v. 31, n. 10, Oct 1988.-pp. 1192-1201.

26. Peterson I. Monte Carlo Physics: A Cautionary Lesson. // Science News. v. 142, n. 25.- 19 Dec 1992.-p. 422.

27. Rivest R. L. The RC5 Encryption Algorithm. 1998. http://www.rsa.com

28. Rivest R. L. The RC5 encryption algorithm.//Proc. 2nd Workshop on Fast Software Encryption — Springer. 1995. p. 86-96

29. Rivest R. L., Robshaw M. J. B., Sidney R. et al. The RC6™ Block Cipher. Technology Square. 545. Cambridge, MA 02139, USA, 1998.

30. Rogaway Phillip. Software-Optimized Encryption Algorithm// J. CRYPTOLOGY. 1998. - N 11. - p. 273-287.

31. Rukhin A. and other. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Special Publication 800-22 (with revision dated May, 15, 2001) http://csrc.nist.gov/rng/SP800-22b.pdf

32. Schneier B. Applied Cryptography. Wiley, 1996.

33. Shannon C. E. Predication and Entropy in Printed English // Bell System Technical Journal. v. 30. - n. 1, 1951.- pp. 50-64.

34. Shimoyama T., Takeuchi K., Hayakawa J. Correlation Attack to the Block Cipher RC5 and the Simplified Variants of RC6 // Proceeding NIST Conference. 2000.

35. Soto J.,Bassham L. Randomness testing of the advanced encryption standard finalist candidates // In: Proceedings AES3, 2001, New-York. http://csrc.nist.gOv/encryption/aes/round2/conD/papers/3 0-jsoto.pdf

36. Vapnik V.N. The nature of statistical learning theory. New York : Springer, 1995.

37. Wegenkittl S., Matsumoto M. Getting rid of correlations among pseudorandom numbers: Discarding versus tempering. ACM Trails. Model. Comput. SimuL // 9 (3), 1999. pp. 282-294.m