Debian Codegraph @

dh/sidh/internal/templates/curve_test.gotemp

raw
1 // Code generated by go generate; DO NOT EDIT.
2 // This file was generated by robots.
3
4 package {{.PACKAGE}}
5
6 import (
7 "bytes"
8 "testing"
9 "math"
10 "math/rand"
11 crand "crypto/rand"
12 "io"
13 . "github.com/cloudflare/circl/dh/sidh/internal/common"
14 "time"
15 )
16
17 func vartimeEqProjFp2(lhs, rhs *ProjectivePoint) bool {
18 var t0, t1 Fp2
19 mul(&t0, &lhs.X, &rhs.Z)
20 mul(&t1, &lhs.Z, &rhs.X)
21 return vartimeEqFp2(&t0, &t1)
22 }
23
24 func toAffine(point *ProjectivePoint) *Fp2 {
25 var affineX Fp2
26 inv(&affineX, &point.Z)
27 mul(&affineX, &affineX, &point.X)
28 return &affineX
29 }
30
31 func Test_jInvariant(t *testing.T) {
32 curve := ProjectiveCurveParameters{A: curveA, C: curveC}
33 jbufRes := make([]byte, params.SharedSecretSize)
34 jbufExp := make([]byte, params.SharedSecretSize)
35 var jInv Fp2
36
37 Jinvariant(&curve, &jInv)
38 FromMontgomery(&jInv, &jInv)
39 Fp2ToBytes(jbufRes, &jInv, params.Bytelen)
40
41 jInv = expectedJ
42 FromMontgomery(&jInv, &jInv)
43 Fp2ToBytes(jbufExp, &jInv, params.Bytelen)
44
45 if !bytes.Equal(jbufRes[:], jbufExp[:]) {
46 t.Error("Computed incorrect j-invariant: found\n", jbufRes, "\nexpected\n", jbufExp)
47 }
48 }
49
50 func TestProjectivePointVartimeEq(t *testing.T) {
51 var xP ProjectivePoint
52
53 xP = ProjectivePoint{X: affineXP, Z: params.OneFp2}
54 xQ := xP
55
56 // Scale xQ, which results in the same projective point
57 mul(&xQ.X, &xQ.X, &curveA)
58 mul(&xQ.Z, &xQ.Z, &curveA)
59 if !vartimeEqProjFp2(&xP, &xQ) {
60 t.Error("Expected the scaled point to be equal to the original")
61 }
62 }
63
64 func TestPointMulVersusSage(t *testing.T) {
65 curve := ProjectiveCurveParameters{A: curveA, C: curveC}
66 cparams := CalcCurveParamsEquiv4(&curve)
67 var xP ProjectivePoint
68
69 // x 2
70 xP = ProjectivePoint{X: affineXP, Z: params.OneFp2}
71 Pow2k(&xP, &cparams, 1)
72 afxQ := toAffine(&xP)
73 if !vartimeEqFp2(afxQ, &affineXP2) {
74 t.Error("\nExpected\n", affineXP2, "\nfound\n", afxQ)
75 }
76
77 // x 4
78 xP = ProjectivePoint{X: affineXP, Z: params.OneFp2}
79 Pow2k(&xP, &cparams, 2)
80 afxQ = toAffine(&xP)
81 if !vartimeEqFp2(afxQ, &affineXP4) {
82 t.Error("\nExpected\n", affineXP4, "\nfound\n", afxQ)
83 }
84 }
85
86 func TestPointMul9VersusSage(t *testing.T) {
87 curve := ProjectiveCurveParameters{A: curveA, C: curveC}
88 cparams := CalcCurveParamsEquiv3(&curve)
89 var xP ProjectivePoint
90
91 xP = ProjectivePoint{X: affineXP, Z: params.OneFp2}
92 Pow3k(&xP, &cparams, 2)
93 afxQ := toAffine(&xP)
94 if !vartimeEqFp2(afxQ, &affineXP9) {
95 t.Error("\nExpected\n", affineXP9, "\nfound\n", afxQ)
96 }
97 }
98
99 func BenchmarkThreePointLadder(b *testing.B) {
100 curve := ProjectiveCurveParameters{A: curveA, C: curveC}
101 for n := 0; n < b.N; n++ {
102 ScalarMul3Pt(&curve, &threePointLadderInputs[0], &threePointLadderInputs[1], &threePointLadderInputs[2], uint(len(scalar3Pt)*8), scalar3Pt[:])
103 }
104 }
105
106 /* -------------------------------------------------------------------------
107 Generate invalid public key points / ciphertext for test TestKEMInvalidPK
108 -------------------------------------------------------------------------*/
109
110 // Left-to-right Montgomery ladder, Algorithm 4 in Costello-Smith
111 // Input: ProjectivePoint P (xP, zP)
112 // Output: x([scalar]P), z([scalar]P)
113 func montgomeryLadder(cparams *ProjectiveCurveParameters, P *ProjectivePoint, scalar []uint8, random uint) ProjectivePoint {
114 var R0, R2, R1 ProjectivePoint
115 coefEq := CalcCurveParamsEquiv4(cparams) // for xDbl
116 aPlus2Over4 := CalcAplus2Over4(cparams) // for xDblAdd
117 R0 = *P // RO <- P
118 R1 = *P
119 Pow2k(&R1, &coefEq, 1) // R1 <- [2]P
120 R2 = *P // R2 = R1-R0 = P
121
122 prevBit := uint8(0)
123 for i := int(random); i >= 0; i-- {
124 bit := (scalar[i>>3] >> (i & 7) & 1)
125 swap := prevBit ^ bit
126 prevBit = bit
127 cswap(&R0.X, &R0.Z, &R1.X, &R1.Z, swap)
128 R0, R1 = xDbladd(&R0, &R1, &R2, &aPlus2Over4)
129 }
130 cswap(&R0.X, &R0.Z, &R1.X, &R1.Z, prevBit)
131 return R0
132 }
133
134 // P = P + T
135 // From paper https://eprint.iacr.org/2017/212.pdf
136 // The map tau_T: P->P+T is (X : Z) -> (Z : X) on Montgomery curves
137 func tauT(P *ProjectivePoint) {
138 P.X, P.Z = P.Z, P.X // magic!
139 }
140
141 // Construct Invalid public key tuple (P,Q) such that P and Q are linearly dependent
142 // Simulate section 3.1.1 of paper https://eprint.iacr.org/2022/054.pdf
143 // We only construct point P and Q because in the attacks the third point is P-Q by construction
144 // and the countermeasure does not test it
145 // Without loss of generality, we assume the curve is the starting curve
146 func testInvalidPKNoneLinear(t *testing.T) {
147
148 // Generate random scalar as secret
149 secret := make([]byte, params.B.SecretByteLen)
150 _, err := io.ReadFull(crand.Reader, secret)
151 if err != nil{
152 t.Error("Fail read random bytes")
153 }
154
155 var P, Q ProjectivePoint
156
157 rand.Seed(time.Now().UnixNano())
158 random_index := rand.Intn(int(params.B.SecretByteLen-1)*8)
159
160 // Set P as a point of order 3^e3
161 P = ProjectivePoint{X: params.B.AffineP, Z: params.OneFp2}
162
163 // Set Q = [k]P, where k = secret[:random_index]
164 Q = montgomeryLadder(&params.InitCurve, &P, secret, uint(random_index))
165
166 // Make sure Q is of full order 3^e_3,
167 var test_Q ProjectivePoint
168 test_Q = Q
169
170 var e3 uint32
171 e3_float := float64(int(params.B.SecretBitLen)+1)/math.Log2(3)
172 e3 = uint32(e3_float)
173 cparam_q := CalcCurveParamsEquiv3(&params.InitCurve)
174 Pow3k(&test_Q, &cparam_q, e3-1)
175
176 var test_QZ Fp2
177 FromMontgomery(&test_QZ, &test_Q.Z)
178
179 // Q are not of full order 3^e_3
180 for((isZero(&test_QZ)==1)){
181 rand.Seed(time.Now().UnixNano())
182 random_index = rand.Intn(int(params.B.SecretByteLen-1)*8)
183 Q = montgomeryLadder(&params.InitCurve, &P, secret, uint(random_index))
184 test_Q = Q
185 Pow3k(&test_Q, &cparam_q, e3-1)
186 FromMontgomery(&test_QZ, &test_Q.Z)
187 }
188
189 // invQz = 1/Q.Z
190 var invQz Fp2
191 invQz = Q.Z
192 inv(&invQz, &invQz)
193
194 mul(&P.X, &P.X, &P.Z)
195 mul(&Q.X, &Q.X, &invQz)
196
197 var xP, xQ, xQmP ProjectivePoint
198 xP = ProjectivePoint{X: P.X, Z: params.OneFp2}
199 xQ = ProjectivePoint{X: Q.X, Z: params.OneFp2}
200 xQmP = ProjectivePoint{X: params.OneFp2, Z: params.OneFp2}
201
202 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
203 if error_verify==nil{
204 t.Errorf("\nExpect linearly dependent ciphertext to fail, index: %v scalar: %v ", random_index, secret)
205 }
206 }
207
208 // Construct Invalid public key tuple (P,Q) such that Q = [k]P + T, where k is random and T is the point of order 2.
209 // Simulate HB and section 3.1.2 of paper https://eprint.iacr.org/2022/054.pdf
210 // We only construct point P and Q because in the attacks the third point is P-Q by construction
211 // and the countermeasure does not test it
212 // Without loss of generality, we assume the curve is the starting curve
213 func testInvalidPKT(t *testing.T) {
214
215 // Generate random scalar as secret
216 secret := make([]byte, params.B.SecretByteLen)
217 _, err := io.ReadFull(crand.Reader, secret)
218 if err != nil{
219 t.Error("Fail read random bytes")
220 }
221
222
223 var P, Q ProjectivePoint
224
225 rand.Seed(time.Now().UnixNano())
226 random_index := rand.Intn(int(params.B.SecretByteLen-1)*8)
227
228 // Set P as a point of order 3^e3
229 P = ProjectivePoint{X: params.B.AffineP, Z: params.OneFp2}
230
231 // Set Q = [k]P, where k = secret[:random_index]
232 Q = montgomeryLadder(&params.InitCurve, &P, secret, uint(random_index))
233 // Q = [k]P + T
234 tauT(&Q)
235
236 var invQz Fp2
237 invQz = Q.Z
238 inv(&invQz, &invQz)
239
240 mul(&P.X, &P.X, &P.Z)
241 mul(&Q.X, &Q.X, &invQz)
242
243 var xP, xQ, xQmP ProjectivePoint
244 xP = ProjectivePoint{X: P.X, Z: params.OneFp2}
245 xQ = ProjectivePoint{X: Q.X, Z: params.OneFp2}
246 xQmP = ProjectivePoint{X: params.OneFp2, Z: params.OneFp2}
247
248 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
249 if error_verify==nil{
250 t.Errorf("\nExpect ciphertext involve point T to fail, index: %v scalar: %v ", random_index, secret)
251 }
252 }
253
254
255 // Construct Invalid public key tuple (P,Q) such that P and Q are in E[2^e2]
256 // Simulate section 3.2 of paper https://eprint.iacr.org/2022/054.pdf
257 // We only construct point P and Q because in the attacks the third point is P-Q by construction
258 // and the countermeasure does not test it
259 // Without loss of generality, we assume the curve is the starting curve
260 func testInvalidPKOrder2(t *testing.T) {
261
262 // Generate random scalar as secret
263 secret := make([]byte, params.B.SecretByteLen)
264 _, err := io.ReadFull(crand.Reader, secret)
265 if err != nil{
266 t.Error("Fail read random bytes")
267 }
268
269
270 var P, Q ProjectivePoint
271
272 P = ProjectivePoint{X: params.A.AffineP, Z: params.OneFp2}
273 Q = ProjectivePoint{X: params.A.AffineQ, Z: params.OneFp2}
274
275 rand.Seed(time.Now().UnixNano())
276 random_index_p := rand.Intn(int(params.A.SecretByteLen-1)*8)
277 random_index_q := rand.Intn(int(params.A.SecretByteLen-1)*8)
278
279 P = montgomeryLadder(&params.InitCurve, &P, secret, uint(random_index_p))
280 Q = montgomeryLadder(&params.InitCurve, &Q, secret, uint(random_index_q))
281
282 var invQz, invPz Fp2
283 invQz = Q.Z
284 invPz = P.Z
285 inv(&invQz, &invQz)
286 inv(&invPz, &invPz)
287
288 mul(&P.X, &P.X, &invPz)
289 mul(&Q.X, &Q.X, &invQz)
290
291 var xP, xQ, xQmP ProjectivePoint
292 xP = ProjectivePoint{X: P.X, Z: params.OneFp2}
293 xQ = ProjectivePoint{X: Q.X, Z: params.OneFp2}
294 xQmP = ProjectivePoint{X: params.OneFp2, Z: params.OneFp2}
295
296 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
297 if error_verify==nil{
298 t.Errorf("\nExpect ciphertext in torsion E[2^e2] to fail, index_p: %v index_q: %v scalar: %v ", random_index_p, random_index_q, secret)
299 }
300
301 }
302
303
304 // Construct Invalid public key tuple (P,Q) such that P and Q are in E[3^e3] but not of full order 3^e3
305 // Simulate section 3.1.1 of paper https://eprint.iacr.org/2022/054.pdf
306 // We only construct point P and Q because in the attacks the third point is P-Q by construction
307 // and the countermeasure does not test it
308 // Without loss of generality, we assume the curve is the starting curve
309 func testInvalidPKFullOrder(t *testing.T) {
310
311 var P, Q ProjectivePoint
312
313 P = ProjectivePoint{X: params.B.AffineP, Z: params.OneFp2}
314 Q = ProjectivePoint{X: params.B.AffineQ, Z: params.OneFp2}
315
316 var e3 uint32
317 e3_float := float64(int(params.B.SecretBitLen)+1)/math.Log2(3)
318 e3 = uint32(e3_float)
319
320 rand.Seed(time.Now().UnixNano())
321 random_index_p := rand.Intn(int(e3))
322 random_index_q := rand.Intn(int(e3))
323
324 cparam_q := CalcCurveParamsEquiv3(&params.InitCurve)
325 Pow3k(&P, &cparam_q, uint32(random_index_p))
326 Pow3k(&Q, &cparam_q, uint32(random_index_q))
327
328
329 var invQz, invPz Fp2
330 invQz = Q.Z
331 invPz = P.Z
332 inv(&invQz, &invQz)
333 inv(&invPz, &invPz)
334
335 mul(&P.X, &P.X, &invPz)
336 mul(&Q.X, &Q.X, &invQz)
337
338 var xP, xQ, xQmP ProjectivePoint
339 xP = ProjectivePoint{X: P.X, Z: params.OneFp2}
340 xQ = ProjectivePoint{X: Q.X, Z: params.OneFp2}
341 xQmP = ProjectivePoint{X: params.OneFp2, Z: params.OneFp2}
342
343 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
344 if error_verify==nil{
345 t.Errorf("\nExpect ciphertext not of full order to fail, index_p: %v index_q: %v ", random_index_p, random_index_q)
346 }
347
348 }
349
350 // A trivial test case not covered by paper https://eprint.iacr.org/2022/054.pdf and HB
351 // Countermeasure in https://eprint.iacr.org/2022/054.pdf only cares about P and Q
352 // But if PmQ is point T or O, that can also lead to recovery of the first bit
353 func testInvalidPmQ(t *testing.T) {
354
355 var zero Fp2
356 var xP, xQ, xQmP ProjectivePoint
357 xP = ProjectivePoint{X: params.A.AffineP, Z: params.OneFp2}
358 xQ = ProjectivePoint{X: params.A.AffineQ, Z: params.OneFp2}
359 xQmP = ProjectivePoint{X: zero, Z: params.OneFp2}
360
361 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
362 if error_verify==nil{
363 t.Errorf("\nExpect PmQ as T to fail\n")
364 }
365
366 }
367
368 // Test valid ciphertext
369 // Where P, Q are linearly independent points of correct order 3^e3 in E[3^e3]
370 func testValidPQ(t *testing.T) {
371
372 var xP, xQ, xQmP ProjectivePoint
373 xP = ProjectivePoint{X: params.B.AffineP, Z: params.OneFp2}
374 xQ = ProjectivePoint{X: params.B.AffineQ, Z: params.OneFp2}
375 xQmP = ProjectivePoint{X: params.OneFp2, Z: params.OneFp2}
376
377 error_verify := PublicKeyValidation(&params.InitCurve, &xP, &xQ, &xQmP, params.B.SecretBitLen)
378 if error_verify!=nil{
379 t.Errorf("\nExpect correct ciphertext to not fail\n")
380 }
381
382 }
383
384
385 /* -------------------------------------------------------------------------
386 Public key / Ciphertext validation against attacks proposed in paper https://eprint.iacr.org/2022/054.pdf and HB
387 -------------------------------------------------------------------------*/
388
389 func TestInvalidPK(t *testing.T) {
390
391 t.Run("InvalidPmQ", testInvalidPmQ)
392 t.Run("InvalidPKNoneLinear", testInvalidPKNoneLinear)
393 t.Run("InvalidPKT", testInvalidPKT)
394 t.Run("InvalidPKOrder2", testInvalidPKOrder2)
395 t.Run("InvalidPKFullOrder", testInvalidPKFullOrder)
396 t.Run("ValidPQ", testValidPQ)
397
398 }