README.md

A variant of Wiener's Attack on RSA

Prerequisites:

1. RSA Encryption/Decryption

2. Wiener's Attack on RSA

As we know that Wiener's Attack works in case where d < N^1/4. This attack works in the scenario when d is a few bits greater than N^1/4.

The Attack

The attack says that in case d is a few bits greater than N^1/4 candidates for private key exponent are of the form , where and is (m+1)th and (m)th convergent of continued fraction of e/n. We can apply this to our exploit as follows:

def wiener(e, n):
	m = 12345
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		k = i.numerator()
		q1 = i.denominator()

		for r in range(30):
			for s in range(30):
				d = r*q1 + s*q0
				m1 = pow(c, d, n)
				if m1 == m:
					return d
		q0 = q1
        return None

The exploit script here. You can also read this paper here that discusses variant of Wiener's Attack in detail.

References

1. A variant of Wiener's Attack on RSA- Andrej Dujella