Иногда я ощущаю себя последним самураем на мосту, дальше отступать некуда, и если серость пройдет, ее уже никто не остановит.
Речь идет от написании криптографии для российских алгоритмов ГОСТ, а заодно об оптимизации. Российские алгоритмы криптографии на эллиптических кривых - это было когда-то очень круто, потому что наши опередили Америку в области стандартизации криптографии на годы, может быть на десяток лет. Шифрование эллиптическими кривыми, сама эллиптическая кривая задается уравнением: y^2 = x^3 +a*x +b. Только это уравнение рассматривается в пространстве завернутом в тор, на множестве целых чисел ограниченных простым числом P. Если идти по оси х, то через P попадем в нуль, P - это простое целое число, ни на что не делится. Такое поле называется finite prime field. Поле - математический термин, означает что на множестве чисел опеределены операции типа сложения и/или умножения. Кроме того, существует нулевой или единичный элемент E, для которого выполняются правила скобок и перестановок слагаемых. a + E = a, a+b=b+a,.. Еще бывает полезно знать, что существует обратный элемент, для которого сумма обращается в нуль, а произведение в единицу. Еще полезно бывает знать, что такой элемент единственный. Множество точек на кривой тоже образуют поле (поле - математический термин). Т/е над точками на кривой определены операции типа сложения точек и существует "единичный" элемент, который называется "бесконечность" и можно найти такой единственный элемент, для которого сумма точек уходит в "бесконечность". Т/е можно сказать, что поверх множества точек у нас действует опять таки алгебра, только операции пришлось подменить и ноль почему-то назвали бесконечностью, но для настоящих математиков и программистов - это не существенно.
Смотрел открытые реализации, как это делают другие. Читал книжки. Книжки пишут умные дядьки, но до программистов доходит долго. Видимо, те кто книжки пишут не пишут программ. А те кто программы пишет, чаще списывает, чем книжки читают. Чтение книг, тоже не помогает. Помогает, когда человек (мне например, помогло и я чувствую себя человеком) после прочтения может выполнять математические действия в аналитическом виде и на практике использовать полученные знания.
Несколько таких выводов я бы и обсудил. Вывод 1 операции и выражения можно и нужно упрощать перед использованием.
a (mod p) * b (mod p) = a*b (mod p)
a + p*m === a (mod p)
p*m === 0 (mod p)
В российской криптографии параметр a = p-3 в наборе параметров Crypto-Pro-A. Таким образом можно упростить уравнение до:
y^3 = x^2 - 3*x + b (mod p)
Умножать x на 3 гораздо проще, чем числа разрядностью 256 бит на 256 бит.
Чаще всего математики идут самым простым путем, они не ищут непонятную операцию и не доказывают ее отсутствие. Например, недостающую операцию умножения на множестве точек на эллиптической кривой можно разложить на операцию "сдвига" и "сложение". Сдвиг можно определить, как результат сложения a+a - point doubling. Нет, возражу себе, это не всегда так иногда операция a+a не тоже самое, что (doubling). В общем случае все-таки две независимые операции умножение и сложение, иногда можно выбрать другой базис: удвоение и сложение. Иногда достаточно только сложения и через него определяется умножение. Высшим пилотажем является доказательство, что операция "умножения" состоящая из таких сдвигов и сложений имеет единственный обратный элемент по отношению к операции "умножения". Но для этого бывает полезно переопределить "единицу" x*x^{-1} = e. Операция деления вообще не имеет право на существование - этому даже в школе учить нельзя. Есть у математиков понятие multiplicative inverse - операция получения обратного числа, для которого справедливо тождество (см выше). Есть необходимость доказательства единственности обратного числа и тогда мы опять оказываемся в поле с двумя операциями типа "сложение" и типа "умножения". Я немного путаюсь с терминами, потому что пишу по памяти. Есть еще понятие группа и абелева группа - это та, для которой определены обе операции типа сложение и типа умножения. И какое-то из правил перестановок делает из группы поле. (стоит продолжить) А ведь бывают еще кольца и бывают группы симметрии кристаллов.
Речь идет от написании криптографии для российских алгоритмов ГОСТ, а заодно об оптимизации. Российские алгоритмы криптографии на эллиптических кривых - это было когда-то очень круто, потому что наши опередили Америку в области стандартизации криптографии на годы, может быть на десяток лет. Шифрование эллиптическими кривыми, сама эллиптическая кривая задается уравнением: y^2 = x^3 +a*x +b. Только это уравнение рассматривается в пространстве завернутом в тор, на множестве целых чисел ограниченных простым числом P. Если идти по оси х, то через P попадем в нуль, P - это простое целое число, ни на что не делится. Такое поле называется finite prime field. Поле - математический термин, означает что на множестве чисел опеределены операции типа сложения и/или умножения. Кроме того, существует нулевой или единичный элемент E, для которого выполняются правила скобок и перестановок слагаемых. a + E = a, a+b=b+a,.. Еще бывает полезно знать, что существует обратный элемент, для которого сумма обращается в нуль, а произведение в единицу. Еще полезно бывает знать, что такой элемент единственный. Множество точек на кривой тоже образуют поле (поле - математический термин). Т/е над точками на кривой определены операции типа сложения точек и существует "единичный" элемент, который называется "бесконечность" и можно найти такой единственный элемент, для которого сумма точек уходит в "бесконечность". Т/е можно сказать, что поверх множества точек у нас действует опять таки алгебра, только операции пришлось подменить и ноль почему-то назвали бесконечностью, но для настоящих математиков и программистов - это не существенно.
Смотрел открытые реализации, как это делают другие. Читал книжки. Книжки пишут умные дядьки, но до программистов доходит долго. Видимо, те кто книжки пишут не пишут программ. А те кто программы пишет, чаще списывает, чем книжки читают. Чтение книг, тоже не помогает. Помогает, когда человек (мне например, помогло и я чувствую себя человеком) после прочтения может выполнять математические действия в аналитическом виде и на практике использовать полученные знания.
Несколько таких выводов я бы и обсудил. Вывод 1 операции и выражения можно и нужно упрощать перед использованием.
a (mod p) * b (mod p) = a*b (mod p)
a + p*m === a (mod p)
p*m === 0 (mod p)
В российской криптографии параметр a = p-3 в наборе параметров Crypto-Pro-A. Таким образом можно упростить уравнение до:
y^3 = x^2 - 3*x + b (mod p)
Умножать x на 3 гораздо проще, чем числа разрядностью 256 бит на 256 бит.
Чаще всего математики идут самым простым путем, они не ищут непонятную операцию и не доказывают ее отсутствие. Например, недостающую операцию умножения на множестве точек на эллиптической кривой можно разложить на операцию "сдвига" и "сложение". Сдвиг можно определить, как результат сложения a+a - point doubling. Нет, возражу себе, это не всегда так иногда операция a+a не тоже самое, что (doubling). В общем случае все-таки две независимые операции умножение и сложение, иногда можно выбрать другой базис: удвоение и сложение. Иногда достаточно только сложения и через него определяется умножение. Высшим пилотажем является доказательство, что операция "умножения" состоящая из таких сдвигов и сложений имеет единственный обратный элемент по отношению к операции "умножения". Но для этого бывает полезно переопределить "единицу" x*x^{-1} = e. Операция деления вообще не имеет право на существование - этому даже в школе учить нельзя. Есть у математиков понятие multiplicative inverse - операция получения обратного числа, для которого справедливо тождество (см выше). Есть необходимость доказательства единственности обратного числа и тогда мы опять оказываемся в поле с двумя операциями типа "сложение" и типа "умножения". Я немного путаюсь с терминами, потому что пишу по памяти. Есть еще понятие группа и абелева группа - это та, для которой определены обе операции типа сложение и типа умножения. И какое-то из правил перестановок делает из группы поле. (стоит продолжить) А ведь бывают еще кольца и бывают группы симметрии кристаллов.
Комментариев нет:
Отправить комментарий