summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2015-09-04 13:27:36 +0200
committerDimitri Sokolyuk <demon@dim13.org>2015-09-04 13:27:36 +0200
commitf8ecfef6f4fe198876f8aebb17e3ddc1108901e3 (patch)
tree908b18aa9645bbeef23ff7167e87c5091122cb70
Initial import
-rw-r--r--main.go89
1 files changed, 89 insertions, 0 deletions
diff --git a/main.go b/main.go
new file mode 100644
index 0000000..678c386
--- /dev/null
+++ b/main.go
@@ -0,0 +1,89 @@
+package main
+
+import (
+ "crypto/rsa"
+ "crypto/x509"
+ "encoding/pem"
+ "fmt"
+ "io/ioutil"
+ "log"
+ "math/big"
+
+ "github.com/cznic/mathutil"
+)
+
+var (
+ one = big.NewInt(1)
+ two = big.NewInt(2)
+)
+
+const confidence = 10
+
+func next(N *big.Int) <-chan *big.Int {
+ ch := make(chan *big.Int, 1)
+ go func(c chan *big.Int, n *big.Int) {
+ for {
+ n.Add(n, two)
+ if n.ProbablyPrime(confidence) {
+ c <- new(big.Int).Set(n)
+ }
+ }
+ }(ch, N)
+ return ch
+}
+
+func prev(N *big.Int) <-chan *big.Int {
+ ch := make(chan *big.Int, 1)
+ go func(c chan *big.Int, n *big.Int) {
+ for {
+ n.Sub(n, two)
+ if n.ProbablyPrime(confidence) {
+ c <- new(big.Int).Set(n)
+ }
+ }
+ }(ch, N)
+ return ch
+}
+
+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 factor(N *big.Int) (*big.Int, *big.Int) {
+ p, q := seed(N)
+ nxt := next(p)
+ prv := prev(q)
+ m := new(big.Int)
+ for {
+ switch m.Mul(p, q).Cmp(N) {
+ case -1:
+ p = <-nxt
+ case 0:
+ return p, q
+ case 1:
+ q = <-prv
+ }
+ }
+ return nil, nil
+}
+
+func seed(N *big.Int) (*big.Int, *big.Int) {
+ p := mathutil.SqrtBig(N)
+ p.SetBit(p, 0, 1)
+ q := new(big.Int).Set(p)
+ return p, q
+}
+
+func main() {
+ pub := pubKey("test.key")
+ fmt.Println(factor(pub.N))
+}