[IT]RSA알고리즘이란?

반응형

암호(暗號 cipher/password) :

비밀을 유지하기 위하여 당사자끼리만 알 수 있도록 꾸민 약속 기호

💡 IT 보안에서의 암호는 정보를 이해할 수 없도록 암호화 하거나 다시 해독하기 위한 일련의 단계를 정의한 알고리즘을 암호 라고 합니다.

용어

암호화를 설명하기 앞서서 자주 사용될 용어에 대해 짚고 넘어가겠습니다.

• 평문(Plaintext) : 암호기술을 통해 보호하고자 하는 원본 데이터
• 암호문(ciphertext) : 평문에 암호기술을 적용한 것
• 암호화 : 평문에 암호 기술을 적용하여 변환하는 과정으로 암호 키 (key) 를 생성
• 복호화 : 암호 기술이 적용된 평문을 다시 복원하는 과정

기대효과

암호 기술을 이용하여 데이터 기밀성, 데이터 무결성, 인증 및 부인 방지 등의 기능을 제공 할 수 있습니다.

• 기밀성 : 허락되지 않은 사용자 또는 객체가 정보의 내용을 알 수 없도록 하는 성질
• 무결성 : 허락되지 않은 사용자 또는 객체가 정보를 함부로 수정할 수 없도록 하는 성질
• 인증 : 사용자 또는 개체의 디지털 정체성을 식별
• 부인방지 : 정보를 보낸 사람이 나중에 정보를 보냈다는 것을 부인하지 못 하도록 하는 것

종류

암호의 종류는 크게 세가지로 나눌 수 있습니다.

1. 대칭형 암호화 (비밀 키 암호)

• 암. 복호화에 같은 암호 키를 사용하는 알고리즘이며, 송신자와 수신자는 암호 키가 노출되지 않도록 비밀로 관리해야하며 블록 암호와 스트림 암호로 나눌 수 있습니다.

1. 비대칭형 암호화 (공개 키 암호)

• 대칭 키 암호화와 달리 암.복호화에 서로 다른 키를 사용하는 알고리즘입니다. 송신자는 수신자의 공개키를 이용하여 암호화하며, 수신자는 자신의 공개키로 암호화된 암호문을 자신의 개인키로 복호화 할 수 있습니다.
• 대표적인 알고리즘으로는 RSA, DSA, ELGamal, ECC 등이 있습니다.

1. 단방향 암호화

• 해시 함수라고도 불리며 임의의 길이의 메시지를 입력으로 받아 고정된 길이의 해시 값을 출력하는 함수 입니다. 해시 함수에는 암호 키가 사용되지 않기 때문에, 같은 입력에 대해서 항상 같은 해시 값을 얻을 수 있습니다.
• 대표적인 해시 함수로는 MD5, HAS-160, SHA-1,SHA-2,SHA-3 등이 있습니다.

위의 암호 종류 중 대중적으로 사용되는 비대칭형 암호화 그 중에서도 RSA가 무엇인지 살펴보도록 하겠습니다.

RSA(Rivest-Shamir-Adleman) 암호

: 암호화 뿐만 아니라 전자서명이 가능한 최초의 알고리즘 RSA 암호체계의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있어 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견된다면 이 암호 체계는 가치가 떨어질 것으로 보고 있습니다.

방식

RSA는 공개키(public key)와 개인키(private key) 를 사용합니다. **키 : 평문을 열고 잠구는 상수(Constant)

공개키 알고리즘은 누구나 어떤 메시지를 암호화 할 수 있지만, 그것을 해독하여 열람할 수 있는 사람은 개인키를 지닌 단 한 사람만이 존재한다는 점에서 대칭 키 알고리즘과 차이를 가집니다.

위의 이미지처럼 메시지와 공개키 모두를 알 수 있다면 변조된 메시지를 보낼 수 있기 때문에, 실제로 사용시에는 수신측의 공개키만을 사용하여 암호화하는 경우는 드뭅니다.

일반적으로 RSA 암호화를 사용하는 경우는 송/수신 쌍방으로 암호화를 진행하는 방식이 있는 B의 개인(private)키로 암호화하여 A의 공개(public)키로 암호화를 한 데이터를 송신하고

A는 본인의 개인(private)키로 복호화 한 후 A의 공개(public)키로 재 복호화하는 방식입니다.

키 생성

1. 소수 선택: 두 개의 큰 소수(p, q)를 선택합니다. 이 소수는 매우 크고 무작위로 선택되어야 합니다. ** p와q : p와q는 각각 매우 큰 소수입니다. RSA의 보안성은 이 두 소수가 크고 무작위로 선택되어야 한다는 점에서 시작됩니다.
2. 곱셈: p와 q를 곱하여 n을 계산합니다.n=p×q
3. 여기서 n은 모듈러 연산에서의 모듈러 값으로 사용됩니다.
4. 오일러 피 함수 계산: 두 소수(p, q)의 오일러 피 함수 값(φ(n))을 계산합니다. ϕ(n)=(p−1)×(q−1)
5. 공개키 선택: 공개키 e를 선택합니다. 일반적으로 1보다 크고, φ(n)과 서로 소인 값을 선택합니다. 가장 일반적으로 사용되는 값은 65537입니다.
6. 개인키 계산: 공개키 e의 모듈러 역수인 d를 계산합니다. 즉, 다음 조건을 만족하는 d를 찾습니다 :d×e≡1 (mod ϕ(n))
7. 즉, d는 e의 역수로, d=e−1 (mod ϕ(n))을 계산하여 얻습니다.
8. 공개키 및 개인키 생성: 공개키는 (e, n)의 쌍으로, 개인키는 (d, n)의 쌍으로 생성됩니다.

이렇게 생성된 공개키와 개인키는 RSA 알고리즘의 핵심 요소로서, 암호화와 복호화에 사용됩니다.

암호화

• 공개키 사용: 위에 언급한 키 생성 중 공개키 방식으로 메시지를 암호화합니다. 공개키는 (e, n) 형태로 제공됩니다.
• 메시지 변환: 암호화하려는 원본 메시지를 숫자로 변환합니다. 일반적으로 메시지를 블록화하고, 각 블록을 숫자로 변환한 후 암호화 과정을 적용합니다.
• 암호화 계산: 메시지의 숫자 표현에 대해 공개키 e를 사용하여 연산을 수행합니다
  암호문=원본 메시지^e mod n
  여기서 n은 공개키와 개인키 쌍에서 사용되는 모듈러 값입니다.
• 암호문 전송: 계산된 암호문은 수신자에게 안전하게 전송됩니다.

암호화 주요 조건

• 메시지 크기: RSA는 대개 고정된 크기의 블록 단위로 메시지를 처리합니다. 일반적으로 블록 크기는 RSA 모듈러 값 n의 크기와 관련이 있으며, RSA의 보안 강도에 중요한 영향을 미칩니다.
• 블록화: 일반적으로 큰 메시지는 블록으로 나누어 암호화됩니다. 각 블록은 RSA 암호화 알고리즘에 의해 개별적으로 처리됩니다. 이는 RSA가 직접적으로 긴 메시지를 처리하기 어렵기 때문에 필요한 절차입니다.
• 패딩 (Padding): RSA에서는 블록 암호화를 사용하고, 메시지 길이가 블록 크기보다 작을 경우 패딩을 추가하여 블록 크기와 맞춥니다. 패딩은 일반적으로 RSA 블록의 마지막에 추가되며, 암호화 및 복호화 과정에서 메시지의 왜곡을 방지합니다.
• 모듈러 연산: RSA에서 모든 연산은 모듈러 연산으로 처리됩니다. 즉, 큰 소수 n에 대해 m^e mod  nm^e \mod nmemodn과 c^d mod  nc^d \mod n c^d mod n과 같은 형태로 암호화와 복호화가 이루어집니다. 이 모듈러 연산은 RSA 알고리즘의 핵심 부분입니다.
• 공개키 및 개인키의 적절한 사용: RSA에서는 공개키는 암호화에, 개인키는 복호화에 사용됩니다. 공개키는 모든 사용자에게 공개되며, 개인키는 오직 소유자만이 접근할 수 있습니다.

복호화

• 개인키 사용: 수신자는 자신의 RSA 개인키를 사용하여 암호문을 복호화합니다. 개인키는 (d, n) 형태로 제공됩니다.
• 암호문 수신: 수신자는 암호화된 메시지(암호문)를 받습니다.
• 복호화 계산: 개인키 d를 사용하여 암호문에 대해 연산을 수행합니다
  원본 메시지=암호문^d mod n
  이 연산은 암호화 과정의 역 연산으로, 개인키 d는 공개키 e와 관련된 역수로 선정되어 있습니다.

• 원본 메시지 복구: 계산된 결과는 원본 메시지의 숫자 표현입니다. 이를 원하는 형태로 변환하여 사용할 수 있습니다.

복호화 주요 조건

• 비밀 키 d:
  • 비밀 키 d는 공개 키 e와 ϕ(n)을 이용하여 계산된 값으로, 암호문을 복호화하는 데 반드시 필요합니다.
  • d는 모듈러 산술에서 e의 역수입니다.
• 모듈러스 n:
  • 복호화 과정에서도 공개 키와 동일한 n이 사용됩니다.
• 모듈러 연산:
  • RSA 암호화와 복호화는 모두 모듈러 연산에 기반합니다. 이는 큰 수의 연산을 효율적으로 처리하기 위해 필수적입니다.
• 소수 p와 q:
  • 비밀 키 생성 시 사용된 소수 p와 q는 공개되지 않습니다. p와 q를 알면 ϕ(n)을 계산할 수 있고, 이를 통해 d를 구할 수 있기 때문에, 이 소수들은 안전하게 비밀로 유지되어야 합니다.

간단 예제

위에서 설명했듯 p와q는 큰 수들로 이루어져 있기 때문에 작은 수를 통해서 계산하는 예제를 통해 암 복호화의 원리를 설명 드리겠습니다.

키 생성

1. 두 개의 소수 선택:
   • p=3p
   • q=11q
2. 모듈러스 계산:
   • n=p×q=3×11=33
3. 오일러의 피 함수 계산:
   • ϕ(n)=(p − 1)×(q − 1)=(3 − 1)×(11 − 1)= 2 × 10 = 20
4. 공개 키 지수 e 선택:
   • e=3 (3은 1과 20 사이의 숫자이며, 3과 20은 서로 소)
5. 비밀 키 지수 d 계산:
   • d는 e×d≡1 (mod ϕ(n))을 만족하는 값입니다.
   • e×d≡1 (mod ϕ(n))e \times d \equiv 1 \ (\text{mod} \ \phi(n))
   • d=7 (3 * 7 = 21, 21 mod 20 = 1)
6. 공개 키와 비밀 키:
   • 공개 키: (e,n)=(3,33)
   • 비밀 키: (d,n)=(7,33)

메시지 암호화

1. 메시지 M:
   • M=7(암호화할 메시지는 7로 가정합니다)
2. 암호문 계산:
   • C = M^e (mod n)=7³ (mod 33) = 343 (mod 33) = 13
   • 따라서 암호문 C=13

메시지 복호화

1. 암호문 C:
   • C=13
2. 복호화하여 원래 메시지 M 계산:
   • M=C^d (mod n)=137 (mod 33)
   • 13⁷=62748517
   • 62748517 (mod 33)=7
   • 따라서 복호화된 메시지 M=7

정리

• 키 생성:
  • 공개 키 (3,33)와 비밀 키 (7,33)
• 메시지 암호화:
  • M=7을 암호화하여 C=13
• 암호문 복호화:
  • C=13을 복호화하여 M=7

예제까지 함께 RSA 알고리즘에 대해 간단하게 설명드렸습니다.

더 깊고 자세하게 들어가기 위해서는 암호학과 이산수학의 심도 깊은 지식이 필요한데 저도 아직 암호학에 대해 자신있게 설명드리기 난해하여 암호기술의 비대칭형 암호화인 RSA 알고리즘의 맛보기로 보시면 될 것 같습니다.

보안점과 피드백이 있다면 편하게 댓글 남겨주심면 감사하겠습니다.