From 80db8a2f72e64caa0b16bb995ee98aa10670cb3f Mon Sep 17 00:00:00 2001
From: Matthias Schiffer <mschiffer@universe-factory.net>
Date: Fri, 7 Dec 2012 20:11:54 +0100
Subject: Add GF reciprocal function

---
 include/libuecc/ecc.h |  1 +
 src/ec25519_gf.c      | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 52 insertions(+)

diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h
index b8f8bc5..42431ec 100644
--- a/include/libuecc/ecc.h
+++ b/include/libuecc/ecc.h
@@ -61,6 +61,7 @@ void ecc_25519_gf_add(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_25
 void ecc_25519_gf_sub(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2);
 void ecc_25519_gf_reduce(ecc_int_256 *out, const ecc_int_256 *in);
 void ecc_25519_gf_mult(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2);
+void ecc_25519_gf_recip(ecc_int_256 *out, const ecc_int_256 *in);
 
 void ecc_25519_gf_sanitize_secret(ecc_int_256 *out, const ecc_int_256 *in);
 
diff --git a/src/ec25519_gf.c b/src/ec25519_gf.c
index 6847cb1..9c57c66 100644
--- a/src/ec25519_gf.c
+++ b/src/ec25519_gf.c
@@ -176,6 +176,57 @@ void ecc_25519_gf_mult(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_2
 	montgomery(out->p, R, C);
 }
 
+void ecc_25519_gf_recip(ecc_int_256 *out, const ecc_int_256 *in) {
+	static const unsigned char C[32] = {
+		0x01
+	};
+
+	unsigned char A[32], B[32];
+	unsigned char R1[32], R2[32];
+	int use_r2 = 0;
+	unsigned int i, j;
+
+	for (i = 0; i < 32; i++) {
+		R1[i] = (i == 0);
+		A[i] = in->p[i];
+	}
+
+	for (i = 0; i < 32; i++) {
+		unsigned char c;
+
+		if (i == 0)
+			c = 0xeb; /* q[0] - 2 */
+		else
+			c = q[i];
+
+		for (j = 0; j < 8; j+=2) {
+			if (c & (1 << j)) {
+				if (use_r2)
+					montgomery(R1, R2, A);
+				else
+					montgomery(R2, R1, A);
+
+				use_r2 = !use_r2;
+			}
+
+			montgomery(B, A, A);
+
+			if (c & (2 << j)) {
+				if (use_r2)
+					montgomery(R1, R2, B);
+				else
+					montgomery(R2, R1, B);
+
+				use_r2 = !use_r2;
+			}
+
+			montgomery(A, B, B);
+		}
+	}
+
+	montgomery(out->p, R2, C);
+}
+
 void ecc_25519_gf_sanitize_secret(ecc_int_256 *out, const ecc_int_256 *in) {
 	int i;
 
-- 
cgit v1.2.3