Теоретически — да.

Здравствуйте, Salih, Вы писали:

Если P!=NP, то нет. Если P=NP, то возможно, но тоже вряд ли.
Если сделают достаточно мощный квантовый компьютер -- то да.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Любой ключ взламывается, вопрос во времени.
Любой пароль взламывается терморектальным криптоанализом.

Здравствуйте, Шахтер, Вы писали:

Ш>Если P!=NP, то нет. Если P=NP, то возможно, но тоже вряд ли.
Ш>Если сделают достаточно мощный квантовый компьютер -- то да.

Или если ключ слабый.

Здравствуйте, Bjorn Skalpe, Вы писали:

BS>Любой ключ взламывается, вопрос во времени.
BS>Любой пароль взламывается терморектальным криптоанализом.

Не любой. Если ты не знаешь собственного пароля, то сколько тебе паяльник в попу не засовывай, сказать тебе будет нечего.

Здравствуйте, Salih, Вы писали:

Ну сам алгоритм, наверное нет, а вот найти слабость в алгоритме генерации ключа — это, я так понял, периодически случается.

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, Salih, Вы писали:

Ш>Если P!=NP, то нет. Если P=NP, то возможно, но тоже вряд ли.
Ш>Если сделают достаточно мощный квантовый компьютер -- то да.


квантовый компьютер это как философский камень — поиски полезны, но цель недостижима.

Здравствуйте, jahr, Вы писали:

J>Теоретически — да.

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

Здравствуйте, Salih, Вы писали:

J>>Теоретически — да.

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

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

А квантовый компьютер это не философский камень, квантовые компьютеры уже много лет строят. IBM в прошлом году компьютер из 17 кубитов сделала, например. Чтобы взламывать 2048 RSA, нужно несколько тысяч кубитов, поэтому пока паниковать рано, но прогресс есть и на то, что лет через 50 такого процессора не будет, я бы деньги не поставил.

Здравствуйте, Salih, Вы писали:

Может. Помнится, звучало предупреждение "черных шляп" в связи с лавинообразно нарастающим интересом к основному разделу математики (в нем криптография "живет"). Это как миллион обезьян, посаженных за печатные машинки: не исключено появление членораздельного текста у одной из них просто в силу случайности. И я слышал от популяризаторов математики, что решение может быть неожиданно простым. Возможно кому-то, именно что не обремененному грузом теории, придет в голову неожиданная идея. Мне однажды пришла такая в голову, и все закончилось весьма скверно. Идея заключалась в использовании частей подлежащего факторизации числа в качестве индексов несложных арифметических прогрессий. Я насчитал их всего три.

В качестве иллюстративного примера:

Что общего у произведений 9 * 9, 17 * 17, ... 257 * 257 и т.д., кроме того, что в каждой паре множители — минимальные нечетные числа в своей разрядности? В двоичной форме произведения имеют вид 1010001, 100100001 и 10000001000000001 соответственно. Весьма похоже, правда? Отбросим крайние единицы, проведем воображаемую границу сразу справа за единицей оставшейся, и, обозначив левую часть как "икс", правую как "игрек", получим унифицированную формулу для множителей в любой разрядности y = x — 1 при условии, что один из множителей остается минимальным в принятой разрядности. Например, для произведения 268 435 457 * 391 892 247 множители находятся мгновенно просто потому, что в результирующем произведении 101110101101111001101000110000111010110111100110100010111 "икс" (61728396) больше "игрека" (61728395) всего на единицу. Для пары множителей, в которой меньший больше минимального на "2" формула будет иметь вид y = 3x — 5, больше на "четверку" y = 5x — 13 и т.д.

Я написал тогда шустрый факторизатор, эксплуатирующий подобные фокусы. Он раскладывал числа в разрядности 2^64 за время до 3-х секунд. Понял ограничения — улучшил алгоритм, сведя к диофантовому уравнению 2-го порядка. Проконсультировался с профессиональными математиками, понял что унифицированного решения не существует, свел проблему к задаче сортировки, и...

Однажды проснулся утром и понял, что на прежнюю работу мне больше ходить не надо.

Здравствуйте, Salih, Вы писали:

Я видел в фильме "Пароль рыба-меч", как задрот взломал Пентагон, но при этом ему отсасывали (вероятно, это является необходимым условием для взлома).

Здравствуйте, AlexRK, Вы писали:

ARK>Я видел в фильме "Пароль рыба-меч", как задрот взломал Пентагон, но при этом ему отсасывали (вероятно, это является необходимым условием для взлома).

пистолет ещё нужен

Теоретически может быть некий задрот, отгадывающий любой ключ с первой попытки.