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

Question

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

Например, я читал на некоторых форумах по математическому программированию, что, используя Quadratic Sieve или General Number Field Sieve, можно относительно легко разложить 256-битное число на коммерчески доступное оборудование.

Как это может привести к нарушению безопасности таких алгоритмов, как RSA, AES и т. Д.? Достаточно ли умножить на число длину ключа?

Есть ли кто-нибудь, кто разбирается в криптографии и алгоритмах шифрования, кто мог бы пролить немного света на это?

Answer 1

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

Вот вопрос об ответах Yahoo, где кто-то дал некоторые детали: http://answers.yahoo.com/question/index?qid=20070125183948AALJ40l

Он опирается на несколько фактов:

• n=p.q легко вычислить, но трудно перевернуть
• Маленькая теорема Ферма: http://en.wikipedia.org/wiki/Fermat%27s_little_theorem
• Различные результаты теории чисел.

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

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

• n = p * q дает большое число, заданное p, q простое число.
• phi (n) = (p-1) (q-1). Это продолжение маленькой теоремы Ферма. Подробнее о том, зачем нам это нужно и почему она работает, можно найти в моем блоге здесь: http://vennard.org.uk/weblog/2010/02/a-full-explanation-of-the-rsa-algorithm/
• Это означает, что если мы выберем число E взаимно простое (без общих простых множителей) для (p-1) (q-1), мы можем найти Es обратный мод phi (n).

• Что мы делаем, мы находим DE = 1 (p-1) (q-1) или, вернее, мы решаем, используя алгоритм наибольшего общего делителя Евклида, расширенную версию.

• Теперь, учитывая все вышесказанное, если мы возьмем T ^ E (pq), мы получим C. Однако, если мы возьмем (T ^ E) ^ D (pq), мы вернем T снова.

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

В Википедии есть хорошая статья об AES для высокого уровня с хорошей ссылкой, которая показывает вам, как она работает - см. здесь и здесь . Особенно мне нравится последняя ссылка.

Answer 2

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

Пропущенная фраза - «открытый ключ», например, «Какова безопасность алгоритма шифрования с открытым ключом ...»

В современной криптографии существуют две основные категории шифров: симметричный (секретный ключ) и открытый ключ (который использует пару открытый / закрытый ключ).

В каждой категории вы найдете ключевые размеры относительно близкими. Для систем с открытым ключом, таких как RSA и DH / DSA, которые используются в шифровании электронной почты OpenPGP, размеры общих ключей в наши дни составляют 1024-битные и более (начало 2010 года). Это связано с математическими требованиями подходящих ключей, используемых для шифрования и дешифрования сообщений. Короче говоря, для RSA намного проще сгенерировать множитель двух случайных больших простых чисел и выполнить с ними умножение, по сравнению с факторингом очень большого числа, в котором нет мелких факторов. Как вы обнаружили, факторинг очень больших чисел является «проблемой» или подходом, необходимым для разрыва RSA с помощью грубой силы.

Алгоритм Диффи-Хеллмана / цифровой подписи (DH / DSA) основан на другой математической задаче, вычисляющей дискретные логарифмы.

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

В то время как с симметричными шифрами, такими как AES, RC6, RC4, Twofish, DES и Triple-DES, эти алгоритмы используют случайный ключ заданной длины в битах. Подходит любой нетривиальный (т. Е. 0x000 ... 000 может быть плохой выбор ключа) случайный ключ. Таким образом, если в этих системах нет атаки на сам алгоритм, вы можете просто выполнить поиск грубой силы в пространстве ключей (то есть попробовать все 2 ^ 256 возможных ключей), чтобы расшифровать сообщение без секретного ключа. Поскольку любой ключ подходит, плотность ключей составляет 2 ^ 256.

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

Я надеюсь, что это объясняет общую разницу между двумя типами криптосистем, такими как RSA и AES.

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

Answer 3

AES сильно отличается, AES создает SPN, сеть перестановочных замен. Он генерирует s-блоки (блоки замещения) на основе полиномиальных функций, сгенерированных во время шифрования. Он проходит через 10-14 раундов подстановки на уровне байтов и перестановки на уровне битов, длина ключа, определяющая количество раундов и ключи раундов, в битах.

RSA основан на факторах больших простых чисел, которые чрезвычайно трудно сделать вычислительно, но довольно легко изначально зашифровать.

Answer 4

RSA нарушается факторингом. На самом деле RSA - это два алгоритма, один для (асимметричного) шифрования и один для цифровых подписей; оба используют один и тот же примитив. В RSA существует публичная ценность (модуль , часто отмечаемый n ), который является продуктом двух (или более) различных основных факторов. Факторинг n раскрывает закрытый ключ. Факторинг становится сложнее, когда размер n увеличивается. Текущая запись (опубликованная ранее в этом году) для 768-битного целого числа; это заняло четыре года больших вычислений и тяжелой работы очень умных людей. Те же самые люди открыто признают, что они мало что знают о том, как они могли бы попробовать один и тот же трюк с 1024-битным целым числом (есть часть самого известного алгоритма факторизации, который требует очень много быстрой оперативной памяти и для 1024-битного целое число, которое потребовало бы смехотворно огромной машины). Текущие рекомендации длины ключа для RSA: 1024 бита для краткосрочной, 2048 бит для долгосрочной безопасности. Обратите внимание, что вычислительная стоимость RSA также увеличивается с размером ключа, поэтому мы не хотим использовать действительно большие ключи без веской причины. Базовый ПК будет производить около 1000 сигнатур RSA в секунду (и на ядро) с 1024-битным ключом и в восемь раз меньше с 2048-битным ключом. Это все еще довольно хорошо.

Существуют другие алгоритмы асимметричного шифрования и алгоритмы цифровой подписи. С RSA несколько связан алгоритм шифрования Рабина-Уильямса; факторинг также ломает это. Затем существуют алгоритмы, основанные на дискретном логарифме (в мультипликативной группе чисел по модулю большого простого числа): Диффи-Хеллман (обмен ключами), DSA (подпись), Эль-Гамаль (шифрование) ... для этих алгоритмов факторизация не является прямой угроза; но они опираются на те же самые части теории чисел, и самый известный алгоритм для дискретного логарифма очень похож на самый известный алгоритм для факторизации (и имеет то же имя: GNFS - как Общее число полей сита ). Таким образом, предполагается, что прогресс в факторизации будет результатом прогресса в теории чисел, который также может пролить свет на дискретный логарифм.

Алгоритмы дискретного логарифма могут применяться к другим группам, наиболее популярными из которых являются эллиптические кривые. Эллиптические кривые не подвержены факторизации. Если бы факторизация стала легкой, таким образом, отказавшись от RSA и косвенно поставив под угрозу DSA и Diffie-Hellman, мы бы переключились на ECDH и ECDSA; стандарты и реализации существуют и развернуты.

«Симметричная криптография», то есть хеш-функции (MD5, SHA-256 ...), код аутентификации (HMAC, CBC-MAC ...), симметричное шифрование (AES, 3DES ...), генерация случайных чисел ( RC4 ...) и связанные с ними виды деятельности не подвержены факторизации. Для этих алгоритмов ключи представляют собой просто наборы битов без какой-либо специальной структуры; нечего учитывать.