Lehrstuhl Kryptologie & IT-Sicherheit

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.

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.

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.

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.

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.

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.

TBA

TBA

TBA

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.

TBA