高效可证安全的伪随机生成器

摘要

本发明设计了一种伪随机序列的生成方法，能够在很小的开销下输出较长的伪随机位。这个伪随机生成器是密码上可证安全的，其安全性基于有限域上多项式重构问题的困难性，可以满足可证安全的密码算法和协议的设计需要，如可直接用于设计比现有加密过程更高效的可证安全流密码算法和分组加密算法等。在一个实施例中，本发明是由一个F_q上的多项式定义的伪随机生成器，q是一个1024位的大素数。通过选择合适的参数，可以在一个模q乘法运算下输出近11个伪随机位，同时其安全级别可以达到2⁸⁰，能满足目前大多数密码应用的需要。此外，由于随机算法和现代通信技术都需要频繁使用随机序列，因此本发明也可应用到这些领域。

主权项

1一种伪随机数或位序列的生成方法，其特征为，这个伪随机生成器是由有限域上的多项式来定义的。选择一个有限域上多项式重构问题的实例PR[z，k，t]，再选择一个随机N-l位的种子x0，从i＝0至多项式m(n)，计算αi+1＝p(xi)mod q，令xi+1为αi+1的最高N-l个有效位，输出αi+1的其余二进制位为σi+1，其中q为一个N位长的大素数，p(x)为有限域Fq上的k次多项式，整数l满足N-l比logN明显大。照此方式计算下去可以得到一个多项式长的输出序列σ1，σ2，…，σi，…，σm(n)，这个输出序列是伪随机的；