필요한 수학
왜 중요한가 목록을 주고받지 않고 공유 고객을 찾거나, 각 사람을 지키는 통계를 발표하는 것 같은 이 모듈의 프라이버시 도구는 작은 수학 조각 셋에 기대요. 수학 학위는 필요 없어요. 시계 산수, 확률에 대한 감, 그리고 무작위 잡음이 큰 무리에서 상쇄된다는 생각이 필요해요. 이 레슨은 바로 그것들을, 해 볼 Python과 함께 줘요.
1. 시계 산수
22:00이에요. 5시간 뒤는 몇 시일까요? 27:00이 아니에요: 시계가 한 바퀴 돌아서 03:00이에요. 22 + 5 = 27을 하고 24로 나눈 나머지를 남겼어요.
모듈러 산술: 숫자가 정해진 크기, 모듈러스에 닿으면 한 바퀴 도는 산술. "27 mod 24"는 3, 27을 24로 나눈 나머지예요. Python에서 나머지 연산자는 %예요: 27 % 24는 3이에요.
한 바퀴 돌기는 아무리 더하거나 곱해도 숫자를 정해진 크기로 유지해서, 암호학에 쓸모 있어요. Python에는 "거듭제곱하고, 그다음 한 바퀴 돌기"를 위한 빠른 내장 함수도 있어요: pow(base, exponent, modulus).
print((22 + 5) % 24) # 3
print(pow(3, 4, 7)) # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23)) # instant, even though 5 to the 200 is huge
2. 한쪽으로는 쉽고, 반대로는 어렵게
노란색과 파란색 물감을 섞어 초록색을 만드는 건 쉬워요. 초록색을 정확한 노란색과 파란색으로 되돌리는 건 사실상 불가능해요. 어떤 수학도 같은 방식으로 작동해요.
큰 소수 모듈러스 P와 숫자 h를 고르세요. 비밀 a에 대해 pow(h, a, P)를 계산하는 건 순식간이에요. 하지만 답만 주어졌을 때 a를 다시 찾는 건 숫자가 충분히 크면 너무 느려서 아무도 할 수 없어요. 이 한 방향 성질을 이산 로그 문제라고 해요.
사실 하나 더, 그리고 그게 다음 실습을 움직여요. a로 거듭제곱하고 그다음 b로 하면 b로 하고 그다음 a로 한 것과 같은 결과가 나와요. 둘 다 h의 a 곱하기 b 제곱과 같으니까요:
P = 1019 # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P)) # True
상자 하나에 자물쇠 둘처럼, 다는 순서는 상관없어요. 두 사람이 각자 비밀을 더하고 비밀을 드러내지 않은 채 같은 곳에 닿을 수 있어요.
3. 한 문단으로 보는 확률
확률은 0(절대 아님)에서 1(언제나)까지의 숫자예요. 공정한 동전은 0.5의 확률로 앞면이 나와요. 두 일이 독립이면 둘 다의 확률은 곱이에요: 연달아 앞면 두 번은 0.5 × 0.5 = 0.25. 기댓값은 장기적인 평균이에요: 공정한 주사위를 여러 번 굴리면 평균이 3.5에 다가가요.
4. 잡음은 무리 속에서 상쇄돼요
잡음: 정확한 값을 숨기려고 참값에 일부러 더한 무작위한 양. 잡음이 위로든 아래로든 똑같이 일어나면, 많은 값에 걸쳐 평균이 0이 돼요.
여기 무작위 응답이라는 고전적인 설문 요령이 있어요. 몇 명이 부끄러운 무언가를 했는지 알고 싶어요. 각자 몰래 동전을 던져요. 앞면: 사실대로 답해요. 뒷면: 다시 던져서 앞면이면 "예", 뒷면이면 "아니요"라고 답해요. 어떤 "예" 하나도 그냥 동전일 수 있으니, 누구의 답도 그 사람에 대해 아무것도 증명하지 않아요.
그래도 무리의 합계는 여전히 쓸모 있어요. 참 비율이 p라면 기대하는 "예" 답의 비율은 0.5 x p + 0.25예요. 그래서 35%가 예라고 하면 p는 약 (0.35 - 0.25) / 0.5 = 0.2, 즉 20%예요. 무리가 클수록 추정이 가까워져요. 무리가 커질수록 무작위 잡음이 합계에 비해 줄어드니까요.
import random
rng = random.Random(1) # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)] # 20% really did it
answers = []
for did_it in truth:
if rng.random() < 0.5:
answers.append(did_it) # heads: tell the truth
else:
answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3)) # close to 0.2
차분 프라이버시에 쓰는 잡음은 라플라스 잡음이라고 하는데, 같은 생각의 매끄러운 버전이에요: 보통 작고, 가끔 더 크고, 위아래로 똑같이 일어나요. 그 척도가 보통 얼마나 큰지 정해요.
다른 언어로
JavaScript의 %는 양수에 대해 같은 방식으로 작동하고, 큰 숫자는 BigInt(n을 붙여 써요)를 써요. 내장 모듈러 거듭제곱이 없으니, 표준 루프는 이래요:
function powMod(base, exp, mod) {
let result = 1n;
base %= mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
console.log(powMod(3n, 4n, 7n)); // 4nGo에서는 math/big의 new(big.Int).Exp(base, exp, mod)가 같은 일을 해요.
흔한 오해
"잡음을 더하면 데이터가 쓸모없어진다." 한 사람의 값에 대해서는 그래요. 그게 요점이에요. 큰 무리에 대해서는 잡음이 대체로 상쇄되니, 합계와 평균은 쓸모 있게 남아요. 프라이버시 기술은 그 틈에 살아요: 개인에게는 흐릿하게, 무리에게는 선명하게.
요약
- 모듈러 산술은 숫자를 모듈러스 둘레로 돌려요. Python은
%와pow(b, e, m)을 써요. - 비밀 제곱으로 거듭제곱하는 건 한쪽으로는 쉽고 되돌리기는 사실상 불가능하며, 두 비밀 제곱의 순서는 상관없어요.
- 독립적인 확률은 곱해지고, 기댓값은 장기적인 평균이에요.
- 무작위 잡음은 개인을 숨기지만 큰 무리에서는 상쇄되고, 그게 무작위 응답이 작동하는 방식이에요.
이 연습은 곧 열려요
앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.
이 브라우저가 learn.floati.life의 쿠키를 막고 있어서, 여기서 마친 레슨들이 순서대로 열리지 않아요. 이 사이트의 쿠키를 허용하고 새로고침하세요.