1 /******************************************************************************
2 *
3 * Copyright 2022 The Android Open Source Project
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at:
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 ******************************************************************************/
18
19 /******************************************************************************
20 * IMPORTANT
21 *
22 * These cryptography methods do not provide any security or correctness
23 * ensurance.
24 * They should be used only in Bluetooth emulation, not including any production
25 * environment.
26 *
27 ******************************************************************************/
28
29 use num_bigint::{BigInt, Sign};
30 use num_integer::Integer;
31 use num_traits::{One, Signed, Zero};
32 use rand::{thread_rng, Rng};
33 use std::convert::TryInto;
34 use std::marker::PhantomData;
35
36 #[derive(Debug, Clone, PartialEq, Eq)]
37 pub enum PublicKey {
38 P192([u8; P192r1::PUBLIC_KEY_SIZE]),
39 P256([u8; P256r1::PUBLIC_KEY_SIZE]),
40 }
41
42 impl PublicKey {
new(size: usize) -> Option<Self>43 pub fn new(size: usize) -> Option<Self> {
44 match size {
45 P192r1::PUBLIC_KEY_SIZE => Some(Self::P192([0; P192r1::PUBLIC_KEY_SIZE])),
46 P256r1::PUBLIC_KEY_SIZE => Some(Self::P256([0; P256r1::PUBLIC_KEY_SIZE])),
47 _ => None,
48 }
49 }
50
from_bytes(bytes: &[u8]) -> Option<Self>51 fn from_bytes(bytes: &[u8]) -> Option<Self> {
52 if let Ok(inner) = bytes.try_into() {
53 Some(PublicKey::P192(inner))
54 } else if let Ok(inner) = bytes.try_into() {
55 Some(PublicKey::P256(inner))
56 } else {
57 None
58 }
59 }
60
as_slice(&self) -> &[u8]61 pub fn as_slice(&self) -> &[u8] {
62 match self {
63 PublicKey::P192(inner) => inner,
64 PublicKey::P256(inner) => inner,
65 }
66 }
67
size(&self) -> usize68 pub fn size(&self) -> usize {
69 self.as_slice().len()
70 }
71
as_mut_slice(&mut self) -> &mut [u8]72 pub fn as_mut_slice(&mut self) -> &mut [u8] {
73 match self {
74 PublicKey::P192(inner) => inner,
75 PublicKey::P256(inner) => inner,
76 }
77 }
78
get_x(&self) -> BigInt79 fn get_x(&self) -> BigInt {
80 BigInt::from_signed_bytes_le(&self.as_slice()[0..self.size() / 2])
81 }
82
get_y(&self) -> BigInt83 fn get_y(&self) -> BigInt {
84 BigInt::from_signed_bytes_le(&self.as_slice()[self.size() / 2..self.size()])
85 }
86
to_point<Curve: EllipticCurve>(&self) -> Point<Curve>87 fn to_point<Curve: EllipticCurve>(&self) -> Point<Curve> {
88 Point::new(&self.get_x(), &self.get_y())
89 }
90 }
91
92 #[derive(Debug, Clone, PartialEq, Eq)]
93 pub enum PrivateKey {
94 P192([u8; P192r1::PRIVATE_KEY_SIZE]),
95 P256([u8; P256r1::PRIVATE_KEY_SIZE]),
96 }
97
98 #[derive(Debug, Clone, PartialEq, Eq)]
99 pub enum DhKey {
100 P192([u8; P192r1::PUBLIC_KEY_SIZE]),
101 P256([u8; P256r1::PUBLIC_KEY_SIZE]),
102 }
103
104 impl DhKey {
from_bytes(bytes: &[u8]) -> Option<Self>105 fn from_bytes(bytes: &[u8]) -> Option<Self> {
106 if let Ok(inner) = bytes.try_into() {
107 Some(DhKey::P192(inner))
108 } else if let Ok(inner) = bytes.try_into() {
109 Some(DhKey::P256(inner))
110 } else {
111 None
112 }
113 }
114 }
115
116 impl PrivateKey {
117 // Generate a private key in range[1,2**191]
generate_p192() -> Self118 pub fn generate_p192() -> Self {
119 let random_bytes: [u8; P192r1::PRIVATE_KEY_SIZE] = thread_rng().gen();
120 let mut key = BigInt::from_signed_bytes_le(&random_bytes);
121
122 if key.is_negative() {
123 key = -key;
124 }
125 if key < BigInt::one() {
126 key = BigInt::one();
127 }
128 let buf = key.to_signed_bytes_le();
129 let mut inner = [0; P192r1::PRIVATE_KEY_SIZE];
130 inner[0..buf.len()].copy_from_slice(&buf);
131 Self::P192(inner)
132 }
133
generate_p256() -> Self134 pub fn generate_p256() -> Self {
135 let random_bytes: [u8; P256r1::PRIVATE_KEY_SIZE] = thread_rng().gen();
136 let mut key = BigInt::from_signed_bytes_le(&random_bytes);
137
138 if key.is_negative() {
139 key = -key;
140 }
141 if key < BigInt::one() {
142 key = BigInt::one();
143 }
144 let buf = key.to_signed_bytes_le();
145 let mut inner = [0; P256r1::PRIVATE_KEY_SIZE];
146 inner[0..buf.len()].copy_from_slice(&buf);
147 Self::P256(inner)
148 }
149
as_slice(&self) -> &[u8]150 pub fn as_slice(&self) -> &[u8] {
151 match self {
152 PrivateKey::P192(inner) => inner,
153 PrivateKey::P256(inner) => inner,
154 }
155 }
156
to_bigint(&self) -> BigInt157 fn to_bigint(&self) -> BigInt {
158 BigInt::from_signed_bytes_le(self.as_slice())
159 }
160
derive(&self) -> PublicKey161 pub fn derive(&self) -> PublicKey {
162 let bytes = match self {
163 PrivateKey::P192(_) => {
164 Point::<P192r1>::generate_public_key(&self.to_bigint()).to_bytes()
165 }
166 PrivateKey::P256(_) => {
167 Point::<P256r1>::generate_public_key(&self.to_bigint()).to_bytes()
168 }
169 }
170 .unwrap();
171 PublicKey::from_bytes(&bytes).unwrap()
172 }
173
shared_secret(&self, peer_public_key: PublicKey) -> DhKey174 pub fn shared_secret(&self, peer_public_key: PublicKey) -> DhKey {
175 let bytes = match self {
176 PrivateKey::P192(_) => {
177 (&peer_public_key.to_point::<P192r1>() * &self.to_bigint()).to_bytes()
178 }
179 PrivateKey::P256(_) => {
180 (&peer_public_key.to_point::<P256r1>() * &self.to_bigint()).to_bytes()
181 }
182 }
183 .unwrap();
184 DhKey::from_bytes(&bytes).unwrap()
185 }
186 }
187
188 // Modular Inverse
mod_inv(x: &BigInt, m: &BigInt) -> Option<BigInt>189 fn mod_inv(x: &BigInt, m: &BigInt) -> Option<BigInt> {
190 let egcd = x.extended_gcd(m);
191 if !egcd.gcd.is_one() {
192 None
193 } else {
194 Some(egcd.x % m)
195 }
196 }
197
198 trait EllipticCurve {
199 type Param: AsRef<[u8]>;
200 const A: i32;
201 const P: Self::Param;
202 const G_X: Self::Param;
203 const G_Y: Self::Param;
204 const PRIVATE_KEY_SIZE: usize;
205 const PUBLIC_KEY_SIZE: usize;
206
p() -> BigInt207 fn p() -> BigInt {
208 BigInt::from_bytes_be(Sign::Plus, Self::P.as_ref())
209 }
210 }
211
212 #[derive(Debug, Clone, PartialEq)]
213 struct P192r1;
214
215 impl EllipticCurve for P192r1 {
216 type Param = [u8; 24];
217
218 const A: i32 = -3;
219 const P: Self::Param = [
220 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
221 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
222 ];
223 const G_X: Self::Param = [
224 0x18, 0x8d, 0xa8, 0x0e, 0xb0, 0x30, 0x90, 0xf6, 0x7c, 0xbf, 0x20, 0xeb, 0x43, 0xa1, 0x88,
225 0x00, 0xf4, 0xff, 0x0a, 0xfd, 0x82, 0xff, 0x10, 0x12,
226 ];
227 const G_Y: Self::Param = [
228 0x07, 0x19, 0x2b, 0x95, 0xff, 0xc8, 0xda, 0x78, 0x63, 0x10, 0x11, 0xed, 0x6b, 0x24, 0xcd,
229 0xd5, 0x73, 0xf9, 0x77, 0xa1, 0x1e, 0x79, 0x48, 0x11,
230 ];
231 const PRIVATE_KEY_SIZE: usize = 24;
232 const PUBLIC_KEY_SIZE: usize = 48;
233 }
234
235 #[derive(Debug, Clone, PartialEq)]
236 struct P256r1;
237
238 impl EllipticCurve for P256r1 {
239 type Param = [u8; 32];
240
241 const A: i32 = -3;
242 const P: Self::Param = [
243 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
244 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
245 0xff, 0xff,
246 ];
247 const G_X: Self::Param = [
248 0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40,
249 0xf2, 0x77, 0x03, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98,
250 0xc2, 0x96,
251 ];
252 const G_Y: Self::Param = [
253 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0x0f, 0x9e,
254 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf,
255 0x51, 0xf5,
256 ];
257 const PRIVATE_KEY_SIZE: usize = 32;
258 const PUBLIC_KEY_SIZE: usize = 64;
259 }
260
261 #[derive(Debug, PartialEq)]
262 enum Point<Curve> {
263 Infinite(PhantomData<Curve>),
264 Finite { x: BigInt, y: BigInt, _curve: PhantomData<Curve> },
265 }
266
267 impl<Curve> Point<Curve>
268 where
269 Curve: EllipticCurve,
270 {
o() -> Self271 fn o() -> Self {
272 Point::Infinite(PhantomData)
273 }
274
generate_public_key(private_key: &BigInt) -> Self275 fn generate_public_key(private_key: &BigInt) -> Self {
276 &Self::g() * private_key
277 }
278
new(x: &BigInt, y: &BigInt) -> Self279 fn new(x: &BigInt, y: &BigInt) -> Self {
280 Point::Finite { x: x.clone(), y: y.clone(), _curve: PhantomData }
281 }
282
g() -> Self283 fn g() -> Self {
284 Self::new(
285 &BigInt::from_bytes_be(Sign::Plus, Curve::G_X.as_ref()),
286 &BigInt::from_bytes_be(Sign::Plus, Curve::G_Y.as_ref()),
287 )
288 }
289
290 #[cfg(test)]
get_x(&self) -> Option<BigInt>291 fn get_x(&self) -> Option<BigInt> {
292 match self {
293 Point::Infinite(_) => None,
294 Point::Finite { x, .. } => Some(x.clone()),
295 }
296 }
297
to_bytes(&self) -> Option<Vec<u8>>298 fn to_bytes(&self) -> Option<Vec<u8>> {
299 match self {
300 Point::Infinite(_) => None,
301 Point::Finite { x, y, _curve: _ } => {
302 let mut x = x.to_signed_bytes_le();
303 x.resize(Curve::PRIVATE_KEY_SIZE, 0);
304 let mut y = y.to_signed_bytes_le();
305 y.resize(Curve::PRIVATE_KEY_SIZE, 0);
306 x.append(&mut y);
307 Some(x)
308 }
309 }
310 }
311 }
312
313 impl<Curve> Clone for Point<Curve>
314 where
315 Curve: EllipticCurve,
316 {
clone(&self) -> Self317 fn clone(&self) -> Self {
318 match self {
319 Point::Infinite(_) => Point::o(),
320 Point::Finite { x, y, .. } => Point::new(x, y),
321 }
322 }
323 }
324
325 // Elliptic Curve Group Addition
326 // https://mathworld.wolfram.com/EllipticCurve.html
327 impl<Curve> std::ops::Add<&Point<Curve>> for &Point<Curve>
328 where
329 Curve: EllipticCurve,
330 {
331 type Output = Point<Curve>;
332
add(self, rhs: &Point<Curve>) -> Self::Output333 fn add(self, rhs: &Point<Curve>) -> Self::Output {
334 // P + O = O + P = P
335 match (self, rhs) {
336 (Point::Infinite(_), Point::Infinite(_)) => Self::Output::o(),
337 (Point::Infinite(_), Point::Finite { .. }) => rhs.clone(),
338 (Point::Finite { .. }, Point::Infinite(_)) => self.clone(),
339 (
340 Point::Finite { _curve: _, x: x1, y: y1 },
341 Point::Finite { _curve: _, x: x2, y: y2 },
342 ) => {
343 // P + (-P) = O
344 if x1 == x2 && y1 == &(-y2) {
345 return Self::Output::o();
346 }
347 let p = &Curve::p();
348 // d(x^3 + ax + b) / dx = (3x^2 + a) / 2y
349 let slope = if x1 == x2 {
350 (&(3 * x1.pow(2) + Curve::A) * &mod_inv(&(2 * y1), p).unwrap()) % p
351 } else {
352 // dy/dx = (y2 - y1) / (x2 - x1)
353 (&(y2 - y1) * &mod_inv(&(x2 - x1), p).unwrap()) % p
354 };
355 // Solving (x-p)(x-q)(x-r) = x^3 + ax + b
356 // => x = d^2 - x1 - x2
357 let x = (slope.pow(2) - x1 - x2) % p;
358 let y = (slope * (x1 - &x) - y1) % p;
359 Point::new(&x, &y)
360 }
361 }
362 }
363 }
364
365 impl<Curve> std::ops::Mul<&BigInt> for &Point<Curve>
366 where
367 Curve: EllipticCurve,
368 {
369 type Output = Point<Curve>;
370
mul(self, rhs: &BigInt) -> Self::Output371 fn mul(self, rhs: &BigInt) -> Self::Output {
372 let mut addend = self.clone();
373 let mut result = Point::o();
374 let mut i = rhs.clone();
375
376 // O(logN) double-and-add multiplication
377 while !i.is_zero() {
378 if i.is_odd() {
379 result = &result + &addend;
380 }
381 addend = &addend + &addend;
382 i /= 2;
383 }
384 result
385 }
386 }
387
388 #[cfg(test)]
389 mod tests {
390 use crate::ec::*;
391 use num_bigint::BigInt;
392
393 struct EcTestCase<const N: usize> {
394 pub priv_a: [u8; N],
395 pub priv_b: [u8; N],
396 pub pub_a: [u8; N],
397 pub dh_x: [u8; N],
398 }
399
400 // Private A, Private B, Public A(x), DHKey
401 const P192_TEST_CASES: [EcTestCase<48>; 4] = [
402 EcTestCase::<48> {
403 priv_a: *b"07915f86918ddc27005df1d6cf0c142b625ed2eff4a518ff",
404 priv_b: *b"1e636ca790b50f68f15d8dbe86244e309211d635de00e16d",
405 pub_a: *b"15207009984421a6586f9fc3fe7e4329d2809ea51125f8ed",
406 dh_x: *b"fb3ba2012c7e62466e486e229290175b4afebc13fdccee46",
407 },
408 EcTestCase::<48> {
409 priv_a: *b"52ec1ca6e0ec973c29065c3ca10be80057243002f09bb43e",
410 priv_b: *b"57231203533e9efe18cc622fd0e34c6a29c6e0fa3ab3bc53",
411 pub_a: *b"45571f027e0d690795d61560804da5de789a48f94ab4b07e",
412 dh_x: *b"a20a34b5497332aa7a76ab135cc0c168333be309d463c0c0",
413 },
414 EcTestCase::<48> {
415 priv_a: *b"00a0df08eaf51e6e7be519d67c6749ea3f4517cdd2e9e821",
416 priv_b: *b"2bf5e0d1699d50ca5025e8e2d9b13244b4d322a328be1821",
417 pub_a: *b"2ed35b430fa45f9d329186d754eeeb0495f0f653127f613d",
418 dh_x: *b"3b3986ba70790762f282a12a6d3bcae7a2ca01e25b87724e",
419 },
420 EcTestCase::<48> {
421 priv_a: *b"030a4af66e1a4d590a83e0284fca5cdf83292b84f4c71168",
422 priv_b: *b"12448b5c69ecd10c0471060f2bf86345c5e83c03d16bae2c",
423 pub_a: *b"f24a6899218fa912e7e4a8ba9357cb8182958f9fa42c968c",
424 dh_x: *b"4a78f83fba757c35f94abea43e92effdd2bc700723c61939",
425 },
426 ];
427
428 // Private A, Private B, Public A(x), DHKey
429 const P256_TEST_CASES: [EcTestCase<64>; 2] = [
430 EcTestCase::<64> {
431 priv_a: *b"3f49f6d4a3c55f3874c9b3e3d2103f504aff607beb40b7995899b8a6cd3c1abd",
432 priv_b: *b"55188b3d32f6bb9a900afcfbeed4e72a59cb9ac2f19d7cfb6b4fdd49f47fc5fd",
433 pub_a: *b"20b003d2f297be2c5e2c83a7e9f9a5b9eff49111acf4fddbcc0301480e359de6",
434 dh_x: *b"ec0234a357c8ad05341010a60a397d9b99796b13b4f866f1868d34f373bfa698",
435 },
436 EcTestCase::<64> {
437 priv_a: *b"06a516693c9aa31a6084545d0c5db641b48572b97203ddffb7ac73f7d0457663",
438 priv_b: *b"529aa0670d72cd6497502ed473502b037e8803b5c60829a5a3caa219505530ba",
439 pub_a: *b"2c31a47b5779809ef44cb5eaaf5c3e43d5f8faad4a8794cb987e9b03745c78dd",
440 dh_x: *b"ab85843a2f6d883f62e5684b38e307335fe6e1945ecd19604105c6f23221eb69",
441 },
442 ];
443
444 #[test]
p192()445 fn p192() {
446 for test_case in P192_TEST_CASES {
447 let priv_a = BigInt::parse_bytes(&test_case.priv_a, 16).unwrap();
448 let priv_b = BigInt::parse_bytes(&test_case.priv_b, 16).unwrap();
449 let pub_a = Point::<P192r1>::generate_public_key(&priv_a);
450 let pub_b = Point::<P192r1>::generate_public_key(&priv_b);
451 assert_eq!(pub_a.get_x().unwrap(), BigInt::parse_bytes(&test_case.pub_a, 16).unwrap());
452 let shared = &pub_a * &priv_b;
453 assert_eq!(shared.get_x().unwrap(), BigInt::parse_bytes(&test_case.dh_x, 16).unwrap());
454 assert_eq!((&pub_a * &priv_b).get_x().unwrap(), (&pub_b * &priv_a).get_x().unwrap());
455 }
456 }
457
458 #[test]
p256()459 fn p256() {
460 for test_case in P256_TEST_CASES {
461 let priv_a = BigInt::parse_bytes(&test_case.priv_a, 16).unwrap();
462 let priv_b = BigInt::parse_bytes(&test_case.priv_b, 16).unwrap();
463 let pub_a = Point::<P256r1>::generate_public_key(&priv_a);
464 let pub_b = Point::<P256r1>::generate_public_key(&priv_b);
465 assert_eq!(pub_a.get_x().unwrap(), BigInt::parse_bytes(&test_case.pub_a, 16).unwrap());
466 let shared = &pub_a * &priv_b;
467 assert_eq!(shared.get_x().unwrap(), BigInt::parse_bytes(&test_case.dh_x, 16).unwrap());
468 assert_eq!((&pub_a * &priv_b).get_x().unwrap(), (&pub_b * &priv_a).get_x().unwrap());
469 }
470 }
471 }
472