엔트로피 비트와 추측 가능성, 후보 수를 로그로 바꾸기

가능한 비밀값 N개가 모두 같은 확률로 선택된다면 Shannon 엔트로피는 H=log₂N 비트입니다. 따라서 1,024개 후보를 균등하게 고르는 경우 H=10비트입니다.

실제 선택이 편향되어 있으면 후보 개수만으로 엔트로피를 정할 수 없습니다. NIST SP 800-90B에서 다루는 min-entropy는 최빈 결과의 확률을 기준으로 하므로, 균등 후보 수의 Shannon 엔트로피와 다른 양입니다.

균등한 후보 공간에서 비트 수를 계산합니다

엔트로피는 불확실성을 수치로 나타내는 방법 가운데 하나입니다. 가능한 결과가 N개이고 각 결과가 같은 확률 1/N로 나온다면 Shannon 엔트로피는 H=−Σpᵢlog₂pᵢ=−N×(1/N)×log₂(1/N)=log₂N입니다. 로그 밑이 2이므로 후보가 두 배가 될 때 필요한 비트 수는 1비트씩 증가합니다. 이 식은 선택이 균등하다는 조건을 포함합니다. 후보 목록만 세고 실제로 어떤 값이 더 자주 선택되는지 무시하면 값을 과대평가할 수 있습니다.

따라서 질문의 1,024개 후보가 정말 균등하게 선택된다는 조건이라면 H=10비트입니다. ‘10비트이므로 어떤 공격에서도 정확히 2¹⁰번이면 풀린다’고 말해서는 안 됩니다. 순차 추측의 평균 시도 횟수는 후보의 순서와 확률에 달리고, 공격자가 흔한 값을 먼저 시도할 수 있다면 균등 모형과 달라집니다. 엔트로피는 정의된 확률 분포의 속성이며, 특정 시스템의 실제 공격 성공 시간을 직접 측정한 값이 아닙니다.

후보 수가 같아도 선택 확률이 치우칠 수 있습니다

후보가 네 개라도 선택 확률이 70%, 10%, 10%, 10%라면 균등 분포의 2비트와 같지 않습니다. Shannon 엔트로피는 −Σpᵢlog₂pᵢ로 약 1.36비트입니다. 가장 가능성이 큰 결과의 확률은 70%이므로 min-entropy는 −log₂(0.7)≈0.515비트입니다. 둘은 서로 다른 질문에 답합니다. Shannon 엔트로피는 평균적인 불확실성을 나타내고, min-entropy는 가장 유력한 결과가 얼마나 쉽게 맞을 수 있는지 보수적으로 봅니다.

난수 생성 표준에서 읽을 수 있는 범위

NIST SP 800-90B는 난수 비트 생성에 쓰이는 엔트로피 원천의 설계 원칙, 요구사항, 검증 시험을 다룹니다. SP 800-90A Rev. 1은 해시 함수나 블록 암호를 기반으로 결정론적 난수 비트를 만드는 메커니즘을 설명합니다. 따라서 엔트로피 원천이 초기 입력에 기여하는 문제와, 그 입력을 받아 결정론적으로 출력하는 생성기 문제는 구분해야 합니다. 두 문서의 주제는 난수 생성이며, 사람의 비밀번호 선택 분포를 측정하는 기준으로 바로 대체할 수 없습니다.

1. 먼저 결과 후보를 정의하고 가능한 값의 수 N을 셉니다.
2. 모든 값이 같은 확률인지, 실제 선택이 편향됐는지 확인합니다.
3. 균등 분포라면 log₂N을 계산하고, 편향이 있으면 확률 분포를 사용합니다.
4. 답에서 Shannon 엔트로피, min-entropy, 평균 추측 횟수 중 무엇을 말하는지 이름을 붙입니다.

흔한 실수는 ‘문자 집합이 64개이니 12글자 비밀번호는 항상 72비트’라고 계산하는 것입니다. 이는 각 문자가 독립적으로 64개 값에서 균등하게 선택된다는 강한 가정을 둡니다. 사람이 반복어·이름·키보드 패턴을 고르면 후보 확률은 균등하지 않을 수 있습니다. 반대로 길이만 보고 엔트로피가 낮다고 단정할 수도 없습니다. 실제 강도 평가는 생성 방식, 사용자의 선택 경향, 공격자가 사용하는 추측 순서와 저장 검증 방식을 함께 확인해야 합니다.

조건을 붙여 계산합니다

교육용 회상 문제입니다. 추첨 상자에 서로 다른 번호표가 1,024개 있고 한 장을 모두 같은 확률로 뽑습니다. Shannon 엔트로피는 몇 비트인가요? 번호표가 똑같이 1,024개 있어도 한 번호표가 70% 확률로 뽑힌다면 같은 답을 쓸 수 있을까요?

첫 조건에서는 log₂(1,024)=10비트입니다. 두 번째 조건에서는 균등 분포가 아니므로 후보 수만으로 10비트라고 답할 수 없습니다. 확률 전체가 주어져야 Shannon 엔트로피를 구하고, 최빈 확률이 주어지면 min-entropy도 계산할 수 있습니다. 이 예시는 개념 설명을 위해 새로 구성했습니다.