During the last few years, a considerable effort has been devoted to the development of reconfigurable computers, machines that are based on the close interoperation of traditional microprocessors and Field Programmable Gate Arrays. Several prototype machines of this type have been designed, and demonstrated significant speed-ups compared to conventional workstations for computationally intensive problems, such as codebreaking. In this paper, we demonstrate an efficient implementation of Elliptic Curve scalar multiplication over GF(2 n ) in Optimal Normal Basis, using one of the leading reconfigurable computers available on the market, SRC-6E. We show how the hardware architecture and programming model of this reconfigurable computer has influenced the choice of the optimum program partitioning scheme. The detailed analysis of the control, data transfer, and reconfiguration overheads is given in the paper. The end-to-end speed-ups in the range from 895 to 1300 compared to the microprocessor implementation are demonstrated depending on the chosen partitioning scheme.

Factorization of large numbers has been a constant source of interest in cryptanalysis. The fastest known algorithm for factoring large numbers is the number field sieve (NFS). The two most time consuming phases of NFS are sieving and matrix step. We propose an efficient way of implementing the matrix step in reconfigurable hardware. Our solution is based on the mesh-routing method proposed by Lenstra et al. We determine the practical size of a partial mesh that can fit in one FFGA device, Xilinx Virtex II XC2V6000. We further extrapolate the computation time for the case of a square systolic array of FFGAs for 512-bit and 1024-bit numbers' factorization. We demonstrate that for practical sizes of numbers used in cryptography, 1024 bits, the matrix step of factorization can be performed using 1024 Virtex II FFGAs in less than 40 days.