Ця курва

Тут покажемо як працює підпис 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 @secp256k1Oid {1, 3, 132, 0, 10} @secp256k1name :secp256k1 @prime256v1 {1, 2, 840, 10045, 3, 1, 7} @prime256v1name :prime256v1 def getCurveByOid(oid) do case oid do @secp256k1Oid -> secp256k1() @prime256v1 -> prime256v1() end end def getCurveByName(name) do case name do @secp256k1name -> secp256k1() @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: @secp256k1Oid } 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 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 require CA.ECDSA.OTP def numberFromString(data) do Base.encode16(data) |> Integer.parse(16) |> (fn {parsedInt, ""} -> parsedInt end).() end def sign(message, privateKey, options \\ []) do %{hashfunc: hashfunc} = Enum.into(options, %{hashfunc: :sha256}) number = :crypto.hash(hashfunc, message) |> numberFromString() curve = CA.KnownCurves.secp256k1() 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: :erlang.element(2,X509.PrivateKey.from_pem(bin)) def public(bin), do: :public_key.pem_entry_decode(hd(:public_key.pem_decode(bin))) def verify(file, signature, pub) do {:ok, msg} = :file.read_file file {:ok, pem} = :file.read_file pub verify(msg, CA.ECDSA.OTP.signature(signature), 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.secp256k1() 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.

OpenSSL ECC Sign/Verify

> CA.CSR.ca > CA.CSR.csr "m2" > CA.CSR.client "m2"
# export client=m2 # openssl dgst -sha256 -sign $client.key mix.exs > mix.sig
# export client=m2 # openssl dgst -sha256 -verify $client.pub -signature mix.sig mix.exs

˙


˙