lib: add invmod

1 files changed, 35 insertions, 0 deletions

diff --git a/lib/rsa.go b/lib/rsa.go
index 86df861..2c0769b 100644
--- a/lib/rsa.go
+++ b/lib/rsa.go
@@ -63,3 +63,38 @@ func egcd(a, b *big.Int) GCDResult {
 		Y:   y,
 	}
 }
+
+func invmod(a, n *big.Int) (*big.Int, error) {
+	// Initialize.
+	t0 := big.NewInt(0)
+	t1 := big.NewInt(1)
+	r0 := biCopy(big.NewInt(0), n)
+	r1 := biCopy(big.NewInt(0), a)
+
+	for r1.Cmp(big.NewInt(0)) != 0 {
+		q := big.NewInt(0)
+		q.Div(r0, r1)
+
+		tt := big.NewInt(0)
+		tt = tt.Mul(q, t1)
+		tt = tt.Sub(t0, tt)
+
+		biCopy(t0, t1)
+		biCopy(t1, tt)
+
+		tr := big.NewInt(0)
+		tr = tr.Mul(q, r1)
+		tr = tr.Sub(r0, tr)
+
+		biCopy(r0, r1)
+		biCopy(r1, tr)
+	}
+
+	if r0.Cmp(big.NewInt(1)) > 0 {
+		return nil, CPError{"not invertible"}
+	}
+	if t0.Cmp(big.NewInt(0)) < 0 {
+		t0.Add(t0, n)
+	}
+	return t0, nil
+}