实现 Naor-Reingold 伪随机函数的 C++ 程序
Naor-Reingold伪随机函数是另一种生成随机数的方法。
MoniNaor和OmerReingold在1997年描述了私钥和公钥密码学中各种密码原语的有效构造。让p和l是质数，l|p−1。选择乘法阶l的元素gεFp*。然后对于每个n维向量a=(a0,a1,...,an)。
他们定义了函数
fa(x)=ga0.a1x1a2x2…..anxn ε Fp
其中x=x1…xn是整数x的位表示，0≤x≤2n−1
此函数可用作许多密码方案的基础，包括对称加密、身份验证和数字签名。
算法
Begin
Declare the variables p, l, g, n, x
Read the variables p, l, g, n
Declare array a[], b[]
For i=0 to 10, do
x = rand() mod 16;
For j=g to 0, do
b[j] = x mod 2;
x =x divided by2;
Done
Assign mult = 1
For k = 0 to n do
mult = mult *(pow(a[k], b[k]))
Done
Print the random numbers
Done
End示例代码
#include输出结果using namespace std; int main(int argc, char **argv) { int p = 7, l = 2, g = 3, n = 6, x; int a[] = { 1, 2, 2, 1 }; int b[4]; cout << "随机数是： "; for (int i = 0; i < 10; i++) { x = rand() % 16; for (int j = 3; j >= 0; j--) { b[j] = x % 2; x /= 2; } int mult = 1; for (int k = 0; k < 6; k++) mult *= pow(a[k], b[k]); cout << pow(g, mult)<<" "; } }
随机数是： 81 81 3 9 3 81 9 9 3 9