RSA Encryption
1. Euler's Phi Function(오일러 피 함수)
- ϕ(m) =
- ϕ(pq) = (p-1)(q-1)
2. Fermat's Little Theorem(페르마의 소정리)
- 페르마의 소정리를 통해 소수를 찾을 수 있음
- p가 소수고, a가 정수일 때 다음이 성립 :
- 만약 gcd(a, p) = 1이라면 :
1) a^p-1 ≡ 1 (mod p) -> 만족하면 소수
2) a^-1 = a^p-2 (mod p)
- 이를 기반으로 한 알고리즘을 통해 어떤 수가 소수인지를 확률적으로 판단 가능(늘 소수가 나오는건 x)
- 번 반복해서 테스트하며, 매번 a∈{2,3,...,pˉ−2} 중 랜덤으로 선택
- 모든 반복에서 조건을 통과하면 pˉ는 소수일 가능성 있음
- Carmichael Number(카마이클 수)는 합성수인데도 불구하고 gcd(a,C) = 1에 대해 a^C-1 ≡ 1 (mod C) 만족
3. Euler Theorem
- a와 m이 서로소일 때 다음이 성립 :
4. Chinese Remainder Theorem
- 서로소인 두 정수 p와 q가 주어졌을 때, 다음 연립 합동식은 항상 mod pq에서 유일한 해를 갖는다 :
- 복호화를 빨리 하기 위해 + 오류를 설명하기 위해 사용
5. Miller-Rabin 소수 판별법
- 어떤 홀수 p에 대해 p-1 = 2^r (s는 홀수)라고 하자.
- 다음 조건을 모두 만족하는 어떤 a가 존재하면, p는 합성수다.
- 알고리즘은 λ번 테스트를 반복하며, 매번 중 무작위로 선택
- 모든 j에 대해 위 조건을 만족하면 합성수 확정
- 여러 개의 a를 무작위로 선택해 모든 시도에서 위 조건을 다 피해가면 소수로 판정
6. RSA: Speed Up
- 암호화는 C = M^e mod N인데, e는 보통 -bit 수준
- 이걸 빠르게 계산하려면 e를 작게 선택하면 됨
- 복호화는 M' = C^d mod N인데, d는 매우 커야 함
- d를 작게 하면 공격에 취약해짐
- Chinese Remainder Theorem 활용 :
7. RSA 보안
- Deterministic encryption → No IND-CPA : 동일한 메세지를 두 번 암호화하면 결과가 같음
- Homomorphic → No IND-CCA2 : RSA는 곱셈 동형성을 가짐
- OAEP : 입력 메세지를 무작위하게 패딩된 EM으로 변환
- 무작위성과 구조적인 변환을 통해 IND-CPA 방지, IND-CCA2에도 안전한 기반 제공