Keccak, новый стандарт хеширования данных

  • Tutorial
Доброго времени суток, уважаемые читатели.
Многие из вас наверняка знают о том, что на протяжении нескольких лет NIST проводил конкурс среди хеш-функций с целью принятия нового стандарта SHA-3. И в этом году награда нашла своего героя. Новый стандарт был благополучно принят.
Ну а раз стандарт уже принят, самое время посмотреть что же он из себя представляет.
И тихим, субботним вечером, я обложившись мануалами открыв в браузере google.com начал свое небольшое исследование.


Прелюдия

В качестве нового стандарта была выбрана хеш-функция Keccak с переменной длиной выхода 224,256,384 и 512 бит. В основе Keccak лежит конструкция под названием Sponge(губка, та самая с верхней картинки).
Данную конструкцию можно представить следующим образом:

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

Внимательный читатель наверняка заметил на рисунке буквы r и с. Не будем раньше времени раскрывать интригу, скажем только что варьируя значение этих переменных мы получим абсолютно разные хеш-функции. Так для SHA-512, в качестве этих значений нужно выбрать r=576, c=1024.

А поподробнее?

Итак, как я уже сказал выше, алгоритм Keccak основан на конструкции Sponge. Это означает, что для получения хеша Нам нужно проделать следующие незамысловатые действия:
  • Взять исходное сообщение M и дополнить его до длины кратной r. Правила дополнения пленяют своей простотой. В виде формулы их можно изобразить следующим образом: M=M||0x01||0x00||..||0x00||0x80. Или говоря по-русски, к сообщению дописывается единичный байт, необходимое количество нулей и весь этот ансамбль завершает байт со значением 0x80.
    UPD:Все вышесказанное справедливо только для случаев, когда добавляется более одного байта. Однако в случае, если необходимо дополнить всего один байт, то достаточно добавить лишь 0x81. Ошибка вскрылась благодаря бдительности уважаемого OverQuantum. А еще раньше об этом же говорил хабраюзер fdsc, чей пост в песочнице был незамечен, но теперь справедливость восторжествовала. Таким образом код необходимо переписать с учетом этого замечания!
  • Затем для каждого блока 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 байт результат)

А код-то где?

И после всех этих разъяснений можно уже перейти непосредственно к псевдокоду алгоритма.
Этап 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[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты на каждом раунде. Значение всех элементов данного массива продемонстированы на таблице ниже:

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


Сама же функция 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 вывод результатов до тех пор пока не будет достигнута требуемая длина хеша.

Под спойлером небольшой класс, написанный на C#, реализующий все эти действия


public class Keccack
    {

        //константы рандов, всего их 24
        //применяются на шаге ι
        private ulong[] RC ={0x0000000000000001,
        0x0000000000008082,
        0x800000000000808A,
        0x8000000080008000,
        0x000000000000808B,
        0x0000000080000001,
        0x8000000080008081,
        0x8000000000008009,
        0x000000000000008A,
        0x0000000000000088,
        0x0000000080008009,
        0x000000008000000A,
        0x000000008000808B,
        0x800000000000008B,
        0x8000000000008089,
        0x8000000000008003,
        0x8000000000008002,
        0x8000000000000080,
        0x000000000000800A,
        0x800000008000000A,
        0x8000000080008081,
        0x8000000000008080,
        0x0000000080000001,
        0x8000000080008008};
        //матрица смещений, применяется при каждом раунде на шаге θ
        private int[,] r = {{0,    36,     3,    41,    18}    ,
                          {1,    44,    10,    45,     2}    ,
                          {62,    6,    43,    15,    61}    ,
                          {28,   55,    25,    21,    56}    ,
                          {27,   20,    39,     8,    14}    };
        private int w, l, n;
        //в конструкторе устанавливаем параметры функции b=1600
        public Keccack(int b)
        {
            w = b / 25;
            l = (Convert.ToInt32(Math.Log(w, 2)));
            n = 12 + 2 * l;
        }
        //циклический сдвиг переменной x на n бит
        private ulong rot(ulong x, int n)
        {
            n = n % w;
            return (((x << n) | (x >> (w - n))));
        }

        private ulong[,] roundB(ulong[,] A, ulong RC)
        {
            ulong[] C = new ulong[5];
            ulong[] D = new ulong[5];
            ulong[,] B = new ulong[5, 5];
            //шаг θ
            for (int i = 0; i < 5; i++)            
                C[i] = A[i, 0] ^ A[i, 1] ^ A[i, 2] ^ A[i, 3] ^ A[i, 4];            
            for (int i = 0; i < 5; i++)            
                D[i] = C[(i + 4) % 5] ^ rot(C[(i + 1) % 5], 1);            
            for (int i = 0; i < 5; i++)            
                for (int j = 0; j < 5; j++)                
                    A[i, j] = A[i, j] ^ D[i];                            
            //шаги ρ и π
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 5; j++)
                    B[j, (2 * i + 3 * j) % 5] = rot(A[i, j], r[i, j]);
            //шаг χ
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 5; j++)                
                    A[i, j] = B[i, j] ^ ((~B[(i + 1) % 5, j]) & B[(i + 2) % 5, j]);                
            //шаг ι
            A[0, 0] = A[0, 0] ^ RC;
            return A;
        }

        private ulong[,] Keccackf(ulong[,] A)
        {
            for (int i = 0; i < n; i++)
                A = roundB(A, RC[i]);
            return A;
        }
        //функция дополняет 16-чную строку до размер r-байт и преобразует ее в матрицу 64-битных слов
        private ulong[][] padding(string M, int r)
        {
            int size = 0;
            //дополняем сообщение до длины кратной r
            M = M + "01";
            while (((M.Length / 2) * 8 % r) != ((r - 8)))
            {
                M = M + "00";
            } ;
            M = M + "80";
            //получаем из скольки блоков длиной b-бит состоит сообщение
            size = (((M.Length / 2) * 8) / r);
            //инициальзируем массив массивов 64-битных слов 
            ulong[][] arrayM = new ulong[size][];
            arrayM[0] = new ulong[1600 / w];
            string temp = "";
            int count = 0;
            int j = 0;
            int i = 0;
            //конвертируем строковое представление в массив 64-битных слов
            foreach (char ch in M)
            {
                if (j > (r/w-1))
                {
                    j = 0;
                    i++;
                    arrayM[i] = new ulong[1600 / w];
                }
                count++;
                if ((count * 4 % w) == 0)
                {
                    arrayM[i][j] = Convert.ToUInt64(M.Substring((count - w / 4), w / 4), 16);
                    temp = ToReverseHexString(arrayM[i][j]);
                    arrayM[i][j] = Convert.ToUInt64(temp, 16);
                    j++;
                }

            }
            return arrayM;

        }
        private string ToReverseHexString(ulong S)
        {
            string temp = BitConverter.ToString(BitConverter.GetBytes(S).ToArray()).Replace("-", "");
            return temp;
        }
        private string ToHexString(ulong S)
        {
            string temp = BitConverter.ToString(BitConverter.GetBytes(S).Reverse().ToArray()).Replace("-", "");
            return temp;
        }
        //
        public string GetHash(string M, int r, int c, int d)
        {
            //Забиваем начальное значение матрицы S=0
            ulong[,] S = new ulong[5, 5];
            for (int i = 0; i < 5; i++)
                for (int j = 0; j < 5; j++)
                    S[i, j] = 0;
            ulong[][] P = padding(M, r);
            //Сообщение P представляет собой массив элементов Pi, 
            //каждый из которых в свою очередь является массивом 64-битных элементов 
            foreach (ulong[] Pi in P)
            {
                for (int i = 0; i < 5; i++)
                    for (int j = 0; j < 5; j++)
                        if((i + j * 5)<(r/w))
                            S[i, j] = S[i, j] ^ Pi[i + j * 5];
                Keccackf(S);
            }
            string Z = "";
            //добавляем к возвращаемой строке значения, пока не достигнем нужной длины
            do
            {
                for (int i = 0; i < 5; i++)
                    for (int j = 0; j < 5; j++)
                        if ((5*i + j) < (r / w))
                            Z = Z + ToReverseHexString(S[j, i]);
                Keccackf(S);
            } while (Z.Length < d*2);
            return Z.Substring(0, d * 2);
        }
    }


Скачать исходники вы можете отсюда.

P.S. все материалы и иллюстрации для этой статьи были найдены на официальном сайте хеш-функции Keccak.

UPD: fshp любезно поделился ссылкой на русскоязычное описание основных возможностей нового стандарта.

UPD2: после опубликовая статьи ко мне на почту обратился читатель с ником Admiral. Он предложил более оптимизированный код, в котором не используется работа со строками.
Реализация читателя Admiral
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    /*const */
    static private Byte InstanceNumber = 6;
    /*const */
    static private UInt16[] b_array = { 25, 50, 100, 200, 400, 800, 1600 }; //permutation_width
    /*const */
    static private Byte matrixSize = 5 * 5;
    /*const */
    static private Byte[] w_array = { 1, 2, 4, 8, 16, 32, 64 }; //b / 25;
    /*const */
    static private Byte[] l_array = { 0, 1, 2, 3, 4, 5, 6 }; //log(static_cast<float>(m_w)) / log(2.0F)
    /*const */
    static private Byte[] n_array = { 12, 14, 16, 18, 20, 22, 24 }; //12 + 2 * l -> number_of_permutation
    /*const */
    static private Byte[,] r = {
        {0, 36, 3, 41, 18},
        {1, 44, 10, 45, 2},
        {62, 6, 43, 15, 61},
        {28, 55, 25, 21, 56},
        {27, 20, 39, 8, 14}
    };
    /*const */
    static private UInt64[] RC = {//24 by w_array[KeccakInstanceCount - 1] (for 1600), for less please use less in w_array
        0x0000000000000001,
        0x0000000000008082,
        0x800000000000808A,
        0x8000000080008000,
        0x000000000000808B,
        0x0000000080000001,
        0x8000000080008081,
        0x8000000000008009,
        0x000000000000008A,
        0x0000000000000088,
        0x0000000080008009,
        0x000000008000000A,
        0x000000008000808B,
        0x800000000000008B,
        0x8000000000008089,
        0x8000000000008003,
        0x8000000000008002,
        0x8000000000000080,
        0x000000000000800A,
        0x800000008000000A,
        0x8000000080008081,
        0x8000000000008080,
        0x0000000080000001,
        0x8000000080008008
    };

    static private UInt64[,] B = new UInt64[5, 5];
    static private UInt64[] C = new UInt64[5];
    static private UInt64[] D = new UInt64[5];

    /*const*/
    static public UInt16[] rate_array = { 576, 832, 1024, 1088, 1152, 1216, 1280, 1344, 1408 };
    /*const*/
    static public UInt16[] capacity_array = { 1024, 768, 576, 512, 448, 384, 320, 256, 192 };
    public enum SHA3 { SHA512 = 0, SHA384, SHA256 = 3, SHA224 };

    static private UInt64[,] Keccak_f(UInt64[,] A)
    {
        for(Byte i = 0; i < n_array[InstanceNumber]; i++)
            A = Round(A, RC[i]);
        return A;
    }

    static private UInt64[,] Round(UInt64[,] A, UInt64 RC_i)
    {
        Byte i, j;

        //theta step
        for (i = 0; i < 5; i++)
            C[i] = A[i,0] ^ A[i,1] ^ A[i,2] ^ A[i,3] ^ A[i,4];
        for (i = 0; i < 5; i++)
            D[i] = C[(i + 4) % 5] ^ ROT(C[(i + 1) % 5], 1, w_array[InstanceNumber]);
        for (i = 0; i < 5; i++)
            for (j = 0; j < 5; j++)
                A[i,j] = A[i,j] ^ D[i];

        //rho and pi steps
        for (i = 0; i < 5; i++)
            for (j = 0; j < 5; j++)
                B[j,(2 * i + 3 * j) % 5] = ROT(A[i,j], r[i,j], w_array[InstanceNumber]);

        //chi step
        for (i = 0; i < 5; i++)
            for (j = 0; j < 5; j++)
                A[i,j] = B[i,j] ^ ((~B[(i + 1) % 5,j]) & B[(i + 2) % 5,j]);

        //iota step
        A[0,0] = A[0,0] ^ RC_i;

        return A;
    }

    static private UInt64 ROT(UInt64 x, Byte n, Byte w)
    {
        return ((x << (n % w)) | (x >> (w - (n % w))));
    }

    static private Byte[] Keccak(UInt16 rate, UInt16 capacity, List<Byte> Message)
    {
        //Padding
        Message.Add(0x01);

        UInt16 min = (UInt16)((rate - 8) / 8);
        UInt16 n = (UInt16)Math.Truncate((Double)(Message.Count / min));
        UInt32 messageFullCount = 0;
        if (n < 2)
        {
            messageFullCount = min;
        }
        else
        {
            messageFullCount = (UInt32)(n * min + (n - 1));
        }

        UInt32 delta = (UInt32)(messageFullCount - Message.Count);
        if ((Message.Count + delta) > UInt16.MaxValue - 1)
            throw (new Exception("Message might be too large"));

        /*Byte[] byteArrayToAdd = new Byte[delta];
        Message.AddRange(byteArrayToAdd);*/

        while (delta > 0)
        {
            Message.Add(0x00);
            delta--;
        }

        if ((Message.Count * 8 % rate) != (rate - 8))
            throw (new Exception("Length was incorect calculated"));

        Message.Add(0x80);
        /*const*/
        Int32 size = (Message.Count * 8) / rate;

        UInt64[] P = new UInt64[size * matrixSize];
        Int32 xF = 0, count = 0;
        Byte i = 0, j = 0;

        for(xF = 0; xF < Message.Count; xF++)
        {
            if (j > (rate / w_array[InstanceNumber] - 1))
            {
                j = 0;
                i++;
            }
            count++;
            if ((count * 8 % w_array[InstanceNumber]) == 0)
            {
                P[size * i + j] = ReverseEightBytesAndToUInt64(
                    Message.GetRange(count - w_array[InstanceNumber] / 8, 8).ToArray()
                    );
                j++;
            }
        }

        //Initialization
        UInt64 [,]S = new UInt64[5,5];
        for(i = 0; i < 5; i++)
            for(j = 0; j < 5; j++)
                S[i,j] = 0;

        //Absorting phase
        for(xF = 0; xF < size; xF++)
        {
            for(i = 0; i < 5; i++)
                for(j = 0; j < 5; j++)
                    if ((i + j * 5) < (rate / w_array[InstanceNumber]))
                    {
                        S[i, j] = S[i, j] ^ P[size * xF + i + j * 5];
                    }
            Keccak_f(S);
        }

        //Squeezing phaze
        Byte a = 0;
        Byte d_max = (Byte)(capacity / (2 * 8));
        List<Byte> retHash = new List<Byte>(d_max);

        for( ; ; )
        {
            for(i = 0; i < 5; i++)
                for(j = 0; j < 5; j++)
                    if((5 * i + j) < (rate / w_array[InstanceNumber]))
                    {
                        if(a >= d_max)
                            i = j = 5;
                        else
                        {
                            retHash.AddRange(FromUInt64ToReverseEightBytes(S[j, i]));
                            a = (Byte)retHash.Count;
                        }
                    }
            if(a >= d_max)
                break;
            Keccak_f(S);
        }

        return retHash.GetRange(0, d_max).ToArray();
    }

    static private UInt64 ReverseEightBytesAndToUInt64(Byte[] bVal)
    {
        UInt64 ulVal = 0L;
        for (Byte i = 8, j = 0; i > 0; i--)
        {
            ulVal += (UInt64)((bVal[i - 1] & 0xF0) >> 4) * (UInt64)Math.Pow(16.0F, 15 - (j++));
            ulVal += (UInt64)(bVal[i - 1] & 0x0F) * (UInt64)Math.Pow(16.0F, 15 - (j++));
        }
        return ulVal;
    }

    static private Byte[] FromUInt64ToReverseEightBytes(UInt64 ulVal)
    {
        Byte[] bVal = new Byte[8];
        Byte a = 0;
        do
        {
            bVal[a] = (Byte)((ulVal % 16) * 1);
            ulVal = ulVal / 16;
            bVal[a] += (Byte)((ulVal % 16) * 16);
            a++;
        }
        while (15 < (ulVal = ulVal / 16));
        while (a < 8)
        {
            bVal[a++] = (Byte)ulVal;
            ulVal = 0;
        }

        return bVal;
    }

    static void Main(String[] args)
    {
        if (args.Length < 1)
            return;
        List<Byte> MessageB;
        String message = string.Copy(args[0]);

        MessageB = strToByteList(message);
        String hash_224 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA224], capacity_array[(Byte)SHA3.SHA224], MessageB));
        MessageB = strToByteList(message);
        String hash_256 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA256], capacity_array[(Byte)SHA3.SHA256], MessageB));
        MessageB = strToByteList(message);
        String hash_384 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA384], capacity_array[(Byte)SHA3.SHA384], MessageB));
        MessageB = strToByteList(message);
        String hash_512 = ByteArrayToString(Keccak(rate_array[(Byte)SHA3.SHA512], capacity_array[(Byte)SHA3.SHA512], MessageB));

        Console.WriteLine("Message: " + message + "\r\n" +
                  "Hash_224: " + hash_224 + "\r\n" +
                  "Hash_256: " + hash_256 + "\r\n" +
                  "Hash_384: " + hash_384 + "\r\n" +
                  "Hash_512: " + hash_512 + "\r\n");
    }

    static List<Byte> strToByteList(String str)
    {
        List<Byte> ret = new List<byte>(str.Length);

        foreach(char ch in str)
        {
            ret.Add((Byte)ch);
        }

        return ret;
    }

    static public String ByteArrayToString(Byte[] b)
    {
        System.Text.StringBuilder sb = new System.Text.StringBuilder(16);
        for (Int32 i = 0; i < Math.Min(b.Length, Int32.MaxValue - 1); i++)
            sb.Append(String.Format("{0:X2}", b[i]));
        return sb.ToString();
    }
}

Share post

Comments 41

    +8
    Только одна мысль — «как они это делают?»
      +19
      Это также просто, как сидеть в контакте. Нужно только захотеть.
        +25
        В своё время мы обсуждали это с Димой Скляровым из элкомсофта и пришли к следующему мнению. Есть три функции — XOR, ADD и циклические сдвиги (wtf you name it), комбинация любых двух-трёх из которых вроде как не может быть обращена быстрее чем брутфорсом. Ну, попробуйте вычислить A, обратив формулу Y = ( (A ADD B) XOR C ) (n раз) по известным n, Y, B и C.
        Суть всех современных гражданских алгоритмов в том, что пихаем побольше циклов над этими функциями и местами размазываем глубокомудрыми константами, и вот он — профит! Главное — нигде не облажаться (такое на самом деле очень часто бывает).
        Однако, есть мнение (с), что всё-таки существует на порядки более эффективный, чем полный перебор, обратный алгоритм. Он не настолько эффективен, чтобы подделывать хэши и расшифровывать криптосообщения на обычном компе, но достаточно быстр, чтобы местная гэбня могла всё это сделать за почти-реальное время на топовом суперкомпьютере. Остюда, кстати, происходит и рост «разрядности» всех гражданских алгоритмов с относительно недавних 56 битов DES до вот уже 512 бит последних стандартов. Хотя полный перебор что 256, что тем более 2256 вариантов на обычном компьютере всё ещё в области фантастики.
        Серьезные же организации (типа военных) используют алгоритмы на эллиптических кривых (здесь три раза «Ку» товарищу Колмогорову и его последователям). Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.
          +5
          Но эскпорт этих алгоритмов до сих пор строжайше запрещен из всех стран, где эти самые последователи Колмогорова имеют место жить.

          Поясните, что именно, откуда и куда запрещено экспортировать.

          А то вот я тут в SSH ключик ecdsa уже года полтора успешно использую.
            0
            А, простите, в какой «серьезной» организации используется ecdsa?
            То, что маркетологи от ИТ проехались по мозгам людей-не-в-теме и рассказали им про преимущества эллиптических кривых еще не значит, что эти самые маркетологи способны/им позволено эту самую эллиптику грамотно реализовать. Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.

            По первой части вопроса — ну попробуйте «экспортировать» военную эллиптику из России или там США :) Ну ладно, даже не экспортировать, просто оформить форму допуска, чтобы узнать детали.
            Ну или хотя бы импортировать циску с криптомодулем.
              +5
              Теория заговора? Я такое люблю!
              Как объясните то, что на каждом углу нынче вон ЭЦП внедряется, вполне себе гражданское и очень даже на эллиптических кривых?
                +2
                ЭЦП на каждом углу? Это который по ГОСТу 34.10-2001? Так оно ж разработано гэбнёй из фапси на той самой эллиптике.
                Там если и есть закладки, то это наши, правильные закладки!
              +5
              Циску нет, но товарищ вам правильно указал на ecdsa. То что вы не доверяете реализации вполне нормально, но это не делает ее автоматически хуже мифической «военной».
                0
                Или что появятся какие-то математики-любители, которые смогут нигде не ошибиться и их при этом не вызовут на беседу.

                А как насчет нелюбителей?
              +4
              То-то фбр позорится и у любителей помощи просит в расшифровке винчестеров преступников, а в Англиях законы принимают об обязанности сообщить пароль к своей зашифрованной информацией, это все чтоб к военным и к гэбне не ходить вестимо.
                +9
                Что значит «экспорт алгоритмов»? В современном мире это понятие осталось в закостенелых умах генералов и законописцев. Нет больше никакого экспорта алгоритмов. Алгоритм либо общеизвестен (информация доступна), либо засекречен (информация недоступна). Передать сейчас информацию через границу в любое государство минуя все надзорные органы не проблема. Что запрещаем тогда?
                А запрещаем экспорт/импорт устройств, реализующих алгоритмы, которые реализовывать нельзя (но они при этом общеизвестны). Это ограничение появилось в до-ЭВМ эпоху, когда шифровальные системы представляли из себя законченное аппаратное решение и только в этом смысле формулировка целесообразна.
                Когда же появились вычислительные машины общего назначения, это ограничение попытались завязать и на них — это лишь вопрос идиотизма соответствующих ведомств, но никак не реального положения дел.
            • UFO just landed and posted this here
                +2
                Код на C# присутствует. Не Паскаль, но тоже вполне читаемый. Правда настораживает обилие конвертаций строка-число (в код не вчитывался, просто настораживает).
                  0
                  более кошерно писать на Java — чтобы везде запустить можно было на J2SE, J2ME и естественно JavaCard :)
                  (возможно даже портирую)
                    +1
                    Давайте, давайте. Нужно продвигать новые технологии в массы.:)
                  0
                  Я псевдокод слизал с сайта Keccak. Сейчас немного подправил, надеюсь стало понятнее.
                  • UFO just landed and posted this here
                      0
                      Ещё бы количество операций над строками уменьшить. Некошерно это. Почему паддинг идёт до преобразования строки в байты, а не после? Да ещё и не через StringBuilder, память замусоривается.
                        0
                        Да я и сам понимаю, что этот момент криво реализован. Но теперь это уже до следующей «неудачной» субботы:)
                    +3
                    >Или говоря по-русски, к сообщению дописывается единичный байт, необходимое количество нулей и весь этот ансамбль завершает байт со значением 0x80.
                    Если 2х байт не хватает, то дописать надо 0x01 и 0x80, верно?
                    А если одного байта не хватает, 0x01 или 0x80?
                      0
                      Видимо дополняется ещё 500 там с чем то (искать лень вверху) — 1 нулём. Т.е. 5xx-1
                        0
                        Судя по коду на C#
                        Всегда дописывается 0x01 к сообщению. А затем необходимое количество 0x00, чтобы (сообщение+1) стало кратным r и затем дописывается 0x80.
                        Таким образом, если не хватает одного байта, дописаны будут (r/8)+1 байт, если 2х то (r/8)+2 байт, а если сообщение уже кратно r то дописаны будут r/8 байт.
                          0
                          Там у меня в коде была ошибка. Но благодаря вам я ее уже исправил:)
                          Этот цикл должен выглядить не do{}while(), а while() do{}. Таким образом минимальное число добавляемых байт все таки 2(это если не хватает двух байт), а максимальное (r/8)+1(если не хватает 1 байта.
                          +1
                          Минимальное количество добавляемых байт-2. Максимальное r+8. Т.е. если не хватает 2-ух байт будут добавлены 01 и 80.
                          Если не хватает одного байта будут дописаны 01, r-8 нулей и 80.
                          +7
                          надеюсь воскресный вечер у Вас будет более удачным ))
                          +1
                          Статья то интересная. Но где инфа о равномерности распределения? Криптостойкости? Чем эта функция так хороша, что её приняли в качестве нового стандарта? Длинна хеша не удивила, значит вкусность в другом.
                            +5
                            Да это несомненно интересно. Но я не ставил перед собой цель сделать полный анализ хеш-функции. Я просто хотел разобраться как она реализована.
                            Так что всех подробностей я не знаю, но если кратко основная вкусность в том, что Keccak не использует функцию сжатия, в отличие от Sha-2 или Sha-1. Вместо функции сжатия используется псевдослучайная перестановка, собственно Sponge.
                            Это позволяет свести скойкость Keccak к модели случайного оракула.Т.е. создателям удалось постоить даказательство неразличимости Keccak от случайного оракула. И это в свою очередь позволяет говорить о Keccak, не просто как о хеш-функции, но как об универсальном криптопримитиве. Т.е. Без всяких дополнительных костылей Keccak можно использовать и для генерации псевдослучайного потока, и для вычисления MAC и для генерации ключей.
                          +6
                          А как это произносится?
                            +1
                            [kɛtʃak], like «ketchak»
                              +8
                              SHA-3 )
                                0
                                «Кечак» читается. Некоторые умудряются писать «кетчак», не осознавая, что [tʃ] — это [ч], и никакого «т» там в помине нет.
                                  +2
                                  Это не вполне так. Русское «ч» произносится как [t͡ɕ], то есть глухая переднеязычная аффриката, а [t͡ʃ] является глухой постальвеолярной аффрикатой, так что «т» там в помине, но есть, по крайней мере в русской транскрипции.

                                  «Cc» в данном случае восходит к итальянскому орфо-фонетическому менталитету создателей алгоритма, а это как раз [t͡ʃ], и на русский долгое итальянское «ч» передаётся традиционно как «чч» (Мартуччи, Феруччо, Пуччини, Уччелини), так что было бы верно писать либо как «Кеччак», в пользу итальянской традиции, или «Кетчак», в пользу английской (Бутч, матч, скотч, и протч.)
                                    +1
                                    Хм, не знал про различия между произношением «ч» в русском и английском. Спасибо за информацию.

                                    Если название а-ля итальянское, то мне «чч» по душе.
                                –3
                                на РНР, я так понял, никто еще не написал реализацию? Даже на Питоне на сайте лежит реализация 3.0, хотя описана версия 3.2. Чё-то медленно взлетает.

                              Only users with full accounts can post comments. Log in, please.