eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
обновлён 2 декабря!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме:
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Основной форум —› Запрос: DLP
Посл.ответ Сообщение

Ранг: 581.2 (!)
Статус: Модератор

Создано: 30 марта 2010 11:24 New!
Цитата · Личное сообщение · #1

Здравствуйте,

нужно решить DLP для не очень большого числа (p - 256 бит). DLPTool не тянет такой модуль.
Гугль говорить что подобную задачу успешно решали Lz0 team для некоторых програм.

Если есть какие-то утилиты - напишите здесь. Если кто может посчитать - пишите ПМ.

2 Модеры. Запрос не подходит под форму в соответствующем топике - создал новый.


Статус: Пришелец

Создано: 30 марта 2010 13:59 New!
Цитата #2

Как задаётся группа? Желательно побольше описания.

Ранг: 581.2 (!)
Статус: Модератор

Создано: 30 марта 2010 14:32 New!
Цитата · Личное сообщение · #3

все элементы - dec/hex числа. Какое описание нужно?


Статус: Пришелец

Создано: 30 марта 2010 14:37 · Поправил: Модератор New!
Цитата #4

Для тех кто не знает криптологию, прошу сюда:
ru.wikipedia.org/wiki/Дискретное логарифмирование

Что-то мне подсказывает, что для такого "небольшого" p в любом случае потребуется нехилая вычислительня мощность. Для сравнения, с использованием индексного исчисления на моей машине подсчёт для 96 бит занимает 10 минут.

Ранг: 581.2 (!)
Статус: Модератор

Создано: 31 марта 2010 10:58 New!
Цитата · Личное сообщение · #5

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

Интересно было бы узнать о требованиях по памяти/времени для разных длин.

p.s. глянь пм


Статус: Пришелец

Создано: 31 марта 2010 11:52 New!
Цитата #6

r_e
Да, я получил ПМ. Сегодня занят буду.

Ранг: 617.3 (!)
Статус: Участник

Создано: 31 марта 2010 14:12 New!
Цитата · Личное сообщение · #7

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

Несколько реализаций встречал тут:
www.cs.umbc.edu/~stephens/crypto/CIPHERS/shankstools.html
Но часть не смог скомпилить, а часть очень медленные.
еще несколько вариантов на яве встречал на форуме msieve (сейчас что-то не нашел ту тему).


Статус: Пришелец

Создано: 31 марта 2010 14:19 New!
Цитата #8

Vovan666
Писать что-то на базе миракла уж проще застрелиться.

Ранг: 2.1 (гость)
Статус: Участник

Создано: 31 марта 2010 15:37 · Поправил: qptJ New!
Цитата · Личное сообщение · #9

http://magma.maths.usyd.edu.au/calc/

Пример: 128-bit prime

p := 240814044127417966511327579528216966723;
g := GF(p) ! 122498031754037724046952196245650501165;
y := GF(p) ! 36445864572062853425320819366118649895;
x := Log(g, y);
x ;


Magma V2.16-6 Wed Mar 31 2010 22:45:41 [Seed = 3409167230]
-------------------------------------

185029509051492910910909119354497357087

Total time: 7.780 seconds, Total memory usage: 27.34MB


Сущаствуют различные атаки на DLP, некоторые из них описаны в Handbook of Applied Cryptography

Ранг: 581.2 (!)
Статус: Модератор

Создано: 31 марта 2010 17:13 New!
Цитата · Личное сообщение · #10

qptJ
Магма - это хорошо, но нет в свободном доступе. Помимо нее есть еще куча матпакетов
en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems
но все перебирать - замахаешься.

> Сущаствуют различные атаки на DLP
Смотри википедию. Все они аналогичны проблемам факторизации.

Vovan666
Уже веселее - посмотрю. Вот здесь еще есть исходники
www.cs.toronto.edu/~cvs/dlog/

Ранг: 2.1 (гость)
Статус: Участник

Создано: 31 марта 2010 17:41 New!
Цитата · Личное сообщение · #11

r_e пишет:
Помимо нее есть еще куча матпакетов

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

Ранг: 389.9 (мудрец)
Статус: Участник

Создано: 31 марта 2010 17:47 New!
Цитата · Личное сообщение · #12

r_e
> Магма - это хорошо, но нет в свободном доступе

это не оно https://magma.maths.usyd.edu.au/magma/export/pc-x86-windows/ ?

https://magma.maths.usyd.edu.au/magma/export/pc-x86-windows/2.16-7/setup.exe

Ранг: 581.2 (!)
Статус: Модератор

Создано: 31 марта 2010 17:48 · Поправил: r_e New!
Цитата · Личное сообщение · #13

qptJ
Если есть сцылка на дистриб - с удовольствием ознакомлюсь. Года 1.5 назад пробегал архив, но найти сейчас не могу.

BFox
Там пасс нужен для скачивания.


Ранг: 1998.8 (!!!!)
Статус: Модератор
retired

Создано: 5 апреля 2010 17:58 · Поправил: Модератор New!
Цитата · Личное сообщение · #14

Насколько я знаю, самое большое ломали-112 бит. Так что забудь.
З.Ы. Мальца некропост получился...

Ранг: 581.2 (!)
Статус: Модератор

Создано: 5 апреля 2010 21:56 New!
Цитата · Личное сообщение · #15

Archer
Да уж, немного припознился.
Смотрим на DSA, которая построена на DLP.
Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The original DSS constrained L to be a multiple of 64 between 512 and 1024 (inclusive). NIST 800-57[7] recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N.[3] specifies L and N length pairs of (1024,160), (2048,224), (2048,256), and (3072,256).
В моем случае L = 256, N = 128. Отседа я делал вывод что должно получиться.

p.s. progopis, ты еще жив?


Статус: Пришелец

Создано: 5 апреля 2010 22:10 New!
Цитата #16

r_e
Archer уже всё сказал, число нереальное, как я и предполагал сразу, хотя сдаётся мне он имел в виду ЭльГамаль на группе точек эллиптической кривой. Короче доступ в НИВЦ пока выбить не получилось, а без этого в любом случае задача не разрешимая. Ботнеты не предлагать

Ранг: 581.2 (!)
Статус: Модератор

Создано: 9 апреля 2010 20:16 New!
Цитата · Личное сообщение · #17

Magma стоит 50 уе для студентов университетов развивающихся стран. Это для стандартной версии с оганичением на workspace в 100 Мб.
В принципе можно купить. Был бы студент. ;)

Ранг: 2.1 (гость)
Статус: Участник

Создано: 10 апреля 2010 11:12 New!
Цитата · Личное сообщение · #18

r_e
у тебя какая система?
Если там Elgamal, то можно взломать систему без решения DLP
Атака называется Existential Forgery Attack

Ранг: 581.2 (!)
Статус: Модератор

Создано: 10 апреля 2010 12:21 New!
Цитата · Личное сообщение · #19

qptJ
Судя по описанию, EFA направлена на поиск коллизии для функции хеширования.
Мне же нужно подписывать достаточно короткие сообщения (порядка 0х100 байт), которые отличаются несколькими байтами. imho, при таких ограничениях найти коллизию будет проблематично.
 eXeL@B —› Основной форум —› Запрос: DLP

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS