Реализация алгоритма SHA256 не возвращает ожидаемый результат

ProgramBox

Реализация алгоритма SHA256 не возвращает ожидаемый результат

Post author:admin
Запись опубликована:27 февраля, 2023
Post category:Вопросы по программированию

#c #sha256

Вопрос:

С помощью приведенной ниже реализации, основанной на псевдокоде, доступном здесь, я пытаюсь преобразовать строку, сгенерированную с помощью конкатенации членов из этого класса:

 class BlockHeader
{
private:
  int version;
  string hashPrevBlock;
  string hashMerkleRoot;
  int time;
  int bits;
  int nonce;
}

в хэш SHA256, как это было сделано с помощью приведенного ниже кода python, доступного здесь:

 >>> import hashlib
>>> header_hex = ("01000000"  
 "81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000"  
 "e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b"  
 "c7f5d74d"  
 "f2b9441a"  
 "42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

Я ожидаю, что моя программа вернет тот же результат, что и вышеприведенная программа, но вместо этого, когда я компилирую и запускаю это:

 int main() {
  BlockHeader header;
  header.setVersion(0x01000000);
  header.setHashPrevBlock("81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000");
  header.setHashMerkleRoot("e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b");
  header.setTime(0xc7f5d74d);
  header.setBits(0xf2b9441a);
  header.setNonce(0x42a14695);

  Sha256 hash1(header.bytes());
  array<BYTE, SHA256_BLOCK_SIZE> h1 = hash1.hash();

  cout << "hash1: ";
  for(int i=0; i<h1.size(); i  )
    printf("%.2x", h1[i]);
  printf("n");

  Sha256 hash2(h1);
  array<BYTE, SHA256_BLOCK_SIZE> h2 = hash2.hash();

  cout << "hash2: ";
  for(int i=0; i<h2.size(); i  )
    printf("%.2x", h2[i]);
  printf("n");
}

результатом является то, что:

 hash1: e2245204380a75c6bc6ac56f0000000040030901000000001100011000000000
hash2: 68a74f2a36c8906068c6cd6f00000000020000000000000080a7d06f00000000

Я знаю, что конечность в моей программе отличается от результата python, но это я могу исправить позже, когда получу правильный результат. Глядя в приведенный ниже код, может кто-нибудь дать подсказку о том, чего мне здесь не хватает?

 #define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b))))
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b))))

#define CH(x,y,z) (((x) amp; (y)) ^ (~(x) amp; (z)))
#define MAJ(x,y,z) (((x) amp; (y)) ^ ((x) amp; (z)) ^ ((y) amp; (z)))

#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))

#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

Sha256::Sha256(vector<BYTE> data) {
    SIZE64 L = data.size() / 2;
    SIZE64 K = 0;
    while( (L   1   K   8) % 64 != 0)
        K = K   1;

    for(int i=0; i<L; i  ) {
        BYTE c = (data[i] % 32   9) % 25 * 16   (data[i 1] % 32   9) % 25;
        source.push_back(c);
    }

    source.push_back(0x80);

    for(int i=0; i<K; i  )
        source.push_back(0x00);

    SIZE64 x = L   1   K   8;
    for(int i=0; i<sizeof(x); i  )
        source.push_back( x >> i*8 );
}

Sha256::Sha256(array<BYTE, SHA256_BLOCK_SIZE> data) {
    SIZE64 L = data.size() / 2;
    SIZE64 K = 0;
    while( (L   1   K   8) % 64 != 0)
        K = K   1;

    for(int i=0; i<L; i  ) {
        BYTE c = (data[i] % 32   9) % 25 * 16   (data[i 1] % 32   9) % 25;
        source.push_back(c);
    }

    source.push_back(0x80);

    for(int i=0; i<K; i  )
        source.push_back(0x00);

    SIZE64 x = L   1   K   8;
    for(int i=0; i<sizeof(x); i  )
        source.push_back( x >> i*8 );
}

array<BYTE, SHA256_BLOCK_SIZE> Sha256::hash() {
    array<BYTE, SHA256_BLOCK_SIZE> resu<

    WORD32 h0 = 0x6a09e667, h1 = 0xbb67ae85, h2 = 0x3c6ef372, h3 = 0xa54ff53a, h4 = 0x510e527f, h5 = 0x9b05688c, h6 = 0x1f83d9ab, h7 = 0x5be0cd19;

    WORD32 k[64] = {0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2};

    WORD32 a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];

    for(int chunk=0; chunk<=source.size()/64; chunk  ) {
        for (i = 0, j = chunk*64; i < 16;   i, j  = 4)
            m[i] = (source[j] << 24) | (source[j   1] << 16) | (source[j   2] << 8) | (source[j   3]);
        for ( ; i < 64;   i)
            m[i] = SIG1(m[i - 2])   m[i - 7]   SIG0(m[i - 15])   m[i - 16];

        a = h0;
        b = h1;
        c = h2;
        d = h3;
        e = h4;
        f = h5;
        g = h6;
        h = h7;

        for (i = 0; i < 64;   i) {
            t1 = h   EP1(e)   CH(e,f,g)   k[i]   m[i];
            t2 = EP0(a)   MAJ(a,b,c);
            h = g;
            g = f;
            f = e;
            e = d   t1;
            d = c;
            c = b;
            b = a;
            a = t1   t2;
        }

        h0  = a;
        h1  = b;
        h2  = c;
        h3  = d;
        h4  = e;
        h5  = f;
        h6  = g;
        h7  = h;
    }

    for(int i=0; i<4; i  ) result[0] = h0 >> i;
    for(int i=0; i<4; i  ) result[1] = h1 >> i;
    for(int i=0; i<4; i  ) result[2] = h2 >> i;
    for(int i=0; i<4; i  ) result[3] = h3 >> i;
    for(int i=0; i<4; i  ) result[4] = h4 >> i;
    for(int i=0; i<4; i  ) result[5] = h5 >> i;
    for(int i=0; i<4; i  ) result[6] = h6 >> i;
    for(int i=0; i<4; i  ) result[7] = h7 >> i;

  return resu<
}

1. Какова цель for(int i=0; i<4; i ) result[0] = h0 >> i; ?

2. Выдать конечное хэш-значение? Что будет возвращено вызывающей стороне?

3. Но почему сдвиги? Я не вижу этого в алгоритме. И почему цикл? Вы перезаписываете результат снова с каждым циклом; вы фактически написали: result[0] = h0; result[0] = h0 >> 1; result[0] = h0 >> 2; result[0] = h0 >> 3; где каждый перезаписывает последний, так что это эквивалентно простому выполнению result[0] = h0 >> 3 . И я не думаю, что вы должны отбросить эти три верхних бита, не так ли?

4. Хорошо, я помню причину цикла: as result является массивом и h0...h7 имеет тип WORD (unsigned int), который имеет 4 байта, я перемещаю каждый байт из h0...h7 в один элемент массива.

5. Правильно, это имеет больше смысла. В этом случае вам понадобятся сдвиги на 24, 16 и 8 бит, а не на 1,2,3, и вам также потребуется увеличить индекс результата для каждого цикла: h0 должны быть записи 0-3 результата, записи h1 4-7 и т.д.

Ответ №1:

В Sha256::hash функции result является BYTE массивом, тогда h0 как является WORD32 . Возможно, вы захотите разделить h0 на 4 BYTE секунды и сохранить в result массив, но цикл for в конце функции не достигнет вашей цели.

Что вы хотите сделать, это объединить h0 в h7 , а затем извлечь байты из h0 в h7 , сдвинув 24, 16, 8, 0 бит:

 // concatenate h0 to h7
WORD32 hs[8] = {h0, h1, h2, h3, h4, h5, h6, h7};

// extract bytes from hs to result
for(int i=0; i<8; i  ) { // loop from h0 to h7
    result[i*4  ] = hs[i] >> 24; // the most significant byte of h_i
    result[i*4 1] = hs[i] >> 16;
    result[i*4 2] = hs[i] >> 8;
    result[i*4 3] = hs[i];       // the least significant byte of h_i
}

Редактировать

После некоторого тестирования я обнаружил еще одну ошибку:

 for(int chunk=0; chunk<=source.size()/64; chunk  ) {
                      ^^

должно быть

 for(int chunk=0; chunk<source.size()/64; chunk  ) {
                      ^

chuck начинается с 0, поэтому вы должны использовать < вместо <= .
Например, когда source.size() равно 64, у вас есть только 1 фрагмент для обработки.

ПРАВКА2

Я полностью протестировал ваш код и обнаружил две проблемы в конструкторах Sha256 класса.

Ваш код подразумевает, что вы предполагаете vector<BYTE> , что переданное конструктору является шестнадцатеричной строкой. Это нормально, но вы используете тот же код для array<BYTE, SHA256_BLOCK_SIZE> версии, которая является типом возвращаемой hash() функции, которая возвращает BYTE массив вместо шестнадцатеричной строки.

Для BYTE массива вы можете просто вставить байт data[i] в source . Кроме того, L должно быть data.size() потому, что каждый элемент имеет размер 1 в байтовом массиве.

Кроме того, вы пытаетесь добавить размер ввода ( x ) к source , но x не должны включать добавленную единицу и нули, и это количество битов ввода, поэтому x должно быть просто L*8 . Кроме того, размер должен быть целым числом с большим порядком, поэтому сначала вам нужно нажать больший байт:

 for(int i=0; i<sizeof(x); i  ) // WRONG: little endian
for(int i=sizeof(SIZE64)-1; i>=0; i--) // Correct: big endian

Я заставил его выполнить правильно и вывести:

 hash1: b9d751533593ac10cdfb7b8e03cad8babc67d8eaeac0a3699b82857dacac9390
hash2: 1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000

Если вы столкнетесь с другими проблемами, не стесняйтесь спрашивать. Вы очень близки к правильному ответу. Надеюсь, вы сможете успешно исправить все ошибки 🙂

ПРАВКА3: реализация другой функции

 struct BlockHeader {
    int version;
    string hashPrevBlock;
    string hashMerkleRoot;
    int time;
    int bits;
    int nonce;
    vector<BYTE> bytes();
};

#define c2x(x) (x>='A' amp;amp; x<='F' ? (x-'A' 10) : x>='a' amp;amp; x<='f' ? (x-'a' 10) : x-'0')
vector<BYTE> BlockHeader::bytes() {
    vector<BYTE> bytes;
    for (int i=24; i>=0; i-=8) bytes.push_back(version>>i);
    for (int i=0; i<hashPrevBlock.size(); i =2)
        bytes.push_back(c2x(hashPrevBlock[i])<<4 | c2x(hashPrevBlock[i 1]));
    for (int i=0; i<hashMerkleRoot.size(); i =2)
        bytes.push_back(c2x(hashMerkleRoot[i])<<4 | c2x(hashMerkleRoot[i 1]));
    for (int i=24; i>=0; i-=8) bytes.push_back(time>>i);
    for (int i=24; i>=0; i-=8) bytes.push_back(bits>>i);
    for (int i=24; i>=0; i-=8) bytes.push_back(nonce>>i);
    return bytes; // return bytes instead of hex string
}

 // exactly the same as the vector<BYTE> version
Sha256::Sha256(array<BYTE, SHA256_BLOCK_SIZE> data) {
    SIZE64 L = data.size(); // <<
    SIZE64 K = 0;
    while( (L   1   K   8) % 64 != 0)
        K = K   1;
    // can be simplified to: int K = (128-1-8-Ld)d;

    // ** thanks to "chux - Reinstate Monica" pointing out i should be a SIZE64
    for(SIZE64 i=0; i<L; i  ) { // **
        source.push_back(data[i]); // <<
    }

    source.push_back(0x80);

    for(int i=0; i<K; i  )
        source.push_back(0x00);

    SIZE64 x = L*8; // <<
    for(int i=sizeof(SIZE64)-1; i>=0; i--) { // big-endian
        source.push_back(x >> i*8);
    }
}

ПРАВКА4: размер переменной в цикле for

Как указала «chux — Reinstate Monica», это может быть проблемой, если размер данных больше, чем INT_MAX . Все циклы for, использующие размер в качестве верхнего предела, должны использовать size_t счетчик типов (вместо int ), чтобы предотвратить эту проблему.

 // in BlockHeader::bytes()
for (size_t i=0; i<hashPrevBlock.size(); i =2)
// in Sha256::hash()
for (size_t chunk=0; chunk<source.size()/64; chunk  )
// in main()
for (size_t i=0; i<h1.size(); i  )
for (size_t i=0; i<h2.size(); i  )

Обратите внимание, что size_t это unsigned . Обратная версия не будет работать, потому i что никогда не бывает меньше 0.

 for (size_t i=data.size()-1; i>=0; i--) // infinite loop

1. часть о x выполняется в обоих конструкторах? Я только что внес предложенные вами изменения, но все равно получаю разные результаты.

2. Я также попробовал версию только с 1 конструктором: pastebin.com/ihHd8dvD / pastebin.com/0F8jQ6Sz

3. Я думаю, что моя проблема может заключаться в том, что я пытаюсь преобразовать класс BlockHeader в строку. Как вы это делаете в своем тесте? Используете ли вы a struct или у вас есть метод, возвращающий a vector с данными класса? код: pastebin.com/0gHyANi2

4. Я отредактировал свой ответ, чтобы обеспечить реализацию другой функции. Да, я использовал struct для упрощения теста. И я преобразую BlockHeader в массив байтов вместо строки. (См. Мой отредактированный ответ)

5. for(int i=0; i<data.size(); i ) является проблемой, когда data.size() > INT_MAX .