1024비트 소수 생성의 어려움

 (glitchcomet.com)
4P by GN⁺ | ★ favorite | 댓글 1개
  • 2048비트 RSA 키에 필요한 두 개의 약 1024비트 소수를 Rust로 직접 생성하며, 외부 의존성 없이 난수 생성부터 큰 정수 연산까지 구현한 실험임
  • 단순한 trial division은 16비트에서는 약 40ms로 충분했지만, 64비트에서도 최적화 후 6.4초가 걸려 1024비트로는 확장하기 어려웠음
  • Fermat 테스트는 빠르지만 pseudoprime을 걸러내지 못할 수 있어, 최종 판정에는 k=10의 Miller-Rabin 테스트를 사용함
  • 기본 정수형 한계를 넘기 위해 직접 BigInt를 만들었고, bool 배열에서 byte 배열, u64 청크 구조로 바꾸며 1024비트 소수 생성 시간이 32분대에서 60~90초 수준으로 줄어듦
  • 최종 구현은 u64 청크 BigInt, 빠른 나눗셈, 작은 소수 trial division, 후보값 +2 증가, 16개 스레드 병렬 실행을 결합해 평균 약 40ms에 1024비트 소수를 찾았지만, 검증된 암호 라이브러리는 아님

RSA용 1024비트 소수를 직접 만들기

  • 목표는 RSA 키 생성에 쓸 수 있는 소수를 직접 생성하는 것이었음
    • 2048비트 RSA 키는 두 소수의 곱으로 만들어지므로, 각각 약 1024비트 크기의 소수가 필요함
    • 도전 과제는 자연스럽게 1024비트 소수 생성으로 좁혀짐
  • 실험에는 세 가지 제약을 둠
    • 코드는 처음부터 작성하고 외부 의존성을 쓰지 않음
    • 외부 하드웨어나 클라우드 없이 AMD Ryzen 7 CPU와 16GB RAM이 있는 노트북을 사용함
    • “합리적인 시간” 안에 소수를 생성해야 함
  • 언어는 최근 배우고 있던 Rust를 선택함
    • 저수준 개념을 다루기에 충분히 가깝고, 코드 조각을 이해하기에는 충분히 높은 수준이라고 봄

16비트와 64비트에서 드러난 trial division의 한계

  • 기본 흐름은 N비트 난수를 반복 생성하고, 소수성 검사를 통과하면 종료하는 방식임
  • 난수는 Rust의 rand crate 대신 Linux의 /dev/urandom을 직접 읽어 만듦
    • /dev/urandom은 Linux 커널의 CSPRNG에 접근하는 의사 장치 파일임
    • 커널은 사용자 환경에서 엔트로피를 수집하고 ChaCha20 기반 결정적 스트림 암호를 주기적으로 시드함
  • 16비트 난수는 첫 비트와 마지막 비트를 1로 설정함
    • 마지막 비트 1은 홀수 보장용임
    • 첫 비트 1은 필요한 비트 범위 전체를 쓰기 위한 장치임
  • 16비트에서는 3부터 sqrt(num)까지 나눠보는 trial division만으로도 약 40ms에 소수를 찾음
    • 예시 실행은 Prime found: 44809, 전체 시간은 약 0.038초였음
  • 64비트로 확장하자 단순 trial division은 약 30초가 걸림
    • 이후 6k±1 형태의 후보만 검사하고, 작은 소수 목록으로 먼저 나눠보는 방식으로 개선함
    • 개선 후 64비트 소수 생성 시간은 약 6.414초였음
  • 64비트에서도 6초가 걸리면서, 이 방식으로는 1024비트 소수 생성에 도달하기 어렵다는 한계가 분명해짐

확률적 소수 판정으로 전환

  • 결정적 알고리듬 중 APR-CL과 ECPP를 찾아봤지만, 수학적으로 복잡하고 접근 가능한 설명이 부족해 구현 대상으로 삼기 어려웠음
  • OpenSSL 소스 코드와 NIST 권고를 살펴본 뒤, RSA를 포함한 실제 사용 사례에서 확률적 소수 판정이 널리 쓰인다는 점을 확인함
  • 이후 알고리듬은 수가 “소수임을 증명”하기보다, 특정 정확도로 probable prime이라고 판정하는 방식으로 바뀜

  • Fermat 테스트

    • Fermat의 작은 정리는 p가 소수이고 a가 p로 나누어떨어지지 않으면 a^(p-1) = 1 mod p가 성립한다는 관계를 사용함
    • 단순 거듭제곱은 u128에서 오버플로가 발생하므로, 모듈러 거듭제곱을 구현함
    • pow()는 지수를 u32로 받으며, u128을 더 큰 지수로 올리면 오버플로가 발생할 수 있음
    • 곱셈 자체도 u128 범위를 넘을 수 있어, 임시로 64비트 수를 u128 안에 저장하는 방식으로 진행함
    • Fermat 테스트는 빠르지만 Fermat pseudoprime 때문에 합성수를 소수로 잘못 판정할 수 있음
    • 이런 합성수는 드물어도 충분히 많아, Fermat 테스트만으로는 신뢰하기 어렵다고 봄

  • Miller-Rabin 테스트

    • Miller-Rabin은 Fermat 테스트와 같은 원리에 기반하지만 더 강한 확률적 소수 판정 알고리듬으로 쓰임
    • 구현은 n-1 = 2^s × d 형태로 2의 거듭제곱을 분리한 뒤 여러 조건을 검사함
    • a^d = 1 mod n
    • 또는 어떤 0 <= r < s에 대해 a^(2^r × d) = n - 1 mod n
    • 128비트 실험에서는 Fermat 테스트와 비슷하게 약 0.042초에 소수를 찾음
    • Miller-Rabin의 최악 오류 한계는 4^-k, 큰 n에서 평균적으로는 8^-k 수준임
    • k=10일 때 평균 오류 확률 계산은 0.000000000931323%였음
    • 이는 동전 30번을 연속으로 던져 모두 앞면이 나올 확률인 2^-30과 같다고 비교함
    • 실제 암호용에서는 랜덤 base 선택과 적대적 조건을 더 조심해야 함

직접 BigInt 만들기

  • Rust 기본 정수형만으로는 64비트를 넘어 충분히 큰 수를 다루기 어려워 임의 정밀도 정수(BigInt) 구현이 필요해짐
  • 외부 bigint crate를 쓰지 않는 제약 때문에 BigInt도 직접 구현함

  • 시도 1: 숫자 자릿수 배열

    • 처음에는 큰 수를 10진수 자릿수 배열로 저장하는 방식을 시도함
    • 덧셈과 곱셈은 손계산 방식처럼 구현할 수 있었지만, 나눗셈 구현에서 막혀 포기함

  • 시도 2: bool 기반 이진 배열

    • 두 번째 방식은 수를 0과 1의 배열로 저장하는 구조였음
    • BigInt는 [bool; 2048] 배열을 사용함
    • 1024비트 수끼리 곱하면 최대 2048비트 공간이 필요해 2048비트를 잡음
    • 덧셈과 뺄셈은 full adder 방식으로 구현함
    • 곱셈은 이진수 특성을 이용해 shift-and-add 방식으로 처리함
    • 나눗셈은 이진 long division으로 구현함
    • 이 구현으로 첫 1024비트 소수를 찾는 데 성공했지만, 실행 시간은 약 32분 44.90초였음
    • 기술적으로 목표는 달성했지만, “합리적인 시간”이라는 제약에는 맞지 않았음

  • 시도 3: byte 청크

    • bool 배열의 각 bool이 1비트가 아니라 1바이트를 차지한다는 점을 확인함
    • [bool; 2048]은 2048비트가 아니라 2048바이트를 사용함
    • 이후 2048비트를 256바이트 배열에 저장하는 방식으로 바꿈
    • 덧셈, 뺄셈, 곱셈은 큰 변경 없이 작동했고, 나눗셈은 byte 청크를 비트 목록처럼 다루도록 조정함
    • 이 방식으로 1024비트 소수 생성 시간은 4분 43초까지 줄어듦

  • 시도 4: u64 청크

    • byte 청크 방식은 사실상 높은 기수의 자릿수를 쓰는 digit 기반 BigInt였음
    • 다음 단계에서는 2048비트를 u64 청크 32개로 저장함
    • 각 청크는 하나의 “자릿수”처럼 동작함
    • 두 u64 청크를 곱한 결과를 담기 위해 u128을 사용함
    • 이 구조에서는 1024비트 수를 10진수 309자리 대신 u64 청크 16개로 표현할 수 있음
    • 1024비트 소수 생성 시간은 60~90초까지 개선됨

병목 최적화

  • 간단한 벤치마크에서 binary 구현과 u64 청크 구현의 차이가 뚜렷했음
    • a + b와 a - b: 5537.35ns → 123.57ns
    • a * b: 1292283.14ns → 842.32ns
    • a / b와 a % b: 733446.76ns → 44440.12ns
    • a < b와 a > b: 2506.02ns → 58.91ns
  • 이후 최적화는 주로 나눗셈, 곱셈, Miller-Rabin 내부 연산, 후보 생성 로직에 집중함

  • 나눗셈

    • 가장 큰 병목은 나눗셈이었음
    • u64 청크 구조에서도 기존 나눗셈은 여전히 한 비트씩 long division을 수행함
    • Handbook of Applied Cryptography의 598쪽 알고리듬을 참고해 radix 기반 long division을 구현함
    • dividend의 앞 3개 “자릿수”와 divisor의 앞 2개 “자릿수”로 현재 quotient “자릿수”를 추정하는 방식임
    • 이 구현은 나눗셈 1회당 약 40,000ns를 절약함
    • divisor가 단일 u64 청크이면 u128을 사용해 더 직접적인 long division을 수행하도록 특수 처리함
    • Miller-Rabin에서 이런 경우가 자주 나타남

  • 곱셈

    • 곱셈은 중간 결과 저장용 BigInt를 제거하도록 루프를 재배치해 약 2배 빨라짐
    • 점유된 청크 개수를 계산해 0이 아닌 청크에 대해서만 루프를 돌도록 바꿈
    • BigInt는 대부분 1024비트 이하 수를 저장하므로 2048비트 공간의 절반이 비어 있는 경우가 많음
    • Karatsuba나 FFT 기반 곱셈도 검토했지만, 직접 구현하기엔 복잡했고 현재 곱셈이 충분히 빨라졌다고 판단함

  • Miller-Rabin 내부 최적화

    • Miller-Rabin 구현에서는 비용이 큰 연산을 줄이는 데 집중함
    • x = mod_exp(x, 2, n) 대신 x = (x * x) % n을 직접 수행함
    • 첫 mod_exp()는 단순화한 인라인 버전으로 바꿔 함수 호출 오버헤드를 줄임
    • 짝수 검사에 num.is_even()을 추가해 % 2 계산을 피함
    • d / 2는 d >>= 1로 바꿈
    • += 1, -= 1은 increase()와 decrease()로 특수 처리함
    • 특히 is_even()과 d >>= 1은 각각 약 70,000ns 이득을 냄
    • 최종 벤치마크에서 u64 청크 최적화 버전은 크게 빨라짐
    • a * b: 842.32ns → 295.04ns
    • a / b와 a % b: 44440.12ns → 831.77ns
    • a / 2: 75121.58ns → 60.89ns
    • a % 2 == 0: 78400.87ns → 21.65ns
    • a - 1: 103.15ns → 67.54ns

최종 1024비트 소수 생성기

  • 최종 함수는 먼저 /dev/urandom에서 1024비트 난수를 읽음
    • 최상위 비트를 켜 1024비트 크기를 보장함
    • 최하위 비트를 켜 홀수를 보장함
  • 이후 새 난수를 매번 다시 읽지 않고, 후보값에 2를 더해 다음 홀수 후보로 이동함
    • increase_by_2()는 대부분 u64 청크 하나의 덧셈만 수행함
  • Miller-Rabin 전에 작은 소수 목록으로 먼저 trial division을 수행함
    • 최종 코드에서는 첫 1000개 작은 소수를 사용함
    • 작은 소수는 단일 u64 청크에 들어가므로, 빠른 단일 청크 나눗셈 특수 처리를 활용할 수 있음
  • 이 문제는 공유 메모리나 스레드 간 동기화가 필요 없는 embarrassingly parallel 형태로 다룰 수 있음
    • 16개 CPU 스레드가 각각 소수를 찾고, 가장 먼저 결과를 보내는 스레드의 값을 사용함
  • 최종 실행 예시는 약 0.086초 elapsed time을 기록함
    • CPU 사용률은 690%로 표시됨
  • 100회 실행 평균은 0.04109 ± 0.00307초였음
    • 평균적으로 약 40ms에 1024비트 소수를 찾음
    • 개별 prime_1024bit() 호출은 무작위성 때문에 약 8ms부터 약 800ms까지 변동할 수 있음
    • 병렬 실행으로 가장 빠른 결과를 선택해 변동을 완화함

코드와 한계

  • 전체 코드와 저장소는 github에 공개됨
  • 토론 링크는 hackernews와 reddit에 있음
  • 이 구현은 실제 암호학적으로 안전하다고 보기 어렵고, 목적도 암호용 라이브러리 제작이 아니라 학습과 구현 실험에 가까움

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 큰 소수를 찾는 작업을 작업 증명 함수의 일부로 쓴 암호화폐가 몇 개 있었고, 8년쯤 전에는 아주 빠른 소수 판정 구현만으로도 돈을 꽤 벌 수 있었음
    한동안 riecoin 채굴 소프트웨어의 작성자이자 유지관리자였는데, 이유는 잘 모르겠고 그냥 소수를 좋아해서였던 듯함
    이 글은 빠른 소수 판정의 1순위 최적화인 Montgomery 곱셈을 빠뜨렸음: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
    이는 실용적인 고속 모듈러 지수승 구현의 기반이 됨
    당시 학계에 있었고 지금은 Nvidia에 있는 것으로 아는 Niall Emmart가 정말 엄청나게 빠른 GPU 큰정수 라이브러리 CGBN을 공개했음: https://github.com/NVlabs/CGBN
    아직도 내가 아는 가장 빠른 배치 모듈러 지수승 구현이고, 잠깐 덕후처럼 감탄하자면 숨이 멎을 정도임
    언젠가 이 덕분에 작은 암호화폐의 생산을 5년쯤 지배했던 이야기를 써야겠음. 그리고 Python에는 pow(x, y, m)의 세 인자 형태로 x^y % m을 계산하는 꽤 괜찮은 모듈러 지수승이 들어 있음
    이걸 쓰면 직접 구현하고 싶을 때 Fermat 또는 Miller-Rabin 소수 판정을 아주 쉽게 만들 수 있고 꽤 재미있음. 직접 만들기 싫다면 gmp 라이브러리의 mpz_probab_prime()도 좋음. gmp가 당연히 더 빠르지만, 큰 소수를 가지고 놀 때 두 줄짜리 Fermat 테스트의 재미를 이기긴 어려움

    • Niall은 빠른 다중 스칼라 곱셈 관련 ZPrize 수상 제출작 중 하나에도 참여했음
      배치 모듈러 지수승과 밀접하지만, 소수 모듈러가 아니라 타원곡선 위에서 동작한다는 차이가 있음. CGBN 작업을 이어받은 결과라고 봄
      작년에 Stanford 암호학 점심 세미나에서 좋은 발표를 했고, 슬라이드와 녹화도 온라인에 있음
      https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
      https://www.youtube.com/watch?v=KAWlySN7Hm8
    • 그런 암호화폐가 왜 그렇게 맞춤형 작업 증명 함수를 썼는지 궁금함
      암호가 어쨌든 소수를 쓴다는 막연한 생각만 있고 언제 왜 쓰는지 몰랐던 건지, 아니면 더 깊은 이유가 있었던 건지 알고 싶음
    • pow(x,e,mod) 때문에 Perl에서 Python으로 갈아탔음

  • 주어진 최대 수 범위가 있으면 Miller-Rabin을 사실상 결정적으로 만드는 건 간단함
    해당 범위 안의 모든 의사소수를 함께 걸러내는 것으로 증명된 밑들을 고르면 됨
    목록도 길어지지 않음. Miller-Rabin은 정말 강력함

    • 1024비트 수 범위에서는 그 밑들이 무엇인지 궁금함
      온라인에서 답을 찾지 못했음
    • 게다가 그냥 소수를 찾는 중이라면, 소수처럼 보이는 후보를 골라서 결정적 테스트로 확인할 수 있음

  • 인라인 어셈블리 한 줄이면 큰정수의 초등학교식 곱셈이 간단해짐: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
    과거로 돌아가 C 언어에서 하나만 바꿀 수 있다면 확장 곱셈 개념을 넣고 싶음. Rust에도 없다는 게 아쉬움. 하드웨어 지원은 어디에나 있음. Cortex M0는 나눗셈도 안 하지만 확장 곱셈은 있음
    오래전에 작성한 아주 못생긴 장난감 RSA 구현에서 나온 코드임: https://github.com/jcalvinowens/toy-rsa
    Fermat 테스트만으로도 버틸 수 있었던 이유는, 소수들이 실제로 소수가 아니면 알고리즘이 동작하지 않기 때문이었음. Fermat 테스트는 빠르고, 암호화/복호화 한 번이면 둘 중 하나가 Fermat 거짓말쟁이일 극도로 작은 가능성도 제거됨
    다만 소수가 아닌 P/Q 값으로도 메시지를 성공적으로 암호화/복호화할 수 있는 RSA 키쌍이 존재하지 않는다고 증명할 수 있는지는 모르겠음. 실제 구현에선 당연히 정석이 아니겠지만, 답을 찾은 적이 없음

    • 흥미롭게도 C에는 이제 큰정수가 있음
      C23에서 _BitInt(N) 타입이 추가됐고, 예를 들면 128바이트 타입으로 _BitInt(1024)를 쓸 수 있음
      다만 컴파일러 지원은 제한적임. Clang에서 N을 128보다 크게 허용하려면 -fexperimental-max-bitint-width=N 플래그를 줄 수 있음. N이 128보다 크고 _BitInt(N)를 나누면 컴파일러가 그냥 크래시하지만, +, -, *는 기대대로 동작함
    • Zig에서는 이게 비교적 쉬움
      @mulWithOverflow 내장 함수가 있어서 결과와 함께 오버플로 비트를 반환하고, 정수는 (u|i)65535까지 있음
      하는 일에 따라 오버플로를 감지한 뒤 더 큰 타입으로 올리거나, 먼저 올린 뒤 선택적으로 잘라낼 수 있음
      또 별도 연산자 *|로 포화 곱셈을, *%로 래핑 곱셈을 지원함. 이런 의미론이 필요할 때 쓸 수 있음. 그 외의 오버플로는 안전성 검사 대상의 정의되지 않은 동작이라 Debug와 ReleaseSafe 빌드 모드에서는 패닉이 남
    • p와 q가 서로소인 Carmichael 수라면 RSA는 여전히 메시지를 성공적으로 암호화하고 복호화할 수 있음
      다만 p*q가 더 작은 소인수를 갖게 되어 인수분해가 쉬워지므로 보안성은 낮아짐
    • 대부분의 C 컴파일러와 Rust에서는 더 큰 타입으로 캐스팅한 뒤 곱하면 정확히 원하는 기계어 명령이 생성되는 것으로 알고 있음
    • Philip Zimmermann의 1994년 원조 Pretty Good Privacy(PGP) 는 알려진 모든 16비트 소수로 나누는 체만 사용했고, 그 표는 에라토스테네스의 체로 만들었음. 그 다음 Fermat 테스트를 적용했음

  • 이 작업에 얼마나 걸렸는지 궁금함
    학부 연구 프로젝트로 큰 정수 곱셈을 했는데 거의 두 학기가 걸렸음. Karatsuba, Toom-Cook, 복소 FFT, 몇 가지 NTT, Schonhage-Strassen을 구현했음
    소수는 거의 수학 마법에 가까움. 관심 있는 사람에게 Silverman의 A Friendly Introduction to Number Theory는 훌륭한 수학 책임
    참고로 페이지의 링크가 40250519가 아니라 4025051로 되어 있음

  • 좋은 글임. 나도 최근에 [0]의 초기 버전용으로 직접 큰정수 코드를 조금 작성했는데, 수학 논문의 고수준 설명을 실제 연산으로 옮기는 일이 얼마나 답답한지 기억남
    다만 작은 이의가 있음
    u64의 전체 범위를 사용한다면 숫자는 2^64-1 진법이 아니라 2^64 진법임. 각 워드는 0부터 2^64-1까지 범위를 갖고, 10진수의 각 자릿수가 0부터 9까지인 것과 같음
    [0] https://github.com/LegionMammal978/bigfoot-sim

  • 마지막 최적화처럼 실패했을 때 새 난수를 생성하지 않고 숫자를 2씩 늘리면 보안이 약간 깨짐
    소수는 균등하게 분포하지 않기 때문에, 큰 소수 간격 바로 뒤에 있는 소수 쪽으로 편향됨

    • 조사하면서 그 내용을 읽었음
      실행 속도와 소수의 무작위성 사이의 절충이고, 16개 스레드가 각각 난수에서 시작해 소수를 찾도록 경쟁하면 충분한 무작위성이 추가된다고 보고 속도를 택했음
      속도보다 무작위성을 더 원한다면 +=2를 rng() 호출로 바꾸는 건 쉬운 변경임

  • 좋은 글이고 잘 썼음
    글쓴이는 base-255가 아니라 base-256을 뜻한 것 같음

  • 몇 개의 1~2KB 숫자는 L1 캐시에 충분히 들어가고, 설령 그렇지 않더라도 접근 시간이 약 3ns인 L2 캐시가 메가바이트 이상 있음
    글에서 L1 캐시 미스 때문에 RAM 읽기/쓰기를 기다렸을 것 같다고 했지만, 이후에 이 부분으로 돌아오지는 않음
    또 이건 소수 생성만 다루므로 RSA의 함정을 대부분 피하고, urandom은 안전해야 함. 코드가 제대로 동작한다면 크게 잘못될 부분은 많지 않음
    RSA에는 피해야 할 약한 소수 관련 이슈가 몇 가지 있지만, 여기서 실제로 문제가 될 만큼 흔한지는 모르겠음

  • 몇십 년 전 대학 1학년 프로젝트가 떠오름
    프로젝트 파트너이자 친구였고 나중에 졸업생 대표가 된 사람이 아이디어를 냈고 핵심 수학을 구현해서, 4096비트 RSA 암호화를 만드는 일이었음
    최종 구현에서 소수 생성이 얼마나 느렸는지 기억남. PA-RISC 워크스테이션에서 생성에 약 20분이 걸렸음
    수학 덕후였던 친구는 프로젝트가 끝난 뒤에도 계속 코드를 최적화했고, 소수 판정과 큰정수 수학 구현 논문을 읽던 모습이 기억남
    예를 들어 구성 곱셈에서 어떤 수가 0이면 곱셈을 건너뛰고 결과를 0으로 주도록 하자 엄청난 개선이 있었음

    • 느린 하드웨어에서는 타원곡선 키를 생성하는 편이 훨씬 나음
      아니면 오래 기다리거나, 미래까지 버틸 보안을 희생하게 됨

  • 낮은 비트를 1로 설정하는 건 이해됨. 짝수는 절대 소수가 아니기 때문임. 물론 2는 예외임
    그런데 왜 높은 비트도 1로 설정하는지 모르겠음. 소수나 암호를 잘 아는 건 아니지만, 불필요하게 엔트로피 1비트를 포기하는 것처럼 보임. 뭘 놓치고 있는 걸까?

    • 높은 비트가 항상 설정되어 있고 그 비트까지 포함해 소수를 인코딩하면, 소수는 항상 같은 바이트 수로 인코딩됨
      가변 길이 바이트 인코딩은 명세가 아주 명확하고 테스트가 잘 되어 있지 않으면 서로 다른 소프트웨어 간 데이터 교환에서 문제를 일으킬 수 있음
      서버 공개키에 선행 0이 있을 때 RSA 기반 DHE에서 생기는 문제를 보면 됨
    • 두 자리 숫자를 생성하는 것과 같음
      첫 자리가 0이면 두 자리 숫자가 아님
    • 첫 비트를 1로 설정하면 엔트로피 1비트를 잃지만, 소수가 충분히 크다는 점을 보장함
      하나 더 덧붙이면 RSA에서는 두 소수를 곱함. 하나가 1024비트라면 다른 하나는 기억이 맞다면 약 200비트여도 키에 필요한 엔트로피 비트 수에 도달할 수 있음
      그래서 두 소수를 모두 1024비트로 두면 약간의 여유도 생김
    • 엔트로피 1비트를 포기하는 건 맞지만 그래도 1022비트가 남음
      누가 1024비트 소수를 요구했는데 1020비트 소수도 괜찮은지 고민하는 것보다는 이쪽이 더 안전할 듯함. 보통 00042를 5자리 숫자로 보지 않는 것과 같음
      기술적으로는 정확히 어디에 쓰느냐에 따라 최적 선택이 달라질 수 있겠지만, 글의 방식이 더 안전한 기본값으로 보임
    • 확실히 50비트짜리에 그치지 않는 소수를 만들기 위해 엔트로피 1비트를 잃는 건 충분히 괜찮은 절충으로 보임
답변달기