Способы обнаружения искажений в пакете

CRC 16-бит

Содержание

Введение……………………………………………………………….3

Способы обнаружения искажений в пакете…………………………4

СRC-арифметика………………………………………………………6

Стандарты для CRC-полиномов………………………………………9

Требования к CRC-полиномам……………………………………….11

Алгоритм……………………………………………………………….17

Приложение. Утилита для вычисления СRC ……………………….20

Библиография и ссылки ………………………………………………24

Введение.

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

Способы обнаружения искажений в пакете.

Чтобы не допустить испорченную информацию существует и применяется на данный момент несколько способов, которые добавляют лишнюю информацию, по которой получатель может определить была ли ошибка.

1. Посимвольный контроль четности. С каждым байтом передается дополнительный бит, принимающего единичное значение по четному или нечетному количеству единичных битов в байте. Может использоваться два типа контроля четности – на четность и нечетность. Не самый эффективный способ обнаружения ошибок. Этот вид контроля обычно реализуется аппаратно в устройствах связи.

Пример. 10010010.0, 0 добавили (проверка на нечетность)

получают:10110010.0, ошибка обнаружена

получают:11110010.0, ошибка не обнаружена

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

Пример:

1

1

0

0

1

0

1

0

0

0

0

0

1

1

0

1

1

0

0

1

0

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

1

0

0

0

1

0

0

1

1

1

1

0

0

0

1

0

0

1

0

0

1

0

1

0

0

0

0

1

0

1

0

0

1

0

3. Вычисление контрольных сумм. В простейшем виде контрольная сумма – это арифметическая сумма двоичных значений контролируемого блока символов. Но этот метод обладает практически теми же недостатками, что и предыдущие, а именно нечувствителен к четному числу ошибок.

4. Контроль циклически избыточным кодом. CRC – Cyclic Redundancy Code. Это гораздо более мощный и широко используемый метол обнаружения ошибок при передаче информации. Он обеспечивает высокую вероятность обнаружения ошибок.

Основная идея вычисления CRC заключается в следующем. Исходная последовательность байтов представляется единой последовательностью битов. Эта последовательность делится на некоторое фиксированное двоичное число. Интерес представляется остаток от деления, который и является значение CRC.

Вообще вышеизложенные способы является хэш-фуенкциями, т.е.:

h: A  {0,x-1}

Метод хеширования позволяет хранить элементы из множества A в линейном массиве X, т. е. Функция h отображает каждый элемент множества A в индекс множества X.

Но чаще используются так называемые односторонние хэш-функции. Функция f:XY называется односторонней, если f(x) может быть легко вычислена для любого элемента из множества X, тогда для всех элементов из множества Y вычисление такого аргумента x, для которого f(x)=y, не разрешимо полиномиально.

CRC и является односторонней хэш-функцией.

CRC-арифметика.

Что же такое особенное есть в CRC, что позволяет обнаруживать большую часть ошибок? Это безусловно метод его нахождения. Для нахождения CRC используется специальная CRC-арифметика, которая является полиномиальной арифметикой по модулю 2. Т.е. битовое значение 1001001112=16710 может быть представлено в виде: 1*x^8+0*x^7+0*x^6+1*x^5+0*x^4+0*x^3+1*x^2+1*x^1+1. Для того чтобы получить искомое значение, можно подставить x=2. Эта арифметика обладает одним весьма не маловажным свойством – операции сложения и вычитания идентичны, и поэтому можно оставить лишь одну операцию, т.е.

_1001011

1100010

0101001

Сложение и вычитание ведется по следующим правилам: 0-0=0, 0-1=1, 1-0=1, 1-1=0. Таким образом можно заметить, что результат вычитания в арифметике без переносов, аналогичен операции XOR.

Для нашего рассмотрения особый интерес представляет операция деления, так как в основе любого алгоритма вычисления CRC лежит представление исходного сообщения в виде огромного двоичного числа, делении его на другое двоичное число и использование остатка от этого деления в качестве значения CRC. Говоря иначе: M — исходное сообщение, n – степень порождающего полинома, G – порождающий полином, тогда CRC – это остаток от M*x^n/G.

Например, сообщение M=0x54, G=0x11021 (Xmodem). M’=0101,0100,0000,0000,0000,0000

G=1,0001,0000,0010,0001

010101000000000000000000|00010001000000100001

10001000000100001частное никого не интересует

00100000000100001000000

10001000000100001

000010000101001010000

10001000000100001

00001101001110001

0001,1010,0111,0001=0x1a71 – остаток от деления

После получения этого остатка – остаток добавляется в конец передаваемого сообщения и сообщение передается. Есть 2 способа обнаружения ошибок:

Приемник может получить сообщение отделить последние 16 бит, посчитать CRC оставшегося и сравнить с тем 16 битами.

Или же приемник может поделить полученное сообщение на G, и таким образом обнаружить ошибку

Стандарты для CRC-полиномов

Несколько протоколов определяют CRC-полиномы используемые для обнаружения ошибок: CCITT X.25, BiSynch, SDLC, HDLC. Они определяют полином и метод нахождения остатка.

Используемые полиномы.

1. CRC X.25 (CCITT), X-modem x16 + x12 + x5 + 1

2. CRC-16 (Bisynch) x16 + x15 + x2 + 1

Полином 1 стандартизирован в спецификации V. 41 CCITT «Кодонезависимая система контроля ошибок».

Полином 2 стандартизирован в спецификации V. 42 того же CCITT. Также он используется в протоколе двоичной синхронной (бисинхронной) передаче данных от компании IBM

Не все протоколы используют обычную схему нахождения остатка, так, например, рассмотрим CCITT X.25. S=0x54, G=0x11021, n=16. В приложении CCITT сначала меняется порядок битов сообщения, т.е. S=0x54 становится S=0x2a. К тому же начальное значение CRC инициализируется единицами. Это тоже, что XOR первых 16-ти бит с 16-ю единицами.

110101011111111100000000 | 10001000000100001

10001000000100001частное не имеет значения

010111011110111110000000

10001000000100001

00110011110011111000000

10001000000100001

010001110010111010000

10001000000100001

00000110010011011000

Остаток равен 0110,0100,1101,1000. Последовательность бит так же меняется, т.е. 0001,1011,0010,0110. Затем результат обращается и две восьмерки битов меняются местами, Итак CRC=1101100111100100, или CRC=0xd9e4.

Протокол Xmodem был разработан специально для программного применения. Он использовал тот же полином, что CCITT X.25. Протокол Xmodem использует обычный алгоритм нахождения CRC. И поэтому довольно просто в применении там, где невозможно реализовать таблицы.

Надо отметить, что различные стандарты так же имеет различные отклонения от обычной математической реализации. Многие стандарты инициализируют начальное значение CRC в единицы, но Xmodem, BiSynch – в нули. Старый CCITT стандарт так же инициализировал в нули, на X.25 инициализирует в единицы. Многие утилиты использующие алгоритм Xmodem’а так же инициализируют начальное значение в 1’ы. Особенности X.25 были показаны выше.

Между прочим, существует множество модификаций протокола Xmodem, но не один из них не менял полином. [4]

Следует так же упомянуть о других CRC полиномах. Существуют и стандартизированы CRC полиномы разрядности – 8, 12, 24, 32. Полиномы меньшей разрядности используются там, где передаваемые сообщения малы, тогда как полиномы разрядности 24 могут обнаружить ошибку в сообщения длины свыше одного мегабайта, а 32 уже свыше 256 мегабайт.

Требования к CRC-полиномам.

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

X.25:0x18408 (обратный к 0x11021)

X-modem:0x11021

CRC-16 (BISYNCH):0x1a001 (обратный к 0x18005)

CRC-16* (IBM):0x18005

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

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

Передаваемое сообщение T=M’+CRC, где M’ – исходное сообщение с добавленными 15-ю нулями в конец, а CRC – остаток от деления. Поскольку сложение также и вычитание – M’ уменьшается до ближайшего кратного к делителю G.

Если сообщение пришло с ошибками, т.е. T’=T+E, тогда приемник просто T’ делит на G, получая (T+E)modG=E mod G, т.к. T mod G=0. Т.е. качество качество полинома определяется количеством E кратных ему.

Эти полиномы были найдены такими, чтобы выполнялись условия:

Обнаруживать ошибку в 1-бите. Для этого в полиноме должно быть больше 1-й единицы.

Обнаруживать ошибки в 2-х различных битах для пакетов длины меньше, чем 215 бит. Надо подобрать G для которые не кратны числам типа 011, 0101, 01001, и.т.д.

Обнаруживать ошибки в нечетном количестве бит. Для этого в G должно быть четное количество единичных бит.

Обнаруживать идущие подряд ошибочные биты длины меньше 17. E=000…011…10…000. Вектор ошибок можно представить в виде: E=(100…00)*(111…1). Если в G младший бит единица, то левый множитель не кратен G, и если G длиннее правого множителя, то ошибка будет отловлена.

Обнаруживать идущие подряд ошибочные биты длины 17, кроме 1/215.

Обнаруживать все другие ошибки, кроме 1/216.

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

Концепция сдвига вносит некоторые ограничения. Поскольку степени x – это ненулевые элементы 216, если сдвиг начался с некоторого ненулевого состояния, то в это же состояние мы вернемся через 215 шагов и не раньше. Таким образом, возникает на ограничение на размер сообщения – 4094 байта.

Исследование.

Было проведено исследование. Цель, которого состояла в том, чтобы узнать выполняются ли на самом деле условия наложенные на полиномы.

Для этого использовалось 105 строк длины 5 байт, содержащих цифры от 0 до 9.

Просмотрев значения, на которых получены одинаковые CRC было обнаружено следующее:

1. Xmodem (0x1021, инициализируется 0)

Повторов: 112320

Нет ни одного случая с одной 1-битной ошибкой.

Все пары 1-битных ошибок находит.

Совпадений CRC при четном количестве различных битов – 35840, при нечетном количестве бит – 76480. Есть совпадения CRC при нечетном количестве различных одиночных бит

Если встречаются группы ошибочных бит, то их несколько.

2. CRC-16* (0x8005, инициализируется 0)

Повторов: 327424

Нет ни одного случая с одной 1-битной ошибкой.

16000 раз встречается совпадение CRC в случае с 2 различными битами. Причем биты находятся на расстоянии в 1 бит.

Совпадений CRC при четном количестве различных битов – 150912, при нечетном количестве бит – 176512. Нет совпадений CRC при нечетном количестве различных одиночных бит



Страницы: Первая | 1 | 2 | 3 | Вперед → | Последняя | Весь текст