cryptowedge

README

cryptowedge

Implementations of classical attacks against RSA and related public-key cryptosystems, written in Go. Each attack targets a specific weakness and recovers key material or plaintext when that weakness is present.

Intended for security research, CTF challenges, and educational use.

Install

go get github.com/dhunkin/cryptowedge

Requires Go 1.22 or later.

Attacks

Attack	Function	Recovers when
Wiener	Wiener	The private exponent d is small (d < N^(1/4)/3)
WienerLat	WienerLat	The private exponent d is small (lattice‑based variant using Lagrange‑Gauss reduction)

More attacks are planned; the table above lists what ships today.

Usage

Wiener's attack recovers the private exponent from an RSA public key whose private exponent is small relative to the modulus:

package main

import (
	"fmt"
	"math/big"

	"github.com/dhunkin/cryptowedge"
)

func main() {
	// Public key (N, e) suspected of using a small private exponent.
	N, _ := new(big.Int).SetString("...", 10)
	e, _ := new(big.Int).SetString("...", 10)

	d, p, q, err := cryptowedge.Wiener(N, e)
	if err != nil {
		fmt.Println("key not vulnerable:", err)
		return
	}

	fmt.Printf("recovered d = %s\n", d)
	fmt.Printf("factored N  = %s * %s\n", p, q)

	// Decrypt a ciphertext c with the recovered exponent:
	//   m := new(big.Int).Exp(c, d, N)
}

The lattice‑based variant WienerLat works identically, with the same signature and recovery conditions:

d, p, q, err := cryptowedge.WienerLat(N, e)

On success both functions return the private exponent d and the two prime factors p and q of N. When no small exponent is found — the usual case for a securely generated key — they return ErrNotVulnerable and nil results.

Scope and authorization

These functions succeed only when the targeted weakness is present; against securely generated keys they report failure rather than recovering anything.

Use them only against systems you own or are explicitly authorized to test. Running these attacks against systems you do not have permission to test may be illegal.

Documentation

Full API documentation is available on pkg.go.dev.

License

Released under the MIT License.

Documentation

Overview

Package cryptowedge provides implementations of classical attacks against RSA and related public-key cryptosystems.

The package is intended for security research, CTF challenges, and educational use: each attack targets a specific weakness (small private exponent, small public exponent, shared factors, and so on) and recovers key material or plaintext when that weakness is present.

Attacks

Wiener implements Wiener's attack, recovering the private exponent of RSA keys with a small d (roughly d < N^(1/4)/3).

WienerLat implements a lattice-based variant of Wiener's attack, using Lagrange-Gauss lattice reduction to recover the private exponent under the same small-d condition.

Usage

These functions succeed only when the targeted weakness is present; against securely generated keys they report failure rather than recovering anything. Use them only against systems you are authorized to test.

Index

• Variables
• func Wiener(N, e *big.Int) (d, p, q *big.Int, err error)
• func WienerLat(N, e *big.Int) (d, p, q *big.Int, err error)

Variables

var (
	ErrNotVulnerable = errors.New("wiener: key not vulnerable to Wiener's attack")
	ErrInvalidKey    = errors.New("wiener: invalid public key")
)

Functions

func Wiener

func Wiener(N, e *big.Int) (d, p, q *big.Int, err error)

Wiener attempts to recover the RSA private exponent from the public key (N, e) using Wiener's attack.

It walks the convergents of the continued fraction of e/N, and for each candidate reconstructs phi(N), solves the quadratic x^2 - (N-phi+1)x + N = 0 for the prime factors, and verifies that they reconstruct N. On success it returns the private exponent d together with the factors p and q of N.

The attack only works against keys with a small private exponent, roughly d < N^(1/4)/3. If no convergent yields a valid factorization - the usual case for a securely generated key - Wiener returns ErrNotVulnerable and the three *big.Int results are nil.

N and e must be a well-formed RSA public key with N = p*q for distinct primes p and q; behavior is unspecified for other inputs.

func WienerLat

func WienerLat(N, e *big.Int) (d, p, q *big.Int, err error)

WienerLat attempts to recover the RSA private exponent from the public key (N, e) using a lattice‑based variant of Wiener’s attack.

It constructs a 2‑dimensional lattice basis from the public key, reduces it using Lagrange‑Gauss reduction to obtain a short basis vector, and extracts the first reduced vector as the candidate for (d, -k), where k satisfies e*d - 1 = k * phi(N). It then reconstructs phi(N) by checking the divisibility of e*d - 1 by k, solves the quadratic x² - (N - phi + 1)x + N = 0 for the prime factors, and verifies that they reconstruct N. On success it returns the private exponent d together with the factors p and q of N.

The attack works under the same condition as the classical Wiener attack: it succeeds when the private exponent d is sufficiently small, roughly d < N^(1/4) / 3. If the candidate vector does not yield a valid factorization – which is the usual case for a securely generated key – WienerLat returns ErrNotVulnerable and the three *big.Int results are nil.

N and e must be a well‑formed RSA public key with N = p*q for distinct primes p and q; behavior is unspecified for other inputs.