Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Специалисты поясните про криптоанализ RSA 12.05.02 13:16
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
Много народу в сети RC5 ломает перебором (на сколько я понимаю хоть и не в лоб, но перебором). Можно конечно и крепостную стену лбом пробить, если 2^N людей будут в нее долбиться в течение 2^M лет.
Насколько я понимаю все методы шифрования с открытым ключем основаны на отсутствии быстрого алгоритма разложения числа на множители. Точнее нужно для числа найти его два сомножителя, поскольку заведомо известно, что для его получения брались два больших простых числа, стало быть других делителей оно не имеет.
Интересно, кто-нибудь подходил к решению этой проблемы достаточно близко. Существуют несколько известных алгоритмов, которые значительно сокращают время поиска сомножителей перебором, но можно же задачу и без перебора решить. Или нельзя. Ни где не видел доказательств, только фраза: "задача NP-полноты".
|
|
про NP 12.05.02 21:26
Автор: Dude Статус: Незарегистрированный пользователь
|
> Интересно, кто-нибудь подходил к решению этой проблемы
> достаточно близко. Существуют несколько известных
Довольно близко - Шор (алгоритм Шора). Алгоритм, как предполагают, позволит факторизовать числа оч быстро, но только на квантовом компе. А таких пока нет, по крайней мере, способных выполнить соотв. прогу.
> решить. Или нельзя. Ни где не видел доказательств, только
> фраза: "задача NP-полноты".
Если это задача NP-полноты (точно не знаю), то:
Доказательств не существует - ни доказательств, ни опровержений, если эта задача NP-полная. Т.е. неизвестно, можно ли решить NP-полную задачу за полиномиальное время. Однако, поскольку есть оч много таких задач (задача о коммивояжере, о максимальном полном подграфе, и т.д.), и если хотя бы одна из них решается за полиномиальное время, то решаются все, а решений не найдено ни для одной, то сейчас NP-полная задача - практически то же, что не разрешимая за полином. время задача.
А за большее - экспоненциальное - пожалуйста, прямым перебором.
Это все относится к задачам NP-полноты, но я, в свою очередь, хочу задать совсем ламерский вопрос: в чем состоит крякинг RC5? Что считают, например, клиеты distributed.net? Это конкретный зашифрованный пароль, или что-то вроде словаря, или что?
|
| |
про алгоритм Шора 13.05.02 21:14
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 13.05.02 21:15 Количество правок: 1
|
> Довольно близко - Шор (алгоритм Шора). Алгоритм, как
> предполагают, позволит факторизовать числа оч быстро, но
> только на квантовом компе. А таких пока нет, по крайней
> мере, способных выполнить соотв. прогу.
IBM в конце прошлого года реализовала выполнение subj на квантовом уровне. Конечно в игрушечном масштабе, но все же...
http://researchweb.watson.ibm.com/resources/news/20011219_quantum.shtml
И вот еще, в продолжение: http://perst.isssph.kiae.ru/Inform/tem/QSIS/2000/n.wcgi?QSIS.htm?C04
> Это все относится к задачам NP-полноты, но я, в свою
> очередь, хочу задать совсем ламерский вопрос: в чем состоит
> крякинг RC5? Что считают, например, клиеты distributed.net?
> Это конкретный зашифрованный пароль, или что-то вроде
> словаря, или что?
полным перебором ищется 64-битный ключ (пароль).
|
|
Специалисты поясните про криптоанализ RSA 12.05.02 14:49
Автор: vp016 Статус: Незарегистрированный пользователь
|
на множители. Точнее нужно для числа найти его два
> сомножителя, поскольку заведомо известно, что для его
> получения брались два больших простых числа, стало быть
> других делителей оно не имеет.
> Интересно, кто-нибудь подходил к решению этой проблемы
> достаточно близко. Существуют несколько известных
> алгоритмов, которые значительно сокращают время поиска
> сомножителей перебором, но можно же задачу и без перебора
> решить. Или нельзя. Ни где не видел доказательств, только
> фраза: "задача NP-полноты".
Брат, стукни в асю - 144221400. я обрыл всю библиотеку, по инет лазил немерянно - ссылки на быструю факторизацию числа, если только 2-а простых сомножителя есть, вот кроме упоминаний - ничего.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
