A world wide number field sieve factoring record: on to 512 bits

We present data concerning the factorization of the 130-digit number RSA130 which we factored on April 10, 1996, using the number field sieve factoring method. This factorization beats the 129-digit record that was set on April 2, 1994, by the quadratic sieve method. The amount of computer time spent on our new record factorization is only a fraction of what was spent on the previous record. We also discuss a World Wide Web interface to our sieving program that we have developed to facilitate contributing to the sieving stage of future large scale factoring efforts. These developments have a serious impact on the security of RSA public key cryptosystems with small moduli. We present a conservative extrapolation to estimate the difficulty of factoring 512-bit numbers

Quantum Cryptography : On the Security of the BB84 Key-Exchange Protocol

Thomas Baignères

In 1984, C.H. Bennet and G. Brassard proposed a new protocol aimed to solve the problem of symmetric cryptographic key exchange. This protocol was called BB84 after the name of its authors. While a traditional method would rely on public key cryptography (like RSA), the BB84 protocol takes benefit of the laws of quantum mechanics, like for example the fact that any quantum measurement can perturb the system. Traditional public key algorithms security often rely on a typical hard mathematical problem. It is well known for example that the ability to factorize easily any number would make the usage of RSA completely insecure. Quantum Key Exchange (QKE) protocols security cannot be proved in a similar way. In this work, we will try to give an overview of security proofs of quantum key exchange protocols, focusing on the BB84 protocol.

2003

Cryptosystems and LLL

Thomas Baignères

Since the late 70’s, several public key cryptographic algorithms have been proposed. Diﬃe and Hellman ﬁrst came with this concept in 1976. Since that time, several other public key cryptosystems were invented, such as the well known RSA, ElGamal or Rabin cryptosystems. Roughly, the scope of these algorithms is to allow the secure exchange of a secret key that will later on be used to encrypt a larger amount of data. All these algorithms share one particularity, namely that their security rely on some mathematical problem which is supposed to be hard (computationally speaking) to solve. For example, it is well known that the ability to factorize easily the product of two large primes without any indication about the primes, would lead to break the RSA cryptosystem. Since those early days, most of the assymetric encryption algorithms that have been proposed relied on the same hard mathematical problems. Yet, it is well accepted that we should not put al l the cryptographic eggs in one basket. This is the reason why Goldreich, Goldwasser, and Halevi proposed in 1997 (exactly 10 years after RSA) a new public-key cryptosystem which security was based on lattice reduction problems. This cryptographic schemes is known as the GGH cryptosystem. Unfortunately, only two years later, Nguyen proposed an attack against GGH which proved that in practice, GGH would not provide the security it originally claimed to have. The attack involved a so called lattice reduction algorithm, known as LLL. The aim of this work is to provide the necessary background to understand the GGH cryptosystem and the attack that goes with it. The basis reduction algorithm LLL has many other applications in cryptography. As an example, we will review a very recent attack against the GNU Privacy Guard software, which is a widely used free implementation of Zimmermann’s famous software. The necessary background about lattices, LLL, . . . will be recalled in sections 2 and 3. Section 4 will review the GGH cryptosystem and Nguyen’s attack against it. Finally, Section 5 will show how lattice reduction techniques can break the ElGamal digital signature scheme implementation in GPGv1.2.3.

2006

Analysis of Bernstein's factorization circuit

Arjen Lenstra

D.J. Bernstein has proposed a circuit-based implementation of the matrix step of the number field sieve factorization algorithm (see "Circuits for integer factorization: a proposal", http://cr.yp.to/papers.html#nfscircuit, 2001). These circuits offer an asymptotic cost reduction under the measure "construction cost × run time". We evaluate the cost of these circuits, in agreement with Bernstein, but argue that, compared to previously known methods, these circuits can factor integers that are 1.17 times larger, rather than 3.01 as claimed (and even this is only under the non-standard cost measure). We also propose an improved circuit design based on a new mesh routing algorithm, and show that, for factorization of 1024-bit integers, the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars. We conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve

2002

Cryptosystems and LLL

Thomas Baignères

2006