Связанные понятия
Обнаруже́ние оши́бок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.
Ту́рбокод — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбокода является известный в теории кодирования термин — каскадный код (англ. concatenated code) (предложен Д. Форни в 1966 году).
В области математики и теории информации линейный код — это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации.
Подробнее: Линейный код
Код Хэ́мминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную.
Хеширование (англ. hashing – «превращать в фарш», «мешанина») — преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины, выполняемое определённым алгоритмом. Функция, воплощающая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.
Алгоритм Берлекэмпа — Мэсси — алгоритм поиска кратчайшего регистра сдвига с линейной обратной связью для поданной на вход бинарной последовательности. Также алгоритм позволяет найти минимальный многочлен поданной на вход линейной рекуррентной последовательности над произвольным полем.
Пото́чный или Пото́ковый шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к симметричному шифрованию, нежели блочные шифры.
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.
ГОСТ Р 34.11-94 — устаревший российский криптографический стандарт вычисления хеш-функции.
Криптографические хеш-функции — это выделенный класс хеш-функций, который имеет определенные свойства, делающие его пригодным для использования в криптографии.
Подробнее: Криптографическая хеш-функция
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Шифрование, сохраняющее формат (англ. format-preserving encryption, FPE) означает шифрование, в котором выходные данные (шифротекст) находятся в таком же формате, что и входные данные (открытый текст). Значение слова «формат» варьируется. Обычно подразумеваются только конечные множества, например...
Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.
Бло́чный шифр — разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками, характерный размер которых меняется в пределах 64‒256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Фактически, блочный шифр представляет собой подстановку на алфавите блоков, которая, как следствие, может быть моно- или полиалфавитной. Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты...
Криптосистема Накаша — Штерна (англ. Naccache — Stern cryptosystem)— криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. В отличии от RSA, гомоморфен по сложению и вычитанию, а не по умножению...
Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.
Симметри́чные криптосисте́мы (также симметричное шифрование, симметричные шифры) (англ. symmetric-key algorithm) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в тайне обеими сторонами, осуществляться меры по защите доступа к каналу, на всем пути следования криптограммы, или сторонами...
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX (англ. Ring Learning with Errors Key Exchange) является одним из алгоритмов с открытым ключом, который предназначен для защиты от противника, обладающего квантовым компьютером. Это важно, потому что криптографические системы с открытым ключом, широко используемые сегодня, легко...
Нейрокриптография — раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа.
Криптосистема Гольдвассер — Микали (GM) — криптографическая система с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое...
Экспоненциальный код Голомба порядка k — это универсальный код, параметризованный целым числом k. Разработан Соломоном Голомбом. Для кодирования неотрицательного числа в экспоненциальный код Голомба порядка k можно использовать следующий метод...
В теории информации
теорема Шеннона об источнике шифрования (или теорема бесшумного шифрования) устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Код — взаимно однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации.
Код Гре́я — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.
Псевдослучайный алгоритм шифрования — такой алгоритм шифрования, что каждый блок (символ) исходного текста шифруется своим собственным ключом, причём каждый следующий ключ является следующим членом псевдослучайной последовательности, а основной (базовый) ключ — первым элементом этой последовательности.
Би́товое поле (англ. bit field) в программировании — некоторое количество бит, расположенных последовательно в памяти, значение которых процессор не способен прочитать из-за особенностей аппаратной реализации.
Блочный код — в информатике тип канального кодирования. Он увеличивает избыточность сообщения так, чтобы в приёмнике можно было расшифровать его с минимальной (теоретически нулевой) погрешностью, при условии, что скорость передачи информации (количество передаваемой информации в битах в секунду) не превысила бы канальную производительность.
Линейный криптоанализ был изобретён японским криптологом Мицуру Мацуи (яп. 松井 充 Мацуи Мицуру). Предложенный им в 1993 году (на конференции Eurocrypt '93) алгоритм был изначально направлен на вскрытие DES и FEAL. Впоследствии линейный криптоанализ был распространён и на другие алгоритмы. На сегодняшний день наряду с дифференциальным криптоанализом является одним из наиболее распространённых методов вскрытия блочных шифров. Разработаны атаки на блочные и потоковые шифры.
Сеть Фе́йстеля , или конструкция Фейстеля (англ. Feistel network, Feistel cipher), — один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется...
Поиск подстроки в строке — одна из простейших задач поиска информации. Применяется в виде встроенной функции в текстовых редакторах, СУБД, поисковых машинах, языках программирования и т. п.
Атака на основе открытых текстов (англ. Known-plaintext attack) — вид криптоанализа, при котором в шифротексте присутствуют стандартные отрывки, смысл которых заранее известен аналитику. Во время Второй мировой войны английские криптоаналитики называли такие отрывки «подсказками» (англ. crib — подсказка, шпаргалка).
Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами.
В криптоанализе методом
встречи посередине или атакой "встречи посередине" (англ. meet-in-the-middle attack) называется класс атак на криптографические алгоритмы, асимптотически уменьшающих время полного перебора за счет принципа "разделяй и властвуй", а также увеличения объема требуемой памяти. Впервые данный метод был предложен Уитфилдом Диффи и Мартином Хеллманом в 1977 году.
Атака на основе адаптивно подобранного открытого текста — вид атаки в криптоанализе, предполагающий, что криптоаналитик может несколько раз выбирать открытый текст и получать соответствующий ему шифртекст прямо во время атаки. Цель криптоаналитика — получить возможность извлекать информацию из перехваченных шифртекстов этой системы, а в идеале подобрать ключ, сопоставляя открытый текст и полученный шифртекст.
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.
Блочный шифр «
Кузнечик » (входит в стандарт ГОСТ Р 34.12-2015) — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа 256 бит и использующий для генерации раундовых ключей сеть Фейстеля.
Шифротекст , шифртекст — результат операции шифрования. Часто также используется вместо термина «криптограмма», хотя последний подчёркивает сам факт передачи сообщения, а не шифрования.
ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования» — действующий российский криптографический стандарт, определяющий алгоритм и процедуру вычисления хеш-функции. Разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «ИнфоТеКС» и введен в действие 1 января 2013 года.
Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) — это криптографически стойкий алогоритм генерации псевдослучайных последовательностей, с использованием зерна (Random seed). Идеи алгоритма были изложены Блюмом и Микали в 1984 году. Алгоритм был разработан на основе алгоритма генератора Шамира, предложенного Ади Шамиром годом ранее. Алгоритм отличается от предшественника более сильными требованиями к сложности вычисления выходной последовательности. В отличие от генератора Шамира выходом данного...
Гомоморфное шифрование — форма шифрования, позволяющая производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом. Например, один человек мог бы сложить два зашифрованных числа, не зная расшифрованных чисел, а затем другой человек мог бы расшифровать зашифрованную сумму — получить расшифрованную сумму, не имея расшифрованных чисел. Гомоморфное шифрование позволило бы предоставлять...
Сжатие звука без потерь — совокупность преобразований, позволяющая эффективно сжимать звуковые данные с возможностью их полного восстановления. Как и любое сжатие без потерь, сжатие звуковых данных эксплуатирует какую-либо особенность данных. В данном случае это...
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.
Протокол Ди́ффи — Хе́ллмана (англ. Diffie–Hellman, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
Алгоритм Верхуффа (англ. Verhoeff algorithm) — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 году нидерландским математиком Якобом Верхуффом. Алгоритм позволяет выявить такое же число ошибок, как аналогичный алгоритм Луна, но ошибки, выявляемые только первым, совершаются людьми обычно чаще, чем ошибки, выявляемые только вторым.