Naor-Reingold 의사 난수 함수를 구현하는 C++ 프로그램

Naor-Reingold 의사 난수 함수(Pseudo Random Function)는 난수를 생성하는 또 다른 방법 중 하나입니다.

모니 나오르(Moni Naor)와 오메르 라인골드(Omer Reingold)는 1997년에 개인키 암호화 및 공개키 암호화 분야의 다양한 암호학적 기본 요소(primitive)에 대한 효율적인 구성 방법을 발표했습니다.

p와 l이 l | p−1 조건을 만족하는 소수라고 가정해 보겠습니다. 이때 곱셈 차수(multiplicative order)가 l인 원소 g ∈ F_p*를 선택합니다. 그런 다음 각 n차원 벡터 a = (a₀, a₁, ..., a_n)에 대해 다음과 같은 함수를 정의합니다.

f_a(x) = g^{a₀ · a₁ˣ¹ · a₂ˣ² · … · aₙˣⁿ} ∈ F_p

여기서 x = x₁ … x_n은 정수 x(0 ≤ x ≤ 2ⁿ⁻¹)의 비트(bit) 표현을 의미합니다.

이 함수는 대칭 암호화(symmetric encryption), 인증(authentication), 디지털 서명(digital signature) 등 다양한 암호 방식의 기반이 되는 핵심 도구로 활용될 수 있습니다.

알고리즘

Naor-Reingold 의사 난수 함수를 구현하기 위한 알고리즘 절차는 다음과 같습니다.

Begin
   변수 p, l, g, n, x를 선언한다
   변수 p, l, g, n 값을 입력받는다
   배열 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 / 2;
      Done
      mult = 1로 초기화한다
      For k = 0 to n do
         mult = mult * (pow(a[k], b[k]))
      Done
      생성된 난수를 출력한다
   Done
End

동작 원리

먼저 rand() 함수를 이용해 0부터 15 사이의 임의의 정수를 생성한 뒤, 이를 2진수 비트로 변환하여 배열 b에 저장합니다. 이후 지수 계산을 통해 최종 난수값을 도출하며, 이 과정을 총 10회 반복하여 결과를 출력합니다.

C++ 예제 코드

#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

결론

위 예제 코드는 Naor-Reingold 의사 난수 함수의 기본 개념을 단순화하여 구현한 것으로, 입력값을 비트 단위로 분해하고 지수 연산을 적용함으로써 예측하기 어려운 난수 시퀀스를 생성합니다. 실제 암호학 환경에서는 더 큰 소수와 안전한 매개변수를 사용하여 보안성을 확보하게 됩니다.