1const std = @import("std"); 2const mem = std.mem; 3 4const NonCanonicalError = std.crypto.errors.NonCanonicalError; 5 6/// 2^252 + 27742317777372353535851937790883648493 7pub const field_size = [32]u8{ 8 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, // 2^252+27742317777372353535851937790883648493 9}; 10 11/// A compressed scalar 12pub const CompressedScalar = [32]u8; 13 14/// Zero 15pub const zero = [_]u8{0} ** 32; 16 17/// Reject a scalar whose encoding is not canonical. 18pub fn rejectNonCanonical(s: [32]u8) NonCanonicalError!void { 19 var c: u8 = 0; 20 var n: u8 = 1; 21 var i: usize = 31; 22 while (true) : (i -= 1) { 23 const xs = @as(u16, s[i]); 24 const xfield_size = @as(u16, field_size[i]); 25 c |= @intCast(u8, ((xs -% xfield_size) >> 8) & n); 26 n &= @intCast(u8, ((xs ^ xfield_size) -% 1) >> 8); 27 if (i == 0) break; 28 } 29 if (c == 0) { 30 return error.NonCanonical; 31 } 32} 33 34/// Reduce a scalar to the field size. 35pub fn reduce(s: [32]u8) [32]u8 { 36 return Scalar.fromBytes(s).toBytes(); 37} 38 39/// Reduce a 64-bytes scalar to the field size. 40pub fn reduce64(s: [64]u8) [32]u8 { 41 return ScalarDouble.fromBytes64(s).toBytes(); 42} 43 44/// Perform the X25519 "clamping" operation. 45/// The scalar is then guaranteed to be a multiple of the cofactor. 46pub inline fn clamp(s: *[32]u8) void { 47 s[0] &= 248; 48 s[31] = (s[31] & 127) | 64; 49} 50 51/// Return a*b (mod L) 52pub fn mul(a: [32]u8, b: [32]u8) [32]u8 { 53 return Scalar.fromBytes(a).mul(Scalar.fromBytes(b)).toBytes(); 54} 55 56/// Return a*b+c (mod L) 57pub fn mulAdd(a: [32]u8, b: [32]u8, c: [32]u8) [32]u8 { 58 return Scalar.fromBytes(a).mul(Scalar.fromBytes(b)).add(Scalar.fromBytes(c)).toBytes(); 59} 60 61/// Return a*8 (mod L) 62pub fn mul8(s: [32]u8) [32]u8 { 63 var x = Scalar.fromBytes(s); 64 x = x.add(x); 65 x = x.add(x); 66 x = x.add(x); 67 return x.toBytes(); 68} 69 70/// Return a+b (mod L) 71pub fn add(a: [32]u8, b: [32]u8) [32]u8 { 72 return Scalar.fromBytes(a).add(Scalar.fromBytes(b)).toBytes(); 73} 74 75/// Return -s (mod L) 76pub fn neg(s: [32]u8) [32]u8 { 77 const fs: [64]u8 = field_size ++ [_]u8{0} ** 32; 78 var sx: [64]u8 = undefined; 79 mem.copy(u8, sx[0..32], s[0..]); 80 mem.set(u8, sx[32..], 0); 81 var carry: u32 = 0; 82 var i: usize = 0; 83 while (i < 64) : (i += 1) { 84 carry = @as(u32, fs[i]) -% sx[i] -% @as(u32, carry); 85 sx[i] = @truncate(u8, carry); 86 carry = (carry >> 8) & 1; 87 } 88 return reduce64(sx); 89} 90 91/// Return (a-b) (mod L) 92pub fn sub(a: [32]u8, b: [32]u8) [32]u8 { 93 return add(a, neg(b)); 94} 95 96/// A scalar in unpacked representation 97pub const Scalar = struct { 98 const Limbs = [5]u64; 99 limbs: Limbs = undefined, 100 101 /// Unpack a 32-byte representation of a scalar 102 pub fn fromBytes(bytes: [32]u8) Scalar { 103 return ScalarDouble.fromBytes32(bytes).reduce(5); 104 } 105 106 /// Pack a scalar into bytes 107 pub fn toBytes(expanded: *const Scalar) [32]u8 { 108 var bytes: [32]u8 = undefined; 109 var i: usize = 0; 110 while (i < 4) : (i += 1) { 111 mem.writeIntLittle(u64, bytes[i * 7 ..][0..8], expanded.limbs[i]); 112 } 113 mem.writeIntLittle(u32, bytes[i * 7 ..][0..4], @intCast(u32, expanded.limbs[i])); 114 return bytes; 115 } 116 117 /// Return x+y (mod l) 118 pub fn add(x: Scalar, y: Scalar) Scalar { 119 const carry0 = (x.limbs[0] + y.limbs[0]) >> 56; 120 const t0 = (x.limbs[0] + y.limbs[0]) & 0xffffffffffffff; 121 const t00 = t0; 122 const c0 = carry0; 123 const carry1 = (x.limbs[1] + y.limbs[1] + c0) >> 56; 124 const t1 = (x.limbs[1] + y.limbs[1] + c0) & 0xffffffffffffff; 125 const t10 = t1; 126 const c1 = carry1; 127 const carry2 = (x.limbs[2] + y.limbs[2] + c1) >> 56; 128 const t2 = (x.limbs[2] + y.limbs[2] + c1) & 0xffffffffffffff; 129 const t20 = t2; 130 const c2 = carry2; 131 const carry = (x.limbs[3] + y.limbs[3] + c2) >> 56; 132 const t3 = (x.limbs[3] + y.limbs[3] + c2) & 0xffffffffffffff; 133 const t30 = t3; 134 const c3 = carry; 135 const t4 = x.limbs[4] + y.limbs[4] + c3; 136 137 const y01: u64 = 5175514460705773; 138 const y11: u64 = 70332060721272408; 139 const y21: u64 = 5342; 140 const y31: u64 = 0; 141 const y41: u64 = 268435456; 142 143 const b5 = (t00 -% y01) >> 63; 144 const t5 = ((b5 << 56) + t00) -% y01; 145 const b0 = b5; 146 const t01 = t5; 147 const b6 = (t10 -% (y11 + b0)) >> 63; 148 const t6 = ((b6 << 56) + t10) -% (y11 + b0); 149 const b1 = b6; 150 const t11 = t6; 151 const b7 = (t20 -% (y21 + b1)) >> 63; 152 const t7 = ((b7 << 56) + t20) -% (y21 + b1); 153 const b2 = b7; 154 const t21 = t7; 155 const b8 = (t30 -% (y31 + b2)) >> 63; 156 const t8 = ((b8 << 56) + t30) -% (y31 + b2); 157 const b3 = b8; 158 const t31 = t8; 159 const b = (t4 -% (y41 + b3)) >> 63; 160 const t = ((b << 56) + t4) -% (y41 + b3); 161 const b4 = b; 162 const t41 = t; 163 164 const mask = (b4 -% 1); 165 const z00 = t00 ^ (mask & (t00 ^ t01)); 166 const z10 = t10 ^ (mask & (t10 ^ t11)); 167 const z20 = t20 ^ (mask & (t20 ^ t21)); 168 const z30 = t30 ^ (mask & (t30 ^ t31)); 169 const z40 = t4 ^ (mask & (t4 ^ t41)); 170 171 return Scalar{ .limbs = .{ z00, z10, z20, z30, z40 } }; 172 } 173 174 /// Return x*r (mod l) 175 pub fn mul(x: Scalar, y: Scalar) Scalar { 176 const xy000 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[0]); 177 const xy010 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[1]); 178 const xy020 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[2]); 179 const xy030 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[3]); 180 const xy040 = @as(u128, x.limbs[0]) * @as(u128, y.limbs[4]); 181 const xy100 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[0]); 182 const xy110 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[1]); 183 const xy120 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[2]); 184 const xy130 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[3]); 185 const xy140 = @as(u128, x.limbs[1]) * @as(u128, y.limbs[4]); 186 const xy200 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[0]); 187 const xy210 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[1]); 188 const xy220 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[2]); 189 const xy230 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[3]); 190 const xy240 = @as(u128, x.limbs[2]) * @as(u128, y.limbs[4]); 191 const xy300 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[0]); 192 const xy310 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[1]); 193 const xy320 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[2]); 194 const xy330 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[3]); 195 const xy340 = @as(u128, x.limbs[3]) * @as(u128, y.limbs[4]); 196 const xy400 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[0]); 197 const xy410 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[1]); 198 const xy420 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[2]); 199 const xy430 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[3]); 200 const xy440 = @as(u128, x.limbs[4]) * @as(u128, y.limbs[4]); 201 const z00 = xy000; 202 const z10 = xy010 + xy100; 203 const z20 = xy020 + xy110 + xy200; 204 const z30 = xy030 + xy120 + xy210 + xy300; 205 const z40 = xy040 + xy130 + xy220 + xy310 + xy400; 206 const z50 = xy140 + xy230 + xy320 + xy410; 207 const z60 = xy240 + xy330 + xy420; 208 const z70 = xy340 + xy430; 209 const z80 = xy440; 210 211 const carry0 = z00 >> 56; 212 const t10 = @truncate(u64, z00) & 0xffffffffffffff; 213 const c00 = carry0; 214 const t00 = t10; 215 const carry1 = (z10 + c00) >> 56; 216 const t11 = @truncate(u64, (z10 + c00)) & 0xffffffffffffff; 217 const c10 = carry1; 218 const t12 = t11; 219 const carry2 = (z20 + c10) >> 56; 220 const t13 = @truncate(u64, (z20 + c10)) & 0xffffffffffffff; 221 const c20 = carry2; 222 const t20 = t13; 223 const carry3 = (z30 + c20) >> 56; 224 const t14 = @truncate(u64, (z30 + c20)) & 0xffffffffffffff; 225 const c30 = carry3; 226 const t30 = t14; 227 const carry4 = (z40 + c30) >> 56; 228 const t15 = @truncate(u64, (z40 + c30)) & 0xffffffffffffff; 229 const c40 = carry4; 230 const t40 = t15; 231 const carry5 = (z50 + c40) >> 56; 232 const t16 = @truncate(u64, (z50 + c40)) & 0xffffffffffffff; 233 const c50 = carry5; 234 const t50 = t16; 235 const carry6 = (z60 + c50) >> 56; 236 const t17 = @truncate(u64, (z60 + c50)) & 0xffffffffffffff; 237 const c60 = carry6; 238 const t60 = t17; 239 const carry7 = (z70 + c60) >> 56; 240 const t18 = @truncate(u64, (z70 + c60)) & 0xffffffffffffff; 241 const c70 = carry7; 242 const t70 = t18; 243 const carry8 = (z80 + c70) >> 56; 244 const t19 = @truncate(u64, (z80 + c70)) & 0xffffffffffffff; 245 const c80 = carry8; 246 const t80 = t19; 247 const t90 = (@truncate(u64, c80)); 248 const r0 = t00; 249 const r1 = t12; 250 const r2 = t20; 251 const r3 = t30; 252 const r4 = t40; 253 const r5 = t50; 254 const r6 = t60; 255 const r7 = t70; 256 const r8 = t80; 257 const r9 = t90; 258 259 const m0: u64 = 5175514460705773; 260 const m1: u64 = 70332060721272408; 261 const m2: u64 = 5342; 262 const m3: u64 = 0; 263 const m4: u64 = 268435456; 264 const mu0: u64 = 44162584779952923; 265 const mu1: u64 = 9390964836247533; 266 const mu2: u64 = 72057594036560134; 267 const mu3: u64 = 72057594037927935; 268 const mu4: u64 = 68719476735; 269 270 const y_ = (r5 & 0xffffff) << 32; 271 const x_ = r4 >> 24; 272 const z01 = (x_ | y_); 273 const y_0 = (r6 & 0xffffff) << 32; 274 const x_0 = r5 >> 24; 275 const z11 = (x_0 | y_0); 276 const y_1 = (r7 & 0xffffff) << 32; 277 const x_1 = r6 >> 24; 278 const z21 = (x_1 | y_1); 279 const y_2 = (r8 & 0xffffff) << 32; 280 const x_2 = r7 >> 24; 281 const z31 = (x_2 | y_2); 282 const y_3 = (r9 & 0xffffff) << 32; 283 const x_3 = r8 >> 24; 284 const z41 = (x_3 | y_3); 285 const q0 = z01; 286 const q1 = z11; 287 const q2 = z21; 288 const q3 = z31; 289 const q4 = z41; 290 const xy001 = @as(u128, q0) * @as(u128, mu0); 291 const xy011 = @as(u128, q0) * @as(u128, mu1); 292 const xy021 = @as(u128, q0) * @as(u128, mu2); 293 const xy031 = @as(u128, q0) * @as(u128, mu3); 294 const xy041 = @as(u128, q0) * @as(u128, mu4); 295 const xy101 = @as(u128, q1) * @as(u128, mu0); 296 const xy111 = @as(u128, q1) * @as(u128, mu1); 297 const xy121 = @as(u128, q1) * @as(u128, mu2); 298 const xy131 = @as(u128, q1) * @as(u128, mu3); 299 const xy14 = @as(u128, q1) * @as(u128, mu4); 300 const xy201 = @as(u128, q2) * @as(u128, mu0); 301 const xy211 = @as(u128, q2) * @as(u128, mu1); 302 const xy221 = @as(u128, q2) * @as(u128, mu2); 303 const xy23 = @as(u128, q2) * @as(u128, mu3); 304 const xy24 = @as(u128, q2) * @as(u128, mu4); 305 const xy301 = @as(u128, q3) * @as(u128, mu0); 306 const xy311 = @as(u128, q3) * @as(u128, mu1); 307 const xy32 = @as(u128, q3) * @as(u128, mu2); 308 const xy33 = @as(u128, q3) * @as(u128, mu3); 309 const xy34 = @as(u128, q3) * @as(u128, mu4); 310 const xy401 = @as(u128, q4) * @as(u128, mu0); 311 const xy41 = @as(u128, q4) * @as(u128, mu1); 312 const xy42 = @as(u128, q4) * @as(u128, mu2); 313 const xy43 = @as(u128, q4) * @as(u128, mu3); 314 const xy44 = @as(u128, q4) * @as(u128, mu4); 315 const z02 = xy001; 316 const z12 = xy011 + xy101; 317 const z22 = xy021 + xy111 + xy201; 318 const z32 = xy031 + xy121 + xy211 + xy301; 319 const z42 = xy041 + xy131 + xy221 + xy311 + xy401; 320 const z5 = xy14 + xy23 + xy32 + xy41; 321 const z6 = xy24 + xy33 + xy42; 322 const z7 = xy34 + xy43; 323 const z8 = xy44; 324 325 const carry9 = z02 >> 56; 326 const c01 = carry9; 327 const carry10 = (z12 + c01) >> 56; 328 const c11 = carry10; 329 const carry11 = (z22 + c11) >> 56; 330 const c21 = carry11; 331 const carry12 = (z32 + c21) >> 56; 332 const c31 = carry12; 333 const carry13 = (z42 + c31) >> 56; 334 const t24 = @truncate(u64, z42 + c31) & 0xffffffffffffff; 335 const c41 = carry13; 336 const t41 = t24; 337 const carry14 = (z5 + c41) >> 56; 338 const t25 = @truncate(u64, z5 + c41) & 0xffffffffffffff; 339 const c5 = carry14; 340 const t5 = t25; 341 const carry15 = (z6 + c5) >> 56; 342 const t26 = @truncate(u64, z6 + c5) & 0xffffffffffffff; 343 const c6 = carry15; 344 const t6 = t26; 345 const carry16 = (z7 + c6) >> 56; 346 const t27 = @truncate(u64, z7 + c6) & 0xffffffffffffff; 347 const c7 = carry16; 348 const t7 = t27; 349 const carry17 = (z8 + c7) >> 56; 350 const t28 = @truncate(u64, z8 + c7) & 0xffffffffffffff; 351 const c8 = carry17; 352 const t8 = t28; 353 const t9 = @truncate(u64, c8); 354 355 const qmu4_ = t41; 356 const qmu5_ = t5; 357 const qmu6_ = t6; 358 const qmu7_ = t7; 359 const qmu8_ = t8; 360 const qmu9_ = t9; 361 const y_4 = (qmu5_ & 0xffffffffff) << 16; 362 const x_4 = qmu4_ >> 40; 363 const z03 = (x_4 | y_4); 364 const y_5 = (qmu6_ & 0xffffffffff) << 16; 365 const x_5 = qmu5_ >> 40; 366 const z13 = (x_5 | y_5); 367 const y_6 = (qmu7_ & 0xffffffffff) << 16; 368 const x_6 = qmu6_ >> 40; 369 const z23 = (x_6 | y_6); 370 const y_7 = (qmu8_ & 0xffffffffff) << 16; 371 const x_7 = qmu7_ >> 40; 372 const z33 = (x_7 | y_7); 373 const y_8 = (qmu9_ & 0xffffffffff) << 16; 374 const x_8 = qmu8_ >> 40; 375 const z43 = (x_8 | y_8); 376 const qdiv0 = z03; 377 const qdiv1 = z13; 378 const qdiv2 = z23; 379 const qdiv3 = z33; 380 const qdiv4 = z43; 381 const r01 = r0; 382 const r11 = r1; 383 const r21 = r2; 384 const r31 = r3; 385 const r41 = (r4 & 0xffffffffff); 386 387 const xy00 = @as(u128, qdiv0) * @as(u128, m0); 388 const xy01 = @as(u128, qdiv0) * @as(u128, m1); 389 const xy02 = @as(u128, qdiv0) * @as(u128, m2); 390 const xy03 = @as(u128, qdiv0) * @as(u128, m3); 391 const xy04 = @as(u128, qdiv0) * @as(u128, m4); 392 const xy10 = @as(u128, qdiv1) * @as(u128, m0); 393 const xy11 = @as(u128, qdiv1) * @as(u128, m1); 394 const xy12 = @as(u128, qdiv1) * @as(u128, m2); 395 const xy13 = @as(u128, qdiv1) * @as(u128, m3); 396 const xy20 = @as(u128, qdiv2) * @as(u128, m0); 397 const xy21 = @as(u128, qdiv2) * @as(u128, m1); 398 const xy22 = @as(u128, qdiv2) * @as(u128, m2); 399 const xy30 = @as(u128, qdiv3) * @as(u128, m0); 400 const xy31 = @as(u128, qdiv3) * @as(u128, m1); 401 const xy40 = @as(u128, qdiv4) * @as(u128, m0); 402 const carry18 = xy00 >> 56; 403 const t29 = @truncate(u64, xy00) & 0xffffffffffffff; 404 const c0 = carry18; 405 const t01 = t29; 406 const carry19 = (xy01 + xy10 + c0) >> 56; 407 const t31 = @truncate(u64, xy01 + xy10 + c0) & 0xffffffffffffff; 408 const c12 = carry19; 409 const t110 = t31; 410 const carry20 = (xy02 + xy11 + xy20 + c12) >> 56; 411 const t32 = @truncate(u64, xy02 + xy11 + xy20 + c12) & 0xffffffffffffff; 412 const c22 = carry20; 413 const t210 = t32; 414 const carry = (xy03 + xy12 + xy21 + xy30 + c22) >> 56; 415 const t33 = @truncate(u64, xy03 + xy12 + xy21 + xy30 + c22) & 0xffffffffffffff; 416 const c32 = carry; 417 const t34 = t33; 418 const t42 = @truncate(u64, xy04 + xy13 + xy22 + xy31 + xy40 + c32) & 0xffffffffff; 419 420 const qmul0 = t01; 421 const qmul1 = t110; 422 const qmul2 = t210; 423 const qmul3 = t34; 424 const qmul4 = t42; 425 const b5 = (r01 -% qmul0) >> 63; 426 const t35 = ((b5 << 56) + r01) -% qmul0; 427 const c1 = b5; 428 const t02 = t35; 429 const b6 = (r11 -% (qmul1 + c1)) >> 63; 430 const t36 = ((b6 << 56) + r11) -% (qmul1 + c1); 431 const c2 = b6; 432 const t111 = t36; 433 const b7 = (r21 -% (qmul2 + c2)) >> 63; 434 const t37 = ((b7 << 56) + r21) -% (qmul2 + c2); 435 const c3 = b7; 436 const t211 = t37; 437 const b8 = (r31 -% (qmul3 + c3)) >> 63; 438 const t38 = ((b8 << 56) + r31) -% (qmul3 + c3); 439 const c4 = b8; 440 const t39 = t38; 441 const b9 = (r41 -% (qmul4 + c4)) >> 63; 442 const t43 = ((b9 << 40) + r41) -% (qmul4 + c4); 443 const t44 = t43; 444 const s0 = t02; 445 const s1 = t111; 446 const s2 = t211; 447 const s3 = t39; 448 const s4 = t44; 449 450 const y01: u64 = 5175514460705773; 451 const y11: u64 = 70332060721272408; 452 const y21: u64 = 5342; 453 const y31: u64 = 0; 454 const y41: u64 = 268435456; 455 456 const b10 = (s0 -% y01) >> 63; 457 const t45 = ((b10 << 56) + s0) -% y01; 458 const b0 = b10; 459 const t0 = t45; 460 const b11 = (s1 -% (y11 + b0)) >> 63; 461 const t46 = ((b11 << 56) + s1) -% (y11 + b0); 462 const b1 = b11; 463 const t1 = t46; 464 const b12 = (s2 -% (y21 + b1)) >> 63; 465 const t47 = ((b12 << 56) + s2) -% (y21 + b1); 466 const b2 = b12; 467 const t2 = t47; 468 const b13 = (s3 -% (y31 + b2)) >> 63; 469 const t48 = ((b13 << 56) + s3) -% (y31 + b2); 470 const b3 = b13; 471 const t3 = t48; 472 const b = (s4 -% (y41 + b3)) >> 63; 473 const t = ((b << 56) + s4) -% (y41 + b3); 474 const b4 = b; 475 const t4 = t; 476 const mask = (b4 -% @intCast(u64, ((1)))); 477 const z04 = s0 ^ (mask & (s0 ^ t0)); 478 const z14 = s1 ^ (mask & (s1 ^ t1)); 479 const z24 = s2 ^ (mask & (s2 ^ t2)); 480 const z34 = s3 ^ (mask & (s3 ^ t3)); 481 const z44 = s4 ^ (mask & (s4 ^ t4)); 482 483 return Scalar{ .limbs = .{ z04, z14, z24, z34, z44 } }; 484 } 485}; 486 487const ScalarDouble = struct { 488 const Limbs = [10]u64; 489 limbs: Limbs = undefined, 490 491 fn fromBytes64(bytes: [64]u8) ScalarDouble { 492 var limbs: Limbs = undefined; 493 var i: usize = 0; 494 while (i < 9) : (i += 1) { 495 limbs[i] = mem.readIntLittle(u64, bytes[i * 7 ..][0..8]) & 0xffffffffffffff; 496 } 497 limbs[i] = @as(u64, bytes[i * 7]); 498 return ScalarDouble{ .limbs = limbs }; 499 } 500 501 fn fromBytes32(bytes: [32]u8) ScalarDouble { 502 var limbs: Limbs = undefined; 503 var i: usize = 0; 504 while (i < 4) : (i += 1) { 505 limbs[i] = mem.readIntLittle(u64, bytes[i * 7 ..][0..8]) & 0xffffffffffffff; 506 } 507 limbs[i] = @as(u64, mem.readIntLittle(u32, bytes[i * 7 ..][0..4])); 508 mem.set(u64, limbs[5..], 0); 509 return ScalarDouble{ .limbs = limbs }; 510 } 511 512 fn toBytes(expanded_double: *ScalarDouble) [32]u8 { 513 return expanded_double.reduce(10).toBytes(); 514 } 515 516 /// Barrett reduction 517 fn reduce(expanded: *ScalarDouble, comptime limbs_count: usize) Scalar { 518 const t = expanded.limbs; 519 const t0 = if (limbs_count <= 0) 0 else t[0]; 520 const t1 = if (limbs_count <= 1) 0 else t[1]; 521 const t2 = if (limbs_count <= 2) 0 else t[2]; 522 const t3 = if (limbs_count <= 3) 0 else t[3]; 523 const t4 = if (limbs_count <= 4) 0 else t[4]; 524 const t5 = if (limbs_count <= 5) 0 else t[5]; 525 const t6 = if (limbs_count <= 6) 0 else t[6]; 526 const t7 = if (limbs_count <= 7) 0 else t[7]; 527 const t8 = if (limbs_count <= 8) 0 else t[8]; 528 const t9 = if (limbs_count <= 9) 0 else t[9]; 529 530 const m0: u64 = 5175514460705773; 531 const m1: u64 = 70332060721272408; 532 const m2: u64 = 5342; 533 const m3: u64 = 0; 534 const m4: u64 = 268435456; 535 const mu0: u64 = 44162584779952923; 536 const mu1: u64 = 9390964836247533; 537 const mu2: u64 = 72057594036560134; 538 const mu3: u64 = 0xffffffffffffff; 539 const mu4: u64 = 68719476735; 540 541 const y_ = (t5 & 0xffffff) << 32; 542 const x_ = t4 >> 24; 543 const z00 = x_ | y_; 544 const y_0 = (t6 & 0xffffff) << 32; 545 const x_0 = t5 >> 24; 546 const z10 = x_0 | y_0; 547 const y_1 = (t7 & 0xffffff) << 32; 548 const x_1 = t6 >> 24; 549 const z20 = x_1 | y_1; 550 const y_2 = (t8 & 0xffffff) << 32; 551 const x_2 = t7 >> 24; 552 const z30 = x_2 | y_2; 553 const y_3 = (t9 & 0xffffff) << 32; 554 const x_3 = t8 >> 24; 555 const z40 = x_3 | y_3; 556 const q0 = z00; 557 const q1 = z10; 558 const q2 = z20; 559 const q3 = z30; 560 const q4 = z40; 561 562 const xy000 = @as(u128, q0) * @as(u128, mu0); 563 const xy010 = @as(u128, q0) * @as(u128, mu1); 564 const xy020 = @as(u128, q0) * @as(u128, mu2); 565 const xy030 = @as(u128, q0) * @as(u128, mu3); 566 const xy040 = @as(u128, q0) * @as(u128, mu4); 567 const xy100 = @as(u128, q1) * @as(u128, mu0); 568 const xy110 = @as(u128, q1) * @as(u128, mu1); 569 const xy120 = @as(u128, q1) * @as(u128, mu2); 570 const xy130 = @as(u128, q1) * @as(u128, mu3); 571 const xy14 = @as(u128, q1) * @as(u128, mu4); 572 const xy200 = @as(u128, q2) * @as(u128, mu0); 573 const xy210 = @as(u128, q2) * @as(u128, mu1); 574 const xy220 = @as(u128, q2) * @as(u128, mu2); 575 const xy23 = @as(u128, q2) * @as(u128, mu3); 576 const xy24 = @as(u128, q2) * @as(u128, mu4); 577 const xy300 = @as(u128, q3) * @as(u128, mu0); 578 const xy310 = @as(u128, q3) * @as(u128, mu1); 579 const xy32 = @as(u128, q3) * @as(u128, mu2); 580 const xy33 = @as(u128, q3) * @as(u128, mu3); 581 const xy34 = @as(u128, q3) * @as(u128, mu4); 582 const xy400 = @as(u128, q4) * @as(u128, mu0); 583 const xy41 = @as(u128, q4) * @as(u128, mu1); 584 const xy42 = @as(u128, q4) * @as(u128, mu2); 585 const xy43 = @as(u128, q4) * @as(u128, mu3); 586 const xy44 = @as(u128, q4) * @as(u128, mu4); 587 const z01 = xy000; 588 const z11 = xy010 + xy100; 589 const z21 = xy020 + xy110 + xy200; 590 const z31 = xy030 + xy120 + xy210 + xy300; 591 const z41 = xy040 + xy130 + xy220 + xy310 + xy400; 592 const z5 = xy14 + xy23 + xy32 + xy41; 593 const z6 = xy24 + xy33 + xy42; 594 const z7 = xy34 + xy43; 595 const z8 = xy44; 596 597 const carry0 = z01 >> 56; 598 const c00 = carry0; 599 const carry1 = (z11 + c00) >> 56; 600 const c10 = carry1; 601 const carry2 = (z21 + c10) >> 56; 602 const c20 = carry2; 603 const carry3 = (z31 + c20) >> 56; 604 const c30 = carry3; 605 const carry4 = (z41 + c30) >> 56; 606 const t103 = @as(u64, @truncate(u64, z41 + c30)) & 0xffffffffffffff; 607 const c40 = carry4; 608 const t410 = t103; 609 const carry5 = (z5 + c40) >> 56; 610 const t104 = @as(u64, @truncate(u64, z5 + c40)) & 0xffffffffffffff; 611 const c5 = carry5; 612 const t51 = t104; 613 const carry6 = (z6 + c5) >> 56; 614 const t105 = @as(u64, @truncate(u64, z6 + c5)) & 0xffffffffffffff; 615 const c6 = carry6; 616 const t61 = t105; 617 const carry7 = (z7 + c6) >> 56; 618 const t106 = @as(u64, @truncate(u64, z7 + c6)) & 0xffffffffffffff; 619 const c7 = carry7; 620 const t71 = t106; 621 const carry8 = (z8 + c7) >> 56; 622 const t107 = @as(u64, @truncate(u64, z8 + c7)) & 0xffffffffffffff; 623 const c8 = carry8; 624 const t81 = t107; 625 const t91 = @as(u64, @truncate(u64, c8)); 626 627 const qmu4_ = t410; 628 const qmu5_ = t51; 629 const qmu6_ = t61; 630 const qmu7_ = t71; 631 const qmu8_ = t81; 632 const qmu9_ = t91; 633 const y_4 = (qmu5_ & 0xffffffffff) << 16; 634 const x_4 = qmu4_ >> 40; 635 const z02 = x_4 | y_4; 636 const y_5 = (qmu6_ & 0xffffffffff) << 16; 637 const x_5 = qmu5_ >> 40; 638 const z12 = x_5 | y_5; 639 const y_6 = (qmu7_ & 0xffffffffff) << 16; 640 const x_6 = qmu6_ >> 40; 641 const z22 = x_6 | y_6; 642 const y_7 = (qmu8_ & 0xffffffffff) << 16; 643 const x_7 = qmu7_ >> 40; 644 const z32 = x_7 | y_7; 645 const y_8 = (qmu9_ & 0xffffffffff) << 16; 646 const x_8 = qmu8_ >> 40; 647 const z42 = x_8 | y_8; 648 const qdiv0 = z02; 649 const qdiv1 = z12; 650 const qdiv2 = z22; 651 const qdiv3 = z32; 652 const qdiv4 = z42; 653 const r0 = t0; 654 const r1 = t1; 655 const r2 = t2; 656 const r3 = t3; 657 const r4 = t4 & 0xffffffffff; 658 659 const xy00 = @as(u128, qdiv0) * @as(u128, m0); 660 const xy01 = @as(u128, qdiv0) * @as(u128, m1); 661 const xy02 = @as(u128, qdiv0) * @as(u128, m2); 662 const xy03 = @as(u128, qdiv0) * @as(u128, m3); 663 const xy04 = @as(u128, qdiv0) * @as(u128, m4); 664 const xy10 = @as(u128, qdiv1) * @as(u128, m0); 665 const xy11 = @as(u128, qdiv1) * @as(u128, m1); 666 const xy12 = @as(u128, qdiv1) * @as(u128, m2); 667 const xy13 = @as(u128, qdiv1) * @as(u128, m3); 668 const xy20 = @as(u128, qdiv2) * @as(u128, m0); 669 const xy21 = @as(u128, qdiv2) * @as(u128, m1); 670 const xy22 = @as(u128, qdiv2) * @as(u128, m2); 671 const xy30 = @as(u128, qdiv3) * @as(u128, m0); 672 const xy31 = @as(u128, qdiv3) * @as(u128, m1); 673 const xy40 = @as(u128, qdiv4) * @as(u128, m0); 674 const carry9 = xy00 >> 56; 675 const t108 = @truncate(u64, xy00) & 0xffffffffffffff; 676 const c0 = carry9; 677 const t010 = t108; 678 const carry10 = (xy01 + xy10 + c0) >> 56; 679 const t109 = @truncate(u64, xy01 + xy10 + c0) & 0xffffffffffffff; 680 const c11 = carry10; 681 const t110 = t109; 682 const carry11 = (xy02 + xy11 + xy20 + c11) >> 56; 683 const t1010 = @truncate(u64, xy02 + xy11 + xy20 + c11) & 0xffffffffffffff; 684 const c21 = carry11; 685 const t210 = t1010; 686 const carry = (xy03 + xy12 + xy21 + xy30 + c21) >> 56; 687 const t1011 = @truncate(u64, xy03 + xy12 + xy21 + xy30 + c21) & 0xffffffffffffff; 688 const c31 = carry; 689 const t310 = t1011; 690 const t411 = @truncate(u64, xy04 + xy13 + xy22 + xy31 + xy40 + c31) & 0xffffffffff; 691 692 const qmul0 = t010; 693 const qmul1 = t110; 694 const qmul2 = t210; 695 const qmul3 = t310; 696 const qmul4 = t411; 697 const b5 = (r0 -% qmul0) >> 63; 698 const t1012 = ((b5 << 56) + r0) -% qmul0; 699 const c1 = b5; 700 const t011 = t1012; 701 const b6 = (r1 -% (qmul1 + c1)) >> 63; 702 const t1013 = ((b6 << 56) + r1) -% (qmul1 + c1); 703 const c2 = b6; 704 const t111 = t1013; 705 const b7 = (r2 -% (qmul2 + c2)) >> 63; 706 const t1014 = ((b7 << 56) + r2) -% (qmul2 + c2); 707 const c3 = b7; 708 const t211 = t1014; 709 const b8 = (r3 -% (qmul3 + c3)) >> 63; 710 const t1015 = ((b8 << 56) + r3) -% (qmul3 + c3); 711 const c4 = b8; 712 const t311 = t1015; 713 const b9 = (r4 -% (qmul4 + c4)) >> 63; 714 const t1016 = ((b9 << 40) + r4) -% (qmul4 + c4); 715 const t412 = t1016; 716 const s0 = t011; 717 const s1 = t111; 718 const s2 = t211; 719 const s3 = t311; 720 const s4 = t412; 721 722 const y0: u64 = 5175514460705773; 723 const y1: u64 = 70332060721272408; 724 const y2: u64 = 5342; 725 const y3: u64 = 0; 726 const y4: u64 = 268435456; 727 728 const b10 = (s0 -% y0) >> 63; 729 const t1017 = ((b10 << 56) + s0) -% y0; 730 const b0 = b10; 731 const t01 = t1017; 732 const b11 = (s1 -% (y1 + b0)) >> 63; 733 const t1018 = ((b11 << 56) + s1) -% (y1 + b0); 734 const b1 = b11; 735 const t11 = t1018; 736 const b12 = (s2 -% (y2 + b1)) >> 63; 737 const t1019 = ((b12 << 56) + s2) -% (y2 + b1); 738 const b2 = b12; 739 const t21 = t1019; 740 const b13 = (s3 -% (y3 + b2)) >> 63; 741 const t1020 = ((b13 << 56) + s3) -% (y3 + b2); 742 const b3 = b13; 743 const t31 = t1020; 744 const b = (s4 -% (y4 + b3)) >> 63; 745 const t10 = ((b << 56) + s4) -% (y4 + b3); 746 const b4 = b; 747 const t41 = t10; 748 const mask = b4 -% @as(u64, @as(u64, 1)); 749 const z03 = s0 ^ (mask & (s0 ^ t01)); 750 const z13 = s1 ^ (mask & (s1 ^ t11)); 751 const z23 = s2 ^ (mask & (s2 ^ t21)); 752 const z33 = s3 ^ (mask & (s3 ^ t31)); 753 const z43 = s4 ^ (mask & (s4 ^ t41)); 754 755 return Scalar{ .limbs = .{ z03, z13, z23, z33, z43 } }; 756 } 757}; 758 759test "scalar25519" { 760 const bytes: [32]u8 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 255 }; 761 var x = Scalar.fromBytes(bytes); 762 var y = x.toBytes(); 763 try rejectNonCanonical(y); 764 var buf: [128]u8 = undefined; 765 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{s}", .{std.fmt.fmtSliceHexUpper(&y)}), "1E979B917937F3DE71D18077F961F6CEFF01030405060708010203040506070F"); 766 767 const reduced = reduce(field_size); 768 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{s}", .{std.fmt.fmtSliceHexUpper(&reduced)}), "0000000000000000000000000000000000000000000000000000000000000000"); 769} 770 771test "non-canonical scalar25519" { 772 const too_targe: [32]u8 = .{ 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 }; 773 try std.testing.expectError(error.NonCanonical, rejectNonCanonical(too_targe)); 774} 775 776test "mulAdd overflow check" { 777 const a: [32]u8 = [_]u8{0xff} ** 32; 778 const b: [32]u8 = [_]u8{0xff} ** 32; 779 const c: [32]u8 = [_]u8{0xff} ** 32; 780 const x = mulAdd(a, b, c); 781 var buf: [128]u8 = undefined; 782 try std.testing.expectEqualStrings(try std.fmt.bufPrint(&buf, "{s}", .{std.fmt.fmtSliceHexUpper(&x)}), "D14DF91389432C25AD60FF9791B9FD1D67BEF517D273ECCE3D9A307C1B419903"); 783} 784