Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 26
Текст из файла (страница 26)
1989. Vol. 52.P. 135-144.63. NIST SP 800-22. A Satistical Test Suite for Random and Pseudorandom Number Generators forCryprographicApplications:Rev.la // NIST.gov - Computer Security Division. 2010. 131 p. URL:http://csrc.nist.gov/publications/nistpubs/800-22-revla/SP800-22revla.pdf (дата обращения: 01.03.2011).64. NIST SP 800-38A.
Recommendation for block cipher modes of operation// NIST.gov-Computer Security Division. 2001. 66 p. URL: h t t p ://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf(дата обращения: 01.03.2011).65. Nyffeler P. Binare Automaten und ihre Linearen Rekursionen: Ph. D. dissertation. Bern: University of Bern, 1975. 113 s.66. Packard N., Wolfram S.
Two-dimensional cellular automata // Journal ofStatistical Physics. 1985. Vol. 38. P. 901-946.67. PreneelВ., deCanniere C. Triviumspecifications// The eS-TREAM Project. 2005. 7 p. URL: http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf (дата обращения: 01.03.2011).68. PublicationsbyStephenWolfram//StephenWolfram:OfficialWebsite. URL: http://www.stephenwolfram.com/publications (датаобращения: 01.03.2011).69. Random number generation // Wolfram Mathematica 8 Documentation.
URL: http://reference.wolfram.com/mathematica/tutorial/RandomNumberGeneration.html (дата обращения: 01.03.2011).70. Random.org —True Random Number Service [web site]. URL: h t t p : / /www.random.org (дата обращения: 01.03.2011).-17171. Rogawski M. Hardware evaluation of eSTREAM candidates: Grain,Lex, Mickeyl28, Salsa20 and Trivium // The eSTREAM Project. 2007.10 p.URL:http://www.ecrypt.eu.org/stream/papersdir/2007/025.pdf (дата обращения: 01.03.2011).72.
Shannon С. A mathematical theory of communication // The Bell SystemTechnical Journal. 1948. Vol. 27. P. 379-423, 623-656.73. Coppersmith D., Krawczyk H., Mansour Y. The shrinking generator// Lecture Notes in Computer Science. 1993. Vol. 773. P. 22-39.74. Smeets B. A note on sequences generated by clock controlled shift registers// EUROCRYPT'85: Conf. proc. Linz, 1985. P. 142-148.75. Thomson W. A modified congruence method of generating pseudo-randomnumbers // Computer Journal. 1958.
Vol. 1. P. 83-86.76. TIA-232-F. Interface between Data Terminal Equipment and Data CircuitTerminating Equipment Employing Serial Binary Data Interchange:TIA'/EIA Standard. 1997. URL: h t t p : / / e n g i n e e r s . i n s . com/document/abstract/IKHQABAAAAAAAAAA (дата обращения: 01.03.2011).77. Tippet L. Random sampling numbers. London: Cambridge UniversityPress, 1927. 35 p.78. von Neumann J. The general and logical theory of automata // Johnvon Neumann Collected Works.
Oxford: Pergamon Press, 1963. Vol. 5.P. 288-326.79. von Neumann J. Various techniques used in connection with random digits// Applied Mathematics Series. 1951. Vol. 12. P. 36-38.80. Watson E. Primitive polynomials (mod 2) // Mathematics of Computation.1962. Vol. 16. P. 368-369.81. Wolfram S. Cellular automata // Los Alamos Science. 1983. Vol. 9. P. 2-21.-17282. Wolfram S.
Cryptography with cellular automata // Lecture Notes in Computer Science. 1986. Vol. 218. P. 429-432.83. Wolfram S. Random sequence generation by cellular automata // Advancesin Applied Mathematics. 1986. Vol. 7. P. 123-169.84. Wolfram S. Cellular automation supercomputing // High-speed computing: scientific applications and algorithm design. Champaign: Universityof Illinois Press, 1988. P. 40-48.85.
Wolfram S. A New Kind of Science. Champaign: Wolfram Media, 2002.1192 p.-173-ПРИЛОЖБНИЯП.1. О П И С А Н И Е С Т А Т И С Т И Ч Е С К И Х Т Е С Т О В NISTНиже кратко рассматриваются разновидности статистических тестов,входящих в состав набора NIST. Для каждой разновидности приводятсявид статистических отклонений, выявляемых тестом, описание процедурытестирования, рекомендации по выбору параметров и указания по интерпретации результатов. Описание составлено на основании [63]. В программной реализации набора тестов, также разработанной NIST, некоторые параметры являются фиксированными; для таких параметров указываетсяих значение с пометкой «фиксированное значение», а рекомендации по ихизменению, приведенные в [63], опускаются.Под термином «случайная последовательность» в описании тестов понимается любая двоичная последовательность, обладающая характернымидля истинно случайной равномерно распределенной на множестве {0,1}последовательности свойствами.П.1.1.
F R E Q U E N C Y ( M O N O B I T ) T E S TОбъектом исследования является соотношение количества единиц инулей в исследуемой последовательности ё. Для истинно случайной последовательности ожидается, что число единиц и нулей будет приблизительноодинаковым.Параметры.1) ё— исследуемая последовательность, ё — £\, £2, • • •, sn;2) п —длина исследуемой последовательности.Процедура тестирования.-1741) вычисляется суммапг=1где Х{ = 2£j — 1 = ± 1 , 1 < г ^ п, т. е. Х{ получается из ч л е н а £%заменой значений 0 и - 1 и 1 н > + 1 ;2) рассчитывается значение статистикиs=|s„l.П '3) вычисляется достигаемый уровень значимостир = erfcл/2УРекомендации по выбору параметров.Для получения достоверных результатов необходимо, чтобы д л и н а исследуемой последовательности была не менее 100 бит, т.
е. п ^ 100.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости м е н ь ш еа, т.е.р< а, то последовательность ё признается неслучайной; в п р о т и в "ном случае (при р ^ а) последовательность считается случайной.Отметим, что малые значения р соответствуют большим з н а ч е н и я м s.Величина Sn, значительно большая нуля, свидетельствует о преобла,Д а Н И Иединичных членов в последовательности, а значительно меньшая — нулевых.П.1.2. F R E Q U E N C Y T E S T WITHIN A B L O C KОбъектом исследования является соотношение количества е д и н и ц инулей в подпоследовательностях длины М исследуемой последовательности ё.
Для истинно случайной последовательности ожидается, чтоединиц блоке будет близко к величине М/2.Параметры.1) ё — исследуемая последовательность, ё = £\, £2, • • •, П£)2) п — длина исследуемой последовательности;3) М — длина подпоследовательности.число-175Процедура тестирования.1) исходная последовательность ё разбивается нап-М.Nнепересекающихся подпоследовательностей длины М; неиспользованные члены в конце последовательности отбрасываются;2) определяется доля щ единичных значений в каждой подпоследовательности:мV7zZs^-l)M+oМдля всех 1 ^ г ^ N;3) рассчитывается значение статистики:s = 4Mf>-i) 2 ;г=14) вычисляется достигаемый уровень значимостиp = igamc(^,Q.Рекомендации по выбору параметров.Рекомендуется использовать последовательности ё длиной не менее100 бит (п ^ 100).
Длина подпоследовательности М должна выбиратьсятаким образом, чтобы выполнялись соотношения М ^ 20, М > 0,01п иN < 100. Также отметим, что п ^MN.Интерпретация результатов.Если вычисленное значение достигаемого уровня значимости меньшеа, т.е. р < а, то последовательность ё признается неслучайной; в противном случае (при р ^ а) последовательность считается случайной.-176П.1.З. RUNS T E S TОбъектом исследования является число непрерывных серий в ё. Подсерией длины к понимается последовательность из к одинаковых (нулевыхили единичных) членов, ограниченная слева и справа членами с противоположными значениями. Целью теста является определение отклоненийколичества серий различной длины от ожидаемой для случайной последовательности величины.
В частности, тест позволяет выявить слишкомчастую или слишком редкую смену значений в последовательности.Параметры.1) ё — исследуемая последовательность, ё = ег, еъ, • • •, £п\2) п — длина исследуемой последовательности.Процедура тестирования.1) вычисляется доля 7г единичных значений в последовательности:117ГПпчП .2) определяется, проходит ли последовательность ё простой частотныйтест из П.1.1: если |7Г — 1/2| ^ -^, текущий тест считается неприменимым и достигаемому уровню значимости присваивается значениер = 0; иначе тестирование продолжается;3) вычисляется значение статистикип-1s = ^ r ( f c ) + l,k=lгде г (к) = 0, если Е^ = €k+i, и г (к) = 1 в противном случае;4) рассчитывается достигаемый уровень значимости_ Лв-2П7Г(1-7Г)|\р = eric ' 2л/2п7г(1 — тг) '/Рекомендации по выбору параметров.Длина последовательности ё должна быть не менее 100 бит (n ^ 100).Интерпретация результатов.-177Если вычисленное значение достигаемого уровня значимости меньшеа, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
