1 of 8

RSA

Will be introduced in this page the fundamentals of RSA, mathematical requirement and also some application with python and openSSL.

This page is pretty long, probably could be split up

Edit: I haved deleted the last part, application with RSA, and i made a special part for this. Maybe we can do the same with the second part: Arithmetic for RSA.

I- Introduction:

RSA is a 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 RSA comes from the surnames of , , and , who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at (the British agency), by the English mathematician . That system was in 1997.

All public-key systems are based on the concept of , 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 . The function involves the use of a public keyto 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, something that should be kept private. Except in certain cases, there exists no efficient algorithm for factoring huge integers.

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 and
Using and , we calculate modulus and its Euler's totient
Now, choose the public exponent 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.

V- Format

Proof of correctness

We now consider necessary for the successful description of an RSA ciphertext. The core of this result is due to which states

for all coprime integers and is .

As a reminder, we say two integers are coprime if they share no non-trivial factors. This is the same statement that .

From the definition of the protocol, we have that

for some . Combining this with Euler's theorem, we see that we recover from the ciphertext

When the requirement does not hold, we can instead look at the equivalences modulo and respectively. Clearly, when we have that and our correctness still holds. Now, consider the case where we have that and Since we have already excluded the case that we can conclude that as is prime. This means that and by the multiplicative properties of the function, we determine that We conclude by invoking the Chinese Remainder theorem with

RSA application

Tutorial for application with RSA. We are going to use openSSL, openSSH and pycryptodome for key generation, key extraction and some implementation with python

Pycryptodome:

Pycryptodome is a python library about cryptography, see the documentation below: https://www.pycryptodome.org/en/latest/ There is an example of RSA key generation with pycryptodome:

from Crypto.Util.number import getPrime, bytes_to_long


def generate_keys():
    e = 0x10001    #public exponent e, we generally use this one by default
    while True:
        p = getPrime(512)
        q = getPrime(512)
        phi = (p - 1) * (q - 1)    #Euler's totient 
        d = pow(e, -1, phi)    #Private exponent d
        if d != -1:
            break

    n = p * q
    public_key = (n, e)
    private_key = (n, d)
    return public_key, private_key


def encrypt(plaintext: int, public_key) -> int:
    n, e = public_key
    return pow(plaintext, e, n)    #plaintext ** e mod n


def decrypt(ciphertext: int, private_key) -> int:
    n, d = private_key
    return pow(ciphertext, d, n)   #ciphertext ** d mod n


message = bytes_to_long(b"super_secret_message")
public_key, private_key = generate_keys()
ciphertext = encrypt(message, public_key)
plaintext = decrypt(ciphertext, private_key)

OpenSSL:

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:

Low Private Component Attacks

Wiener's Attack

Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent $d$ when it's small (less than $\frac{1}{3}\sqrt[4]{n}$ , where $n$ is the modulus). We know that when we pick the public exponent $e$ to be a small number and calcute its inverse $d \equiv e^{-1} \mod \phi(n)$

Wiener's theorem

Wiener's attack is based on the following theorem:

Let $n = pq$ , with $q < p < 2q$ . Let $d < \frac{1}{3}\sqrt[4]{n}$ . Given $n$ and $e$ with $ed \equiv 1 \mod \phi(n)$ , the attacker can efficiently recover $d$ .

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 $\phi(n)$ is correct, the polynomial $x^2 - (n - \phi(n) + 1)x + n$ will have roots $p$ and $q$ , which we can verify by checking if $pq = n$ .

The Attack

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

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:

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

//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:

#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Wiener's attack--------#

d = owiener.attack(e, N)

if d:
    m = pow(c, d, N)
    flag = long_to_bytes(m).decode()
    print(flag)
else:
    print("Wiener's Attack failed.")

Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component $d$ with a further relaxed condition. If $d$ satisfies:

d < N^{0.292}

Then we can use Boneh-Durfee attack to retrive $d$

this, using a graphical directed point of view, can be seen as:

\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\}

Consider $d < N^{i}$ for first, see that

1=ed + \frac{k \phi(N)}{2}\\

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

\phi(N) = (p-1)(q-1) = N-q-p+1

continuing with the equation, we see that

Sage Implementation

Common Modulus Attack

What to do when the same message is encrypted twice with the same modulus but a different public key?

Imagine we have Alice and Bob. Alice sends the SAME message to Bob more than once using the same public key. The internet being the internet, a problem may happen; a bit is flipped, and the public key changed while the modulus stayed the same.

What we know

Let be the following:

m the message in plaintext
e1 the public key of the first ciphertext
c1 the first ciphertext
e2 the public key of the second ciphertext
c2 the second ciphertext
n the modulus that is common to both ciphertexts

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:

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

Recovering the Modulus

When you want to recover N given some (plaintext, ciphertext) pairings

Scenario

Consider the case that that you know a set of (plaintext, ciphertext) pairings - this may be that you are provided them, or that you have access to some functionality that returns ciphertexts for provided plaintexts. If you do not know the modulus, but know the exponent used (note: this may be prone to a brute-force regardless), then given these pairings you can recover the modulus used.

What we know

Let the following be known:

plaintext && ciphertext pairings:

public exponent e (e.g. e = 65537 = 0x10001)

Process

The idea behind this attack is effectively finding common factors between pairings. Recall that, under general RSA encryption, we have:

and recall what modular arithmetic tells us about the relation between these terms, namely that:

This, rearranged, tells us that

However, this is only true for the case that

Thus:

Practical Notes

In reality, you're likely to only need two or three (plaintext, ciphertext) pairings (in the context of ctf challenges and exercises), and as such computations can be manual if needed, but shouldn't be too complex
As it's likely you'll be dealing with large numbers, overflows and precision errors may arise in code - using libraries like gmpy provide support for integers of (theoretically) infinite size, and some nice accompanying features too (like in-built gcd and efficient modular exponentiation)
These two statements are mathematically equivalent, but one is easier to implement in code:

Code Example

Wiener's Attack

Wiener's theorem

Wiener's attack is based on the following theorem:

Let $n = pq$ , with $q < p < 2q$ . Let $d < \frac{1}{3}\sqrt[4]{n}$ . Given $n$ and $e$ with $ed \equiv 1 \mod \phi(n)$ , the attacker can efficiently recover $d$ .

Some observations on RSA

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

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 $\phi(n)$ is correct, the polynomial $x^2 - (n - \phi(n) + 1)x + n$ will have roots $p$ and $q$ , which we can verify by checking if $pq = n$ .

The Attack

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

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]$
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}}}},$
Check if the convergent is $\frac{k}{d}$ by doing the following:
- Set the numerator to be $k$ and denominator to be $d$
- Check if $d$ is odd, if not, move on to the next convergent
- Check if $ed \equiv 1 \mod k$ , if not, move on to the next convergent
- Set $\phi(n) = \frac{ed-1}{k}$ and find the roots of the polynomial $x^2 - (n - \phi(n) + 1)x + n$
- If the roots of the polynomial are integers, then we've found $d$ . (If not, move on to the next convergent)
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:

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

//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:

#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Wiener's attack--------#

d = owiener.attack(e, N)

if d:
    m = pow(c, d, N)
    flag = long_to_bytes(m).decode()
    print(flag)
else:
    print("Wiener's Attack failed.")

RSA

Will be introduced in this page the fundamentals of RSA, mathematical requirement and also some application with python and openSSL.

This page is pretty long, probably could be split up

Edit: I haved deleted the last part, application with RSA, and i made a special part for this. Maybe we can do the same with the second part: Arithmetic for RSA.

I- Introduction:

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 and
Using and , we calculate modulus and its Euler's totient
Now, choose the public exponent 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

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 and are inverses such that , Alice can sign her message by "encrypting" it with the private key such that , where is the signature verifying that the message came from Alice. Alice can now send and to Bob, who is now able to check the authenticity of the message by checking if . If Mallory tries to change , this congruence no longer holds, and since she does not have the private key, she is also unable to provide a maching for her tampered message.

V- Format

Recovering the Modulus

When you want to recover N given some (plaintext, ciphertext) pairings

Scenario

What we know

Let the following be known:

plaintext && ciphertext pairings:

public exponent e (e.g. e = 65537 = 0x10001)

Process

The idea behind this attack is effectively finding common factors between pairings. Recall that, under general RSA encryption, we have:

and recall what modular arithmetic tells us about the relation between these terms, namely that:

a \equiv b\text{ }(mod\text{ } N)\\ a = b + kN \text{ for some } k \in \mathbb{Z}

This, rearranged, tells us that

a - b \equiv 0\text{ } (mod \text{ } N)\\ a - b = kN

What this means for our known pairings is that, given we know and , we can form the relationship:

C_i - M_i^e \equiv 0\text{ } (mod \text{ } N)\\ C_i - M_i^e = k_iN

Thus we can calculate for the value , though don't know either value individually - we want to somehow derive .

Observe that any two pairings will equate to such a value, both with as a factor. We can take the gcd of these two values, and it is probable that the resulting value will be our value, such that:

N = gcd(C_1 - M_1^e, C_2 - M_2^e)

However, this is only true for the case that

gcd(k_1, k_2) = 1

i.e., both and are coprime. In the case that they are not, i.e. , we have that

aN = gcd(C_1 - M_1^e, C_2 - M_2^e) \text{ s.t. } 1 \ne a \in \mathbb{Z}

In such a case, we don't have sufficient information to completely recover the modulus, and require more plaintext-ciphertext pairs to be successful. In general, the more pairings you have, the more confident you can be the value you calculate is . More specifically:

Pr(a \ne1) \rightarrow 0 \text{ as } k\rightarrow \infty

Thus:

N = \lim_{k \rightarrow \infty} gcd(C_1 - M_1^e, C_2 - M_2^e, ..., C_k - M_k^e)

Practical Notes

In reality, you're likely to only need two or three (plaintext, ciphertext) pairings (in the context of ctf challenges and exercises), and as such computations can be manual if needed, but shouldn't be too complex
As it's likely you'll be dealing with large numbers, overflows and precision errors may arise in code - using libraries like gmpy provide support for integers of (theoretically) infinite size, and some nice accompanying features too (like in-built gcd and efficient modular exponentiation)
These two statements are mathematically equivalent, but one is easier to implement in code:

gcd(a, b, c, d, ...) = gcd(a, gcd(b, gcd(c, gcd(d, ...))))

Code Example

import gmpy2

"""
@param pairings
    list: [(pt1, ct1), (pt2, ct2), ..., (ptk, ctk)]
@param e
    int : encryption exponent
@return
    int : recovered N
"""
def recover_n(pairings, e):
    pt1, ct1 = pairings[0]
    N = ct1 - pow(pt1, e)
    
    # loop through and find common divisors
    for pt,ct in pairings:
        val = gmpy2.mpz(ct - pow(pt, e))
        N = gmpy2.gcd(val, N)
    
    return N