Free, open-source 3D sculpting for Linux, macOS and Windows: dense meshes, remeshing, painting, built-in AI (image/text to 3D), Send to Unreal, game-ready LODs, Gaussian splats and OpenUSD.
C++ 3d3d-sculptingcppdear-imguidigital-sculptingfbxgame-developmentgaussian-splattinggltfimage-to-3dmcpopenglopenusdsculptingtext-to-3dunreal-engine
// SculptForge - open source digital sculpting
// SPDX-License-Identifier: GPL-3.0-or-later
#include "core/Ed25519.h"
#include <cstring>
#include <vector>
namespace sf {
namespace {
// --- SHA-512 (FIPS 180-4) ---
constexpr uint64_t kRound[80] = {
0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL, 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
0xd807aa98a3030242ULL, 0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL, 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL, 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL, 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
0xd192e819d6ef5218ULL, 0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL, 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL, 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL,
};
constexpr uint64_t rotr(uint64_t x, int n) { return (x >> n) | (x << (64 - n)); }
void compress(uint64_t h[8], const uint8_t* block) {
uint64_t w[80];
for (int i = 0; i < 16; ++i) {
w[i] = 0;
for (int k = 0; k < 8; ++k) w[i] = w[i] << 8 | block[i * 8 + k];
}
for (int i = 16; i < 80; ++i) {
const uint64_t s0 = rotr(w[i - 15], 1) ^ rotr(w[i - 15], 8) ^ (w[i - 15] >> 7);
const uint64_t s1 = rotr(w[i - 2], 19) ^ rotr(w[i - 2], 61) ^ (w[i - 2] >> 6);
w[i] = w[i - 16] + s0 + w[i - 7] + s1;
}
uint64_t a = h[0], b = h[1], c = h[2], d = h[3], e = h[4], f = h[5], g = h[6], hh = h[7];
for (int i = 0; i < 80; ++i) {
const uint64_t t1 = hh + (rotr(e, 14) ^ rotr(e, 18) ^ rotr(e, 41)) + ((e & f) ^ (~e & g)) + kRound[i] + w[i];
const uint64_t t2 = (rotr(a, 28) ^ rotr(a, 34) ^ rotr(a, 39)) + ((a & b) ^ (a & c) ^ (b & c));
hh = g, g = f, f = e, e = d + t1, d = c, c = b, b = a, a = t1 + t2;
}
h[0] += a, h[1] += b, h[2] += c, h[3] += d, h[4] += e, h[5] += f, h[6] += g, h[7] += hh;
}
// --- GF(2^255 - 19): 16 limbs of 16 bits (TweetNaCl) ---
using i64 = long long;
using gf = i64[16];
constexpr gf gf0 = {0}, gf1 = {1};
constexpr gf D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070,
0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203}; // -121665/121666
constexpr gf D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0,
0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406}; // 2d
constexpr gf X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c,
0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169}; // the base point
constexpr gf Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666};
constexpr gf I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43,
0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83}; // sqrt(-1)
void set(gf r, const gf a) { std::memcpy(r, a, sizeof(gf)); }
void carry(gf o) {
for (int i = 0; i < 16; ++i) {
o[i] += i64(1) << 16;
const i64 c = o[i] >> 16;
o[(i + 1) * (i < 15)] += c - 1 + 37 * (c - 1) * (i == 15);
o[i] -= c * (i64(1) << 16);
}
}
void select(gf p, gf q, int b) {
const i64 c = ~(i64(b) - 1);
for (int i = 0; i < 16; ++i) {
const i64 t = c & (p[i] ^ q[i]);
p[i] ^= t, q[i] ^= t;
}
}
void pack(uint8_t* o, const gf n) {
gf m, t;
set(t, n);
carry(t), carry(t), carry(t);
for (int j = 0; j < 2; ++j) {
m[0] = t[0] - 0xffed;
for (int i = 1; i < 15; ++i) {
m[i] = t[i] - 0xffff - ((m[i - 1] >> 16) & 1);
m[i - 1] &= 0xffff;
}
m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1);
const int b = int((m[15] >> 16) & 1);
m[14] &= 0xffff;
select(t, m, 1 - b);
}
for (int i = 0; i < 16; ++i) o[2 * i] = uint8_t(t[i] & 0xff), o[2 * i + 1] = uint8_t(t[i] >> 8);
}
bool differ(const gf a, const gf b) {
uint8_t c[32], d[32];
pack(c, a), pack(d, b);
return std::memcmp(c, d, 32) != 0;
}
int parity(const gf a) {
uint8_t d[32];
pack(d, a);
return d[0] & 1;
}
void unpack(gf o, const uint8_t* n) {
for (int i = 0; i < 16; ++i) o[i] = n[2 * i] + (i64(n[2 * i + 1]) << 8);
o[15] &= 0x7fff;
}
void add(gf o, const gf a, const gf b) { for (int i = 0; i < 16; ++i) o[i] = a[i] + b[i]; }
void sub(gf o, const gf a, const gf b) { for (int i = 0; i < 16; ++i) o[i] = a[i] - b[i]; }
void mul(gf o, const gf a, const gf b) {
i64 t[31] = {};
for (int i = 0; i < 16; ++i)
for (int j = 0; j < 16; ++j) t[i + j] += a[i] * b[j];
for (int i = 0; i < 15; ++i) t[i] += 38 * t[i + 16];
for (int i = 0; i < 16; ++i) o[i] = t[i];
carry(o), carry(o);
}
void square(gf o, const gf a) { mul(o, a, a); }
void invert(gf o, const gf in) {
gf c;
set(c, in);
for (int a = 253; a >= 0; --a) {
square(c, c);
if (a != 2 && a != 4) mul(c, c, in);
}
set(o, c);
}
void pow2523(gf o, const gf in) {
gf c;
set(c, in);
for (int a = 250; a >= 0; --a) {
square(c, c);
if (a != 1) mul(c, c, in);
}
set(o, c);
}
// --- The curve, in extended coordinates (X, Y, Z, T) ---
void addPoint(gf p[4], gf q[4]) {
gf a, b, c, d, t, e, f, g, h;
sub(a, p[1], p[0]), sub(t, q[1], q[0]), mul(a, a, t);
add(b, p[0], p[1]), add(t, q[0], q[1]), mul(b, b, t);
mul(c, p[3], q[3]), mul(c, c, D2);
mul(d, p[2], q[2]), add(d, d, d);
sub(e, b, a), sub(f, d, c), add(g, d, c), add(h, b, a);
mul(p[0], e, f), mul(p[1], h, g), mul(p[2], g, f), mul(p[3], e, h);
}
void swapPoints(gf p[4], gf q[4], int b) { for (int i = 0; i < 4; ++i) select(p[i], q[i], b); }
void packPoint(uint8_t* r, gf p[4]) {
gf tx, ty, zi;
invert(zi, p[2]);
mul(tx, p[0], zi), mul(ty, p[1], zi);
pack(r, ty);
r[31] ^= uint8_t(parity(tx) << 7);
}
void scalarMult(gf p[4], gf q[4], const uint8_t* s) {
set(p[0], gf0), set(p[1], gf1), set(p[2], gf1), set(p[3], gf0);
for (int i = 255; i >= 0; --i) {
const int b = (s[i / 8] >> (i & 7)) & 1;
swapPoints(p, q, b);
addPoint(q, p);
addPoint(p, p);
swapPoints(p, q, b);
}
}
void scalarBase(gf p[4], const uint8_t* s) {
gf q[4];
set(q[0], X), set(q[1], Y), set(q[2], gf1), mul(q[3], X, Y);
scalarMult(p, q, s);
}
// The group order L = 2^252 + 27742317777372353535851937790883648493, little-endian.
constexpr i64 L[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10};
void modL(uint8_t* r, i64 x[64]) {
for (int i = 63; i >= 32; --i) {
i64 c = 0;
int j = i - 32;
for (; j < i - 12; ++j) {
x[j] += c - 16 * x[i] * L[j - (i - 32)];
c = (x[j] + 128) >> 8;
x[j] -= c * 256;
}
x[j] += c;
x[i] = 0;
}
i64 c = 0;
for (int j = 0; j < 32; ++j) {
x[j] += c - (x[31] >> 4) * L[j];
c = x[j] >> 8;
x[j] &= 255;
}
for (int j = 0; j < 32; ++j) x[j] -= c * L[j];
for (int i = 0; i < 32; ++i) {
x[i + 1] += x[i] >> 8;
r[i] = uint8_t(x[i] & 255);
}
}
void reduce(uint8_t* r) { // 64 bytes in, mod L in the first 32
i64 x[64];
for (int i = 0; i < 64; ++i) x[i] = i64(r[i]);
std::memset(r, 0, 64);
modL(r, x);
}
// -A from its 32-byte encoding; false when it isn't a point.
bool unpackNegated(gf r[4], const uint8_t p[32]) {
gf t, chk, num, den, den2, den4, den6;
set(r[2], gf1);
unpack(r[1], p);
square(num, r[1]);
mul(den, num, D);
sub(num, num, r[2]);
add(den, r[2], den);
square(den2, den), square(den4, den2), mul(den6, den4, den2);
mul(t, den6, num), mul(t, t, den);
pow2523(t, t);
mul(t, t, num), mul(t, t, den), mul(t, t, den);
mul(r[0], t, den);
square(chk, r[0]), mul(chk, chk, den);
if (differ(chk, num)) mul(r[0], r[0], I);
square(chk, r[0]), mul(chk, chk, den);
if (differ(chk, num)) return false;
if (parity(r[0]) == (p[31] >> 7)) sub(r[0], gf0, r[0]);
mul(r[3], r[0], r[1]);
return true;
}
// S < L (RFC 8032 5.1.7: a larger S would let one signature be rewritten into others).
bool belowOrder(const uint8_t s[32]) {
for (int i = 31; i >= 0; --i)
if (s[i] != L[i]) return s[i] < L[i];
return false;
}
} // namespace
void sha512(const void* data, size_t size, uint8_t out[64]) {
uint64_t h[8] = {0x6a09e667f3bcc908ULL, 0xbb67ae8584caa73bULL, 0x3c6ef372fe94f82bULL, 0xa54ff53a5f1d36f1ULL,
0x510e527fade682d1ULL, 0x9b05688c2b3e6c1fULL, 0x1f83d9abfb41bd6bULL, 0x5be0cd19137e2179ULL};
const auto* bytes = static_cast<const uint8_t*>(data);
size_t i = 0;
for (; i + 128 <= size; i += 128) compress(h, bytes + i);
// Final block(s): the remaining bytes, 0x80, zeros, then the 128-bit bit length (big-endian).
uint8_t tail[256] = {};
const size_t rest = size - i;
std::memcpy(tail, bytes + i, rest);
tail[rest] = 0x80;
const size_t tailLen = rest < 112 ? 128 : 256;
const uint64_t bits = uint64_t(size) * 8;
for (int k = 0; k < 8; ++k) tail[tailLen - 1 - k] = uint8_t(bits >> (8 * k));
tail[tailLen - 9] = uint8_t(uint64_t(size) >> 61);
compress(h, tail);
if (tailLen == 256) compress(h, tail + 128);
for (int w = 0; w < 8; ++w)
for (int k = 0; k < 8; ++k) out[w * 8 + k] = uint8_t(h[w] >> (56 - 8 * k));
}
bool ed25519PublicKeyValid(const uint8_t publicKey[32]) {
gf q[4];
return unpackNegated(q, publicKey);
}
bool ed25519Verify(const uint8_t signature[64], const void* message, size_t size, const uint8_t publicKey[32]) {
gf p[4], q[4];
if (!belowOrder(signature + 32) || !unpackNegated(q, publicKey)) return false;
// h = SHA-512(R || A || M) mod L; the signature holds when [S]B - [h]A encodes to R.
std::vector<uint8_t> m(64 + size);
std::memcpy(m.data(), signature, 32);
std::memcpy(m.data() + 32, publicKey, 32);
if (size) std::memcpy(m.data() + 64, message, size);
uint8_t h[64], t[32];
sha512(m.data(), m.size(), h);
reduce(h);
scalarMult(p, q, h);
scalarBase(q, signature + 32);
addPoint(p, q);
packPoint(t, p);
uint8_t diff = 0; // (constant time, though nothing here is secret)
for (int i = 0; i < 32; ++i) diff |= uint8_t(t[i] ^ signature[i]);
return diff == 0;
}
} // namespace sf