A random keystream generation apparatus and method for use in an encryption system, generates an m-bit random keystream, using a PS-LFSR with n storage stages for storing n-bit binary data is divided into k sub-storages connected in series, each sub-storage having parallel storage stages (k is a minimum integer larger than the quotient of n divided by m). Each sub-storage stores in the parallel storage stages m-bit parallel binary data received from the previous sub-storage and outputs the m-bit parallel binary data simultaneously in accordance with a system clock signal. A buffer has m storage stages to store m-bit parallel data received from the last sub-storage of the PS-LFSR. M feedback connections receive the outputs of the sub-storages and the buffer corresponding to predetermined primitive polynomials, calculate the primitive polynomials with the received data, and output the calculation results as the bits of the m-bit keystream sequence.