SHA-3

Материал из BitcoinWiki
(перенаправлено с «Keccak»)

Это утверждённая версия страницы. Она же — наиболее свежая версия.
Перейти к: навигация, поиск

SHA-3 (Keccak) – алгоритм хеширования переменной разрядности, разработанный группой во главе с Йоаном Дайменом в 2012 году. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Алгоритм SHA-3 построен по принципу криптографической губки.

История[править]

В 2004-2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного Национальным институтом стандартов и технологий (NIST).

В ответ NIST провел открытые семинары и 2 ноября 2007 года анонсировал конкурс на разработку нового алгоритма хеширования.

2 октября 2012 года победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3.

5 августа 2015 года алгоритм утвержден и опубликован в качестве стандарта FIPS 202.

Алгоритм был разработан Гвидо Бертони, Йоаном Дайменом, Жилем Ван Аше из STMicroelectronics и Микаэлем Питерсом из NXP.

Алгоритм основан на более ранних хеш-функциях Panama и RadioGatún. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году.

В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak:

  • Количество раундов было увеличено с 12 + l до 12 + 2l;
  • Padding был изменён со сложной формы на более простую, описанную ниже;
  • Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2).

Описание Алгоритма[править]

Keccak основан на конструкции Sponge. Это означает, что для получения хеша нужно проделать следующие незамысловатые действия: Взять исходное сообщение M и дополнить его до длины кратной r. В виде формулы их можно изобразить следующим образом: M=M||0x01||0x00||..||0x00||0x80. То есть к сообщению дописывается единичный байт, необходимое количество нулей и завершается байт со значением 0x80.

UPD: Все вышесказанное справедливо только для случаев, когда добавляется более одного байта.

Однако в случае, если необходимо дополнить всего один байт, то достаточно добавить лишь 0x81.

Затем для каждого блока Mi длиной r бит выполняем:

  • Сложение по модулю 2 с первыми r-битами набора начальных состояний S. Перед началом работы функции все элементы S будут равны нулю.
  • N раз применяем к полученным в результате данным функцию f. Набором начальных состояний S для блока Mi+1 будет результат последнего раунда блока Mi.
  • После того как все блоки Mi закончатся взять итоговый результат и вернуть его в качестве хеш-значения.

Параметры r и c[править]

Хеш-функция Keccak реализована таким образом, что функцию перестановки f, применяемую для каждого блока Mi, пользователь может выбирать самостоятельно из набора предопределенных функции b={f-25, f-50, f-100, f-200, f-400, f-800, f-1600}.

Для использования функции f-800, необходимо выбрать такие r и c, чтобы выполнялось равенство r+c=800.

Кроме того, изменяя значения r и c, вы тем самым изменяете количество раундов вашей хеш-функции.

Т.к. количество оных вычисляется по формуле n=12+2l, где 2l=(b/25). Так для b=1600, Количество раундов равно 24.

Однако хотя пользователь в праве выбирать для своей реализации любую из предложенных авторами функций, следует отметить что в качестве стандарта SHA-3 принята только функция Keccak-1600 и авторы всячески рекомендуют пользоваться только ею. Так в качестве основных значений для хешей разной длины авторы выбрали следующие параметры:

  • SHA-224: r=1156, c=448 (вернуть первые 28 байт результат)
  • SHA-256: r=1088, c=512 (вернуть первые 32 байт результат)
  • SHA-384: r=832, c=768 (вернуть первые 48 байт результат)
  • SHA-512: r=576, c=1024 (вернуть первые 64 байт результат)

Схема работы[править]

Схема SHA-3 (Keccak) состоит из двух этапов:

SHA-3 – алгоритм Keccak
  • Absorbing (впитывание). Исходное сообщение M подвергается многораундовым перестановкам f.
  • Squeezing (отжатие). Вывод получившегося в результате перестановок значения Z.

Функция Keccak представляет из себя следующее:

Keccak[r,c](M) {
 Initialization and padding
 for(int x=0; x<5; x++)
   for(int y=0; y<5; y++)
     S[x,y] = 0;
 P = M || 0x01 || 0x00 || … || 0x00;
 P = P xor (0x00 || … || 0x00 || 0x80);
 //Absorbing phase
 forall block Pi in P
 for(int x=0; x<5; x++)
   for(int y=0; y<5; y++)
     S[x,y] = S[x,y] xor Pi[x+5*y];
   S = Keccak-f[r+c](S);
 //Squeezing phase
 Z = empty string;
do
{
 for(int x=0; x<5; x++)
   for(int y=0; y<5; y++)
     if((x+5y)<r/w)  
       Z = Z || S[x,y];
   S = Keccak-f[r+c](S)
}  while output is requested
 return Z;
}
  • На этапе Absorbig производится вычисление хеш значения.
  • А на этапе Squeezing вывод результатов до тех пор пока не будет достигнута требуемая длина хеша.

Этап absorbing[править]

Этап absorbing можно представить в виде следующей функции:

Keccak-f[b](A) 
{
 forall i in 0…nr-1
   A = Round[b](A, RC[i])
 return A
}
  • Здесь b это значение выбранной функции(по умолчанию 1600).
  • А функция Round()-псевдослучайная перестановка, применяемая на каждом раунде. Количество раундов nr вычисляется из значений r и c.

Операции выполняемые на каждом раунде представляют из себя следующую функцию:

Round[b](A,RC)
{
 θ step
 for(int x=0; x<5; x++)
   C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4];
 for(int x=0; x<5; x++)
   D[x] = C[x-1] xor rot(C[x+1],1);
 for(int x=0; x<5; x++)
   A[x,y] = A[x,y] xor D[x];

 ρ and π steps
 for(int x=0; x<5; x++)
   for(int y=0; y<5; y++)
     B[y,2*x+3*y] = rot(A[x,y], r[x,y]);

 χ step
 for(int x=0; x<5; x++)
   for(int y=0; y<5; y++)
     A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]);

 ι step
 A[0,0] = A[0,0] xor RC

 return A
}

Тут 4 шага на каждом из которых над входящими данными производится ряд логических действий.

Здесь функция rot(X,n) обозначает циклический сдвиг элемента X на n позиций.

Массив r[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты на каждом раунде:

SHA-3 алгоритм

Массив RC это набор констант, которые тоже являются предопределенными:

Keccak майнинг

См. также на BitcoinWiki[править]

Источники[править]