โปรแกรม C++ นำฟังก์ชันสุ่มปลอม Naor-Reingold ไปใช้ (Naor-Reingold Pseudo Random Function)

ฟังก์ชันสุ่มปลอม Naor-Reingold

ฟังก์ชันสุ่มปลอม Naor-Reingold เป็นอีกวิธีหนึ่งในการสร้างตัวเลขสุ่ม

Moni Naor และ Omer Reingold อธิบายการสร้างที่มีประสิทธิภาพสำหรับ primitive ทางเข้ารหัสลับต่างๆ ในคีย์ส่วนตัว (private key) และการเข้ารหัสลับแบบสาธารณะ (public-key cryptography) ในปี 1997 ให้ p และ l เป็นจำนวนเฉพาะที่ l หาร p-1 ลงตัว เลือกสมาชิก g ∈ Fp* ที่มีออเดอร์การคูณเป็น l จากนั้นสำหรับเวกเตอร์ n มิติ a = (a₀, a₁, ..., aₙ)

พวกเขากำหนดฟังก์ชัน

fₐ(x) = g^(a₀·a₁x₁·a₂x₂...aₙxₙ) ∈ Fp

โดยที่ x = x₁ ... xₙ เป็นการแทนบิตของจำนวนเต็ม x, 0 ≤ x ≤ 2^(n-1)

ฟังก์ชันนี้สามารถใช้เป็นพื้นฐานของโครงการเข้ารหัสลับหลายอย่าง รวมถึงการเข้ารหัสลับแบบสมมาตร การรับรองความถูกต้อง และลายเซ็นดิจิทัล

อัลกอริทึม

เริ่มต้น
  ประกาศตัวแปร p, l, g, n, x
  อ่านตัวแปร p, l, g, n
  ประกาศอาร์เรย์ a[], b[]
  For i = 0 ถึง 10
    x = rand() mod 16
    For j = g ถึง 0
      b[j] = x mod 2
      x = x หาร 2
    กำหนด mult = 1
    For k = 0 ถึง n
      mult = mult * (pow(a[k], b[k]))
    พิมพ์ตัวเลขสุ่ม
สิ้นสุด

โค้ดตัวอย่าง

#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 << "The Random numbers are: ";
    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) << " ";
    }
}

ผลลัพธ์ตัวอย่าง

The Random numbers are: 81 81 3 9 3 81 9 9 3 9