Experimental study of NIST Statistical Test Suite ability to detect long repetitions in binary sequences
Citations Over TimeTop 21% of 2023 papers
Abstract
Представлены и обсуждаются результаты эмпирического тестирования возможности обнаружения длинных повторов в двоичных последовательностях набором статистических тестов NIST. Набор детерминированных двоичных последовательностей, которые не отклоняются пакетом NIST, искажается детерминированным образом. Для того чтобы повредить двоичную последовательность, выбирается несколько ее подстрок фиксированной длины и каждая подстрока дублируется в случайном месте последовательности. Длина повторяющихся подстрок была выбрана значительно большей типичной длины самой длинной повторяющейся подстроки. Если количество повторяющихся подстрок в поврежденной последовательности невелико, то пакет NIST не отклоняет такие неслучайные криптографически слабые двоичные последовательности. Описан алгоритм, реализующий поиск самого длинного повторения подстрок в двоичной последовательности длины $n$. Этот алгоритм основан на дереве суффиксов, и его временная и пространственная сложности имеют порядок $O(n)$.
Related Papers
- → Uncertainty in NIST force measurements(2005)21 cited
- → Primary atomic frequency standards at NIST(2001)31 cited
- → Assessing the Impact of the National Institute of Standards and Technology’s Research Collaborations(2014)1 cited
- → Evaluation of National Institute of Standards and Technology (NIST) Thermal Conductivity Standard Reference Materials Using a 20-cm Heat Flow Meter Apparatus(1989)1 cited
- → Technique for assessing PNA measurement repeatability using a NIST standard(2005)1 cited