Skip to content

Instantly share code, notes, and snippets.

@jackhftang
Last active February 8, 2019 02:21
Show Gist options
  • Save jackhftang/a3ce77d57d3990fc0f9ca7221809c060 to your computer and use it in GitHub Desktop.
Save jackhftang/a3ce77d57d3990fc0f9ca7221809c060 to your computer and use it in GitHub Desktop.
A memory-reduced version of scalarmult(), marginally be able to run on arduino uno (2K bytes memroy). Original [tweetnacl](https://tweetnacl.cr.yp.to/20140427/tweetnacl.c)
#define FOR(i, n) for (i = 0;i < n;++i)
#define sv static void
typedef unsigned char u8;
typedef unsigned long u32;
typedef unsigned long long u64;
typedef long long i64;
typedef i64 gf[16]; // 1024-bit = 128 bytes
static const gf _121665 = {0xDB41, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int crypto_verify_32(const u8 *x, const u8 *y) {
int i = 0;
u32 d = 0;
FOR(i, 32) d |= x[i] ^ y[i];
return (1 & ((d - 1) >> 8)) - 1;
}
sv car25519(gf o) {
i64 i, c;
FOR(i, 16) {
o[i] += (1LL << 16);
c = o[i] >> 16;
o[(i + 1) * (i < 15)] += c - 1 + 37 * (c - 1) * (i == 15);
o[i] -= c << 16;
}
}
sv sel25519(gf p, gf q, int b) {
int i;
i64 t, c = ~(b - 1);
FOR(i, 16) {
t = c & (p[i] ^ q[i]);
p[i] ^= t;
q[i] ^= t;
}
}
sv pack25519(u8 *o, const gf n) {
int i, j;
i64 b;
gf m, t;
FOR(i, 16) t[i] = n[i];
car25519(t);
car25519(t);
car25519(t);
FOR(j, 2) {
m[0] = t[0] - 0xffed;
for (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);
b = (m[15] >> 16) & 1;
m[14] &= 0xffff;
sel25519(t, m, 1 - b);
}
FOR(i, 16) {
o[2 * i] = t[i] & 0xff;
o[2 * i + 1] = t[i] >> 8;
}
}
sv unpack25519(gf o, const u8 *n) {
int i;
FOR(i, 16) o[i] = n[2 * i] + ((i64) n[2 * i + 1] << 8);
o[15] &= 0x7fff;
}
sv A(gf o, const gf a, const gf b) {
int i;
FOR(i, 16) o[i] = a[i] + b[i];
}
sv Z(gf o, const gf a, const gf b) {
int i;
FOR(i, 16) o[i] = a[i] - b[i];
}
sv M(gf o, const gf a, const gf b) {
int i, j;
gf t;
FOR(i, 16) t[i] = a[0] * b[i];
for (i = 1; i < 16; ++i) {
for (j = 0; j < 16 - i; ++j) t[i + j] += a[i] * b[j];
for (j = 16 - i; j < 16; ++j) t[(i + j) & 15] += 38 * a[i] * b[j];
}
FOR(i, 16) o[i] = t[i];
car25519(o);
car25519(o);
}
sv S(gf o, const gf a) {
M(o, a, a);
}
sv inv25519(gf o, const gf i) {
gf c;
int a;
FOR(a, 16) c[a] = i[a];
for (a = 253; a >= 0; a--) {
S(c, c);
if (a != 2 && a != 4) M(c, c, i);
}
FOR(a, 16) o[a] = c[a];
}
int crypto_scalarmult(u8 *q, const u8 *n, const u8 *p) {
int i, r;
u8 z[32];
gf e, f;
i64 x[80];
i64 *a = x + 16;
i64 *c = x + 32;
i64 *b = x + 48;
i64 *d = x + 64;
FOR(i, 32) z[i] = n[i];
z[31] = (z[31] & 127) | 64;
z[0] &= 248;
unpack25519(x, p);
FOR(i, 16) {
b[i] = x[i];
d[i] = a[i] = c[i] = 0;
}
a[0] = d[0] = 1;
for (i = 254; i >= 0; --i) {
r = (z[i >> 3] >> (i & 7)) & 1;
sel25519(a, b, r);
sel25519(c, d, r);
A(e, a, c);
Z(a, a, c);
A(c, b, d);
Z(b, b, d);
S(d, e);
S(f, a);
M(a, c, a);
M(c, b, e);
A(e, a, c);
Z(a, a, c);
S(b, a);
Z(c, d, f);
M(a, c, _121665);
A(a, a, d);
M(c, c, a);
M(a, d, f);
M(d, b, x);
S(b, e);
sel25519(a, b, r);
sel25519(c, d, r);
}
inv25519(c, c);
M(a, a, c);
pack25519(q, a);
return 0;
}
int crypto_scalarmult_base(u8 *q, u8 *n) {
u8 _9[32] = {
9, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0
};
return crypto_scalarmult(q, n, _9);
}
void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
Serial.println("Starting");
Serial.flush();
}
u8 result[32] = {
178, 68,166, 37,138,219,116,209,
25, 0, 23,147, 69, 3, 5, 58,
172,252, 63,210, 73,204, 90,138,
86, 36,152,124, 75, 98,179, 42
};
u8 n[32] = {
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
};
u8 g[32] = {
9,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0
};
void loop() {
unsigned long start = millis();
Serial.print("n=" + String(n[0]) + " ");
crypto_scalarmult(result, n, g);
for(int i=0; i<32; i++){
Serial.print(String(result[i]) + ",");
}
Serial.println(" time: " + String(millis() - start));
Serial.flush();
n[0] += 8;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment