summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorsiddharth ravikumar <s@ricketyspace.net>2022-08-14 14:28:52 -0400
committersiddharth ravikumar <s@ricketyspace.net>2022-08-14 14:28:52 -0400
commit73a1417859e1251a93e7157a137ca0d220beb2b2 (patch)
treea4ec5e1cd2a829eeed2d31e348aa0f300f3a1f21 /lib
parent295d782194e7495b4d577c16debbf62506674916 (diff)
lib: remove `egcd`
No longer needed.
Diffstat (limited to 'lib')
-rw-r--r--lib/rsa.go48
-rw-r--r--lib/rsa_test.go43
2 files changed, 0 insertions, 91 deletions
diff --git a/lib/rsa.go b/lib/rsa.go
index 3d29bae..1a860eb 100644
--- a/lib/rsa.go
+++ b/lib/rsa.go
@@ -8,12 +8,6 @@ import (
"math/big"
)
-type GCDResult struct {
- Gcd *big.Int
- X *big.Int // Bézout coefficient 'x'
- Y *big.Int // Bézout coefficient 'y'
-}
-
// Represents an RSA key pair.
type RSAPair struct {
Public *RSAPub
@@ -39,48 +33,6 @@ func biCopy(a, b *big.Int) *big.Int {
return a
}
-// Extended Euclidian.
-func egcd(a, b *big.Int) GCDResult {
- // Initialize.
- s0 := big.NewInt(1)
- s1 := big.NewInt(0)
- r0 := biCopy(big.NewInt(0), a)
- r1 := biCopy(big.NewInt(0), b)
-
- for r1.Cmp(big.NewInt(0)) != 0 {
- q := big.NewInt(0)
- q.Div(r0, r1)
-
- tr := big.NewInt(0)
- tr = tr.Mul(q, r1)
- tr = tr.Sub(r0, tr)
-
- biCopy(r0, r1)
- biCopy(r1, tr)
-
- tr = big.NewInt(0)
- tr = tr.Mul(q, s1)
- tr = tr.Sub(s0, tr)
-
- biCopy(s0, s1)
- biCopy(s1, tr)
- }
-
- x := biCopy(big.NewInt(0), s0)
- y := big.NewInt(0)
- if b.Cmp(big.NewInt(0)) != 0 {
- y = y.Mul(s0, a)
- y = y.Sub(r0, y)
- y = y.Div(y, b)
- }
-
- return GCDResult{
- Gcd: biCopy(big.NewInt(0), r0),
- X: x,
- Y: y,
- }
-}
-
func invmod(a, n *big.Int) (*big.Int, error) {
// Initialize.
t0 := big.NewInt(0)
diff --git a/lib/rsa_test.go b/lib/rsa_test.go
index c0d4ce4..eee20c6 100644
--- a/lib/rsa_test.go
+++ b/lib/rsa_test.go
@@ -8,49 +8,6 @@ import (
"testing"
)
-func TestEGCD(t *testing.T) {
- a := big.NewInt(128)
- b := big.NewInt(96)
- r := egcd(a, b)
- if r.Gcd.Cmp(big.NewInt(32)) != 0 {
- t.Errorf("gcd(128, 96) != 32")
- }
- if r.X.Cmp(big.NewInt(1)) != 0 || r.Y.Cmp(big.NewInt(-1)) != 0 {
- t.Errorf("bézout_coef(128, 96) != {1,-1}")
- }
-
- a = big.NewInt(360)
- b = big.NewInt(210)
- r = egcd(a, b)
- if r.Gcd.Cmp(big.NewInt(30)) != 0 {
- t.Errorf("gcd(360, 210) != 30")
- }
- if r.X.Cmp(big.NewInt(3)) != 0 || r.Y.Cmp(big.NewInt(-5)) != 0 {
- t.Errorf("bézout_coef(360, 210) != {3,-5}")
- }
-
- a = big.NewInt(108)
- b = big.NewInt(144)
- r = egcd(a, b)
- if r.Gcd.Cmp(big.NewInt(36)) != 0 {
- t.Errorf("gcd(108, 144) != 36")
- }
- if r.X.Cmp(big.NewInt(-1)) != 0 || r.Y.Cmp(big.NewInt(1)) != 0 {
- t.Errorf("bézout_coef(108, 144) != {-1,1}")
- }
-
- a = big.NewInt(240)
- b = big.NewInt(46)
- r = egcd(a, b)
- if r.Gcd.Cmp(big.NewInt(2)) != 0 {
- t.Errorf("gcd(240, 46) != 2")
- }
- if r.X.Cmp(big.NewInt(-9)) != 0 || r.Y.Cmp(big.NewInt(47)) != 0 {
- t.Errorf("bézout_coef(240, 46) != {-9,47}")
- }
-
-}
-
func TestInvMod(t *testing.T) {
a := big.NewInt(17)
b := big.NewInt(3120)