2023-08-05 CA CURVE

Ця курва

Тут покажемо як працює підпис ECDSA на рівні операцій над точкою, що знаходиться на еліптичній кривій, та операціями додавання та множення які рухать точку по цій кривій.

Точка на лінії

Для початку визнається точка на площині в координатах Якобі.


defmodule CA.Point do
  defstruct [:x, :y, z: 0]
  def isAtInfinity?(p) do p.y == 0 end
end

Та функція визначення належності точки до геометричного місця точок кривої (локуса).


defmodule CA.Curve do
  @moduledoc false
  require CA.Integer
  require CA.Point
  defstruct [:A, :B, :P, :N, :G, :name, :oid]
  def contains?(curve, p) do
      cond do
        p.x < 0 || p.x > curve."P" - 1 -> false
        p.y < 0 || p.y > curve."P" - 1 -> false
        CA.Integer.ipow(p.y, 2) - (CA.Integer.ipow(p.x, 3)
          + curve."A" * p.x + curve."B")
          |> CA.Integer.modulo(curve."P") != 0 -> false
        true -> true
      end
  end
  def getLength(curve) do
      div(1 + String.length(Integer.to_string(curve."N", 16)), 2)
  end
end

Множення в координатах Якобі

Алгоритм бінарного множення в координатах Якобі.


defmodule CA.Jacobian do
  require CA.Integer
  require CA.Point
  @moduledoc false

  def toJacobian(p), do: %CA.Point{x: p.x, y: p.y, z: 1}
  def fromJacobian(p, cP) do
      z = inv(p.z, cP)
      %CA.Point{
        x: CA.Integer.modulo(p.x * CA.Integer.ipow(z, 2), cP),
        y: CA.Integer.modulo(p.y * CA.Integer.ipow(z, 3), cP)
      }
  end

  def multiply(p, n, cN, cA, cP), do:
      p |> toJacobian()
        |> jacobianMultiply(n, cN, cA, cP)
        |> fromJacobian(cP)
  def add(p, q, cA, cP), do:
      jacobianAdd(toJacobian(p), toJacobian(q), cA, cP)
        |> fromJacobian(cP)
  def inv(x, _) when x == 0, do: 0
  def inv(x, n), do:
      invOperator(1, 0, CA.Integer.modulo(x, n), n)
        |> CA.Integer.modulo(n)
  def invOperator(lm, hm, low, high) when low > 1 do
      r = div(high, low)
      invOperator(hm - lm * r, lm, high - low * r, low) end
  def invOperator(lm, _, _, _), do: lm

  def jacobianDouble(p, cA, cP) do
      if p.y == 0 do
         %CA.Point{x: 0, y: 0, z: 0}
      else
        ysq = CA.Integer.ipow(p.y, 2) |> CA.Integer.modulo(cP)
        s = (4 * p.x * ysq) |> CA.Integer.modulo(cP)
        m = (3 * CA.Integer.ipow(p.x, 2) + cA * CA.Integer.ipow(p.z, 4))
          |> CA.Integer.modulo(cP)
        nx = (CA.Integer.ipow(m, 2) - 2 * s) |> CA.Integer.modulo(cP)
        ny = (m * (s - nx) - 8 * CA.Integer.ipow(ysq, 2))
          |> CA.Integer.modulo(cP)
        nz = (2 * p.y * p.z) |> CA.Integer.modulo(cP)
        %CA.Point{x: nx, y: ny, z: nz}
      end
  end

  def jacobianAdd(p, q, cA, cP) do
      if p.y == 0 do
         q
      else
         if q.y == 0 do
            p
         else
           u1 = (p.x * CA.Integer.ipow(q.z, 2)) |> CA.Integer.modulo(cP)
           u2 = (q.x * CA.Integer.ipow(p.z, 2)) |> CA.Integer.modulo(cP)
           s1 = (p.y * CA.Integer.ipow(q.z, 3)) |> CA.Integer.modulo(cP)
           s2 = (q.y * CA.Integer.ipow(p.z, 3)) |> CA.Integer.modulo(cP)

           if u1 == u2 do
             if s1 != s2 do
                %CA.Point{x: 0, y: 0, z: 1}
             else
               jacobianDouble(p, cA, cP)
             end
           else
             h = u2 - u1
             r = s2 - s1
             h2 = (h * h) |> CA.Integer.modulo(cP)
             h3 = (h * h2) |> CA.Integer.modulo(cP)
             u1h2 = (u1 * h2) |> CA.Integer.modulo(cP)
             nx = (CA.Integer.ipow(r, 2) - h3 - 2 * u1h2) |> CA.Integer.modulo(cP)
             ny = (r * (u1h2 - nx) - s1 * h3) |> CA.Integer.modulo(cP)
             nz = (h * p.z * q.z) |> CA.Integer.modulo(cP)
             %CA.Point{x: nx, y: ny, z: nz}
           end
         end
       end
  end

  def jacobianMultiply(_p, n, _cN, _cA, _cP) when n == 0, do:
      %CA.Point{x: 0, y: 0, z: 1}
  def jacobianMultiply(p, n, _cN, _cA, _cP) when n == 1 do
      case p.y do
           0 -> %CA.Point{x: 0, y: 0, z: 1}
           _ -> p
      end
  end
  def jacobianMultiply(p, n, cN, cA, cP) when n < 0 or n >= cN do
      case p.y do
           0 -> %CA.Point{x: 0, y: 0, z: 1}
           _ -> jacobianMultiply(p, CA.Integer.modulo(n, cN), cN, cA, cP)
      end
  end
  def jacobianMultiply(p, _n, _cN, _cA, _cP) when p.y == 0, do:
      %CA.Point{x: 0, y: 0, z: 1}
  def jacobianMultiply(p, n, cN, cA, cP) when rem(n, 2) == 0 do
      jacobianMultiply(p, div(n, 2), cN, cA, cP) |> jacobianDouble(cA, cP)
  end
  def jacobianMultiply(p, n, cN, cA, cP) do
      jacobianMultiply(p, div(n, 2), cN, cA, cP)
      |> jacobianDouble(cA, cP) |> jacobianAdd(p, cA, cP)
  end

end

Параметри курв

Параметри кривих ідентифікуються атомом та/або OID, та визначають точки А, Б, Засіювання, Точка на кривій, Порядок, Кофактор.


defmodule CA.KnownCurves do
  require CA.Curve
  require CA.Point

  @secp384r1 {1, 3, 132, 0, 34}
  @secp256k1 {1, 3, 132, 0, 10}
  @prime256v1 {1, 2, 840, 10045, 3, 1, 7}
  @secp384r1name :secp384r1
  @secp256k1name :secp256k1
  @prime256v1name :prime256v1

  def getCurveByOid(oid) do
    case oid do
      @secp256k1 -> secp256k1()
      @secp384r1 -> secp384r1()
      @prime256v1 -> prime256v1()
    end
  end

  def getCurveByName(name) do
    case name do
      @secp256k1name -> secp256k1()
      @secp384r1name -> secp384r1()
      @prime256v1name -> prime256v1()
    end
  end

  def secp256k1() do
    %CA.Curve{
      name: @secp256k1name,
      A: 0x0000000000000000000000000000000000000000000000000000000000000000,
      B: 0x0000000000000000000000000000000000000000000000000000000000000007,
      P: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
      N: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
      G: %CA.Point{
        x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
        y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
      },
      oid: @secp256k1
    }
  end

  def prime256v1() do
    %CA.Curve{
      name: @prime256v1name,
      A: 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC,
      B: 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B,
      P: 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF,
      N: 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551,
      G: %CA.Point{
        x: 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
        y: 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
      },
      oid: @prime256v1
    }
  end

  def secp384r1() do
    %CA.Curve{
      name: @secp384r1name,
      A: 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc,
      B: 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef,
      P: 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff,
      N: 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973,
      G: %CA.Point{
        x: 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7,
        y: 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f
      },
      oid: @secp384r1
    }
  end
end

BigNum RND

Алгоритм генерація великого довільного числа, яке береться як координата точки на еліптичній кривій, автоматично визначається її пара, яка утворює точку на прямій, і далі відбуваються подальші криптографічні перетворення.


defmodule CA.Integer do
  @moduledoc false
  import Bitwise

  def modulo(x, n), do: rem(x, n) |> correctNegativeModulo(n)
  def correctNegativeModulo(r, n) when r < 0, do: r + n
  def correctNegativeModulo(r, _n), do: r
  def ipow(base, p, acc \\ 1)
  def ipow(base, p, acc) when p > 0, do: ipow(base, p - 1, base * acc)
  def ipow(_base, _p, acc), do: acc

  def between(minimum, maximum) when minimum < maximum do
      range = maximum - minimum + 1
      {bytesNeeded, mask} = calculateParameters(range)
      randomNumber = :crypto.strong_rand_bytes(bytesNeeded)
                  |> :binary.bin_to_list()
                  |> bytesToNumber &&& mask

      if randomNumber < range do
         minimum + randomNumber
      else
         between(minimum, maximum)
      end
  end

  def bytesToNumber(randomBytes, randomNumber \\ 0, i \\ 0)
  def bytesToNumber([randomByte | otherRandomBytes], randomNumber, i), do:
      bytesToNumber(otherRandomBytes, randomNumber ||| randomByte <<< (8 * i), i + 1)
  def bytesToNumber([], randomNumber, _i), do: randomNumber

  def calculateParameters(range), do: calculateParameters(range, 1, 0)
  def calculateParameters(range, mask, bitsNeeded) when range > 0, do:
      calculateParameters(range >>> 1, mask <<< 1 ||| 1, bitsNeeded + 1)
  def calculateParameters(_range, mask, bitsNeeded), do:
      {div(bitsNeeded, 8) + 1, mask}

end

ECDSA

Обчислення r та s для криптографічного підпису.


defmodule CA.ECDSA do
  require CA.Point
  require CA.Integer
  require CA.Jacobian
  @moduledoc "CA/ECDSA ECC Signature (SYNRC)."

  def sign(message, privateKey, options) do
      %{hashfunc: hashfunc} = Enum.into(options, %{hashfunc: :sha256})
      number = :crypto.hash(hashfunc, message) |> numberFromString()
      curve = CA.KnownCurves.secp384r1()
      randNum = CA.Integer.between(1, curve."N" - 1)
      r = CA.Jacobian.multiply(curve."G", randNum, curve."N", curve."A", curve."P").x
        |> CA.Integer.modulo(curve."N")
      s = ((number + r * privateKey) * CA.Jacobian.inv(randNum, curve."N"))
        |> CA.Integer.modulo(curve."N")
      {r, s}
  end

  def private(bin), do: numberFromString(:erlang.element(3,:erlang.element(2,X509.PrivateKey.from_pem(bin))))
  def public(bin),  do: :public_key.pem_entry_decode(hd(:public_key.pem_decode(bin)))

  def numberFromString(string) do
      Base.encode16(string)
      |> Integer.parse(16)
      |> (fn {parsedInt, ""} -> parsedInt end).()
  end

  def decodePointFromECPoint(ec) do
      {{:ECPoint, raw}, {:namedCurve, oid}} = ec
      bin = :binary.part(raw,1,:erlang.size(raw)-1)
      curve = CA.KnownCurves.getCurveByOid(oid)
      baseLength = CA.Curve.getLength(curve)
      xs = :binary.part(bin, 0, baseLength)
      ys = :binary.part(bin, baseLength, :erlang.size(bin) - baseLength)
      %CA.Point{ x: numberFromString(xs), y: numberFromString(ys)}
  end

  def signature(name) do
      {:ok, sig} = :file.read_file name
      {{_,[{_,r},{_,s}]},""} = :asn1rt_nif.decode_ber_tlv sig
      { :ca_enroll.decode_integer(r),
        :ca_enroll.decode_integer(s) }
  end

  def sign(file, key) do
      {:ok, msg} = :file.read_file file
      {:ok, pem} = :file.read_file key
      sign(msg, private(pem), [])
  end

  def verify(file, signature_file, pub) do
      {:ok, msg} = :file.read_file file
      {:ok, pem} = :file.read_file pub
      verify(msg, signature(signature_file), decodePointFromECPoint(public(pem)), [])
  end

  def verify(message, {r,s}, publicKey, options) do
      %{hashfunc: hashfunc} = Enum.into(options, %{hashfunc: :sha256})
      number = :crypto.hash(hashfunc, message) |> numberFromString()
      curve = CA.KnownCurves.secp384r1()
      inv = CA.Jacobian.inv(s, curve."N")
      v = CA.Jacobian.add(
        CA.Jacobian.multiply(curve."G", CA.Integer.modulo(number * inv, curve."N"),
           curve."N", curve."A", curve."P"),
        CA.Jacobian.multiply(publicKey, CA.Integer.modulo(r * inv, curve."N"),
           curve."N", curve."A", curve."P" ), curve."A", curve."P")
      cond do
        r < 1 || r >= curve."N" -> false
        s < 1 || s >= curve."N" -> false
        CA.Point.isAtInfinity?(v) -> false
        CA.Integer.modulo(v.x, curve."N") != r -> false
        true -> true
      end
  end
end

Висновки

Промислової якості криптографічні перетворення з використанням бібліотеки великих цілих чисел GMP вбудованої в віртуальну машину Erlang вміщаються в 250 LOC та всього в декілька разів повільніше OpenSSL імплементації на мові C.

SYNRC ECC Sign/Verify Elixir


> CA.CSR.ca
> CA.CSR.csr          "maxim"
> CA.CSR.client       "maxim"
> CA.ECDSA.sign       "mix.exs", "maxim.key"
> CA.ECDSA.OTP.sign   "mix.exs", "maxim.key"
> CA.ECDSA.verify     "mix.exs", "mix.sig", "maxim.pub"
> CA.ECDSA.OTP.verify "mix.exs", "mix.sig", "maxim.pub"

Для додаткової самоперевірки в середовищі Erlang/OTP ми скористалися стандартним додатком CRYPTO. Так виглядає природній ECDSA підпис на платформі Ericsson Open Telecom Platform, який імплементований в модулі CA.ECDSA.OTP:


  def signBin(msg, priv) do
      CA."ECPrivateKey"(privateKey: point, parameters: {:namedCurve, oid}) = priv
      :crypto.sign(:ecdsa, :sha256, msg,
          [point, :crypto.ec_curve(:pubkey_cert_records.namedCurves(oid))])
  end

  def verifyBin(msg, sig, pub) do
      {CA."ECPoint"(point: point), {:namedCurve, oid}} = pub
      :crypto.verify(:ecdsa, :sha256, msg, sig,
          [point, :crypto.ec_curve(:pubkey_cert_records.namedCurves(oid))])
  end

OpenSSL ECC Sign/Verify C

Для самоперевірки з найпоширенішими промисловими імплементаціями ECDSA ми використали OpenSSL:


# export client=maxim
# openssl dgst -sha256 -sign $client.key mix.exs > mix.sig


# export client=maxim
# openssl x509 -pubkey -noout -in $client.pem > $client.pub
# openssl dgst -sha256 -verify $client.pub -signature mix.sig mix.exs