Chương trình C++ triển khai hàm giả ngẫu nhiên Naor-Reingold

Hàm giả ngẫu nhiên Naor-Reingold (Naor-Reingold Pseudo Random Function) là một phương pháp khác để tạo số ngẫu nhiên.

Moni Naor và Omer Reingold đã mô tả các cấu trúc hiệu quả cho nhiều nguyên ngữ mật mã học trong mật mã khóa riêng cũng như khóa công khai, vào năm 1997. Cho p và l là các số nguyên tố với l | p-1. Chọn một phần tử g ∈ Fp* có bậc nhân l. Sau đó, với mỗi vectơ n chiều a = (a₀, a₁, ..., a_n).

Họ định nghĩa hàm:

fa(x) = ga0·a1x1·a2x2·...·anxn ∈ Fp

trong đó x = x₁ ... x_n là biểu diễn bit của số nguyên x, 0 ≤ x ≤ 2^n-1.

Hàm này có thể dùng làm cơ sở cho nhiều lược đồ mật mã bao gồm mã hóa đối xứng, xác thực và chữ ký số.

Thuật toán

Bắt đầu
    Khai báo biến p, l, g, n, x
    Đọc các biến p, l, g, n
    Khai báo mảng a[], b[]
    For i = 0 đến 10
        x = rand() mod 16;
        For j = g xuống 0
            b[j] = x mod 2;
            x = x chia 2;
        Gán mult = 1
        For k = 0 đến n
            mult = mult * (pow(a[k], b[k]))
        In số ngẫu nhiên
Kết thúc

Mã ví dụ

#include <iostream>
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 << "Các số ngẫu nhiên là: ";
    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) << " ";
    }
}

Kết quả đầu ra

Các số ngẫu nhiên là: 81 81 3 9 3 81 9 9 3 9