Подсчет CRC

[insite2012]

Приветствую всех.
Проблема в следующем.
Имеется бинарный файл. Известна его контрольная сумма, и известно, что просчитывается она по алгоритму CRC(вероятнее всего, CRC16). Однако, ни один их Hex-редакторов не дает верного результата при попытке просчитать ее встроенными средствами. Я подозреваю, что там используются специфические входные данные, такие как значение полинома и/или начальной контрольной суммы.
Вопрос такой: имеются ли в VB методы для просчета CRC или необходимо реализовать все это самому? Естественно, если имеются, то это упростило бы задачу, поскольку я планирую сделать что-то вроде переборщика по подбору значений, при которых просчитанная и реальная CRC файла совпадут.

[FireFenix]

имеются ли в VB методы для просчета CRC или необходимо реализовать все это самому?

на VB6 - в другой раздел, для VB.NET - самому в 15-20 строк на просторах гугла тонна готовых примеров

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

Проще реверснуть алгоритм

[insite2012]

Извиняюсь, ошибся))) Естественно, я имел ввиду VB.NET, поскольку именно на нем и работаю.
Если не сложно, можно пару ссылок на примеры для VB.NET?)
А что значит "реверснуть алгоритм"?

[FireFenix]

А что значит "реверснуть алгоритм"?

Это значит открыть и протрейсить код, чтобы узнать как он работает.
Тот код для которого нужен CRC

И на основе полученных знаний создать нужный алгоритм.

Если не сложно, можно пару ссылок на примеры для VB.NET?)

Вначале нужно начать с http://ru.wikipedia.org/wiki/CRC16 , чтобы узнать какие виды вообще есть и их полиномы

один из видов
http://www.vbforums.com/showthread.php? ... ost4159650

[insite2012]

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

[pronto]

Можно у тех.поддержки производителя попытаться выведать алгоритм CRC или его название (Modbus, CCITT и др.)... Это не должно быть большим секретом.
Вычисление CRC некоторыми распространёнными алгоритмами — это для самопроверки...

[insite2012]

Можно у тех.поддержки производителя попытаться выведать алгоритм CRC или его название (Modbus, CCITT и др.)... Это не должно быть большим секретом.
Вычисление CRC некоторыми распространёнными алгоритмами — это для самопроверки...

Нет, тут без вариантов.
Этот производитель своим АСЦ запрещает ремонт блоков на компонентном уровне, какой уж тут алгоритм... Все что известно - что там точно используется CRC.
Есть программа от этого производителя, и вот в ней этот алгоритм и реализован, то есть если в нормальном файле хоть бит поменять, она сразу же определяет этот файл как некорректный. Вот из этой бы программы вытащить алгоритм... Я специально смотрел, написана она на MVC++6, упаковщиком не запакована. Но у самого пока нет необходимых знаний, чтобы это осуществить (если это вообще возможно, конечно)

[insite2012]

Всем доброго дня. Продолжаю тему.
Пошарился по инету, по ссылкам, переделал код под свои нужды. CRC считает, корректно. Но есть несколько вопросов.
1. По самой программе. Как я понял, при создании экземпляра класса высчитывается таблица. Вопрос-что это за таблица значений, я так и не совсем понял ее назначение. Все-таки математических знаний не хватает, думаю, что когда-то изучал, уже подзабыл.
2. По коду. Есть ли возможность его реверснуть? То есть, если сейчас код высчитывает на основе полинома, начального значения и входной информации CRC, возможно ли сделать, чтобы код на основе уже известного значения CRC, начального значения и входных данных высчитал используемый полином. Это возможно?
Вот мой код.

Код: Выделить всё

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim CRC As CRC16 = New CRC16(&H0)
        Dim List As New ArrayList
        Dim InData() As Byte = Nothing
        Dim Dialog As New OpenFileDialog
        Dialog.FileName = Nothing
        Dialog.Filter = "eep files(*.eep)|*.eep|bin files(*.bin)|*.bin"   
        Dim CRC_My As String = ""
        If Dialog.ShowDialog = DialogResult.OK Then
            List.AddRange(My.Computer.FileSystem.ReadAllBytes(Dialog.FileName))
            ReDim InData(List.Count - 1)
            InData = List.ToArray(GetType(Byte))
            CRC_My = CRC.ComputeCheckSumString(InData)
            MsgBox("Контрольная сумма: " & CRC_My)
        End If
    End Sub
End Class

Public Class CRC16
    Private Const Poly As UInt16 = &H8005
    Dim Table(255) As UInt16
    Dim intValue As UInt16 = 0

    Public Function ComputeCheckSumString(ByVal Bytes() As Byte) As String
        Dim CRC As UInt16 = Me.intValue
        For i As Integer = 0 To Bytes.Length - 1
            CRC = CUInt((CRC << 8) Xor Table(((CRC >> 8) Xor (&HFF And Bytes(i)))))
        Next
        Return CRC.ToString("X2")
    End Function

    Public Sub New(ByVal InitialValue As UInteger)
        Me.intValue = CUInt(InitialValue)
        Dim temp, a As UInt16
        For i As Integer = 0 To Table.Length - 1
            temp = 0
            a = CUInt(i << 8)
            For j As Integer = 0 To 7
                If ((temp Xor a) And &H8000) <> 0 Then
                    temp = CUInt((temp << 1) Xor Poly)
                Else
                    temp <<= 1
                End If
                a <<= 1
            Next
            Table(i) = temp
        Next
    End Sub
End Class


[FireFenix]

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

Тут математика не причём, это ваше не знание алгоритма и способов возможных оптимизаций

Есть ли возможность его реверснуть? То есть, если сейчас код высчитывает на основе полинома, начального значения и входной информации CRC, возможно ли сделать, чтобы код на основе уже известного значения CRC, начального значения и входных данных высчитал используемый полином. Это возможно?

Очевидно, что возможно

[insite2012]

Тут математика не причём, это ваше не знание алгоритма и способов возможных оптимизаций
Очевидно, что возможно

Если не трудно, разъясните по этой таблице и ее значениям. Сколько ни читал по CRC, кое-что, конечно, понял, но все равно не до конца.

[iGrok]

http://piclist.ru/S-CRC16-RUS/CRC16.html
http://embedded.ifmo.ru/embedded_old/ET ... /crc32.htm

[insite2012]

Ага... Ну в принципе, я тоже так и предполагал, что эта таблица высчитывается из значения полинома как предварительная, чтобы не вычислять ее в самой функции просчета CRC. И если так, ее размер зависит от размерности CRC. В данном случае 256 (16х16). Для CRC8, к примеру, она будет уже 64 (8х8). Думаю, для моих целей (если следовать такому же алгоритму), придется сначала на основе имеющейся CRC и входного массива байт просчитать все значения такой таблицы, а потом по ней уже высчитывать полином. Ну или сначала написать полный код просчета, без таблицы, и уже потом его реверсить в обратную сторону.

[insite2012]

Всем доброго времени. Ну, с помощью MSDN удалось написать более-менее приемлемую функцию просчета CRC, без использования таблицы. Правда, не все понятно в алгоритме, потому есть вопросы. Вот мой код.

Код: Выделить всё

Private Function ComputeCRC16(ByVal Bytes() As Byte) As String
        Dim Poly As UInt16 = &H8005
        Dim CRC As UInteger
        Dim Temp As UInteger
        CRC = &HFFFF
        For i As Integer = 0 To Bytes.Length - 1
            Temp = Bytes(i) * &H100
            CRC = CRC Xor Temp
            For j As Integer = 0 To 7
                If (CRC And &H8000) > 0 Then
                    CRC = ((CRC * 2) Xor Poly) And &HFFFF
                Else
                    CRC = (CRC * 2) And &HFFFF
                End If
            Next
        Next
        CRC = CRC Xor &HFFFF
        Return CRC.ToString("X2")
    End Function

Начало понятно, инициализация переменных. Дальше берется первый байт. На &H100 он умножается, как я понимаю, для создания двухбайтного представления. Дальше он Xor-ится с начальной суммой. Тоже вроде понятно. А вот в циклах уже не совсем.
1. Не пойму, зачем используется вот это выражение:(CRC And &H8000) Что это дает?
2.И вот тут: ((CRC * 2) Xor Poly) And &HFFFF, зачем умножение на 2 и логическое сложение с &HFFFF (хотя по сложению, как я думаю, используется, если значение отрицательное).
Вот такие 2 вопроса. извиняюсь, если кому-то они покажутся не очень компетентными, но я считаю, что прежде чем пытаться реверсить этот код, надо сначала полностью понять, как он работает. Иначе будет пустая трата времени.
Ну и уже по будущему реверсингу: если я правильно понимаю, придется идти от обратного: брать готовую КС, Xor-ить ее, и начинать с последнего байта данных и двигаться от конца массива к началу. Я прав в своих предположениях?

[Qwertiy]

логическое сложение

Ничего себе! Назвать побитовый and логическим сложением!!!

[insite2012]

Ничего себе! Назвать побитовый and логическим сложением!!!

Ув.Qwertiy, ну я же только учусь, мне простительны ошибки. Подскажите, в чем ошибаюсь, буду постигать науку постепенно)
Ага, посмотрел по операторам. And это побитовое умножение, как я понял...

[Qwertiy]

Подскажите, в чем ошибаюсь, буду постигать науку постепенно)

В том что And - побитовый оператор, а AndAlso - логический. Если только ты не на VB2003 пишешь. Но применение логических операторов в данном контексте - полный бред.
А ещё в том, что and - это умножение, а or - сложение. Но беспричинно называть их этими словами вообще как-то странно в контексте программирования - это же не математика всё-таки.

And &HFFFF

Это приведение к двухбайтовому числу с игнорированием переполнения. Точнее, оно ничего не приводит, а только обнуляет всё что выходит за 2 байта.

And &H8000

Проверка знака у двухбайтового числа...
Знаю что непонятно, на как понятнее объяснить - не знаю.

[insite2012]

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

[Qwertiy]

А зачем умножение на 2 стоит?

Не знаю. Это надо теорию алгоритма подсчёта изучать.

[insite2012]

Понял. Большое спасибо за ответы, уже многое становится понятнее, чем до этого.

[FireFenix]

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

Зачем вообще делать код без таблицы? разница то ?
Да нет ничего проще даже сделать без таблицы, просто на каждом цикле считать значение ячейки таблицы, т.е. скопипастить код генерации таблицы в расчёт 1го цикла

Ну, с помощью MSDN удалось написать более-менее приемлемую функцию просчета CRC, без использования таблицы. Правда, не все понятно в алгоритме, потому есть вопросы.

Ну как, как можно написать код и не понимать как он работает!

Ну и уже по будущему реверсингу

Какой ещё реверсинг, если перед тобой наглядный исходный код?

В новом "написанном" примере аж целых 8 строк с математическими операциями. И зачем для каждой строки лезть на форум то? неужели так сложно погуглить или почитать вики? Да даже в калькуляторе посмотреть что и как будет!

С таким подходом, нужно начинать не с циклических кодов, а с учебника "дискретной математики" и "языка программирования"!

[insite2012]

Можно написать... Еще как можно, и не понимать, как он работает)
А на форум обращаюсь потому, что знаний (именно по программированию) - почти никаких, кроме того, что вычитал в учебниках. Взгляните на дату регистрации. Это как раз тот момент, когда я и занялся написанием программ. До этого все мои знания (по данной области) оканчивались уроками информатики. И естественно, я и гуглил, и вики (да и не только) читал, иначе бы и то, что сейчас уже могу сделать не сделал бы. Думаю, не все родились перед экраном монитора и со знанием нескольких языков программирования в голове, верно? Все когда-то и чему-то учились. Для меня сейчас как раз такой момент-учусь, что непонятно-спрашиваю.
Уверяю Вас, ув. FireFenix, есть области, в которых наше положение диаметрально противоположно - мне там все понятно, а Вам это будет очень сложно, реши Вы заняться этим делом.
Если не сложно, подскажите, направьте на путь, как добиться поставленной цели и сделать обратную операцию - просчет полинома на основе имеющейся КС...

[pronto]

Дело может быть не только в начальном полиноме и/или таблице начальных значений, но и в самом алгоритме расчёта. Поэтому нужно реверсить или брутить...

[insite2012]

Дело может быть не только в начальном полиноме и/или таблице начальных значений, но и в самом алгоритме расчёта. Поэтому нужно реверсить или брутить...

Алгоритм расчета там однозначно CRC. Это все, что известно точно. Ну и еще окончательный результат, контрольная сумма.
Если кратко, есть массив байт. В конце этого массива прописана КС. И вот все, что до нее, просчитывается и сравнивается с прописанной КС. Если будет несовпадение-массив считается поврежденным и не пригодным к использованию в качестве файла конфигурации.

[pronto]

Можешь выложить файл конфигурации с соответсвующей КС?
Умножение на 2^n даёт сдвиг на n бит влево, а деление — сдвиг вправо. Поэтому умножение на 2 — это сдвиг влево на один бит, а умножение на 4 — сдвиг влево на 2 бита, и тд...

[insite2012]

Естественно, могу. Сейчас...
Считается КС файла с адреса 0х0000 до 0х18BB (естественно, это только к этому файлу относится). Следующие 2 байта, то есть адреса 0х18BC и 0х18BD и есть КС этого файла (для уточнения: КС - 5434). Все что дальше-роли для файла не играет. Это точно, программа (производителя, которая ее может считать) именно так и показывает.

[pronto]

Для этого файла функцией ComputeCRC16 какая КС получается у тебя?
ухожу до завтра...

[insite2012]

Для части файла (без реальной КС и все что дальше) - &HBE1B, для всего файла - &H46AF. Полином - &H8005

[FireFenix]

Можно написать... Еще как можно, и не понимать, как он работает)

Это называется - передрать в слепую код.

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

Да причём тут это? Причём тут вообще программирование в целом?
Здесь я с 2007 года, на других ресурсах есть и пораньше, да даже если сейчас спросить Хакера, он скажет, что я дурак и вообще не шарю программирование. Разница не велика!

Для меня сейчас как раз такой момент-учусь, что непонятно-спрашиваю.

Ладно бы если проблемы с алгоритмом, сложно или что-то ещё, но ведь Вы спрашивает основы, основы математики, которые легко Самому проверить в калькуляторе или отладчике или прочитать в интернете/учебниках при должном желании.

Уверяю Вас, ув. FireFenix, есть области, в которых наше положение диаметрально противоположно - мне там все понятно, а Вам это будет очень сложно

Вы осознано стали или становитесь программистом. Любой программист как и гений это 99% усердия и 1% вдохновения.

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

Вначале ознакомиться с данными документами
viewtopic.php?p=6754310
http://citforum.ru/howto/smart-questions-ru.shtml#intro -> Особенно уделить внимание разделу Прежде, чем спрашивать...

Когда будет ясность в базовом алгоритме решения всех проблем - начать с правильной постановки задачи, т.к. правильный вопрос - 50% ответа.

Возможно вы изначально не правильно поставили задачу. Вы сказали, что у вас имеется программа, тогда зачем писать или изучать алгоритмы CRC? можно просто открыть из под дизассемблера и передрать весь код (если там замешано SSE и прочий хардкор, то конечно по сложне, но IDA + HexRay облегчат ситуацию). Если программа написана под .NET, то под Reflect'ором вообще почти чистые сырцы, только Ctrl+C Ctrl+V в свой проект.

Если вы действительно стремитесь изучить программирование, алгоритмы и прочее, то пожалуйста - Начните тратить своё время на самостоятельное изучение, отладку и различные подходы! ибо это сэкономит всем время и силы. Честно, когда человек пришёл на форум программистов и спрашивает по базовым математическим операциям - это есть не уважение к участникам форума и становится подозрение, что человек использует участников для собственной выгоды, не приложив никаких усилий самостоятельно в изучении.

[insite2012]

По порядку.
Да, согласен, легко проверить в калькуляторе (что и делаю). Но мне непонятно сама ЛОГИКА работы операторов, в вышеприведенном мной коде. Вот выше человек ответил, зачем там идет умножение на 2 - и сразу многое стало ясно.
Далее. Становлюсь - ну это, возможно, сильно сказано. Основная область деятельности-иная, но там, тоже, не помешает умение писать (хоть и простенькие) программы. Потому и занялся, по учебникам и по интернету. Кое-что уже написано, и работает довольно не плохо, хотя, возможно, программист с большим опытом сделал бы это более изящно... И все свободное время, когда не занят, именно тем и занимаюсь-читаю книги, интернет и прочее. Но поскольку, как правило, большинство примеров приведены абстрактно, то без подсказок трудно их применить в реальном проекте.
И последнее. Да, программа как бы есть, но как я указывал выше, написана она (как я понял) на MVC6.0, дизассемблировать мне ее точно не удастся (если уж я в простых операторах путаюсь). Так что задача поставлена именно так, как (по моему предположению) именно я смог бы ее решить. Умей я понимать, что пишет IDA, естественно, то и написание программы бы не понадобилось.
PS.
Всем спасибо за участие, в любом случае, эта тема оказалась для меня очень полезной, в плане познания работы операторов. Одно дело-прочитать на сайте MSDN, а совершенно другое-увидеть в реальной работе.
Что касается проблемы-я нашел выход. Может немного и не так, как предполагал вначале, но все же...
Функция просчета CRC16 у меня есть, входные данные и искомая контрольная сумма тоже. Поставил цикл перебора всех значений полинома от 0х0000 до 0хFFFF и выход из цикла по искомой КС. Возможно, это и не очень верно, но главное-цель достигнута.
Еще раз всем спасибо.

[pronto]

О, молодец! По сути это и есть «brute force» — решение проблемы путём перебора всех возможных вариантов. И какой полином у тебя получился? Кстати, его нужно проверить и на других конфигурациях, чтобы быть окончательно уверенным в его правильности...