вычисление синдрома бчх кода

Новые методы диагностики COVID-19

Поведение нового коронавируса, который вызывает COVID-19, изучают ученые по всему миру. Совершенствуются методы диагностики, направленные на выявление в организме SARS-CoV-2. В конце 2020 года на рынке лабораторных исследований были представлены более 300 разных тестов:

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

ДИЛА одной из первых частных лабораторий Украины начала тестирование на COVID-19 методом ПЦР и имеет уникальный для Украины экспертный опыт, приобретенный на базе 241 184* проведенных тестов!

Одной из последних разработок стали тесты на определение специфических антигенов вируса SARS-CoV-2. У них есть как преимущества, так и недостатки: они более доступны и результат можно получить прямо на месте тестирования в течение 20 минут. Однако чувствительность этих тестов ниже по сравнению с ПЦР, потому как результат теста на АГ, как правило, напрямую зависит от вирусной нагрузки. Антиген-тесты в мазке из носо-, ротоглотки выявляют белки коронавируса SARS-CoV-2, которые синтезируются в ходе репликации и результат также очень зависим от качества и места взятия материала. На сегодня многие компании по всему миру заняты разработкой тестов для выявления антигенов коронавируса SARS-CoV-2. Однако это исследование имеет свои особенности и ограничения применения. Какие именно, расскажут эксперты ДИЛА.

*данные Центра общественного здоровья МОЗУ состоянием на 01.02.2021 г.

В чем заключаются отличия метода ПЦР и антиген-теста

Метод ПЦР – золотой стандарт диагностики, регламентированный Министерством здравоохранения Украины и рекомендованный Всемирной организацией здравоохранения для установления наличия/отсутствия возбудителя коронавирусной болезни.

ДИЛА предлагает выбор ПЦР исследований в зависимости от необходимости срока получения результата:

Когда показан ПЦР тест:

Современные возможности ПЦР диагностики позволяют ответить на вопрос: присутствует или нет вирус в данном мазке, а также определить вирусную нагрузку (ВН): как много вирусных частиц в 1 мл исследуемого материала (может быть высокая, средняя, низкая). От показателя ВН напрямую зависит контагиозность (заразность) инфицированного человека для окружающих.

Материалом для ПЦР исследования на определение COVID 19 может служить мокрота, смывы с бронхов, кал

Как определяется ВН и ЧТО означает показатель Сt**.

Для условного определения ВН используют показатель «пороговый цикл», обозначенный в результате анализа как Сt (Сycle threshold). Он показывает, сколько циклов амплификации произошло для достижения порога обнаружения вирусной РНК в образце. С каждым циклом количество копий РНК удваивается. Чем больше вирусных частичек в образце, тем быстрее их выявит тест-система и тем ниже будет показатель Ct.

Обычно ПЦР в реальном времени происходит в течение 40 циклов. После каждого цикла оценивают наличия свечения (флюоресценции), которое исходит от меченых фрагментов РНК возбудителя.

Тест для определения антигена SARS-CoV-2 основан на выявлении в биоматериале специфического белка, который принадлежит нуклеокапсиду коронавируса

Для исследования используется материал тот же, что и в большинстве случаев для проведения ПЦР – соскоб из носо- и ротоглотки. Большим плюсом является то, что результат можно получить на месте уже через 20 минут. Также положительным моментом служит его стоимость – экспресс-тесты более доступны, так как для проведения тестирования не требуется дорогостоящее оборудование, квалифицированный персонал, современные лаборатории.

Тест на антиген способен выявить присутствие COVID-19 в том случае, когда вирусная нагрузка высокая, т.е. в носоглотке находятся сотни тысяч и миллионы копий вируса, что чаще бывает в начале заболевания или в период разгара коронавирусной болезни. При средней или низкой вирусной нагрузке тест может дать ложноотрицательный результат.

В основном экспресс тесты предназначены для «быстрого реагирования»:

Положительный результат теста на антиген при наличии симптомов заболевания свидетельствует о том, что человек болен COVID-19. Однако если результат теста положительный, а проявления отсутствуют, необходимо в течение ближайших двух дней провести ПЦР тест для подтверждения полученных результатов теста на антиген.

Отрицательный тест на антиген не исключает наличие COVID-19:

В данном случае для подтверждения антиген-теста используется ПЦР.

Также данный вид тестирования не рекомендуется для проведения лицам с подозрительным и вероятным случаем COVID-19 без клинических проявлений, у которых количество вирусов в носоглотке может быть небольшим и быстрый АГ тест не сможет их выявить.

Отрицательный тест на антиген не является заключением о выздоровлении после коронавирусной болезни, разрешительным документом для досрочного снятия с самоизоляции в сервисе «Дій вдома» в случае прибытия из стран «красной зоны». В этих случаях также требуется результат ПЦР.

Иммунохемилюминесцентный анализ (ИХЛА) – методика выявления антител (иммуноглобулинов) IgM и IgG к коронавирусу. В ДИЛА проводится определение:

ИХЛА позволяет подтвердить или исключить факт встречи с вирусом SARS-COV-2 и оценить наличие иммунного ответа к нему. Метод направлен на полуколичественное обнаружение антител, которые указывают на то, что человек сейчас болен COVID-19 (IgM) или переболел ранее к SARS-COV-2 (IgG), а также дает возможность оценить иммунный ответ в динамике.

ИХЛА – метод серологической диагностики, обладающий весомыми преимуществами по сравнению с методом ИФА (иммуноферментный анализ):

ИХЛА исследования показаны:

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

Иммуноглобулины (антитела) каждого класса появляются, а затем снижаются ниже порога обнаружения в определенный отрезок времени, который зависит от индивидуальных особенностей организма. Например, антитела могут начать вырабатываться гораздо позже, или если антитела класса М уже снизились ниже порога определения, то прибор определит антитела класса G, и наоборот. В таком случае определение суммарных антител имеет значительные преимущества по сравнению с обнаружением IgG и IgM по отдельности за счет большего временного диапазона определения иммунного ответа и позволяет перекрыть «серологические окна», что значительно повышает чувствительность тест-систем.

Как используются тесты для диагностики COVID-19

Разные тесты служат для разных целей

Исследование на антитела lgM позволяет:

Исследование на антитела lgG позволяет:

Они направлены на прямое определение антигена (нуклеокапсидного белка) SARS-CoV-2 иммунохроматографическим методом в образцах соскобов из носоглотки человека, что позволяет с высокой вероятностью предположить инфицирования вирусом (SARS-CoV-2).

Исследование методом ПЦР позволяет:

Диагностический экспресс-тест – скрининговое исследование, оправданное в условиях ограниченной доступности ПЦР, а также когда продолжительность ожидания результата ПЦР-исследования исключает его клиническую эффективность. Он позволяет непосредственно на месте получить качественную оценку касательно заражения. Поэтому экспресс-тесты уместны, если результаты нужно получить максимально быстро у лиц с подозрительным и вероятным случаем COVID-19. Кроме того, исследование методом полимеразной цепной реакции требуется во всех официальных случаях: при выезде за границу, возвращении из стран с высоким уровнем распространением инфекции с целью досрочного прекращения самоизоляции. Во всех этих случаях в качестве подтверждения отсутствия инфекции SARS-CoV-2 рассматриваются исключительно результаты ПЦР.

Быстрый тест на антиген можно сдать в отдельных отделениях, предварительно заполнив Анкету-направление на сайте

Источник

Применение помехоустойчивых кодов в криптографии

Contents

Введение

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

Появлением помехоустойчивого кодирования считается 1948г, когда была опубликована статья Клода Шеннона «Математическая теория связи». Из идей, изложенных в данной статье, следует важный вывод: построение слишком хороших каналов является расточительством; экономически выгоднее использовать кодирование. Однако Шеннон лишь доказал существование данных кодов. С пятидесятых годов начались активные исследования кодов, позволяющих получить сколь угодно малую вероятность ошибки. К настоящему времени эти исследования привели к образованию множества классов помехоустойчивых кодов.

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

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

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

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

Математические основы

Механизм помехоустойчивого кодирования в современных системах передачи информации реализуется с использованием кодеров и декодеров различной конфигурации, сложности и принципам работы. Пусть при передаче информации источник сообщений генерирует последовательность символов. Символы выбираются из конечного множества А, |A| = q, которое называется алфавитом источника. Сообщение поступает на вход кодера, который преобразует входные символы. После прохождения сигнала через дискретный канал передачи, сигнал поступает на вход декодера. Декодер должен выдать получателю передаваемое сообщение. Для этого декодер осуществляет анализ полученной последовательности.

Пусть дан произвольный вектор . Нормой, или весом Хэмминга, вектора называется число его ненулевых координат, обозначается |x|. Расстоянием Хэмминга между векторами x и y называется норма их разности |x-y|.

Пусть дан код C с векторами . Кодовым расстоянием в метрике Хэмминга называются число , равное минимальному из попарных расстояний между его векторами: .

Кодовое расстояние определяет способность кода исправлять ошибки. Пусть и при передаче некоторого кодового слова по каналу произошли ошибки точно в t позициях этого слова. Тогда существует декодер, способный правильно определить переданное по каналу связи кодовое слово при условии, что .

Линейные блочные коды

Блоковое кодирование состоит в том, что последовательность символов источника сообщений разбивается на блоки по k символов в каждом. Кодер преобразует входной k-блок в выходной n-блок по определенному правилу, таким образом, чтобы различным входным блокам соответствовали различные выходные блоки. При этом n ≥ k, иначе нашлись бы одинаковые входные блоки для одного выходного.

Рассматриваются входные блоки длины k, , где a – буквы «укрупненного» алфавита . В свою очередь выходные блоки являются буквами укрупненного алфавита . Совокупность таких различных букв x(a) называется блоковым кодом длины n и мощности .

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

Любое линейное подпространство С можно задать с помощью базиса из k линейно независимых векторов. Число k называется размерностью подпространства. Линейным (n,k)-кодом называется k-мерное линейное подпространство. Линейные коды играют важную роль, прежде всего потому, что для них проста процедура кодирования.

Для нелинейного кода объемом необходимо помнить все кодовых последовательностей. Для линейного кода можно ограничиться хранением лишь k векторов или эквивалентной порождающей матрицей кода G.

Для кодирования достаточно знать k-блок . Тогда кодовый вектор g получается путем умножения этого вектора на порождающую матрицу кода: . Также линейный код можно задать проверочной матрицей кода H размера rxn с линейно независимыми строками, где , причем . Следовательно, любое кодовое слово будет удовлетворять уравнению . Оба способа задания кода эквивалентны.

Если в таких кодах , то такие коды называют МДР-кодами, то есть разделимыми кодами с максимальным расстоянием. В остальных случаях .

Коды Рида-Соломона

Код Рида-Соломона (РС код) над полем – код, состоящий из всех слов длины n, для которых выполняются уравнение: , где ― различные ненулевые элементы поля , называемые локаторами i-ой позиции слова. Число различных локаторов определяет максимальную длину кода Рида-Соломона. Параметры кодирования (n,k,d), где n ― длина, k ― размерность, d ― минимальное расстояние. Любой набор из k позиций кодового слова является информационным, то есть позволяет восстановить все зашифрованное слово.

Алгоритм кодирования следующий. Пусть I ― множество k информационных позиций кодового слова и π множество проверочных позиций. На информационных позициях размещены k символов сообщения, на проверочных размещены нули. Рассматриваются суммы: Задача состоит в том, чтобы вычислить и записать на проверочных позициях такие символы , которые удовлетворяют данным суммам.

Значения проверочных символов могут быть найдены из системы линейных уравнений:

Рассмотрим алгоритм декодирования. Пусть ― принятая последовательность символов. , где – символ кодового слова, ― значение ошибок из поля . Обнаружение ошибок состоит в проверке условий, определяющих задание РС кода. Синдромом называется вектор . Если данное значение равно нулю для всех возможных j, то принятое слово является кодовым. В противном случае кодовое слово содержит ошибки. Синдром зависит только от ошибок в принятом слове.

На основе определения синдрома строится многочлен вида: Предполагается, что в переданном слове содержится ровно t ошибок в позициях с номерами . После преобразований получается уравнение вида , где ― многочлен локаторов ошибок, называемый так потому, что его корни являются обратными величинами локаторов искаженных позиций. Многочлен называют многочленом значений ошибок.

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

Коды Гоппы

Код Гоппы Г(L,G) состоит из всех q-ичных векторов , для которых выполняется следующее сравнение: где ― многочлен степени t с коэффициентами из поля , называемый многочленом Гоппы, и элементы образуют подмножество , называемое множеством нумераторов позиций кодового слова.

Размерность k и минимальное расстояние d этих кодов удовлетворяет следующим неравенствам: Величину принято называть конструктивным расстоянием кода Гоппы.

Пусть при передаче кодового слова Γ(L,G)-кода имел место вектор ошибки такой, что число его ненулевых компонент не превышает половину , то есть половину конструктивного расстояния Γ(L,G)— кода.

Аналогично РС коду, составляется ключевое уравнение: и позволяющее исправлять число ошибок, определяемое величиной

Код Боуза-Чоудхури-Хоквингема

Код Боуза-Чоудхури-Хоквингема (БЧХ-код) является циклическим кодом, который можно задать порождающим полиномом. Циклическим кодом называется линейный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Для нахождения данного полинома в случае БЧХ-кода необходимо заранее определить длину кода n (она не может быть произвольной) и требуемое минимальное расстояние .

Пусть α – примитивный элемент поля , – элемент поля порядка n, . Тогда нормированный полином g(x) минимальной степени над полем , корнями которого являются подряд идущих степеней элемента β для некоторого целого является порождающим полиномом БЧХ-кода над полем с длиной n и минимальным расстоянием

Число проверочных символов r равно степени g(x), число информационных символов величина d называется конструктивным расстоянием БЧХ кода. Если , то код называется примитивным, иначе непримитивным.

Так же, как и для циклического кода, кодовый полином c(x) может быть получен из информационного полинома m(x), степени не больше , путём перемножения m(x) и g(x).

Криптографические схемы

Существует несколько ассиметричных криптосистем, основанных на помехоустойчивых кодах. Вообще говоря, задача декодирования произвольного линейного кода является NP-полной для хэмминговой и ранговой метрик. С другой стороны, в некоторых случаях для некоторых семейств кодов данная задача является полиномиальной. Таким образом, используя код, обладающим быстрым алгоритмом декодирования, можно сделать задачу декодирования для легального пользователя полиномиальной. При этом, при маскировании данного кода под случайный, данную задачу для нарушителя можно сделать чрезвычайно трудоемкой.

Такой подход позволяет строить однонаправленную функцию с лазейкой. Два основных типа криптосистем с открытым ключом, основанных на помехоустойчивых кодах были предложены МакЭлисом и Нидеррайтером. В первом случае публикуется порождающая матрица кода, а шифртекстом является кодовое слово, искаженное искусственной ошибкой. В другом случае публикуется проверочная матрица кода, а шифртекстом является синдром ошибки, которая является открытым текстом.

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

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

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

Данная криптосистема была предложена МакЭлисом в 1978 году. Основная идея состоит в маскировании линейного кода под код, не обладающей видимой алгебраической и комбинаторной структурой. Есть несколько разновидностей данной криптосистемы:

Основанная на кодах Гоппы

В этом случае алгоритм построения выглядит следующим образом.

Закрытый ключ состоит из:

Матрицы P и S необходимы для сокрытия структуры открытого ключа.

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

При шифровании случайным образом выбирается вектор длины над GF(2) с весом Хэмминга не более t. Затем идет вычисление шифртекста: .

Расшифрование производится в три этапа:

Достоинство данного алгоритма в том, что он работает на порядок быстрее алгоритма RSA. Недостатком является большой размер открытого ключа, вследствие чего данная система не сильно распространена.

Основанная на БЧХ-коде

Ниже описана идея построения криптосистемы МакЭлиса на примере (n,d)-БЧХ-кода размерности k.

Пусть A ― фиксированная порождающая матрица обобщенного (n,d)-БЧХ-кода над , то есть матрица ранга k и размера kxn, для которой , где матрица С имеет вид . В качестве А можно выбрать матрицу такого же вида.

Ансамбль порождающих матриц (n,d)-БЧХ-кода можно определить как множество матриц вида , где h пробегает множество всех невырожденных kxk матриц над , D ― множество всех матриц с ненулевыми элементами на диагоналях, Г ― множество всех перестановочных матриц размера nxn.

Ансамбль кодов определяется как множество всех кодов с порождающими матрицами из ансамбля . Матрицы h, Г, d необходимы для того, чтобы замаскировать матрицу А.

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

Криптосистема Нидеррайтера

Криптосистема строится на основе обобщенного кода Рида-Соломона. Сообщением в данном случае являются все векторы с координатами из поля GF(q) и весом, не превосходящим r/2. Сообщения не являются кодовыми словами выбранного кода Рида-Соломона, а представляют собой всевозможные ошибки, которые этот код в состоянии исправлять.

Закрытый ключ состоит из:

Открытым ключом является матрица

Шифртекст, соответствующий открытому тексту m, вычисляется по правилу:

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

Вариация на основе кодов Гоппы

Выбирается (n, k)-линейный код Гоппы Г, исправляющий не более t ошибок и обладающий эффективным алгоритмом декодирования.

Закрытый ключ состоит из:

Открытым ключом является матрица

При шифровании сообщение m кодируется в двоичную строку размером n и весом не более t, после чего вычисляется шифртекст

При расшифровании законный получатель умножает слева шифртекст на после чего применяет алгоритм декодирования для Г, чтобы восстановить Наконец, m вычисляется через

Эквивалентность систем МакЭлиса и Нидеррайтера была отмечена в различных работах. Одинаковая стойкость к атакам у обеих систем объясняется тем, что криптографическая атака на одну из систем может быть легко трансформирована в атаку на другую.

Пусть А ― открытый ключ системы МакЭлиса и В ― открытый ключ системы Нидеррайтера, связанные соотношением то есть из одной матрицы можно получить другую не более чем за операций.

При известном синдроме нетрудно вычислить вектор такой, что Для этого надо найти какое-либо решение уравнения

Пусть b ― шифртекст в системе МакЭлиса. Пусть для криптосистемы найдена криптографическая атака со сложностью Q. То есть известен алгоритм вычисления вектора α, являющегося конфиденциальной информацией в системе МакЭлиса. Тогда вектор e, являющийся конфиденциальной информацией в системе Нидеррайтера может быть представлен в виде то есть сложность его определения совпадает со сложностью определения вектора α.

Пусть найдена криптографическая атака на систему Нидеррайтера со сложностью Q. Пусть в качестве шифртекста используется вектор где b ― шифртекст системы МакЭлиса. Таким образом можно вычислить вектор ошибок e, после чего вычислить α, являющийся единственным решением линейного уравнения

Рассматриваемые системы различаются скоростью передачи. Если ― малое число, то есть код характеризуется низкой скоростью, то скорость передачи в системе Нидеррайтера выше по сравнению с системой МакЭлиса.

Шифрование сообщения е в системе Нидеррайтера состоит в вычислении его синдрома, шифрование можно произвести за операций. Сложность расшифрования равна сложности восстановления вектора е и определяется трудоемкостью декодирования (n, d)-кода и не превосходит операций.

Система Нидеррайтера полностью определяется как проверочной матрицей B, так и ортогональной к ней порождающей матрицей A. Следовательно, открытым ключом принято считать матрицу, содержащую меньшее число строк, хотя шифртекст на практике строится с помощью проверочной матрицы.

Переход от системы МакЭлиса к системе Нидеррайтера повышает скорость шифрования и позволяет с помощью различных модификаций повысить стойкость системы к различным криптографическим атакам.

Задачи ИБ, решаемые технологией помехоустойчивого кодирования

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

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

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

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

Протокол электронной подписи, основанный на криптосистеме МакЭлиса

При использовании криптосистемы МакЭлиса для ЭП абонент А может послать абоненту В сообщение М с подписью для этого абоненты должны выполнить следующие шаги:

Таким образом, без передачи секретного ключа между абонентами в сети, А послал В секретное сообщение со своей подписью, а В открыл данное сообщение. Причем В может рассчитать ЭП абонента А: . Таким образом, абонент В тоже может послать абоненту А секретное сообщение М со своей подписью.

Преимущества и недостатки криптосистем на помехоустойчивых кодах

Ниже приведено сравнение криптосистемы МакЭлиса и криптосистемы, построенной на базе алгоритма RSA.

Алгоритм построения пары ключей для криптосистемы RSA:

Множеством D всех возможных сообщений для этой криптосистемы является Открытому ключу Р соответствует преобразование секретному ключу S соответствует преобразование

Эти преобразования можно использовать и для шифрования, и для ЭП.

В таблице 1 отражены характеристики криптосистем, при заданных параметрах n = 1024, k = 524, t =101, где n ― длина векторов в коде Гоппы, k ― размерность кода Гоппы, t ― минимальное кодовое расстояние.

Таблица 1 — Характеристики криптосистем при заданных параметрах

Стоит заметить, что криптосистема Нидеррайтера представляет собой модификацию системы МакЭлиса, предложенную в 1986 году Нидеррайтером. Отсюда можно сделать вывод, что их основные преимущества и недостатки относительно других криптосистем будут совпадать. Хотя при сравнении МакЭлиса и Нидеррайтера между собой, их характеристики будут отличаться.

К основным недостаткам криптосистем МакЭлиса и Нидеррайтера можно отнести большой размер ключей. Как видно из вышеприведенной таблицы размер открытого ключа этих криптосистем во много раз превышает длину открытого ключа RSA при одинаковых заданных параметрах. Это создает сложность для хранения данного ключа, особенно на устройствах с не очень высокой производительностью.

В качестве недостатка можно рассмотреть и относительно низкую скорость передачи в криптосистемах МакЭлиса и Нидеррайтера (в том числе по сравнению с RSA). Однако данный недостаток вполне может стать несущественным, в связи с быстрым развитием вычислительной техники и с увеличением производительности вычислительных систем.

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

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

Что касается преимуществ, системы Нидеррайтера и МакЭлиса гораздо проще для восприятия и реализации. К тому же, исходя из результатов таблицы, можно сделать вывод, что они имеют гораздо более высокую скорость работы, чем система RSA: при расшифровании превосходство по скорости более чем в 100 раз.

При сравнении систем МакЭлиса и Нидеррайтера между собой можно сделать вывод, что при зашифровании система Нидеррайтера работает быстрее МакЭлиса (однако обе превосходят RSA в 50 и 5 раз соответственно), но при расшифровании преимущество остается за оригинальной системой МакЭлиса.

Преимуществом является и то, что с ростом длины ключа степень защиты криптосистемы МакЭлиса растет гораздо быстрее.

Еще одно преимущество МакЭлиса/Нидеррайтера в том, что в каждом зашифровании присутствует случайный элемент (случайный образом выбранный вектор/невырожденная матрица) при вычислении шифртекста. RSA и другие современные криптосистемы не содержат подобного элемента случайности в алгоритме зашифрования.

Данный элемент случайности придает криптосистемам МакЭлиса и Нидеррайтера неплохой статус защищенности в постквантовой криптографии. RSA, схема Эль-Гамаля и другие методы зашифрования взламываются при помощи квантового компьютера.

Актуальные направления исследований

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

Также существуют различные направления развития криптосистем, основанных на помехоустойчивых кодах. Во-первых, исследование возможности использования других кодов. Например, интересным представляется построение криптосистемы МакЭлиса на кодах, отличных от кодов Гоппы и БЧХ-кодов. Во-вторых, исследование других схем с целью их реализации. В перспективе использование таких схем, например, FHE-схемы, для которой на данный момент существует всего одна реализация, увеличит криптостойкость и производительность. В-третьих, исследование возможности повышения скорости работы криптографических схем, основанных на помехоустойчивом кодировании. Перспектива появления квантовых компьютеров дает предпосылки к исследованию возможностей ускорения алгоритмов с целью противостояния более эффективным атакам.

Глоссарий

Библиографический указатель

Перейти к списку литературы раздела «Применение помехоустойчивых кодов в криптографии».

Источник