FPGA Prototype of Low Latency BBS PRNG

Blum-Blum-Shub (x2 mod N) is proved cryptographically secure pseudorandom generator which passes all the statistical properties of randomness tests. It is secure, because it cannot predict in forward direction as well as in backward direction. The reason is hard to factorize the large integer N (≥ 264) which is the product of two special primes. The major challenge of BBS is the efficient hardware design for the computation of the expression i.e. X2 mod N, in case of large Blum integer N. Among various architectures for BBS Generator, Montgomery is an efficient architecture to perform modular multiplication. But it has a disadvantage that clock latency increases with increase in bit size by (2n+5) clock cycles. Another disadvantage is critical path in n-bit adder used in iterative modular multiplication, which increases with an increase in bit size. Here in this paper, a prefix adder i.e. Han-Carlson adder based architecture is used for a BBS generator that reduces the overall latency in the iterative Montgomery modular multiplication. The design is prototyped using commercially available FPGA chip Virtex5 XC5VLX110T and physical implementation results are reported. This is found that the design can work at maximum frequency of 92.32 MHz and 80.60 MHz with overall latency of 2826.63 ns and 6415.97 ns for the modular size of 128-bit and 256-bit respectively.