RSA: 개념, 알고리즘 및 암호화 응용

RSA란 무엇인가?

RSA는 1977년 Ron Rivest, Adi Shamir 및 Leonard Adleman이 개발한 공개 키 암호화 알고리즘입니다. 이름은 저자들의 성 첫 글자에서 따왔습니다. 이 알고리즘은 암호화 키와 복호화 키가 다른 최초의 실용적으로 적용 가능한 비대칭 암호 시스템이 되었습니다.

창조의 역사

RSA 알고리즘은 1977년 Scientific American 잡지에 발표되었으며 Whitfield Diffie와 Martin Hellman의 공개 키 암호화에 대한 초기 연구를 기반으로 합니다. 매사추세츠 공과대학은 1983년에 RSA 특허를 취득했으며 2000년까지 유효했습니다. RSA Laboratories 보고서(2023)에 따르면, 이 알고리즘은 세계에서 가장 널리 퍼진 암호화 표준 중 하나로 남아 있으며 매일 수십억 개의 장치에서 사용됩니다.

비대칭성의 원리

암호화와 복호화 모두에 동일한 키를 사용하는 대칭 암호와 달리, RSA는 수학적으로 연결된 키 쌍으로 작동합니다. 공개 키는 시스템 손상 위험 없이 누구에게나 공개될 수 있습니다. 개인 키는 소유자만 알고 네트워크를 통해 전송되지 않습니다. IBM Security X-Force Threat Intelligence Index(2024) 연구에 따르면, 최신 보안 데이터 전송 프로토콜의 96%에서 비대칭 암호화가 사용됩니다.

수학적 기초

RSA의 보안은 인수분해 문제, 즉 두 개의 큰 소수의 곱을 인수로 분해하는 것에 기반합니다. 각각 1024비트의 소수 p와 q를 선택하면 그 곱 n은 2048비트가 됩니다. 현대적인 방법으로 n만 알고 p와 q를 계산하는 것은 사실상 불가능합니다. CNRS 전문가 평가(2024)에 따르면, RSA-2048을 해독하려면 기존 컴퓨터에서 3000억 년 이상의 계산이 필요합니다.

RSA 알고리즘의 작동 방식

키 생성부터 메시지 암호화 및 복호화까지 RSA의 전체 작업 흐름을 살펴보겠습니다. 이러한 단계를 이해하는 것은 모바일 애플리케이션에서 알고리즘을 올바르게 구현하는 데 필요합니다.

키 생성

프로세스는 두 개의 큰 소수 p와 q를 선택하는 것으로 시작됩니다. 키 길이를 결정하는 모듈러스 n = p x q가 계산됩니다. 그런 다음 오일러의 토션트 함수 phi(n) = (p-1)(q-1)이 계산됩니다. phi(n)과 서로소인 공개 지수 e가 선택됩니다. 개인 지수 d는 e 모듈로 phi(n)의 모듈러 곱셈 역원으로 계산됩니다. NIST SP 800-56B Rev. 2에 따르면, 적절한 보호를 보장하려면 n의 최소 길이는 2048비트여야 합니다.

import java.security.KeyPairGenerator;
import java.security.KeyPair;
import java.security.SecureRandom;

public class RSAKeyGenerator {
    public static KeyPair generateKeyPair() throws Exception {
        KeyPairGenerator generator = KeyPairGenerator.getInstance("RSA");
        generator.initialize(2048, new SecureRandom());
        return generator.generateKeyPair();
    }
}

암호화 및 복호화

메시지 m을 암호화하려면 발신자가 이를 n보다 작은 정수로 변환하고 암호문 c = m^e mod n을 계산합니다. 수신자는 개인 키 d를 사용하여 원래 메시지를 복원합니다: m = c^d mod n. RSA는 성능이 낮기 때문에 대량의 데이터를 암호화하기 위한 것이 아닙니다. 최대 메시지 크기는 키 길이에서 오버헤드 바이트를 뺀 것과 같습니다(OAEP를 사용한 RSA-2048의 경우 약 190바이트).

import javax.crypto.Cipher;
import java.security.PublicKey;
import java.util.Base64;

public class RSAEncryptor {
    public static String encrypt(String data, PublicKey publicKey) throws Exception {
        Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        byte[] encrypted = cipher.doFinal(data.getBytes());
        return Base64.getEncoder().encodeToString(encrypted);
    }
}

RSA를 사용한 디지털 서명

RSA는 디지털 서명을 만드는 데에도 사용됩니다. 이는 데이터의 신뢰성과 무결성을 검증하는 메커니즘입니다. 소유자가 개인 키로 메시지 해시에 서명하면 누구나 공개 키를 사용하여 서명을 검증할 수 있습니다. Sectigo Certificate Transparency 보고서(2025)에 따르면, 인터넷 TLS 인증서의 85% 이상이 디지털 서명에 RSA를 사용하여, 이 알고리즘을 웹 통신의 신뢰 기반으로 만듭니다.

import java.security.Signature

fun signData(data: ByteArray, privateKey: java.security.PrivateKey): ByteArray {
    val signature = Signature.getInstance("SHA256withRSA")
    signature.initSign(privateKey)
    signature.update(data)
    return signature.sign()
}

fun verifySignature(
    data: ByteArray, signedData: ByteArray, publicKey: java.security.PublicKey
): Boolean {
    val signature = Signature.getInstance("SHA256withRSA")
    signature.initVerify(publicKey)
    signature.update(data)
    return signature.verify(signedData)
}

키 크기 및 보안 수준

키 길이는 RSA의 암호화 강도에 직접적인 영향을 미칩니다. 컴퓨팅 성능이 증가함에 따라 최소 허용 키 크기는 국제 표준화 기구에 의해 정기적으로 검토됩니다. NIST 및 기타 규제 기관의 현재 권장 사항을 살펴보겠습니다.

성능에 미치는 영향

RSA 키 길이를 늘리면 작업 실행 시간에 상당한 영향을 미칩니다. 4096비트 키를 생성하는 데는 2048비트 키보다 약 10배 더 오래 걸립니다. 더 긴 키를 사용한 암호화 및 복호화 작업에는 더 많은 계산 리소스가 필요하며, 이는 전력 소비가 제한된 모바일 장치에 중요합니다.

양자 위협

양자 컴퓨팅의 발전으로 RSA는 쇼어의 알고리즘을 사용하여 다항식 시간 내에 해독될 수 있습니다. 1994년 Peter Shor가 제안한 이 알고리즘은 O((log n)^3) 연산으로 큰 수를 인수분해할 수 있습니다. IBM Quantum Roadmap(2025)에 따르면, RSA-2048의 실용적 해독은 2035년 이전에는 예상되지 않지만, NIST는 이미 양자 내성 알고리즘 CRYSTALS-Kyber 및 CRYSTALS-Dilithium으로의 점진적 전환을 권장합니다.

모바일 개발에서 RSA의 응용

RSA는 안전한 데이터 전송, 서버 인증 및 디지털 거래 보호를 보장하기 위해 모바일 애플리케이션에서 적극적으로 사용됩니다. 통합은 두 주요 플랫폼의 표준 암호화 API를 통해 수행됩니다.

Android Keystore

Android 플랫폼은 Trusted Execution Environment 하드웨어 수준으로 보호되는 시스템 암호화 키 저장소인 Android Keystore를 제공합니다. KeyStore에서 생성된 RSA 키는 애플리케이션이 손상되더라도 장치에서 추출할 수 없습니다. 이는 루트 액세스 권한이 있는 맬웨어를 포함한 광범위한 공격으로부터 보호를 제공합니다.

import android.security.keystore.KeyGenParameterSpec
import android.security.keystore.KeyProperties
import java.security.KeyPairGenerator

fun generateKeyInAndroidKeystore() {
    val generator = KeyPairGenerator.getInstance(
        KeyProperties.KEY_ALGORITHM_RSA,
        "AndroidKeyStore"
    )
    val spec = KeyGenParameterSpec.Builder(
        "rsa_key_pair",
        KeyProperties.PURPOSE_ENCRYPT or KeyProperties.PURPOSE_DECRYPT
    )
        .setKeySize(2048)
        .setBlockModes(KeyProperties.BLOCK_MODE_ECB)
        .setEncryptionPaddings(KeyProperties.ENCRYPTION_PADDING_RSA_OAEP)
        .build()
    generator.initialize(spec)
    val keyPair = generator.generateKeyPair()
}

iOS Security Framework

iOS에서 RSA는 A7 칩 이상이 탑재된 장치의 Secure Enclave에 액세스하는 Security Framework를 통해 처리됩니다. Secure Enclave는 메인 프로세서와 분리된 전용 코프로세서로, 암호화 작업을 수행하고 키를 하드웨어 볼트에 저장합니다. RSA 키는 Secure Enclave 내부와 소프트웨어 Keychain 모두에서 다양한 액세스 수준으로 생성할 수 있습니다.

실제 하이브리드 암호화

실제 모바일 애플리케이션에서 RSA는 대량 데이터의 직접 암호화에 거의 사용되지 않습니다. 표준 방법은 하이브리드 방식입니다. 애플리케이션이 AES 세션 키를 생성하고, 서버의 RSA 공개 키로 암호화하여 서버로 전송합니다. 이후 모든 트래픽은 AES로 암호화되며, 이는 RSA를 통한 직접 데이터 전송보다 100-1000배 빠릅니다.

RSA의 장점과 한계

다른 암호화 알고리즘과 마찬가지로 RSA에는 보안 시스템을 설계할 때 고려해야 할 강점과 약점이 있습니다. 객관적인 평가는 특정 작업에 적합한 도구를 선택하는 데 도움이 됩니다.

주요 장점

RSA의 주요 장점은 근본적인 키 분배 문제를 해결한다는 것입니다. 공개 키는 전체 시스템을 손상시킬 위험 없이 자유롭게 공개될 수 있습니다. 알고리즘의 다양성은 단일 키 쌍으로 암호화와 디지털 서명을 모두 지원하는 데 나타납니다. 또한 RSA는 광범위한 지원 생태계를 갖추고 있으며 모든 언어와 플랫폼에 라이브러리가 제공됩니다.

주요 한계

RSA의 주요 단점은 대칭 알고리즘에 비해 성능이 낮다는 것입니다. 최신 모바일 프로세서에서 RSA-2048을 복호화하는 데 약 5-15밀리초가 걸리지만, AES-256은 같은 시간에 기가바이트의 데이터를 처리합니다. 또한 RSA는 쇼어의 알고리즘을 통한 양자 공격에 취약하므로 장기 데이터 보호가 필요한 시스템에서 사용이 제한됩니다.

사용 권장 사항

모바일 프로젝트의 경우 NIST 전문가는 다음을 권장합니다. RSA를 키 암호화 및 디지털 서명에만 사용하고, 새 프로젝트에는 최소 3072비트의 키 길이를 선택하고, RSA를 AES와 하이브리드 방식으로 결합하고, 장기적인 계획 마이그레이션을 위해 양자 내성 표준의 개발을 모니터링합니다.