factorization solver for SquareCTF 2022 Hardcopy

solve.go

package main

import (
	"crypto/rsa"
	"crypto/x509"
	"encoding/pem"
	"fmt"
	"math/big"
	"os"
)

func factor(n *big.Int) (*big.Int, *big.Int, error) {
	const bits = 2048
	var bigOne = big.NewInt(1)
	bsq := new(big.Int).Lsh(bigOne, 2*(bits/2-4))
	asq := new(big.Int).Add(n, bsq)
	a := asq.Sqrt(asq)
	b := new(big.Int)
	for i := 0; i < 1_000_000; i++ {
		bsq.Mul(a, a)
		bsq.Sub(bsq, n)
		b.Sqrt(bsq)
		if new(big.Int).Mul(b, b).Cmp(bsq) == 0 {
			p := new(big.Int).Sub(a, b)
			q := new(big.Int).Add(a, b)
			return p, q, nil
		}
		a.Add(a, bigOne)
	}
	return nil, nil, fmt.Errorf("Factorization failed")
}

func solve() error {
	data, err := os.ReadFile("cert.raw") // extracted from packets
	if err != nil {
		return err
	}

	cert, err := x509.ParseCertificate(data)
	if err != nil {
		return err
	}

	publicKey := cert.PublicKey.(*rsa.PublicKey)

	p, q, err := factor(publicKey.N)
	if err != nil {
		return err
	}

	privateKey := &rsa.PrivateKey{}
	privateKey.Primes = []*big.Int{p, q}
	privateKey.N = publicKey.N
	privateKey.E = 65537

	var bigOne = big.NewInt(1)

	pminus1 := new(big.Int).Sub(p, bigOne)
	qminus1 := new(big.Int).Sub(q, bigOne)
	totient := new(big.Int).Mul(pminus1, qminus1)

	privateKey.D = new(big.Int)
	bigE := big.NewInt(int64(privateKey.E))
	ok := privateKey.D.ModInverse(bigE, totient)
	if ok == nil {
		return fmt.Errorf("failed prime number generation")
	}
	privateKey.Precompute()

	keyDERBytes, err := x509.MarshalPKCS8PrivateKey(privateKey)
	if err != nil {
		return fmt.Errorf("failed to encode private key: %w", err)
	}

	keyPEMBytes := pem.EncodeToMemory(&pem.Block{Type: "PRIVATE KEY", Bytes: keyDERBytes})
	if err := os.WriteFile("key.pem", keyPEMBytes, 0600); err != nil {
		return fmt.Errorf("failed to write private key: %w", err)
	}

	return nil
}

func main() {
	err := solve()
	fmt.Println(err)
}