// 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) }