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

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

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

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

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

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

Просто? Ага.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я думаю , что важно в криптографии не воспламеняет себя, но это трудность в прайм задачи факторизации

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

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

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

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