Почему простые числа важны в криптографии?

Question

Одна вещь, которая всегда поражает меня как некриптографа: почему так важно использовать простые числа? Что делает их такими особенными в криптографии?

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

Спасибо за все ответы. Я принял тот, который сделал концепцию самой ясной для меня.

Answer 1

Самое основное и общее объяснение: криптография - это все о теории чисел , а все целые числа (кроме 0 и 1) состоят из простых чисел, поэтому вы много работаете с простыми числами в теории чисел.

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

Answer 2

Simple? Да.

Если вы умножите два больших простых числа, вы получите огромное не простое число только с двумя (большими) простыми множителями.

Факторинг этого числа является нетривиальной операцией, и этот факт является источником множества криптографических алгоритмов. См. односторонние функции для получения дополнительной информации.

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

Answer 3

Вот очень простой и распространенный пример.

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

Answer 4

Потому что никто не знает быстрого алгоритма для деления целого числа на его основные множители. Тем не менее, очень легко проверить, умножается ли набор простых факторов на определенное целое число.

Answer 5

Важны не столько простые числа, сколько алгоритмы, которые работают с простыми числами. В частности, нахождение множителей числа (любого числа).

Как известно, любое число имеет как минимум два фактора. Простые числа обладают уникальным свойством: они имеют ровно два фактора: 1 и самих себя.

Причина, по которой факторинг так важен, состоит в том, что математики и ученые-компьютерщики не знают, как вычислить число без простой попытки каждой возможной комбинации. То есть сначала попробуйте разделить на 2, затем на 3, затем на 4 и так далее. Если вы попытаетесь разложить простое число, особенно очень большое, вам придется (по существу) попробовать каждое возможное число от 2 до этого большого простого числа. Даже на самых быстрых компьютерах потребуются годы (даже столетия), чтобы определить виды простых чисел, используемых в криптографии.

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

Answer 6

Есть несколько хороших ресурсов для наращивания крипто. Вот один из них:

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

С этой страницы:

В наиболее часто используемых открытых ключах криптографическая система, изобретенная Роном Ривест, Ади Шамир и Лен Адлеман в 1977, как общественные, так и частные ключи получены из пары больших простые числа в соответствии с относительно простая математика формула. В теории это может быть можно получить закрытый ключ из открытого ключа, работая формула в обратном направлении. Но только произведение больших простых чисел общественности, и факторинг номера этого размер в простые так сложно, что даже самые мощные суперкомпьютеры в мир не может сломать обычный открытый ключ.

Книга Брюса Шнайера Прикладная криптография - это другое. Я очень рекомендую эту книгу; это весело читать.

Answer 7

Чтобы быть немного более конкретным о том, как RSA использует свойства простых чисел, алгоритм RSA критически зависит от теоремы Эйлера , в которой говорится, что для относительно простых чисел "a" и "N" e конгруэнтно 1 по модулю N, где e - общая функция Эйлера из N.

Где простые числа входят в это? Для эффективного вычисления функции Эйлера в N требуется эффективное знание факторизации N. В случае алгоритма RSA, где N = pq для некоторых простых чисел "p" и "q", то e = (p - 1) (q - 1) = N - p - q + 1. Но, не зная p и q, вычислить e очень сложно.

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

Answer 8

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

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

Answer 9

Еще один ресурс для вас. Безопасность сейчас! эпизод 30 (~ 30-минутный подкаст, ссылка на стенограмму) рассказывает о проблемах криптографии и объясняет, почему простые числа важны.

Answer 10

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

Вся эта цепочка заполнена пояснениями о КАК простых числах используются в криптографии, трудно найти кого-либо в этой теме, объясняющих простой способ ПОЧЕМУ простые числа используются ... скорее всего, потому что каждый принимает эти знания как должное.

Только смотреть на проблему со стороны может вызвать такую ​​реакцию; но если они используют суммы двух простых чисел, почему бы не создать список всех возможных сумм, которые могут сгенерировать любые два простых числа?

На этом сайте есть список 455,042,511 простых чисел, где самые высокие простые числа составляют 9,987,500,000 ( 10 цифр).

Наибольшее известное простое число (по состоянию на февраль 2015 года) составляет 2 для степени 257,885,161 - 1 , что составляет 17,425,170 цифр.

Это означает, что нет смысла сохранять список всех известных простых чисел и тем более всех их возможных сумм. Проще взять число и проверить, простое ли это число.

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