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

Ответ 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 prime.
• 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 обратную mod phi (n).

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

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

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

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

Ответ 2

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

Недопустимая фраза - это "открытый ключ", как в разделе "Как защищает алгоритм шифрования открытого ключа..."

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

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

Diffie-Hellman/Digital Signature Algorithm (DH/DSA) основаны на другой математической задаче, вычисляющей дискретные логарифмы.

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Существуют и другие асимметричные алгоритмы шифрования и алгоритмы цифровой подписи. В некоторой степени это связано с алгоритмом шифрования Рабина-Вильямса; факторинг также нарушает его. Тогда существуют алгоритмы, основанные на дискретном логарифме (в мультипликативной группе чисел по модулю большого простого): Diffie-Hellman (обмен ключами), DSA (подпись), El Gamal (шифрование)... для этих алгоритмов факторизация не является прямой угроза; но они полагаются на одни и те же части теории чисел, а самый известный алгоритм дискретного логарифма очень похож на наиболее известный алгоритм факторизации (и имеет одно и то же имя: GNFS - как общее полевое сечение). Поэтому предполагается, что продвижение в факторизации будет связано с продвижением в теории чисел, которое, вероятно, также прольет некоторый свет на дискретный логарифм.

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

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