МЕТОД ПОСТРОЕНИЯ ПОЛИНОМА ОДНОЙ ПЕРЕМЕННОЙ НАД КОНЕЧНЫМ ПОЛЕМ РАУНДОВОЙ ФУНКЦИИ БЛОЧНЫХ ШИФРОВ
В работе предлагается метод построения раундовой функции в виде полинома одной переменной над конечным полем. Предложенный метод основан на вычислении исходного криптографического преобразования в специальных точках конечного поля и последующем обращении матрицы Вандермонда. Для этого класса матриц существуют алгоритмы вычисления обратной матрицы, которые значительно эффективнее стандартного алгоритма обращения с помощью метода Гаусса. В работе был использован алгоритм Трауба, вычислительная сложность которого пропорциональна квадрату размера заданной матрицы. Метод применим для блочных итеративных шифров специального вида (SP-сеть). Для этого класса шифров приведены математические оценки алгебраических параметров полиномов раундовых функций над конечным полем. Количественные значения оценок посчитаны для актуального российского стандарта шифрования «Кузнечик». Представлены оценки вычислительной сложности предлагаемого метода. Проведены практические вычисления полиномов одной переменной для преобразования над конечными полями с различными характеристиками. Приведены практические результаты измерений времени работы при построении полиномов в конечных полях различной размерности. С помощью представленного метода в явном виде вычислен многочлен одной переменной над конечным полем раундовой функции блочного шифра PRESENT.