diff options
| -rw-r--r-- | lib/rsa.go | 48 | ||||
| -rw-r--r-- | lib/rsa_test.go | 43 |
2 files changed, 0 insertions, 91 deletions
@@ -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) |