RSA: What It Is, Algorithm and Encryption Application

What is RSA?

RSA is a public-key cryptographic algorithm developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. The name is formed from the first letters of the authors' surnames. The algorithm became the first practically applicable asymmetric cryptosystem where encryption and decryption keys differ.

History of Creation

The RSA algorithm was published in 1977 in Scientific American magazine and is based on earlier work by Whitfield Diffie and Martin Hellman on public-key cryptography. The Massachusetts Institute of Technology obtained a patent for RSA in 1983, which lasted until 2000. According to the RSA Laboratories report (2023), the algorithm remains one of the most widespread cryptographic standards in the world — it is used in billions of devices daily.

The Principle of Asymmetry

Unlike symmetric ciphers where the same key is used for both encryption and decryption, RSA operates with a mathematically linked pair of keys. The public key can be published for anyone without risk of system compromise. The private key is known only to the owner and is never transmitted over the network. According to the IBM Security X-Force Threat Intelligence Index (2024) study, asymmetric encryption is used in 96% of modern secure data transmission protocols.

Mathematical Foundations

The security of RSA is based on the factoring problem — decomposing the product of two large prime numbers into factors. If you choose prime numbers p and q of 1024 bits each, their product n will be 2048 bits. Computing p and q knowing only n using modern methods is practically impossible: according to CNRS expert assessment (2024), cracking RSA-2048 would require over 300 billion years of computation on a classical computer.

How the RSA Algorithm Works

Let us consider the full RSA workflow from key generation to message encryption and decryption. Understanding these stages is necessary for correct implementation of the algorithm in mobile applications.

Key Generation

The process begins with selecting two large prime numbers p and q. The modulus n = p x q is computed, which determines the key length. Then Euler’s totient function phi(n) = (p-1)(q-1) is calculated. A public exponent e is chosen that is coprime with phi(n). The private exponent d is computed as the modular multiplicative inverse of e modulo phi(n). According to NIST SP 800-56B Rev. 2, the minimum length of n must be 2048 bits to ensure adequate protection.

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();
    }
}

Encryption and Decryption

To encrypt a message m, the sender converts it into an integer smaller than n and computes the ciphertext c = m^e mod n. The recipient uses the private key d to recover the original message: m = c^d mod n. It is important to note that RSA is not intended for encrypting large amounts of data due to low performance — the maximum message size equals the key length minus overhead bytes (approximately 190 bytes for RSA-2048 with OAEP).

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);
    }
}

Digital Signature with RSA

RSA is also used to create digital signatures — a mechanism for verifying data authenticity and integrity. The owner signs the message hash with their private key, and anyone can verify the signature using the public key. According to the Sectigo Certificate Transparency report (2025), over 85% of TLS certificates on the internet use RSA for digital signatures, making the algorithm the foundation of trust for web communications.

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)
}

Key Sizes and Security Levels

Key length directly affects the cryptographic strength of RSA. As computing power increases, the minimum acceptable key size is regularly reviewed by international standardization bodies. Let us examine the current recommendations from NIST and other regulators.

Impact on Performance

Increasing the RSA key length significantly affects operation execution time. Generating a 4096-bit key takes approximately 10 times longer than a 2048-bit key. Encryption and decryption operations with a longer key require more computational resources, which is critical for mobile devices with limited power consumption.

Quantum Threat

With the development of quantum computing, RSA can be broken using Shor’s algorithm in polynomial time. This algorithm, proposed by Peter Shor in 1994, can factor large numbers in O((log n)^3) operations. According to the IBM Quantum Roadmap (2025), practical cracking of RSA-2048 is expected no earlier than 2035, however NIST already recommends a gradual transition to post-quantum algorithms CRYSTALS-Kyber and CRYSTALS-Dilithium.

RSA in Mobile Development

RSA is actively used in mobile applications to ensure secure data transmission, server authentication, and digital transaction protection. Integration is carried out through standard cryptographic APIs of both major platforms.

Android Keystore

The Android platform provides Android Keystore — a system cryptographic key storage protected by the Trusted Execution Environment hardware level. RSA keys generated in KeyStore cannot be extracted from the device even if the application is compromised. This provides protection against a wide range of attacks, including malware with root access.

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

On iOS, RSA is handled through the Security Framework with access to the Secure Enclave on devices with A7 chip and newer. The Secure Enclave is a dedicated coprocessor isolated from the main processor that performs cryptographic operations and stores keys in a hardware vault. RSA keys can be generated both inside the Secure Enclave and in the software Keychain with various access levels.

Hybrid Encryption in Practice

In real mobile applications, RSA is rarely used for direct encryption of large data. The standard practice is a hybrid scheme: the application generates an AES session key, encrypts it with the server’s RSA public key, and sends it to the server. All subsequent traffic is encrypted with AES, which is 100-1000 times faster than transmitting data directly through RSA.

Advantages and Limitations of RSA

Like any cryptographic algorithm, RSA has strengths and weaknesses that must be considered when designing secure systems. An objective assessment helps choose the right tool for a specific task.

Key Advantages

The main advantage of RSA is solving the fundamental key distribution problem — the public key can be freely published without risk of compromising the entire system. The algorithm’s versatility is demonstrated by supporting both encryption and digital signatures with a single key pair. Additionally, RSA has an extensive support ecosystem: libraries are available for all languages and platforms.

Key Limitations

The main drawback of RSA is low performance compared to symmetric algorithms. Decrypting RSA-2048 on a modern mobile processor takes approximately 5-15 milliseconds, while AES-256 processes gigabytes of data in the same time. Also, RSA is vulnerable to quantum attacks via Shor’s algorithm, which limits its use in systems requiring long-term data protection.

Usage Recommendations

For mobile projects, NIST experts recommend: use RSA only for key encryption and digital signatures, choose a key length of at least 3072 bits for new projects, combine RSA with AES in a hybrid scheme, and monitor the development of post-quantum standards for planned migration in the long term.