ed25519ph.erl

-module(ed25519ph).

-export([start/0]).

-export([
    prehash/1,
    prehash_init/0,
    prehash_update/2,
    prehash_final/1,
    sign/3,
    sign_with_prehash/3,
    verify/4,
    verify_with_prehash/4
]).

-record(ed25519ph_prehash_ctx, {
    hash_state = undefined :: undefined | crypto:hash_state()
}).

-define(H(M), crypto:hash(sha512, M)).
-define(p, 57896044618658097711785492504343953926634992332820282019728792003956564819949). % 2^255 - 19
-define(I, 19681161376707505956807079304988542015446066515923890162744021073123829784752). % expmod(2, (?p - 1) div 4, ?p)
-define(d, -4513249062541557337682894930092624173785641285191125241628941591882900924598840740). % (-121665) * ?inv(121666)
-define(inv(Z), expmod(Z, ?p - 2, ?p)). % $= z^{-1} \mod p$, for z != 0
-define(By, 46316835694926478169428394003475163141307993866256225615783033603165251855960). % 4 * ?inv(5)
-define(Bx, 15112221349535400772501151409588531511454012693041857206046113283949847762202). % xrecover(?By)
-define(B, {?Bx, ?By, 1, 46827403850823179245072216630277197565144205554125654976674165829533817101731}). % {?Bx, ?By, 1, (?Bx * ?Bx) rem ?p}
-define(l, 7237005577332262213973186563042994240857116359379907606001950938285454250989). % ?math:intpow(2, 252) + 27742317777372353535851937790883648493

start() ->
    Secret = <<131,63,230,36,9,35,123,157,98,236,119,88,117,32,145,30,154,117,156,236,29,25,117,91,125,169,1,185,109,202,61,66>>,
    Public = <<236,23,43,147,173,94,86,59,244,147,44,112,225,36,80,52,195,84,103,239,46,253,77,100,235,248,25,104,52,103,226,191>>,
    Message = <<"abc">>,
    Signature = <<152,167,2,34,240,184,18,26,169,211,15,129,61,104,63,128,158,70,43,70,156,127,248,118,57,73,155,185,78,109,174,65,49,248,80,66,70,60,42,53,90,32,3,208,98,173,245,170,161,11,140,97,230,54,6,42,170,209,28,42,38,8,52,6>>,
    Context = <<>>,
    Signature = sign(Context, Message, Secret),
    true = verify(Context, Signature, Message, Public),
    io:format("Test Vector passed!~n", []),
    erlang:halt(0).

prehash(M) when is_binary(M) ->
    crypto:hash(sha512, M).

prehash_init() ->
    #ed25519ph_prehash_ctx{hash_state = crypto:hash_init(sha512)}.

prehash_update(#ed25519ph_prehash_ctx{hash_state = HashState}, M) when is_binary(M) ->
    #ed25519ph_prehash_ctx{hash_state = crypto:hash_update(HashState, M)}.

prehash_final(#ed25519ph_prehash_ctx{hash_state = HashState}) ->
    crypto:hash_final(HashState).

sign(C, M, Secret) when is_binary(C) andalso is_binary(M) andalso bit_size(Secret) =:= 256 ->
    sign_with_prehash(C, prehash(M), Secret).

sign_with_prehash(C, PrehashCtx = #ed25519ph_prehash_ctx{}, Secret) when is_binary(C) andalso bit_size(Secret) =:= 256 ->
    sign_with_prehash(C, prehash_final(PrehashCtx), Secret);
sign_with_prehash(C, PH, Secret) when is_binary(C) andalso bit_size(PH) =:= 512 andalso bit_size(Secret) =:= 256 ->
    Dom2 = dom2(1, C),
    << HHead0:8/integer, HBody:30/binary, HFoot0:8/integer, Prefix:32/binary >> = ?H(Secret),
    HHead = HHead0 band 248,
    HFoot = (HFoot0 band 63) bor 64,
    << As:256/unsigned-little-integer-unit:1 >> = << HHead:8/integer, HBody/binary, HFoot:8/integer >>,
    A = edwards_scalarmult_base(As),
    << Rs:512/unsigned-little-integer-unit:1 >> = ?H([Dom2, Prefix, PH]),
    R = edwards_scalarmult_base(Rs),
    << K:512/unsigned-little-integer-unit:1 >> = ?H([Dom2, R, A, PH]),
    S = mod(Rs + (mod(K, ?l) * As), ?l),
    << R/binary, S:256/unsigned-little-integer-unit:1 >>.

verify(C, Signature, M, Public) when is_binary(C) andalso bit_size(Signature) =:= 512 andalso is_binary(M) andalso bit_size(Public) =:= 256 ->
    verify_with_prehash(C, Signature, prehash(M), Public).

verify_with_prehash(C, Signature, PrehashCtx = #ed25519ph_prehash_ctx{}, Public) when is_binary(C) andalso bit_size(Signature) =:= 512 andalso bit_size(Public) =:= 256 ->
    verify_with_prehash(C, Signature, prehash_final(PrehashCtx), Public);
verify_with_prehash(C, Signature, PH, Public) when is_binary(C) andalso bit_size(Signature) =:= 512 andalso bit_size(PH) =:= 512 andalso bit_size(Public) =:= 256 ->
    << R:256/bitstring, S:256/unsigned-little-integer-unit:1 >> = Signature,
    Dom2 = dom2(1, C),
    A = edwards_decode_point(Public),
    << K:512/unsigned-little-integer-unit:1 >> = ?H([Dom2, R, Public, PH]),
    edwards_equal(edwards_scalarmult(?B, S), edwards_add(edwards_decode_point(R), edwards_scalarmult(A, K))).

%% @private
dom2(X, Y) when is_integer(X) andalso X >= 0 andalso X =< 255 andalso is_binary(Y) andalso byte_size(Y) =< 255 ->
    YLen = byte_size(Y),
    <<
        "SigEd25519 no Ed25519 collisions",
        X:8/unsigned-integer,
        YLen:8/unsigned-integer,
        Y:YLen/binary
    >>.

%% Ed25519 Operations

edwards_xrecover(Y) ->
    YY = Y * Y,
    A = (YY - 1) * ?inv((?d * YY) + 1),
    X = expmod(A, (?p + 3) div 8, ?p),
    case ((X * X) - A) rem ?p =:= 0 of
        true -> % x^2 = a (mod p).  Then x is a square root.
            case X rem 2 of
                0 ->
                    X;
                _ ->
                    ?p - X
            end;
        false ->
            case ((X * X) + A) rem ?p =:= 0 of
                true -> % x^2 = -a (mod p).  Then 2^((p-1)/4) x is a square root.
                    Xi = (X * ?I) rem ?p,
                    case Xi rem 2 of
                        0 ->
                            Xi;
                        _ ->
                            ?p - Xi
                    end;
                false -> % a is not a square modulo p.
                    erlang:error(badarg)
            end
    end.

%% @private
edwards_add({X1, Y1, Z1, T1}, {X2, Y2, Z2, T2}) ->
    A = ((Y1 - X1) * (Y2 - X2)) rem ?p,
    B = ((Y1 + X1) * (Y2 + X2)) rem ?p,
    C = (T1 * 2 * ?d * T2) rem ?p,
    D = (Z1 * 2 * Z2) rem ?p,
    E = B - A,
    F = D - C,
    G = D + C,
    H = B + A,
    X3 = E * F,
    Y3 = G * H,
    T3 = E * H,
    Z3 = F * G,
    {X3 rem ?p, Y3 rem ?p, Z3 rem ?p, T3 rem ?p}.

%% @private
edwards_double(P) ->
    edwards_add(P, P).

%% @private
edwards_equal({X1, Y1, Z1, _T1}, {X2, Y2, Z2, _T2}) ->
    Z1i = ?inv(Z1),
    X1p = mod((X1 * Z1i), ?p),
    Y1p = mod((Y1 * Z1i), ?p),
    Z2i = ?inv(Z2),
    X2p = mod((X2 * Z2i), ?p),
    Y2p = mod((Y2 * Z2i), ?p),
    {X1p, Y1p} =:= {X2p, Y2p}.

%% @private
edwards_decode_point(<< YpHead:(256 - 8)/bitstring, Xb:1, YpTail:7/bitstring >>) ->
    << Yp:256/unsigned-little-integer-unit:1 >> = << YpHead/bitstring, 0:1, YpTail/bitstring >>,
    case Yp >= ?p of
        true ->
            erlang:error(badarg);
        false ->
            Xp = edwards_xrecover(Yp),
            X = case Xp band 1 of
                Xb ->
                    Xp;
                _ ->
                    ?p - Xp
            end,
            {X, Yp, 1, (X * Yp) rem ?p}
    end.

%% @private
edwards_encode_point({X, Y, Z, _T}) ->
    Zi = ?inv(Z),
    Xp = mod((X * Zi), ?p),
    Yp = mod((Y * Zi), ?p),
    << YpHead:(256 - 8)/bitstring, YpTail:8/integer >> = << Yp:256/unsigned-little-integer-unit:1 >>,
    << YpHead/bitstring, (YpTail bxor (16#80 * (Xp band 1))):8/integer >>.

%% @private
edwards_scalarmult(_P, 0) ->
    {0, 1, 1, 0};
edwards_scalarmult(P, E) ->
    Q = edwards_scalarmult(P, E div 2),
    QQ = edwards_double(Q),
    case E band 1 of
        0 ->
            QQ;
        1 ->
            edwards_add(QQ, P)
    end.

%% @private
edwards_scalarmult_base(E) when is_integer(E) ->
    edwards_encode_point(edwards_scalarmult(?B, E)).

    % MX = x25519_scalarmult_base(E),
    % mx2ey(MX).

% %% @private
% x25519_scalarmult_base(K) when bit_size(K) =:= 256 ->
%     {R, _} = crypto:generate_key(eddh, x25519, K),
%     R.

% %% @private
% mx2ey(<<MX:256/unsigned-little-integer-unit:1>>) ->
%     N0 = MX + 1,
%     D0 = ?inv(N0),
%     N1 = MX - 1,
%     EY = mod(N1 * D0, ?p),
%     <<EY::256/unsigned-little-integer-unit:1>>.

    % A = X bsr 16,
    % B = X band 16#FFFF,
    % C = Y bsr 16,
    % D = Y band 16#FFFF,
    % DB = D * B,
    % DA = D * A,
    % CB = C * B,
    % (DB + ((DA + CB) bsl 16)) band 16#FFFFFFFF.

%% Math

% @private
expmod(B, E, M) ->
    expmod_fast(B, E, M).

% @private
expmod_fast(B, E, M) ->
    (exprem_fast(B, E, M) + M) rem M.

% @private
exprem_fast(B, E, M) when B < 0 andalso E rem 2 =/= 0 ->
    -exprem_fast(abs(B), E, M);
exprem_fast(B, E, M) when B < 0 ->
    exprem_fast(abs(B), E, M);
exprem_fast(B, E, M) ->
    crypto:bytes_to_integer(crypto:mod_pow(B, E, M)).

% @private
mod(B, M) ->
    (B rem M + M) rem M.