MASH-1 (MASH-1)
MASH-1 (Modular Arithmetic Secure Hash) — это хеш-функция, используемая в криптографии, основанная на модульной арифметике. Главные преимущества этой функции - возможность повторного использования существующего программного или аппаратного обеспечения и масштабируемость. Из недостатков: не очень высокая скорость, обусловленная скоростью RSA-шифрования, которая на 2-3 порядка ниже скорости блочно-симметричных шифров, и история неудачных предложений функций, основанных на модульной арифметике.
История
[править | править код]MASH-1 и MASH-2 после долгой проработки и множества неудачных предложений вошли в стандарт ISO/IEC 10118-4 [1] в 1998 году. К данному моменту нет опубликованных результатов проблем в безопасности этих хеш-функций.
Мотивация к использованию модульной арифметики в хэш-функции основана на двух факторах: возможности повторного использования существующего программного или аппаратного обеспечения (в системах с открытым ключом) для модульной арифметики и масштабируемости для соответствия требуемому уровню безопасности и желаемому размеру хэш-значения.
Описание алгоритма
[править | править код]MASH-1 предполагает использование модуля M, аналогичного модулю из RSA. Битовая длина M оказывает прямое влияние на безопасность. M должно быть сложно факторизовать и безопасность держится на сложности выделения корней по модулю. Также битовая длина M определяет размер блока обрабатываемых данных и размер хеш-результата.
На вход алгоритма получаем x битовой длины . На выходе хотим получить n битный хеш x (n почти той же битовой длины, что и M).
1) m = битовая длина M, p и q - засекреченные простые числа, выбранные так, чтобы факторизация M была трудной. Пусть битовая длина n будет наибольшим множителем 16, меньшим чем m (т.е. ). определим как IV и n-битная целочисленная константа A = 0xf0...0. "" - обозначение для побитового ИЛИ, - обозначение для побитового исключающего ИЛИ.
2)Разбиваем сообщения с помощью структуры Меркла — Дамгора. Заполняем x 0-битами, если это необходимо чтобы получить строку битовой длины для наименьшего возможного . Поделим дополненный текст на блоки по бита - и добавим последний блок , в котором лежит b, выраженная битами.
3)Расширим каждый до n-битного блока . Для этого поделим его в 4 битные полубайты и вставим 4 бита один за другим, за исключением , где вставленный полубайт 1010, а не 1111
4)Теперь обработаем функцию сжатия. Для , сопоставим 2 n-битных входа () одному n-битному входу следующим образом:
Здесь "" обозначает сохранение правых n бит m-битного результата слева от него.
5) Нужный нам хеш лежит в n-битном блоке [1]
Пример кода
[править | править код]Пример реализации алгоритма на Java с использованием класса BigInteger для работы с длинной арифметикой:
private final BigInteger compress(BigInteger X, BigInteger H) {
BigInteger XX = BigInteger.value0f(0);
BigInteger rem;
for (int j = k - 4; j >= 0; j -= 4) {
XX = XX.shiftLeft(4).or(FEFTEEN);
rem = block.shiftRight(j).mod(SIXSTEEN);
XX = XX.shiftLeft(4).or(rem);
}
return H.xor(XX).or(E).pow(2).mod(N).mod(TWO_POW_N).xor(H);
}
Чтобы сделать этот код более эффективным можно добавить следующие оптимизации:
- Работать с векторами фиксированной длины
- Работать с беззнаковыми числами
- Модульное возведение в степень только для степень 2 или 257(в случае MASH-2)
- Модульное вычитание только для чётных модулей[2]
MASH-2
[править | править код]MASH-2 отличается от MASH-1 только другим значением экспоненты. В MASH-1 используется , в то время как в MASH-2 используется .
- Пример сравнения MASH-1 и MASH-2:
Хеш-функция | Применяемые преобразования | Скорость обработки данных | Модель безопасности |
---|---|---|---|
MASH-1 | Модулярное возведение в квадрат | бит/с | Доказуемая безопасность |
MASH-2 | Модулярное возведение в степень | бит/с | Доказуемая безопасность |
- Для очень высокой безопасности рекомендуется выбирать MASH-2, а не MASH-1, где могут быть нежелательные статистические зависимости [2]
Примечания
[править | править код]- ↑ A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, c.352
- ↑ 1 2 Implementation and parallel cryptanalysis of MASH hash function family Marek Gradzki 2011
- ↑ Метод каскадного формирования МАС-кодов с использованием модулярных преобразований Король.О.Г., Парцхуль Л.Т., Евсеев С.П.
Ссылки
[править | править код]- Smashing MASH-1, Vladimir Antipkin
- A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, ISBN 0-8493-8523-7
- Метод каскадного формирования МАС-кодов с использованием модулярных преобразований Король.О.Г., Парцхуль Л.Т., Евсеев С.П.
- Implementation and parallel cryptanalysis of MASH hash function family Marek Gradzki 2011
- P. van Oorschot and M. Wiener , Parallel collision search with cryptanalytic applications , Journal of Cryptology, 12(1):1-28, 1999.
- D. Bishop , Introduction to Cryptography with Java Applets , 2003.
- ISO/IEC 10118. Information technology{security. Part 4: Hash-functions using modular arithmetic , 1998.
- H.C.A. van Tilborg , Encyclopedia of Cryptography and Security , Springer-Verlag New York, Inc., Secaucus, NJ, 2005.
- J. Bloch , E ective Java: Programming Language Guide , Addison Wesley, 2001.