summaryrefslogtreecommitdiff
path: root/main.go
blob: 2cf77af05aa871dddf4347188420b2e9dbc22c3a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// Linear search factorization
package main

//go:generate openssl genrsa -out test.key 48
//go:generate openssl rsa -in test.key -noout -text

import (
	"crypto/rsa"
	"crypto/x509"
	"encoding/pem"
	"fmt"
	"io/ioutil"
	"log"
	"math/big"

	"github.com/cznic/mathutil"
)

func seed(N *big.Int) (<-chan *big.Int, <-chan *big.Int) {
	// we start with sqrt(N)
	p := mathutil.SqrtBig(N)
	p.SetBit(p, 0, 1) // ensure it's odd

	q := new(big.Int).Div(N, p)
	q.SetBit(p, 0, 1) // ensure it's odd

	nxt := make(chan *big.Int)
	go func(c chan *big.Int, n *big.Int) {
		two := big.NewInt(2)
		for {
			// search next prime
			n.Add(n, two)
			if n.ProbablyPrime(1) {
				c <- new(big.Int).Set(n)
			}
		}
	}(nxt, p)

	prv := make(chan *big.Int)
	go func(c chan *big.Int, n *big.Int) {
		two := big.NewInt(2)
		for {
			// search previous prime
			n.Sub(n, two)
			if n.ProbablyPrime(1) {
				c <- new(big.Int).Set(n)
			}
		}
	}(prv, q)

	return nxt, prv
}

func factor(N *big.Int) (*big.Int, *big.Int) {
	nxt, prv := seed(N)
	m := new(big.Int)
	p := <-nxt
	q := <-prv

	for {
		switch m.Mul(p, q).Cmp(N) {
		case -1: // m < N, go up
			p = <-nxt
		case 0: // found
			return p, q
		case 1: // m > N, go down
			q = <-prv
		}
	}

	return nil, nil
}

func pubKey(f string) rsa.PublicKey {
	file, err := ioutil.ReadFile(f)
	if err != nil {
		log.Fatal(err)
	}

	block, _ := pem.Decode(file)

	key, err := x509.ParsePKCS1PrivateKey(block.Bytes)
	if err != nil {
		log.Fatal(err)
	}

	return key.PublicKey
}

func main() {
	pub := pubKey("test.key")
	fmt.Println(factor(pub.N))
}