Search

Assuming the intractability of factoring, we show that the output of the exponentiation modulo a composite function f N,g (x)=g x mod N (where N=P⋅ Q ) is pseudorandom, even when its input is restricted to being half the size (i.e. x< $\sqrt N$ ). This result is equivalent to the simultaneous hardness of the upper half of the bits of f N,g , proven by Hastad, Schrift and Shamir. Yet, we provide a different proof that is significantly simpler than the original one. In addition, we suggest a pseudorandom generator that is more efficient than all previously known factoring-based pseudorandom generators.

A new type of signature scheme is proposed. It consists of two phases. The first phase is performed off-line, before the message to be signed is even known. The second phase is performed on-line, once the message to be signed is known, and is supposed to be very fast. A method for constructing such on-line/off-line signature schemes is presented. The method uses one-time signature schemes, which are very fast, for the on-line signing. An ordinary signature scheme is used for the off-line stage. In a practical implementation of our scheme, we use a variant of Rabin's signature scheme (based on factoring) and DES. In the on-line phase all we use is a moderate amount of DES computation and a single modular multiplication. We stress that the costly modular exponentiation operation is performed off-line. This implementation is ideally suited for electronic wallets or smart cards.

We present a new serial-parallel concurrent modular-multiplication algorithm and architecture suitable for standard RSA encryption. In the new scheme, multiplication is performed modulo a multiple of the RSA modulus n, which has a diminished-radix form 2 k -v, where k and v are positive integers and v < n. This design is the first concurrent modular multiplier to use a diminished-radix algorithm and to pipeline concurrent modular-reduction to optimize the clock rate. For a modular multiplier of order ranging from 1 to 10 (number of multiplier bits per clock cycle), a faster clock rate and throughput is possible than with other known designs including those of Brickell, Morita, Sedlak and Golze, and Miyaguchi. Throughput estimates for 512-bit RSA decryption range from 100 kbit/s in a serial mode to 650 kbit/s with a modular multiplier of order 10, at a clock rate of 20 MHz on 1.5 μm CMOS.

This article is concerned with various arithmetic operations inGF(2 m ). In particular we discuss techniques for computing multiplicative inverses and doing exponentiation. The method used for exponentiation is highly suited to parallel computation. All methods achieve much of their efficiency from exploiting a normal basis representation in the field.

In this paper we examine the development of a high-speed implementation of a system to perform exponentiation in fields of the form GF(2 n ). For sufficiently large n, this device has applications in public-key cryptography. The selection of representation and observations on the structure of multiplication have led to the development of an architecture which is of low complexity and high speed. A VLSI implementation has being fabricated with measured throughput for exponentiation for cryptographic purposes of approximately 300 kilobits per second.