Эффективные методы построения идеальных криптографических систем защиты информации
Диссертация
Основным способом построения невскрываемых шифров при использовании коротких ключей является кодирование сообщений перед шифрованием. Можно выделить два основных подхода к такому кодированию. Первый заключается в применении традиционного сжатия данных для уменьшения избыточности сообщения и, следовательно, увеличения расстояния единственности шифра. Особенностью этого подхода является то, что… Читать ещё >
Содержание
- 1. Методы эффективного кодирования для повышения расстояния единственности шифров
- 1. 1. Введение
- 1. 2. Теория систем с совершенной секретностью
- 1. 3. Соотношение избыточностей по входу и выходу
- 1. 4. Основные подходы к потроению метода эффективного кодирования
- 1. 4. 1. Быстрое кодирование с использованием скользящего окна
- 1. 4. 2. Использование мнимого скользящего окна для уменьшения объема памяти кодера и декодера
- 1. 4. 3. Кодирование марковских источников
- 1. 4. 4. Избыточность арифметического кодирования
- 2. 1. Обзор побуквенных омофонных кодов
- 2. 2. Арифметическое кодирование с разделением интервала
- 2. 2. 1. Основная идея метода
- 2. 2. 2. Описание алгоритма кодирования
- 2. 2. 3. Свойства метода
- 2. 3. Арифметическое кодирование с фиктивным символом
- 2. 3. 1. Описание алгоритма
- 2. 3. 2. Оценка избыточности по входу. щ 2.3.3. Потребление внешних случайных бит
- 2. 3. 4. Вычислительная сложность метода
- 3. 1. Задачи, возникающие при использовании физических генераторов случайных чисел
- 3. 2. Эффективная нумерация множеств
- 3. 2. 1. Постановка задачи
- 3. 2. 2. Нумерация сочетаний
- 3. 2. 3. Быстрый алгоритм нумерации сочетаний
- 3. 3. Эффективная генерация произвольно распределенных случай®- ных величин
- 3. 3. 1. Постановка задачи
- 3. 3. 2. Быстрая генерация случайных величин для омофонных кодеров
- 3. 3. 3. Генерация случайных величин на основе омофонного декодирования щ 3.3.4. Уменьшение числа случайных бит, используемых в омофонном кодировании
- 3. 3. 5. Эффективное преобразование вероятностностных распределений
- 4. 1. Основные определения и постановка задачи
- 4. 2. Конструкция идеальной криптосистемы на базе нумерационного кода
- 4. 2. 1. Основная идея и свойства метода. а 4.2.2. Описание общего алгоритма и его свойства
- 4. 3. Построение строго идеальной системы на базе универсального омофонного кода
- 4. 3. 1. Введение
- 4. 3. 2. Основная идея
- 4. 3. 3. Общая конструкция строго идеальной системы
- 5. 1. Тесты для проверки генераторов случайных и псевдослучайных чисел
- 5. 1. 1. Тест «Стопка книг»
- 5. 1. 2. Порядковый тест
- 5. 1. 3. Экспериментальные исследования
- 5. 2. Статистическая атака на блоковые шифры
Список литературы
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. — 383 с.
- Бабкин В. Ф. Метод универсального кодирования независимых сообщений неэкспоненциальной трудоемкости // Проблемы передачи информации. 1971. — Т. 7, № 4. — С. 13−21.
- Введение в криптографию / Под общ. ред. В. В. Ященко. М.: МЦНМО: «ЧеРо», 2000. — 287 с.
- Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974. — 425 с.
- ГОСТ 28 147–89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования данных.
- Кнут Д. Искусство программирования для ЭВМ. В 3-х томах. Т. 2. Получисленные алгоритмы. М.: Мир, 1977. — 724 с.
- Кричевский Р. Е. Оптимальное кодирование источника на основе наблюдений // Проблемы передачи информации. 1975. — Т. 11, № 4. — С. 37−42.
- Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.
- Рябко Б. Я. Сжатие данных с помощью стопки книг // Проблемы передачи информации. 1980. — Т. 16, № 4. — С. 16−21.
- Рябко Б. Я. Быстрый алгоритм адаптивного кодирования // Проблемы передачи информации. 1990. — Т. 26, № 4. — С. 24−37.
- Рябко Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Проблемы передачи информации. 1995. — Т. 31, № 1. — С. 3−12.
- Рябко Б. Я. Сжатие данных с помощью «мнимого скользящего окна» // Проблемы передачи информации. 1996. — Т. 32, № 2. — С. 22−30.
- Рябко Б. Я. Быстрая нумерация комбинаторных объектов // Дискретная математика. 1998. — Т. 10, № 2. — С. 101−119.
- Рябко Б. Я. Просто реализуемая идеальная криптографическая система // Проблемы передачи информации. 2000. — Т. 36, № 1. — С. 90−104.
- Рябко Б. Я., Пестунов А. И. «Стопка книг» как новый статистический тест для случайных чисел // Проблемы передачи информации. -2004. Т. 40, № 1. — С. 73−78.
- Рябко Б. Я., Стогниенко В. С., Шокин Ю. И. Адаптивный критерий хи-квадрат для различения близких гипотез при большом числе классов и его применение к некоторым задачам криптографии // Проблемы передачи информации. 2003. — Т. 30, № 2. — С. 53−62.
- Трофимов В. К. Избыточность универсального кодирования произвольных марковских источников // Проблемы передачи информации. -1974. Т. 10, № 4. — С. 16−24. .
- Феллер В. Введение в теорию вероятностей и ее приложения. В 2-х томах. М.: Мир, 1984. — Т 1. — 527 с.
- Фитингоф Б. М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений // Проблемы передачи информации. 1966. -Т. 2, № 2.-С. 3−11.
- Шеннон К. Работы по теории информации и кибернетике. М.: ИЛ, 1963. — С. 333−369 (Теория связи в секретных системах).
- Штарьков Ю. М. Универсальное последовательное кодирование отдельных сообщений // Проблемы передачи информации. 1987. — Т. 23, № 3. — С. 3−17.
- Штарьков Ю. М. Некоторые теоретико-информационные задачи защиты дискретных данных // Проблемы передачи информации. 1994. -Т. 30, № 2. — С. 49−60.
- Abrahams J. Generation of discrete distributions from biased coins // IEEE Transactions on Information Theory. 1996. — V. 42, № 5. — P. 1541−1546.
- Ahlswede R. Remarks on Shannon’s secrecy systems // Problems of Control and Information Theory. 1982. — V. 11, № 4. — P. 301−318.
- Bell Т. C., Cleary J. G., Witten I. H. Text compression. Englewood Cliffs, NJ: Prentice Hall, Inc. — 1990.
- Bentley J. L., Sleator D. D., Tarjan R. E. Wei V. K. A locally adaptive data compression scheme // Communications of the ACM. 1986. — V. 29, № 4. — P. 320−330.
- Cleary J. G., Witten I. H. Data compression using adaptive coding and partial string matching // IEEE Transactions on Communications. 1984. -V. 32, № 4. — P. 396−402.
- Cleary J. G., Witten I. H. A comparison of enumerative and adaptive codes // IEEE TYansactions on Information Theory. 1984. — V. 30, № 2. -P. 306−315.
- Cover Т. M. Enumerative source encoding // IEEE Transactions on Information Theory. 1973. — V. 19, № 1. — P. 73−77.
- Daemen J., Rijmen V. The Rijndael Block Cipher, см. http://csrc.nist.gov/encryption/aes/rijndael/.
- Elias P. Minimax optimal universal codeword sets // Transactions of the IEEE. 1983. — V. 29, № 4. — P. 491−502.
- Elias P. Interval and recency rank source encoding: two on-line adaptive variable-length schemes // TYansactions of the IEEE. 1987. — V. 33M. — P. 3−10.
- FIPS 197. Advanced encryption standard, см. http://csrc.nist.gov/publications/.
- Fitingof В., Waksman Z. Fuzed trees and some new approaches to source coding // IEEE TYansactions on Information Theory. 1988. V. 34, № 3. -P. 417−424.
- Gehrmann Ch. An adaptive homophonic algorithm // 1993 IEEE Internationsl Symposium on Information Theory (ISIT 1993). San Antonio, 1993. — P. 280.
- Gehrmann Ch. Remarks on theoretical treatments of secrecy systems // 7th Joint Swedish-Russian International Workshop on Information Theory. -St. Petersburg, June 1995. P. 84−88.
- Goldwasser S., Bellare M. Lecture notes on cryptography, http://www-cse.ucsd.edu/users/mihir/crypto-lecnotes.html
- Guazzo М. A general minimum-redundancy source-coding algorithm // IEEE Transactions on Information Theory. 1980. — V. 26, № 1. — P. 1525.
- Gunther Ch. G. A universal algorithm for homophonic coding // Advances in Cryptology Eurocrypt-88. Heidelberg and New York: Springer-Verlag, 1988. — P. 405−414 (Lecture Notes in Computer Science- V. 330).
- Han T. S., Hoshi M. Interval algorithm for random number generation // IEEE Transactions on Information Theory. 1997. — V. 43, № 2. — P. 599−611.
- Jelinek F. Probabilistic information theory. New York: McGraw-Hill, 1968. — P. 476−489.
- Jendal H. N., Kuhn Y. J. В., Massey J. L. An information-theoretic treatment of homophonic substitution // Advances in Cryptology Eurocrypt-89. Berlin: Springer-Verlag, 1990. — P. 382−394 (Lecture Notes in Computer Science- V. 434).
- Knuth D. E., Yao A. C. The complexity of nonuniform random number generation // Algorithms and Complexity: New Directions and Results, J. F. Traub Ed. New York: Academic Press, 1976. — P. 357−248.
- Krichevsky R. Universal Compression and Retrieval. Dordrecht: Kluwer Academic Publishers, 1994.
- Krichevsky R. E., Trofimov V. K. The performance of universal encoding // IEEE Transactions on Information Theory. 1981. — V. 27, № 2. — P. 199 207.
- Langdon G. G., Rissanen J. A simple general binary source code // IEEE Transactions on Information Theory. 1982. — V. 28, № 9. — P. 800−803.
- Langdon G. G. An introduction to arithmetic coding // IBM J. Res. Dev. 1984. — V. 28, № 2. — P. 135−149.
- Massey J. L. An introduction to contemporary cryptology // Proceedings of the IEEE. 1988. — V. 76. — P. 533−549.
- Massey J. L. Some applications of source coding in cryptography // European Transactions on Telecommunications. 1994. — V. 5. — P. 421−429.
- Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. — 661 p. http://www.cacr.math.uwaterloo.ca/hac/.
- Moffat A. A note on the PPM data compression algorithm. Res. Rep. 88/7, Dep. Comput. Sci. Univ. of Melbourne. Australia, 1988.
- Moffat A., Turpin A. Efficient construction of minimum-redundancy codes for large alphabets // IEEE Transactions on Information Theory. 1998. -V. 44, № 4. — P. 1650−1657.
- Moffat A., Neal R. M., Witten I. H. Arithmetic coding revisited // ACM Transactions on Information Systems. 1998. — V. 16, № 3. — P. 256−294.
- Nisan N., Ta-Shma A. Extracting randomness: a survey and new constructions // Journal of Computing and System Science. 1999. V. 58, № 1. — P. 148−173.
- Nisan N., Zuckerman D. Randomness is linear in space // Journal of Computing and System Science. 1996. — V. 52, № 1. — P. 43−52.
- Rissanen J. J. Generalized Kraft inequality and arithmetic coding // IBM J. Res. Dev. 1976. — V. 20. — P. 198−203.
- Rissanen J. J., Langdon G. G. Arithmetic coding // IBM J. Res. Dev. -1979. V. 23, №. — P. 149−162.
- Rissanen J., Langdon G. G. Universal modeling and coding // IEEE
- Transactions on Information Theory. 1981. — V. 27, № 1. — P. 12−23.
- Roche J. R. Efficient generation of random variables from biased coins // 1991 IEEE International Symposium on Information Theory (ISIT 1991). -P. 169.
- Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Transactions on Information Theory. 1979. — V. 2, № 6. — P. 672−675.
- Rukhin A. et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications // NIST Special Publication 800−22 (rev. May, 15,2001). http://csrc.nist.gov/rng/SP800−22b.pdf.
- Ryabko В. Y. Fast and effective coding of information sources // IEEE Transactions on Information Theory. 1994. — V. 40, № 1. — P. 96−99.
- Ryabko B. The simple ideal cipher system // 2000 IEEE International Symposium on Information Theory (ISIT 2000). Sorrento, Italy, June 2000. — P. 240.
- Ryabko В., Matchikina E. Fast and efficient construction of an unbiased random sequence // IEEE Transactions on Information Theory. 2000. — V. 46, N 3. — P. 1090−1093.
- Ryabko B. Ya., Monarev V. A. Using information theory approach to randomness testing // Journal of Statistical Planning and Inference. 2005.
- Ryabko В., Rissanen J. Fast adaptive arithmetic code for large alphabet sources with asymmetrical distributions // IEEE Communications Letters. -2003.-V. 7, № l.-P. 33−35.
- Schneier B. Self-study course in block cipher cryptanalysis // Cryptologia. 2000. — V. 24, N. 1. — P. 18−34. http://www.counterpane.com/self-study.html.
- Shannon C. Communication theory of secrecy systems // Bell System Technical Journal. 1949. — V. 28, № 4. — P. 656−715.
- Simmons G. J. Cryptology // Encyclopaedia Britannica. ed. 16. Chicago, IL: Encyclopaedia Britannica Inc. — 1986. — P. 913−924.
- Shtarkov Y. М., Babkin V. F. Combinatorial encoding for discrete stationary sources // 1973 IEEE International Symposium on Information Theory. Budapest, 1973. — P. 249−257.
- Willems F. M. J., Shtarkov Y. M., Tjalkens T. J. The context-tree weighting method: Basic properties // IEEE Transactions on Information Theory. 1995. — V. 41, № 3. — P. 653−664.
- Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Communications of the ACM. 1987. — V. 30, № 6. — P. 520−540.
- Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory. 1977. — V. 23, № 3. — P. 337−343.
- Ziv J., Lempel A. Compression of individual sequences via variable-rate coding // IEEE Transactions on Information Theory. 1978. — V. 24, № 5. -P. 530−536.
- Работы автора, в которых изложены основные результаты диссертации1. Монографии
- Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях. М.: Научный мир, 2004.- 173 с.
- Статьи и доклады на конференциях
- Ryabko В. Y., Fionov А. N. A fast and efficient homophonic coding algorithm // Algorithms and Computation. Berlin: Springer, 1996. — P. 427−438 (Lecture Notes in Computer Science- V. 1178).
- Фионов A.H. Быстрый метод полной рандомизации сообщений // Российская научно-техн. конф. «Информатика и проблемы телекоммуникаций». Новосибирск, 1996. — Т. 1. — С. 70.
- Фионов А. Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. — Т. 4, № 2. — С. 51−74.
- Рябко Б. Я., Федотов А. М., Фионов А. Н. Надежные системы защиты электронных публикаций, базирующиеся на эффективном омо-фонном кодировании // Вычислительные технологии. 1997. — Т. 2, № 3.- С. 68−72.
- Фионов А. Н. Эффективная рандомизация сообщений на основе арифметического кодирования // Международная научно-техн. конф. «Информатика и проблемы телекоммуникаций». Новосибирск, 1997. — С. 157−158.
- Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. Berlin: Springer, 1997. P. 253−262 (Lecture Notes in Computer Science- V. 1350).
- Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Проблемы передачи информации. 1997. — Т. 33, № 3. — С. 3−14.
- Ryabko В., Fionov A. Decreasing redundancy of homophonic coding // 1997 IEEE International Symposium on Information Theory (ISIT 1997). -Ulm, Germany, July 1997. P. 94.
- Рябко Б. Я., Федотов А. М., Фионов А. Н. Современные средства криптографической защиты информации в сетях передачи данных // Международная конф. «Современные информационные технологии». -Новосибирск, 1998. С. 42−44.
- Рябко Б. Я., Фионов А. Н., Федотов А. М. Конфиденциальность взаимодействий в открытых информационных сетях // Международный семинар «Перспективы развития современных средств и систем телекоммуникаций». Новосибирск, 1998. — С. 38−42.
- Fionov А. N. Computationally efficient randomization of messages // Международная Сибирская конф. по исслед. операций. Новосибирск, 1998. — С. 159.
- Ryabko В. Ya., Fionov А. N. Efficient algorithm of adaptive arithmetic coding // Международная Сибирская конф. по исслед. операций. Новосибирск, 1998. — С. 151.
- Fionov А. N. Using homophonic decoding for random number generation // Международный семинар «Распределенная обработка информации». -Новосибирск, 1998. С. 63−67.
- Ryabko В., Fionov A. Fast homophonic coding with logarithmic memory size // 1998 IEEE International Symposium on Information Theory (ISIT 1998). Cambridge, MA, USA, August 1998. — P. 52.
- Ryabko В., Fionov A. Efficient homophonic coding // IEEE Transactions on Information Theory. 1999. — V. 45, N. 6. — P. 2083−2091.
- Рябко Б. Я., Фионов А. Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. 1999. — Т. 35, № 4. — С. 1−14.
- Ryabko В., Fionov A. Fast and space-efficient adaptive arithmetic coding // Cryptography and Coding. Berlin: Springer, 1999. — P. 270−279 (Lecture Notes in Computer Science- V. 1746).
- Фионов A. H. Составные коды для криптосистем // Международный семинар «Перспективы развития современных средств и систем телекоммуникаций». Новосибирск, 2000. — С. 74−79.
- Fionov A. Random number generation via homophonic coding // 2000 IEEE International Symposium on Information Theory (ISIT 2000). Sorrento, Italy, June 25−30, 2000. — P. 354.
- Фионов A.H. Стойкий потоковый шифр на базе рандомизированных кодов // Международная научно-техн. конф. «Информатика и проблемы телекоммуникаций». Новосибирск, 2001. — С. 40−41.
- Fionov A. Universal homophonic coding // 2001 IEEE International Symposium on Information Theory (ISIT 2001). Washington, DC, USA, June 24−29, 2001. — P. 116.
- Ryabko В., Fionov A. Efficient algorithm for strongly ideal cipher // Workshop on Computer Science and Information Technologies (CSIT 2001). Ufa, Russia, 2001.
- Ryabko В., Fionov A. Adaptive arithmetic coding for changing statistics: randomization vs space // 2002 IEEE International Symposium on Information Theory (ISIT 2002). Lausanne, Switzerland, June 24 — June 29, 2002. — P. 116.
- Фионов A. H. Построение омофонных кодов при неизвестной статистике источника сообщений // Международный семинар «Перспективы развития современных средств и систем телекоммуникаций». Санкт-Петербург, 30 июня — 4 июля, 2002. — С. 83−86.
- Ryabko В., Fionov A. Efficient algorithm for strongly ideal cipher // 2nd IMA Conference on Mathematics in Communication. Lancaster University, UK, 16−18 December 2002.
- Рябко Б. Я., Фионов А. Н. Перспективы применения криптографических систем // Электросвязь. 2003. — № 8. — С. 28−31.
- Fionov A. Arithmetic homophonic coding with dummy symbols // 2004 IEEE International Symposium on Information Theory (ISIT 2004). -Chicago, Illinois, USA, June 27 July 2, 2004. — P. 129.
- Ryabko B. Ya., Fionov A. N., Monarev V. A., Shokin Yu. I.
- Using information theory approach to randomness testing // 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. Stuttgart, Germany, March 14 — 16, 2005. -http://www.hlrs.de.