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

191

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

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

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

Майкл Стум
источник
Пара замечаний: 1. Люди ниже отмечают, что «первичная факторизация больших чисел занимает много времени». На самом деле, то же самое верно для любой факторизации. Важно то, что любое целое число! = 0 имеет уникальную факторизацию как произведение простых чисел (включая 1, у которого есть разложение длины 0).
TT_
1
2. Пожалуйста, проверьте мое объяснение, почему простые числа важны для хеш-функций: stackoverflow.com/questions/1145217/… Это связано со свойством многочленов с коэффициентами, принадлежащими полю (что, вероятно, не является кратким объяснением).
TT_
2
Чрезмерно простое краткое объяснение → Решите: a * b = 91. Теперь решить: 13 * 7 = x. Второе уравнение гораздо быстрее решить (для человека или компьютера).
Дем

Ответы:

204

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

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

Майкл Боргвардт
источник
7
Поскольку мы входим в эру квантовых вычислений представляется целесообразным отметить , что разложение простых чисел с помощью квантового компьютера может быть достигнуто за полиномиальное время usiong алгоритма Шора en.wikipedia.org/wiki/Shor%27s_algorithm Вполне вероятно , что компьютеры уже существуют , которые могут расшифровать шифрование с открытым ключом, как RSA
stujo
16
@stujo: вы сильно переоцениваете состояние квантовых вычислений. На самом деле точно, что такого компьютера не существует. Наибольшее число, которое было вычислено с использованием алгоритма Шора и новейших исследований в области квантового оборудования, составляет 21. Это не 21 бит, а число 21, простые факторы 3 и 7.
Майкл Боргвардт,
1
Я не уверен, какие данные являются текущими, сложно получить информацию о последней работе, я полагаю, что это было в 2012 году, эта статья написана в 2014 году ( m.phys.org/news/2014-11-largest-factored- квант-устройство.html ) Видели ли мы какие-либо публичные данные за 2016 год? Не исключаю, что может быть классифицировано. Хотя он не может запустить алгоритм Шорса, D-Wave теперь больше 1000 кубитов
stujo
1
@stujo: одни и те же принципы будут действовать, когда все мы будем использовать квантовые процессоры, поскольку простые числа могут продолжать расти, все дело в поиске больших, непрактичных для квантовых процессоров, проблема существует, если некоторые используют обычный CPUS для создания ключей, а некоторые используют квантовые процессоры для сломать тех. Как я понимаю, мощь квантовых процессоров заключается в том, что они используют кубиты, каждый кубит может иметь 3 значения, поэтому новая технология - это база 3, а не база 2. ЦП 64 битов будет иметь 3 ^ 64 комбинации в слове. Не знаю, как это влияет на производительность.
17
5
@juanmf: ваше понимание квантовых вычислений совершенно неверно. Это не имеет абсолютно никакого отношения к наличию 3 значений, что было бы совершенно неинтересно. Детали очень сложны, но эффект заключается в том, что некоторые квантовые алгоритмы могут решать задачи с меньшей сложностью Big-O, чем «нормальные» алгоритмы на неквантовом оборудовании.
Майкл Боргвардт
137

Просто? Ага.

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

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

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

user54650
источник
2
Также стоит отметить, что, помимо проблемы факторизации, многие современные криптографы также (или вместо этого) полагаются на проблему дискретного логарифма. Обе функции являются «односторонними»: легко взять известные входные данные и вычислить ответ, но трудно получить ответ и вычислить эти входные данные.
Незрой
4
Было бы полезно связать это объяснение с термином «односторонняя функция»: en.wikipedia.org/wiki/One-way_function
Крис Конвей,
Но если открытый ключ можно использовать для шифрования, почему его нельзя использовать для обратного?
Джаярджо
45

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

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

Ювал Адам
источник
30
Просто К вашему сведению, число, которое вы получите при умножении двух простых чисел, называется полу-простым.
Мэтью Брубейкер
15

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

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

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

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

Барри Браун
источник
10
На самом деле вам нужно только проверить простые числа до квадратного корня из числа, которое вы пытаетесь вычислить.
Мэтью Брубейкер
3
Я знаю. Это была деталь, которую я "упустил из виду" во имя простоты.
Барри Браун
@ MatthewBrubaker Не могли бы вы объяснить, почему это так? Я не очень понимаю.
Картик Чаг
4
@KartikChugh ヅ скажем n, не простое & n = a * b. Если a > sqrt(n), bдолжно быть меньше, и наоборот, иначе это a * b > nсамо по себе отрицает наше первоначальное требование. Таким образом, чтобы проверить на простое, мы проверяем только до sqrt.
Абхинав Гауниял
13

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

nes1983
источник
1
Интересно, что в скором времени уже можно узнать, если число простое.
nes1983
Здесь отсутствует "если главные факторы велики" здесь.
Бен Фойгт
@ Бен: это не пропало. В общем, проблема сложная. Обратите внимание, что проблемы, которые сложны в общем, могут иметь простые случаи. В этом случае небольшие простые числа - далеко не единственные простые случаи.
nes1983
2
Никто не знает "на публике". Вполне возможно, что у спецслужб различных правительств мира есть методы, которыми они не делятся. Они нанимают огромное количество выпускников по математике. Например, АНБ тайно продвигало генерацию случайных простых чисел с помощью «Dual EC_DRBG», которая, как они знали, была слабой, как часть стандартной криптографической схемы для публичного использования. bits.blogs.nytimes.com/2013/09/10/…
Дон
Дон: заснеженные документы, кажется, показывают, что это не так. они рисуют довольно убедительную картину того, что (по большому счету могут быть углы), АНБ не может расшифровать зашифрованные данные с помощью специальной математической магии, только они знают. Шнайер широко обсуждал этот вопрос.
nes1983
12

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

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

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

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

Брайан Клаппер
источник
9

Чтобы быть немного более конкретным о том, как 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 очень сложно.

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

Сэм Хаслер
источник
7

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

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

Джейсон Роу
источник
6

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

Билл Ящерица
источник
6

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

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

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

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

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

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

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

Calmo
источник
3
Только ваш последний абзац действительно действителен. Аргумент сумм можно сказать и для любого составного числа (существует большой диапазон [технически бесконечно большой], хранение всех сумм невозможно / глупо). Кроме того, суммы простых чисел не имеют большого значения в криптографии, более важным (как правило, как в случае RSA) является их продукт. Кроме того, под обратным расчетом вы, вероятно, подразумеваете факторинг . Это, вероятно, поможет с тем, что вы имеете в виду.
initramfs
4

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

gkrogers
источник
4

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

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

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

Gant
источник
3

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

Майкл
источник
Это выглядит немного излишним для меня. Часть из более слабой ключевой части, которую можно прокомментировать в верхнем ответе :)
Ulysse BN
-1

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

Ченгаппа Б.С.
источник
7
Выяснить, является ли число простым числом, дешево, и нам нужно, чтобы оно было дешевым. Как еще мы могли бы знать, что мы выбрали простые числа в качестве наших главных факторов в RSA или простое число в качестве модуля в криптографии с конечным полем? То, что дорого, так это деление большого составного числа на его основные факторы.
CodesInChaos