💻 컴퓨터 과학

A High-Throughput DSP-Free PRNG for FPGA based on Xoshiro128** and Integer Chaotic Mixing

본 논문은 높은 처리량(5.82 Gbps)을 달성하고 임베디드 애플리케이션에 적합한 작은 풋프린트를 유지하면서도 엄격한 통계적 테스트를 통과하는, Xilinx Zynq-7000 플랫폼을 위한 자원 효율적이고 DSP가 필요 없으며 완전 파이프라인화된 하이브리드 PRNG를 Xoshiro128**, Weyl 시퀀스, 그리고 정수 텐트 맵(integer Tent map)을 결합하여 제시한다.

원저자: Milad Mohammadian, Bahadin Azizinasab, Abobakr Mohammadian, Mahrokh G. Shayesteh, Mohammad Saeed khayati, Sheida Mohammadpour, Mosleh yousefi

게시일 2026-11-09

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Milad Mohammadian, Bahadin Azizinasab, Abobakr Mohammadian, Mahrokh G. Shayesteh, Mohammad Saeed khayati, Sheida Mohammadpour, Mosleh yousefi

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

디지털 세계에서 많은 시스템은 제대로 작동하기 위해 완전히 무작위해 보이는 숫자 시퀀스에 의존합니다. 이러한 시퀀스는 통신 보안, 복잡한 물리 시스템 시뮬레이션, 그리고 암호 프로토콜을 실행하는 데 필수적입니다. 그러나 기계가 진정한 무작위성을 생성하는 것은 어렵기 때문에, 엔지니어들은 이들을 만들기 위해 알고리즘을 사용하여 "의사 난수(pseudo-random)"를 생성합니다. 이것들은 초기 시드(seed)로부터 시작되는 특정 규칙에 의해 생성되지만 관찰자에게는 무작위하게 보이는 결정론적 시퀀스입니다. 하드웨어 설계자들의 과제는 너무 많은 전력을 소비하거나 컴퓨터 칩에서 너무 많은 공간을 차지하지 않으면서도 이러한 시퀀스를 빠르고 효율적으로 만드는 것입니다. 이들이 임베디드 시스템에서 자주 사용되는 재구성 가능한 하드웨어인 FPGA라고 불리는 특수 칩에 구축될 때, 목표는 일반적으로 무거운 수학적 계산을 위해 예약된 비싸고 전력을 많이 소모하는 부품들을 피하면서 높은 속도를 달이고 매우 작은 크기와 에너지 효율성을 유지하는 것입니다.

이란의 대학 연구진들로 구성된 한 팀이 FPGA에서 실행되는 이러한 생성기를 구축하는 새로운 방법을 개발했습니다. 그들의 연구는 일반적인 칩에서 발견되는 고성능 수학 유닛을 사용하지 않고도 숫자를 생성하는 장치를 만드는 데 집중되어 있습니다. 이 팀은 이러한 특수 컴포넌트들에 의존하는 대신, 오직 기본적인 논리 게이트와 표준 메모리 레지스터만을 사용하는 시스템을 설계했습니다. 그 결과, 이 생성기는 훨씬 더 복잡한 설계들과 견줄 만한 5.82 Gbps의 데이터 속도를 구현하면서도 칩의 자원을 매우 적게 사용하고 전력을 최소한으로 소비합니다.

이 새로운 설계의 핵심은 세 가지 서로 다른 숫자 혼합 방법을 결합한 하이브리드 접근 방식입니다. 주요 엔진은 Xoshiro128**라고 불리는 잘 알려진 알고리즘으로, 시퀀스의 주된 원천 역할을 합니다. 이 엔진은 효율적이고 반복되기까지의 주기가 매우 길지만, 숙련된 공격자가 악용할 수 있는 예측 가능한 수학적 구조를 가지고 있습니다. 이를 해결하기 위해 연구진은 두 개의 추가적인 혼합 계층을 더했습니다. 첫 번째 계층은 값들을 이동시켜 다른 종류의 패턴을 만들어내는 단순한 가산 프로세스를 사용합니다. 두 번째 계층은 숫자를 늘리고 접는 방식인 '텐트(tent)' 맵을 사용하는데, 이는 마치 제빵사가 반죽을 접는 것과 유사하지만, 이 경우에는 물리적인 조작 대신 단순한 정수 연산을 통해 접기가 일어납니다. 이러한 계층들은 주 엔진의 예측 가능한 패턴을 깨뜨리기 위해 함께 작동하도록 설계되었으며, 최종 출력을 역설계하기 훨씬 더 어렵게 만듭니다.

연구진은 소프트웨어 설명을 칩의 물리적 레이아웃으로 자동 변환해 주는 고수준 합성(high-level synthesis) 도구를 사용하여 이 시스템을 구축했습니다. 그들은 Xilinx Zynq-7000으로 알려진 특정 유형의 칩에서 설계를 테스트했습니다. 구현은 임베디드 애플리케이션에서 중요한 모든 지표에서 성공적이었습니다. 최종 설계는 칩 상에서 단 934개의 작은 로직 블록을 차지했으며 1,071개의 레지스터를 사용했는데, 이는 매우 조밀한 풋프린트입니다. 결정적으로, 이 설계는 0개의 특수 디지털 신호 처리(DSP) 슬라이스와 0개의 전용 메모리 블록을 사용하였으며, 이는 무거운 자원 없이도 고속 난수 생성이 가능하다는 것을 증명했습니다. 시스템은 181.82 MHz의 주파수에서 작동하여 앞서 언급한 높은 처리량을 제공했습니다. 전력 측면에서, 칩은 작동 중 29mW의 동적 전력을 소비했는데, 이 수치는 하한 추정치이며 설계가 극도로 에너지 효율적임을 시사합니다.

생성된 숫자들이 진정으로 심각한 용도에 사용할 만큼 무작위적인지 확인하기 위해, 팀은 출력값을 엄격한 통계 테스트 세트에 노출시켰습니다. 정부 기관 및 독립 연구자들이 사용하는 표준 스위트를 포함하는 이 테스트들은 시퀀스의 결함을 나타낼 수 있는 패턴, 편향 및 상관관계를 점검합니다. 생성기는 미세한 결함을 찾는 가장 까다로운 테스트를 포함하여 모든 테스트를 통과했습니다. 연구진 또한 시스템이 초기 조건의 변화에 얼마나 민감한지를 분석했습니다. 그들은 초기 설정에서 단 1비트만 바꾸더라도 출력이 완전히 달라진다는 것을 발견했는데, 이는 초기 조건에 대한 민감성(sensitivity to initial conditions)이라고 알려진 특성입니다. 이는 두 장치가 약간 다른 시드로 시작하더라도 완전히 다른 시퀀스를 생성하게 함을 보장하며, 이는 보안에 매우 중요합니다.

이 연구에는 각 부분이 시스템에 기여하는 상세한 내역도 포함되었습니다. 연구진은 주요 Xoshiro128** 엔진이 이미 통계적으로 충분히 강력하여 단독으로도 테스트를 통과할 수 있다는 것을 발견했습니다. 추가된 계층들은 숫자의 통계적 품질을 개선하지는 않았지만, 다른 중요한 일을 수행했습니다. 즉, 주 엔진을 예측 가능하게 만들었던 선형적 수학 구조를 제거한 것입니다. 이러한 계층들을 추가함으로써, 연구진은 공격자가 생성기의 출력을 보고 내부 상태를 파악하는 것을 훨씬 더 어렵게 만들었습니다. 주 엔진만 있다면 비교적 빠르게 역설계될 수 있었겠지만, 전체 하이브리드 시스템은 이를 깨뜨리기 위해 훨씬 더 복잡하고 시간이 많이 드는 노력을 요구하며, 결과적으로 속도나 효율성을 희생하지 않으면서 특정 유형의 공격으로부터 생성기를 효과적으로 보호합니다.

이 작업은 무거운 하드웨어 구성 요소에 의존하지 않고도 자원이 제한된 환경을 위한 고성능 난수 생성기를 구축하는 것이 가능하다는 것을 시사합니다. 이 설계는 속도, 자원 사용량, 그리고 보안 사이의 실질적인 절충안을 제공합니다. 연구진은 폴딩 계층에서 사용된 수학적 단계들이 대수적으로 복잡하지는 않다고 언급했지만, 다른 계층들과의 결합을 통해 견고한 시스템을 만들어냈습니다. 연구 결과는 이 접근 방식이 공간과 전력이 최우선인 임베디드 시스템에 매우 적합하며, 다양한 장치에 통합될 수 있는 신뢰할 수 있는 무작위성 소스를 제공한다는 것을 보여줍니다. 연구진은 다른 이들이 결과를 검증하고 구축할 수 있도록 코드와 데이터를 공개하여, 결과가 재현 가능하고 설계가 미래의 요구에 따라 조정될 수 있도록 했습니다.

기술 요약: Xoshiro128 및 정수 카오틱 믹싱 기반의 FPGA용 고처리량 DSP-Free PRNG**

문제 정의
본 논문은 FPGA 상에서 카오틱 의사 난수 생성기(PRNG)를 구현할 때 발생하는 통계적 품질, 처리량, 그리고 하드웨어 점유 면적 사이의 트레이드오프 문제를 다룹니다. 기존의 연속형 카오틱 맵(chaotic maps)은 동적 퇴화(예: 짧은 주기)를 방지하기 위해 고정밀 부동 소수점 연산을 요구하는 경우가 많으며, 이는 상당한 양의 DSP 슬라이스와 BRAM을 소비하여 전력 소선 소비를 증가시키고 자원이 제한된 장치로의 이식성을 제한합니다. 반대로, 경량 구현 방식은 TestU01 BigCrush와 같은 엄격한 통계 테스트 세트를 통과하지 못하는 경우가 많습니다. 많은 고처리량 설계들은 FPGA의 한정된 하드웨어 자원인 DSP 슬라이스에 크게 의존합니다. 저자들은 DSP 슬레이스나 BRAM을 사용하지 않으면서도 깊은 통계적 검증을 유지하며 멀티 기가비트 처리량을 달abatic 할 수 있는 솔루션을 모색합니다.

방법론
제안된 아키텍처는 High-Level Synthesis(HLS)를 사용한 Out-of-Context(OOC) 플로우를 통해 Xilinx Zynq-7000 SoC(xa7z010 디바이스)에 구현된 하이브리드 PRNG입니다. 이 설계는 세 가지 결정론적 메커니즘을 결합합니다:

Xoshiro128 백본:** 기본 상태 엔진 역할을 수행하며, 긴 주기( $2^{128} - 1$ )의 결정론적 시퀀스를 제공합니다. 이는 XOR, 논리 시프트 및 회전을 통해 업데이트되는 128비트 상태 벡터를 활용하며, 출력 생성을 위한 비선형 스크램블링 함수를 포함합니다.
Weyl Sequence Mixer: $2^{32}$ 모듈로에 대한 가산 재귀(additive recurrence)에 기반한 보조 레이어입니다. 이는 백본의 XOR 기반 전이를 보완하기 위해 캐리 전파(carry-propagating) 정수 믹싱을 도입합니다.
Integer Tent Map: "확장 및 접기(stretch-and-fold)" 연산을 수행하는 이산화된 브랜치리스(branchless) 정수 맵입니다. 이는 비트 단위 섭동(perturbation)과 회전을 사용하여 상태를 확산시킵니다.

주요 기여
본 논문은 다섯 가지 구체적인 기여를 강조합니다:

브랜치리스 정수 매핑: 카오틱 레이어는 최상위 비트(MSB)가 멀티플렉서 선택 신호로 작동하는 상수 시간(constant-time) 하드웨어 로직으로 구현되었습니다. 이는 제어 흐름 분기(control-flow branching)를 피하고, DSP 슬라이스나 임베디드 메모리의 필요성을 제거하기 위해 시프트-앤-애드(shift-and-add) 로직과 배열 파티셔닝을 활용합니다.
HLS 최적화: 설계는 Initiation Interval(II) 1을 달하여 클록 사이클당 하나의 32비트 출력 워드를 생성할 수 있습니다. 이는 C-to-RTL 최적화 지침을 통해 멀티 도메인 상태 업데이트의 데이터 의존성을 줄임으로써 달성되었습니다.
DSP-Free 및 BRAM-Free 구현: 전체 데이터패스는 AXI4 인터페이스를 포함하여 표준 로직 슬라이스(LUT 및 Flip-Flop)를 사용하여 구현되었습니다. 이 구현은 DSP48E1 프리미티브와 BRAM 타일을 전혀 사용하지 않습니다.
포괄적 평가: 생성기는 NIST SP 800-22, Dieharder, 그리고 전체 TestU01 BigCrush 배터리에 대해 검증되었습니다. 또한, 저자들은 Weyl 및 Tent 레이어의 기여를 격리하는 절제 연구(ablation study)를 제공합니다.
구조적 분석: 저자들은 추가된 레이어들이 통계적으로 출력을 개선하지는 않지만(Xoshiro128**이 이미 BigCrush를 통과하므로), 일반 생성기의 선형 출력 구조를 효과적으로 제거한다는 것을 입증합니다. 이는 직접적인 상태 복구 및 키 독립적 선형 복잡도 구별기(linear-complexity distinguishers)를 방지하여, 유효 공격 복잡도를 사소한 복구 시간에서 약 $2^{63}$ 번의 추측 수준으로 확장합니다.

실험 결과
Xilinx Zynq xa7z010 디바이스에서 181.82 MHz 클록 주파수로 구현된 코어는 다음 지표를 달성했습니다:

처리량: 5.82 Gbps (지속).
자원 사용량: 934개 Slice LUTs (디바이스의 5.31%) 및 1,071개 Slice Registers.
전력: 29 mW 동적 전력 (제로 딜레이 추정치, 하한값) 및 글리치 활동을 포함한 42 mW.
통계적 성능: 생성기는 NIST SP 800-22의 15개 카테고리 전체, Dieharder의 114개 테스트 전체, 그리고 TestU01 BigCrush의 160개 통계 전체를 통과했습니다.
민감도: 설계는 거의 균등한 출력 통계와 초기화 변경에 대한 높은 민감도를 보이며, NPCR 및 UACI 지표가 독립적인 균등 시퀀스에 대한 이상적인 값에 근접합니다.
절제 연구 결과: 연구는 Weyl과 Tent 레이어가 개별적으로보다는 결합되었을 때 효과적임을 확인합니다. 일반 Xoshiro128**은 네 개의 출력으로부터 약 2,000회의 시도로 약 28 µs 내에 128비트 상태를 완전히 복구할 수 있는 반면, 전체 하이브리드 설계는 약 $2^{63}$ 의 결합 추측을 필요로 합니다. Tent 맵은 대수적으로 아핀(affine)하며, 비선형성을 더하기보다는 상태 시퀀스의 주기를 연장합니다.

의의 및 주장
본 논문은 제안된 설계가 자원이 제한된 임베디드 애플리케이션을 위한 실용적인 트레이드오프를 제공한다고 주장합니다. 이것이 가장 빠르거나 가장 작은 생성기라고 제시하는 것이 아니라, 희소한 DSP 자원에 의존하지 않고 표준 로직에서 멀티 기가비트 처리량을 달성하면서 전체 BigCrush 배터리 수준까지 검증된 DSP-free, BRAM-free 정수 코어임을 강조합니다.

저자들은 추가된 레이어들의 가치가 통계적이라기보다 구조적(선형 시그니처 제거 및 주기 연장)이라는 점을 강조합니다. 또한 Tent 맵의 대수적 아핀 특성, Weyl 시드의 약한 민감도, 그리고 전력 수치가 이상적인 클록 네트를 가정한 OOC 추정치라는 점을 포함한 한계를 인정합니다. 결론적으로, 본 아키텍처는 희소한 DSP 자원에 대한 의존성 없이 컴팩트하고 고처리량이며 통계적으로 견고한 난수 소스를 필요로 하는 애플리케이션에 적합합니다.

유사한 논문