Нахождение полинома CRC, Нахождение полинома CRC Опции

[uk8adi]

Господа! Нижайшая просьба.
Есть последовательность данных (передаются сегментами по 6 (шесть) байт) и есть значения CRC для этих байт (сегментов). Необходимо узнать применяемый полином.

323333333331 hex 233331 ANSII 5E23 - CRC
323333333332 233332 FE76
323333333333 233333 2E5D
323333333334 233334 6EF4
323333333335 233335 BEDF
323333333336 233336 1E8A
323333333337 233337 CEA1

Данные сняты с рабочего устройства.

Буду признателен за любую помощь.

[DuHast]

Господа! Нижайшая просьба.
Есть последовательность данных (передаются сегментами по 6 (шесть) байт) и есть значения CRC для этих байт (сегментов). Необходимо узнать применяемый полином.

323333333331 hex 233331 ANSII 5E23 - CRC
323333333332 233332 FE76
323333333333 233333 2E5D
323333333334 233334 6EF4
323333333335 233335 BEDF
323333333336 233336 1E8A
323333333337 233337 CEA1

Данные сняты с рабочего устройства.

Буду признателен за любую помощь.

Давно этим занимался, могу где-то ошибится, но помоему это делается так:
запишите друг под другом кодовие слова в двоичном виде (минимум 48) и складывайте их поразрядно друг с другом так, чтобы в левой части получившейся матрицы получилась единичная матрица 48*48.Тогда получившаяся мотрица будет пораждающей для искомого блочного кода. Ручками это делать будет сложно, можете попробовать написать программу.
Пример полазрядгого сложения: 1001+0101=1100.

Удачи

[DuHast]

Дополню:
Последняя строка матрицы и будет порождающий многочлен (конечно если у Вас именно циклический блочный код, если не циклический, то о пораждающем полиноме говорить не корректно). Поэтому искать всю матрицу не обязательно, достаточно будет найти её последнюю строку: сложите несколько кодавых слов, таких чтобы получилось кодовое слово начинающееся с 47 нулей и одной единицы, это и будет пораждающий полином.


...
О, да у Вас кодовые слова что надо:
323333333332 233332 FE76 +
323333333333 233333 2E5D
или
323333333334 233334 6EF4 +
323333333335 233335 BEDF
и полином получается:
10000000000000000000000011101000000101011
ещё раз повторюсь, что Вы должны быть увереня, что у Вас циклический код и кодовые слова приняты без ошибок.

Сообщение отредактировал DuHast - Oct 11 2006, 14:06

[uk8adi]

Как я правильно понял Вас, порождающий полином равен D02B hex. Но он не укладывается в общую картину. Попробуйте посчитать.
Дело в том, что СRC, посчитанное с данным полиномом отличается от СRС, передаваемым рабочим устройством, посылку которого мы хотим повторить. Мы пробовали проследить разницу между этими двумя CRC и вывести какую-нибудь зависимость путем последовательного наращивания исходного сегмента данных, как в последнем из 6-ти передаваемых, байт, так и во всех 5-ти остальных, но закон изменения этой разницы увидеть не смогли. Простое наложение маски (Init) к исходному сегменту данных или к вычисленному СRC по полиному D02B (Out) не подходит - у маски (какой?) есть какая-то функциональноая зависимость от исходных данных сегмента? Мы можем таблицу с другими фрагментами сегментов:

сегмент...............принятое CRC...........разница (XOR).......расчитанное CRC
..........................с устройства.........................................с полиномом D02B
303333333330...........6B3D.........................8538........................
.EE05
303333333331...........BB16.........................8538........................
.3E2E
303333333332...........1B43.........................853B........................
.9E78
303333333333...........CB68........................853B.........................
4E53
303333333334...........8BC1........................853E.........................
.0EFF
303333333335...........5BEA.........................853E........................
.DED4
303333333336...........FBB6.........................8534........................
.7E82
303333333337...........2B94.........................853D........................
AEA9
303333333338...........7AEE.........................8534........................
.FFDA
303333333339...........AAC5........................8534.........................
2FF1
30333333333A...........0A90.........................8537........................
.8FA7
30333333333B...........DABB........................8537.........................
5F8C
30333333333C...........9A12........................8532.........................
.1F20
30333333333D...........4A39........................8532.........................
.CF0B
30333333333E...........EA6C........................8531.........................
.6F5D
30333333333F............3A47........................8531........................
..BF76

313333333341...........23F0.........................BFC4........................
..9C34
313333333344...........1327.........................BFC2........................
..ACE5
313333333345...........C30C........................BFC2.........................
.7CCE
313333333346...........6359........................BFC1.........................
.DC98
313333333347...........B372........................BF49.........................
.0CB3
313333333348...........E208........................BFC8.........................
.5DC0
313333333349...........3223........................BFC8.........................
.8DEB
31333333334A...........9276........................BFCB.........................
.2DBD
31333333334B...........425D........................BFCB.........................
.FD96
31333333334C...........02F4........................BFCE.........................
.BD3A
31333333334D...........D2DF........................BFCE.........................
.6D11
31333333334E...........728A........................BFCD.........................
.CD47
31333333334F...........A2A1........................BFCD.........................
.1D6C



Если этих данных мало, то могу прислать еще (на данный момент наснято и более 1000 :-) )
Могу прислать данные с измением в любом байте, не только в этих.

Спасибо, очень жду ответа.

Сообщение отредактировал uk8adi - Oct 12 2006, 07:09

[Epikur]

Да, отправь посылку со всеми нулями.

[uk8adi]

Да, отправь посылку со всеми нулями.

CRC посылки 000000000000hex снято 0003 hex

[Fast]

перед прямым вскрытием порождающего полинома
неплохо проверить на соответствие 2 основный полинома CRC-16
g(x)=x16 + x12 + x5 + 1,
g(x)=x16 + x5 + x2 + 1.

возможно, полином не циклический, а допустим порождающая матрица задана таблично
тогда уже выстраиваем каноническую матрицу для нахождения базиса (методом Гаусса, что предложен выше)

[uk8adi]

неплохо проверить на соответствие 2 основный полинома CRC-16
g(x)=x16 + x12 + x5 + 1,
g(x)=x16 + x5 + x2 + 1.

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

Сообщение отредактировал uk8adi - Oct 12 2006, 12:51

[Fast]

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

А как Вы проверяли, простым делением на порождающий? Инвертировали ли первые 2 байта перед делением согласно рекомендации V.42 (ну мало ли..) и результат деления?

кстати, D02B полинома не существует в природе
список неприводимых многочленов степени 16 имеется, только я его найти не могу, видел в какой-то книжке
знаю, что их можно получить в Матлабе

[uk8adi]

Данные полиномы (1021hex и 0023hex) были проверены в самом начале поиска. Это не они.

А как Вы проверяли, простым делением на порождающий? Инвертировали ли первые 2 байта перед делением согласно рекомендации V.42 (ну мало ли..) и результат деления?

кстати, D02B полинома не существует в природе
список неприводимых многочленов степени 16 имеется, только я его найти не могу, видел в какой-то книжке
знаю, что их можно получить в Матлабе

Все далалось по данной рекомендации (CCITT V.24).
Причем считалось, как вручную на бумаге, так и программой "Hex Workshop v4.23". У нее есть функция подсчета CRC, как со стандартными полиномами, так и с пользовательскими, задаваемыми вручную.

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

[Сергей Борщ]

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

Лично я применяю начальное значение CRC отличное от нуля. Попробуйте просчитать свою нулевую посылку по стандартным полиномам с начальным значением отличным от нуля.

Еще у Скляра в "Цифровой связи" на стр. 933 описан метод взлома системы шифрования на регистре с обратными связями - оно не поможет?

Сообщение отредактировал Сергей Борщ - Oct 12 2006, 13:39

[Fast]

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

Ну могу предложить следующее - вырубить все топором

принять 48 последовательностей и CRCi к ним (i = 1...48)
100000000000hex
200000000000hex
400000000000hex
800000000000hex
010000000000hex
... ... ... ... ...
000000000001hex
т.е. с единичкой в каждом разряде
отнять от каждого CRCi CRC0 (crc для нулевого КС)

CRC любой кодовой последовательности(кодового слова = КС) будет равно сумме частных СRСi,
соответствующих каждому ненулевому биту КС

[DuHast]

Как я правильно понял Вас, порождающий полином равен D02B hex.

Похоже я вас не так понял.
Описаный мною алгоритм нахождения полинома верный, но когда я его применял, я исходил из того, что: кодовое слово состоит из 6-ти информационных байт и 5-ти проверочных. Это так? Если да то пролином 10000000000000000000000011101000000101011 . Но как я теперь понимаю у Вас 2 проверочных байта, тогда мне не понятна запись

323333333332 233332 FE76
323333333333 233333 2E5D
323333333334 233334 6EF4
323333333335 233335 BEDF
323333333336 233336 1E8A
323333333337 233337 CEA1

И ещё, CRC нулевого кодового слова - тоже ноль, а у Вас 0003. Здесь возможны два варианта:
1 Вы приняли сигнал с ошибкой (думаю это мало вероятно).
2 на CRC после вычисления накладывается маска 0003hex. Тогда её надо сперва снять, а затем искать полином по описанниму выше алгоритму

...

Если я Вас на сей раз правильно понял и
303333333330 6B3D
303333333331 BB16
являются кодовыми словами, то полином 11101000000101011

...

Но самое простое решение продрожил в предыдущем ответе Fast, конечно если Вы можете сами формировать информационные сегменты.

Сообщение отредактировал DuHast - Oct 12 2006, 19:29

[DuHast]

ю.

Сообщение отредактировал DuHast - Oct 12 2006, 19:31

[Epikur]

Да, отправь посылку со всеми нулями.

CRC посылки 000000000000hex снято 0003 hex

Какая-то подозрительная сумма. Если начальное состояние регистров нулевое, то и сумма будет нулевая. Если не нулевое, то как-то маловато единиц в конечной сумме.
Есть мнение, что используется всё же не полноценный CRC.

Предлагаю попробовать начальные значения - все единицы.
ЗЫ.
Здесь http://www.ee.unb.ca/cgi-bin/tervo/factor....000000000000101
написано, что стандартный полином CRC-16 не примитивный.


Попробуйте полином D027 в комбинации со стартовым значением. Какое пока сказать не знаю.
Предлагаю попробовать прогнать комбинацию FFFF00000000

Сообщение отредактировал Epikur - Oct 12 2006, 21:52

[uk8adi]

Доброе утро.
По поводу единичек в каждом разряде. До устройства пока не добрался, но проверил на стандартном полиноме CRC16CCITT 1021hex. Вот данные:

двоичные данные.......HEX.......CRC..............Разность:
(2 байта)................................p1021.......XOR.....алгебраическая

0000000000000000......0000......1D0F
0000000000000001......0001......0D2E......1021......0FE1
0000000000000010......0002......3D4D......2042......DFC2
0000000000000100......0004......5D8B......3063......BF84
0000000000001000......0008......9C07......8108......8108
0000000000010000......0010......0F3E......1231......0DD1
0000000000100000......0020......396D......2462......E3A2
0000000001000000......0040......55CB......48C4......C744
0000000010000000......0080......8C87......9188......9088
0000000100000000......0100......2E3E......3331......EED1
0000001000000000......0200......7B6D......6662......A1A2
0000010000000000......0400......D1CB......CCC4......4B44
0000100000000000......0800......94A6......89A9......8869
0001000000000000......1000......1E7C......0373......FE93
0010000000000000......2000......1BE9......06E6......0126
0100000000000000......4000......10C3......0DCC......0C4C
1000000000000000......8000......0697......1B98......1678

Как я правильно понял, CRC для данных 0003hex будет сумма разностей для нулевого и первого бита.

Правильное CRC, расчитанное программой для данных 0003hex будет 2D6Chex.
По варианту, предложенному Вами, CRC будет 3063hex, при сложении XOR, и EFA3hex при алгебраическом.

Извеняюсь за первое сообщение, не проследил за табуляцией.

Сообщение отредактировал uk8adi - Oct 13 2006, 06:14

[uk8adi]

Кто знает разработчиков того устройства, они могли применить и нестандартный полином, и может быть что-нибудь еще.

Лично я применяю начальное значение CRC отличное от нуля. Попробуйте просчитать свою нулевую посылку по стандартным полиномам с начальным значением отличным от нуля.

Еще у Скляра в "Цифровой связи" на стр. 933 описан метод взлома системы шифрования на регистре с обратными связями - оно не поможет?

Как я понял, вычислить начальное значение (init по описанию CRC) для нулевой посылки и после применять ее для дальнейшего расчета других данных.
Это было сделано, и расчитанные CRC отличались от принятых, причем довольно сильно и без видимой мною системы.

[uk8adi]

Попробуйте полином D027 в комбинации со стартовым значением. Какое пока сказать не знаю.
Предлагаю попробовать прогнать комбинацию FFFF00000000

Подсчитано с полиномом D027 и стартовым значением FFFF00000000 (стандартное для CRC16 CCITT):
.............................принятые...расчитанные
........................................CRC
303333333330..........6B3D..........EB11
303333333331..........BB16..........FB36
303333333332..........1B43..........CB5F
303333333333..........CB68..........DB78
303333333334..........8BC1..........AB8D
303333333335..........5BEA..........BBAA

[Epikur]

>> Подсчитано с полиномом D027 и стартовым значением FFFF00000000
Не, я имею ввиду, прогнать эту комбинацию по полиному.
А какое стартовое значение нам поможет определить единичка со всеми нулями.
Вообще, есть есть такая возможность, то стоит прогнать комбинацию XXXX00000000 со всеми возможными значениями XXXX и посмотреть, какая посылка даст нулевую сумму. Это XXXX и будет стартовым значением.

[Fast]

uk8adi, Неверно

1. я говорил, что от всех частных CRCi надо было отнять CRC0, конечно по модулю
тут я что-то уже запутался, т.к. было это дело давно,
но что надо от чего-то отнять CRC0, помню точно
наверное, от конечного результата

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

3. чтобы найти правильный полином, надо для каждого полинома CRC-16 (и все-таки найти их все)
получить XOR -разницу с нашими частными CRCi
если это будет величина постоянная, то полином мы угадали
останется только найти предустановку регистра

[uk8adi]

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу.
Сообщу о результатах.

[Сергей Борщ]

2. Пусть
- сложение по модулю
- вычитание по модулю

CRC для данных 0003hex будет равно
CRC1 CRC2 CRC0
или
0D2E 3D4D 1D0F = 2D6C

Работает! Проверил на стандартном полиноме. Сейчас пойду к железке и наработаю таблицу.
Сообщу о результатах.

Если не получится попробуйте еще полином 0x8408 (CRC-XMODEM) вкупе со сдвигом в другую сторону

[uk8adi]

Что и куда двигаем. Не понятно. Пожалуйста, поподробнее.

Сообщение отредактировал uk8adi - Oct 16 2006, 12:31

[Сергей Борщ]

Что и куда двигаем. Не понятно. Пожалуйста, поподробнее.

Меняется порядок обработки битов. Можно я на примере?

Код

//==============================================================//
//          Calculate one byte of CCITT CRC-16                  //
//==============================================================//
void CRC_CRC16 (uint8_t Data, uint16_t &CRC) {
    CRC ^= (uint16_t)(Data) << 8;
    uint8_t i = 8;
    do {
        if (CRC & 0x8000) { CRC <<= 1; CRC ^= 0x1021; }
        else CRC <<= 1;
    }while(--i);
}
//==============================================================//
//          Calculate one byte of XModem CRC                    //
//==============================================================//
void CRC_XMODEM (uint8_t Data, uint16_t &CRC) {
    CRC ^= Data;
    uint8_t i = 8;
    do {
        if (CRC & 0x01) { CRC >>= 1; CRC ^= 0x8408; }
        else CRC >>= 1;
    } while(--i);
}

[uk8adi]

Господа!
Сделал эту таблицу, с одной единичкой в каждом бите.
Работает все прекрасно!

ВСЕМ СПАСИБО!


Но как всетаки вытащить образующий полином, я не понял.

[Fast]

Но как всетаки вытащить образующий полином, я не понял.

ну.. это волшебство..

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

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

[DuHast]

Но как всетаки вытащить образующий полином, я не понял.

ну.. это волшебство..

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

Сообщение отредактировал DuHast - Oct 17 2006, 18:10

[Fast]

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

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

Потом производится хитрая перестановка и сложение строк матрицы (линейная комбинация строк). Обычно это делается для придания коду нужных спектральных характеристик, когда какие-то кодовые слова (КС) передаются чаще других.

[DuHast]

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

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

А вот

хитрая перестановка и сложение строк матрицы (линейная комбинация строк).

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

Сообщение отредактировал DuHast - Oct 18 2006, 18:44

[uk8adi]

Добрый день.

Снятая и частично вычисленная таблица:

000000000000...........0003
000000000001...........D028
000000000002...........707D
000000000004...........E0FF
000000000008...........11D0
000000000010...........23A6
000000000020...........474A
000000000040...........8E92
000000000080...........CD09
000000000100...........4A3C
000000000200...........947E
000000000400...........F8D1
000000000800...........218C
000000001000...........431E
000000002000...........863A
000000004000...........DC59
000000008000...........689C
000000010000...........D13E
000000020000...........7251
000000040000...........E4A7
000000080000...........1960
000000100000...........32C6
000000200000...........658A
000000400000...........CB12
000000800000...........4609
000001000000...........8С17
000002000000...........С800
000004000000...........402D
000008000000...........805F
000010000000...........D090
000020000000...........710D
000040000000...........E21F
000080000000...........1410
000100000000...........2826
000200000000...........504A
000400000000...........A092
000800000000...........9109
001000000000...........F23C
002000000000...........3455
004000000000...........68AF
008000000000...........D15B
010000000000...........7298
020000000000...........E536
040000000000...........1A41
080000000000...........3487
100000000000...........690B
200000000000...........D213
400000000000...........7408
800000000000...........E816

Заметил еще одну вещь. Сегмент данных проверяется на четность (количество едениц), если четно, то еще прибавляется 0003.

[Fast]

А вот

хитрая перестановка и сложение строк матрицы (линейная комбинация строк).

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

CRCi оставляем на месте, информационную часть с единичками переставляем (меняем местами)
или наоборот,
единички оставим, а CRCi будем переставлять и комбинировать, но чтобы не было 2х одинаковых

это я плохо выражовываюсь
или ошибаюсь...

[DuHast]

это я плохо выражовываюсь
или ошибаюсь...

Теперь всё понял

[uk8adi]

"Может лучше про реактор, про любимый лунный трактор....."

Табличным способом считать относительно долго, и место таблица занимает.

Это я по вопросу полинома. Он есть или его нет?
Если есть, то как его найти.
Если нет, то тогда ладно...

[3.14]

Имею 5 байт и контрольную сумму:
0x20 0x00 0x00 0x00 0x00 - 0xE0
0xE0 0x00 0x00 0x00 0x00 - 0x20
0x60 0x00 0x00 0x00 0x00 - 0xA0
0x00 0x70 0x00 0x01 0x43 - 0xCE

Интересно, это циклическая сумма или как?

[DuHast]

Имею 5 байт и контрольную сумму:
0x20 0x00 0x00 0x00 0x00 - 0xE0
0xE0 0x00 0x00 0x00 0x00 - 0x20
0x60 0x00 0x00 0x00 0x00 - 0xA0
0x00 0x70 0x00 0x01 0x43 - 0xCE

Интересно, это циклическая сумма или как?

Четырёх слов недостаточно для идентификации кода