PGP построен на RSA. RSA использует математику простых чисел.
факторизация простого числа является математической задачей с полиномиальной сложностью -> вскрыть за приемлемое время невозможно. учим матчасть.
гыгы .... чо, правда? ссылку на акт в студию!
PGP построен на RSA. RSA использует математику простых чисел.
факторизация простого числа является математической задачей с полиномиальной сложностью -> вскрыть за приемлемое время невозможно. учим матчасть.
имхо единственный способ - квантовые вычисления, где одновременность подбора обеспечивается суперпозицией, но этим девайсам еще далеко до криптографии.
а он тут не при чем.
головой подумай.
ну, там и ключеги покомпактнее при той же вычислительной стойкости.

тоже к ней присматриваюсь

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

> а он тут не при чем.
опять вы не совсем правы. Есть в PGP возможность использовать DSA - такой алгоритм подписи. Благо ключики для него в принципе совместимы с ключами RSA в смысле что можно использовать один ключ и там и там.
Этот алгоритм в общем за авторством Диффи-Хеллмана и очень похож на алгоритм Эль-Гамаля для подписей -  оба они строятся на задаче дискретного логарифма очень большого числа по модулю очень большого простого числа (конкретно - 160 бит).
в общем задача дискретного логарифма очень похожа на задачу факторизации. посему очень логично предположить что при взломе факторизации (например - появлении гения который обнаружит полиномиальный алгоритм или какой-то суперспособ снижать экспоненциальную сложность в миллиарды миллиардов раз...) - задача дискретного логарифма будет решаться тем же методом не менее эффективно. уж очень похожи эти две задачи =)

take care.

этоттам:
Это ещё бабушка надвое сказала, причём американская.

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

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

>to Гость, 24.10.2006 10:27:22:
>А есть что-нибудь кроме указа? Закон, например.
>Потому как указ - это не закон
Указ, насколько я понимаю, - подзаконный акт, и обязателен для исполнения, если только не противоречит другим актам, имеющим бОльшую силу. Насколько я знаю, таких законов нет.
Но, с тех пор приняты другие подзаконные акты, которые противоречат процитированному указу. Но и "указ" никто не отменял. Поэтому и хотелось услышать мнение других.

все зависит от ключа. ключ в 1024 бита может поломать за теоретически разумное время - где то около года - только гипотетическая машина TWIRL. Ни один традиционный компьютер или кластер или что-то подобное на их основе - даже если бы закон Мура выполнялся в его извращенной форме - про производительность в два раза за год - так вот еще десятки лет традиционным компьютерам не сломать.
идея в общем в том чтобы как можно больше делать за один такт.. такая машина будет стоить около 10 миллионов долларов (оценка Шамира).
что касается американской бабушки - к вашему сведению процесс разработки и исследований RSA как впрочем и AES полностью открыт. Американцы предпочитают не полагаться на security through obscurity.
Исследуйте хоть с утра до вечера...
ключ в 10240 бит и все что выше.. это к квантовым компьютерам которых пока нет и неизвестно когда будут. вы понимаете хоть на сколько порядков увеличивается сложность перебора с каждым десятком бит? это порядки порядков порядков порядков помноженные на порядки.
я думаю ближайшие 10 лет можно полагаться на ключи в 2048 и выше бит без особых проблем.

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

Вообще-то было написано не только про производительность (про которую все мы "думаем", но никто не знает). Кстати, если система за 10M$ может делать что-то реальное, то что сможет система за 100M$? А за 1000М$? Не думаю, что спецслужбам США такие масштабы недоступны.

Хотя реально они скорее всего пользуются этим:

откуда они это возьмут если все остальные не могут. или вы думаете что они сверхлюди какие-то? лучше тех же авторов RSA? возможно - но маловероятно =)
пользуйтесь ключом в 2048 бит и спите спокойно еще минимум 10 лет.
или меняйте его каждый месяц - и спите еще более спокойно...