Как ключи используются в алгоритмах шифрования?

Question

Я просматривал и нашел хорошие статьи о шифровании. Однако ни один из них не объяснил, почему важна длина ключа и для чего именно используется ключ. Я предполагаю, что это могло бы работать так:

Plaintext: 0101001101010101010 
Key:   01010010101010010101 //the longer the key, the longer unique sequence 
XOR or smth: //result 

Это хотя бы немного, как это работает, или я чего-то не хватает?

Answer 1

Системы шифрования, как правило, намного сложнее, чем описанная вами система XOR. Фактически, XORing действительно работает, только если у вас есть ключ, у которого есть как минимум столько же бит, сколько текстовое сообщение, и вы только когда-либо используете ключ для шифрования одного сообщения. Это называется «одноразовой клавиатурой».

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

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

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

Answer 2

Прошло много времени (более 25 лет) с моего курса по криптографии, но я постараюсь помочь.

Хотя это не идеальный пример для вещей в современной криптографии, возможно, более легкое понимание придет путем рассмотрения Vigenere cipher, используя строго алфавитный простой текст и ключ. В таком шифре ваш ключ будет представлять собой последовательность букв - часто слово или фразу - и используется для поворота в серии Caesar ciphers для шифрования обычного текста. Например, простой текст «dog» с ключом «cat» приведет к зашифрованному тексту «foz» (если я сделал это правильно).

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

Answer 3

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

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

В порядке, ключ концентраты секрет. Все, что является секретным в шифровании, лежит в этом ключе.

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

Сколько стоит ключ? Ну, так как ключ является единственной частью всего, что является секретным, все, что должен сделать атакующий, - угадать ключ. Самая основная форма угадывания - исчерпывающий поиск: злоумышленник просто пытается использовать все возможные ключи. Количество возможных ключей растет довольно быстро с длиной ключа. Например, 10-битный ключ имеет 1024 возможных ключа. С 20-битным ключом имеется 1048576 возможных ключей. Каждый дополнительный бит удваивает количество возможных ключей.

Алгоритм считается «надежным», если Известная атака является исчерпывающим поиском. В этом смысле надежный алгоритм - это алгоритм, который не предлагает лучшего пути атаки, чем жестокий исчерпывающий поиск, который всегда «выполним», но может быть непомерно дорогостоящим. Если алгоритм является надежным и, используемый ключ является достаточно большим, чтобы прервать исчерпывающий поиск, тогда шифрование защищено. «Достаточно большой», с практической точки зрения, означает «сто бит или больше». Самый большой ключ, который был атакован исчерпывающим поиском, - это 64-битный ключ. Количество комбинаций было огромным (18446744073709551616), что могло быть достигнуто с помощью существующих технологий (потребовалось несколько лет и тысячи компьютеров). Постоянный прогресс в скорости компьютера делает исчерпывающий поиск лучше и лучше, но не так быстро, как можно было себе представить. В основном, исчерпывающий поиск увеличивается на 1 бит каждые 12-18 месяцев (это известно как «закон Мура»). Существует много веских причин, по которым закон Мура не может быть соблюден до 2020 года (именно это и предсказывал сам Гордон Мур), и в этот момент вычислительная мощность по данной цене каким-то образом застопорится. 100-битный ключ должен оставаться в безопасности (это слишком много комбинаций для того, что компьютер сможет сделать через 10 лет). Обычные алгоритмы шифрования используют 128-битный ключ, потому что «128» выглядит хорошо, когда записывается в двоичном формате.

Есть также асимметричный шифрование и цифровые подписи. Основной принцип остается тем же: ключ - это часть, которая является секретной, в отличие от метода (программы), который известен всем. Асимметричное шифрование и цифровые подписи пытаются выполнять сложные вещи, в которых, например, у кого-то, кто знает, как шифровать , нет, достаточно информации, чтобы знать, как расшифровать. Для этого требуются некоторые сложные математические структуры. Ключами являются тогда математические объекты, которым требуется больше бит, когда они закодированы.Опять же, количество возможных ключей растет с размером ключа, но не так быстро, потому что очень немногая последовательность бит будет иметь требуемую математическую структуру. Кроме того, эта же структура позволяет использовать более быстрые пути атаки, подразумевая при этом более крупные ключи для обеспечения безопасности. Вот почему мы слышим о таких вещах, как «1024-битный ключ RSA». Ключ RSA состоит из нескольких целых чисел, наиболее важным из которых является то, что нецелесообразно превращать его в произведение простого целого числа. 1024-битное целое число (целое число, которое, будучи записано в двоичном выражении, состоит из 1024 нулей и единиц), которое должно быть чуть более 300 цифр в десятичной форме) кажется достаточно большим, чтобы помешать факторизации (текущая запись для 768-битного целое число).