RSA 비대칭 암호

RSA의 기본 원리:

• 암호화: P^E mod N = C
• 복호화: C^D mod N = P

여기서 P는 플레인 텍스트, C는 암호화된 텍스트, N은 두 큰 소수의 곱, E는 공개키, D는 비밀키입니다.

• 왜 N은 큰 소수의 곱이어야 하는가:
  • 보안: RSA의 보안은 소인수분해의 어려움에 기반합니다. 큰 소수의 곱 N=p×q을 소인수분해하는 것은 현재의 컴퓨터 기술로는 매우 어렵습니다. 만약 N이 소수가 아닌 작은 수들의 곱이라면, 소인수분해가 쉽게 가능하여 암호가 쉽게 깨질 수 있습니다.
  • 수학적 성질: RSA는 N이 소수의 곱일 때 특정 수학적 성질을 이용합니다. 이러한 성질은 N이 소수의 곱이 아닌 경우에는 성립하지 않습니다
  • N이 큰 소수의 곱일 때의 특정 수학적 성질:
    • RSA 암호화의 안전성은 N이 큰 소수의 곱 p×q로 이루어져 있을 때 나타나는 수학적 성질에 기반합니다.
    • 이 성질 중 하나는 오일러의 피 함수 ϕ(n)의 계산과 관련이 있습니다.
      n=p×q일 때, ϕ(n)=(p−1)×(q−1)입니다.
      이는 n보다 작은 양의 정수 중 n과 서로소인 수의 개수입니다.
    • 소수의 성질에 의해, 소수 p와 q가 주어졌을 때 ϕ(n)을 쉽게 계산할 수 있습니다. 그러나 n만 알고 p와 q를 모르면, ϕ(n)을 계산하기 매우 어렵습니다.
    • RSA의 핵심은 ϕ(n)을 알아야만 공개키 E와 비밀키 D를 찾을 수 있다는 것입니다. n이 큰 소수의 곱인 경우, 이 ϕ(n)을 계산하려면 p와 q를 알아야 하며, 이는 소인수분해 문제로 귀결됩니다.
    • 따라서, N이 큰 소수의 곱이어야 하는 이유는, 소인수분해가 계산상 매우 어렵기 때문에 RSA 암호화가 안전하다는 것을 의미합니다. 이는 공격자가 N을 소인수분해하여 p와 q를 찾고, 따라서 ϕ(n)을 계산하여 비밀키 D를 찾는 것을 매우 어렵게 만듭니다.

모듈러 지수승의 성질:

• • 성질: a ^ k ⋅ ϕ(n) + 1 ≡ a( mod n )
  • 여기서 n=p×q (두 큰 소수의 곱), a<n, k는 정수입니다.
  • ϕ(n)은 오일러의 피 함수로, ϕ(n)=(p−1)×(q−1)입니다.

암호화과정 

• P를 E로 거듭제곱하고, N으로 나눈 나머지를 구합니다.
• P ^ E mod N 결과는 C입니다.

복호화 과정:

• C를 D로 거듭제곱하고, N으로 나눈 나머지를 구합니다.
• C ^ D mod N 결과는 P입니다.