개인키 알고리즘(feat. RSA)

이전 https://code-boki.tistory.com/136

대칭키 / 비대칭키(공개키) 암호화

이전 글에서의 공개키 암호화에 대해 생각해보자

 

공개키 암호화에서 중요한건 탈취되어도 상관 없는 공개키가 아닌 개인키이다

어차피 공개키를 통해 누구나 메시지를 암호화할 순 있어도, 해당 메시지를 복호화 할 수 있는건 오직 개인키를 가진 사람뿐이기 때문이다

그럼 어떻게 공개키와 개인키가 안전하게 보호될 수 있는걸까?

https://man.openbsd.org/ssh-keygen.1#t

ssh-keygen 여기 위의 링크에 보면 사용가능한 키 알고리즘 종류를 볼 수 있다

 

키 알고리즘

1. DSA (Digital Signature Algorithm)
   - DSA는 디지털 서명을 위해 설계된 알고리즘
   - 하지만 현대 암호학에서는 더 안전한 대안들이 존재하기 때문에 이제는 잘 사용되지 않음
2. ECDSA (Elliptic Curve Digital Signature Algorithm)
   - ECDSA는 타원 곡선 암호학을 기반으로 한 디지털 서명 알고리즘
   - RSA보다 적은 양의 데이터와 연산으로 같은 수준의 보안을 제공
3. ECDSA-SK (ECDSA with Security Key)
   - ECDSA의 변형으로, 물리적 보안 키(예: 하드웨어 토큰)를 사용하여 키 생성 및 인증을 수행한다
4. Ed25519
   Edwards-curve Digital Signature Algorithm을 기반으로 하며, 속도와 보안 측면에서 뛰어난 성능을 제공
   특히 소프트웨어 구현에 최적화되어있음
5. Ed25519-SK (Ed25519 with Security Key) 
   Ed25519-SK는 Ed25519 알고리즘을 확장하여 물리적 보안 키를 사용
6. RSA(Rivest Shamir Adleman)
   이것은 가장 널리 알려진 공개키 암호화 알고리즘 중 하나
   RSA는 큰 소수를 사용하여 안전성을 보장한다
   • ssh-rsa
     RSA의 전통적인 형태이며, SHA-1을 사용하여 서명
     SHA-1의 취약성으로 인해 이 방식은 더 이상 추천되지 않음
   • rsa-sha2-256 / rsa-sha2-512
     이러한 변형들은 각각 SHA-256과 SHA-512 해시 알고리즘을 사용하여 서명하는 보다 안전한 방식

이 중 가장 널리 쓰이는 RSA 키 알고리즘에 대해서 간단하게 알아보자

RSA Key Algorithm

RSA는 두 개의 큰 수를 곲한 값에 기반한다. 공개키는 이 소수들의 곱이고, 개인키는 이 소수들에 대한 정보를 이용해 생성된다

또한 모듈러연산이 쓰이게 된다

 

짧막하게 암호학 또는 정보보안기사를 공부하다가 기본적인 내용에 대해 잠시 말해보면...

암호학에서는 평문을 M(Message), 암호문을 C(Ciphertext)라고 관례적으로 표시한다

또한 암호화 과정을 간단히 표시하면 "C = E(M, K)" 라고 나타낼 수 있는데, 해석하면 "암호문 C는 평문 M을 키 K로 암호화한 결과"라는 뜻이 된다(E는 암호화 함수)

 

이제 이어서 RSA 알고리즘에 대해서 예시를 통해 알아보자

1. 두 개의 소수 선택

p = 3, q = 11

2. 모듈러스 n계산

두 소수를 곱하여 n을 계산한다 n = p * q이므로 n=3*11, 즉 33이고, 이 n이 공개키와 개인키에 모두 사용되는 값이다

3. 오일러의 피함수 계산(φ(n))

φ(n)은 n보다 작은 자연수 중에서 n과 서로소인 수의 개수

φ(n) = (p-1) * (q-1) 공식으로 구할 수 있다

φ(n) = (3-1) * (11-1) = 2 * 10 = 20

4. 공개키 지수 e 선택

1 < e < φ(n) 범위 내에서 φ(n)과 e가 서로소인 e를 찾기

여기에서는 e=3을 찾을 수 있다(3과 20은 이미 서로소)

5. 개인키 지수 d 계산

d는 e에 대한 모듈러스 φ(n)의 역원

(e * d) mod φ(n) = 1 공식으로 구할 수 있다

즉, e * d를 φ(n)로 나누었을 때 나머지가 1인 d를 찾는다

3*d를 20으로 나누었을 때 나머지가 1인 d는 7

(3*7)/20 = 1

 

e: 3, d: 7, n: 33

 

공개키: (e, n) => (3, 33)

개인키: (d, n) => (7, 33)

 

페르마의 소정리에 의해 암/복호화 공식을 구할 수 있다

암호화: C≡M^e(mod n) 

복호화: M≡C^d(mod n)

 

실제로는 매우 큰 수 소수를 이용하며, 큰 정수의 소인수분해가 어렵다는 점을 이용한 알고리즘이다

 

다음 포스팅은 인코딩, 개인키 또는 인증서의 파일 확장자에 대해서 작성할 예정이다

 

 

출처

https://man.openbsd.org/ssh-keygen.1

ssh-keygen(1) - OpenBSD manual pages