1%% -*- mode: erlang; tab-width: 4; indent-tabs-mode: 1; st-rulers: [70] -*- 2%% vim: ts=4 sw=4 ft=erlang noet 3%%%------------------------------------------------------------------- 4%%% @author Andrew Bennett <potatosaladx@gmail.com> 5%%% @copyright 2014-2016, Andrew Bennett 6%%% @doc Edwards-curve Digital Signature Algorithm (EdDSA) - Ed25519 7%%% See https://tools.ietf.org/html/draft-irtf-cfrg-eddsa 8%%% @end 9%%% Created : 06 Jan 2016 by Andrew Bennett <potatosaladx@gmail.com> 10%%%------------------------------------------------------------------- 11-module(jose_jwa_ed25519). 12 13%% API 14-export([xrecover/1]). 15-export([encode_point/1]). 16-export([decode_point/1]). 17-export([edwards_add/2]). 18-export([edwards_double/1]). 19-export([edwards_equal/2]). 20-export([scalarmult/2]). 21-export([scalarmult_base/1]). 22-export([normalize_point/1]). 23-export([secret/0]). 24-export([secret_to_curve25519/1]). 25-export([secret_to_pk/1]). 26-export([keypair/0]). 27-export([keypair/1]). 28-export([sk_to_secret/1]). 29-export([sk_to_pk/1]). 30-export([sk_to_curve25519/1]). 31-export([pk_to_curve25519/1]). 32-export([sign/2]). 33-export([sign_with_prehash/2]). 34-export([verify/3]). 35-export([verify_with_prehash/3]). 36 37%% Macros 38-define(math, jose_jwa_math). 39-define(inv(Z), ?math:expmod(Z, ?p - 2, ?p)). % $= z^{-1} \mod p$, for z != 0 40% 3. EdDSA Algorithm - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-3 41% 5.1. Ed25519ph and Ed25519 - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-01#section-5.1 42-define(d, -4513249062541557337682894930092624173785641285191125241628941591882900924598840740). % (-121665) * ?inv(121666) 43-define(I, 19681161376707505956807079304988542015446066515923890162744021073123829784752). % ?math:expmod(2, (?p - 1) div 4, ?p) 44%% 1. An odd prime power p. EdDSA uses an elliptic curve over the 45%% finite field GF(p). 46-define(p, 57896044618658097711785492504343953926634992332820282019728792003956564819949). % ?math:intpow(2, 255) - 19 47%% 2. An integer b with 2^(b-1) > p. EdDSA public keys have exactly b 48%% bits, and EdDSA signatures have exactly 2*b bits. b is 49%% recommended to be multiple of 8, so public key and signature 50%% lengths are integral number of octets. 51-define(b, 256). % ?math:intpow(2, ?b - 1) > ?p 52%% 3. A (b-1)-bit encoding of elements of the finite field GF(p). 53-define(GFp, << 54 16#ED,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF, 55 16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF, 56 16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF, 57 16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FF,16#FE 58>>). % << ?p:(?b - 1)/unsigned-little-integer-unit:1, 0:1 >> 59%% 4. A cryptographic hash function H producing 2*b-bit output. 60%% Conservative hash functions are recommended and do not have much 61%% impact on the total cost of EdDSA. 62-define(H(M), crypto:hash(sha512, M)). 63-define(HBits, 512). % ?b * 2 64%% 5. An integer c that is 2 or 3. Secret EdDSA scalars are multiples 65%% of 2^c. The integer c is the base-2 logarithm of the so called 66%% cofactor. 67-define(c, 3). 68%% 6. An integer n with c <= n < b. Secret EdDSA scalars have exactly 69%% n + 1 bits, with the top bit (the 2^n position) always set and 70%% the bottom c bits always cleared. 71-define(n, 254). % ?c =< ?n andalso ?n < ?b 72%% 7. A nonzero square element a of GF(p). The usual recommendation 73%% for best performance is a = -1 if p mod 4 = 1, and a = 1 if p 74%% mod 4 = 3. 75-define(a, -1). 76%% 8. An element B != (0,1) of the set E = { (x,y) is a member of 77%% GF(p) x GF(p) such that a * x^2 + y^2 = 1 + d * x^2 * y^2 }. 78-define(By, 46316835694926478169428394003475163141307993866256225615783033603165251855960). % 4 * ?inv(5) 79-define(Bx, 15112221349535400772501151409588531511454012693041857206046113283949847762202). % xrecover(?By) 80-define(B, {?Bx, ?By, 1, 46827403850823179245072216630277197565144205554125654976674165829533817101731}). % {?Bx, ?By, 1, (?Bx * ?Bx) rem ?p} 81% (?a * ?math:intpow(?Bx, 2) + ?math:intpow(?By, 2)) rem ?p == (1 + ?d * ?math:intpow(?Bx, 2) * ?math:intpow(?By, 2)) rem ?p 82%% 9. An odd prime l such that [l]B = 0 and 2^c * l = #E. The number 83%% #E (the number of points on the curve) is part of the standard 84%% data provided for an elliptic curve E. 85-define(l, 7237005577332262213973186563042994240857116359379907606001950938285454250989). % ?math:intpow(2, 252) + 27742317777372353535851937790883648493 86-define(E, ?math:intpow(2, ?c) * ?l). 87%% 10. A "prehash" function PH. PureEdDSA means EdDSA where PH is the 88%% identity function, i.e., PH(M) = M. HashEdDSA means EdDSA where 89%% PH generates a short output, no matter how long the message is; 90%% for example, PH(M) = SHA-512(M). 91-define(PH(M), crypto:hash(sha512, M)). 92 93-define(secretbytes, 32). % (?b + 7) div 8 94-define(publickeybytes, 32). % (?b + 7) div 8 95-define(secretkeybytes, 64). % ?secretbytes + ?publickeybytes 96 97%%==================================================================== 98%% API 99%%==================================================================== 100 101% 5.1.1. Modular arithmetic - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.1 102 103xrecover(Y) -> 104 YY = Y * Y, 105 A = (YY - 1) * ?inv((?d * YY) + 1), 106 X = ?math:expmod(A, (?p + 3) div 8, ?p), 107 case ((X * X) - A) rem ?p =:= 0 of 108 true -> % x^2 = a (mod p). Then x is a square root. 109 case X rem 2 of 110 0 -> 111 X; 112 _ -> 113 ?p - X 114 end; 115 false -> 116 case ((X * X) + A) rem ?p =:= 0 of 117 true -> % x^2 = -a (mod p). Then 2^((p-1)/4) x is a square root. 118 Xi = (X * ?I) rem ?p, 119 case Xi rem 2 of 120 0 -> 121 Xi; 122 _ -> 123 ?p - Xi 124 end; 125 false -> % a is not a square modulo p. 126 erlang:error(badarg) 127 end 128 end. 129 130% 5.1.2. Encoding - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.2 131 132encode_point({X, Y, Z, _T}) -> 133 Zi = ?inv(Z), 134 Xp = ?math:mod((X * Zi), ?p), 135 Yp = ?math:mod((Y * Zi), ?p), 136 << YpHead:(?b - 8)/bitstring, YpTail:8/integer >> = << Yp:?b/unsigned-little-integer-unit:1 >>, 137 << YpHead/bitstring, (YpTail bxor (16#80 * (Xp band 1))):8/integer >>. 138 139% 5.1.3. Decoding - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.3 140 141decode_point(<< YpHead:(?b - 8)/bitstring, Xb:1, YpTail:7/bitstring >>) -> 142 << Yp:?b/unsigned-little-integer-unit:1 >> = << YpHead/bitstring, 0:1, YpTail/bitstring >>, 143 case Yp >= ?p of 144 true -> 145 erlang:error(badarg); 146 false -> 147 Xp = xrecover(Yp), 148 X = case Xp band 1 of 149 Xb -> 150 Xp; 151 _ -> 152 ?p - Xp 153 end, 154 {X, Yp, 1, (X * Yp) rem ?p} 155 end. 156 157% 5.1.4. Point addition - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.4 158 159edwards_add({X1, Y1, Z1, T1}, {X2, Y2, Z2, T2}) -> 160 A = ((Y1 - X1) * (Y2 - X2)) rem ?p, 161 B = ((Y1 + X1) * (Y2 + X2)) rem ?p, 162 C = (T1 * 2 * ?d * T2) rem ?p, 163 D = (Z1 * 2 * Z2) rem ?p, 164 E = B - A, 165 F = D - C, 166 G = D + C, 167 H = B + A, 168 X3 = E * F, 169 Y3 = G * H, 170 T3 = E * H, 171 Z3 = F * G, 172 {X3 rem ?p, Y3 rem ?p, Z3 rem ?p, T3 rem ?p}. 173 174edwards_double(P) -> 175 edwards_add(P, P). 176 177edwards_equal({X1, Y1, Z1, _T1}, {X2, Y2, Z2, _T2}) -> 178 Z1i = ?inv(Z1), 179 X1p = ?math:mod((X1 * Z1i), ?p), 180 Y1p = ?math:mod((Y1 * Z1i), ?p), 181 Z2i = ?inv(Z2), 182 X2p = ?math:mod((X2 * Z2i), ?p), 183 Y2p = ?math:mod((Y2 * Z2i), ?p), 184 {X1p, Y1p} =:= {X2p, Y2p}. 185 186scalarmult(_P, 0) -> 187 {0, 1, 1, 0}; 188scalarmult(P, E) -> 189 Q = scalarmult(P, E div 2), 190 QQ = edwards_double(Q), 191 case E band 1 of 192 0 -> 193 QQ; 194 1 -> 195 edwards_add(QQ, P) 196 end. 197 198scalarmult_base(E) -> 199 scalarmult(?B, E). 200 201normalize_point({X, Y, Z, _T}) -> 202 Zi = ?inv(Z), 203 Xp = ?math:mod((X * Zi), ?p), 204 Yp = ?math:mod((Y * Zi), ?p), 205 Zp = ?math:mod((Z * Zi), ?p), 206 {Xp, Yp, Zp, ?math:mod((Xp * Yp), ?p)}. 207 208% 5.1.5. Key Generation - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.5 209 210secret() -> 211 crypto:strong_rand_bytes(?secretbytes). 212 213secret_to_curve25519(Secret = << _:?secretbytes/binary >>) -> 214 << HHead0:8/integer, HBody:30/binary, HFoot0:8/integer, _/binary >> = ?H(Secret), 215 HHead = HHead0 band 248, 216 HFoot = (HFoot0 band 63) bor 64, 217 << HHead:8/integer, HBody/binary, HFoot:8/integer >>. 218 219secret_to_pk(Secret = << _:?secretbytes/binary >>) -> 220 << As:?b/unsigned-little-integer-unit:1 >> = secret_to_curve25519(Secret), 221 A = scalarmult(?B, As), 222 encode_point(A). 223 224keypair() -> 225 Secret = secret(), 226 keypair(Secret). 227 228keypair(Secret = << _:?secretbytes/binary >>) -> 229 PK = secret_to_pk(Secret), 230 SK = << Secret/binary, PK/binary >>, 231 {PK, SK}. 232 233sk_to_secret(<< Secret:?secretbytes/binary, _:?publickeybytes/binary >>) -> 234 Secret. 235 236sk_to_pk(<< _:?secretbytes/binary, PK:?publickeybytes/binary >>) -> 237 PK. 238 239sk_to_curve25519(<< Secret:?secretbytes/binary, _:?publickeybytes/binary >>) -> 240 secret_to_curve25519(Secret). 241 242pk_to_curve25519(<< PK:?publickeybytes/binary >>) -> 243 _A = {_X, Y, _Z, _T} = decode_point(PK), 244 U = ?math:mod((1 + Y) * ?inv(1 - Y), ?p), 245 << U:?b/unsigned-little-integer-unit:1 >>. 246 247% 5.1.6. Sign - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.6 248 249sign(M, << Secret:?secretbytes/binary, PK:?publickeybytes/binary >>) when is_binary(M) -> 250 << HHead0:8/integer, HBody:30/binary, HFoot0:8/integer, HTail:32/binary >> = ?H(Secret), 251 HHead = HHead0 band 248, 252 HFoot = (HFoot0 band 63) bor 64, 253 << As:?b/unsigned-little-integer-unit:1 >> = << HHead:8/integer, HBody/binary, HFoot:8/integer >>, 254 << Rs:?HBits/unsigned-little-integer-unit:1 >> = ?H(<< HTail/binary, M/binary >>), 255 R = encode_point(scalarmult(?B, Rs)), 256 << K:?HBits/unsigned-little-integer-unit:1 >> = ?H(<< R/binary, PK/binary, M/binary >>), 257 S = ?math:mod(Rs + (K * As), ?l), 258 << R/binary, S:?b/unsigned-little-integer-unit:1 >>. 259 260sign_with_prehash(M, SK = << _:?secretkeybytes/binary >>) when is_binary(M) -> 261 sign(?PH(M), SK). 262 263% 5.1.7. Verify - https://tools.ietf.org/html/draft-irtf-cfrg-eddsa#section-5.1.7 264 265verify(<< R:?b/bitstring, S:?b/unsigned-little-integer-unit:1 >>, M, PK = << _:?publickeybytes/binary >>) when is_binary(M) -> 266 A = decode_point(PK), 267 << K:?HBits/unsigned-little-integer-unit:1 >> = ?H(<< R/binary, PK/binary, M/binary >>), 268 edwards_equal(scalarmult(?B, S), edwards_add(decode_point(R), scalarmult(A, K))); 269verify(Sig, M, << _:?publickeybytes/binary >>) when is_binary(Sig) andalso is_binary(M) -> 270 false. 271 272verify_with_prehash(Sig, M, PK = << _:?publickeybytes/binary >>) when is_binary(Sig) andalso is_binary(M) -> 273 verify(Sig, ?PH(M), PK). 274