Господа! Нижайшая просьба.
Есть последовательность данных (передаются сегментами по 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.

Удачи

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


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

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

Как я правильно понял Вас, порождающий полином равен 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

...

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

...

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

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

ю.

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

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

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


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

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