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