Разработка программы "Формирование и проверка контрольной суммы кластеров" (стр. 1 из 5)
ВВЕДЕНИЕ
Сложно переоценить важность такого устройства, как персональный компьютер. Интеграция компьютеров в повседневную жизнь людей достигла очень высокого уровня, что позволяет спрогнозировать еще большую компьютеризацию всех сфер жизни. Такая ситуация сложилась благодаря тому, что компьютер превратился в широко распространённое и гибкое средство для решения разнообразных задач.
Персональный компьютер, как известно, является универсальным устройством для обработки информации. Персональные компьютеры могут выполнять практически любые действия по обработке информации. Для этого необходимо составить для компьютера на понятном ему языке точную и подробную последовательность инструкций (программу), как надо обрабатывать информацию.
Абсолютное большинство всех персональных компьютеров мира работают под операционной системой Windows разных версий. Поэтому и большинство программ, которые создаются, созданы для использования именно под ОС Windows. Несложно понять потенциальную применимость любой программы, ведь работа нескольких профессиональных программистов может помочь миллионам пользователей в их работе, разнообразить их досуг, облегчить общение и многое другое.
В современных условиях разработки программного обеспечения сложно придумать что-нибудь новое, поэтому практически в каждом направлении разработки прикладных программ ведется ожесточенная борьба «за пользователя». Если раньше программа должна была всего лишь выполнять определенные функции, то теперь она должна обладать еще и рядом дополнительных свойств: удобным интерфейсом, простотой использования, гармоничностью дизайна.
1 ОБЩИЕ СВЕДЕНИЯ В ОБЛАСТИ ФОРМИРОВАНИЯ КОНТРОЛЬНОЙ СУММЫ И ПРОВЕРКИ КЛАСТЕРОВ
Целью данного курсового проекта является разработка программного обеспечения под названием «Подсчет и проверка контрольной суммы кластеров». Очевидно, что для выполнения задания в приложении должны быть реализованы функции просмотра параметров жесткого диска указанной операционной системы и анализа его структуры, также подсчета контрольной суммы. Следует отметить, что для понимания программных возможностей разрабатываемой программы необходимы конкретные знания о предметах исследования – стуктура файловых систем Windows и контрольная сумма.
1.1 Основные элементы в файловой системе Windows и их взаимодействие
Файловая система (англ. filesystem) — регламент, определяющий способ организации, хранения и именования данных на носителях информации. Она определяет формат физического хранения информации, которую принято группировать в виде файлов. Конкретная файловая система определяет размер имени файла (папки), максимальный возможный размер файла и раздела, набор атрибутов файла. Некоторые файловые системы предоставляют сервисные возможности, например, разграничение доступа или шифрование файлов.
Файловая система связывает носитель информации с одной стороны и API для доступа к файлам — с другой. Когда прикладная программа обращается к файлу, она не имеет никакого представления о том, каким образом расположена информация в конкретном файле, так же, как и на каком физическом типе носителя (CD, жёстком диске, магнитной ленте или блоке флеш-памяти) он записан. Всё, что знает программа — это имя файла, его размер и атрибуты. Эти данные она получает от драйвера файловой системы. Именно файловая система устанавливает, где и как будет записан файл на физическом носителе (например, жёстком диске).
С точки зрения операционной системы, весь диск представляет собой набор кластеров размером от 512 байт и выше. Драйверы файловой системы организуют кластеры в файлы и каталоги (реально являющиеся файлами, содержащими список файлов в этом каталоге). Эти же драйверы отслеживают, какие из кластеров в настоящее время используются, какие свободны, какие помечены как неисправные.
Кластер (англ. cluster) — в некоторых типах файловых систем логическая единица хранения данных в таблице размещения файлов, объединяющая группу секторов. Например, на дисках с размером секторов в 512 байт, 512-байтный кластер содержит один сектор, тогда как 4-килобайтный кластер содержит восемь секторов.
Как правило, это наименьшее место на диске, которое может быть выделено для хранения файла.
Понятие кластер используется в файловых системах FAT и NTFS. Другие файловые системы оперируют схожими понятиями (зоны в Minix, блоки в Unix).
Рисунок 1.1 – Структура диска
На рисунку 1.1 показаны основные элементы структуры диска:
A. Дорожка.
B. Геометрический сектор.
C. Сектор дорожки.
D. Кластер.
1.2 Понятие контрольной суммы, ее предназначение
Контрольная сумма — некоторое значение, рассчитанное из последовательности данных путём применения определённого алгоритма, используемое для проверки правильности передачи данных (для исключения влияния каких-либо помех при передаче).
С точки зрения математики контрольная сумма является хеш-функцией, используемой для вычисления контрольного кода — небольшого количества бит внутри большого блока данных, например, сетевого пакета или блока компьютерного файла, применяемого для обнаружения ошибок при передаче или хранении информации. Значение контрольной суммы добавляется в конец блока данных непосредственно перед началом передачи или записи данных на какой-либо носитель информации. Впоследствии оно проверяется для подтверждения целостности данных.
Популярность использования контрольных сумм для проверки целостности данных обусловлена тем, что подобная проверка просто реализуема в двоичном цифровом оборудовании, легко анализируется и хорошо подходит для обнаружения общих ошибок, вызванных наличием шума в каналах передачи данных.
Одним из методов подсчета контрольной суммы является циклический избыточный код (в частности, CRC32), применяется для проверки целостности передачи данных. Программы-архиваторы включают CRC исходных данных в созданный архив для того, чтобы получающий мог удостовериться в корректности полученных данных. Такая контрольная сумма проста в реализации и обеспечивает низкую вероятность возникновения коллизий.
Алгоритм вычисления контрольной суммы (англ. Cyclic redundancy code, CRC — циклический избыточный код) — способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её циклического избыточного кода.
Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем GF(2). Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.
Каждой конечной последовательности битов
взаимно-однозначно сопоставляется двоичный многочлен 
, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:
Нетрудно видеть, что количество различных многочленов степени меньшей N равно 2N, что совпадает с числом всех двоичных последовательностей длины N.
Значение CRC с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):
где:
R(x) — многочлен, представляющий значение CRC.
P(x) — многочлен, коэффициенты которого представляют входные данные.
G(x) — порождающий многочлен.
— степень порождающего многочлена.
Умножение xN осуществляется приписыванием N нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.
При делении с остатком степень многочлена-остатка строго меньше степени многочлена-делителя, то есть при делении на многочлен G(x) степени N можно получить 2N различных остатков от деления. При «правильном» выборе порождающего многочлена G(x), остатки от деления на него будут обладать нужными свойствами хеширования — хорошей перемешиваемостью и быстрым алгоритмом вычисления. Второе обеспечивается тем, что степень порождающего многочлена обычно пропорциональна длине байта или машинного слова (например 8, 16 или 32).
Операция деления на примитивный полином также эквивалентна следующей схеме:
Пусть выбран примитивный полином, задающий цикл де Брейна 0010111001011100… и блок данных 0111110, построена таблица, верхняя строка заполнена блоком данных, а нижние строки — смещения на 0,1,2 бит цикла де Брейна
Тогда контрольная сумма будет равна операции XOR тех столбцов, над которыми в верхней строке расположена 1. В этом случае, 010 xor 101 xor 011 xor 111 xor 110 = 101 (CRC).
Алгоритм CRC32, используемый данным проектом, основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7) и является одним из самых распространенных методов подсчета контрольной суммы.
Еще используется криптографический алгоритм MD5.
MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины. Является улучшенной в плане безопасности версией MD4.[1] Зная MD5-образ (называемый также MD5-хеш или MD5-дайджест), невозможно восстановить входное сообщение, так как одному MD5-образу могут соответствовать разные сообщения. Используется для проверки подлинности опубликованных сообщений путём сравнения дайджеста сообщения с опубликованным. Эту операцию называют «проверка хеша» (hashcheck).