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

Простой? Да.

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

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

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

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

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

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

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

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

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

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

Существуют некоторые хорошие ресурсы для того, чтобы расти на crypto. Вот тот:

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

От той страницы:

В обычно используемой системе криптографии с открытым ключом, изобретенной Ron Rivest, Adi Shamir и Len Adleman в 1977, и общественность и закрытые ключи получены из пары больших простых чисел согласно относительно простой математической формуле. В теории могло бы быть возможно получить закрытый ключ из открытого ключа путем работы формулы назад. Но только продукт больших простых чисел общедоступен, и числа факторинга того размера в начала так твердо, что даже самые мощные суперкомпьютеры в мировом наклоне повреждают обычный открытый ключ.

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

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

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

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

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

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

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

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

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

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

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