Search
Duplicate

chapter2. 비대칭키 암호화 (Asymmetric-Key Encipherment)

작성일시
2022/03/15 11:50
강의 번호
유형
보안
자료
복습
속성
속성 1

비대칭 키 암호화 (Asymmetric-Key Encipherment)

•
개인키와 공개키 두 키를 한 쌍으로 암호키를 구성
◦
개인키 (Private Key) - 개인이 보관
◦
공개키 (Public Key) - 타인에게 공개

비대칭 키를 이용한 응용분야

◦
비밀 메시지
▪
A의 공개키로 암호화한 메시지는 A의 개인키로 풀 수 있다
◦
전자서명
▪
A의 공개키로 풀리면 A의 개인키로 암호화한 것이라는 증거

대칭키 암호화와의 비교

𝜑(n)(n) : 오일러의 파이함수

◦
n보다 작으면서 n과 서로소인 정수의 개수 ← Zn∗Z_n{^*} 에 속하는 원소의 개수
▪
ex) 𝜑(10)=(10) = count({1, 3, 7, 9}) = 4
◦
구하는 방법
▪
𝜑(1)=0(1) = 0
▪
𝜑(p)=p−1(p) = p-1
•
p가 소수일 경우
•
𝜑(13)=12(13) = 12
▪
𝜑(m∗n)=(m*n) = 𝜑(m)∗(m) *𝜑(n)(n)
•
m과 n이 서로소일때
▪
𝜑(n)=(n) = 𝜑(pe)=pe−pe−1(p^e) = p^e - p^{e-1}
•
p가 소수일 때
◦
𝜑(n)(n) 에 관한 오일러 정리
▪
a와 n이 서로소일 경우,
•
aφ(n)=1a^{φ(n)}=1
▪
a < n, k 가 정수이면
•
ak∗φ(n)+1=a(mod(n))a^{k∗φ(n)+1}=a(mod(n))

RSA 암호 시스템

•
Revest, Shamir, Adleman 의 이름을 딴 공개키 알고리즘으로 가장 널리 사용된다.
◦
공개키 = (e, n)
◦
기본키 = d
◦
C=PemodC = P^e mod nn
◦
P=CdmodP = C^d mod nn

키 생성 알고리즘

RSA_Key_Generation { p != q 인 두 개의 큰 소수 p와 q를 선택한다 // p와 q는 각각 512비트 이상 n <- p x q // n은 1024비트(309자리) 이상 𝜑(n) <- (p - 1) x (q - 1) 1 < e < 𝜑(n) 이면서 𝜑(n)과 서로소인 e를 선택한다. d <- e^-1 mod 𝜑(n) // d는 modulo 𝜑(n)으로 e의 역원 (e*d mod 𝜑(n) == 1) Public_Key <- (e, n) // 공개키 Private_Key <- d // 개인키 return Public_Key and Private_Key }
Python
복사
•
e 의 역원인 d를 구하기 위하여 Extended Euclidian 알고리즘을 이용
def extendedEuclidanAlgorithm(n, b) : r1 = n; r2 = b t1 = 0; t2 = 1 while r2 > 0 : q = math.floor(r1 / r2) r = r1 - q * r2 r1 = r2; r2 = r t = t1 - q * t2 t1 = t2; t2 = t if r1 != 1 : raise Exception('역원이 없습니다') return t1
Python
복사

RSA의 정확성 증명

RSA 예(1)

RSA 예(2)

•
암호화와 복호화 과정

RSA에 대한 공격 : 소인수분해 공격

n=p∗qn = p * q → 𝜑(n)=(p−1)(n) = (p-1) x (q−1)(q-1)
→ ee x dd modmod 𝜑(n)=1(n) = 1
•
매우 큰 n으로부터 (1024비트 이상) p와 q를 찾는 것은 infeasible
•
RSA가 안전해지기 위한 권장사항
◦
n은 1024비트 이상 (4096비트까지도 권고)
◦
두 개의 소수 p와 q는 적어도 512비트 이상
◦
p와 q는 너무 가까이 있는 수가 되지 않도록 설정
◦
p-1 과 q-1은 적어도 하나의 큰 소인수를 가져야 한다.
◦
n 값을 공동으로 사용해서는 안된다.
◦
e 값은 216+1(=65537)2^{16} + 1(=65537) 이거나 이 값에 가까운 정수를 사용
▪
e를 먼저 정한 후, 𝜑(n)(n)이 서로소가 되도록 p, q를 선택한다.

타원 곡선 암호 시스템

•
RSA의 문제점
◦
보안을 위해서는 키의 길이가 매우 커야한다. (n은 최소 1024비트 이상)
•
타원 곡선 암호 시스템 (ECC - Elliptic Curve Cryptosystem)
◦
보다 짧은 키의 길이(256비트~)로 동일한 보안 수준을 제공
◦
일반적인 타원 곡선 방정식 : 2개의 변수를 갖는 3차 방정식
실수 상의 타원 곡선
y2=x3+ax+by^2 = x^3 + ax + b
•
모든 근이 실근일 경우, 좌표의 수평선과 곡선이 3지점에서 교차

타원 곡선 상의 덧셈 연산

타원 곡선 상의 두 점 P(x1, y1), Q(x2, y2) 에 대해 R = P + Q 정의
•
P와 Q를 연결하는 직선과 교차하는 곡선 상의 점(-R)에 대해 x축으로 대칭점
•
P와 Q가 동일할 경우에는 P를 지나는 접선을 이용𝝀
→ a의 경우
•
기울기 = 𝝀, R=(x3,y3)R = (x_3, y_3)
◦
𝝀 = (y2−y1)/(x2−x1)(y_2 - y_1) / (x_2 - x_1)
◦
x3=λ2−x1−x2​x^3=λ^2−x^1−x^2​
◦
y3=λ(x1−x3)−y1y^3=λ(x^1−x^3)−y^1
→ b의 경우
•
𝝀 = (3x12+a)/(2y1)3x_1^{2} + a) / (2y_1)
◦
x3,y3x_3, y_3 은 위 식과 동일

GF(p) 상의 타원 곡선

•
Modulo p를 이용한 타원 곡선
◦
x의 값 = 0부터 p-1 범위에 존재
◦
덧셈 연산 = 덧셈의 결과를 mod p
•
역원 구하기 : (x,y)(x, y)의 역원 → (x,−y)(x, -y)
◦
ㄷ단, −y-y는 yy의 덧셈에 대한 역원
ex) p=13일 경우, (4, 2)의 역원 → (4, -2) → (4, 11)
•
y2=(x3+ax+b)y^2 = (x^3 + ax + b) modmod pp 곡선 상의 점 찾기

타원 곡선 E13(1,1)E_{13}(1, 1) 의 예

•
y2=(x3+x+1)y^2 = (x^3 + x+1) modmod 1313 위에 정의된 점들
ex) P = (4, 2), Q = (10, 6) 일 때, P + Q = R 이다. R의 좌표는?
𝝀 = (6−2)∗(10−4)−1(6 -2 ) * (10-4)^{-1} modmod 13 13 (6−16^{-1} modmod 13 13 은 Extended Euclidian 알고리즘 활용)
= 4∗114 * 11 modmod 1313
= 55 modmod 1313
x=(52−4−10)x = (5^2 - 4 - 10) modmod 13=1113 = 11 modmod 1313
y=(5(4−11)−2)y = (5 (4-11)-2) modmod 1313 = 22 modmod 1313
따라서 R = (11, 2) → E13(1,1)E_{13}(1,1)의 곡선 상의 점이다

비트코인에서 사용하는 타원 곡선 : Secp256k1

•
비트코인에서는 전자서명을 위해서 타원곡선을 사용한다 (ECDSA)
•
Secp256k1 타원곡선 : Y2=(x3+7)Y^2 = (x^3 +7) % pp
◦
p는 아주 큰 소수이다
p=2256−232−29−28−27−25−24−21p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^5-2^4-2^1
•
공개키, K = K * G
◦
k: 개인키 (256비트)
◦
G: 타원 곡선 상의 고정된 점 (공개)
공개키로부터 개인키를 유추하기 위해서는 적어도 k번의 덧셈이 필요하다
→ 거의 불가능
마찬가지로 공개키를 만들기 위해서도 G를 k번 더해야하지 않나?
→ Double-and-Add 알고리즘 이용

Double-and-Add 알고리즘

•
left-to-right 로 k의 비트를 조사
•
1 : Double and Add
•
0 : Double