Preview

Математика и математическое моделирование

Расширенный поиск
№ 4 (2020)

ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ

1-51 655
Аннотация

С помощью численного расчета описывается работа алгоритмов пермутаций матриц, основанных на циклических сдвигах строк и столбцов. Такой выбор алгоритмов дискретного преобразования обоснован удобством клеточно-автоматных формулировок, которые и приводятся. Получены эмпирические формулы для периода пермутаций; для последнего алгоритма формула периода носит рекуррентный характер. Для базовой и наиболее простой схемы период N(n) имеет асимптотику exp(2n)/n для матрицы nxn с попарно различными элементами. Несмотря на усложнение схемы алгоритма, две другие модификации дают лишь полиномиальный рост степени не выше 3. Четвертая схема имеет нетривиальную зависимость периода, но не выше экспоненциальной. В ряде случаев алгоритмы порождают особые пермутации: поворот, отражение и перестановку блоков для матрицы 2kx2k. Эти формулы тесно связаны с индивидуальными траекториями элементов, а они – с влиянием границ, что дает ветвление порядка матрицы по классу вычета по модулю 3,4 или 12. Визуализации этих траекторий приводятся в расширенном поле КА. В качестве параметра динамики КА анализируются две «метрики перемешанности» на пермутациях матрицы (по сравнению с начальной). Для всех схем и большинства ветвей поведение этих метрик представлено на графиках и гистограммах (условно: плотности распределения), показывающих, как часто встречаются по периоду пермутации с заданным интервалом значений метрик. Практическое значение работы состоит в оценке применения КА в областях генерации псевдослучайных чисел и криптографии.

СИСТЕМНЫЙ АНАЛИЗ И ОБРАБОТКА ИНФОРМАЦИИ

52-64 648
Аннотация

В работе исследуются проблемы редукции (декомпозиции) моделей многомерных данных в виде гиперкубовых OLAP-структур. OLAP обработка данных не допускает изменения размерности пространства. С увеличением объемов данных падает производительность вычислений кубовых структур. Методы редукции больших кубов данных на подкубы с меньшими объемами позволяют решать проблему снижения производительности вычислений.

Рассматриваются задачи редукции для случаев, когда агрегирование критериев уже определено решёткой куба, а декомпозиция куба на меньшие по размерности кубы нужна для снижения времени вычисления полной решётки при динамическом изменении данных в кубе.

Цель работы состоит в нахождении условий уменьшения вычислительной сложности решения задач анализа данных редукционными методами, получении точных количественных границ уменьшения сложности декомпозиционных методов из класса полиномиальной степеней сложности, установлении характера зависимости вычислительной производительности от структурных свойств гиперкуба и определении количественных границ вычислительной производительности решения декомпозиционных задач агрегирования данных.

Проведено исследование вычислительной сложности декомпозиционных методов анализа многомерных гиперкубов полиномиально-логарифмической и полиномиальной степеней сложности. Найдена точная верхняя граница уменьшения сложности декомпозиционных методов анализа исходного OLAP--гиперкуба данных по отношению к недекомпозиционным, и на их основе доказаны критерии эффективного применения редукционных методов анализа гиперкубовых структур по сравнению с традиционными нередукционными методами.

Приведены примеры методов декомпозиции кубовых структур, как уменьшающих, так и увеличивающих вычислительную сложность по сравнению с вычислениями по полной модели.

Результаты работы могут быть использованы при обработке и анализе массивов информации гиперкубовых структур аналитических OLAP-систем, относящихся к классу BigData, или сверхбольших компьютерных систем многомерных данных.

КРИПТОГРАФИЯ И КРИПТОАНАЛИЗ

65-92 384
Аннотация

Одной из важных проблем, возникающих при проектировании и практической реализации криптосистем, является противодействие атакам по побочным каналам. Нередко алгоритмы, стойкость которых с чисто математической точки зрения не вызывает больших сомнений, оказываются уязвимыми к таким атакам при их реализации на конкретном физическом устройстве.

Атака методом анализа сбоев является одним из вариантов атаки на криптосистему по побочным каналам. Суть ее состоит в активном воздействии атакующим на физическое устройство, осуществляющее процесс вычислений (например, смарт-карту). Получаемые в результате воздействия искажения затем анализируются с целью восстановить секретную информацию, хранимую внутри устройства. Подобные атаки зачастую оказываются значительно эффективнее пассивных атак по побочным каналам.

Атаки методом анализа сбоев были предложены в более 20 лет назад. С тех пор были успешно построены атаки на реализации целого ряда симметричных и асимметричных криптоалгоритмов. Также был предложен ряд различных методов осуществления активного воздействия на процесс вычислений, с использованием конкретных физических эффектов и особенностей вычислительной среды. Также активно развиваются и подходы к противодействию такого рода атакам. Для этого используются как физические, так и чисто математические методы. Однако следует отметить, что криптографические хэш-функции, и более сложные криптосхемы, содержащие их в качестве компонент (например, некоторые имитовставки и цифровые подписи), в рамках этих работ представлены незначительно.

Важно отметить, что для практического применения конкретной атаки необходимо сочетание следующих факторов: наличия возможности конкретного физического воздействия на вычислительный процесс, адекватной математической модели данного физического воздействия и чисто математического компонента атаки --конкретного алгоритма внесения искажений и последующего анализа результатов. При этом решение каждой из этих задач по отдельности представляет самостоятельную теоретическую ценность.

Результаты настоящей работы не затрагивают физическую составляющую атаки, ограничиваясь лишь математикой. Иными словами, предложены конкретные алгоритмы внесения искажений и последующего анализа результатов. При этом конкретная модель сбоев считается известной и заданной. Рассмотрено несколько таких моделей, которые базируются на аналогах, ранее предложенных для других алгоритмов.

В качестве объекта исследований выбраны два стандарта формирования имитовставок: HMAC и NMAC. Указанные стандарты могут базироваться на любой криптографической хэш-функции, обеспечивающей нужный уровень стойкости. В данной работе исследованы четыре примера широкораспространенных хэшей: MD5, MD4, SHA-1, SHA-0.

Основными результатами данной работы являются следующие:

-     построены конкретные алгоритмы внесения искажений в вычислительный процесс, и их дальнейшего анализа, позволяющие извлечь секретную информацию (секретные ключи);

-     найдены и обоснованы оценки сложности таких атак (в терминах числа вносимых сбоев и трудоемкости последуюшего анализа) для различных сочетаний параметров(алгоритмов и моделей сбоев);

-     показано, что атаки могут быть проведены за разумное время.



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)