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

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

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

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

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

-----
старый пень

| Сообщение посчитали полезным:

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

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

| Сообщение посчитали полезным:

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

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

p.s. глянь пм

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

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

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

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

-----
...или ты работаешь хорошо, или ты работаешь много...

| Сообщение посчитали полезным:

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

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

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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, ты еще жив?

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

-----
старый пень

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

-----
старый пень

| Сообщение посчитали полезным: