1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
/*
`X25519` (aka `curve25519`) Elliptic-Curve Diffie-Hellman key exchange protocol.
See:
- [[ https://www.rfc-editor.org/rfc/rfc7748 ]]
*/
package x25519
import "core:crypto"
import ed "core:crypto/_edwards25519"
import field "core:crypto/_fiat/field_curve25519"
import "core:mem"
// SCALAR_SIZE is the size of a X25519 scalar (private key) in bytes.
SCALAR_SIZE :: 32
// POINT_SIZE is the size of a X25519 point (public key/shared secret) in bytes.
POINT_SIZE :: 32
when crypto.COMPACT_IMPLS == true {
@(private,rodata)
_BASE_POINT: [32]byte = {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}
@(private)
_scalar_bit :: #force_inline proc "contextless" (s: ^[32]byte, i: int) -> u8 {
if i < 0 {
return 0
}
return (s[i >> 3] >> uint(i & 7)) & 1
}
@(private)
_scalarmult :: proc "contextless" (out, scalar, point: ^[32]byte) {
// Montgomery pseduo-multiplication taken from Monocypher.
// computes the scalar product
x1: field.Tight_Field_Element = ---
field.fe_from_bytes(&x1, point)
// computes the actual scalar product (the result is in x2 and z2)
x2, x3, z2, z3: field.Tight_Field_Element = ---, ---, ---, ---
t0, t1: field.Loose_Field_Element = ---, ---
// Montgomery ladder
// In projective coordinates, to avoid divisions: x = X / Z
// We don't care about the y coordinate, it's only 1 bit of information
field.fe_one(&x2) // "zero" point
field.fe_zero(&z2)
field.fe_set(&x3, &x1) // "one" point
field.fe_one(&z3)
swap: int
for pos := 255 - 1; pos >= 0; pos = pos - 1 {
// constant time conditional swap before ladder step
b := int(_scalar_bit(scalar, pos))
swap ~= b // xor trick avoids swapping at the end of the loop
field.fe_cond_swap(&x2, &x3, swap)
field.fe_cond_swap(&z2, &z3, swap)
swap = b // anticipates one last swap after the loop
// Montgomery ladder step: replaces (P2, P3) by (P2*2, P2+P3)
// with differential addition
//
// Note: This deliberately omits reductions after add/sub operations
// if the result is only ever used as the input to a mul/square since
// the implementations of those can deal with non-reduced inputs.
//
// fe_tighten_cast is only used to store a fully reduced
// output in a Loose_Field_Element, or to provide such a
// Loose_Field_Element as a Tight_Field_Element argument.
field.fe_sub(&t0, &x3, &z3)
field.fe_sub(&t1, &x2, &z2)
field.fe_add(field.fe_relax_cast(&x2), &x2, &z2) // x2 - unreduced
field.fe_add(field.fe_relax_cast(&z2), &x3, &z3) // z2 - unreduced
field.fe_carry_mul(&z3, &t0, field.fe_relax_cast(&x2))
field.fe_carry_mul(&z2, field.fe_relax_cast(&z2), &t1) // z2 - reduced
field.fe_carry_square(field.fe_tighten_cast(&t0), &t1) // t0 - reduced
field.fe_carry_square(field.fe_tighten_cast(&t1), field.fe_relax_cast(&x2)) // t1 - reduced
field.fe_add(field.fe_relax_cast(&x3), &z3, &z2) // x3 - unreduced
field.fe_sub(field.fe_relax_cast(&z2), &z3, &z2) // z2 - unreduced
field.fe_carry_mul(&x2, &t1, &t0) // x2 - reduced
field.fe_sub(&t1, field.fe_tighten_cast(&t1), field.fe_tighten_cast(&t0)) // safe - t1/t0 is reduced
field.fe_carry_square(&z2, field.fe_relax_cast(&z2)) // z2 - reduced
field.fe_carry_scmul_121666(&z3, &t1)
field.fe_carry_square(&x3, field.fe_relax_cast(&x3)) // x3 - reduced
field.fe_add(&t0, field.fe_tighten_cast(&t0), &z3) // safe - t0 is reduced
field.fe_carry_mul(&z3, field.fe_relax_cast(&x1), field.fe_relax_cast(&z2))
field.fe_carry_mul(&z2, &t1, &t0)
}
// last swap is necessary to compensate for the xor trick
// Note: after this swap, P3 == P2 + P1.
field.fe_cond_swap(&x2, &x3, swap)
field.fe_cond_swap(&z2, &z3, swap)
// normalises the coordinates: x == X / Z
field.fe_carry_inv(&z2, field.fe_relax_cast(&z2))
field.fe_carry_mul(&x2, field.fe_relax_cast(&x2), field.fe_relax_cast(&z2))
field.fe_to_bytes(out, &x2)
field.fe_clear_vec([]^field.Tight_Field_Element{&x1, &x2, &x3, &z2, &z3})
field.fe_clear_vec([]^field.Loose_Field_Element{&t0, &t1})
}
// scalarmult "multiplies" the provided scalar and point, and writes the
// resulting point to dst.
scalarmult :: proc(dst, scalar, point: []byte) {
ensure(len(scalar) == SCALAR_SIZE, "crypto/x25519: invalid scalar size")
ensure(len(point) == POINT_SIZE, "crypto/x25519: invalid point size")
ensure(len(dst) == POINT_SIZE, "crypto/x25519: invalid destination point size")
// "clamp" the scalar
e: [32]byte = ---
copy_slice(e[:], scalar)
e[0] &= 248
e[31] &= 127
e[31] |= 64
p := (^[32]byte)(raw_data(point))
d := (^[32]byte)(raw_data(dst))
_scalarmult(d, &e, p)
mem.zero_explicit(&e, size_of(e))
}
// scalarmult_basepoint "multiplies" the provided scalar with the X25519
// base point and writes the resulting point to dst.
scalarmult_basepoint :: proc(dst, scalar: []byte) {
when crypto.COMPACT_IMPLS == true {
scalarmult(dst, scalar, _BASE_POINT[:])
} else {
ensure(len(scalar) == SCALAR_SIZE, "crypto/x25519: invalid scalar size")
ensure(len(dst) == POINT_SIZE, "crypto/x25519: invalid destination point size")
sc: ed.Scalar = ---
ed.sc_set_bytes_rfc8032(&sc, scalar)
ge: ed.Group_Element = ---
ed.ge_scalarmult_basepoint(&ge, &sc)
// u = (y + z)/(z - y)
y_plus_z: field.Loose_Field_Element = ---
z_minus_y: field.Loose_Field_Element = ---
u: field.Tight_Field_Element = ---
field.fe_add(&y_plus_z, &ge.y, &ge.z)
field.fe_sub(&z_minus_y, &ge.z, &ge.y)
field.fe_carry_inv(&u, &z_minus_y)
field.fe_carry_mul(&u, &y_plus_z, field.fe_relax_cast(&u))
dst_ := (^[32]byte)(raw_data(dst))
field.fe_to_bytes(dst_, &u)
field.fe_clear_vec([]^field.Loose_Field_Element{&y_plus_z, &z_minus_y})
field.fe_clear(&u)
ed.sc_clear(&sc)
ed.ge_clear(&ge)
}
}
|
