1 #include "fe.h" 2 3 /* 4 Preconditions: 5 |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. 6 7 Write p=2^255-19; q=floor(h/p). 8 Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))). 9 10 Proof: 11 Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4. 12 Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4. 13 14 Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9). 15 Then 0<y<1. 16 17 Write r=h-pq. 18 Have 0<=r<=p-1=2^255-20. 19 Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1. 20 21 Write x=r+19(2^-255)r+y. 22 Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q. 23 24 Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1)) 25 so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. 26 */ 27 fe_tobytes(unsigned char * s,const fe h)28void fe_tobytes(unsigned char *s,const fe h) 29 { 30 crypto_int32 h0 = h[0]; 31 crypto_int32 h1 = h[1]; 32 crypto_int32 h2 = h[2]; 33 crypto_int32 h3 = h[3]; 34 crypto_int32 h4 = h[4]; 35 crypto_int32 h5 = h[5]; 36 crypto_int32 h6 = h[6]; 37 crypto_int32 h7 = h[7]; 38 crypto_int32 h8 = h[8]; 39 crypto_int32 h9 = h[9]; 40 crypto_int32 q; 41 crypto_int32 carry0; 42 crypto_int32 carry1; 43 crypto_int32 carry2; 44 crypto_int32 carry3; 45 crypto_int32 carry4; 46 crypto_int32 carry5; 47 crypto_int32 carry6; 48 crypto_int32 carry7; 49 crypto_int32 carry8; 50 crypto_int32 carry9; 51 52 q = (19 * h9 + (((crypto_int32) 1) << 24)) >> 25; 53 q = (h0 + q) >> 26; 54 q = (h1 + q) >> 25; 55 q = (h2 + q) >> 26; 56 q = (h3 + q) >> 25; 57 q = (h4 + q) >> 26; 58 q = (h5 + q) >> 25; 59 q = (h6 + q) >> 26; 60 q = (h7 + q) >> 25; 61 q = (h8 + q) >> 26; 62 q = (h9 + q) >> 25; 63 64 /* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */ 65 h0 += 19 * q; 66 /* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */ 67 68 carry0 = h0 >> 26; h1 += carry0; h0 -= carry0 << 26; 69 carry1 = h1 >> 25; h2 += carry1; h1 -= carry1 << 25; 70 carry2 = h2 >> 26; h3 += carry2; h2 -= carry2 << 26; 71 carry3 = h3 >> 25; h4 += carry3; h3 -= carry3 << 25; 72 carry4 = h4 >> 26; h5 += carry4; h4 -= carry4 << 26; 73 carry5 = h5 >> 25; h6 += carry5; h5 -= carry5 << 25; 74 carry6 = h6 >> 26; h7 += carry6; h6 -= carry6 << 26; 75 carry7 = h7 >> 25; h8 += carry7; h7 -= carry7 << 25; 76 carry8 = h8 >> 26; h9 += carry8; h8 -= carry8 << 26; 77 carry9 = h9 >> 25; h9 -= carry9 << 25; 78 /* h10 = carry9 */ 79 80 /* 81 Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20. 82 Have h0+...+2^230 h9 between 0 and 2^255-1; 83 evidently 2^255 h10-2^255 q = 0. 84 Goal: Output h0+...+2^230 h9. 85 */ 86 87 s[0] = h0 >> 0; 88 s[1] = h0 >> 8; 89 s[2] = h0 >> 16; 90 s[3] = (h0 >> 24) | (h1 << 2); 91 s[4] = h1 >> 6; 92 s[5] = h1 >> 14; 93 s[6] = (h1 >> 22) | (h2 << 3); 94 s[7] = h2 >> 5; 95 s[8] = h2 >> 13; 96 s[9] = (h2 >> 21) | (h3 << 5); 97 s[10] = h3 >> 3; 98 s[11] = h3 >> 11; 99 s[12] = (h3 >> 19) | (h4 << 6); 100 s[13] = h4 >> 2; 101 s[14] = h4 >> 10; 102 s[15] = h4 >> 18; 103 s[16] = h5 >> 0; 104 s[17] = h5 >> 8; 105 s[18] = h5 >> 16; 106 s[19] = (h5 >> 24) | (h6 << 1); 107 s[20] = h6 >> 7; 108 s[21] = h6 >> 15; 109 s[22] = (h6 >> 23) | (h7 << 3); 110 s[23] = h7 >> 5; 111 s[24] = h7 >> 13; 112 s[25] = (h7 >> 21) | (h8 << 4); 113 s[26] = h8 >> 4; 114 s[27] = h8 >> 12; 115 s[28] = (h8 >> 20) | (h9 << 6); 116 s[29] = h9 >> 2; 117 s[30] = h9 >> 10; 118 s[31] = h9 >> 18; 119 } 120