As said in the previous post, we will now present Dixon’s algorithm, which is a straightforward implementation of the ideas discussed so far. As we will see, it is still not very fast, but at least it is significantly better than trial division.

# Category Archives: English

# Factoring integers—Factor bases

We are now facing the following problem: given an integer $n$ which we wish to factor, find integers $x_1,\dots,x_k$ such that $\prod \left(x_i^2-n\right)$ is a square. We mentioned in the previous post that Kraitchik basically used trial and error to find such values, but still he did not try completely random values.

# Factoring integers—Fermat and Kraitchik

### Fermat

Some integers with no obvious small divisor, such as for example $8051$, are nonetheless easily factored on paper. One need only notice that

\[ 8051 = 8100-49 = 90^2 – 7^2, \]

and use the well-known identity $a^2-b^2 = (a+b)(a-b)$ to find that $8051 = 83\times 97$.

# Polynomial factorisation over finite fields, part 3: Final splitting (Cantor-Zassenhaus)

*(Part of this.)*

We are left with the following problem: given a polynomial $A \in \mathbf{F}_p[X]$ which is known to be squarefree and the product of irreducible factors which are all of degree $d$, find these factors. One algorithm to do this was introduced by Cantor and Zassenhaus in 1981.

# Polynomial factorisation over finite fields, part 2: Distinct degree factorisation

*(Part of this.)*

We now have our squarefree polynomial $A_i$, which is the product of all the factors of $A$ with exponent $i$. Our goal is to factor it into $A_i = A_{i,1}A_{i,2}\dots A_{i,\ell}$, where $A_{i,d}$ is the product of all the factors of $A_i$ of degree $d$. This is much simpler than the squarefree factorisation algorithm; it is essentially based on the fact that, over a field $\mathbf{F}_p$, the irreducible factors of $X^{p^n}-X$ are precisely the (monic) irreducible polynomials whose degree is a divisor of $n$.

# Polynomial factorisation over finite fields, part 1: Squarefree factorisation

*(Continues this post.)*

We wish to factor a polynomial $A$ with coefficients in the finite field $\mathbf{F}_p$ where $p$ is prime. As we stated in the previous post, the first step is to obtain a *squarefree factorisation* of $A$. Namely, we wish to obtain polynomials $A_1,A_2,\dots,A_k$, which are all squarefree and relatively prime, and such that $A = A_1A_2^2\dots A_k^k$. Ultimately, $A_i$ will be precisely the product of all the irreducible factors of $A$ with exponent $i$, which will ensure that all the above conditions are satisfied. We first need some preliminary results.

# Return-to-libc

*(This is part of my series on program vulnerability exploitation.)*

So far, our method of code execution has been to write a shellcode on the stack, and execute it from there. Since there is normally no reason why a program should need to execute anything on the stack, an obvious countermeasure was to make the stack non-executable. Indeed, if you omit the -z execstack compilation flag on the programs of the previous two posts, the attacks will fail with a segmentation fault. So executing code on the stack is no longer possible.

A new method, now referred to as return-to-libc (or ret2libc for short), was introduced by Solar Designer in 1997. As its name implies, instead of overwriting the return address of our vulnerable function with an address on the stack, we will overwrite it with the address of a *libc* function. The libc library contains all the standard functions such as printf() and exit(), so there is almost surely a function in it that does what we need.

# NOP sleds

*(This is part of my series on program vulnerability exploitation.)*

In the following program, the register eax no longer contains the address of buffer at the end of the execution of the function vuln():

# The Guillou-Quisquater protocol

Introduced by Guillou and Quisquater in 1988, it is a zero-knowledge identification protocol.

The scenario is as follows: we first have a trusted authority, whom we will name Trent. Trent is trusted by everyone: what he says is true. Trent distributes to all interested parties a secret based on their identity, that he only can compute. Then, when Alice wants to identify to Bob, she uses a zero-knowledge protocol to demonstrate that she knows the secret associated to her identity, but without revealing it (so that Bob cannot subsequently impersonate her).

# Return-to-register

*(This is part of my series on program vulnerability exploitation.)*

We saw in the previous post what a shellcode was, and studied one in detail. We also discussed the basic idea of what we want to do with it: write it in memory, and have the processor execute it. The first part is easy: since a shellcode is just a string of bytes, we can pass it to a vulnerable program like we would any other string. The second part is where the challenge is. In this post, we will see one way to do it, which is very simple but works only under very favourable conditions.