RSA 이해하기: 공개키 수학에 대한 간단한 가이드

Source: Dev.to

죄송합니다만, 번역하려는 전체 텍스트를 제공해 주시면 한국어로 번역해 드리겠습니다. 현재는 링크만 제공되어 있어 실제 내용이 없으므로 번역이 불가능합니다. 텍스트를 복사해서 보내 주시면 바로 도와드리겠습니다.

RSA 기본

RSA (Rivest–Shamir–Adleman)는 공개키 암호화 알고리즘입니다. 데이터를 암호화하기 위해 공개키를 사용하고, 해당 개인키로 복호화하여 안전한 전송 및 디지털 서명을 가능하게 합니다.

키 생성

1. 두 개의 큰 소수 p와 q를 선택합니다.

2. n = p × q를 계산합니다.

3. n의 오일러 토션트(φ)를 구합니다:

   [ \phi(n) = (p-1)(q-1) ]

   토션트는 n보다 작고 n과 서로소인 정수의 개수를 나타냅니다.

   예시:

   • (\phi(11) = 10) because the numbers 1‑10 are all relatively prime to 11.
   • (\phi(12) = 4) because only 1, 5, 7, 11 are relatively prime to 12.

4. 1 < e < φ(n)이며 gcd(e, φ(n)) = 1을 만족하는 정수 e(공개 지수)를 선택합니다.

5. e의 모듈러 역원인 개인 지수 d를 구합니다:

   [ d \equiv e^{-1} \pmod{\phi(n)} ]

암호화와 복호화

If the plaintext message is m and the ciphertext is c:

• Encryption:

  c = m^e mod n

• Decryption:

  m = c^d mod n

예시

Let p = 7 and q = 17, so n = 7 × 17 = 119.

[ \phi(n) = (7-1)(17-1) = 96 ]

Choose e = 53 (relatively prime to 96).

• Encrypt the message m = 7 (ASCII for “H”):

  c = 7^53 mod 119 = 28

• Decrypt:

  m = 28^29 mod 119 = 7

The decrypted value matches the original plaintext. (복호화된 값이 원본 평문과 일치합니다.)

RSA가 안전한 이유

실제에서는 소수 p와 q가 수백 비트 길이이며(예: 2048‑비트 RSA) e와 n만 알고 있어도 n을 p와 q로 소인수분해하지 않으면 φ(n)을 알 수 없습니다. 충분히 큰 키에 대해서는 이는 계산적으로 실현 불가능합니다.

“2048‑비트 RSA” 키는 n이 2048‑비트 정수(최대값 ≈ (2^{2048} - 1))임을 의미하며, 현재 기술로는 소인수분해가 사실상 불가능합니다.

구현

간단한 Java 구현이 실험용으로 제공됩니다. 아래는 최소 예제이며 (전체 소스와 README는 원본 저장소에 제공됩니다).

// RSAExample.java
import java.math.BigInteger;
import java.security.SecureRandom;

public class RSAExample {
    public static void main(String[] args) {
        // Generate two large prime numbers
        SecureRandom rnd = new SecureRandom();
        BigInteger p = BigInteger.probablePrime(1024, rnd);
        BigInteger q = BigInteger.probablePrime(1024, rnd);

        BigInteger n = p.multiply(q);
        BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));

        // Choose public exponent e
        BigInteger e = BigInteger.valueOf(65537); // common choice
        while (!phi.gcd(e).equals(BigInteger.ONE)) {
            e = e.add(BigInteger.TWO);
        }

        // Compute private exponent d
        BigInteger d = e.modInverse(phi);

        // Example message
        BigInteger m = new BigInteger("123456789");
        BigInteger c = m.modPow(e, n); // encryption
        BigInteger decrypted = c.modPow(d, n); // decryption

        System.out.println("Original: " + m);
        System.out.println("Encrypted: " + c);
        System.out.println("Decrypted: " + decrypted);
    }
}

공통 위험 및 완화 방안

이러한 최선의 실천 방안을 따름으로써—큰 소수를 선택하고, 적절한 패딩을 사용하며, 충분한 키 길이를 적용하면—RSA는 안전한 통신을 위한 견고한 기반으로 남습니다.