Обычно для DLOG строят таблицу логарифмов, главный минус которой - можно построить только по одному .
Таблица степеней - это перевернутая таблица логарифмов, строка переносится в шапку таблицы степеней и сортируется, строка переносится вниз, а слева появляется возможность добавить колонку для , см. рис.
таблица степеней слева, таблица логарифмов справа
По идее в таблицу степеней можно добавить колонку дляно ее обычно опускают.
Наверное моя вина - в статье неправильно расставлены акценты.
У меня нет претензий к DH, описанные уязвимости - математические.
Они "пришли" в протокол DH вместе с дискретным логарифмом (DLOG).
Создатели DH всегда подчеркивали что зависят от DLOG.
И вообще протокол DH - прекрасная идея.
Другое дело тривиальные случаи DLOG (не DH), (в терминах DH - когда закрытый ключ может быть вычислен легко), освещены в публичной сфере очень слабо, в комментах исходного кода, в обсуждениях на форумах и прочее.
А статья будет полезна начинающим криптографам - к которым причисляю и себя.
Насчет (p-1)/2 точно не думаю - уж слишком "наверху" находится, смущает что не описано в какой-нибудь вики или открытой статье, чтобы быстро находилось.
Я думаю что и известен пример с (p-2) хотя спрятан дальше.
Спасибо, для математики не важно - большое или маленькое.
Проверять заранее невалидный закрытый ключ на уровне публичного ключа неверно, так как тратятся лишние ресурсы на ненужное вычисление того-же публичного ключа.
Что касается p-2 - то этот случай тоже давно известен. Там открытый ключ окажется маленьким
Почитал несколько статей про эти коды РС(Рида-Соломона) - что то как то "рыхло", куча способов реализации, в общем нарыл следующее - в кодах РС у понятия "порождающий полином" два разных применения:
"порождающий полином" для полей Галуа, полностью повторяет то, что я имею в виду в своей статье.
"порождающий полином" для кодов РС, используемый на этапе кодирования, в одной статье видел его название как "полином-генератор" (с англ. generator polynomial) так и буду в дальнейшем его называть, чтобы не путать с первым.
Добавляет непонятности, что использование порождающего ("неприводимого" как на скрине) полинома является необязательным. Например, если используется поле , так как результат можно получить по . Также, кажется и у Вас в проекте, дали подсказку - PrimeNumber^1
Еще в статье порождающий полином тоже не использовался, так как поле . В этой статье комментарии очень интересные.
Еще больше непонятности добавляет, что и "полином-генератор" (2-е применение) является кажется необязательным, привожу цитату из комментариев из выше приведенной статьи (поправил немножко):
... Ваш алгоритм похож на тот, который мы изучали. Методы, которые у нас были по кодированию:
1) чистое DFT;
2) несистематическое кодирование с g(x);
3) систематическое кодирование с g(x) и вычислением остатка;
4) систематическое кодирование с полиномом парности.
...
Таким образом, если нужно перейти на более чем первую степень, т.е. использовать поле , при , понадобится порождающий полином для полей Галуа.
Про "полином-генератор" (2-е применение) не буду говорить, так как не разбираюсь.
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены
Наверное в ваших рассуждениях есть смысл - попробуйте сами реализовать свою идею.
Я честно говоря уже "охладел" к конечным полям, на столе лежит другой проект.
С этим могу согласиться, смысла для поля искать порождающие полиномы нет. В статье так и написано:
Для можно обойтись получением результата по mod.
Единственное, у Вас неудачный пример с , так как 9 не простое число - мультипликативную группу по этому полю не построить, для 9 элементов нужно использовать поле
Спасибо, когда я искал информацию по порождающим полиномам для конечных полей мне попадались статьи по кодам Рида-Соломона, я не стал глубоко разбираться в данном вопросе, потому что эти коды выходят за пределы моего текущего интереса. Но у меня осталось четкое представление что порождающий полином для кодов Рида-Соломона строится по другому, зависит от таких параметров как: длина сообщения, количество ошибочных символов,... Могу ошибаться, поправьте если что.
Дискретный логарифм (DLOG) по модулю
Пример для
для примитива 
Обычно для DLOG строят таблицу логарифмов, главный минус которой - можно построить только по одному
.
Таблица степеней - это перевернутая таблица логарифмов, строка
переносится в шапку таблицы степеней и сортируется, строка 
переносится вниз, а слева появляется возможность добавить колонку для 
, см. рис.
По идее в таблицу степеней можно добавить колонку для
но ее обычно опускают.
Извините, просто некогда "воду в ступе толочь"
Наверное моя вина - в статье неправильно расставлены акценты.
У меня нет претензий к DH, описанные уязвимости - математические.
Они "пришли" в протокол DH вместе с дискретным логарифмом (DLOG).
Создатели DH всегда подчеркивали что зависят от DLOG.
И вообще протокол DH - прекрасная идея.
Другое дело тривиальные случаи DLOG (не DH), (в терминах DH - когда закрытый ключ может быть вычислен легко), освещены в публичной сфере очень слабо, в комментах исходного кода, в обсуждениях на форумах и прочее.
А статья будет полезна начинающим криптографам - к которым причисляю и себя.
Спасибо :)
Нет уязвимости в DH, есть (не уязвимость) а особенность DLOG.
А насчет вероятности стремящейся к 0 - Вы правы на 100%
Да, и описана у меня в статье
Насчет (p-1)/2 точно не думаю - уж слишком "наверху" находится, смущает что не описано в какой-нибудь вики или открытой статье, чтобы быстро находилось.
Я думаю что и известен пример с (p-2) хотя спрятан дальше.
Спасибо, для математики не важно - большое
или маленькое.
Проверять заранее невалидный закрытый ключ на уровне публичного ключа неверно, так как тратятся лишние ресурсы на ненужное вычисление того-же публичного ключа.
Сможете математически доказать?
Спасибо, почитаю, не слишком ли глубоко спрятано "циклическую подгруппу (простого) порядка (p-1)/2 " и у меня в статье имеется ввиду классический DH
Спасибо, но это обсуждение с двумя минусовыми ответами, а не утверждение.
Ccылку пришлите где вы нашли запрет на использование в качестве закрытого ключа (p-1)/2 ?
Жду вторую часть, нашел небольшую ошибку визуализации P-блока при расшифровке, создал issue https://github.com/AlexeyCamacho/Basic_SP_Encryption/issues/1
Надо будет проверить. Спасибо
Не очень то я в плюсах :(
Почитал несколько статей про эти коды РС(Рида-Соломона) - что то как то "рыхло", куча способов реализации, в общем нарыл следующее - в кодах РС у понятия "порождающий полином" два разных применения:
"порождающий полином" для полей Галуа, полностью повторяет то, что я имею в виду в своей статье.
"порождающий полином" для кодов РС, используемый на этапе кодирования, в одной статье видел его название как "полином-генератор" (с англ. generator polynomial) так и буду в дальнейшем его называть, чтобы не путать с первым.
А в этой статье - это прямо видно, скрин привожу:
Добавляет непонятности, что использование порождающего ("неприводимого" как на скрине) полинома является необязательным. Например, если используется поле
, так как результат можно получить по 
. Также, кажется и у Вас в проекте, дали подсказку - PrimeNumber^1
Еще в статье порождающий полином тоже не использовался, так как поле
. В этой статье комментарии очень интересные.
Еще больше непонятности добавляет, что и "полином-генератор" (2-е применение) является кажется необязательным, привожу цитату из комментариев из выше приведенной статьи (поправил немножко):
Таким образом, если нужно перейти на более чем первую степень, т.е. использовать поле
, при 
, понадобится порождающий полином для полей Галуа.
Про "полином-генератор" (2-е применение) не буду говорить, так как не разбираюсь.
Вроде так
Наверное в ваших рассуждениях есть смысл - попробуйте сами реализовать свою идею.
Я честно говоря уже "охладел" к конечным полям, на столе лежит другой проект.
Спасибо, очень интересно - руки чешутся попробовать разобраться
С этим могу согласиться, смысла для поля
искать порождающие полиномы нет. В статье так и написано:
Единственное, у Вас неудачный пример с
, так как 9 не простое число - мультипликативную группу по этому полю не построить, для 9 элементов нужно использовать поле 
Во-первых, формула подтверждается эмпирическим путем.
Во-вторых, Вы мне льстите - это не моя формула, если бы я имел отношение к данной формуле, я бы не преминул это указать.
Кстати, в самой статье я привел ссылку на статью где приведена данная формула, если не достаточно, вот еще.
А у Вас что-то с расчетом не то.
Спасибо, когда я искал информацию по порождающим полиномам для конечных полей мне попадались статьи по кодам Рида-Соломона, я не стал глубоко разбираться в данном вопросе, потому что эти коды выходят за пределы моего текущего интереса.
Но у меня осталось четкое представление что порождающий полином для кодов Рида-Соломона строится по другому, зависит от таких параметров как: длина сообщения, количество ошибочных символов,... Могу ошибаться, поправьте если что.