defmodule Ed25519 do
import Bitwise
@moduledoc """
Ed25519 signature functions
This is mostly suitable as part of a pure Elixir solution.
## Configuration
*No configuration is needed* in most cases. However, if needed, a custom hash
function can be configured. As per the specification - `sha512` is the default.
`config/config.exs`
import Config
# The hash function will be invoked as 'Blake2.hash2b(payload, 16)'
config :ed25519,
hash_fn: {Blake2, :hash2b, [], [16]}
# The hash function will be invoked as ':crypto.hash(:sha256, payload)'
config :ed25519,
hash_fn: {:crypto, :hash, [:sha256], []}
"""
@typedoc """
public or secret key
"""
@type key :: binary
@typedoc """
computed signature
"""
@type signature :: binary
@p 57_896_044_618_658_097_711_785_492_504_343_953_926_634_992_332_820_282_019_728_792_003_956_564_819_949
@l 7_237_005_577_332_262_213_973_186_563_042_994_240_857_116_359_379_907_606_001_950_938_285_454_250_989
@d -4_513_249_062_541_557_337_682_894_930_092_624_173_785_641_285_191_125_241_628_941_591_882_900_924_598_840_740
@i 19_681_161_376_707_505_956_807_079_304_988_542_015_446_066_515_923_890_162_744_021_073_123_829_784_752
@t254 28_948_022_309_329_048_855_892_746_252_171_976_963_317_496_166_410_141_009_864_396_001_978_282_409_984
@base {15_112_221_349_535_400_772_501_151_409_588_531_511_454_012_693_041_857_206_046_113_283_949_847_762_202,
46_316_835_694_926_478_169_428_394_003_475_163_141_307_993_866_256_225_615_783_033_603_165_251_855_960}
defp xrecover(y) do
xx = (y * y - 1) * inv(@d * y * y + 1)
x = expmod(xx, div(@p + 3, 8), @p)
x =
case (x * x - xx) |> mod(@p) do
0 -> x
_ -> mod(x * @i, @p)
end
case x |> mod(2) do
0 -> @p - x
_ -> x
end
end
defp mod(x, _y) when x == 0, do: 0
defp mod(x, y) when x > 0, do: rem(x, y)
defp mod(x, y) when x < 0, do: rem(y + rem(x, y), y)
# __using__ Macro generates the hash function at compile time, which allows the
# hashing function to be configurable without runtime overhead
use Ed25519.Hash
defp hashint(m), do: m |> hash |> :binary.decode_unsigned(:little)
# :crypto.mod_pow chokes on negative inputs, so we feed it positive values
# only and patch up the result if necessary
defp expmod(_b, 0, _m), do: 1
defp expmod(b, e, m) when b > 0 do
b |> :crypto.mod_pow(e, m) |> :binary.decode_unsigned()
end
defp expmod(b, e, m) do
i = b |> abs() |> :crypto.mod_pow(e, m) |> :binary.decode_unsigned()
cond do
mod(e, 2) == 0 -> i
i == 0 -> i
true -> m - i
end
end
defp inv(x), do: x |> expmod(@p - 2, @p)
defp edwards({x1, y1}, {x2, y2}) do
x = (x1 * y2 + x2 * y1) * inv(1 + @d * x1 * x2 * y1 * y2)
y = (y1 * y2 + x1 * x2) * inv(1 - @d * x1 * x2 * y1 * y2)
{mod(x, @p), mod(y, @p)}
end
defp encodepoint({x, y}) do
val =
y
|> band(0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
|> bor((x &&& 1) <<< 255)
<<val::little-size(256)>>
end
defp decodepoint(<<n::little-size(256)>>) do
xc = n |> bsr(255)
y = n |> band(0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
x = xrecover(y)
point =
case x &&& 1 do
^xc -> {x, y}
_ -> {@p - x, y}
end
if isoncurve(point), do: point, else: raise("Point off Edwards curve")
end
defp decodepoint(_), do: raise("Provided value not a key")
defp isoncurve({x, y}), do: (-x * x + y * y - 1 - @d * x * x * y * y) |> mod(@p) == 0
@doc """
Returns whether a given `key` lies on the ed25519 curve.
"""
@spec on_curve?(key) :: boolean
def on_curve?(key) do
try do
decodepoint(key)
true
rescue
_error -> false
end
end
@doc """
Sign a message
If only the secret key is provided, the public key will be derived therefrom.
This adds significant overhead.
"""
@spec signature(binary, key, key) :: signature
def signature(m, sk, pk \\ nil)
def signature(m, sk, nil), do: signature(m, sk, derive_public_key(sk))
def signature(m, sk, pk) do
h = hash(sk)
a = a_from_hash(h)
r = hashint(:binary.part(h, 32, 32) <> m)
bigr = r |> scalarmult(@base) |> encodepoint
s = mod(r + hashint(bigr <> pk <> m) * a, @l)
bigr <> <<s::little-size(256)>>
end
defp a_from_hash(<<h::little-size(256), _rest::binary>>) do
@t254 +
(h
|> band(0xF3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8))
end
defp scalarmult(0, _pair), do: {0, 1}
defp scalarmult(e, p) do
q = e |> div(2) |> scalarmult(p)
q = edwards(q, q)
case e &&& 1 do
1 -> edwards(q, p)
_ -> q
end
end
defp clamp(c) do
c
|> band(~~~7)
|> band(~~~(128 <<< (8 * 31)))
|> bor(64 <<< (8 * 31))
end
@doc """
validate a signed message
"""
@spec valid_signature?(signature, binary, key) :: boolean
def valid_signature?(<<for_r::binary-size(32), s::little-size(256)>>, m, pk)
when byte_size(pk) == 32 do
r = decodepoint(for_r)
a = decodepoint(pk)
h = hashint(encodepoint(r) <> pk <> m)
scalarmult(s, @base) == edwards(r, scalarmult(h, a))
end
def valid_signature?(_s, _m_, _pk), do: false
@doc """
Generate a secret/public key pair
Returned tuple contains `{random_secret_key, derived_public_key}`
"""
@spec generate_key_pair :: {key, key}
def generate_key_pair do
secret = :crypto.strong_rand_bytes(32)
{secret, derive_public_key(secret)}
end
@doc """
Generate a secret/public key pair from supplied secret
Returned tuple contains `{secret_key, derived_public_key}`
"""
@spec generate_key_pair(key) :: {key, key}
def generate_key_pair(secret) do
{secret, derive_public_key(secret)}
end
@doc """
derive the public signing key from the secret key
"""
@spec derive_public_key(key) :: key
def derive_public_key(sk) do
sk
|> hash
|> a_from_hash
|> scalarmult(@base)
|> encodepoint
end
@doc """
Derive the x25519/curve25519 encryption key from the ed25519 signing key
By converting an `EdwardsPoint` on the Edwards model to the corresponding `MontgomeryPoint` on the Montgomery model
Handles either `:secret` or `:public` keys as indicated in the call
May `raise` on an invalid input key or unknown atom
See: https://blog.filippo.io/using-ed25519-keys-for-encryption
"""
@spec to_curve25519(key, atom) :: key
def to_curve25519(key, which)
def to_curve25519(ed_public_key, :public) do
{_, y} = decodepoint(ed_public_key)
u = mod((1 + y) * inv(1 - y), @p)
<<u::little-size(256)>>
end
def to_curve25519(ed_secret_key, :secret) do
<<digest32::little-size(256), _::binary-size(32)>> = :crypto.hash(:sha512, ed_secret_key)
<<clamp(digest32)::little-size(256)>>
end
end
