Last active
February 8, 2019 02:21
-
-
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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