Аппроксимация распределений частот буквенных биграмм текста для идентификации букв
Ключевые слова:
аппроксимация, идентификация, буква, биграмма, простая замена, шифрАннотация
В статье рассмотрены особенности применения методов частотного упорядочивания и аппроксимации для решения задачи идентификации знаков текста. Определены условия реализации метода Якобсена для получения наименьшей погрешности идентификации. Предложен метод аппроксимации одномерных и двумерных распределений частот знаковых биграмм текста и буквенных биграмм эталона языка текста. Приведены экспериментальные данные о погрешностях метода Якобсена и предложенного метода аппроксимации для русскоязычных текстов. Погрешность предложенного метода меньше, чем у метода Якобсена. Метод может быть использован для идентификации знаков текста любого языка, для которого существует эталонное распределение частот буквенных биграмм.Литература
1. Котов Ю.А. Детерминированная идентификация буквенных биграмм в русскоязычных текстах // Труды СПИИРАН. 2016. №1. С.181-197.
2. Шеннон К. Теория связи в секретных системах //Шеннон К. Работы по теории информации и кибернетике // М.: ИЛ. 1963. С. 333-369.
3. Бабенко Л.К., Ищукова Е.А., Маро Е.А., Сидоров И.Д., Кравченко П.П. Развитие криптографических методов и средств защиты информации // Известия ЮФУ. Технические науки. 2012. № 4. С.40-50.
4. Бабенко Л.К., Ищукова Е.А. Анализ симметричных криптосистем // Известия ЮФУ. Технические науки. 2012. № 12. С.136-147.
5. Глухов М.М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии // СПб.: Лань. 2011. 400 с.
6. Минеев М. П., Чубариков В. Н. Лекции по арифметическим вопросам криптографии // М.: Изд-во ≪Попечительский совет Механико-математического факультета МГУ им. М. В. Ломоносова≫. 2010. 186 с.
7. Jakobsen T. A fast Method for Cryptanalysis of Substitution Ciphers // Cryptologia. 1995. vol.19. no 3. pp. 265-274.
8. Corlett E. An Exact A* Method for Solving Letter Substition Ciphers //University of Toronto, 2011.-ftp://ftp.cs.toronto.edu/pub/gh/Corlett-MSc-2011.pdf.
9. SambasivaRao Baragada, P. Satyanarayana Reddy A Survey of Cryptanalytic Works Based on Genetic Algorithms // International Journal of Emerging Trends & Technology in Computer Science (IJETTCS). 2013. vol. 2. no. 5. pp. 18-22.
10. Amrit Pal Singh, Dr. S K. Pal and Dr. M P S Bhatia The Firefly Algorithm and Application in Cryptanalysis of Monoalphabetic Substitution Ciphers // American Journal of Computer Science and Engineering Survey. 2013. vol.1. no.1. pp. 33-52.
11. Морозенко В.В., Плешкова И.Ю. О применении генетического алгоритма для криптоанализа шифра Тритемия-Белазо-Виженера // Современные проблемы науки и образования: электронный научный журнал. 2014. № 2. С. 1-11.
12. Chen Jian, Rosenthal Jeffrey S. Decrypting classical cipher text using Markov chain Monte Carlo // Statistics and Computing. 2011. vol. 22. no. 2. pp. 397-413.
13. Aditi Bhateja, Shailender Kumar, Ashok K. Bhateja Cryptanalysis of Vigenere Cipher using Particle Swarm Optimization with Markov chain random walk // International Journal on Computer Science and Engineering (IJCSE). 2013. vol. 5. no. 5. pp. 422-429.
14. Васильев Е.М., Жданова Д.В. Диахроническое исследование энтропии графем русского письма // Вестник Воронежского государственного технического университета. 2010. № 4. С.1-3.
15. Васильев Е.М., Гусев К.Ю. Анализ избыточности русскоязычного текста // Вестник Воронежского государственного технического университета. 2010. № 8. С.1-4.
16. Жданов О. Н., Куденкова И. А. Криптоанализ классических шифров // Красноярск: Изд-во Сиб. гос. аэрокосм. ун-та им. акад. М.Ф. Решетнева. 2008. 107 с.
17. Maya Mohan, M. K. Kavitha Devi, V. Jeevan Prakash Security Analysis and Modification of Classical Encryption Scheme // Indian Journal of Science and Technology. 2015. vol. 8 no. 8. pp. 542–548.
18. Губарев В.В. Введение в теоретическую информатику // Новосибирск: Изд-во НГТУ. 2014. 420 с.
2. Шеннон К. Теория связи в секретных системах //Шеннон К. Работы по теории информации и кибернетике // М.: ИЛ. 1963. С. 333-369.
3. Бабенко Л.К., Ищукова Е.А., Маро Е.А., Сидоров И.Д., Кравченко П.П. Развитие криптографических методов и средств защиты информации // Известия ЮФУ. Технические науки. 2012. № 4. С.40-50.
4. Бабенко Л.К., Ищукова Е.А. Анализ симметричных криптосистем // Известия ЮФУ. Технические науки. 2012. № 12. С.136-147.
5. Глухов М.М., Круглов И.А., Пичкур А.Б., Черёмушкин А.В. Введение в теоретико-числовые методы криптографии // СПб.: Лань. 2011. 400 с.
6. Минеев М. П., Чубариков В. Н. Лекции по арифметическим вопросам криптографии // М.: Изд-во ≪Попечительский совет Механико-математического факультета МГУ им. М. В. Ломоносова≫. 2010. 186 с.
7. Jakobsen T. A fast Method for Cryptanalysis of Substitution Ciphers // Cryptologia. 1995. vol.19. no 3. pp. 265-274.
8. Corlett E. An Exact A* Method for Solving Letter Substition Ciphers //University of Toronto, 2011.-ftp://ftp.cs.toronto.edu/pub/gh/Corlett-MSc-2011.pdf.
9. SambasivaRao Baragada, P. Satyanarayana Reddy A Survey of Cryptanalytic Works Based on Genetic Algorithms // International Journal of Emerging Trends & Technology in Computer Science (IJETTCS). 2013. vol. 2. no. 5. pp. 18-22.
10. Amrit Pal Singh, Dr. S K. Pal and Dr. M P S Bhatia The Firefly Algorithm and Application in Cryptanalysis of Monoalphabetic Substitution Ciphers // American Journal of Computer Science and Engineering Survey. 2013. vol.1. no.1. pp. 33-52.
11. Морозенко В.В., Плешкова И.Ю. О применении генетического алгоритма для криптоанализа шифра Тритемия-Белазо-Виженера // Современные проблемы науки и образования: электронный научный журнал. 2014. № 2. С. 1-11.
12. Chen Jian, Rosenthal Jeffrey S. Decrypting classical cipher text using Markov chain Monte Carlo // Statistics and Computing. 2011. vol. 22. no. 2. pp. 397-413.
13. Aditi Bhateja, Shailender Kumar, Ashok K. Bhateja Cryptanalysis of Vigenere Cipher using Particle Swarm Optimization with Markov chain random walk // International Journal on Computer Science and Engineering (IJCSE). 2013. vol. 5. no. 5. pp. 422-429.
14. Васильев Е.М., Жданова Д.В. Диахроническое исследование энтропии графем русского письма // Вестник Воронежского государственного технического университета. 2010. № 4. С.1-3.
15. Васильев Е.М., Гусев К.Ю. Анализ избыточности русскоязычного текста // Вестник Воронежского государственного технического университета. 2010. № 8. С.1-4.
16. Жданов О. Н., Куденкова И. А. Криптоанализ классических шифров // Красноярск: Изд-во Сиб. гос. аэрокосм. ун-та им. акад. М.Ф. Решетнева. 2008. 107 с.
17. Maya Mohan, M. K. Kavitha Devi, V. Jeevan Prakash Security Analysis and Modification of Classical Encryption Scheme // Indian Journal of Science and Technology. 2015. vol. 8 no. 8. pp. 542–548.
18. Губарев В.В. Введение в теоретическую информатику // Новосибирск: Изд-во НГТУ. 2014. 420 с.
Approximation of Distributions of Text Characters Bigrams Frequencies for Alphabetic Characters Identification
Abstract
The article discusses the application features of methods of the frequencies ordering and approximation to solve the problem of text characters identification. The conditions for realization of Jacobsen’s method for receiving the least error of identification are defined. The method of approximation of one- and two-dimensional distributions of the frequencies of characters bigrams of the text and the language is offered. The experimental data about errors of Jacobsen’s method and the offered approximation method for Russian language texts are provided. The error of the offered method is less than that of Jacobsen's method. This method can be used for identification of text characters for any language that has a reference distribution of the alphabetic characters bigrams frequencies.
Опубликован
2017-02-02
Как цитировать
Котов, Ю. А. (2017). Аппроксимация распределений частот буквенных биграмм текста для идентификации букв. Труды СПИИРАН, 1(50), 190-208. https://doi.org/10.15622/sp.50.8
Раздел
Теоретическая и прикладная математика
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
