ТПСГ

Тема

Лекции ​

Лекционный раздел собран из методического пособия по генераторам псевдослучайных чисел. Материал идет от математической базы к алгоритмам, криптографической стойкости и статистическому тестированию.

ВведениеОткрыть раздел лекционного курса.Арифметика в конечных поляхОткрыть раздел лекционного курса.Структура генератора ПСЧОткрыть раздел лекционного курса.Алгоритмы генерации ПСЧОткрыть раздел лекционного курса.Криптографически стойкие ГПСЧОткрыть раздел лекционного курса.Тестирование статистических свойствОткрыть раздел лекционного курса.Преобразование к распределениямОткрыть раздел лекционного курса.

Рекомендуемый порядок ​

  1. Начните с введения и арифметики в конечных полях.
  2. Разберите структуру генератора и основные классы алгоритмов.
  3. Перейдите к криптографически стойким генераторам.
  4. Завершите статистическими критериями и преобразованием распределений.

Список источников ​

  1. Дональд Кнут. Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
  2. The RAND Corporation (Author). A Million Random Digits with 100,000 Normal Deviates Paperback – October 23, 2001.
  3. A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications).
  4. Intel® Digital Random Number Digital Random Number Generator Generator(DRNG). Software Implementation Guide. Revision 1.1. August 7, 2012. [Электронный ресурс]. – Режим доступа: https://software.intel.com/sites/default/files/m/d/4/1/d/8/441_Intel_R__DRNG_Software_Implementation_Guide_final_Aug7.pdf. Дата 29.07.2016.
  5. Аппаратный генератор случайных чисел ГСЧ-6. [Электронный ресурс]. – Режим доступа: http://tegir.ru/ml/k66.html. Проверено 29.07.2016.
  6. ГОСТ Р ИСО 28640-2012. [Электронный ресурс]. – Режим доступа: http://files.stroyinf.ru/cgi-bin/ecat/ecat.fcgi?b=0&i=53898&pr=1. Проверено 29.07.2016.
  7. http://www.noisecom.com. [Электронный ресурс]. – Режим доступа: Проверено 29.07.2016.
  8. Шнайер Б. 14.1 Алгоритм ГОСТ 28147-89 // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 373-377.
  9. Barker E., Kelsey J. NIST Special Publication 800-90A. Recommendation for Random Number Generation Using Deterministic Random Bit Generators.
  10. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с.
  11. Lock-in effect in cascades of clock-controlled shift-registers. In Christoph G. Gunther, editor, Advances in Cryptology—EUROCRYPT 88, volume 330 of Lecture Notes in Computer Science, pages 331–344.
  12. G. Mayhew, R. Frazee, and M. Bianco, “Kinetic Protection Device”, Proceedings of the 15th National Computer Security Conference, NIST, 1994, pp. 147-154.
  13. Ross J. Anderson. On Fibonacci Keystream Generators [Электронный ресурс]. – Режим доступа: http://www.iacr.org/cryptodb/data/paper.php?pubkey=2963. Заглавие с экрана. Проверено 20.07.2016.
  14. Н. Смарт. Криптография. – Москва: Техносфера, 2005. 528 с. ISBN 5-94836-043-1.
  15. Recommendation for Block Cipher Modes of Operation. NIST Special Publication 800-38A. Technology Administration U.S. Department of Commerce. 2001 Edition.
  16. S. Wolfram, “Random Sequence generation by Cellular Automata”, Advances in Applied Mathematics, v. 7, 1986, pp.123-164.
  17. W. Meier and O. Staffelbach, “Fast Correlation Attack on Stream Ciphers”, Journal of Cryptology v I n. 3, 1989, pp.159-176.
  18. P.H. Bardell, “Analisis of Cellular Automata Used as Pseudorandom Pattern generators”, Proceedings of 1990 International Test Conference, pp. 762-768.
  19. A. Shamir. «On the generation of cryptographically strong pseudorandom sequences». Journal: ACM Transactions on Computer Systems - TOCS, vol. 1, no. 1, pp. 38-44, 1983.
  20. Lenore Blum, Manuel Blum, and Michael Shub. «A Simple Unpredictable Pseudo-Random Number Generator», SIAM Journal on Computing, volume 15, pages 364—383, May 1986.
  21. C. Borrelli. IEEE 802.3 Cyclic Redundancy Check. [Электронный ресурс]. – Режим доступа: http://www.xilinx.com/support/documentation/application_notes/xapp209.pdf. Проверено 20.08.2015.
  22. RFC 1320 - The MD4 Message-Digest Algorithm. [Электронный ресурс]. – Режим доступа: http://www.faqs.org/rfcs/rfc1320.html. Проверено 29.07.2016.
  23. RFC 1321 - The MD5 Message-Digest Algorithm. [Электронный ресурс]. – Режим доступа: https://tools.ietf.org/html/rfc1321. Проверено 29.07.2016.
  24. Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. [Электронный ресурс]. – Режим доступа: http://eprint.iacr.org/2004/199. Проверено 29.07.2016.
  25. ГОСТ Р 34.11-2012: функция хеширования «Стрибог». [Электронный ресурс]. – Режим доступа: https://www.streebog.net/ru/. Проверено 21.07.2016.
  26. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования. [Электронный ресурс]. – Режим доступа: http://protect.gost.ru/document.aspx?control=7&id=180209. Проверено 20.08.2015.
  27. O. Kazymyrov, V. Kazymyrova. Algebraic Aspects of the Russian Hash Standard GOST R 34.11-2012. [Электронный ресурс]. – Режим доступа: http://eprint.iacr.org/2013/556.pdf. Проверено 20.08.2015.
  28. Р 50.1.033–2001. Рекомендации по стандартизации. Прикладная статистика. Правила проверки согласия опытного распределения с теоретическим. Часть I. Критерии типа хи-квадрат. – М.: Изд-во стандартов. 2002. – 87 с.
  29. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. [Электронный ресурс]. – Режим доступа: http://protect.gost.ru/document.aspx?control=7&id=139177. Проверено 29.07.2016.
  30. Большев Л. Н., "Теория вероятностей и ее применения", 1963, т. 8, в. 2, с. 129-55.
  31. NIST Statistical Test Suite. [Электронный ресурс]. – Режим доступа: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html. Проверено 23.08.2015.
  32. TEST-U01. [Электронный ресурс]. – Режим доступа: http://www.iro.umontreal.ca/~simardr/testu01/tu01.html. Проверено 23.08.2014.
  33. CRYPT-X. [Электронный ресурс]. – Режим доступа: http://www.isi.qut.edu.au/resources/cryptx. Проверено 23.08.2015.
  34. The pLab Project. [Электронный ресурс]. – Режим доступа: http://random.mat.sbg.ac.at. Проверено 23.08.2015.
  35. George Marsaglia, DIEHARD Statistical Tests. [Электронный ресурс]. – Режим доступа: http://stat.fsu.edu/~geo/diehard.html. Проверено 23.08.2014.
  36. ENT. [Электронный ресурс]. – Режим доступа: http://www.fourmilab.ch/random/. Проверено 23.08.2015.
  37. Официальный сайт StatSoft Russia. [Электронный ресурс]. – Режим доступа. http://www.statsoft.ru. Проверено 23.08.2014.
  38. Официальный сайт программы MathLab. [Электронный ресурс]. – Режим доступа. http://matlab.ru/. Проверено 23.08.2014.
  39. Robert G. Brown's General Tools Page. [Электронный ресурс]. – Режим доступа. http://www.phy.duke.edu/~rgb/General/dieharder.php. Проверено 23.08.2014.
  40. A. Rukhin, J. Soto, and others. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. [Электронный ресурс]. – Режим доступа: http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf. Проверено 25.08.2014.
  41. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
  42. J.A. Reeds, “Solution of Challenge Cipher”, Cryptologia, v.3, n.2, Apr 1979, pp. 83-95.
  43. J.B. Plumstead, “Inferring a Sequence generated by a Linear Congruence”, Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science, 1982, pp. 153-159.
  44. Alex Biryukov, Adi Shamir, "Real Time Cryptanalysis of the Alleged A5/1 on a PC (preliminary draft)". [Электронный ресурс]. – Режим доступа: http://cryptome.org/a51-bsw.htm. Проверено 05.01.2015.
  45. Vlastimil Klima. “Tunnels in Hash Functions: MD5 Collisions Within a Minute”. [Электронный ресурс]. – Режим доступа: http://eprint.iacr.org/2006/105. Проверено 06.01.2015.
  46. Turing A. Programmers' Handbook for the Manchester Electronic Computer Mark II. — 1952. — С. 25. — 110 с.
  47. Eichenauer J., Lehn J. A non-linear congruential pseudo random number generator // Statistische Hefte — Springer Berlin Heidelberg, 1986. — Vol. 27, Iss. 1. — P. 315—326. — ISSN 0932-5026 — doi:10.1007/BF02932576
  48. Eichenauer-Herrmannn J., Grothe H., Niederreiter H. et al. On the lattice structure of a nonlinear generator with modulus 2ᵅ // J. Comput. Appl. Math. — 1990. — Vol. 31, Iss. 1. — P. 81—85. — ISSN 0377-0427 — doi:10.1016/0377-0427(90)90338-Z
  49. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последователеьностей. – М.: КУДИЦ-ОБРАЗ, 2003. – 240 с. (СКБ – специалисту по компьютерной безопасности).
  50. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. – М.: Мир. — 1989.
  51. Берлекэмп Э. Алгебраическая теория кодирования. = Algebraic Coding Theory. – М.: Мир, 1971.
  52. Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — 430 с.
  53. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: Мир, 1976.
  54. N.Zierler, Brillhart J., On primitive trinomial (mod 2), Inform. Control 13 (1968), 541-554.
  55. C.G. Gunter, “Alternating Step Generators Contolled by de Bruijn Sequences”, Advances in Cryptology EUROCRYPT ’87 Proceedings, Springer-Verlag, 1988, pp. 5-14.
  56. D. Gollmann, “Kaskadenschaltungen takt gesteuerter Schicberegister als Pseudozu fallszahlengencratoren”, Ph.D. dissertation Universitat Linz, 1983.

Автор курса: Слеповичев Иван Иванович