Просмотр кода страницы 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 битовой длины <math>0 \leq b < 2^{n/2} </math>. На выходе хотим получить n битный хеш x (n почти той же битовой длины, что и M).

1)<math>M = pq</math> m = битовая длина M, p и q - засекреченные простые числа, выбранные так, чтобы факторизация M была трудной. Пусть битовая длина n будет наибольшим множителем 16, меньшим чем m (т.е. <math>n = 16n' < m </math>). <math>H_0 = 0</math> определим как IV и n-битная целочисленная константа A = 0xf0...0. "<math>\vee</math>" - обозначение для [[Побитовое ИЛИ|побитового ИЛИ]], <math>\oplus</math> - обозначение для [[Побитовое исключающее ИЛИ|побитового исключающего ИЛИ]].

2)Разбиваем сообщения с помощью [[Структура Меркла — Дамгора|структуры Меркла — Дамгора]]. Заполняем x 0-битами, если это необходимо чтобы получить строку битовой длины <math>t * n / 2 </math> для наименьшего возможного <math>t \geq 1 </math>. Поделим дополненный текст на блоки по <math>n/2</math> бита - <math>x_1, x_2, ... x_t </math> и добавим последний блок <math>x_{t+1} </math>, в котором лежит b, выраженная <math>n/2</math> битами.

3)Расширим каждый <math>x_i</math> до n-битного блока <math>y_i</math>. Для этого поделим его в 4 битные полубайты и вставим 4 бита один за другим, за исключением <math>y_{t+1}</math>, где вставленный полубайт 1010, а не 1111

4)Теперь обработаем функцию сжатия. Для <math>1 \leq  i  \leq t + 1</math>, сопоставим 2 n-битных входа (<math>H_{i - 1}, y_i</math>) одному n-битному входу  следующим образом:

<math>H_i \gets ((((H_{i-1} \oplus y_i) \vee A)^2 mod  M) \dashv n) \oplus H_{i-1}</math>

Здесь "<math>\dashv</math>" обозначает сохранение правых n бит m-битного результата слева от него.

5) Нужный нам хеш лежит в n-битном блоке <math> H_{t+1} </math><ref>A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, c.352</ref>

== Пример кода ==
Пример реализации алгоритма на [[Java]] с использованием класса BigInteger для работы с [[Длинная арифметика|длинной арифметикой]]:
<source lang = "Java">
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);
}
</source>
Чтобы сделать этот код более эффективным можно добавить следующие оптимизации:
* Работать с векторами фиксированной длины
* Работать с беззнаковыми числами
* Модульное возведение в степень только для степень 2 или 257(в случае MASH-2)
* Модульное вычитание только для чётных модулей<ref name="ReferenceA">Implementation and parallel cryptanalysis of MASH hash function family Marek Gradzki 2011</ref>

== MASH-2 ==
MASH-2 отличается от MASH-1 только другим значением экспоненты. В MASH-1 используется <math>e = 2</math>, в то время как в MASH-2 используется <math>e = 2^8 + 1</math>.
* Пример  сравнения MASH-1 и MASH-2:
   
{| class="wikitable"
|+ Результаты сравнительного анализа
|-
! Хеш-функция !! Применяемые преобразования !! Скорость обработки данных !! Модель безопасности
|-
| MASH-1 || Модулярное возведение в квадрат || <math>10^5..10^6</math> бит/с || Доказуемая безопасность
|-
| MASH-2 || Модулярное возведение в степень <math>e = 2^8 + 1 = 257</math> || <math>10^4..10^5</math> бит/с  || Доказуемая безопасность
|}<ref>Метод каскадного формирования МАС-кодов с использованием модулярных преобразований Король.О.Г., Парцхуль Л.Т., Евсеев С.П.</ref>
* Для очень высокой безопасности рекомендуется выбирать MASH-2, а не MASH-1, где могут быть нежелательные статистические зависимости <ref name="ReferenceA"/>

== Примечания ==
<!--- Смотрите в [[Википедия:Сноски]] примеры использования тегов <ref> </ref> -->
{{примечания}}

== Ссылки ==
* [https://eprint.iacr.org/2013/589.pdf 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.

<!--- Категории --->
{{Хеш-алгоритмы}}