Оптимизация функции шифрования ГОСТ

Есть вот такой код. Что из него еще можно выжать?

Код (Text):

1.  
2. #define GOST_SYNCHRO_SIZE   8
3.  
4. #define OFFSET_GOST_SBOX1   0
5. #define OFFSET_GOST_SBOX2   256
6. #define OFFSET_GOST_SBOX3   512
7. #define OFFSET_GOST_SBOX4   768
8.  
9.  
10. #define MACRO_CHANGE_LINK(aa, bb)                   \
11. {                                                   \
12.     _asm{mov    eax, [ecx][aa]}                     \
13.     _asm{add    eax, edi}                           \
14.     _asm{mov    dl,  al}                            \
15.     _asm{mov    al,  [ebx][edx+OFFSET_GOST_SBOX1]}  \
16.     _asm{mov    dl,  ah}                            \
17.     _asm{mov    ah,  [ebx][edx+OFFSET_GOST_SBOX2]}  \
18.     _asm{ror    eax, 16}                            \
19.     _asm{mov    dl,  al}                            \
20.     _asm{mov    al,  [ebx][edx+OFFSET_GOST_SBOX3]}  \
21.     _asm{mov    dl,  ah}                            \
22.     _asm{mov    ah,  [ebx][edx+OFFSET_GOST_SBOX4]}  \
23.     _asm{ror    eax, 5}                             \
24.     _asm{xor    esi, eax}                           \
25.     _asm{mov    eax, [ecx][bb]}                     \
26.     _asm{add    eax, esi}                           \
27.     _asm{mov    dl,  al}                            \
28.     _asm{mov    al,  [ebx][edx+OFFSET_GOST_SBOX1]}  \
29.     _asm{mov    dl,  ah}                            \
30.     _asm{mov    ah,  [ebx][edx+OFFSET_GOST_SBOX2]}  \
31.     _asm{ror    eax, 16}                            \
32.     _asm{mov    dl,  al}                            \
33.     _asm{mov    al,  [ebx][edx+OFFSET_GOST_SBOX3]}  \
34.     _asm{mov    dl,  ah}                            \
35.     _asm{mov    ah,  [ebx][edx+OFFSET_GOST_SBOX4]}  \
36.     _asm{ror    eax, 5}                             \
37.     _asm{xor    edi, eax}                           \
38. }
39.  
40.  
41. int EncipherGOSTLinkEx(
42.     IN      CONST PVOID     pKey,
43.     IN      CONST PVOID     pSBox,
44.     OUT     PVOID           pDst,
45.     IN      CONST PVOID     pSrc,
46.     IN OUT  PVOID           pContext,
47.     IN      unsigned long   uLength)
48. {
49.     unsigned long   uCount;
50.  
51.     if(uLength % GOST_SYNCHRO_SIZE)
52.     {
53.         return(0);
54.     }
55.  
56.     _asm {
57.         pushad
58.         mov     eax,    uLength     // eax == uLength
59.         mov     uCount, eax
60.         mov     ebx,    pContext    // ebx == Synchro
61.         mov     eax,    pDst        // eax == pDst
62.         mov     esi,    [ebx]       // esi == Synchro[0]
63.         mov     edi,    [ebx+4]     // edi == Synchro[1]
64.         mov     ebx,    pSrc        // ebx == pSrc
65.         mov     ecx,    pKey        // ecx == pKey
66.         xor     esi,    [ebx]
67.         xor     edi,    [ebx+4]
68.         xor     edx,    edx
69. up:
70.         push    ebx
71.         push    eax
72.         xchg    esi,    edi
73.         mov     ebx,    pSBox       // ebx == SBox
74.     }
75.  
76.     MACRO_CHANGE_LINK(0,  4)
77.     MACRO_CHANGE_LINK(8,  12)
78.     MACRO_CHANGE_LINK(16, 20)
79.     MACRO_CHANGE_LINK(24, 28)
80.     MACRO_CHANGE_LINK(0,  4)
81.     MACRO_CHANGE_LINK(8,  12)
82.     MACRO_CHANGE_LINK(16, 20)
83.     MACRO_CHANGE_LINK(24, 28)
84.     MACRO_CHANGE_LINK(0,  4)
85.     MACRO_CHANGE_LINK(8,  12)
86.     MACRO_CHANGE_LINK(16, 20)
87.     MACRO_CHANGE_LINK(24, 28)
88.     MACRO_CHANGE_LINK(28, 24)
89.     MACRO_CHANGE_LINK(20, 16)
90.     MACRO_CHANGE_LINK(12, 8)
91.     MACRO_CHANGE_LINK(4,  0)
92.  
93.     _asm {
94.         pop     eax                 // eax == pDst
95.         mov     [eax],   esi       
96.         mov     [eax+4], edi
97.  
98.         // Сохранение контекста:
99.         mov     ebx,     pContext
100.         mov     [ebx],   esi
101.         mov     [ebx+4], edi
102.  
103.         pop     ebx                 // ebx == pSrc
104.  
105.         sub     uCount,  8
106.         jz      down1
107.  
108.         add     ebx,    8
109.         add     eax,    8
110.         xor     esi,    DWORD PTR [ebx]
111.         xor     edi,    DWORD PTR [ebx+4]
112.  
113.         jmp     up
114. down1:
115.         popad
116.     }
117.  
118.     return(1);
119. }
120.  

 

Может, заюзать SSE-регистры и в них хранить, скажем, ключ? Даст ли это какой-то выигрыш по скорости?

 

А цель этого выжимания ? (без шуток, просто непонятно, что именно тебе хочется)

 

Тут особо не выжмешь, в макросе ror eax,5 мешает, без него можно было бы распараллелить xor (~ на 30% увеличит производительность) путем перевода кода и таблицы SBOX на 32 бита

 

Скорости хочется конечно...

 

2bogrus: можно подробнее, что-то я не совсем понял. Это ror не спаривается чтоли или как? И что такое "путем перевода кода и таблицы SBOX на 32 бита"?

 

В MACRO_CHANGE_LINK 26 простых(одномопных) команд, которые PIII может выполнять по 3шт. за такт, т.е. теоретически в идеальном варианте код выполнялся бы за ~10 тактов, практически же выполняется ~50 из-за зависимостей и чтения eax после записей в al\ah (~ по 5 тактов пенальти)



Часть макроса выглядела бы так

Код (Text):

1. #define MACRO_CHANGE_LINK(aa, bb)                   \
2. {                                                   \
3.     _asm{mov    eax, [ecx][aa]}                     \
4.     _asm{add    eax, edi}                           \
5.     _asm{mov    edx, eax}                           \
6.     _asm{and    edx, 0xff}                          \
7.     _asm{shr    eax, 8}                             \
8.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX1]}\
9.     _asm{rol    esi, 8}                             \
10.     _asm{mov    edx, eax}                           \
11.     _asm{and    edx, 0xff}                          \
12.     _asm{shr    eax, 8}                             \
13.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX2]}\
14.     _asm{rol    esi, 8}                             \
15.     _asm{mov    edx, eax}                           \
16.     _asm{and    edx, 0xff}                          \
17.     _asm{shr    eax, 8}                             \
18.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX3]}\
19.     _asm{rol    esi, 8}                             \
20.     _asm{mov    edx, eax}                           \
21.     _asm{and    edx, 0xff}                          \
22.     _asm{shr    eax, 8}                             \
23.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX4]}\
24.     _asm{rol    esi, 8}                             \

Это "32-х битный код" он выполняется быстрее, но ror eax, 5 не позволяет такое(надо ещё подумать над этим), таблицу для такого кода надо увеличить в 4 раза, один элемент будет выглядеть не 1-м байтом 0х55, а 4-мя 0х00000055

 

Имхо, SSE ничего не даст, так как преобразование по S-блокам требует косвенного обращения к памяти, а регистр SSE нельзя использовать в качестве индекса для операций с памятью. Нужно переводить число в GPR, а это долго. Тем более, алгоритм ГОСТ изначально оптимизирован под 32-битные регистры.



Советую поиграть с кэш-памятью. Возможно, будет выгодным добавить prefetch.



Также попробуй mov dl, al поменять на movzx edx, al.



Выложи, пожалуйста, полный код в аттаче, чтобы любой желающий мог проверить свои (без)умные идеи, всего лишь заменив пару инструкций в коде и перекомпилировав твой проект. Еще лучше сделать и выложить тестилку, замеряющую время выполнения программы, и набор тестов, как это делали раньше на этом форуме.



bogrus Можно, конечно, реализовать как в каноническом алгоритме ГОСТ, т.е. выделять по маске байты перед тем, как отправить их на вход S-блока, а в конце сделать rol T, 11, но тогда сдвигов (инструкций rol/ror/shr) будет больше. Ты считаешь, что стОит увеличивать число сдвигов для того, чтобы убрать обращения к 8-битным регистрам?

 

Все дело в камне, для PIII это может повысить производительность в 2 раза, на каждом сдвиге eax после записи в al\ah мы теряем 6 тактов (это равноценно 6-ти сдвигам, на нем кстати и лучше пойдет shrd), можно и не ксорить сразу, а сперва собирать в отдельном регистре результат

 

Код:

483638169__GOST_Opt.rar

 

Потестируй такой макрос:

Код (Text):

1. #define MACRO_CHANGE_LINK(aa, bb)                   \
2. {                                                   \
3.     _asm{mov    eax, [ecx][aa]}                     \
4.     _asm{add    eax, edi}                           \
5.     _asm{ror    esi, 5}                             \
6.     _asm{mov    edx, eax}                           \
7.     _asm{shr    eax, 8}                             \
8.     _asm{and    edx, 0xff}                          \
9.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX1]}\
10.     _asm{ror    esi, 8}                             \
11.     _asm{mov    edx, eax}                           \
12.     _asm{shr    eax, 8}                             \
13.     _asm{and    edx, 0xff}                          \
14.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX2]}\
15.     _asm{ror    esi, 8}                             \
16.     _asm{mov    edx, eax}                           \
17.     _asm{shr    eax, 8}                             \
18.     _asm{and    edx, 0xff}                          \
19.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX3]}\
20.     _asm{ror    esi, 8}                             \
21.     _asm{mov    edx, eax}                           \
22.     _asm{shr    eax, 8}                             \
23.     _asm{and    edx, 0xff}                          \
24.     _asm{xor    esi, [ebx][edx*4+OFFSET_GOST_SBOX4]}\
25.     _asm{rol    esi, 3}                             \
26.  
27.     _asm{mov    eax, [ecx][bb]}                     \
28.     _asm{add    eax, esi}                           \
29.     _asm{ror    edi, 5}                             \
30.     _asm{mov    edx, eax}                           \
31.     _asm{shr    eax, 8}                             \
32.     _asm{and    edx, 0xff}                          \
33.     _asm{xor    edi, [ebx][edx*4+OFFSET_GOST_SBOX1]}\
34.     _asm{ror    edi, 8}                             \
35.     _asm{mov    edx, eax}                           \
36.     _asm{shr    eax, 8}                             \
37.     _asm{and    edx, 0xff}                          \
38.     _asm{xor    edi, [ebx][edx*4+OFFSET_GOST_SBOX2]}\
39.     _asm{ror    edi, 8}                             \
40.     _asm{mov    edx, eax}                           \
41.     _asm{shr    eax, 8}                             \
42.     _asm{and    edx, 0xff}                          \
43.     _asm{xor    edi, [ebx][edx*4+OFFSET_GOST_SBOX3]}\
44.     _asm{ror    edi, 8}                             \
45.     _asm{mov    edx, eax}                           \
46.     _asm{shr    eax, 8}                             \
47.     _asm{and    edx, 0xff}                          \
48.     _asm{xor    edi, [ebx][edx*4+OFFSET_GOST_SBOX4]}\
49.     _asm{rol    edi, 3}                             \
50. }

Но учти, таблицу BYTE SBox[GOST_SBOX_SIZE] надо переделать на DWORD или xor заменить на две команды:

Код (Text):

1.     _asm{movzx  edx, byte[ebx][edx+OFFSET_GOST_SBOX1]}\
2.     _asm{xor    esi, edx}                             \

 

Я не очень смотрел алго, но если S-box'ы статичны (те не пересчитываются в процессе шифрования блокофф), и если не жалко памяти, то можно заюзать две таблички 0x100 * 0x100 для SBOX1_SBOX2 и SBOX3_SBOX4, и доставать сразу WORD (а не два раза по байту).



ps Вообще надо стремицца к избежанию AGI, те команд, использующих результаты предидущих типа:



_asm{mov dl, al}

_asm{mov al, [ebx][edx+OFFSET_GOST_SBOX1]} ; USE EDX - AGI



но это тупая рекомендация о которой все и так знают

 

Андрей Винокуров 4 года потратил на работу с данным алгоритмом, лучше сходить на его страничку и глянуть чего там.

А там:

1. Ключ шифрования\дешифрования готовится сразу, то бишь есть 1,2,3,4,5,6,7,8 а ты аля 1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1

2. Если глянешь таблицу замен сразу увидешь что есть 4 по 2 строки, а лучше глянь в мою статью я там старался разжевать, как можно проще, то что увидел в исходниках А.Винокурова

 

Ну тут чтобы ваще без AGI никак не получаецца

 

bogrus

После использования такого макроса шифротекст получаецца отличным от того, который показывает исходный вариант.

 

Хотя по скорости раза в 3 быстрее.

 

Если я не туплю, то поправь 2 сдвига и попробуй ещё

Код (Text):

1. #define MACRO_CHANGE_LINK(aa, bb)                   \
2. {                                                   \
3.     _asm{mov    eax, [ecx][aa]}                     \
4.     _asm{add    eax, edi}                           \
5.     _asm{ro[b]l[/b]    esi, [b]16+[/b]5}                          \
6.         ...                                         \
7.     _asm{mov    eax, [ecx][bb]}                     \
8.     _asm{add    eax, esi}                           \
9.     _asm{ro[b]l[/b]    edi, [b]16+[/b]5}                          \
10.         ...                                         \
11. }                                                   \

 

bogrus

Похоже, все-таки тупишь )) Опять каша получаецца.

ЗЫ: Если чесна, не совсем твой код понимаю...

 

В макросе вроде все правильно (вот в аттаче), выдает такой-же результат как и твой, а в коде там смысл поубирать все задержки (т.е. можно сдвигать esi и ксорить побайтно с таблицей, а не собирать байты в частях eax, сдвигать его и ксорить с esi)

Код (Text):

1. mov eax,0x01234567              ; 00000001001000110100010101100111b
2. mov esi,0x89abcdef              ; 10001001101010111100110111101111b
3. ror eax,5    ; eax = 0x38091a2b = 00111000000010010001101000101011b
4. xor esi,eax  ; esi = 0xb1a2d7c4 = 10110001101000101101011111000100b
5.  
6. mov eax,0x01234567              ; 00000001001000110100010101100111b
7. mov esi,0x89abcdef              ; 10001001101010111100110111101111b
8. rol esi,5    ; esi = 0x3579bdf1 = 00110101011110011011110111110001b
9. xor esi,eax  ; esi = 0x345af896 = 00110100010110101111100010010110b
10. ror esi,5    ; esi = 0xb1a2d7c4 = 10110001101000101101011111000100b

957814723__macrotest.zip

 

Надо протестить на разных процах...