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

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

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

Он основан на нескольких фактах:

• n = pq легко вычислить, но трудно обратить вспять
• Маленькая теорема Ферма: 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 для высокого уровня с хорошей ссылкой, которая показывает, как это работает - см. здесь и здесь . Мне особенно нравится последняя ссылка.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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