Алгоритм вычисления контрольной суммы

Рассмотрим алгоритм вычисления контрольной суммы (КС).

КС — способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её кода.

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

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

P(x) = 1 * x6 + 0 * x5 + 1 * x4 + 1 * x3 + 0 * x2 + 1 * x1 + 0 * x0

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

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

R(x) = P(x) * xr mod G(x)

(6.1)

где

R(x) — контрольный код многочлена P(x).

P(x) — исходный многочлен.

G(x) — порождающий многочлен.

r — степень порождающего многочлена.

Применим алгоритм к поиску КС, если задано:

Р(х) = 90, х = 2.

Пусть G(x)= 1 * x3 + 0 * x2 + 1 * x1 + 0 * x0 – этот полином скрыт от передачи и не изменен.

r=3, G(x) = 8 + 0 + 2 + 0 = 10. Тогда, согласно формуле получим:

R(x) = 90 * 2r mod 10=90*8 mod 10 = 720 mod 10 = 0.

Продолжим решение и внесем изменение в передаваемую информацию, изменив только один последний бит, получим число 91 (1011011 в двоичной записи) соответствует многочлену следующего вида:

P(x) = 1 * x6 + 0 * x5 + 1 * x4 + 1 * x3 + 0 * x2 + 1 * x1 + 1 * x0

Далее действуем по аналогии с выше рассмотренными действиями. Получим:

Р(х) = 91, х = 2.

Пусть G(x)= 1 * x3 + 0 * x2 + 1 * x1 + 0 * x0

r=3, G(x) = 8 + 0 + 2 + 0 = 10. Тогда, согласно формуле получим:

R(x) = 91 * 2r mod 10=91*8 mod 10 = 728 mod 10 = 8.

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

Порядок выполнения самостоятельной работы

1. Возьмите любое число P, например, трехзначное. Представьте его в двоичной системе счисления (x=2). Получим

полином P(х), который будет передаваться по каналу связи вместе с КС блоками по 8 бит.

2. В качестве порождающего полинома возьмите G(x) = 1 * x3 + 0 * x2 + 1 * x1 + 1 * x0 , где степень полинома r = 3.

3. Вычисли число порождающего полинома G(x).

4. Вычислим контрольный код по формуле (6.1) и представим его объемом 8 бит, добавляя незначащие нули слева.

5. Присоединим КС к передаваемому числу в конец блока из 8 бит.

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

сбой в системе или нет.

Ассиметричное шифрование

Цель работы – изучить принципы ассиметричного шифрования, алгоритм RSA и уметь его применять в задачах ассиметричного шифрования.

Функциональная схема взаимодействия участников асимметричного криптографического обмена представлена на рис. 7.1.

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

Рис. 7.1. Функциональная схема асимметричной криптосистемы

Отправитель B, зная открытый ключ получателя А, может зашифровать на данном ключе открытый текст и переслать его пользователю А. Пользователь А с помощью своего секретного ключа, соответствующего ОКА, может дешифровать присланное пользователем B сообщение. Злоумышленник, зная ОКА и закрытый текст, не может получить доступ не к СКА, не к открытому тексту.

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

1. Пользователь A генерирует ключевую пару (ОКА,СКА).

2. Пользователь B генерирует ключевую пару (ОКB,СКB).

3. Пользователи A и B должны обменяться своими открытыми ключами. Пользователь А передает свой открытый ключ ОКА пользователю B, пользователь B передает свой открытый ключ ОКB пользователю A.

4. Пользователь А шифрует информацию для пользователя B на ключе ОКB, пользователь B шифрует информацию для пользователя A на ключе ОКA.

5. Пользователь А дешифрует информацию, присланную ему от пользователя B, на ключе СКА, пользователь B дешифрует информацию, присланную ему от пользователя A, на ключе СКB.

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

У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы [6]:

1. Вычисление ключевой пары (ОК, СК) должно быть достаточно простым.

2. Отправитель, зная открытый ключ получателя, может легко получить шифротекст.

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

4. Знание открытого ключа злоумышленником не должно влиять на криптостойкость системы. При попытке вычислить злоумышленником закрытый ключ по открытому, он должен наталкиваться на непреодолимую вычислительную проблему.

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

Алгоритм шифрования RSA

В криптосистеме RSA открытый ключ ОК, секретный ключ СК, исходное сообщение М и шифротекст С являются целыми числами от 0 до N-1, где N – модуль. Пусть пользователь А является получателем сообщения, которое ему должен переслать отправитель B. Пользователь A должен вначале сгенерировать ключевую пару RSA, это он делает следующим образом.

Статьи к прочтению:

57.CRC алгоритм (Урок 48. Теория)

Похожие статьи: