All of these but m are essentially given to us.

Conditions of the attack

Because we are going to need to calculate inverses for this attack, we must first make sure that these inverses exist in the first place:

The math behind the attack

We know that RSA goes as follows:

From the conditions above we also know that $e1$ and $e2$ are co-prime. Thus using Bezout's Theorem we can get:

Using this, we can derive the original message $m$ :

NB: all the calculations are done mod $n$

In general, Bezout's Theorem gives a pair of positive and negative numbers. We just need to adapt this equation a little to make it work for us. In this case, let's assume $y$ is the negative number:

Now to truly recover the plaintext, we are actually doing:

for some $k \in \mathbb{Z}$. Combining this with Euler's theorem, we see that we recover $m$from the ciphertext

When the requirement $\gcd(m, n) = 1$does not hold, we can instead look at the equivalences modulo $p$and $q$respectively. Clearly, when $\gcd(m, n) = n,$we have that $c \equiv m \equiv 0 \mod n$and our correctness still holds. Now, consider the case $m = k\cdot p,$where we have that $c \equiv m \equiv 0 \mod p$and $c^d \equiv (m^e)^d \pmod q.$Since we have already excluded the case that $\gcd(m, q) = q,$we can conclude that $\gcd(m, q) = 1,$as $q$is prime. This means that $m^{\ell\phi(q)} \equiv 1 \mod q$and by the multiplicative properties of the $\phi$function, we determine that $m^{\ell_n\phi(n)} = m^{\ell\phi(q)} \equiv 1 \mod q.$We conclude by invoking the Chinese Remainder theorem with

that $m^{e\cdot d} \equiv m \mod n.$The case for $m = k\cdot q$follows in a parallel manner.

OpenSSL is a robust, commercial-grade, and full-featured toolkit for the Transport Layer Security (TLS) and Secure Sockets Layer (SSL) protocols. It is also a general-purpose cryptography library

OpenSSH:

As stated above, the RSA's totient function can be espressed as:

continuing with the equation, we see that

and if we decide to consider $x = \frac{N+1}{2}$and $y = \frac{p+q}{2}$, we will have:

At this point, finding $d$is equivalent to find the 2 small solutions $x$and $y$to the congruence

now let $s = -\frac{p+q}{2}$and $A = \frac{N+1}{2}$this will preserve the scomposed $\phi(N)$subtraction

consider $e=N^{\alpha}$(with any $\alpha$), we deduct that $\alpha$must be really closed to $1$because $e$is in the same order of the length of $N$(so $e=N^{\sim 1^{-}}$), we will get

Sage Implementation

RSA is a public-key cryptosystem that is widely used in the world today to provide a secure transmission system to millions of communications, is one of the oldest such systems in existence. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at GCHQ (the British signals intelligence agency), by the English mathematician Clifford Cocks. That system was declassified in 1997.

All public-key systems are based on the concept of trapdoor functions, functions that are simple to compute in one direction but computationally hard to reverse without knowledge of some special information called the trapdoor. In RSA, the trapdoor function is based on the hardness of factoring integers. The function involves the use of a public key$N$to encrypt data, which is (supposed to be) encrypted in such a way that the function cannot be reversed without knowledge of the prime factorisation of$N$, something that should be kept private. Except in certain cases, there exists no efficient algorithm for factoring huge integers.

Further reading: Shor's algorithm

II- Arithmetic for RSA

Before starting to introducing you RSA, a few arithmetic notions need to be introduce to understand perfectly other steps.

III- Key generation

• We pick two primes $p$ and $q$

• Using $p$ and $q$, we calculate modulus $n = p\times q$ and its Euler's totient $\phi(n) = (p-1) \times (q-1)$

• Now, choose the public exponent $\mathbb{e}$such as

• By using the Extended Euclidean algorithm, we compute the invert of : which is our private exponent.

• Public key:

• Private key:

• Now, chose a message that you convert into integers

• We can encrypt this plaintext and receive a ciphertext

• We can decrypt a ciphertext with

IV- Signature

A digital signature is a proof of the authenticity of a message, i.e. a proof that the message has not been tampered with. RSA allows us to sign messages by "encrypting" them using the private key, the result being a signature that anyone can verify by "decrypting" it with the public key and comparing it to the associated message. Any attempt to tamper with the message will result in it no longer matching the signature, and vice-versa. Futhermore, a signature can only be generated using the private key, making it a secure and efficient method of confirming the authenticity of messages.

Say Alice wants to send a message to Bob, but does not want Mallory, who has established herself as a middleman, to make changes to the message or swap it out entirely. Fortunately, Bob knows Alice's public key, and since $e$ and $d$ are inverses such that $ed \equiv 1\mod \phi(n)$, Alice can sign her message $m$ by "encrypting" it with the private key such that $s \equiv m^d \mod n$, where $s$ is the signature verifying that the message came from Alice. Alice can now send $m$ and $s$ to Bob, who is now able to check the authenticity of the message by checking if $m \equiv s^e \mod n$. If Mallory tries to change $m$, this congruence no longer holds, and since she does not have the private key, she is also unable to provide a maching $s$for her tampered message.

V- Format

Some observations on RSA

In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:

We may start by noting that the congruence $ed \equiv 1 \mod \phi(n)$ can be written as the equality $ed = k\phi(n)+1$ for some value $k$, we may additionally note that $\phi(n) = (p-1)(q-1) = pq - p - q + 1$, since both $p$ and $q$ are much shorter than $pq = n$, we can say that $\phi(n) \approx n$.

Dividing the former equation by $d\phi(n)$ gives us $\frac{e}{\phi(n)} = \frac{k+1}{d}$, and using the latter approximation, we can write this as $\frac{e}{n} \approx \frac{k}{d}$. Notice how the left-hand side of this equation is composed entirely of public information, this will become important later.

It is possible to quickly factor $n$ by knowing $n$ and $\phi(n)$. Consider the quadratic polynomial $(x-q)(x-p)$, this polynomial will have the roots $p$ and $q$. Expanding it gives us $x^2 - (p + q)x + pq$, and substituting for the variables we know we can write this as $x^2 - (n - \phi(n) + 1)x + n$. Applying the quadratic formula gives us $p$ and $q$: $p \wedge q = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$, where $a = 1$, $b = n - \phi(n) + 1$, and $c = n$.

Wiener's attack works by expanding $\frac{e}{n}$ to a continued fraction and iterating through the terms to check various approximations of $\frac{k}{d}$. In order to make this checking process more efficient, we can make a few observations (this part is optional):

• Since $\phi(n)$ is even, and $e$ and $d$ are both by definition coprime to $\phi(n)$, we know that $d$ is odd.

• Given the above equations and the values of $e$, $n$, $d$, and $k$, we can solve for $\phi(n)$ with the equation $\phi(n) = \frac{ed-1}{k}$, thus we know that $ed-1$ has to be divisible by $k$.

• If our is correct, the polynomial will have roots and , which we can verify by checking if .

The Attack

Suppose we have the public key $(n, e)$, this attack will determine $d$

1. Convert the fraction $\frac{e}{n}$ into a continued fraction $[a_0;a_1,a_2, \ldots , a_{k-2},a_{k-1}, a_k]$

2. Iterate over each convergent in the continued fraction: $\frac{a_{0}}{1},a_{0} + \frac{1}{a_{1}},a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots, a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}},$

3. Check if the convergent is $\frac{k}{d}$ by doing the following:

   • Set the numerator to be and denominator to be

   • Check if is odd, if not, move on to the next convergent

   • Check if , if not, move on to the next convergent

   • Set and find the roots of the polynomial

   • If the roots of the polynomial are integers, then we've found . (If not, move on to the next convergent)

4. If all convergents have been tried, and none of them work, then the given RSA parameters are not vulnerable to Wiener's attack.

Here's a sage implementation to play around with:

//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:

Here is a Wiener's attack template: