26 декабря 2012 г.

Алгоритм SHA-2 подвид SHA-256

А сегодня мои маленькие любители биткоинов будет небольшой вам подарок на новый год, мы рассмотрим основополагающий алгоритм этой криптовалюты под названием SHA-2 подвид SHA-256 на ассемблере. Да и в коментах к SHA-1 просили. В принципе со стороны коденья на асме, он даже немного легче чем SHA-1 ибо тут плоский матан, один только геморрой - набить небольшую кучку констант(копипаста утомляет).

Пока идут рождественские выходные - накидал небольшую програмку с алгоритмом SHA-2.
Итак, для тех, кто хочет узреть этот алгоритм, прошу под кат.

1. и 2. пункт делаем как в SHA1, смотрим соотвествующую запись. Это преобразование строки.
3. Объявляем теперь 8 регистров и 64 константы.

H0 = 6A09E667h
H1 = 0BB67AE85h
H2 = 3C6EF372h
H3 = 0A54FF53Ah
H4 = 510E527Fh
H5 = 9B05688Ch
H6 = 1F83D9ABh
H7 = 5BE0CD19h

Константы приводить не буду, чтобы не мусорить в тексте, их можно посмотреть на педевикии или в моих исходниках, ссылка на которые будет в конец этого поста. Массив костант у нас обзывается буковкой K.

4. Так как в случае SHA-256 у нас всего 64 итерации с 32битными двойными словами, а данных в текущий момент всего 64байта(512бит) необходимо добить эти данные до 2048бит(256байт).
Получившееся сообщение в пункте 1,2 оставляем без изменений, а сразу за ним вычисляем оставшиеся 192байта(48 двойных слов) следующим образом.
Определим W[0] - как указатель на начало сообщения которое получили в пунтке 1 и 2, тогда указатель на дополненные данные выглядит как W[16], если обозначим W[i]то формулы выглядит так:
s0 = (W[i-15] ROTR 7) XOR (W[i-15] ROTR 18) XOR (W[i-15] SHR 3) 
s1 = (W[i-2] ROTR 17) XOR (W[i-2] ROTR 19) XOR (W[i-2] SHR 10) 
W[i] = W[i-16] + s0 + W[i-7] + s1
Где ROTR - цикличный сдвиг в право на n позиций.
Где SHR - просто сдвиг в право на n позиций.
И так, пока не достигнем 63 позиции, итого мы получили 192байт всякого "мусора" и это хорошо. :)

5. Перемещаем 8 регистров во временные с которыми будем работать.
A = H0 
B = H1 
C = H2 
D = H3 
E = H4
F = H5
G = H6
H = H7

6. Основной цикл будет выглядеть в псевдо коде както так:
for i from 0 to 63 { 
      S0 = (A ROTR 2) XOR (A ROTR 13) XOR (A ROTR 22)
      maj = (A AND B) XOR (A AND C) XOR (B AND C)
      t2 = S0 + maj 
      S1 = (E ROTR 6) XOR (E ROTR 11) XOR (E ROTR 25)
      t1 = H + S1 + ch + K[i] + W[i]
      H = G
      G = F
      F = E
      E = D + t1 
      D = C 
      C = B 
      B = A 
      A = t1 + t2 
}
Как видно из этого псевдо кода, совершенно ничего сложного, даже подфункции не надо было писать. Все линейно.

7. А теперь складываем основные регистры со временными, что в них получилось, и хэш для SHA-256 готов.

H0 = H0 + A
H1 = H1 + B
H2 = H2 + C
H3 = H3 + D
H4 = H4 + E
H5 = H5 + F
H6 = H6 + G
H7 = H7 + H

8. Выстраиваем их друг за другом и получаем собственно хэш, для Bearchik он выглядеть будет вот так: cb87ebd655337a266289377c8c9bf27e1e1cda972e260944c026775d13e078a7

Ну а теперь мал мал говнокодъа на асме. 
Я не буду расписывать функции которые я описывал в SHA1, об них можно почитать в соответствующей теме, или посмотреть исходники.
Опишу только основные 4ый и 6ый пункты.

Пункт 4, дополняем сообщение до 256байт
Не забываем, в edi у нас указатель на 16ую позицию в сообщении.
lea        eax,  mkey ; в eax ссылка на сообщение
    mov        ebx, edi ; копируем текущий адрес в сообщении
    sub        ebx, eax ; отнимаем от текущей позиции нулевую, чтобы узнать сколько надо добавить данных
    shr        ebx, 2h ; умножаем на 4
    mov        eax, 40h ; копируем в eax 64
    sub        eax, ebx ; отнимаем и получаем количество итераций

@@:
;s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
    push    eax ; сохраним eax
    mov        ebx, DWORD PTR [edi-15*4h] ; в ebx копируем позицию W[i-15]
    ror        ebx, 7 ; сдвигаем циклично в право на 7
    mov        edx, DWORD PTR [edi-15*4h] ; в edx копируем позицию W[i-15]
    ror        edx, 18 ; сдвигаем циклично в право на 18
    xor        ebx, edx ; делаем XOR между ebx и edx
    mov        edx, DWORD PTR [edi-15*4h] ; в edx копируем позицию W[i-15]
    shr        edx, 3 ; свдигаем в право на 4 
    xor        ebx, edx ; делаем XOR между ebx и edx

;s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
    mov        eax, DWORD PTR [edi-2*4h] ; в eax копируем позицию W[i-2]
    ror        eax, 17 ; сдвигаем циклично в право на 17
    mov        edx, DWORD PTR [edi-2*4h] ; в edx копируем позицию W[i-2]
    ror        edx, 19 ; сдвигаем циклично в право на 19
    xor        eax, edx ; делаем XOR между eax и edx
    mov        edx, DWORD PTR [edi-2*4h] ; в edx копируем позицию W[i-2]
    shr        edx, 10 ; свдигаем в право на 10
    xor        eax, edx ; делаем XOR между eax и edx

;w[i] := w[i-16] + s0 + w[i-7] + s1    
    mov        edx, DWORD PTR [edi-16*4h] ; в edx копируем позицию W[i-16]
    add        edx, ebx ; делаем add между edx и ebx
    add        edx, DWORD PTR [edi-7*4h] ; в edx копируем позицию W[i-7]
    add        edx, eax ; делаем add между edx и ebx
    mov        DWORD PTR [edi], edx ; записываем что получилось на позицию W[i]
    
    add        edi, 4 ; сдвигаем указатель на следующую позицию
    inc        ecx ; увеличиваем ecx
    pop        eax ; востанавливаем eax
    .if    ecx < eax ; пока ecx меньше eax
        jmp        @b ; обрабатываем следующую позицию
    .endif

Пункт 6. Оновной математический цикл.


xor        ecx, ecx ; обнуляем счетчик
    lea        edi, mkey ; в edi помещаем ссылку на начало сообщения
mainloop: ; метка для основного цикла
;S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    mov        eax, aav ; в eax помещаем временный регистр A
    ror        eax, 2 ; сдвигаем циклично в право на 2
    mov        edx, aav ; в edx помещаем временный регистр A
    ror        edx, 13 ; сдвигаем циклично в право на 13
    xor        eax, edx ; делаем XOR между eax и edx
    mov        edx, aav ; в edx помещаем временный регистр A
    ror        edx, 22 ; сдвигаем циклично в право на 22
    xor        eax, edx ; делаем XOR между eax и edx

;maj := (a and b) xor (a and c) xor (b and c)
    mov        ebx, aav ; в ebx помещаем временный регистр A
    and        ebx, bbv : делаем AND между A и B
    mov        edx, aav ; в edx помещаем временный регистр A
    and        edx, ccv : делаем AND между A и C
    xor        ebx, edx ; Делаем XOR между первыми выражениями
    mov        edx, bbv ; в edx помещаем временный регистр B
    and        edx, ccv : делаем AND между B и C
    xor        ebx, edx ; Делаем XOR между вторыми выражениями

;t2 := S0 + maj
    add        eax, ebx ; тупо складываем то что получилось выше
    mov        t2, eax ; копируем во временную переменную t2
    
;S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    mov        eax, eev ; в eax помещаем временный регистр E
    ror        eax, 6 ; сдвигаем циклично в право на 6
    mov        edx, eev ; в edx помещаем временный регистр E
    ror        edx, 11 ; сдвигаем циклично в право на 11
    xor        eax, edx ; Делаем XOR между первыми выражениями
    mov        edx, eev ; в edx помещаем временный регистр E
    ror        edx, 25 ; сдвигаем циклично в право на 25
    xor        eax, edx ; Делаем XOR между вторыми выражениями
    
;ch := (e and f) xor ((not e) and g)
    mov        ebx, eev ; в ebx помещаем временный регистр E
    and        ebx, ffv ; делаем AND между E и F
    mov        edx, eev ; в edx помещаем временный регистр E
    not        edx ; делаем NOT над E
    and        edx, ggv ; делаем AND между NOT(E) и G
    xor        ebx, edx ; Делаем XOR между первыми выражениями
    
;t1 := h + S1 + ch + k[i] + w[i]
    add        eax, hhv ; складываем S1 и H
    add        eax, ebx ; прибавляем ch
    add        eax, DWORD PTR [K+ecx*4h] ; прибавляем K[i]
    add        eax, DWORD PTR [mkey+ecx*4h] ; прибавляем [Wi]

;h := g    
    mov        ebx, ggv ; G
    mov        hhv, ebx ; в H
    
;g := f
    mov        ebx, ffv : F
    mov        ggv, ebx : в G
    
;f := e
    mov        ebx, eev ; E
    mov        ffv, ebx ; в F
    
;e := d + t1
    mov        ebx, ddv ; копируем в ebx D
    add        ebx, eax ; складываем с t1
    mov        eev, ebx ; пишем в E
    
;d := c
    mov        ebx, ccv : C
    mov        ddv, ebx : в D
    
;c := b
    mov        ebx, bbv ; B
    mov        ccv, ebx ; в С
    
;b := a
    mov        ebx, aav ; A
    mov        bbv, ebx ; в B
    
;a := t1 + t2
    add        eax, t2 ; складываем eax с t2
    mov        aav, eax ; записываем в eax
    
    
    
    inc        ecx ; увеличиваем счетчик на 1
    .if        ecx < 40h ; пока меньше 64
        jmp        mainloop ; идем на следующий круг
    .endif

Вообщем както так, исходник можно посмотреть как обычно на pastebin.
Исходники и скомпилированная программа на депозите.
Удачного нового года и рождества :)

1 комментарий:

  1. Урааааа! Спасибо! Автору респект огромный!

    ОтветитьУдалить