summaryrefslogtreecommitdiff
path: root/main.go
blob: 88767894469803afff91896b42a2ce77f8a9e34a (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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// Linear search factorization
package main

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

// 64 bit ~ 17 min
// 48 bit ~ 12 sec
// 32 bit ~ .2 sec

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

	"github.com/cznic/mathutil"
)

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

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

	// step 2 to next odd
	two := big.NewInt(2)

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

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

	return nxt, prv
}

func factor(N *big.Int) (*big.Int, *big.Int) {
	nxt, prv := seed(N)

	m := new(big.Int)
	p := <-nxt
	q := <-prv

	t := time.NewTicker(time.Second)
	defer t.Stop()

	for {
		select {
		case <-t.C:
			fmt.Printf("%x %x\n", p, q)
		default:
			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, error) {
	file, err := ioutil.ReadFile(f)
	if err != nil {
		return nil, err
	}

	block, _ := pem.Decode(file)

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

	return &key.PublicKey, nil
}

func main() {
	pub, err := pubKey("test.key")
	if err != nil {
		log.Fatal(err)
	}
	p, q := factor(pub.N)
	fmt.Printf("%x %x\n", p, q)
}