[JAVA] RSA 알고리즘에 대해 쉽게 알아보고 구현해보기

RSA 알고리즘은 공개키와 비밀키라는 두 개의 키를 사용하여 데이터를 암호화하고 복호화하는 방식입니다.
이 알고리즘의 핵심은 두 개의 소수를 사용하여 공개키와 비밀키를 생성하고 이를 통해 안전하게 정보를 전달하는 것입니다.

• 공개키 : 공개키는 공유되며 암호화에 사용됩니다.
• 비밀키 : 공유되면 안되며 암호화된 데이터를 복호화하는 데 사용됩니다.

RSA 알고리즘

RSA 알고리즘을 구현하기 위한 몇가지 과정은 아래와 같습니다.

1. 2개의 소수 선택 및 N 추출

소수 P와 Q를 선택한 후 N을 계산합니다.
예를 들어 P = 5, Q = 11를 선택한다면 N = P * Q = 55가 됩니다.
 
중요한 점은 P와 Q가 노출되면 공개키와 비밀키를 만들 수 있기 때문에 꼭 제거해야합니다.

2. 오일러 피 함수( φ(N) ) 계산

오일러 피 함수( φ(N))는 N과 서로소인 숫자의 개수를 구하는 함수입니다.

φ(N) = (p - 1) * (q - 1)

위 공식에 대입하면 φ(N) = (5 - 1) * (11 - 1) = 4 * 10 = 40이 됩니다.

3. 공개키 E

공개키 E는 1보다 크며 φ(N)보다 작아야합니다.
그리고 E는 φ(N)과 서로소여야 합니다.

1 < E < φ(N)

여기서 1 ~ φ(N) 중에 φ(N)를 소인수 분해한 결과의 배수를 모두 지운 후 일반적으로 가장 작은 수를 선택하게 됩니다.
해당 예시에서는 3이 됩니다.

4. 비밀키 D

비밀키 D는 ED = (K * φ(N)) + 1에 부합하는 수를 의미합니다.

ED = 1(mod φ(N))

E와 D의 곱을 φ(N)으로 나누었을 때 나머지가 1이 되어야 합니다.
이를 풀어서 만들면 ED = (K * φ(N)) + 1 이렇게 만들 수 있습니다.
여기서 K는 배수를 의미하며 현재 예시의 결과로 보면 3d = 41, 81, 121이 되며 d는 27입니다.

5. 암호화

현재 공개키는 N, E가 되며 예를 들어 2를 암호화 하나면 2^E를 N으로 나눈 나머지 즉 8이 됩니다.

6. 복호화

현재 비밀키는 N,D가 되며 암호화된 8을 복호화 한다면 8^D를 N으로 나눈 나머지 즉 2로 복호화됩니다.

---

Java 직접 RSA 구현

@Slf4j
public class RsaTest {

    @Test
    public void rsa() {
    	// 공개되면 큰일나는 소수 두개
        BigInteger p = BigInteger.valueOf(1000000007);  
        BigInteger q = BigInteger.valueOf(1000000009);
        
        // n = p * q ( 공개 )
        // n이 충분히 커야 한글과 같이 유니코드 값이 큰 문자도 암호화/복호화 가능
        BigInteger n = p.multiply(q);  
        
        // φ(N) 계산: φ(N) = (p-1) * (q-1)
        BigInteger eulerN = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));  

        // 공개키 (public key)
        BigInteger e = chooseE(eulerN);
        // 비밀키 (private key)
        BigInteger d = calculateD(e, eulerN);  

        log.info("Public  Key = ({}, {})", n, e);
        log.info("private Key = ({}, {})", n, d);

        String message = "Hello! RSA!\n안녕 알에스에이\n123456";
        log.info("메시지 : {}", message);

        // 암호화
        StringBuilder encryptedMessage = new StringBuilder();
        for (char c : message.toCharArray()) {
        	// 문자 c를 유니코드 값(BigInteger로 변환)
            BigInteger m = BigInteger.valueOf(c); 
            // 암호화
            BigInteger encryptedChar = encryptionOrDecryption(m, e, n); 
            // 16진수로 변환 후 추가
            encryptedMessage.append(encryptedChar.toString(16)).append(" ");  
        }
        log.info("[Hex] 암호화 된 메시지 : {}", encryptedMessage.toString());

        // 복호화
        String[] encryptedMessageArray = encryptedMessage.toString().split(" ");
        StringBuilder decryptedMessage = new StringBuilder();
        for (String em : encryptedMessageArray) {
        	// 16진수 문자열을 BigInteger로 변환
            BigInteger encryptedChar = new BigInteger(em, 16);
            // 복호화
            BigInteger decryptedChar = encryptionOrDecryption(encryptedChar, d, n);
            // 복호화된 숫자를 문자로 변환하여 메시지에 추가
            decryptedMessage.append((char) decryptedChar.intValue()); 
        }
        log.info("복호화 된 메시지 : {}", decryptedMessage.toString());
    }

    private static BigInteger encryptionOrDecryption(BigInteger m, BigInteger key, BigInteger n) {
        return m.modPow(key, n);
    }

    private static BigInteger calculateD(BigInteger e, BigInteger phiN) {
        return e.modInverse(phiN);
    }
    
    private BigInteger chooseE(BigInteger phiN) {
        BigInteger e = BigInteger.valueOf(2);
        while (e.compareTo(phiN) < 0) {
            if (e.gcd(phiN).equals(BigInteger.ONE)) {
                return e; 
            }
            e = e.add(BigInteger.ONE); 
        }
        return null; 
    }
}

1. 소수 생성

예제에서는 소수를 직접 입력했지만 실제로 소수를 만들때는 BigInteger.probablePrime(bitLength, random) 메서드를 사용하여 생성할 수 있으며 해당 메소드는 내부적으로 밀러-라빈 알고리즘을 통해 소수 검증을 하며 주어진 비트 길이에 맞는 소수를 반환합니다.

// 1024 : 비트 길이
// new SecureRandom() : 난수 생성기
BigInteger test = BigInteger.probablePrime(1024, new SecureRandom());

2. 공개키와 비밀키의 일치 문제

간혹 공개키와 비밀키가 서로 같아지는 문제가 발생하는데 이를 해결하기 위해서 실제 사용시 e와 d가 같다면 p와 q를 다시 생성하도록 만들어줘야 합니다.

---

Java 라이브러리로 RSA 구현

 @Test
    void rsaTest() throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, IllegalBlockSizeException, BadPaddingException {
        KeyPairGenerator keyPairGen = KeyPairGenerator.getInstance("RSA");
        keyPairGen.initialize(2048);

        KeyPair keyPair = keyPairGen.generateKeyPair();
        PublicKey publicKey = keyPair.getPublic();
        PrivateKey privateKey = keyPair.getPrivate();

        String message = "안녕하세요!\nHello!\nThis is RSA";
        System.out.println("origin message = " + message);

        // 암호화
        Cipher encryptCipher = Cipher.getInstance("RSA");
        encryptCipher.init(Cipher.ENCRYPT_MODE, publicKey); // 공개키로 암호화
        byte[] encryptedMessage = encryptCipher.doFinal(message.getBytes(StandardCharsets.UTF_8));
        System.out.println("encrypted message = " + Base64.getEncoder().encodeToString(encryptedMessage));

        // 복호화
        Cipher decryptCipher = Cipher.getInstance("RSA");
        decryptCipher.init(Cipher.DECRYPT_MODE, privateKey); // 비밀키로 복호화
        byte[] decryptedMessage = decryptCipher.doFinal(encryptedMessage);
        String decryptedText = new String(decryptedMessage, StandardCharsets.UTF_8);
        System.out.println("decrypted message = " + decryptedText);

        assertThat(decryptedText).isEqualTo(message);
    }

---

결론

RSA는 매우 큰 수의 연산을 기반으로 하기 때문에 짧은 데이터를 암호화하고 복호화하는 데 적합합니다.
긴 데이터를 처리하려면 효율성이 떨어질 수 있으므로 일반적으로 RSA는 대칭 키 암호화를 위한 키 교환이나 디지털 서명 같은 용도로 사용된다고 합니다.
긴 데이터의 경우 다른 암호화 알고리즘을 사용하는 것이 적합합니다.