Size: a a a

DCG#7812 DEFCON-RUSSIA

2019 November 23

r

rzrzrz in DCG#7812 DEFCON-RUSSIA
Для меня это дно.
источник

AP

Al Po in DCG#7812 DEFCON-RUSSIA
Malwaretech второй ресурс на которой были статьи с описанием
источник

JB

James Brook Bond in DCG#7812 DEFCON-RUSSIA
Поорал с этого блока сообщений))
источник

AP

Al Po in DCG#7812 DEFCON-RUSSIA
Ну то есть я не вижу смысла задавать вопрос, который подразумевает что кто то должен пойти и найти файл или ссылку, вот если был бы вопрос про конкретную часть реализации то одно дело, а второе когда просто думают что найдут конкретную инфу чтоб самим не искать
источник

JB

James Brook Bond in DCG#7812 DEFCON-RUSSIA
Что ни день то вопрос. Выручайте. При передаче сообщения электронной почты достаточно ли знать только mx запись для подключения к серверу? (Есть адресат, есть от кого отправка)
источник

JB

James Brook Bond in DCG#7812 DEFCON-RUSSIA
Может с подвохом вопрос?
источник

JB

James Brook Bond in DCG#7812 DEFCON-RUSSIA
По идее мы отправили на наш местный smtp он, получив через mx запись smtp адресата направляется прямиком к нему и присылает ему письмо
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
Товарищи, здравствуйте. Есть вопрос из области криптографии/математики по вычислению сложности алгоритмов.
Вопрос по асимптотике задачи дискретного логарифмирования в мультипликативной группе кольца вычетов по модулю m. Условно, известны g и a = g^x, найти x.
В самом тупом варианте решения - при переборе - мы возводим g в степени 2, 3, 4 ... x, соответственно, у нас идёт x операций умножения. Операция умножения в худшем случае выполняется за O(n^2), где n - это количество знаков в числе. Оно у нас ограничено модулем m, то есть выполняется за полиномиальное время.

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

В гугле искал, не помогает.
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
С оценкой вычислительной сложности знаком довольно поверхностно, поэтому если подскажете статей или книжек, тоже буду благодарен.
источник

DK

Denis Kolegov in DCG#7812 DEFCON-RUSSIA
Операций умножения как раз не x, а log2(|G|). Почитать можно здесь:

1) https://crypto.stackexchange.com/questions/12865/why-is-the-discrete-logarithm-problem-assumed-to-be-hard
2) https://en.wikipedia.org/wiki/Discrete_logarithm
источник

DP

D P in DCG#7812 DEFCON-RUSSIA
Alexander Krikun
Товарищи, здравствуйте. Есть вопрос из области криптографии/математики по вычислению сложности алгоритмов.
Вопрос по асимптотике задачи дискретного логарифмирования в мультипликативной группе кольца вычетов по модулю m. Условно, известны g и a = g^x, найти x.
В самом тупом варианте решения - при переборе - мы возводим g в степени 2, 3, 4 ... x, соответственно, у нас идёт x операций умножения. Операция умножения в худшем случае выполняется за O(n^2), где n - это количество знаков в числе. Оно у нас ограничено модулем m, то есть выполняется за полиномиальное время.

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

В гугле искал, не помогает.
в теории сложности алгоритмы оцениваются число шагов алгоритма на машине Тьюринга от _размера_ входных данных. Т.е. _длина_ записи слова (вх. данных). При этом считается, что основание системы > 1

в нашем случае, число допустим размера 512 бит. А число шагов - 2^512 * Const, к примеру
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
Ну, так операция умножения зависит от размера числа, которое максимально размер модуля группы.
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
И 2^512 - это всё ещё полиномиальное время.
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
По крайней мере по определению отсюда:
https://en.m.wikipedia.org/wiki/Time_complexity
источник

DP

D P in DCG#7812 DEFCON-RUSSIA
> И вот вопрос: как из выполнения полиномиальной операции (умножение) линейное количество раз (искомая степень)

не линейное количество раз. в том то и дело. а количество раз exp(<длина числа в битах>)
источник

JG

JeisonWi Garrison in DCG#7812 DEFCON-RUSSIA
сложность еще разная бывает
источник

JG

JeisonWi Garrison in DCG#7812 DEFCON-RUSSIA
малая омега, большая, еще несколько разных
источник

AK

Alexander Krikun in DCG#7812 DEFCON-RUSSIA
Сейчас смотрим на большое О, как я понимаю.
источник

JG

JeisonWi Garrison in DCG#7812 DEFCON-RUSSIA
да, заметил
источник

JG

JeisonWi Garrison in DCG#7812 DEFCON-RUSSIA
Alexander Krikun
С оценкой вычислительной сложности знаком довольно поверхностно, поэтому если подскажете статей или книжек, тоже буду благодарен.
курс был на курсере про сложность
источник