17:31 SHA-3 | |
| SHA-3 ( Secure Hash Algorithm 3 ) - последний член семейства стандартов Secure Hash Algorithm , выпущенный NIST 5 августа 2015 года. Хотя SHA-3 является частью той же серии стандартов, внутренне отличается от MD5 -подобной структуры из SHA-1 и SHA-2
SHA-3 использует конструкцию губки , в которой данные «впитываются» в губку, а затем результат «выдавливается». В фазе поглощения блоки сообщений XOR преобразуются в подмножество состояния, которое затем преобразуется в целом с использованием функции перестановки f . В фазе «сжатия» выходные блоки считываются из одного и того же подмножества состояния, чередующегося с функцией преобразования состояния f . Размер части состояния, которое записывается и читается, называется «скоростью» (обозначается как r ), а размер части, не затронутой вводом / выводом, называется «емкостью» (обозначается как « c»).). Мощность определяет безопасность схемы. Максимальный уровень безопасности составляет половину емкости. Учитывая входную битовую строку N , площадку функции дополнения, функцию перестановки f, которая работает с битовыми блоками ширины b , скорости r и выходной длины d , мы имеем емкость c = b - r и конструкцию губки Z = sponge [ f , pad, r ] ( N , d ), получая битовую строку Z длины d , работает следующим образом: : 18 дополняет ввод N с помощью функции pad, получая битовую строку дополненного P с длиной, кратной r (так что n = len ( P ) / r является целым числом) разбить P на n последовательных r- битных частей P 0 , ..., P n − 1 инициализировать состояние S в строку из нулевых битов b впитать ввод в состояние: для каждого блока P i : расширять P i в конце строкой с нулевыми битами, получая длину b XOR, что с S применить перестановку блоков f к результату, получив новое состояние S инициализировать Z, чтобы быть пустой строкой в то время как длина Z меньше чем d : добавить первые r битов S к Z если Z все еще меньше чем d битов, применить f к S , получая новое состояние S обрезать биты от Z до d Тот факт, что внутреннее состояние S содержит c дополнительных битов информации в дополнение к тому, что выводится в Z, предотвращает атаки с удлинением длины, которым подвержены SHA-2, SHA-1, MD5 и другие хэши, основанные на конструкции Меркля-Дамгарда . В SHA-3 состояние S состоит из массива w- битных слов размером 5 × 5 (с w = 64), b = 5 × 5 × w = 5 × 5 × 64 = всего 1600 бит. Keccak также определяется для меньших мощности из-2 размеров слов ш вплоть до 1 бит (общее состояние 25 битов). Небольшие размеры состояний могут использоваться для проверки криптоаналитических атак, а промежуточные размеры состояний (от w = 8 200 бит до w = 32 800 бит) могут использоваться в практических, легких приложениях. Для экземпляров SHA-3-224, SHA-3-256, SHA-3-384 и SHA-3-512 r больше, чем d , поэтому нет необходимости в дополнительных перестановках блоков в фазе сжатия; старшие d биты состояния являются желаемым хешем. Однако SHAKE-128 и SHAKE-256 допускают произвольную длину вывода, что полезно в таких приложениях, как оптимальное заполнение асимметричного шифрования .. Чтобы сообщение можно было равномерно разделить на r- битные блоки, требуется заполнение. SHA-3 использует шаблон 10 * 1 в своей функции заполнения: 1 бит, за которым следует ноль или более 0 бит (максимум r - 1 ) и последний 1 бит. Максимум r - 1 нулевых битов происходит, когда последний блок сообщения имеет длину r - 1 бит. Затем добавляется еще один блок после начального 1 бита, содержащий r - 1 нулевых бит перед последним 1 битом. Два 1 бита будут добавлены, даже если длина сообщения уже делится на r . : 5.1 В этом случае к сообщению добавляется еще один блок, содержащий 1 бит, за которым следует блок из r - 2 нулевых бит и еще один 1 бит. Это необходимо для того, чтобы сообщение с длиной, кратной r, заканчивающейся чем-то, похожим на заполнение, не создавало тот же хэш, что и сообщение с удаленными этими битами. Требуется начальный 1 бит, поэтому сообщения, отличающиеся только несколькими дополнительными 0 битами в конце, не создают одинаковый хэш. Позиция последнего 1 бита указывает, какая скорость r использовалась (многоскоростное заполнение), что требуется для доказательства безопасности для работы с различными вариантами хеширования. Без него разные варианты хеш-функции одного и того же короткого сообщения были бы одинаковыми вплоть до усечения. Блочная трансформация f , которая является Keccak-f [1600] для SHA-3, является перестановкой, использующей операции XOR , AND и NOT , и предназначена для легкой реализации как в программном, так и в аппаратном обеспечении. Он определен для любого размера слова степени двух , w = 2 ℓ бит. Основное представление SHA-3 использует 64-битные слова, ℓ = 6 . Состояние может рассматриваться как массив битов 5 × 5 × w . Пусть a [ i ] [ j ] [ k ] будет битом (5 i + j ) × w + k ввода, используя соглашение о порядке нумерации битов с прямым порядком байтов и индексирование основной строки . Т.е. я выбираю строку, j столбец и k бит. Индексная арифметика выполняется по модулю 5 для первых двух измерений и по модулю w для третьего. Основной функциональный блок перестановки состоит из 12 + 2 л раундов пяти этапов: θ (тета) Вычислите четность каждого из 5-битных столбцов 5 w (320, когда w = 64 ), и исключите или это в два соседних столбца в регулярном образце. Чтобы быть точным, a [ i ] [ j ] [ k ] ← a [ i ] [ j ] [ k ] ⊕ четность (a [0 ... 4] [ j −1] [ k ]) ⊕ четность (a [ 0 ... 4] [ j +1] [ k −1]) ρ (ро) Побитово поверните каждое из 25 слов на другое треугольное число 0, 1, 3, 6, 10, 15, .... Если быть точным, a [0] [0] не вращается, и для всех 0 ≤ t < 24 , a [ i ] [ j ] [ k ] ← a [ i ] [ j ] [ k - ( t +1) ( t +2) / 2] , где{\ displaystyle {\ begin {pmatrix} i \\ j \ end {pmatrix}} = {\ begin {pmatrix} 3 & 2 \\ 1 & 0 \ end {pmatrix}} ^ {t} {\ begin {pmatrix} 0 \\ 1 \ конец {pmatrix}}}. π (пи) Перестановка 25 слов в фиксированном порядке. a [ j ] [2 i +3 j ] ← a [ i ] [ j ] . χ (чи) Побитовое объединение вдоль строк, используя x ← x ⊕ (¬ y & z ) . Чтобы быть точным, a [ i ] [ j ] [ k ] ← a [ i ] [ j ] [ k ] ⊕ (¬ a [ i ] [ j + 1 ] [ k ] & a [ i ] [ j + 2 ] [ к ]) . Это единственная нелинейная операция в SHA-3. J (Йота) Эксклюзив - или круглая константа в одно слово государства. Чтобы быть точными, в круглом п , для 0 ≤ т ≤ л , [0] [0] [2 м -1] является операция XOR с битом м + 7 п градуса 8- LFSR последовательности. Это нарушает симметрию, которая сохраняется другими шагами. В скорости хеширования длинных сообщений SHA-3 преобладают вычисления f = Keccak-f [1600] и XORing S с расширенным P i , операция на b = 1600 бит. Однако, поскольку последние c битов расширенного P i в любом случае равны 0, а XOR с 0 является noop, достаточно выполнить операции XOR только для r битов ( r = 1600 - 2 × 224 = 1152 бит для SHA3-224 , 1088 бит для SHA3-256, 832 бита для SHA3-384 и 576 бит для SHA3-512). Чем ниже r (и, наоборот, чем выше c = b - r = 1600 -r ) чем менее эффективным, но более безопасным становится хеширование, так как меньшее количество битов сообщения может быть XOR в состояние (быстрая операция) перед каждым применением вычислительно дорогого f . Авторы сообщают о следующих скоростях для программных реализаций Keccak-f [1600] плюс XORing 1024 бита , что примерно соответствует SHA3-256: 57,4 cpb на IA-32, Intel Pentium 3 41 cpb на IA-32 + MMX, Intel Pentium 3 20 cpb на IA-32 + SSE, Intel Core 2 Duo или AMD Athlon 64 12,6 cpb на типичной машине на базе x86-64 6–7 cpb на IA-64 Для точного SHA3-256 на x86-64 Бернштейн измеряет 11.7–12.25 cpb в зависимости от процессора. : 7 SHA-3 подвергся критике за медлительность в архитектурах наборов команд (ЦП), в которых нет инструкций, предназначенных специально для более быстрого вычисления функций Keccak - SHA2-512 более чем в два раза быстрее, чем SHA3-512, и SHA -1 более чем в три раза быстрее на процессоре Intel Skylake с тактовой частотой 3,2 ГГц. Авторы отреагировали на эту критику, предложив использовать SHAKE128 и SHAKE256 вместо SHA3-256 и SHA3-512, за счет сокращения сопротивления прообразу вдвое (но при сохранении сопротивления столкновению). При этом производительность на одном уровне с SHA2-256 и SHA2-512. Однако в аппаратных реализациях SHA-3 заметно быстрее всех других финалистов а также быстрее, чем SHA-2 и SHA-1. В ARM ARMv8 и в архитектуре IBM s390x уже (по состоянию на 2018 г.) содержатся специальные инструкции, которые позволяют алгоритмам Keccak работать быстрее. | |
|
| |
| Всього коментарів: 0 | |