summaryrefslogtreecommitdiffstats
path: root/lib/rsa.go
diff options
context:
space:
mode:
authorsiddharth ravikumar <s@ricketyspace.net>2022-08-11 20:30:53 -0400
committersiddharth ravikumar <s@ricketyspace.net>2022-08-11 20:30:53 -0400
commite12ccae7a96c01dce5e86aa17c27e20644c75a15 (patch)
tree86aa7a239277ba7d86e1110faa73a45eae329023 /lib/rsa.go
parentc8bfbfb85e368511a033561cd68f7e86f14fcde7 (diff)
lib: add invmod
Diffstat (limited to 'lib/rsa.go')
-rw-r--r--lib/rsa.go35
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
+}