fe_tobytes.c (3245B)
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 28 void 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 -= SHL32(carry0,26); 69 carry1 = h1 >> 25; h2 += carry1; h1 -= SHL32(carry1,25); 70 carry2 = h2 >> 26; h3 += carry2; h2 -= SHL32(carry2,26); 71 carry3 = h3 >> 25; h4 += carry3; h3 -= SHL32(carry3,25); 72 carry4 = h4 >> 26; h5 += carry4; h4 -= SHL32(carry4,26); 73 carry5 = h5 >> 25; h6 += carry5; h5 -= SHL32(carry5,25); 74 carry6 = h6 >> 26; h7 += carry6; h6 -= SHL32(carry6,26); 75 carry7 = h7 >> 25; h8 += carry7; h7 -= SHL32(carry7,25); 76 carry8 = h8 >> 26; h9 += carry8; h8 -= SHL32(carry8,26); 77 carry9 = h9 >> 25; h9 -= SHL32(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) | SHL32(h1,2); 91 s[4] = h1 >> 6; 92 s[5] = h1 >> 14; 93 s[6] = (h1 >> 22) | SHL32(h2,3); 94 s[7] = h2 >> 5; 95 s[8] = h2 >> 13; 96 s[9] = (h2 >> 21) | SHL32(h3,5); 97 s[10] = h3 >> 3; 98 s[11] = h3 >> 11; 99 s[12] = (h3 >> 19) | SHL32(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) | SHL32(h6,1); 107 s[20] = h6 >> 7; 108 s[21] = h6 >> 15; 109 s[22] = (h6 >> 23) | SHL32(h7,3); 110 s[23] = h7 >> 5; 111 s[24] = h7 >> 13; 112 s[25] = (h7 >> 21) | SHL32(h8,4); 113 s[26] = h8 >> 4; 114 s[27] = h8 >> 12; 115 s[28] = (h8 >> 20) | SHL32(h9,6); 116 s[29] = h9 >> 2; 117 s[30] = h9 >> 10; 118 s[31] = h9 >> 18; 119 }