Умножение точек эллиптической кривой

Скалярное умножение эллиптической кривой — это операция последовательного многократного добавления точки вдоль эллиптической кривой сама к себе. Он используется в криптографии на основе эллиптических кривых (ECC). В литературе эта операция представлена как скалярное умножение , записанное в гессенской форме эллиптической кривой . Широко распространенное название этой операции — также умножение точек эллиптической кривой , но это может создать неправильное впечатление, что это умножение между двумя точками.

Основы [ править ]

Учитывая кривую E , определенную некоторым уравнением в конечном поле (например, E : $y 2 = х 3 + ax + b$ ), умножение точек определяется как повторное добавление точки вдоль этой кривой. Обозначим как $nP = P + P + P + \dots + P$ для некоторого скалярного (целого) n и точки $P = (x, y),$ на кривой E. лежащей Этот тип кривой известен как кривая Вейерштрасса.

Безопасность современного ECC зависит от сложности определения n из $Q = nP$ при известных значениях Q и P , если n велико (известная как проблема дискретного логарифмирования эллиптической кривой по аналогии с другими криптографическими системами ). Это связано с тем, что добавление двух точек на эллиптической кривой (или добавление одной точки к самой себе) дает третью точку на эллиптической кривой, местоположение которой не имеет очевидной связи с местоположениями первых двух, и это повторяется много раз. over дает точку nP , которая может находиться практически где угодно. Интуитивно это похоже на тот факт, что если бы у вас была точка P на окружности, добавление 42,57 градуса к ее углу все равно может быть точкой «не слишком далеко» от P , но добавление 1000 или 1001 раза по 42,57 градуса даст точка, которая требует немного более сложных вычислений, чтобы найти исходный угол. Обратить этот процесс, т. е. при условии Q=nP и P , и определить n , можно только перепробовав все возможные n — усилие, которое вычислительно невыполнимо, если n велико.

Точечные операции [ править ]

Операции с точками эллиптической кривой: сложение (показано на фасете 1), удвоение (фасеты 2 и 4) и отрицание (фасет 3).

Для точек эллиптической кривой обычно используются три операции: сложение, удвоение и отрицание.

Точка в бесконечности [ править ]

Точка в бесконечности ⁠ ${\mathcal {O}}$ ⁠ — единичный элемент арифметики эллиптических кривых. Добавление его к любой точке приводит к созданию этой другой точки, включая добавление точки, находящейся на бесконечности, к самой себе. То есть:

{\begin{aligned}{\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}\\{\mathcal {O}}+P=P\end{aligned}}

Точка на бесконечности также записывается как $0$ .

Отрицание точки [ править ]

Отрицание точки - это поиск такой точки, прибавление которой к самой себе приведет к точке, находящейся в бесконечности ( ⁠ ${\mathcal {O}}$ ⁠ ).

{\begin{aligned}P+(-P)={\mathcal {O}}\end{aligned}}

Для эллиптических кривых вида E : $y 2 = х 3 + ax + b$ , отрицание — это точка с той же координатой x, но с отрицательной координатой y :

{\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}

Добавление очков [ править ]

При наличии двух различных точек P и Q полученной в результате пересечения кривой E и прямой линии, определяемой точками P и Q , дающей точку R. сложение определяется как отрицание точки , ^[1]

{\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}

Предполагая, что эллиптическая кривая E задается выражением $y 2 = х 3 + ax + b$ это можно рассчитать как:

{\begin{aligned}\lambda &={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=\lambda ^{2}-x_{p}-x_{q}\\y_{r}&=\lambda (x_{p}-x_{r})-y_{p}\\\end{aligned}}

Эти уравнения верны, если ни одна из точек не является точкой, находящейся на бесконечности, ⁠ ${\mathcal {O}}$ ⁠ , и если точки имеют разные координаты x (они не являются взаимно инверсными). Это важно для алгоритма проверки ECDSA , где значение хеш-функции может быть нулевым.

Удвоение очков [ править ]

Если точки P и Q совпадают (в одних и тех же координатах), сложение аналогично, за исключением того, что нет четко определенной прямой линии, проходящей через P , поэтому операция завершается с использованием предельного случая, касательной к кривой E , у П.

Это рассчитывается, как указано выше, с использованием производных (dE/dx)/(dE/dy): ^[2]

\lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}

где a взято из определяющего уравнения кривой E , приведенного выше.

Умножение точек [ править ]

Самый простой способ вычисления умножения точек — многократное сложение. Однако существуют более эффективные подходы к вычислению умножения.

Двойное сложение [ править ]

Самый простой метод — метод двойного сложения. ^[3] аналогично квадрату и умножению в модульном возведении в степень. Алгоритм работает следующим образом:

Чтобы вычислить sP , начните с двоичного представления s : ⁠ $s=s_{0}+2s_{1}+2^{2}s_{2}+\cdots +2^{n-1}s_{n-1}$ ⁠ , где ⁠ $s_{0}~..~s_{n-1}\in \{0,1\},n=\lceil \log _{2}{s}\rceil$ ⁠ .

Итерационный алгоритм, увеличение индекса:

   let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
   let res =  ${\begin{aligned}{\mathcal {O}}\end{aligned}}$  # point at infinity
   let temp = P # track doubled P val
   for bit in bits: 
       if bit == 1:            
           res = res + temp # point add
       temp = temp + temp # double
   return res

Итерационный алгоритм, уменьшение индекса:

   let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
   let i = length(bits) - 2
   let res = P
   while (i >= 0): # traversing from second MSB to LSB
       res = res + res # double
       if bits[i] == 1:            
           res = res + P # add
       i = i - 1
   return res

Обратите внимание, что оба описанных выше итерационных метода уязвимы для временного анализа. Альтернативный подход см. ниже в «Лестнице Монтгомери».

Рекурсивный алгоритм:

  f(P, d) is
     if d = 0 then
         return 0                         # computation complete
     else if d = 1 then
         return P
     else if d mod 2 = 1 then
         return point_add(P, f(P, d - 1)) # addition when d is odd
     else
         return f(point_double(P), d / 2)   # doubling when d is even

где f — функция умножения, P — координата умножения, d — количество раз, которое нужно прибавить координату к самой себе. Пример: 100P можно записать как 2(2[P + 2(2[2(P + 2P)])]) и, таким образом, требует шести операций удвоения точек и двух операций сложения точек. 100P будет равно f(P, 100) .

Этот алгоритм требует log ₂ ( d ) итераций удвоения и сложения точек для вычисления полного умножения точек. Существует множество вариантов этого алгоритма, например использование окна, скользящего окна, NAF, NAF-w, векторных цепочек и лестницы Монтгомери.

Оконный метод [ править ]

В оконной версии этого алгоритма ^[3] выбирают размер окна w и вычисляют все $2^{w}$ значения $dP$ для $d=0,1,2,\dots ,2^{w}-1$ . Алгоритм теперь использует представление $d=d_{0}+2^{w}d_{1}+2^{2w}d_{2}+\cdots +2^{mw}d_{m}$ и становится

  Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if d_i > 0 then
          Q ← point_add(Q, d_iP) # using pre-computed value of d_iP
  return Q

Этот алгоритм имеет ту же сложность, что и подход «двойное сложение», но с преимуществом использования меньшего количества добавлений точек (которые на практике медленнее, чем удвоение). Обычно значение w выбирается достаточно небольшим, что делает этап предварительных вычислений тривиальным компонентом алгоритма. Для кривых, рекомендованных NIST, $w=4$ обычно это лучший выбор. Полная сложность для n -битного числа измеряется как $n+1$ очко удваивается и $2^{w}-2+{\tfrac {n}{w}}$ точечные дополнения.

Метод скользящего окна [ править ]

В версии со скользящим окном мы стремимся заменить добавление очков удвоением очков. Мы вычисляем ту же таблицу, что и в оконной версии, за исключением того, что мы вычисляем только точки $dP$ для $d=2^{w-1},2^{w-1}+1,\dots ,2^{w}-1$ . По сути, мы вычисляем только те значения, для которых установлен старший бит окна. Затем алгоритм использует исходное представление двойного сложения $d=d_{0}+2d_{1}+2^{2}d_{2}+\cdots +2^{m}d_{m}$ .

  Q ← 0
  for i from m downto 0 do
      if d_i = 0 then
          Q ← point_double(Q)
      else 
          t ← extract j (up to w − 1) additional bits from d (including d_i)
          i ← i − j
          if j < w then
              Perform double-and-add using t 
              return Q
          else 
              Q ← point_double_repeat(Q, w)
              Q ← point_add(Q, tP)
  return Q

Преимущество этого алгоритма состоит в том, что этап предварительного расчета примерно вполовину сложнее обычного оконного метода, а также позволяет заменить более медленное добавление очков удвоением очков. По сути, нет особых причин использовать оконный метод вместо этого подхода, за исключением того, что первый может быть реализован за постоянное время. Алгоритм требует $w-1+n$ очко удваивается и не более $2^{w-1}-1+{\tfrac {n}{w}}$ точечные дополнения.

$w$ -арный несмежный метод формы ( $w$ NAF) [ править ]

В несмежной форме мы стремимся использовать тот факт, что вычитание точек так же просто, как и добавление точек, чтобы выполнить меньше (и того, и другого) по сравнению с методом скользящего окна. NAF множимого $d$ необходимо сначала вычислить по следующему алгоритму

   i ← 0
   while (d > 0) do
       if (d mod 2) = 1 then 
           d_i ← d mods 2^w
           d ← d − d_i
       else
           d_i = 0
       d ← d/2
       i ← i + 1
   return (d_i−1, d_i-2, …, d₀)

Где подписанные функции по модулю mods определяются как

   if (d mod 2^w) >= 2^w−1
       return (d mod 2^w) − 2^w
   else
       return d mod 2^w

Это создает NAF, необходимый для выполнения умножения. Этот алгоритм требует предварительного расчета точек $\lbrace 1,3,5,\dots ,2^{w-1}-1\rbrace P$ и их негативы, где $P$ это точка, которую нужно умножить. На типичных кривых Вейерштрасса, если $P=\lbrace x,y\rbrace$ затем $-P=\lbrace x,-y\rbrace$ . Так что, по сути, вычислить негативы несложно. Далее следующий алгоритм вычисляет умножение $dP$ :

   Q ← 0
   for j ← i − 1 downto 0 do
       Q ← point_double(Q)
       if (d_j != 0)
           Q ← point_add(Q, d_jP)
   return Q

WNAF гарантирует, что в среднем будет плотность ${\tfrac {1}{w+1}}$ точечные дополнения (чуть лучше, чем неподписанное окно). Это требует удвоения на 1 очко и $2^{w-2}-1$ добавление точек для предварительного расчета. Тогда алгоритм требует $n$ удвоение очков и ${\tfrac {n}{w+1}}$ прибавление точек для оставшейся части умножения.

Одним из свойств NAF является то, что мы гарантируем, что каждый ненулевой элемент $d_{i}$ за которым следует как минимум $w-1$ дополнительные нули. Это связано с тем, что алгоритм очищает нижние $w$ кусочки $d$ с каждым вычитанием вывода функции mods . Это наблюдение можно использовать для нескольких целей. После каждого ненулевого элемента могут подразумеваться дополнительные нули, которые не нужно сохранять. Во-вторых, многократное серийное деление на 2 можно заменить делением на $2^{w}$ после каждого ненулевого $d_{i}$ элемент и делим на 2 после каждого нуля.

Было показано, что с помощью атаки по побочному каналу FLUSH+RELOAD на OpenSSL полный закрытый ключ может быть раскрыт после выполнения синхронизации кэша всего лишь с 200 выполненными подписями. ^[4]

Лестница Монтгомери [ править ]

Лестница Монтгомери ^[5] подход вычисляет умножение точек за фиксированное количество операций. , получает доступ к измерениям времени, энергопотребления или измерений ветвей Это может быть полезно, когда злоумышленник, выполняющий атаку по побочному каналу . Алгоритм использует то же представление, что и в методе «двойное сложение».

  R₀ ← 0
  R₁ ← P
  for i from m downto 0 do
      if d_i = 0 then
          R₁ ← point_add(R₀, R₁)
          R₀ ← point_double(R₀)
      else
          R₀ ← point_add(R₀, R₁)
          R₁ ← point_double(R₁)

      // invariant property to maintain correctness
      assert R₁ == point_add(R₀, P)
  return R₀

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

Однако было показано, что с помощью атаки по побочному каналу FLUSH+RELOAD на OpenSSL можно раскрыть полный закрытый ключ после выполнения синхронизации кэша только для одной подписи с очень низкими затратами. ^[6]

Код ржавчины для лестницы Монтгомери: ^[7]

/// Constant operation point multiplication. 
/// NOTE: not memory safe.
/// * `s`: scalar value to multiply by
/// * multiplication is defined to be P₀ + P₁ + ... Pₛ
fn sec_mul(&mut self, s: big) -> E521{
    let mut r0 = get_e521_id_point();
    let mut r1 = self.clone();
    for i in (0..=s.significant_bits()).rev()  {
        if s.get_bit(i) {
            r0 = r0.add(&r1);
            r1 = r1.add(&r1.clone());
        } else {
            r1 = r0.add(&r1);
            r0 = r0.add(&r0.clone());
        }
    }
    r0 // r0 = P * s
}

Лестница Монтгомери постоянным временем с

Безопасность криптографической реализации может столкнуться с угрозой так называемых тайминговых атак. который использует зависящие от данных временные характеристики реализации. Машины, работающие с криптографическими реализации потребляют переменное количество времени для обработки различных входных данных, поэтому время различаться в зависимости от ключа шифрования. Для решения этой проблемы реализованы криптографические алгоритмы. таким образом, чтобы исключить временную характеристику переменной, зависящей от данных, из реализации, ведущей к так называемым реализациям с постоянным временем. Реализации программного обеспечения считаются постоянными во времени. следующий смысл, как указано в: ^[8] « избегает всех ветвей, зависящих от ввода, всех индексов массива, зависящих от ввода, и других инструкций с таймингами, зависящими от ввода. Страница на GitHub ^[9] перечисляет правила кодирования для реализации криптографических операций и, в более общем плане, для операций, связанных с секретными или чувствительные ценности.

Лестница Монтгомери – это $x$ -алгоритм только координат для умножения точек эллиптической кривой и основан на правилах двойного и сложения для определенного набора кривых, известных как кривая Монтгомери . Алгоритм имеет условное ветвление так что условие зависит от секретного бита. Таким образом, простой реализации лестницы не будет. постоянное время и может привести к утечке секретного бита. Эта проблема нашла свое отражение в литературе. ^[10]^[11] и известно несколько реализаций с постоянным временем. Ниже представлен лестничный алгоритм Монтгомери с постоянным временем, который использует две функции CSwap и Ladder-Step. В возвращаемом значении алгоритма Z ₂^р-2 значение Z ₂^-1 вычисляется с помощью малой теоремы Ферма .

  Algorithm Montgomery-Ladder(x_P,n)
  input: An  $l$ -bit scalar  $n$  and the  $x$ -coordinate  $x_{P}$  of a point  $P$ .
  output:  $x$ -coordinate of  $nP$ , the  $n$ -times scalar multiple of  $P$ .  
  
  X₁ ← x_P; X₂ ← 1; Z₂ ← 0; X₃ ← x_P; Z₃ ← 1
  prevbit ← 0
  for  $i$  from  $l-1$  downto 0 do
      bit ← bit-value at index  $i$  of  $n$ 
      b ← bit  $\oplus$  prevbit
      prevbit ← bit
      ( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ ) ← CSwap( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ ,b)
      ( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ ) ← Ladder-Step( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ ,X₁)
       
  return X₂Z₂^p-2

Функция Ladder-Step (приведенная ниже), используемая в лестнице, является ядром алгоритма и представляет собой комбинированную форму дифференциальных операций сложения и удвоения. Поле константа a ₂₄ определяется как a ₂₄ = $(A+2)/4$ , где $A$ является параметром базовой кривой Монтгомери .

  Function Ladder-Step( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ ,X₁)

  T₁ ← X₂ + Z₂
  T₂ ← X₂ - Z₂
  T₃ ← X₃ + Z₃
  T₄ ← X₃ - Z₃
  T₅ ← T₁²
  T₆ ← T₂²
  T₂ ← T₂ · T₃
  T₁ ← T₁ · T₄
  T₁ ← T₁ + T₂
  T₂ ← T₁ - T₂
  X₃ ← T₁²
  T₂ ← T₂²
  Z₃ ← T₂ · X₁
  X₂ ← T₅ · T₆
  T₅ ← T₅ - T₆
  T₁ ← a₂₄ · T₅
  T₆ ← T₆ + T₁
  Z₂ ← T₅ · T₆

  return ( $\langle$ X₂,Z₂ $\rangle$ , $\langle$ X₃,Z₃ $\rangle$ )

Функция CSwap управляет условным ветвлением и помогает релейной схеме работать в соответствии с требованиями реализации с постоянным временем. Функция меняет местами пару элементов поля $\langle$ Х ₂ ,З ₂ $\rangle$ и $\langle$ Х ₃ , Я ₃ $\rangle$ только если $b$ = 1 и это делается без утечки какой-либо информации о секретном бите. В литературе предложены различные методы реализации CSwap. ^[10]^[11] Менее затратным вариантом управления требованием постоянного времени лестницы Монтгомери является условный выбор, который формализуется с помощью функции CSelect. Эта функция использовалась в различных оптимизациях и формально обсуждалась в ^[12]

С момента появления стандартной кривой Монтгомери Curve25519 на 128-битном уровне безопасности существовало множество программных реализаций для вычисления ECDH на различных архитектурах и для достижения максимально возможной производительности разработчики криптографических систем прибегали к написанию реализаций с использованием языка ассемблера базовой архитектуры. . Работа ^[13] предоставил пару реализаций 64-битной сборки, ориентированных на архитектуру AMD64. Реализации были разработаны с использованием инструмента, известного как qhasm. ^[14] который может генерировать высокоскоростные криптографические программы на языке ассемблера. Следует отметить, что в реализации этих цепочек использовалась функция CSwap. После этого было предпринято несколько попыток оптимизировать реализацию релейной логики с помощью написанных вручную программ на ассемблере, в которых впервые было использовано понятие CSelect. ^[15] а потом в. ^[16] Помимо использования последовательных инструкций, векторные инструкции также использовались для оптимизации вычислений лестницы посредством различных работ. ^[17]^[18]^[19]^[20] Наряду с AMD64 также были предприняты попытки добиться эффективной реализации на других архитектурах, таких как ARM. Работы ^[21] и ^[22] обеспечивает эффективные реализации, ориентированные на архитектуру ARM. Библиотеки lib25519 ^[23] и ^[24] — это две современные библиотеки, содержащие эффективные реализации лестницы Монтгомери для Curve25519 . Тем не менее, в библиотеках есть реализации и других криптографических примитивов.

Помимо Curve25519 , было несколько попыток вычислить лестницу по другим кривым на различных уровнях безопасности. эффективные реализации лестницы по стандартной кривой Curve448 на 224-битном уровне безопасности. В литературе также изучались ^[15]^[18]^[20] Была предложена кривая под названием Curve41417, обеспечивающая безопасность чуть более 200 бит. ^[25] в котором вариант стратегии Карацубы использовался для реализации умножения полей, необходимого для соответствующего программного обеспечения ECC. В поисках кривых Монтгомери, которые могли бы конкурировать с Curve25519 и Curve448, было проведено исследование и предложено несколько кривых наряду с эффективными последовательными ^[16] и векторизованные реализации ^[20] соответствующих лестниц. На 256-битном уровне безопасности эффективные реализации лестницы также рассматривались с помощью трех различных кривых Монтгомери. ^[26]

Ссылки [ править ]

^ «Эллиптические кривые — формулы явного сложения» .
^ «Эллиптические кривые — формулы явного сложения» .
↑ Перейти обратно: Перейти обратно: ^а ^б Хэнкерсон, Даррел; Ванстон, Скотт; Менезес, Альфред (2004). Руководство по криптографии на основе эллиптических кривых . Springer Профессиональные вычисления. Нью-Йорк: Springer-Verlag. дои : 10.1007/b97644 . ISBN 0-387-95273-Х . S2CID 720546 .
^ Бенгер, Наоми; ван де Поль, Йооп; Смарт, Найджел П.; Яром, Юваль (2014). Батина, Лейла; Робшоу, Мэтью (ред.). «Ох-а-а… совсем немного»: небольшое количество побочного канала может иметь большое значение (PDF) . Криптографическое оборудование и встроенные системы – CHES 2014. Конспекты лекций по информатике. Том. 8731. Спрингер. стр. 72–95. дои : 10.1007/978-3-662-44709-3_5 . ISBN 978-3-662-44708-6 .
^ Монтгомери, Питер Л. (1987). «Ускорение методов факторизации Полларда и эллиптических кривых» . Математика. Комп. 48 (177): 243–264. дои : 10.2307/2007888 . JSTOR 2007888 . МР 0866113 .
^ Яром, Юваль; Бенгер, Наоми (2014). «Восстановление одноразовых номеров OpenSSL ECDSA с использованием атаки по побочному каналу кэша FLUSH+RELOAD» . Архив электронной печати криптологии IACR .
^ Рэй, Дастин. «Е521» . Проверено 25 февраля 2023 г.
^ Бернштейн, Дэниел Дж. «Curve25519: Новые рекорды скорости Диффи-Хеллмана» . В: Юнг М., Додис Ю., Киайас А., Малкин Т. (ред.) Криптография с открытым ключом - PKC 2006. Конспект лекций по информатике, том 3958. Springer, Берлин, Гейдельберг.
^ Омассон, Жан-Филипп. «Руководство по программному обеспечению низкоуровневой криптографии» . Гитхаб . Проверено 26 марта 2024 г.
↑ Перейти обратно: Перейти обратно: ^а ^б Бернштейн, Дэниел Дж.; Ланге, Таня. «Кривые Монтгомери и лестница Монтгомери» . В книге Джоппе В. Боса и Арьена К. Ленстры, редакторов, «Темы вычислительной теории чисел», вдохновленные Питером Л. Монтгомери, страницы 82–115. Издательство Кембриджского университета, 2017.
↑ Перейти обратно: Перейти обратно: ^а ^б Костелло, Крейг; Смит, Бенджамин. «Кривые Монтгомери и их арифметика — случай больших характеристических полей» . Дж. Криптографическая инженерия, 8 (3): 227–240, 2018.
^ Нат, Кошик; Саркар, Палаш. «Лестница Монтгомери в постоянное время» . Архив криптологии ePrint, статья 2020/956.
^ Бернштейн, Дэниел Дж.; Дуиф, Нильс; Ланге, Таня; Швабе, Питер; Ян, Бо Инь. «Высокоскоростные подписи с высокой степенью защиты» . Журнал «Криптографическая инженерия», 2(2):77–89, 2012.
^ Бернштейн, Дэниел Дж. «qhasm: инструменты, помогающие писать высокоскоростное программное обеспечение» .
↑ Перейти обратно: Перейти обратно: ^а ^б Оливейра, Томаз; Лопес, Хулио; Хисил, Хусейн; Фас-Эрнандес, Армандо; Родригес-Энрикес, Франциско. «Как (предварительно) вычислить лестницу: улучшение производительности X25519 и X448» . Карлайл Адамс и Ян Камениш, редакторы, «Выбранные области криптографии - SAC 2017 - 24-я международная конференция», Оттава, Онтарио, Канада, 16–18 августа 2017 г., Пересмотренные избранные статьи, том 10719 конспектов лекций по информатике, страницы 172– 191. Springer, 2017. Код доступен по адресу https://github.com/armfazh/rfc7748_precomputed .
↑ Перейти обратно: Перейти обратно: ^а ^б Нат, Кошик; Саркар, Палаш. «Компромисс безопасности и эффективности для эллиптической кривой Диффи-Хеллмана на 128- и 224-битных уровнях безопасности» . J Cryptogr Eng 12, 107–121 (2022). , Код доступен по адресу https://github.com/kn-cs/x25519.
^ Чжоу, Тунг. «Sandy2x: Новые рекорды скорости Curve25519» . Орр Данкельман и Лиам Келихер, редакторы, «Выбранные области криптографии – SAC 2015 – 22-я Международная конференция», Саквилл, Северная Каролина, Канада, 12–14 августа 2015 г., Пересмотренные избранные статьи, том 9566 конспектов лекций по информатике, страницы 145–160. Springer, 2015. Код доступен по адресу https://tungchou.github.io/sandy2x/.
↑ Перейти обратно: Перейти обратно: ^а ^б Фас-Эрнандес, Армандо; Лопес, Хулио; Дахаб, Рикардо. «Высокопроизводительная реализация криптографии на основе эллиптических кривых с использованием векторных инструкций» . АКМ Транс. Математика. Softw., 45(3):25:1–25:35, 2019. , Coce доступно по адресу https://github.com/armfazh/fld-ecc-vec.
^ Хисил, Хусейн; Эгриче, Беркан; Ясси, Мерт. «Быстрая четырехсторонняя векторизованная лестница для полного набора кривых Монтгомери» . Международный журнал науки информационной безопасности, Vol. 11, № 2, стр. 12-24. , Код доступен по адресу https://github.com/crypto-ninjaturtles/montgomery4x.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Нат, Кошик; Саркар, Палаш. «Эффективная четырехсторонняя векторизация лестницы Монтгомери» . Транзакции IEEE на компьютерах, том. 71, нет. 3, стр. 712–723, 1 марта 2022 г. , код доступен по адресу https://github.com/kn-cs/vec-ladder.
^ Бернштейн, Дэниел Дж.; Швабе, Питер. «НЕОН криптография» . Эммануэль Пруфф и Патрик Шаумон, редакторы, Криптографическое оборудование и встроенные системы - CHES 2012 - 14-й международный семинар, Левен, Бельгия, 9–12 сентября 2012 г. Материалы, том 7428 конспектов лекций по информатике, страницы 320–339. Спрингер, 2012.
^ Леннгрен, Эмиль. «Оптимизированная реализация AArch64 для X25519» (PDF) . Гитхаб.
^ Нат, Кошик; Бернштейн, Дэниел Дж . «lib25519» .
^ Харрисон, Джон Р. «s2n-bignum» .
^ Бернштейн, Дэниел Дж.; Чичанок, Чуэнсатиансуп; Таня, Ланге. «Curve41417: Возвращение к Карацубе» . В: Батина Л., Робшоу М. (ред.) Криптографическое оборудование и встроенные системы – CHES 2014. CHES 2014. Конспекты лекций по информатике, том 8731. Springer, Berlin, Heidelberg.
^ Нат, Кошик; Саркар, Палаш. «Эффективное вычисление Диффи-Хеллмана по эллиптической кривой на 256-битном уровне безопасности» . IET Information Security, 14(6):633640, 2020. Код доступен по адресу https://github.com/kn-cs/mont256-dh и https://github.com/kn-cs/mont256-vec.

[1] «Эллиптические кривые — формулы явного сложения» .

[2] «Эллиптические кривые — формулы явного сложения» .

[guide-3] Перейти обратно: Перейти обратно: ^а ^б Хэнкерсон, Даррел; Ванстон, Скотт; Менезес, Альфред (2004). Руководство по криптографии на основе эллиптических кривых . Springer Профессиональные вычисления. Нью-Йорк: Springer-Verlag. дои : 10.1007/b97644 . ISBN 0-387-95273-Х . S2CID 720546 .

[4] Бенгер, Наоми; ван де Поль, Йооп; Смарт, Найджел П.; Яром, Юваль (2014). Батина, Лейла; Робшоу, Мэтью (ред.). «Ох-а-а… совсем немного»: небольшое количество побочного канала может иметь большое значение (PDF) . Криптографическое оборудование и встроенные системы – CHES 2014. Конспекты лекций по информатике. Том. 8731. Спрингер. стр. 72–95. дои : 10.1007/978-3-662-44709-3_5 . ISBN 978-3-662-44708-6 .

[5] Монтгомери, Питер Л. (1987). «Ускорение методов факторизации Полларда и эллиптических кривых» . Математика. Комп. 48 (177): 243–264. дои : 10.2307/2007888 . JSTOR 2007888 . МР 0866113 .

[6] Яром, Юваль; Бенгер, Наоми (2014). «Восстановление одноразовых номеров OpenSSL ECDSA с использованием атаки по побочному каналу кэша FLUSH+RELOAD» . Архив электронной печати криптологии IACR .

[7] Рэй, Дастин. «Е521» . Проверено 25 февраля 2023 г.

[8] Бернштейн, Дэниел Дж. «Curve25519: Новые рекорды скорости Диффи-Хеллмана» . В: Юнг М., Додис Ю., Киайас А., Малкин Т. (ред.) Криптография с открытым ключом - PKC 2006. Конспект лекций по информатике, том 3958. Springer, Берлин, Гейдельберг.

[9] Омассон, Жан-Филипп. «Руководство по программному обеспечению низкоуровневой криптографии» . Гитхаб . Проверено 26 марта 2024 г.

[djbmont-10] Перейти обратно: Перейти обратно: ^а ^б Бернштейн, Дэниел Дж.; Ланге, Таня. «Кривые Монтгомери и лестница Монтгомери» . В книге Джоппе В. Боса и Арьена К. Ленстры, редакторов, «Темы вычислительной теории чисел», вдохновленные Питером Л. Монтгомери, страницы 82–115. Издательство Кембриджского университета, 2017.

[costellomont-11] Перейти обратно: Перейти обратно: ^а ^б Костелло, Крейг; Смит, Бенджамин. «Кривые Монтгомери и их арифметика — случай больших характеристических полей» . Дж. Криптографическая инженерия, 8 (3): 227–240, 2018.

[12] Нат, Кошик; Саркар, Палаш. «Лестница Монтгомери в постоянное время» . Архив криптологии ePrint, статья 2020/956.

[13] Бернштейн, Дэниел Дж.; Дуиф, Нильс; Ланге, Таня; Швабе, Питер; Ян, Бо Инь. «Высокоскоростные подписи с высокой степенью защиты» . Журнал «Криптографическая инженерия», 2(2):77–89, 2012.

[14] Бернштейн, Дэниел Дж. «qhasm: инструменты, помогающие писать высокоскоростное программное обеспечение» .

[precompute-15] Перейти обратно: Перейти обратно: ^а ^б Оливейра, Томаз; Лопес, Хулио; Хисил, Хусейн; Фас-Эрнандес, Армандо; Родригес-Энрикес, Франциско. «Как (предварительно) вычислить лестницу: улучшение производительности X25519 и X448» . Карлайл Адамс и Ян Камениш, редакторы, «Выбранные области криптографии - SAC 2017 - 24-я международная конференция», Оттава, Онтарио, Канада, 16–18 августа 2017 г., Пересмотренные избранные статьи, том 10719 конспектов лекций по информатике, страницы 172– 191. Springer, 2017. Код доступен по адресу https://github.com/armfazh/rfc7748_precomputed .

[knpsjec2022-16] Перейти обратно: Перейти обратно: ^а ^б Нат, Кошик; Саркар, Палаш. «Компромисс безопасности и эффективности для эллиптической кривой Диффи-Хеллмана на 128- и 224-битных уровнях безопасности» . J Cryptogr Eng 12, 107–121 (2022). , Код доступен по адресу https://github.com/kn-cs/x25519.

[17] Чжоу, Тунг. «Sandy2x: Новые рекорды скорости Curve25519» . Орр Данкельман и Лиам Келихер, редакторы, «Выбранные области криптографии – SAC 2015 – 22-я Международная конференция», Саквилл, Северная Каролина, Канада, 12–14 августа 2015 г., Пересмотренные избранные статьи, том 9566 конспектов лекций по информатике, страницы 145–160. Springer, 2015. Код доступен по адресу https://tungchou.github.io/sandy2x/.

[fazacmtoms-18] Перейти обратно: Перейти обратно: ^а ^б Фас-Эрнандес, Армандо; Лопес, Хулио; Дахаб, Рикардо. «Высокопроизводительная реализация криптографии на основе эллиптических кривых с использованием векторных инструкций» . АКМ Транс. Математика. Softw., 45(3):25:1–25:35, 2019. , Coce доступно по адресу https://github.com/armfazh/fld-ecc-vec.

[19] Хисил, Хусейн; Эгриче, Беркан; Ясси, Мерт. «Быстрая четырехсторонняя векторизованная лестница для полного набора кривых Монтгомери» . Международный журнал науки информационной безопасности, Vol. 11, № 2, стр. 12-24. , Код доступен по адресу https://github.com/crypto-ninjaturtles/montgomery4x.

[knpsieeetc2022-20] Перейти обратно: Перейти обратно: ^а ^б ^с Нат, Кошик; Саркар, Палаш. «Эффективная четырехсторонняя векторизация лестницы Монтгомери» . Транзакции IEEE на компьютерах, том. 71, нет. 3, стр. 712–723, 1 марта 2022 г. , код доступен по адресу https://github.com/kn-cs/vec-ladder.

[21] Бернштейн, Дэниел Дж.; Швабе, Питер. «НЕОН криптография» . Эммануэль Пруфф и Патрик Шаумон, редакторы, Криптографическое оборудование и встроенные системы - CHES 2012 - 14-й международный семинар, Левен, Бельгия, 9–12 сентября 2012 г. Материалы, том 7428 конспектов лекций по информатике, страницы 320–339. Спрингер, 2012.

[22] Леннгрен, Эмиль. «Оптимизированная реализация AArch64 для X25519» (PDF) . Гитхаб.

[23] Нат, Кошик; Бернштейн, Дэниел Дж . «lib25519» .

[24] Харрисон, Джон Р. «s2n-bignum» .

[25] Бернштейн, Дэниел Дж.; Чичанок, Чуэнсатиансуп; Таня, Ланге. «Curve41417: Возвращение к Карацубе» . В: Батина Л., Робшоу М. (ред.) Криптографическое оборудование и встроенные системы – CHES 2014. CHES 2014. Конспекты лекций по информатике, том 8731. Springer, Berlin, Heidelberg.

[26] Нат, Кошик; Саркар, Палаш. «Эффективное вычисление Диффи-Хеллмана по эллиптической кривой на 256-битном уровне безопасности» . IET Information Security, 14(6):633640, 2020. Код доступен по адресу https://github.com/kn-cs/mont256-dh и https://github.com/kn-cs/mont256-vec.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]