Необычный старый крякми (crackme)

Сделал все байты. Увы, с распаралеливанием у меня совсем никак... % не стал выводить, ибо чтобы их посчитать делить надо каждую итерацию... По нажатию любой клавиши выводится текущий пароль и число уже проверенных. Если найдет правильный пароль - выведет его в ascii и в hex .

 

Tronix
Знаете, что надо еще? чтобы можно было продолжить с заданной итерации. И почему бы не выводить при нажатии на энтер % да надо делить, но я не буду тыкать без умолку). Хотя если ты напишешь продолжение с определенного номера, то и разбить по потоком не должно быть проблемой) вообще я сам мало верю в возможность перебора, просто интересно посмотреть до куда дойдет.

 

Да, вот что значит отвечать после 11-часового рабочего дня.

Конечно в моем посте выше следует читать "система из 256 переменных", и далее :

"Если пароль автора 32 символа или меньше, он будет определен однозначно за миллисекунды.
Если пароль был длиннее 32 символов, алгоритм даст какую-то 32-байтную строку, ..."

Любой циклический код является линейным (здесь в терминах операции сложения по модулю "2").
То есть любой выходной бит можно представить в виде суммы по модулю 2 некоторых входных бит
(исходного заполнения и строки пароля).

Выходной объем информации в данном кракми - 8х32 бит (256 бит), следовательно,
имеем линейную систему из 256 уравнений. Т.к. система линейна и, я полагаю, независима,
то она будет однозначно определяема при ровно 256 неизвестных (32-байтном или более коротком пароле),
а при большем количестве неизвестных - она станет переопределенной, т.е. будут возможны разные
наборы являющиеся решениями.

По-прежнему утверждаю, что решение линейной системы из 256 неизвестных по модулю 2 занимает
миллисекунды на современной компьютерной технике.

 

Попытаюсь привести пример на 3-битном коде на основе полинома 101,
старший бит слева, сдвиг производим слева направо.

Начальное состояние CRC :
(c; b; a)

Добавляем один бит из обрабатываемой строки "p0" и на основании значения "(крайний правый бит) XOR p0", т.е. "(a) XOR p0" изменяем 2-ой и 0-ой биты (те которые равны "1" в образующем полиноме 101) (биты "предыдущего" значения CRC при этом сдвинулись на 1 позицию вправо):
(a XOR p0; c; b XOR a XOR p0)

Добавляем следующий бит из обрабатываемой строки "p1" и на основании значения "(b XOR a XOR p0) XOR p1" изменяем 2-ой и 0-ой биты :
(b XOR a XOR p0 XOR p1; a XOR p0; c XOR b XOR a XOR p0 XOR p1)

Добавляем последний бит из обрабатываемой строки "p2" и на основании значения "(c XOR b XOR a XOR p0 XOR p1) XOR p2" изменяем 2-ой и 0-ой биты :
(c XOR b XOR a XOR p0 XOR p1 XOR p2; b XOR a XOR p0 XOR p1; a XOR p0 XOR c XOR b XOR a XOR p0 XOR p1 XOR p2)

Пусть итоговое значение было равно 110. Имеем :

c XOR b XOR a XOR p0 XOR p1 XOR p2 = 1
b XOR a XOR p0 XOR p1 = 1
a XOR p0 XOR c XOR b XOR a XOR p0 XOR p1 XOR p2 = 0

Не забываем, что мы знаем начальное заполнение (c; b; a). Например, 000.

Тогда :

p0 XOR p1 XOR p2 = 1
p0 XOR p1 = 1
p1 XOR p2 = 0

дает нам линейную систему из 3 уравнений с 3 неизвестными в матричном виде :

1 1 1 | 1
1 1 0 | 1
0 1 1 | 0

которая решается единственным образом : p0=1, p1=0, p2=0.

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

 

Алгоритм решения уже рассказал OLS.
В случае, когда разрешены любые значения символов в строке, при 32 символах решение единственно, при меньших значениях решений нет, а дальше число решений начинает расти, умножаясь на 256 с каждым новым байтом. Решение из 32 символов в hex-виде:
DF 88 04 11 E4 3E 7C 7E
65 AC 62 65 E1 EE AC E8
FB 6D A4 F6 FB EF 73 B2
F0 7E F7 A4 F6 FF 73 F8
Если ограничиться только символами из первой половины ASCII-таблицы, то принцип решения тот же, только из каждого байта возникает не 8, а только 7 битовых переменных. Ситуация здесь несколько интереснее из-за того, что матрица системы вырождается, в результате чего решение может существовать только при определённых размерах строк (поскольку инициализация CRC здесь традиционная из 0xFFFFFFFF, то свободный член в уравнениях зависит от длины строки) - в данном случае длина должна быть 36. При этом есть 28 свободных бит и, соответственно, 2^28 решений с нулевым старшим битом во всех байтах. Если, например, взять все решения, состоящие только из букв A-Z,a-z, цифр 0-9 и пробела, получается следующий список (полный):

jebe wnty1syb6bett1rnb6kizt eye1dbtb
jtse wneh1bys6bete rns6kxkt1tyt dbeb
ifbf wmwy1sza5beww1qmb6kiyw fze2dbwa
jfaf wnwz2pyb5betw2qna6hizt eye1data
ieae wmtz2pza6bewt2rma6hiyw fze2dawb
jdcd wnux0ryb7betu0snc6jizt eye1dctc
kuse wodh0bxs6beud ros6jyku0txu dceb
lebc whty1uyd0bert1thd0mizt eye1bdrd
ltsc wheh1dyu0bere thu0mxkt1tyt bdcd
ldcb whux0tyd1beru0uhe0lizt eye1bere
ogca wkvx0tzg2beqv0vke0liyw fze2beqf
musc widh0dxu0besd tiu0lyku0txu becd
oeac wktz2vzg0beqt2tkg0niyw fze2bgqd
mtbs wiey eht bese1dit lxze1eht1rebt
mess with the best die like the rest
kgce wovx0pzc6beuv0roa4hiyw fze2faub
ofac wkwz2uyg0beqw2tkd3mizt eye1adqd
lgcb whvx0wzd1berv0uhf3oiyw fze2afre
odca wkux0wyg2bequ0vkf3oizt eye1afqf
lfbc whwy1vzd0berw1thg3niyw fze2agrd
jusd wndh0cxr7betd snr7kyku0txu ebdc
kdce woux0syc6beuu0rob7kizt eye1ebub
ktsd woeh1cyr7beue sor7jxkt1tyt ecdc
kebd woty1ryc7beut1soc7jizt eye1ecuc
lusb whdh0ext1berd uht1myku0txu cdbe
mdcc wiux0uye0besu0tid1mizt eye1cdsd
neab wjtz2wzf1bept2ujf1oiyw fze2cfpe
mfaa wiwz2wye2besw2vif1oizt eye1cfsf
nfba wjwy1tzf2bepw1vje1liyw fze2cepf
mtsb wieh1eyt1bese uit1lxkt1tyt cebe
mebb wity1tye1best1uie1lizt eye1cese
jeaf wntz2szb5bett2qnb5kiyw fze2gbta
ifae wmwz2sya6beww2rmb5kizt eye1gbwb
jfbe wnwy1pzb6betw1rna5hiyw fze2gatb
itsf wmeh1ayp5bewe qmp5hxkt1tyt gafa
iebf wmty1pya5bewt1qma5hizt eye1gawa

Внимательный читатель, несомненно, выделит один из вариантов, который явно был исходным паролем, но подходит любой из вышеприведённых.

 

diamond,OLS - Браво!
Тоже пытаюсь систему уравнений составить - возник вопрос (знаний не хватает в этой области):

Как учесть тот факт, что

Код (Text):

1. table[BYTE(crc32[i] xor longint(ord(pwd[n])))]

- выбираемый элемент полинома зависит от предыдущего значения crc и текущего значения байта из пароля.
Пока на ум лезет только такая система уравнений:

Код (Text):

1.  CRC(10) = 0xFFFFFFFF
2.  CRC(11) = (CRC(10)>>8)^T[CRC(10)^pwd(1)]
3.  CRC(12) = (CRC(11)>>8)^T[CRC(11)^pwd(2)]
4.   ...
5.  CRC(1N) = (CRC(1N-1)>>8)^T[CRC(1N-1)^pwd(N)] = ~073EE641 = F8C119BE;
6. (отсюда можно найти, кстати, по F8 номер полинома - F862AE69, т.е. BYTE(CRC(1N-1)^pwd(N)) = 0xDE )
7.  
8.  
9.  CRC(20) = 0xFFFFFFFF
10.  CRC(21) = (CRC(20)>>8)^T[CRC(20)^pwd'(1)]
11.  CRC(22) = (CRC(21)>>8)^T[CRC(21)^pwd'(2)]
12.   ...
13.  CRC(2N) = (CRC(2N-1)>>8)^T[CRC(2N-1)^pwd'(N)] = ~6E40EADF;
14.  
15.  (pwd'(1) - циклический сдвиг вправо pwd(1) на один бит)
16. ...

- и так для CRC1-CRC8 - 8 независимых уравнений...

 

Дело в том, что табличный алгоритм вычисления CRC, который обычно используется в программах, является по существу оптимизацией, обрабатывающей по 8 бит сообщения за раз. Как и многие оптимизации, он затуманивает смысл происходящего. Неоптимизированная версия, обрабатывающая по биту за раз, могла бы выглядеть так: вместо

Код (Text):

1.   crc32:=$ffffffff;
2.   for n:=1 to length(pwd) do
3.   begin
4.     crc32:=table[BYTE(crc32 xor longint(ord(pwd[n])))] xor (crc32[i] shr 8);
5.   end;
6.   crc32:=not crc32;

тот же самый результат даёт код

Код (Text):

1.   crc32:=$ffffffff;
2.   for n:=1 to length(pwd) do for bit:=0 to 7 do
3.   begin
4.     if ((crc32 and 1) xor ((ord(pwd[n]) shr bit) and 1)) = 1 then
5.       crc32:=(crc32 shr 1) xor $EDB88320
6.     else
7.       crc32:=crc32 shr 1
8.   end;
9.   crc32:=not crc32;

Табличный вариант весь внутренний цикл по битам ужимает в одно обращение к таблице.
Теория, кстати, подробно изложена на сайте в разделе "Документы", http://www.wasm.ru/docs/5/crc.zip .

 

Ну например =)))
A quick fox jumps over a lazy dog. A quick fox jumpsLTDEr a lazy dog.

 

Да, конечно, в моем описании теории решения тоже имеется в виду неоптимизированный побитный алгоритм - в точности так, как приведено выше diamond-ом.

Код (Text):

1. fillchar(ucrc32, sizeof(ucrc32), $FF);
2.  
3. for n:=1 to length(pwd) do
4.     begin
5.     for i:=0 to 7 do
6.         begin
7.         x:=ord(pwd[n]);
8.         for b:=0 to 7 do
9.             begin
10.             if (ucrc32[i] xor x) and 1 = 1 then ucrc32[i]:=(ucrc32[i] shr 1) xor $EDB88320
11.                                            else ucrc32[i]:=(ucrc32[i] shr 1);
12.             x:=x shr 1
13.             end;
14.         pwd[n]:=chr((ord(pwd[n]) shr 1) or ((ord(pwd[n]) and 1) shl 7))
15.         end;
16.     end;
17.  
18. for i:=0 to 7 do
19.     ucrc32[i]:=not ucrc32[i];

 

diamond,OLS спасибо за разъяснения и за ссылку на теорию.

 

Вот щас и проверим, кто умеет обращать crc32, а кто тупо брутфорсит с начала до конца и так каждый раз. Задачка =)))

есть строка из 100 млн. символов 'a'.
Нужно пропатчить ее четырьмя символами подряд из множества a..z,A..Z,0..9
чтобы получить 55555555h. Первое решение это адрес 1F0h строка 'givN' - типа я сам умею =)))

Нужно получить следущее за ним реШение o:

 

Появилось несколько свободных часов времени - решил для себя прояснить
реверс CRC32...Может кому тоже будет интересно.
CRC32 представляет собой множество 2^32 - соответственно, входная последовательность 32 бит полностью
отображается на множестве CRC32. Т.е. любая CRC32 может быть получена из
некой последовательности 32 бит. Ниже я приведу два решения реверса CRC32.
Задача: по известной CRC32 получить последовательность 32 бит, КС которых
соответствует входной(заданной) CRC32.
Получим для CRC32 побитовый алгоритм обработки входных данных (см. #27 и #29):

Код (Text):

1.    
2.     CRC32 = 0xFFFFFFFF;
3.     //
4.     for(i=0;i<NumBits;i++)
5.     {
6.         l = (CRC32^(pInpBit[i]))&0x01;
7.         if(l)
8.             CRC32=(CRC32>>1)^dwPoly;
9.         else
10.             CRC32=(CRC32>>1);
11.     }
12.     //
13.     CRC32 = 0xFFFFFFFF^CRC32;

где pInpBit - i-й бит из последовательности входных данных,
dwPoly - полином CRC32 (0xEDB88320).
Запишем вышеприведенный алгоритм в более простой форме:

Код (Text):

1.     CRC32 = 0xFFFFFFFF;
2.     //
3.     for(i=0;i<32;i++)
4.     {
5.         //l = (CRC32^(pInpBit[i]))&0x01;
6.         l = (CRC32^(dwPass>>i))&0x01;//-если входная последовательность - dwPass(32 бит)
7.         CRC32=(CRC32>>1);
8.         if(l)
9.             CRC32=CRC32^dwPoly;
10.     }
11.     //
12.     CRC32 = 0xFFFFFFFF^CRC32;

Кстати, из теории - старший бит полинома CRC (dwPoly) равен 1.

Предложим первый вариант реверса, основанный на графах. Итак, рассмотрим
строки алгоритма:

Код (Text):

1.         CRC32=(CRC32>>1);
2.         if(l)
3.             CRC32=CRC32^dwPoly;

Отсюда следует - если старший бит результирующей CRC32 равен 1, то на данном шаге
выполнялась операция CRC32=CRC32^dwPoly; Причем, информация о старшем бите CRC32
сохраняется на "глубину" 32 шагов - следовательно входная последовательность
из 32 бит может быть полностью восстановлена. Далее, привожу пример на С
реверса CRC32 (1 вариант).

Код (Text):

1. void GraphRevers(DWORD CRC32_Inp)
2. {
3.     int i;
4.     const DWORD dwPoly = 0xEDB88320;
5.     DWORD dwPassRec;
6.     DWORD pwd[32];
7.  
8.     #define PassBits 32
9.  
10.     //reverce
11.     printf("\nGraphRevers - %08X\n",CRC32_Inp);
12.     //1
13.     DWORD CRC32 = 0xFFFFFFFF^CRC32_Inp;
14.     //dwPassRec = 0;
15.     //2
16.     for(i=PassBits-1;i>=0;i--)
17.     {
18.         pwd[i] = CRC32>>31;//теория - вытаскиваем инфорацию
19.         //был ли XOR dwPoly на i-ом шаге вычисления CRC32
20.         if(pwd[i])
21.         {
22.             //был XOR dwPoly
23.             CRC32=CRC32^dwPoly;
24.         }
25.         //
26.         CRC32 = CRC32<<1;
27.     }
28.     //3 восстанавливаем входную последовательность (32 бит) - dwPassRec
29.     dwPassRec = 0;
30.     CRC32 = 0xFFFFFFFF;
31.     for(i=0;i<PassBits;i++)
32.     {
33.         //Восстанавливаем i-й бит последовательности
34.         dwPassRec|=((pwd[i]^CRC32)&0x01)<<i;
35.         CRC32=(CRC32>>1);
36.         if(pwd[i])
37.             CRC32=CRC32^dwPoly;
38.     }
39.     //
40.     CRC32 = 0xFFFFFFFF^CRC32;
41.     //Здесь можно проверить, что CRC32==CRC32_Inp
42.     //if(CRC32==CRC32_Inp)
43.     printf("GraphRevers-pass: %08X\n",dwPassRec);
44.  
45. };

Пример работы программы:

Код (Text):

1.  GraphRevers - E951A406
2.  GraphRevers-pass: 01020304

В следующем посте я опишу второй способ реверса CRC32 (общий алгоритм которого был
описан OLS в #23 и #24) - составление битовой матрицы уравнений (32х33) и ее решение.
Тоже приведу пример кода.

 

А как там моя задачка про 100 млн 'a' ?

 

Итак - второй способ реверса CRC32 (общий алгоритм которого был
описан OLS в #23 и #24) - составление битовой матрицы уравнений (32х33) и ее решение.
Для составления битовой матрицы уравнений для CRC32 в качестве шаблона будем использовать
алгоритм вычисления CRC32, приведенный в посте #32:

Код (Text):

1.     CRC32 = 0xFFFFFFFF;
2.     //
3.     for(i=0;i<NumBits;i++)
4.     {
5.         l = (CRC32^(pInpBit[i]))&0x01;
6.         CRC32=(CRC32>>1);
7.         if(l)
8.             CRC32=CRC32^dwPoly;
9.     }
10.     //
11.     CRC32 = 0xFFFFFFFF^CRC32;

Сами уравнения p0^p1^p2^...^p(NumBits-1)^P
представим в виде битовой строки, где p0,...p(NumBits-1) - есть биты входной
последовательности(искомые). Их наличие/отсутствие в уравнении определяется
соответствующим битом (1/0) строки, а P - свободный член уравнения тоже определяется
соответствующим битом (1/0) строки. Уравнения составляем для каждого бита CRC32 отдельно.
Алгоритм решения делится на 2 части:
1)Составляем побитовые уравнения CRC32;
2)Решаем полученную систему уравнений.

В коде используются функции, реализующие элементарные операции над битовыми строками:
AllocBitString - выделить память под строку;
SetBit - установить значение конкретного бита в строке;
GetBit - получить значение конкретного бита в строке;
XorStrings - выполнить операцию XOR над двумя строками;
CopyString - копирование строки;
ShowString - визуализация строки.

Код этих функций:

Код (Text):

1. //Битовое представление:
2. #define BITS_ALLOC 32+1
3. #define DWORD_ALLOC 2
4.  
5. PDWORD AllocBitString()
6. {
7.     return( (PDWORD)HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,DWORD_ALLOC*sizeof(DWORD)) );
8.    
9. }
10. BOOL SetBit(PDWORD pdwBitsString,DWORD dwNumBit,DWORD dwBitSet)
11. {
12.     DWORD dwNumDWord;
13.     DWORD dwNumBitDW;
14.     //
15.     //
16.     if(dwNumBit>=BITS_ALLOC)
17.         return FALSE;
18.     //
19.     dwNumDWord = dwNumBit/(sizeof(DWORD)*8);
20.     dwNumBitDW = dwNumBit%(sizeof(DWORD)*8);
21.     //
22.     pdwBitsString[dwNumDWord]&=~((0x01)<<dwNumBitDW);
23.     //
24.     if(dwBitSet)
25.         pdwBitsString[dwNumDWord]|=(0x01)<<dwNumBitDW;
26.     //
27.     return TRUE;
28. }
29. DWORD GetBit(PDWORD pdwBitsString,DWORD dwNumBit)
30. {
31.     DWORD dwNumDWord;
32.     DWORD dwNumBitDW;
33.     //
34.     DWORD dwBit;
35.     //
36.     if(dwNumBit>=BITS_ALLOC)
37.         return 0;
38.     //
39.     dwNumDWord = dwNumBit/(sizeof(DWORD)*8);
40.     dwNumBitDW = dwNumBit%(sizeof(DWORD)*8);
41.     //
42.     dwBit=(pdwBitsString[dwNumDWord]>>dwNumBitDW)&0x01;
43.     //
44.     return dwBit;
45. }
46. void XorStrings(PDWORD pdwBitsString1,PDWORD pdwBitsString2,PDWORD pdwBitsStringRes)
47. {
48.     for(DWORD i=0;i<DWORD_ALLOC;i++)
49.     {
50.         pdwBitsStringRes[i] = pdwBitsString1[i]^pdwBitsString2[i];
51.     }
52. }
53. void CopyString(PDWORD pdwBitsString,PDWORD pdwBitsStringRes)
54. {
55.     for(DWORD i=0;i<DWORD_ALLOC;i++)
56.     {
57.         pdwBitsStringRes[i] = pdwBitsString[i];
58.     }
59. }
60. //
61. void ShowString(PDWORD pdwBitsString)
62. {
63.     printf("\n");
64.     for(DWORD n=0;n<BITS_ALLOC;n++)//
65.         if(GetBit(pdwBitsString,n))
66.             printf("1");
67.         else
68.             printf("0");
69. }

Далее код реверса на С с комментариями:

Код (Text):

1. void BitsSytem(DWORD CRC32_Inp)
2. {
3.     //Представление уравнений в виде строки:
4.     //p0^p1^p2^...^p(n-1)^p(n)^1
5.     //где p0,...p(n) - есть биты входной последовательности(искомые)
6.     //Их наличие/отсутствие в уравнении определяется соответствующим битом (1/0) строки
7.     //^1 - свободный член уравнения тоже определяется соответствующим битом (1/0) строки
8.     //
9.     //---------------------------------------------------------------------
10.     //Предварительные объявления:
11.     #define MATRIX_SIZE 32
12.     int i,j,k;
13.     const DWORD dwPoly = 0xEDB88320;
14.     PDWORD pArrayPolinomsCRCs[MATRIX_SIZE]; //Уравнения CRC побитно (указатели на битовые строки)
15.     PDWORD pStrNull = AllocBitString();     //Строка с нулевыми битами
16.     PDWORD pStrNewBit = AllocBitString();   //Строка для вычисления l = (CRC32^(dwPass>>i))&0x01; crc(0bit)^p(i)
17.     for(i=0;i<MATRIX_SIZE;i++)
18.         pArrayPolinomsCRCs[i] = AllocBitString();
19.     //
20.     //p0^p1^p2^...^p30^p31^1
21.     //
22.     printf("\nBitRevers - %08X\n",CRC32_Inp);
23.     //---------------------------------------------------------------------
24.     // Составляем побитные уравнения CRC
25.     //1) CRC32 = 0xFFFFFFFF;
26.     for(i=0;i<MATRIX_SIZE;i++)
27.         SetBit(pArrayPolinomsCRCs[i],32,1);//Свободный бит уравнений устанавливаем в 1
28.  
29.     //2)
30.     for(i=0;i<MATRIX_SIZE;i++)//Количество раундов вычисления CRC (число неизвестных бит): for(i=0;i<32;i++)
31.     {
32.         //2.1  l = (CRC32^(dwPass>>i))&0x01; -- crc(0bit)^p(i) = pArrayPolinomsCRCs[0]^p(i)
33.         CopyString(pArrayPolinomsCRCs[0],pStrNewBit);
34.         SetBit(pStrNewBit,i,1);
35.  
36.         //2.2 CRC32=(CRC32>>1);
37.         for(j=0;j<32-1;j++)//
38.         {
39.             CopyString(pArrayPolinomsCRCs[j+1],pArrayPolinomsCRCs[j]);
40.         }
41.         CopyString(pStrNull,pArrayPolinomsCRCs[32-1]);//Старший бит CRC обнуляется
42.  
43.         //2.3 if(l) CRC32=CRC32^dwPoly;
44.         for(j=0;j<32;j++)//
45.         {
46.             if((dwPoly>>j)&0x1)
47.                 XorStrings(pArrayPolinomsCRCs[j],pStrNewBit,pArrayPolinomsCRCs[j]);
48.         }
49.     }
50.  
51.     //3) заносим биты CRC32_Inp для решения в нашу систему (XOR со свободным членом)
52.     CRC32_Inp = ~CRC32_Inp;
53.     //
54.     XorStrings(pStrNewBit,pStrNewBit,pStrNewBit);
55.     SetBit(pStrNewBit,32,1);
56.     for(i=0;i<32;i++)
57.     {
58.         if((CRC32_Inp>>i)&0x01)
59.             XorStrings(pArrayPolinomsCRCs[i],pStrNewBit,pArrayPolinomsCRCs[i]);
60.     }
61.     //
62.     //Отображаем систему
63.     printf("\nSystem:\n");
64.     for(i=0;i<MATRIX_SIZE;i++)
65.         ShowString(pArrayPolinomsCRCs[i]);
66.     //
67.     //---------------------------------------------------------------------
68.     //Решаем полученную систему уравнений (Гаусс)
69.     BYTE pArrNumBits[MATRIX_SIZE];//Номера битов (перестановка уравнений)
70.     for(i=0;i<MATRIX_SIZE;i++)
71.         pArrNumBits[i]=(BYTE)i;
72.     //1 Приводим к верхнетреугольному виду
73.     for(i=0;i<MATRIX_SIZE;i++)
74.     {
75.         for(j=i;j<MATRIX_SIZE;j++)
76.         {
77.             if(GetBit(pArrayPolinomsCRCs[j],i))
78.             {
79.                 //перестановка уравнений
80.                 //запоминаем истинное расположение уравнений
81.                 BYTE bBuf = pArrNumBits[j];
82.                 pArrNumBits[j] = pArrNumBits[i];
83.                 pArrNumBits[i] = bBuf;
84.                 //перестановка уравнений
85.                 CopyString(pArrayPolinomsCRCs[j],pStrNewBit);
86.                 CopyString(pArrayPolinomsCRCs[i],pArrayPolinomsCRCs[j]);
87.                 CopyString(pStrNewBit,pArrayPolinomsCRCs[i]);
88.                 //
89.                 //Обнуление нижних элементов i-го столбца путем XOR-а уравнений
90.                 for(k=i+1;k<MATRIX_SIZE;k++)
91.                     if(GetBit(pArrayPolinomsCRCs[k],i))
92.                     XorStrings(pArrayPolinomsCRCs[k],pArrayPolinomsCRCs[i],pArrayPolinomsCRCs[k]);
93.                 //
94.                 break;
95.             }
96.         }
97.         //
98.     }
99.     //
100.     //Отображаем систему
101.     printf("\nGauss(1 step):\n");
102.     for(i=0;i<MATRIX_SIZE;i++)
103.     {
104.         ShowString(pArrayPolinomsCRCs[i]);
105.         printf(" (%d-bit)",pArrNumBits[i]);
106.     }
107.     //
108.     //2 Обратный ход
109.     for(i=MATRIX_SIZE-1;i>=0;i--)
110.     {
111.         for(j=i-1;j>=0;j--)
112.         {
113.             if(GetBit(pArrayPolinomsCRCs[j],i))
114.                 XorStrings(pArrayPolinomsCRCs[j],pArrayPolinomsCRCs[i],pArrayPolinomsCRCs[j]);
115.         }
116.     }
117.     //
118.     //Отображаем систему
119.     printf("\nGauss(2 step)\n");
120.     for(i=0;i<MATRIX_SIZE;i++)
121.     {
122.         ShowString(pArrayPolinomsCRCs[i]);
123.         printf(" (%d-bit)",pArrNumBits[i]);
124.     }
125.     //
126.     //Отображаем биты CRC, согласно их истинному расположению (pArrNumBits)
127.     CRC32_Inp = 0;
128.     for(i=0;i<MATRIX_SIZE;i++)
129.     {
130.         if(GetBit(pArrayPolinomsCRCs[(pArrNumBits[i])],32))
131.             CRC32_Inp|=(0x01<<i);
132.     }
133.     //
134.     printf("\nBitRevers-pass:%08X\n",CRC32_Inp);
135. }

Пример работы программы:

Код (Text):

1. BitRevers - E951A406
2.  
3. System:
4.  
5. 111110111000000010001011001000000
6. 011111011100000001000101100100001
7. 101111101110000000100010110010000
8. 010111110111000000010001011001001
9. 001011111011100000001000101100101
10. 100101111101110000000100010110010
11. 101100000110111010001001000011000
12. 010110000011011101000100100001100
13. 101011000001101110100010010000111
14. 101011011000110101011010000000011
15. 101011010100011000100110001000000
16. 010101101010001100010011000100001
17. 001010110101000110001001100010001
18. 100101011010100011000100110001001
19. 110010101101010001100010011000101
20. 011001010110101000110001001100010
21. 010010010011010110010011101110001
22. 001001001001101011001001110111000
23. 100100100100110101100100111011101
24. 110010010010011010110010011101110
25. 100111110001001111010010000110111
26. 101101000000100101100010001011010
27. 001000011000010000111010001101100
28. 100100001100001000011101000110110
29. 001100111110000110000101101011010
30. 011000100111000001001001111101100
31. 001100010011100000100100111110110
32. 111000110001110010011001010111011
33. 100010100000111011000111100011100
34. 110001010000011101100011110001110
35. 000110010000001100111010110000111
36. 111101110000000100010110010000011
37. Gauss(1 step):
38.  
39. 111110111000000010001011001000000 (0-bit)
40. 011111011100000001000101100100001 (1-bit)
41. 001110001010000011101100011110001 (2-bit)
42. 000110100001000010111000100011001 (3-bit)
43. 000011010000100001011100010001101 (4-bit)
44. 000001101000010000101110001000111 (5-bit)
45. 000000111000011011110111100000101 (6-bit)
46. 000000011100001101111011110000010 (7-bit)
47. 000000001110000110111101111000001 (8-bit)
48. 000000000101010110000011100000110 (9-bit)
49. 000000000010101011000001110000010 (10-bit)
50. 000000000001101011111100010100101 (11-bit)
51. 000000000000110111000110100011110 (14-bit)
52. 000000000000010000000001110111001 (15-bit)
53. 000000000000001011100010100110110 (12-bit)
54. 000000000000000101110001010011011 (13-bit)
55. 000000000000000011100010011101011 (16-bit)
56. 000000000000000001110001001110101 (17-bit)
57. 000000000000000000110001001001110 (19-bit)
58. 000000000000000000010011011101000 (18-bit)
59. 000000000000000000001011111001111 (20-bit)
60. 000000000000000000000111101011101 (21-bit)
61. 000000000000000000000011110101111 (22-bit)
62. 000000000000000000000001111010111 (23-bit)
63. 000000000000000000000000100101001 (24-bit)
64. 000000000000000000000000011101000 (26-bit)
65. 000000000000000000000000001010110 (25-bit)
66. 000000000000000000000000000100110 (28-bit)
67. 000000000000000000000000000010110 (29-bit)
68. 000000000000000000000000000001000 (27-bit)
69. 000000000000000000000000000000110 (31-bit)
70. 000000000000000000000000000000010 (30-bit)
71. Gauss(2 step)
72.  
73. 100000000000000000000000000000000 (0-bit)
74. 010000000000000000000000000000000 (1-bit)
75. 001000000000000000000000000000001 (2-bit)
76. 000100000000000000000000000000000 (3-bit)
77. 000010000000000000000000000000000 (4-bit)
78. 000001000000000000000000000000000 (5-bit)
79. 000000100000000000000000000000000 (6-bit)
80. 000000010000000000000000000000000 (7-bit)
81. 000000001000000000000000000000001 (8-bit)
82. 000000000100000000000000000000001 (9-bit)
83. 000000000010000000000000000000000 (10-bit)
84. 000000000001000000000000000000000 (11-bit)
85. 000000000000100000000000000000000 (14-bit)
86. 000000000000010000000000000000000 (15-bit)
87. 000000000000001000000000000000000 (12-bit)
88. 000000000000000100000000000000000 (13-bit)
89. 000000000000000010000000000000000 (16-bit)
90. 000000000000000001000000000000001 (17-bit)
91. 000000000000000000100000000000000 (19-bit)
92. 000000000000000000010000000000000 (18-bit)
93. 000000000000000000001000000000000 (20-bit)
94. 000000000000000000000100000000000 (21-bit)
95. 000000000000000000000010000000000 (22-bit)
96. 000000000000000000000001000000000 (23-bit)
97. 000000000000000000000000100000001 (24-bit)
98. 000000000000000000000000010000000 (26-bit)
99. 000000000000000000000000001000000 (25-bit)
100. 000000000000000000000000000100000 (28-bit)
101. 000000000000000000000000000010000 (29-bit)
102. 000000000000000000000000000001000 (27-bit)
103. 000000000000000000000000000000100 (31-bit)
104. 000000000000000000000000000000010 (30-bit)
105. BitRevers-pass:01020304

Приведенный алгоритм с минимальными доработками можно использовать для решения
задачи, изложенной в #1 посте.