Wiener's attack with Go

go.mod

module weakrsa

go 1.19

require golang.org/x/crypto v0.3.0

wiener.go

// Package main implements Wiener's attack using Go. It accepts a public key
// encoded in DER and PEM as standard input and produces the corresponding
// PKCS#1 private key encoded in PEM format.
//
// Install:
// 1. Copy wiener.go and go.mod to a directory.
// 2. Run `go mod tidy`.
//
// Usage: cat <public key file> | go run wiener.go
package main

import (
	"bytes"
	"crypto/rsa"
	"crypto/x509/pkix"
	"encoding/asn1"
	"encoding/pem"
	"errors"
	"fmt"
	"io"
	"math/big"
	"os"

	"golang.org/x/crypto/cryptobyte"
	cryptobyte_asn1 "golang.org/x/crypto/cryptobyte/asn1"
)

var (
	bigZero = big.NewInt(0)
	bigOne  = big.NewInt(1)
	bigTwo  = big.NewInt(2)
	bigFour = big.NewInt(4)

	oidPublicKeyRSA = asn1.ObjectIdentifier{1, 2, 840, 113549, 1, 1, 1}
)

// rsaPublicKey wraps the exponent and modulus that define an RSA public key. It
// is inspired by the `crypto/rsa` package in the Go standard library with
// adaptations to support large exponents.
type rsaPublicKey struct {
	N *big.Int
	E *big.Int
}

// rsaPrivateKey wraps the exponent and primes that define an RSA private key,
// along with the public key and some precomputed values to accelerate various
// calculations. It is inspired by the `crypto/rsa` package in the Go standard
// library with adaptations to support large exponents.
type rsaPrivateKey struct {
	rsaPublicKey
	D      *big.Int
	Primes []*big.Int

	Precomputed rsa.PrecomputedValues
}

// publicKeyInfo is taken from the Go standard library and is used to support
// the parsing of public keys with large exponents.
type publicKeyInfo struct {
	Raw       asn1.RawContent
	Algorithm pkix.AlgorithmIdentifier
	PublicKey asn1.BitString
}

// pkcs1PrivateKey is taken from the Go standard library and is used to support
// the encoding of PKCS#1 private keys.
type pkcs1PrivateKey struct {
	Version          int
	N                *big.Int
	E                *big.Int
	D                *big.Int
	P                *big.Int
	Q                *big.Int
	Dp               *big.Int                  `asn1:"optional"`
	Dq               *big.Int                  `asn1:"optional"`
	Qinv             *big.Int                  `asn1:"optional"`
	AdditionalPrimes []pkcs1AdditionalRSAPrime `asn1:"optional,omitempty"`
}

type pkcs1AdditionalRSAPrime struct {
	Prime *big.Int
	Exp   *big.Int
	Coeff *big.Int
}

func main() {
	pubkey, err := loadRSAPublicKey(os.Stdin)
	if err != nil {
		fmt.Printf("Error loading public key: %v\n", err)
		os.Exit(1)
	}

	privkey, err := weinerAttack(pubkey)
	if err != nil {
		fmt.Printf("Error cracking public key: %v\n", err)
		os.Exit(1)
	}

	if err := storeRSAPrivateKey(os.Stdout, privkey); err != nil {
		fmt.Printf("Error serialising private key: %v\n", err)
		os.Exit(1)
	}
}

// weinerAttack uses Weiner's theorem to recover the private exponent (and hence
// the private key) from the provided public key.
func weinerAttack(pubkey *rsaPublicKey) (*rsaPrivateKey, error) {
	e := pubkey.E
	n := pubkey.N
	r := big.NewRat(0, 1)
	r.Num().Set(e)
	r.Denom().Set(n)
	quotients := computeQuotients(r)
	convergents := computeConvergents(quotients)
	d, p, q, phi := extractSecrets(e, n, convergents)
	if d == nil || p == nil || q == nil || phi == nil {
		return nil, errors.New("failed to crack public key")
	}

	return &rsaPrivateKey{
		rsaPublicKey: *pubkey,
		D:            d,
		Primes:       []*big.Int{p, q},
	}, nil
}

// computeQuotients deterimines the continued fraction quotients of the given
// rational number.
func computeQuotients(rat *big.Rat) []*big.Int {
	quotients := []*big.Int{}

	// Determine quotients by dividing the numerator n of some rational number
	// by its denominator d. If the remainder is non-zero, take its reciprocal
	// and repeat the process, otherwise halt.

	n := rat.Num()
	d := rat.Denom()
	q := &big.Int{}
	r := &big.Int{}
	q.DivMod(n, d, r)
	quotients = append(quotients, q)

	for r.Cmp(bigZero) != 0 {
		n = d
		d = r

		q = &big.Int{}
		r = &big.Int{}
		q.DivMod(n, d, r)
		quotients = append(quotients, q)
	}

	return quotients
}

// computeConvergents determines the continued fraction convergents
// corresponding to the provided quotients.
func computeConvergents(quotients []*big.Int) []*big.Rat {
	convergents := make([]*big.Rat, len(quotients))

	// Taken from http://monge.univ-mlv.fr/~jyt/Crypto/4/10.1.1.92.5261.pdf
	for i, q := range quotients {
		r := big.NewRat(0, 1)
		switch i {
		case 0:
			r.Num().Set(q)
		case 1:
			n := &big.Int{}
			n.Add(n.Mul(q, quotients[i-1]), bigOne)
			r.Num().Set(n)
			r.Denom().Set(q)
		default:
			n := &big.Int{}
			n.Add(n.Mul(q, convergents[i-1].Num()), convergents[i-2].Num())
			r.Num().Set(n)
			d := &big.Int{}
			d.Add(d.Mul(q, convergents[i-1].Denom()), convergents[i-2].Denom())
			r.Denom().Set(d)
		}
		convergents[i] = r
	}

	return convergents
}

func computePhiN(e, k, d *big.Int) *big.Int {
	phi := &big.Int{}
	phi.Div(phi.Sub(phi.Mul(e, d), bigOne), k)

	return phi
}

// extractSecrets uses the provided convergents as approximations of e/n. These
// approximations are tested using the method outlined in
// http://monge.univ-mlv.fr/~jyt/Crypto/4/10.1.1.92.5261.pdf to recover the
// value of the private key exponent, d, along with phi(N), p and q.
func extractSecrets(
	e, n *big.Int,
	convergents []*big.Rat,
) (*big.Int, *big.Int, *big.Int, *big.Int) {

	for _, c := range convergents {
		pk := c.Num()
		pd := c.Denom()
		if pk.Cmp(bigZero) == 0 {
			continue
		}

		phi := computePhiN(e, pk, pd)

		b := &big.Int{}
		b.Sub(b.Sub(phi, n), bigOne)

		pp, pq := solveQuad(bigOne, b, n)
		if pp == nil || pq == nil {
			continue
		}
		pN := &big.Int{}
		pN.Mul(pp, pq)

		if pN.Cmp(n) == 0 {
			return pd, pp, pq, phi
		}
	}

	return nil, nil, nil, nil
}

// solveQuad solves the quadratic equation defined by a, b and c.
func solveQuad(a, b, c *big.Int) (*big.Int, *big.Int) {
	b2 := &big.Int{}
	b2.Mul(b, b)

	// Calculate discriminant, b * b - 4 * a * c
	disc := &big.Int{}
	disc.Sub(b2, disc.Mul(disc.Mul(bigFour, a), c))

	switch disc.Cmp(bigZero) {
	case -1:
		// No roots - return nil values
		return nil, nil
	case 0:
		// Duplicate roots - return -b / (2 * a)
		x := &big.Int{}
		x.Quo(x.Neg(b), x.Mul(bigTwo, a))
		return x, x
	default:
		// Distinct roots - return (-b + sqrt(b * b - 4 * a * c)) / (2 * a) and
		// (-b - sqrt(b * b - 4 * a * c)) / (2 * a)

		// Compute 2 * a
		denom := &big.Int{}
		denom.Mul(bigTwo, a)

		// Root of discriminant
		discSqrt := &big.Int{}
		discSqrt.Sqrt(disc)

		// First root - (-b - sqrt(b * b - 4 * a * c)) / (2 * a)
		x0 := &big.Int{}
		x0.Div(x0.Sub(x0.Neg(b), discSqrt), denom)
		// Second root - (-b + sqrt(b * b - 4 * a * c)) / (2 * a)
		x1 := &big.Int{}
		x1.Div(x1.Add(x1.Neg(b), discSqrt), denom)
		return x0, x1
	}
}

// loadRSAPublicKey reads and decodes an RSA public key from the provider Reader
// instance.
func loadRSAPublicKey(r io.Reader) (*rsaPublicKey, error) {
	bytes, err := io.ReadAll(r)
	if err != nil {
		return nil, err
	}

	derBytes, _ := pem.Decode(bytes)
	if derBytes == nil {
		return nil, errors.New("invalid DER bytes")
	}

	return decodePrivateKey(derBytes.Bytes)
}

// decodePrivateKey is based on ParsePKIXPublicKey in the x509 package of the Go
// standard library.
func decodePrivateKey(derBytes []byte) (*rsaPublicKey, error) {
	var pki publicKeyInfo
	if rest, err := asn1.Unmarshal(derBytes, &pki); err != nil {
		if _, err := asn1.Unmarshal(derBytes, &rsaPublicKey{}); err == nil {
			return nil, errors.New("failed to parse public key")
		}
		return nil, err
	} else if len(rest) != 0 {
		return nil, errors.New("trailing data after ASN.1 of public-key")
	}
	if !pki.Algorithm.Algorithm.Equal(oidPublicKeyRSA) {
		return nil, errors.New("unsupported public key algorithm")
	}
	der := cryptobyte.String(pki.PublicKey.RightAlign())
	if !bytes.Equal(pki.Algorithm.Parameters.FullBytes, asn1.NullBytes) {
		return nil, errors.New("RSA key missing NULL parameters")
	}

	pub := &rsaPublicKey{N: new(big.Int), E: new(big.Int)}
	if !der.ReadASN1(&der, cryptobyte_asn1.SEQUENCE) {
		return nil, errors.New("invalid RSA public key")
	}
	if !der.ReadASN1Integer(pub.N) {
		return nil, errors.New("invalid RSA modulus")
	}
	if !der.ReadASN1Integer(pub.E) {
		return nil, errors.New("invalid RSA public exponent")
	}

	if pub.N.Sign() <= 0 {
		return nil, errors.New("RSA modulus is not a positive number")
	}
	return pub, nil
}

// storeRSAPrivateKey encodes and stores the provided RSA private key in the
// provided Writer object.
func storeRSAPrivateKey(w io.Writer, k *rsaPrivateKey) error {
	bytes, err := encodePrivateKey(k)
	if err != nil {
		return err
	}
	pemBlock := &pem.Block{
		Type:  "RSA PRIVATE KEY",
		Bytes: bytes,
	}
	return pem.Encode(w, pemBlock)
}

// encodePrivateKey encodes the provided private key as a sequence of ASN.1
// bytes. The implementation is based on MarshalBigPKCS1BigPrivateKey in the
// github.com/sourcekris/x509big package.
func encodePrivateKey(k *rsaPrivateKey) ([]byte, error) {
	k.precompute()

	version := 0

	pkcs1Key := pkcs1PrivateKey{
		Version: version,
		N:       k.rsaPublicKey.N,
		E:       k.rsaPublicKey.E,
		D:       k.D,
		P:       k.Primes[0],
		Q:       k.Primes[1],
		Dp:      k.Precomputed.Dp,
		Dq:      k.Precomputed.Dq,
		Qinv:    k.Precomputed.Qinv,
	}

	pkcs1Key.AdditionalPrimes = make([]pkcs1AdditionalRSAPrime, len(k.Precomputed.CRTValues))
	for i, values := range k.Precomputed.CRTValues {
		pkcs1Key.AdditionalPrimes[i].Prime = k.Primes[2+i]
		pkcs1Key.AdditionalPrimes[i].Exp = values.Exp
		pkcs1Key.AdditionalPrimes[i].Coeff = values.Coeff
	}

	return asn1.Marshal(pkcs1Key)
}

func (k *rsaPrivateKey) precompute() {
	if k.Precomputed.Dp != nil {
		return
	}

	k.Precomputed.Dp = new(big.Int).Sub(k.Primes[0], bigOne)
	k.Precomputed.Dp.Mod(k.D, k.Precomputed.Dp)

	k.Precomputed.Dq = new(big.Int).Sub(k.Primes[1], bigOne)
	k.Precomputed.Dq.Mod(k.D, k.Precomputed.Dq)

	k.Precomputed.Qinv = new(big.Int).ModInverse(k.Primes[1], k.Primes[0])

	r := new(big.Int).Mul(k.Primes[0], k.Primes[1])
	k.Precomputed.CRTValues = make([]rsa.CRTValue, len(k.Primes)-2)
	for i := 2; i < len(k.Primes); i++ {
		prime := k.Primes[i]
		values := &k.Precomputed.CRTValues[i-2]

		values.Exp = new(big.Int).Sub(prime, bigOne)
		values.Exp.Mod(k.D, values.Exp)

		values.R = new(big.Int).Set(r)
		values.Coeff = new(big.Int).ModInverse(r, prime)

		r.Mul(r, prime)
	}
}