148. FN-DSA (구 FALCON)

⚠️ 이 문서는 범용 PQC 서명인 ML-DSA(딜리슘)의 크기가 너무 뚱뚱해서 도저히 집어넣을 수 없는 소형 기기(IoT)나 네트워크 병목 구간을 구원하기 위해, 고도의 수학적 꼼수(푸리에 변환)를 써서 서명의 덩치를 기존 타원곡선 수준으로 극단적으로 쥐어짜 낸 PQC 핀셋 서명 표준, FALCON(FN-DSA)을 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: FN-DSA(Falcon)는 범용 1등인 딜리슘과 똑같은 '격자(Lattice)' 수학을 기반으로 하지만, $NTRU$ 격자라는 더 촘촘한 수학 도화지와 고속 푸리에 변환(FFT) 알고리즘을 섞어 만든 초경량 양자 내성 디지털 서명 알고리즘이다.
  2. 가치: 딜리슘의 서명 크기(약 2.4KB) 대비 **절반 이하의 크기(약 660바이트)**를 자랑한다. 즉, 네트워크 트래픽(MTU) 하나에 무난하게 쏙 들어갈 만큼 다이어트에 성공하여 스마트 카드나 IoT 센서 등 메모리와 대역폭이 쥐꼬리만 한 환경에서 유일한 생존 대안이 된다.
  3. 융합: 치명적 단점은 서명을 생성하는 연산(수학 공식)이 너무나 복잡하고 까다로워서 하드웨어 칩으로 굽기(구현) 힘들다는 점이다. 따라서 모든 곳에 쓰이는 범용(딜리슘)과는 달리, **오직 크기(대역폭)가 목숨보다 중요한 특수 도메인 환경에 한정되어 융합 사용(니치 마켓 표준)**된다.

Ⅰ. 개요 및 왜 2인자(Falcon)가 표준으로 같이 뽑혔나?

NIST의 PQC 서명 공모전 결승전에서 두 개의 격자(Lattice) 기반 서명이 격돌했다. **Dilithium(딜리슘)**과 **Falcon(팔콘)**이다.

  • NIST의 고민:
    • 딜리슘은 너무 만들기 쉽고 속도도 짱짱 빠르다. 당연히 1등이다.
    • 그런데 딜리슘은 서명 크기가 너무 뚱뚱해서(2.4KB), 한 번에 보낼 수 있는 네트워크 패킷 크기(보통 1.5KB)를 터뜨려버린다. 대용량 클라우드 서버는 알아서 패킷을 쪼개고 조립하겠지만, 산에 박아둔 싸구려 화재 감지 IoT 센서나 구형 라우터 장비들은 딜리슘 도장을 던져주면 시스템이 숨이 막혀 뻗어버릴 것이다.
  • 해결책 (투트랙 전략):
    • "인터넷 생태계는 넓다. 범용 1등 딜리슘(ML-DSA)을 밀어붙이되, 덩치가 크면 절대 안 되는 소형 기기들을 위한 구명조끼로 다이어트에 성공한 2등 Falcon(FN-DSA)도 같이 표준으로 합격시켜 주자!"
    • 이로써 2024년, Falcon은 **FN-DSA (FFT-based NTRU-Lattice DSA)**라는 공식 표준 이름표를 달고 화려하게 데뷔했다.

📢 섹션 요약 비유: 딜리슘(1등)은 거대한 덤프트럭입니다. 물건(보안)을 확실하게 나르지만 좁은 골목길(IoT 통신망)에는 들어갈 수가 없습니다. 팔콘(2등)은 오토바이입니다. 엔진(수학) 구조가 복잡해서 만들기는 더럽게 어렵지만, 좁은 골목길을 휙휙 뚫고 들어가 안전하게 편지를 배달해 내는 특수 배달원입니다.

Ⅱ. Falcon의 극한 다이어트 비결 (FFT와 NTRU 격자)

Falcon이 서명 덩치를 딜리슘의 $1/3$ 로 줄일 수 있었던 것은 순전히 수학의 승리다.

1. NTRU 격자의 촘촘함

  • 딜리슘은 LWE(노이즈 섞인 연립방정식)를 쓴다. 구조가 단순한 대신, 안전성을 맞추려면 행렬(표)을 무식하게 크게 그려야 해서 용량이 팽창한다.
  • Falcon은 NTRU라는 구조가 다항식 링(Ring)으로 촘촘하게 맞물린 격자를 쓴다. 밀도가 높아서 작은 크기(적은 비트 수)로도 LWE와 똑같은 양자 방어력 맷집을 뽑아낼 수 있다.

2. FFT (고속 푸리에 변환) 엔진 탑재

  • 신호 처리나 오디오 주파수 분석에 쓰이는 공학 공식인 푸리에 변환(FFT)을 암호학에 끌고 들어왔다.
  • 이 복잡한 서명 생성 과정(가우스 샘플링)을 풀기 위해 FFT를 돌리면, 아주 복잡하고 큰 차원의 다항식 곱셈을 순식간에 압축해서 가볍게 끝내버릴 수 있다.
  • 결과: 공개키 크기 약 897바이트, 서명 크기 666바이트 달성! 기존 RSA-2048 서명 덩치와 거의 맞먹는 수준까지 쥐어짜 내어, 과거 네트워크 칩셋의 변경 없이 그대로 호환이 가능하다.
┌────────────────────────────────────────────────────────────────────────────────┐
│           PQC 서명 3대장의 특성(크기와 복잡성) 비교 시각화                     │
├────────────────────────────────────────────────────────────────────────────────┤
│                                                                                │
│ [ 🚀 ML-DSA (Dilithium) - 범용 대장 ]                                          │
│   - 공개키 + 서명 = 약 3,700 바이트 (존나 큼 🐘)                               │
│   - 개발 난이도: "쉬움! 코딩 초보도 매뉴얼 보고 짤 수 있음."                   │
│   - 결론: 덩치가 커도 감당 가능한 PC, 클라우드, 구글 서버의 황제.              │
│                                                                                │
│ [ 🏎️ FN-DSA (Falcon) - 다이어트 대장 ]                                         │
│   - 공개키 + 서명 = 약 1,500 바이트 (오! 작다 🪶)                              │
│   - 개발 난이도: "지옥☠️ 부동소수점 수학 계산하다가 CPU 미쳐버림."             │
│   - 결론: 코딩하기 토 나오지만, 어떻게든 우겨넣어야 하는 스마트 카드, IoT 픽.  │
│                                                                                │
│ [ 🛡️ SLH-DSA (SPHINCS+) - 콘크리트 대장 ]                                      │
│   - 공개키 + 서명 = 약 17,000 바이트 (미친 괴물 크기 🦖)                       │
│   - 개발 난이도: "이건 격자 수학 털리면 쓸 최후의 보루(플랜 B) 방패야."        │
└────────────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] Falcon(FN-DSA)의 가장 치명적인 약점은 바로 "수학이 너무 지저분하고 구현하기가 지옥 같다"는 점이다. FFT 연산을 하려면 실수(부동소수점, Float) 계산이 들어가는데, 컴퓨터마다 소수점을 쳐내는 반올림(Rounding) 로직이 미세하게 달라 자칫하면 암호가 엇갈리거나, 해커에게 부채널 공격의 실마리를 줄 수 있다. 그래서 NIST는 "웬만하면 그냥 딜리슘 쓰고, 딜리슘 크기 때문에 진짜 시스템 뻗을 거 같은 놈들만 목숨 걸고 팔콘을 조심해서 써라"라고 가이드를 줬다.

  • 📢 섹션 요약 비유: 여행 가방을 쌀 때, 딜리슘은 옷을 대충 구겨 넣고 엄청 큰 트렁크 두 개에 담아 가는 겁니다(쉬움, 무거움). 팔콘은 옷을 진공 압축팩에 넣고 청소기로 공기를 쫙 빨아들인 뒤 테트리스처럼 쌓아서 작은 배낭 하나에 우겨넣는 겁니다(어려움, 가벼움). 평소엔 트렁크를 끌고 가지만, 기내 수하물(좁은 대역폭)만 허용될 땐 어쩔 수 없이 팔콘 짐 싸기 스킬을 써야 합니다.

Ⅲ. 실무 적용 시나리오: 드론과 스마트카드

어떤 기업이 Falcon을 선택해야 할까? 대역폭 1바이트와 찰나의 전송 시간이 생사를 가르는 도메인이다.

  1. 저사양 IoT 기기 및 드론 펌웨어 업데이트
    • 수백 킬로미터 밖의 군사용 드론에게 소프트웨어 업데이트 파일을 쏜다. 이때 해커가 악성코드를 섞을 수 있으니 무조건 양자 내성 전자서명 도장을 찍어 보내야 한다.
    • 드론의 라디오 통신망(LoRa 등)은 대역폭이 바닥을 기어 다닌다. 딜리슘 3KB 서명을 던지면 전송에 1분이 걸리거나 에러가 난다. 이때 팔콘(666바이트)으로 쏙 던져주면 드론이 빠르게 받아 도장 검사 후 펌웨어를 패치한다.
  2. 스마트카드 및 IC칩 (금융)
    • 신용카드 칩 안에는 메모리가 고작 1~2KB밖에 없다. 딜리슘 공개키를 넣으면 메모리 풀(Full)로 에러가 난다. 팔콘의 얇은 키만이 유일하게 이 좁은 칩 속으로 들어갈 자격이 있다.

Ⅳ. 결론

"가장 구현하기 까다로운 자가, 가장 가벼운 왕관을 쓴다." FN-DSA(Falcon)는 범용성에서는 딜리슘에게 왕좌를 내어주었지만, 그 뼈를 깎는 수학적 다이어트(FFT와 NTRU)를 통해 양자 내성 암호가 현실의 물리적 한계(네트워크 병목, 구형 장비)를 돌파할 수 있는 유일한 탈출구를 마련해 주었다. PQC 전환 시기, 수많은 인프라 엔지니어들이 딜리슘의 크기 폭탄을 맞고 좌절할 때 구급함처럼 꺼내어 쓸 수 있는 날카로운 핀셋 표준이 바로 Falcon이다.

📌 관련 개념 맵

  • 전체 분류: PQC (Post-Quantum Cryptography) Digital Signature (전자 서명)
  • 공식 표준 명칭: FN-DSA (FFT-based NTRU-Lattice DSA), FIPS 205
  • 기반 수학: NTRU 격자 (Lattice) + 고속 푸리에 변환 (FFT) 가우스 샘플러
  • 트레이드 오프(장단점): 서명/키 크기가 매우 작음 (장점) ↔ 코딩 및 구현이 극도로 어렵고 복잡함 (단점)

👶 어린이를 위한 3줄 비유 설명

  1. 양자 로봇을 막는 1등 캡슐 도장(딜리슘)은 방어력은 짱인데 크기가 덤프트럭만 해서, 좁은 골목길(스마트폰이나 작은 시계)에는 아예 배달을 갈 수가 없었어요.
  2. 그래서 과학자들이 진공 압축기(FFT 수학)를 써서 도장의 덩치를 3분의 1로 확 쥐어 짜내어 오토바이에 싣고 배달할 수 있는 '팔콘'이라는 2등 캡슐 도장을 만들었죠!
  3. 압축기를 돌리는 과정이 너무 피곤하고 어지러워서 컴퓨터가 짜증을 내지만, 좁은 골목길 배달을 가려면 어쩔 수 없이 이 얇고 빠른 팔콘 도장을 꼭 써야 한답니다!