n2n-3.1.1.tar.gz: n2n-3.1.1/src/curve25519.c

"Fossies" - the Fresh Open Source Software Archive

Member "n2n-3.1.1/src/curve25519.c" (31 Mar 2022, 8563 Bytes) of package /linux/misc/n2n-3.1.1.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "curve25519.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report:

3.0_vs_3.1.1.

1 /** 2 * (C) 2007-22 - ntop.org and contributors 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 3 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not see see <http://www.gnu.org/licenses/> 16 * 17 */ 18 19 20 /** 21 * version 20081011 22 * Matthew Dempsky 23 * Public domain. 24 * Derived from public domain code by D. J. Bernstein. 25 * 20140216 tweak: Mask top bit of point input. 26 * 27 */ 28 29 30 static void add (unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { 31 32 unsigned int j; 33 unsigned int u; 34 35 u = 0; 36 for(j = 0; j < 31; ++j) { 37 u += a[j] + b[j]; 38 out[j] = u & 255; 39 u >>= 8; 40 } 41 u += a[31] + b[31]; 42 out[31] = u; 43 } 44 45 46 static void sub (unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { 47 48 unsigned int j; 49 unsigned int u; 50 51 u = 218; 52 for(j = 0; j < 31; ++j) { 53 u += a[j] + 65280 - b[j]; 54 out[j] = u & 255; 55 u >>= 8; 56 } 57 u += a[31] - b[31]; 58 out[31] = u; 59 } 60 61 62 static void squeeze (unsigned int a[32]) { 63 64 unsigned int j; 65 unsigned int u; 66 67 u = 0; 68 for(j = 0; j < 31; ++j) { 69 u += a[j]; 70 a[j] = u & 255; 71 u >>= 8; 72 } 73 u += a[31]; 74 a[31] = u & 127; 75 u = 19 * (u >> 7); 76 for(j = 0; j < 31; ++j) { 77 u += a[j]; 78 a[j] = u & 255; 79 u >>= 8; 80 } 81 u += a[31]; 82 a[31] = u; 83 } 84 85 86 static const unsigned int minusp[32] = { 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 87 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128 }; 88 89 90 static void freeze (unsigned int a[32]) { 91 92 unsigned int aorig[32]; 93 unsigned int j; 94 unsigned int negative; 95 96 for(j = 0; j < 32; ++j) 97 aorig[j] = a[j]; 98 add(a, a, minusp); 99 negative = -((a[31] >> 7) & 1); 100 for(j = 0; j < 32; ++j) 101 a[j] ^= negative & (aorig[j] ^ a[j]); 102 } 103 104 105 static void mult (unsigned int out[32], const unsigned int a[32], const unsigned int b[32]) { 106 107 unsigned int i; 108 unsigned int j; 109 unsigned int u; 110 111 for(i = 0; i < 32; ++i) { 112 u = 0; 113 for(j = 0; j <= i; ++j) 114 u += a[j] * b[i - j]; 115 for(j = i + 1; j < 32; ++j) 116 u += 38 * a[j] * b[i + 32 - j]; 117 out[i] = u; 118 } 119 squeeze(out); 120 } 121 122 123 static void mult121665 (unsigned int out[32], const unsigned int a[32]) { 124 125 unsigned int j; 126 unsigned int u; 127 128 u = 0; 129 for(j = 0; j < 31; ++j) { 130 u += 121665 * a[j]; 131 out[j] = u & 255; 132 u >>= 8; 133 } 134 u += 121665 * a[31]; 135 out[31] = u & 127; 136 u = 19 * (u >> 7); 137 for(j = 0; j < 31; ++j) { 138 u += out[j]; 139 out[j] = u & 255; 140 u >>= 8; 141 } 142 u += out[j]; 143 out[j] = u; 144 } 145 146 147 static void square (unsigned int out[32], const unsigned int a[32]) { 148 149 unsigned int i; 150 unsigned int j; 151 unsigned int u; 152 153 for(i = 0; i < 32; ++i) { 154 u = 0; 155 for(j = 0; j < i - j; ++j) 156 u += a[j] * a[i - j]; 157 for(j = i + 1; j < i + 32 - j; ++j) 158 u += 38 * a[j] * a[i + 32 - j]; 159 u *= 2; 160 if((i & 1) == 0) { 161 u += a[i / 2] * a[i / 2]; 162 u += 38 * a[i / 2 + 16] * a[i / 2 + 16]; 163 } 164 out[i] = u; 165 } 166 squeeze(out); 167 } 168 169 170 static void select (unsigned int p[64], unsigned int q[64], const unsigned int r[64], 171 const unsigned int s[64], unsigned int b) { 172 173 unsigned int j; 174 unsigned int t; 175 unsigned int bminus1; 176 177 bminus1 = b - 1; 178 for(j = 0; j < 64; ++j) { 179 t = bminus1 & (r[j] ^ s[j]); 180 p[j] = s[j] ^ t; 181 q[j] = r[j] ^ t; 182 } 183 } 184 185 186 static void mainloop (unsigned int work[64], const unsigned char e[32]) { 187 188 unsigned int xzm1[64]; 189 unsigned int xzm[64]; 190 unsigned int xzmb[64]; 191 unsigned int xzm1b[64]; 192 unsigned int xznb[64]; 193 unsigned int xzn1b[64]; 194 unsigned int a0[64]; 195 unsigned int a1[64]; 196 unsigned int b0[64]; 197 unsigned int b1[64]; 198 unsigned int c1[64]; 199 unsigned int r[32]; 200 unsigned int s[32]; 201 unsigned int t[32]; 202 unsigned int u[32]; 203 unsigned int j; 204 unsigned int b; 205 int pos; 206 207 for(j = 0; j < 32; ++j) 208 xzm1[j] = work[j]; 209 xzm1[32] = 1; 210 for(j = 33; j < 64; ++j) 211 xzm1[j] = 0; 212 213 xzm[0] = 1; 214 for(j = 1; j < 64; ++j) 215 xzm[j] = 0; 216 217 for(pos = 254; pos >= 0; --pos) { 218 b = e[pos / 8] >> (pos & 7); 219 b &= 1; 220 select(xzmb, xzm1b, xzm, xzm1, b); 221 add(a0, xzmb, xzmb + 32); 222 sub(a0 + 32, xzmb, xzmb + 32); 223 add (a1, xzm1b, xzm1b + 32); 224 sub(a1 + 32, xzm1b, xzm1b + 32); 225 square(b0, a0); 226 square(b0 + 32, a0 + 32); 227 mult(b1, a1, a0 + 32); 228 mult(b1 + 32, a1 + 32, a0); 229 add(c1, b1, b1 + 32); 230 sub(c1 + 32, b1, b1 + 32); 231 square(r, c1 + 32); 232 sub(s, b0, b0 + 32); 233 mult121665 (t, s); 234 add(u, t, b0); 235 mult(xznb, b0, b0 + 32); 236 mult(xznb + 32, s, u); 237 square(xzn1b, c1); 238 mult(xzn1b + 32, r, work); 239 select(xzm, xzm1, xznb, xzn1b, b); 240 } 241 242 for(j = 0; j < 64; ++j) 243 work[j] = xzm[j]; 244 } 245 246 247 static void recip (unsigned int out[32], const unsigned int z[32]) { 248 249 unsigned int z2[32]; 250 unsigned int z9[32]; 251 unsigned int z11[32]; 252 unsigned int z2_5_0[32]; 253 unsigned int z2_10_0[32]; 254 unsigned int z2_20_0[32]; 255 unsigned int z2_50_0[32]; 256 unsigned int z2_100_0[32]; 257 unsigned int t0[32]; 258 unsigned int t1[32]; 259 int i; 260 261 /* 2 */ square(z2, z); 262 /* 4 */ square(t1, z2); 263 /* 8 */ square(t0, t1); 264 /* 9 */ mult(z9, t0, z); 265 /* 11 */ mult(z11, z9, z2); 266 /* 22 */ square(t0, z11); 267 /* 2^5 - 2^0 = 31 */ mult(z2_5_0, t0, z9); 268 269 /* 2^6 - 2^1 */ square(t0, z2_5_0); 270 /* 2^7 - 2^2 */ square(t1, t0); 271 /* 2^8 - 2^3 */ square(t0, t1); 272 /* 2^9 - 2^4 */ square(t1, t0); 273 /* 2^10 - 2^5 */ square(t0, t1); 274 /* 2^10 - 2^0 */ mult(z2_10_0, t0, z2_5_0); 275 276 /* 2^11 - 2^1 */ square(t0, z2_10_0); 277 /* 2^12 - 2^2 */ square(t1, t0); 278 /* 2^20 - 2^10 */ for(i = 2; i < 10; i += 2) { 279 square(t0, t1); 280 square(t1, t0); 281 } 282 /* 2^20 - 2^0 */ mult(z2_20_0, t1, z2_10_0); 283 284 /* 2^21 - 2^1 */ square(t0, z2_20_0); 285 /* 2^22 - 2^2 */ square(t1, t0); 286 /* 2^40 - 2^20 */ for(i = 2; i < 20; i += 2) { 287 square(t0, t1); 288 square(t1, t0); 289 } 290 /* 2^40 - 2^0 */ mult(t0, t1, z2_20_0); 291 292 /* 2^41 - 2^1 */ square(t1, t0); 293 /* 2^42 - 2^2 */ square(t0, t1); 294 /* 2^50 - 2^10 */ for(i = 2; i < 10; i += 2) { 295 square(t1, t0); 296 square(t0, t1); 297 } 298 /* 2^50 - 2^0 */ mult(z2_50_0, t0, z2_10_0); 299 300 /* 2^51 - 2^1 */ square(t0, z2_50_0); 301 /* 2^52 - 2^2 */ square(t1, t0); 302 /* 2^100 - 2^50 */ for(i = 2; i < 50; i += 2) { 303 square(t0, t1); 304 square(t1, t0); 305 } 306 /* 2^100 - 2^0 */ mult(z2_100_0, t1, z2_50_0); 307 308 /* 2^101 - 2^1 */ square(t1, z2_100_0); 309 /* 2^102 - 2^2 */ square(t0, t1); 310 /* 2^200 - 2^100 */ for(i = 2; i < 100; i += 2) { 311 square(t1, t0); 312 square(t0, t1); 313 } 314 /* 2^200 - 2^0 */ mult(t1, t0, z2_100_0); 315 316 /* 2^201 - 2^1 */ square(t0, t1); 317 /* 2^202 - 2^2 */ square(t1, t0); 318 /* 2^250 - 2^50 */ for(i = 2; i < 50; i += 2) { 319 square(t0, t1); 320 square(t1, t0); 321 } 322 /* 2^250 - 2^0 */ mult(t0, t1, z2_50_0); 323 324 /* 2^251 - 2^1 */ square(t1, t0); 325 /* 2^252 - 2^2 */ square(t0, t1); 326 /* 2^253 - 2^3 */ square(t1, t0); 327 /* 2^254 - 2^4 */ square(t0, t1); 328 /* 2^255 - 2^5 */ square(t1, t0); 329 /* 2^255 - 21 */ mult(out, t1, z11); 330 } 331 332 333 void curve25519 (unsigned char *q, const unsigned char *n, const unsigned char *p) { 334 335 unsigned int work[96]; 336 unsigned char e[32]; 337 unsigned int i; 338 339 for (i = 0; i < 32; ++i) 340 e[i] = n[i]; 341 e[0] &= 248; 342 e[31] &= 127; 343 e[31] |= 64; 344 345 for (i = 0; i < 32; ++i) 346 work[i] = p[i]; 347 work[31] &= 127; 348 349 mainloop(work, e); 350 recip(work + 32, work + 32); 351 mult(work + 64, work, work + 32); 352 freeze(work + 64); 353 354 for(i = 0; i < 32; ++i) 355 q[i] = work[64 + i]; 356 }