Annotation of src/usr.bin/signify/sc25519.c, Revision 1.1
1.1 ! deraadt 1: /* $OpenBSD: sc25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */
! 2:
! 3: /*
! 4: * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange,
! 5: * Peter Schwabe, Bo-Yin Yang.
! 6: * Copied from supercop-20130419/crypto_sign/ed25519/ref/sc25519.c
! 7: */
! 8:
! 9: #include "sc25519.h"
! 10:
! 11: /*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */
! 12:
! 13: static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14,
! 14: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10};
! 15:
! 16: static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21,
! 17: 0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F};
! 18:
! 19: static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */
! 20: {
! 21: unsigned int x = a;
! 22: x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */
! 23: x >>= 31; /* 0: no; 1: yes */
! 24: return x;
! 25: }
! 26:
! 27: /* Reduce coefficients of r before calling reduce_add_sub */
! 28: static void reduce_add_sub(sc25519 *r)
! 29: {
! 30: crypto_uint32 pb = 0;
! 31: crypto_uint32 b;
! 32: crypto_uint32 mask;
! 33: int i;
! 34: unsigned char t[32];
! 35:
! 36: for(i=0;i<32;i++)
! 37: {
! 38: pb += m[i];
! 39: b = lt(r->v[i],pb);
! 40: t[i] = r->v[i]-pb+(b<<8);
! 41: pb = b;
! 42: }
! 43: mask = b - 1;
! 44: for(i=0;i<32;i++)
! 45: r->v[i] ^= mask & (r->v[i] ^ t[i]);
! 46: }
! 47:
! 48: /* Reduce coefficients of x before calling barrett_reduce */
! 49: static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64])
! 50: {
! 51: /* See HAC, Alg. 14.42 */
! 52: int i,j;
! 53: crypto_uint32 q2[66];
! 54: crypto_uint32 *q3 = q2 + 33;
! 55: crypto_uint32 r1[33];
! 56: crypto_uint32 r2[33];
! 57: crypto_uint32 carry;
! 58: crypto_uint32 pb = 0;
! 59: crypto_uint32 b;
! 60:
! 61: for (i = 0;i < 66;++i) q2[i] = 0;
! 62: for (i = 0;i < 33;++i) r2[i] = 0;
! 63:
! 64: for(i=0;i<33;i++)
! 65: for(j=0;j<33;j++)
! 66: if(i+j >= 31) q2[i+j] += mu[i]*x[j+31];
! 67: carry = q2[31] >> 8;
! 68: q2[32] += carry;
! 69: carry = q2[32] >> 8;
! 70: q2[33] += carry;
! 71:
! 72: for(i=0;i<33;i++)r1[i] = x[i];
! 73: for(i=0;i<32;i++)
! 74: for(j=0;j<33;j++)
! 75: if(i+j < 33) r2[i+j] += m[i]*q3[j];
! 76:
! 77: for(i=0;i<32;i++)
! 78: {
! 79: carry = r2[i] >> 8;
! 80: r2[i+1] += carry;
! 81: r2[i] &= 0xff;
! 82: }
! 83:
! 84: for(i=0;i<32;i++)
! 85: {
! 86: pb += r2[i];
! 87: b = lt(r1[i],pb);
! 88: r->v[i] = r1[i]-pb+(b<<8);
! 89: pb = b;
! 90: }
! 91:
! 92: /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3
! 93: * If so: Handle it here!
! 94: */
! 95:
! 96: reduce_add_sub(r);
! 97: reduce_add_sub(r);
! 98: }
! 99:
! 100: void sc25519_from32bytes(sc25519 *r, const unsigned char x[32])
! 101: {
! 102: int i;
! 103: crypto_uint32 t[64];
! 104: for(i=0;i<32;i++) t[i] = x[i];
! 105: for(i=32;i<64;++i) t[i] = 0;
! 106: barrett_reduce(r, t);
! 107: }
! 108:
! 109: void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16])
! 110: {
! 111: int i;
! 112: for(i=0;i<16;i++) r->v[i] = x[i];
! 113: }
! 114:
! 115: void sc25519_from64bytes(sc25519 *r, const unsigned char x[64])
! 116: {
! 117: int i;
! 118: crypto_uint32 t[64];
! 119: for(i=0;i<64;i++) t[i] = x[i];
! 120: barrett_reduce(r, t);
! 121: }
! 122:
! 123: void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x)
! 124: {
! 125: int i;
! 126: for(i=0;i<16;i++)
! 127: r->v[i] = x->v[i];
! 128: for(i=0;i<16;i++)
! 129: r->v[16+i] = 0;
! 130: }
! 131:
! 132: void sc25519_to32bytes(unsigned char r[32], const sc25519 *x)
! 133: {
! 134: int i;
! 135: for(i=0;i<32;i++) r[i] = x->v[i];
! 136: }
! 137:
! 138: int sc25519_iszero_vartime(const sc25519 *x)
! 139: {
! 140: int i;
! 141: for(i=0;i<32;i++)
! 142: if(x->v[i] != 0) return 0;
! 143: return 1;
! 144: }
! 145:
! 146: int sc25519_isshort_vartime(const sc25519 *x)
! 147: {
! 148: int i;
! 149: for(i=31;i>15;i--)
! 150: if(x->v[i] != 0) return 0;
! 151: return 1;
! 152: }
! 153:
! 154: int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y)
! 155: {
! 156: int i;
! 157: for(i=31;i>=0;i--)
! 158: {
! 159: if(x->v[i] < y->v[i]) return 1;
! 160: if(x->v[i] > y->v[i]) return 0;
! 161: }
! 162: return 0;
! 163: }
! 164:
! 165: void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y)
! 166: {
! 167: int i, carry;
! 168: for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i];
! 169: for(i=0;i<31;i++)
! 170: {
! 171: carry = r->v[i] >> 8;
! 172: r->v[i+1] += carry;
! 173: r->v[i] &= 0xff;
! 174: }
! 175: reduce_add_sub(r);
! 176: }
! 177:
! 178: void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y)
! 179: {
! 180: crypto_uint32 b = 0;
! 181: crypto_uint32 t;
! 182: int i;
! 183: for(i=0;i<32;i++)
! 184: {
! 185: t = x->v[i] - y->v[i] - b;
! 186: r->v[i] = t & 255;
! 187: b = (t >> 8) & 1;
! 188: }
! 189: }
! 190:
! 191: void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y)
! 192: {
! 193: int i,j,carry;
! 194: crypto_uint32 t[64];
! 195: for(i=0;i<64;i++)t[i] = 0;
! 196:
! 197: for(i=0;i<32;i++)
! 198: for(j=0;j<32;j++)
! 199: t[i+j] += x->v[i] * y->v[j];
! 200:
! 201: /* Reduce coefficients */
! 202: for(i=0;i<63;i++)
! 203: {
! 204: carry = t[i] >> 8;
! 205: t[i+1] += carry;
! 206: t[i] &= 0xff;
! 207: }
! 208:
! 209: barrett_reduce(r, t);
! 210: }
! 211:
! 212: void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y)
! 213: {
! 214: sc25519 t;
! 215: sc25519_from_shortsc(&t, y);
! 216: sc25519_mul(r, x, &t);
! 217: }
! 218:
! 219: void sc25519_window3(signed char r[85], const sc25519 *s)
! 220: {
! 221: char carry;
! 222: int i;
! 223: for(i=0;i<10;i++)
! 224: {
! 225: r[8*i+0] = s->v[3*i+0] & 7;
! 226: r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
! 227: r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
! 228: r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
! 229: r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
! 230: r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
! 231: r[8*i+5] = (s->v[3*i+1] >> 7) & 7;
! 232: r[8*i+5] ^= (s->v[3*i+2] << 1) & 7;
! 233: r[8*i+6] = (s->v[3*i+2] >> 2) & 7;
! 234: r[8*i+7] = (s->v[3*i+2] >> 5) & 7;
! 235: }
! 236: r[8*i+0] = s->v[3*i+0] & 7;
! 237: r[8*i+1] = (s->v[3*i+0] >> 3) & 7;
! 238: r[8*i+2] = (s->v[3*i+0] >> 6) & 7;
! 239: r[8*i+2] ^= (s->v[3*i+1] << 2) & 7;
! 240: r[8*i+3] = (s->v[3*i+1] >> 1) & 7;
! 241: r[8*i+4] = (s->v[3*i+1] >> 4) & 7;
! 242:
! 243: /* Making it signed */
! 244: carry = 0;
! 245: for(i=0;i<84;i++)
! 246: {
! 247: r[i] += carry;
! 248: r[i+1] += r[i] >> 3;
! 249: r[i] &= 7;
! 250: carry = r[i] >> 2;
! 251: r[i] -= carry<<3;
! 252: }
! 253: r[84] += carry;
! 254: }
! 255:
! 256: void sc25519_window5(signed char r[51], const sc25519 *s)
! 257: {
! 258: char carry;
! 259: int i;
! 260: for(i=0;i<6;i++)
! 261: {
! 262: r[8*i+0] = s->v[5*i+0] & 31;
! 263: r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
! 264: r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
! 265: r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
! 266: r[8*i+3] = (s->v[5*i+1] >> 7) & 31;
! 267: r[8*i+3] ^= (s->v[5*i+2] << 1) & 31;
! 268: r[8*i+4] = (s->v[5*i+2] >> 4) & 31;
! 269: r[8*i+4] ^= (s->v[5*i+3] << 4) & 31;
! 270: r[8*i+5] = (s->v[5*i+3] >> 1) & 31;
! 271: r[8*i+6] = (s->v[5*i+3] >> 6) & 31;
! 272: r[8*i+6] ^= (s->v[5*i+4] << 2) & 31;
! 273: r[8*i+7] = (s->v[5*i+4] >> 3) & 31;
! 274: }
! 275: r[8*i+0] = s->v[5*i+0] & 31;
! 276: r[8*i+1] = (s->v[5*i+0] >> 5) & 31;
! 277: r[8*i+1] ^= (s->v[5*i+1] << 3) & 31;
! 278: r[8*i+2] = (s->v[5*i+1] >> 2) & 31;
! 279:
! 280: /* Making it signed */
! 281: carry = 0;
! 282: for(i=0;i<50;i++)
! 283: {
! 284: r[i] += carry;
! 285: r[i+1] += r[i] >> 5;
! 286: r[i] &= 31;
! 287: carry = r[i] >> 4;
! 288: r[i] -= carry<<5;
! 289: }
! 290: r[50] += carry;
! 291: }
! 292:
! 293: void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2)
! 294: {
! 295: int i;
! 296: for(i=0;i<31;i++)
! 297: {
! 298: r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2);
! 299: r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2);
! 300: r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2);
! 301: r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2);
! 302: }
! 303: r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2);
! 304: r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2);
! 305: r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2);
! 306: }
![[BACK]](/icons/back.gif){kind=icon}
Return to sc25519.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / signify