RSA는 큰 정수의 거듭제곱과 모듈러 연산을 바탕으로 평문을 암호화한다. 키를 만드는 데는 소수 판정과 확장 유클리드 알고리즘이 필요하고, 안전하게 사용하려면 OAEP 같은 인코딩도 필요하다.
1. 정수론의 기본 연산
1.1 Modular Exponentiation
RSA 암복호화에는 를 효율적으로 계산해야 한다. 번의 순차 곱셈은 비효율적이며, 지수의 이진 전개를 이용하면 개의 제곱과 곱셈으로 계산할 수 있다. 기본 예시:
1.2 Left-to-Right 방식
지수 의 최상위 비트에서 최하위 비트로 이동한다.
R = 1
for bit in binary(a), from MSB to LSB:
R = (R * R) mod p
if bit == 1:
R = (R * g) mod p
return R
현재 누적한 부분 지수를 두 배로 만들기 위해 제곱하고, 다음 비트가 1이면 밑 g를 곱한다.
1.3 Right-to-Left 방식
최하위 비트에서 최상위 비트로 이동한다.
R = 1
T = g mod p
while a > 0:
if a mod 2 == 1:
R = (R * T) mod p
T = (T * T) mod p
a = floor(a / 2)
return R
현재 밑의 제곱이 T에 저장된다. 두 알고리즘 모두 지수의 비트 수에 비례하는 곱셈을 수행한다. 두 방식은 MSB부터 누적 제곱하는 방식과 LSB부터 밑을 제곱하는 방식으로 나뉜다.
2. Euclidean과 Extended Euclidean Algorithm
2.1 최대공약수
나머지가 0이 될 때까지 반복한다.
r0 = a
r1 = b
while r1 != 0:
r0, r1 = r1, r0 mod r1
return r0
2.2 Bézout Identity
정수 a,b와 에 대해
가 되는 정수 s,t가 존재한다. 정수 r에 대해 의 해가 존재할 필요충분조건은 이다. 확장 유클리드 알고리즘은 나머지와 함께 이 계수들을 갱신한다.
(old_r,r) = (a,b)
(old_s,s) = (1,0)
(old_t,t) = (0,1)
while r != 0:
q = old_r // r
(old_r,r) = (r,old_r-q*r)
(old_s,s) = (s,old_s-q*s)
(old_t,t) = (t,old_t-q*t)
return old_r,old_s,old_t
을 얻었다면
RSA는 공개 지수 e의 에 대한 역원 d를 계산해야 하므로 확장 유클리드 알고리즘이 핵심이다.
3. Euler Phi Function
가 소수라면 이고, 서로 다른 소수 p,q에 대해
예시:
4. Fermat’s Little Theorem과 Euler’s Theorem
4.1 Fermat
p가 소수일 때 모든 정수 a에 대해
이면
예시: , .
4.2 Euler
이면
예시: , , 이므로
5. Chinese Remainder Theorem(CRT)
5.1 정리
서로소인 p,q에 대해
는 에서 정확히 하나의 해를 가진다.
유일성 증명: 두 해 x,y가 두 법에 대해 일치하면 와 . p,q가 서로소이므로 다.
5.2 계산 예제
, , 이므로
검산: , .
6. 소수 판정
6.1 Fermat Primality Test
가 소수라면 임의의 에 대해 이므로, 랜덤으로 선택한 여러 에서
가 한 번이라도 나오면 후보 p는 합성수다.
repeat lambda times:
choose random a in {2,...,p-2}
if pow(a,p-1,p) != 1:
return composite
return probably_prime
확률적 소수 판정을 통과했다고 해서 소수임이 확정되는 것은 아니다. 통과한 수는 probable prime으로 해석한다.
6.2 Carmichael Number 반례
합성수 인데도 모든 인 a에 대해
를 만족하면 Carmichael Number라고 한다. 사례:
은 합성수지만 Fermat 판정의 여러 밑에서 소수로 오판될 수 있다.
6.3 Miller-Rabin의 아이디어
홀수 후보 n에 대해
로 분해한다. 무작위 밑 를 고르고
을 계산한다. 또는 이면 이번 라운드를 통과한다. 그렇지 않으면 회까지 제곱하면서 이 등장하는지 확인한다.
for iteration in 1..lambda:
choose random a in [2,n-2]
x = pow(a,s,n)
if x == 1 or x == n-1:
continue
passed = false
for j in 1..r-1:
x = x*x mod n
if x == n-1:
passed = true
break
if x == 1:
return composite
if not passed:
return composite
return probably_prime
합성수를 소수로 판단할 확률은 반복 횟수와 랜덤 밑의 선택으로 줄일 수 있다.
561 예시: 이고, 밑 a=5일 때
처음에 1도 아니고, 이후 제곱에서도 -1(=560)이 등장하지 않아 합성수로 판정된다.
7. RSA 암호
7.1 역사와 기반 문제
Rivest, Shamir, Adleman이 1978년 발표한 공개키 암호. 소인수분해의 어려움과 관련된 구조로 설계된다. 단, RSA의 모든 안전성 정의가 단순히 소인수분해의 어려움과 동치로 증명되는 것은 아니다.
7.2 Key Generation
-
큰 서로 다른 소수 p,q 선택
-
계산
-
계산
-
인 공개 지수 e 선택
-
인 d 계산
-
공개키 와 비밀키 생성
실제 구현에는 CRT를 위한 p,q 등을 비밀키 자료에 함께 보관하기도 한다.
7.3 Enc, Dec
7.4 Correctness
이므로, 페르마의 소정리를 p와 q에 각각 적용한 뒤 CRT로 결합하면 다음 합동식이 성립한다.
따라서 올바른 RSA 키쌍으로 복호화하면 원문 M을 얻는다. 여기에는 메시지가 반드시 에 있어야 한다는 제약을 일반적으로 요구하지 않는다. p,q 각각에 대한 Fermat 정리와 CRT로 전체 에 대해 정합성을 보여줄 수 있다.
7.5 Toy RSA 전체 계산
평문 일 때
복호화:
을 이용해 을 계산할 수도 있다.
8. RSA의 속도 향상
8.1 빠른 공개 지수 e
이진수에서 1의 개수가 적은 작은 e를 쓰면 modular exponentiation의 곱셈 수가 감소한다. 예를 들어
인 경우 덧셈사슬로 거듭제곱을 계산하면 제곱을 포함해 각각 2, 5, 17회의 모듈러 곱셈이 필요하다. 낮은 공개 지수 자체만으로 안전성을 판단할 수는 없지만, 잘못된 패딩과 결합하면 공격에 취약해질 수 있다.
8.2 비밀 지수 d를 너무 작게 두지 않기
작은 비밀 지수 d는 공격의 대상이 될 수 있다. Boneh–Durfee 공격의 대표적인 경계는 다. 따라서 e의 계산 편의성을 d를 임의로 짧게 만드는 식으로 얻으면 안 된다.
8.3 CRT 기반 복호화
이후 CRT로 를 결합한다.
같은 예제: .
, 이므로
이 계산에서 inverse의 법을 바꾸어 쓰지 않도록 유의한다.
9. RSA의 안전성과 textbook RSA의 문제점
9.1 소인수분해
공개키의 모듈러스 에서 p,q를 구하기 어렵다는 점이 비밀키 d 복원 난이도와 연결된다. 역사적 factoring challenge 결과에는 RSA-100(1991), RSA-576(2003), RSA-640(2005), RSA-768(2009), RSA-704(2012)가 포함된다. 이는 역사적 기록이고 최신 최대 기록은 아니다. 고전적 공격에 대한 보안강도와 모듈러스 길이 비교: 80비트 강도에 1024, 112비트에 2048, 128비트에 3072, 192비트에 7680, 256비트에 15360비트.
9.2 결정성
textbook RSA는 동일 평문과 공개키에서 동일 암호문이 나온다. 공격자가 pk를 알고 직접 암호화를 할 수 있으므로 IND-CPA에 안전하지 않다.
9.3 곱셈 준동형성
이는 암호문을 곱해 평문 곱의 암호문을 구성할 수 있다는 뜻이므로, 변형 불가능성 및 선택 암호문 공격에 대한 안전성에도 문제가 생긴다. 무패딩 textbook RSA는 사용하지 않는다.
10. OAEP(Optimal Asymmetric Encryption Padding)
OAEP는 RSA의 메시지 인코딩에 **난수 Seed와 Mask Generation Function(MGF)**를 이용하여 단순 결정성 및 구조적 약점을 완화한다. 표준화된 RSA-OAEP의 정확한 보안성은 사용하는 해시, MGF, 구현 조건에 의존한다.
10.1 인코딩 단계
를 모듈러스 길이(바이트), 을 해시 출력 길이라 두고,
-
메시지 길이에 맞는 0 바이트 패딩 PS 생성. 길이는
-
연결. L은 선택적 Label
-
바이트 무작위 Seed 생성
-
-
-
-
-
출력
10.2 구조와 목적
Masking을 Seed와 DB 양쪽에 적용해 입력 메시지와 인코딩 결과 간에 복잡한 관계를 만든다. 기존 RSA의 결정성과 단순 곱셈 준동형성을 그대로 노출하지 않도록 하는 패딩이라는 점이 핵심이다.

Comments