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