Skip to content

Instantly share code, notes, and snippets.

@mspraggs
Last active March 31, 2023 07:16
Show Gist options
  • Save mspraggs/f1ccca8bc6f852186efa63adf2d8a8b4 to your computer and use it in GitHub Desktop.
Save mspraggs/f1ccca8bc6f852186efa63adf2d8a8b4 to your computer and use it in GitHub Desktop.
Wiener's attack with Go
module weakrsa
go 1.19
require golang.org/x/crypto v0.3.0
// 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)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment