1261287Sdes/* $OpenBSD: sc25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */ 2261287Sdes 3261287Sdes/* 4261287Sdes * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange, 5261287Sdes * Peter Schwabe, Bo-Yin Yang. 6261287Sdes * Copied from supercop-20130419/crypto_sign/ed25519/ref/sc25519.c 7261287Sdes */ 8261287Sdes 9261287Sdes#include "includes.h" 10261287Sdes 11261287Sdes#include "sc25519.h" 12261287Sdes 13261287Sdes/*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */ 14261287Sdes 15261287Sdesstatic const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14, 16261287Sdes 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10}; 17261287Sdes 18261287Sdesstatic const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21, 19261287Sdes 0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F}; 20261287Sdes 21261287Sdesstatic crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ 22261287Sdes{ 23261287Sdes unsigned int x = a; 24261287Sdes x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */ 25261287Sdes x >>= 31; /* 0: no; 1: yes */ 26261287Sdes return x; 27261287Sdes} 28261287Sdes 29261287Sdes/* Reduce coefficients of r before calling reduce_add_sub */ 30261287Sdesstatic void reduce_add_sub(sc25519 *r) 31261287Sdes{ 32261287Sdes crypto_uint32 pb = 0; 33261287Sdes crypto_uint32 b; 34261287Sdes crypto_uint32 mask; 35261287Sdes int i; 36261287Sdes unsigned char t[32]; 37261287Sdes 38261287Sdes for(i=0;i<32;i++) 39261287Sdes { 40261287Sdes pb += m[i]; 41261287Sdes b = lt(r->v[i],pb); 42261287Sdes t[i] = r->v[i]-pb+(b<<8); 43261287Sdes pb = b; 44261287Sdes } 45261287Sdes mask = b - 1; 46261287Sdes for(i=0;i<32;i++) 47261287Sdes r->v[i] ^= mask & (r->v[i] ^ t[i]); 48261287Sdes} 49261287Sdes 50261287Sdes/* Reduce coefficients of x before calling barrett_reduce */ 51261287Sdesstatic void barrett_reduce(sc25519 *r, const crypto_uint32 x[64]) 52261287Sdes{ 53261287Sdes /* See HAC, Alg. 14.42 */ 54261287Sdes int i,j; 55261287Sdes crypto_uint32 q2[66]; 56261287Sdes crypto_uint32 *q3 = q2 + 33; 57261287Sdes crypto_uint32 r1[33]; 58261287Sdes crypto_uint32 r2[33]; 59261287Sdes crypto_uint32 carry; 60261287Sdes crypto_uint32 pb = 0; 61261287Sdes crypto_uint32 b; 62261287Sdes 63261287Sdes for (i = 0;i < 66;++i) q2[i] = 0; 64261287Sdes for (i = 0;i < 33;++i) r2[i] = 0; 65261287Sdes 66261287Sdes for(i=0;i<33;i++) 67261287Sdes for(j=0;j<33;j++) 68261287Sdes if(i+j >= 31) q2[i+j] += mu[i]*x[j+31]; 69261287Sdes carry = q2[31] >> 8; 70261287Sdes q2[32] += carry; 71261287Sdes carry = q2[32] >> 8; 72261287Sdes q2[33] += carry; 73261287Sdes 74261287Sdes for(i=0;i<33;i++)r1[i] = x[i]; 75261287Sdes for(i=0;i<32;i++) 76261287Sdes for(j=0;j<33;j++) 77261287Sdes if(i+j < 33) r2[i+j] += m[i]*q3[j]; 78261287Sdes 79261287Sdes for(i=0;i<32;i++) 80261287Sdes { 81261287Sdes carry = r2[i] >> 8; 82261287Sdes r2[i+1] += carry; 83261287Sdes r2[i] &= 0xff; 84261287Sdes } 85261287Sdes 86261287Sdes for(i=0;i<32;i++) 87261287Sdes { 88261287Sdes pb += r2[i]; 89261287Sdes b = lt(r1[i],pb); 90261287Sdes r->v[i] = r1[i]-pb+(b<<8); 91261287Sdes pb = b; 92261287Sdes } 93261287Sdes 94261287Sdes /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3 95261287Sdes * If so: Handle it here! 96261287Sdes */ 97261287Sdes 98261287Sdes reduce_add_sub(r); 99261287Sdes reduce_add_sub(r); 100261287Sdes} 101261287Sdes 102261287Sdesvoid sc25519_from32bytes(sc25519 *r, const unsigned char x[32]) 103261287Sdes{ 104261287Sdes int i; 105261287Sdes crypto_uint32 t[64]; 106261287Sdes for(i=0;i<32;i++) t[i] = x[i]; 107261287Sdes for(i=32;i<64;++i) t[i] = 0; 108261287Sdes barrett_reduce(r, t); 109261287Sdes} 110261287Sdes 111261287Sdesvoid shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16]) 112261287Sdes{ 113261287Sdes int i; 114261287Sdes for(i=0;i<16;i++) r->v[i] = x[i]; 115261287Sdes} 116261287Sdes 117261287Sdesvoid sc25519_from64bytes(sc25519 *r, const unsigned char x[64]) 118261287Sdes{ 119261287Sdes int i; 120261287Sdes crypto_uint32 t[64]; 121261287Sdes for(i=0;i<64;i++) t[i] = x[i]; 122261287Sdes barrett_reduce(r, t); 123261287Sdes} 124261287Sdes 125261287Sdesvoid sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x) 126261287Sdes{ 127261287Sdes int i; 128261287Sdes for(i=0;i<16;i++) 129261287Sdes r->v[i] = x->v[i]; 130261287Sdes for(i=0;i<16;i++) 131261287Sdes r->v[16+i] = 0; 132261287Sdes} 133261287Sdes 134261287Sdesvoid sc25519_to32bytes(unsigned char r[32], const sc25519 *x) 135261287Sdes{ 136261287Sdes int i; 137261287Sdes for(i=0;i<32;i++) r[i] = x->v[i]; 138261287Sdes} 139261287Sdes 140261287Sdesint sc25519_iszero_vartime(const sc25519 *x) 141261287Sdes{ 142261287Sdes int i; 143261287Sdes for(i=0;i<32;i++) 144261287Sdes if(x->v[i] != 0) return 0; 145261287Sdes return 1; 146261287Sdes} 147261287Sdes 148261287Sdesint sc25519_isshort_vartime(const sc25519 *x) 149261287Sdes{ 150261287Sdes int i; 151261287Sdes for(i=31;i>15;i--) 152261287Sdes if(x->v[i] != 0) return 0; 153261287Sdes return 1; 154261287Sdes} 155261287Sdes 156261287Sdesint sc25519_lt_vartime(const sc25519 *x, const sc25519 *y) 157261287Sdes{ 158261287Sdes int i; 159261287Sdes for(i=31;i>=0;i--) 160261287Sdes { 161261287Sdes if(x->v[i] < y->v[i]) return 1; 162261287Sdes if(x->v[i] > y->v[i]) return 0; 163261287Sdes } 164261287Sdes return 0; 165261287Sdes} 166261287Sdes 167261287Sdesvoid sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y) 168261287Sdes{ 169261287Sdes int i, carry; 170261287Sdes for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; 171261287Sdes for(i=0;i<31;i++) 172261287Sdes { 173261287Sdes carry = r->v[i] >> 8; 174261287Sdes r->v[i+1] += carry; 175261287Sdes r->v[i] &= 0xff; 176261287Sdes } 177261287Sdes reduce_add_sub(r); 178261287Sdes} 179261287Sdes 180261287Sdesvoid sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y) 181261287Sdes{ 182261287Sdes crypto_uint32 b = 0; 183261287Sdes crypto_uint32 t; 184261287Sdes int i; 185261287Sdes for(i=0;i<32;i++) 186261287Sdes { 187261287Sdes t = x->v[i] - y->v[i] - b; 188261287Sdes r->v[i] = t & 255; 189261287Sdes b = (t >> 8) & 1; 190261287Sdes } 191261287Sdes} 192261287Sdes 193261287Sdesvoid sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y) 194261287Sdes{ 195261287Sdes int i,j,carry; 196261287Sdes crypto_uint32 t[64]; 197261287Sdes for(i=0;i<64;i++)t[i] = 0; 198261287Sdes 199261287Sdes for(i=0;i<32;i++) 200261287Sdes for(j=0;j<32;j++) 201261287Sdes t[i+j] += x->v[i] * y->v[j]; 202261287Sdes 203261287Sdes /* Reduce coefficients */ 204261287Sdes for(i=0;i<63;i++) 205261287Sdes { 206261287Sdes carry = t[i] >> 8; 207261287Sdes t[i+1] += carry; 208261287Sdes t[i] &= 0xff; 209261287Sdes } 210261287Sdes 211261287Sdes barrett_reduce(r, t); 212261287Sdes} 213261287Sdes 214261287Sdesvoid sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y) 215261287Sdes{ 216261287Sdes sc25519 t; 217261287Sdes sc25519_from_shortsc(&t, y); 218261287Sdes sc25519_mul(r, x, &t); 219261287Sdes} 220261287Sdes 221261287Sdesvoid sc25519_window3(signed char r[85], const sc25519 *s) 222261287Sdes{ 223261287Sdes char carry; 224261287Sdes int i; 225261287Sdes for(i=0;i<10;i++) 226261287Sdes { 227261287Sdes r[8*i+0] = s->v[3*i+0] & 7; 228261287Sdes r[8*i+1] = (s->v[3*i+0] >> 3) & 7; 229261287Sdes r[8*i+2] = (s->v[3*i+0] >> 6) & 7; 230261287Sdes r[8*i+2] ^= (s->v[3*i+1] << 2) & 7; 231261287Sdes r[8*i+3] = (s->v[3*i+1] >> 1) & 7; 232261287Sdes r[8*i+4] = (s->v[3*i+1] >> 4) & 7; 233261287Sdes r[8*i+5] = (s->v[3*i+1] >> 7) & 7; 234261287Sdes r[8*i+5] ^= (s->v[3*i+2] << 1) & 7; 235261287Sdes r[8*i+6] = (s->v[3*i+2] >> 2) & 7; 236261287Sdes r[8*i+7] = (s->v[3*i+2] >> 5) & 7; 237261287Sdes } 238261287Sdes r[8*i+0] = s->v[3*i+0] & 7; 239261287Sdes r[8*i+1] = (s->v[3*i+0] >> 3) & 7; 240261287Sdes r[8*i+2] = (s->v[3*i+0] >> 6) & 7; 241261287Sdes r[8*i+2] ^= (s->v[3*i+1] << 2) & 7; 242261287Sdes r[8*i+3] = (s->v[3*i+1] >> 1) & 7; 243261287Sdes r[8*i+4] = (s->v[3*i+1] >> 4) & 7; 244261287Sdes 245261287Sdes /* Making it signed */ 246261287Sdes carry = 0; 247261287Sdes for(i=0;i<84;i++) 248261287Sdes { 249261287Sdes r[i] += carry; 250261287Sdes r[i+1] += r[i] >> 3; 251261287Sdes r[i] &= 7; 252261287Sdes carry = r[i] >> 2; 253261287Sdes r[i] -= carry<<3; 254261287Sdes } 255261287Sdes r[84] += carry; 256261287Sdes} 257261287Sdes 258261287Sdesvoid sc25519_window5(signed char r[51], const sc25519 *s) 259261287Sdes{ 260261287Sdes char carry; 261261287Sdes int i; 262261287Sdes for(i=0;i<6;i++) 263261287Sdes { 264261287Sdes r[8*i+0] = s->v[5*i+0] & 31; 265261287Sdes r[8*i+1] = (s->v[5*i+0] >> 5) & 31; 266261287Sdes r[8*i+1] ^= (s->v[5*i+1] << 3) & 31; 267261287Sdes r[8*i+2] = (s->v[5*i+1] >> 2) & 31; 268261287Sdes r[8*i+3] = (s->v[5*i+1] >> 7) & 31; 269261287Sdes r[8*i+3] ^= (s->v[5*i+2] << 1) & 31; 270261287Sdes r[8*i+4] = (s->v[5*i+2] >> 4) & 31; 271261287Sdes r[8*i+4] ^= (s->v[5*i+3] << 4) & 31; 272261287Sdes r[8*i+5] = (s->v[5*i+3] >> 1) & 31; 273261287Sdes r[8*i+6] = (s->v[5*i+3] >> 6) & 31; 274261287Sdes r[8*i+6] ^= (s->v[5*i+4] << 2) & 31; 275261287Sdes r[8*i+7] = (s->v[5*i+4] >> 3) & 31; 276261287Sdes } 277261287Sdes r[8*i+0] = s->v[5*i+0] & 31; 278261287Sdes r[8*i+1] = (s->v[5*i+0] >> 5) & 31; 279261287Sdes r[8*i+1] ^= (s->v[5*i+1] << 3) & 31; 280261287Sdes r[8*i+2] = (s->v[5*i+1] >> 2) & 31; 281261287Sdes 282261287Sdes /* Making it signed */ 283261287Sdes carry = 0; 284261287Sdes for(i=0;i<50;i++) 285261287Sdes { 286261287Sdes r[i] += carry; 287261287Sdes r[i+1] += r[i] >> 5; 288261287Sdes r[i] &= 31; 289261287Sdes carry = r[i] >> 4; 290261287Sdes r[i] -= carry<<5; 291261287Sdes } 292261287Sdes r[50] += carry; 293261287Sdes} 294261287Sdes 295261287Sdesvoid sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2) 296261287Sdes{ 297261287Sdes int i; 298261287Sdes for(i=0;i<31;i++) 299261287Sdes { 300261287Sdes r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2); 301261287Sdes r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2); 302261287Sdes r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2); 303261287Sdes r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2); 304261287Sdes } 305261287Sdes r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2); 306261287Sdes r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2); 307261287Sdes r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2); 308261287Sdes} 309