BSI-Logo

Workshop on Factoring Large Integers

On September 11./12. there will be a workshop on Factoring at the Ruhr-University Bochum. It is organized by the Federal Office for Information Security (BSI) and the Chair of Cryptology and IT-Security.

Everyone interested in the topic is welcome.

The workshop will take place in Veranstaltungsraum 2 (room number 01/53), which is located at level 01 in the mensa building.

Friday, 11th

9:00-9:30	Reception
9:30-10:15	Antoine Joux, DGA and Université de Versailles Factoring pq² with hints (Abstract Slides) In this talk, we show how a homogeneous version of Coppersmith's small root algorithm can be applied to the problem of factoring numbers of the form N=p^2q, when given some additional side information. This can be applied to break a variant of the NICE cryptosystem called REAL-Nice.
10:15-11:00	Colin Stahlke, Edizone and Ruhr-University Bochum Some Remarks on Polynomial Selection in the GNFS (Abstract Slides) The last step of the polynomial selection process in the GNFS is the local optimization. For a 768 bit number we speed up this part from several CPU years to 400 CPU hours. In the second part, we check that partial sieving gives a hint about the quality of a polynomial pair. Then we improve one of Murphy's quality functions using the data of several thousand polynomial pairs.
11:00-11:30	Break
11:30-12:15	Claus-Peter Schnorr, Goethe-University Frankfurt Average-Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time (Abstract Slides) We propose and analyze novel algorithms for finding shortest and closest lattice vectors. The algorithm NEW ENUM performs the stages of exhaustive enumeration of short / close lattice vectors in order of decreasing success rate. We analyze this algorithm under GSA which in practice holds on the average. A shortest lattice vector is found in polynomial time if the density of the lattice is not close to maximum. This gives NEW ENUM enormous power in attacking lattice based cryptographic schemes, in particular the Ajtai-Dwork scheme uses lattices of low density. The RSA scheme may also be affected. We show under GSA and standard assumptions on the distribution of smooth integers that integers N can be factored in polynomial time by solving (ln N)^4 easy CVP's for the prime number lattice. Each CVP solution of the prime number lattice, for a suitable target vector that encodes N, yields a multiplicative relation modulo N of the primes of its factor basis. The CVP solutions simulate the quadratic sieve algorithm. A main point is that the density of the number field lattice can be made sufficiently small so that the required CVP's can be solved in polynomial time. Similarly the discrete logarithm for the group of units in Z/NZ, for prime N, can be computed in polynomial time. The geometric series assumption (GSA) The lengths of the orthogonal vectors of the given lattice basis decrease by a constant factor $q$ i.e., $\\|b_{i+1}\\| = \\|b_i\\| q$ for all i. This assumption approximately holds, with equality = replaced by \approx , for well reduced bases.
12:15-14:00	Lunch
14:00-14:45	Willi Geiselmann, University Karlsruhe Sieving Hardware for the NFS: Architectures and their Bottlenecks (Abstract Slides) In the last years significant progress has been made in the design of special purpose hardware to support the sieving step of the Number Field Sieve. The two most promising approaches to cope with a 1024 Bit factorization seem to be TWIRL and "Non-Wafer-Scale Sieving Hardware". In this talk different hardware designs will be presented, and the impact of technical improvements (like the increase of the number of transistors per chips or the speed of inter chip communication) on these designs will be discussed.
14:45-15:30	Ralf Zimmermann, Ruhr-University Bochum Implementing the Elliptic Curve Method (ECM) on Special-Purpose Hardware (Abstract Slides) After a brief introduction that reviews the selection process of the most suitable hardware platform (as of 2006/2007), we discuss our ECM implementation for Virtex-4 FPGAs. Since the runtime of the modular multiplication is of crucial importance in elliptic curve arithmetic, we show how to efficiently use DSP blocks of Virtex-4 FPGAs to accelerate that operation. Using this arithmetic unit, we describe how to implement the two phases of the ECM in a processor core of which many can be placed on a single FPGA device. Finally, we outline the integration of our design into a variant of COPACOBANA that was specifically redesigned for the use with ECM. Please note that the hardware architecture of this modified COPACOBANA is presented by a separate talk on the workshop.
15:30-16:00	Break
16:00-16:45	Daniel Loebenberger, B-IT Bonn Optimization strategies for hardware-based cofactorization (Abstract Slides) We use the specific structure of the inputs to the cofactorization step in the general number field sieve (GNFS) in order to optimize the runtime for the cofactorization step on a hardware cluster. An optimal distribution of bitlength-specific ECM modules is proposed and compared to existing ones. With our optimizations we obtain a speedup between 17% and 33% of the cofactorization step of the GNFS when compared to the runtime of an unoptimized cluster. We further analyze the expected inputs for the cofactorization step from a number theoretic perspective and give arguments that the optimization works in almost all cases.
16:45-17:30	Francesco Sica Striding Towards a New Subexponential Factoring Algorithm (Abstract Slides) TBA

Saturday, 12th

9:00-09:45	Tanja Lange, Technische Universiteit Eindhoven ECM using Edwards curves (Abstract Slides) TBA
09:45-10:30	Mathias Herrmann, Ruhr-University Bochum Polynomial Selection Using Lattice Reduction (Abstract Slides) TBA
10:30-11:00	Break
11:00-11:45	Stefan Baumgart, Kiel University COPACOBANA and Upcoming Architectures for Cryptanalysis (Abstract Slides) An overview on the problems and design challenges for a cryptanalysis optimized hardware architecture is presented. Starting with a short introduction of the history of COPACOBANA, the cost optimized parallel code breaker and analyzer, some design problems and their technical solutions are exemplarily explained. These solutions evolved COPACOBANA to a new platform architecture addressing today’s and some futures requirements. The new platform RIVYERA, a high performance massively parallel FPGA based supercomputer for cryptanalysis, is presented.
11:45-12:30	Daniel J. Bernstein, University of Illinois at Chicago ECM speed records on CPU and GPU (Abstract Slides) TBA
12:30-14:00	Lunch

The workshop is free of charge, but for organisatorial reasons, we kindly ask everyone who plans on attending the workshop to register until 8 Sep. via the following link: