Тест на профіль лінійної складності

Скорочена інформація про документ
dc.contributor.authorЗавадська, Людмила
dc.contributor.authorСемибаламут, Максим
dc.contributor.authorЗавадская, Людмила
dc.contributor.authorСемибаламут, Максим
dc.contributor.authorZavadskaya, Lyudmila
dc.contributor.authorSemybalamut, Maxim
dc.date.accessioned2014-11-24T14:28:32Z
dc.date.available2014-11-24T14:28:32Z
dc.date.issued2010
dc.description.abstractenA new test for assessing the quality of random sequences is developed, based on the profile of linear complexity. Test operates the number of leaps of the linear complexity and in some cases much more effective than the corresponding test set of NIST. The task of composition a new effective criteria for detecting deviations from randomness is relevant. As a basis of the test, called by the author the LP test (Linear Profile-test), is laid the random value Sn=(Nn-n/4)/√n/8. The speed of the created test approximately the same as the speed test on the linear complexity of the package of NIST, as the basis of both tests is the algorithm Berlekempa-Messi. But the realization of LP-test somewhat easier, because it has a normal distribution statistics as against to specific distribution of test statistics in NIST. As a result of investigations of authors it was found that the LP test is much more effective at least for these types of low-quality input sequences : a. Linear recurrent sequences with the noise. b. Sequence generated by a regular or random alternation of the different segments of linear recurrent sequences. c. Sequence generated by a regular or random alternation of the segments of linear recurrent sequences and the segments created by a good generator of the pseudorandom numbers. d. Sequence generated with the noise. e. Sequence generated of linear recurrent sequences by accidental deletion of bits.uk
dc.description.abstractruРазработано новый тест для оценки качества случайных последовательностей, основанный на профили линейной сложности. Тест оперирует количеством прыжков линейной сложности и в определенных случаях значительно эффективнее чем соответствующий тест из набора NIST. Задача построения новых эффективных критериев для выявления отклонений от случайности актуальна. В основу теста, названного авторами LP-тестом (Linear Profile-тест), положена случайная величина Sn=(Nn-n/4)/√n/8. Скорость работы построенного теста примерно такая же, как и скорость теста на линейную сложность из пакета NIST, так как в основе обоих тестов лежит алгоритм Берлекемпа-Месси. Однако реализация LP-теста несколько проще, ведь в нем статистика имеет стандартное распределение в отличие от специфического распределения статистики в тесте NIST. В результате исследований было выявлено, что тест LP намного эффективнее по крайней мере на следующих типах некачественных входных последовательностей (тут шум означает инвертирование каждого бита с вероятностью p): a. Линейные рекуррентные последовательности с шумом. b. Последовательности, сформированные путем регулярного или случайного чередование отрезков разных линейных рекуррентных последовательностей. c. Последовательности, сформированные путем регулярного или случайного чередование отрезков линейных рекуррентных последовательностей и отрезков, образованных с помощью хорошего генератора псевдослучайных чисел. d. Последовательности, сформированы, как указано в предыдущем пункте, с шумом. e. Последовательности, сформированные из линейных рекуррентных последовательностей путем случайного удаления битов.uk
dc.description.abstractukРозроблено новий тест для оцінювання якості випадкових послідовностей, який базується на профілі лінійної складності. Тест оперує кількістю стрибків лінійної складності і у певних випадках значно ефективніший за відповідний тест з набору NIST. Задача побудови нових ефективних критеріїв для виявлення відхилень від випадковості є актуальною. В основу тесту, названого авторами LP-тестом (Linear Profile-тест), покладена випадкова величина Sn=(Nn-n/4)/√n/8. Швидкість роботи побудованого тесту приблизно така сама, як і швидкість тесту на лінійну складність з пакету NIST, так як в основі обох тестів лежить алгоритм Берлекемпа-Мессі. Проте реалізація LP-тесту дещо простіша, адже в ньому статистика має стандартний розподіл на відміну від специфічного розподілу статистики у тесті NIST. В результаті досліджень авторів було виявлено, що тест LP набагато ефективніший принаймні на наступних типах неякісних вхідних послідовностей (тут шум означає інвертування кожного біту з імовірністю p): a. Лінійні рекурентні послідовності з шумом. b. Послідовності, сформовані шляхом регулярного або випадкового чергування відрізків різних лінійних рекурентних послідовностей. c. Послідовності, сформовані шляхом регулярного або випадкового чергування відрізків лінійних рекурентних послідовностей та відрізків, утворених за допомогою гарного генератора псевдовипадкових чисел. d. Послідовності, сформовані, як зазначено у попередньому пункті, з шумом. e. Послідовності, сформовані з лінійних рекурентних послідовностей шляхом випадкового видалення бітів.uk
dc.format.pagerangeС.55-59uk
dc.identifier.citationЗавадська, Л. Тест на профіль лінійної складності / Людмила Завадська, Максим Семибаламут // Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні : науково-технічний збірник. – 2010. – Вип. 2(21). – С. 55-59. – Бібліогр.: 6 назв.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/9495
dc.language.isoukuk
dc.publisherНТУУ "КПІ"uk
dc.publisher.placeКиївuk
dc.source.nameПравове, нормативне та метрологічне забезпечення системи захисту інформації в Україні: науково-технічний збірникuk
dc.status.pubpublisheduk
dc.subjectКриптографіяuk
dc.subjectвипадкові послідовностіuk
dc.subjectтести оцінки якостіuk
dc.subjectлінійна складністьuk
dc.subjectпрофіль лінійної складностіuk
dc.subject.udc681.3.06:519.248.681uk
dc.titleТест на профіль лінійної складностіuk
dc.title.alternativeTest profile linear complexityuk
dc.title.alternativeТест на профиль линейной сложностиuk
dc.typeArticleuk
thesis.degree.level-uk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
21_p55.pdf
Розмір:
382.14 KB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
1.71 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Правове, нормативне та метрологічне забезпечення системи захисту інформації в Україні: науково-технічний збірник, Вип. 2(21)