1 /*############################################################################
2 # Copyright 2017 Intel Corporation
3 #
4 # Licensed under the Apache License, Version 2.0 (the "License");
5 # you may not use this file except in compliance with the License.
6 # You may obtain a copy of the License at
7 #
8 # http://www.apache.org/licenses/LICENSE-2.0
9 #
10 # Unless required by applicable law or agreed to in writing, software
11 # distributed under the License is distributed on an "AS IS" BASIS,
12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
15 ############################################################################*/
16 /// Unit tests of Fq implementation.
17 /*! \file */
18
19 #include <gtest/gtest.h>
20
21 #include "epid/member/tiny/math/unittests/cmp-testhelper.h"
22 #include "epid/member/tiny/math/unittests/onetimepad.h"
23
24 extern "C" {
25 #include "epid/member/tiny/math/fq.h"
26 #include "epid/member/tiny/math/mathtypes.h"
27 }
28
29 namespace {
30
31 ////////////////////////////////////////////////////////////////////////
32 // FqInField
33
TEST(TinyFqTest,FqInFieldPasses)34 TEST(TinyFqTest, FqInFieldPasses) {
35 FqElem zero = {0};
36 FqElem q_minus_one = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
37 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
38 EXPECT_TRUE(FqInField(&zero));
39 EXPECT_TRUE(FqInField(&q_minus_one));
40 }
41
TEST(TinyFqTest,FqInFieldFails)42 TEST(TinyFqTest, FqInFieldFails) {
43 FqElem q = {{0xAED33013, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
44 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
45 EXPECT_FALSE(FqInField(&q));
46 }
47
48 ////////////////////////////////////////////////////////////////////////
49 // FqAdd
50
TEST(TinyFqTest,FqAddWorks)51 TEST(TinyFqTest, FqAddWorks) {
52 FqElem result = {0}, expected = {0}, left = {0}, right = {0};
53 left.limbs.word[5] = 1;
54 right.limbs.word[5] = 2;
55 expected.limbs.word[5] = 3;
56 FqAdd(&result, &left, &right);
57 EXPECT_EQ(expected, result);
58
59 FqElem q_minus_one = {0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
60 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF};
61 right = {2, 0, 0, 0, 0, 0, 0, 0};
62 expected = {1, 0, 0, 0, 0, 0, 0, 0};
63 FqAdd(&result, &q_minus_one, &right);
64 EXPECT_EQ(expected, result);
65 }
66
67 ////////////////////////////////////////////////////////////////////////
68 // FqSub
69
TEST(TinyFqTest,FqSubWorks)70 TEST(TinyFqTest, FqSubWorks) {
71 FqElem result = {0}, expected = {0}, left = {0}, right = {0};
72 left.limbs.word[4] = 2;
73 right.limbs.word[4] = 1;
74 expected.limbs.word[4] = 1;
75 FqSub(&result, &left, &right);
76 EXPECT_EQ(expected, result);
77
78 left = {1, 0, 0, 0, 0, 0, 0, 0};
79 right = {2, 0, 0, 0, 0, 0, 0, 0};
80 FqElem q_minus_one = {0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
81 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF};
82 FqSub(&result, &left, &right);
83 EXPECT_EQ(q_minus_one, result);
84 }
85
86 ////////////////////////////////////////////////////////////////////////
87 // FqMul
88
TEST(TinyFqTest,FqMulWorks)89 TEST(TinyFqTest, FqMulWorks) {
90 FqElem left = {0x22cfd6a2, 0x23e82f1e, 0xd50e1450, 0xe853e88c,
91 0xafa65357, 0x4780716c, 0xffd94b0f, 0x5e643124};
92 FqElem right = {0x848cdb73, 0x6399829e, 0xcaa20cc0, 0x1b02bff6,
93 0x2b477bd2, 0xf9d48534, 0xff7929a0, 0xd4745161};
94 FqElem expected = {0x28f2f1dd, 0x2cb2b611, 0xa24767b3, 0x4e880c0e,
95 0xed7f7b9e, 0x6ff4a7f2, 0x25fb15d0, 0x7b8c4fed};
96 FqElem result = {0};
97 FqMul(&result, &left, &right);
98 EXPECT_EQ(expected, result);
99 }
100
101 ////////////////////////////////////////////////////////////////////////
102 // FqExp
TEST(TinyFqTest,FqExpWorks)103 TEST(TinyFqTest, FqExpWorks) {
104 FqElem result = {0}, expected = {0}, in = {0};
105 VeryLargeInt exp = {0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
106 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF};
107 in.limbs.word[0] = 1;
108 expected.limbs.word[0] = 1;
109 FqExp(&result, &in, &exp);
110 EXPECT_EQ(expected, result);
111
112 exp = {4, 0, 0, 0, 0, 0, 0, 0};
113 in = {{0x0000007B, 0, 0, 0, 0, 0, 0, 0}};
114 expected = {{0x0DA48871, 0, 0, 0, 0, 0, 0, 0}};
115 FqExp(&result, &in, &exp);
116 EXPECT_EQ(expected, result);
117 }
118
119 ////////////////////////////////////////////////////////////////////////
120 // FqCp
121
TEST(TinyFqTest,FqCpWorks)122 TEST(TinyFqTest, FqCpWorks) {
123 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
124 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
125 FqElem result = {0};
126 FqCp(&result, &a);
127 EXPECT_EQ(a, result);
128 }
129
130 ////////////////////////////////////////////////////////////////////////
131 // FqIsZero
132
TEST(TinyFqTest,FqIsZeroPasses)133 TEST(TinyFqTest, FqIsZeroPasses) {
134 FqElem zero = {0};
135 EXPECT_TRUE(FqIsZero(&zero));
136 }
137
TEST(TinyFqTest,FqIsZeroFails)138 TEST(TinyFqTest, FqIsZeroFails) {
139 FqElem non_zero = {{0, 0, 0, 0, 0, 0, 1, 0}};
140 EXPECT_FALSE(FqIsZero(&non_zero));
141 }
142
143 ////////////////////////////////////////////////////////////////////////
144 // FqInv
145
TEST(TinyFqTest,FqInvWorks)146 TEST(TinyFqTest, FqInvWorks) {
147 FqElem a = {{0x76abb18a, 0x92c0f7b9, 0x2c1a37e0, 0x7fdf6ca1, 0xe3401760,
148 0x66eb7d52, 0x918d50a7, 0x12a65bd6}};
149 FqElem expected = {{0x5a686df6, 0x56b6ab63, 0xdf907c6f, 0x44ad8d51,
150 0xa5513462, 0xc597ef78, 0x93711b39, 0x15171a1e}};
151 FqElem result;
152 FqInv(&result, &a);
153 EXPECT_EQ(result, expected);
154 }
155
156 ////////////////////////////////////////////////////////////////////////
157 // FqNeg
TEST(TinyFqTest,FqNegWorks)158 TEST(TinyFqTest, FqNegWorks) {
159 FqElem const pairing_q = {{0xAED33013, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
160 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
161 FqElem neg_value = {0};
162 FqElem one = {{1, 0, 0, 0, 0, 0, 0, 0}};
163 FqElem minus_one = pairing_q;
164 --minus_one.limbs.word[0];
165 FqNeg(&neg_value, &one);
166 EXPECT_EQ(minus_one, neg_value);
167
168 FqElem value = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
169 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
170 FqNeg(&neg_value, &value);
171 FqNeg(&neg_value, &neg_value);
172 EXPECT_EQ(value, neg_value);
173 }
174
175 ////////////////////////////////////////////////////////////////////////
176 // FqSquare
177
TEST(TinyFqTest,FqSquareWorks)178 TEST(TinyFqTest, FqSquareWorks) {
179 FqElem const pairing_q = {{0xAED33013, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
180 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
181 FqElem four = {{4, 0, 0, 0, 0, 0, 0, 0}}, result = {0};
182 FqElem minus_two = pairing_q;
183 minus_two.limbs.word[0] -= 2;
184 FqSquare(&result, &minus_two);
185 EXPECT_EQ(four, result);
186
187 FqElem in = {{0x00003039, 0, 0, 0, 0, 0, 0, 0}};
188 FqElem expected = {{0x09156CB1, 0, 0, 0, 0, 0, 0, 0}};
189 FqSquare(&result, &in);
190 EXPECT_EQ(expected, result);
191 }
192
193 ////////////////////////////////////////////////////////////////////////
194 // FqClear
195
TEST(TinyFqTest,FqClearWorks)196 TEST(TinyFqTest, FqClearWorks) {
197 FqElem zero = {0};
198 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
199 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
200 FqClear(&a);
201 EXPECT_EQ(zero, a);
202 }
203
204 ////////////////////////////////////////////////////////////////////////
205 // FqSet
206
TEST(TinyFqTest,FqSetWorks)207 TEST(TinyFqTest, FqSetWorks) {
208 uint32_t small = 0xffffffff;
209 FqElem expected = {{small, 0, 0, 0, 0, 0, 0, 0}};
210 FqElem result = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
211 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
212 FqSet(&result, small);
213 EXPECT_EQ(expected, result);
214 }
215
216 ////////////////////////////////////////////////////////////////////////
217 // FqEq
218
TEST(TinyFqTest,FqEqPasses)219 TEST(TinyFqTest, FqEqPasses) {
220 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
221 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
222 FqElem c = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
223 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
224 EXPECT_TRUE(FqEq(&a, &c));
225 }
226
TEST(TinyFqTest,FqEqFails)227 TEST(TinyFqTest, FqEqFails) {
228 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
229 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
230 FqElem b = {{0, 0, 0, 0, 0, 0, 1, 0}};
231 EXPECT_FALSE(FqEq(&a, &b));
232 }
233
234 ////////////////////////////////////////////////////////////////////////
235 // FqCondSet
236
TEST(TinyFqTest,FqCondSetWorksForTrue)237 TEST(TinyFqTest, FqCondSetWorksForTrue) {
238 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
239 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
240 FqElem b = {{0, 0, 0, 0, 0, 0, 1, 0}};
241 FqElem result = {0};
242 FqCondSet(&result, &a, &b, true);
243 EXPECT_EQ(a, result);
244 }
245
TEST(TinyFqTest,FqCondSetWorksForFalse)246 TEST(TinyFqTest, FqCondSetWorksForFalse) {
247 FqElem a = {{0xAED33012, 0xD3292DDB, 0x12980A82, 0x0CDC65FB, 0xEE71A49F,
248 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF}};
249 FqElem b = {{0, 0, 0, 0, 0, 0, 1, 0}};
250 FqElem result = {0};
251 FqCondSet(&result, &a, &b, false);
252 EXPECT_EQ(b, result);
253 }
254
255 ////////////////////////////////////////////////////////////////////////
256 // FqSqrt
257
TEST(TinyFqTest,FqSqrtWorks)258 TEST(TinyFqTest, FqSqrtWorks) {
259 FqElem actual = {0};
260 FqElem in = {0x02869F4A, 0xDF28D8AC, 0x2B4BD20F, 0xB158EA77,
261 0x89D86073, 0x4D6F2CE1, 0x0211F496, 0x9C977A80};
262 FqElem expected = {0x0E41765B, 0x7E2AEDF6, 0x7C01BC1B, 0xB1C0F3E4,
263 0x95CB5637, 0x8B275494, 0x3FBF1556, 0x8DAE1450};
264
265 EXPECT_TRUE(FqSqrt(&actual, &in));
266 EXPECT_EQ(expected, actual);
267 }
TEST(TinyFqTest,FqSqrtWorksForFour)268 TEST(TinyFqTest, FqSqrtWorksForFour) {
269 FqElem actual = {0};
270 FqElem in = {0x00000004, 0x00000000, 0x00000000, 0x00000000,
271 0x00000000, 0x00000000, 0x00000000, 0x00000000};
272 FqElem expected = {0xAED33011, 0xD3292DDB, 0x12980A82, 0x0CDC65FB,
273 0xEE71A49F, 0x46E5F25E, 0xFFFCF0CD, 0xFFFFFFFF};
274 EXPECT_TRUE(FqSqrt(&actual, &in));
275 EXPECT_EQ(expected, actual);
276 }
TEST(TinyFqTest,FqSqrtFailsForFive)277 TEST(TinyFqTest, FqSqrtFailsForFive) {
278 FqElem actual = {0};
279 FqElem in = {0x00000005, 0x00000000, 0x00000000, 0x00000000,
280 0x00000000, 0x00000000, 0x00000000, 0x00000000};
281 EXPECT_FALSE(FqSqrt(&actual, &in));
282 }
283 ////////////////////////////////////////////////////////////////////////
284 // FqRand
285
TEST(TinyFqTest,FqRandConsumes384BitsOfEntropy)286 TEST(TinyFqTest, FqRandConsumes384BitsOfEntropy) {
287 OneTimePad otp(64);
288 FqElem actual = {0};
289 EXPECT_TRUE(FqRand(&actual, OneTimePad::Generate, &otp));
290 EXPECT_EQ(384u, otp.BitsConsumed());
291 }
292
TEST(TinyFqTest,FqRandWorks)293 TEST(TinyFqTest, FqRandWorks) {
294 OneTimePad otp({// slen bits
295 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
296 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
297 // q + 1
298 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, 0xF0, 0xCD, 0x46, 0xE5,
299 0xF2, 0x5E, 0xEE, 0x71, 0xA4, 0x9F, 0x0C, 0xDC, 0x65, 0xFB,
300 0x12, 0x98, 0x0A, 0x82, 0xD3, 0x29, 0x2D, 0xDB, 0xAE, 0xD3,
301 0x30, 0x14});
302 FqElem expected = {{1, 0, 0, 0, 0, 0, 0, 0}};
303 FqElem actual = {0};
304 EXPECT_TRUE(FqRand(&actual, OneTimePad::Generate, &otp));
305 EXPECT_EQ(expected, actual);
306 }
307
308 ////////////////////////////////////////////////////////////////////////
309 // FqFromHash
310
TEST(TinyFqTest,FqFromHashWorks)311 TEST(TinyFqTest, FqFromHashWorks) {
312 FqElem q_mod_q;
313 FqElem zero = {0};
314 uint8_t q_str[32] = {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, 0xF0, 0xCD,
315 0x46, 0xE5, 0xF2, 0x5E, 0xEE, 0x71, 0xA4, 0x9F,
316 0x0C, 0xDC, 0x65, 0xFB, 0x12, 0x98, 0x0A, 0x82,
317 0xD3, 0x29, 0x2D, 0xDB, 0xAE, 0xD3, 0x30, 0x13};
318 FqFromHash(&q_mod_q, q_str, sizeof(q_str));
319 EXPECT_EQ(zero, q_mod_q);
320
321 FqElem one = {{1, 0, 0, 0, 0, 0, 0, 0}};
322 uint8_t one_str[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
323 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
324 FqElem one_mod_q;
325 FqFromHash(&one_mod_q, one_str, sizeof(one_str));
326 EXPECT_EQ(one, one_mod_q);
327 }
328
329 } // namespace
330