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