RSA Encryption Algorithm Explained: Principles, Implementation & Applications

RSA is a public-key cryptographic algorithm proposed in 1977 by mathematicians Ron Rivest, Adi Shamir, and Leonard Adleman. It is the most theoretically mature and well-established asymmetric encryption algorithm to date. RSA is based on the mathematical difficulty of factoring large integers into their prime factors, and its security relies on the computational difficulty of large number factorization. As the cornerstone of public-key cryptography, RSA is widely used in digital signatures, key exchange, secure communication, and many other fields. This article delves into the core mechanisms of the RSA algorithm starting from its mathematical foundations.

I. Overview of RSA

RSA was the first algorithm that could be used for both data encryption and digital signatures. It is named after the initials of its three inventors.

Core Features

As a representative asymmetric encryption algorithm, RSA has the following notable features: 1) Encrypt with public key, decrypt with private key; 2) Sign with private key, verify with public key; 3) Simple key distribution, no secure channel required; 4) Security based on mathematical hard problems.

II. Mathematical Principles

The security of the RSA algorithm is built on several classic hard problems in number theory. Understanding these mathematical foundations is key to mastering RSA.

2.1 Large Prime Factorization Problem

The large prime factorization problem is the core of RSA security. The problem can be stated as follows: given two large primes p and q, computing their product n = p × q is easy; but conversely, finding p and q given n is considered very difficult. This is the so-called 'one-way function' property. Currently, the fastest factorization algorithms (such as the Number Field Sieve) still have subexponential time complexity. For sufficiently large primes (e.g., 2048 bits or more), factorization within a reasonable time is infeasible.

2.2 Euler's Totient Function

Euler's totient function φ(n) counts the positive integers up to n that are relatively prime to n. For a prime p, φ(p) = p - 1. For the product of two distinct primes n = p × q, we have φ(n) = φ(p) × φ(q) = (p-1)(q-1). This property plays a crucial role in RSA key generation.

2.3 Modular Exponentiation

Modular exponentiation is the core operation of RSA encryption and decryption, computing a^b mod n. Directly computing a^b would produce astronomical numbers, but through properties of modular arithmetic and the fast exponentiation algorithm (square-and-multiply algorithm), the result can be computed efficiently. The properties of modular exponentiation ensure that RSA encryption and decryption operations are computationally feasible.

2.4 Fermat-Euler Theorem

Fermat's Little Theorem is a special case of Euler's theorem. It states that if p is prime and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p). Euler's theorem generalizes this: if a and n are coprime, then a^φ(n) ≡ 1 (mod n). This theorem is the mathematical foundation for the correctness of RSA encryption and decryption.

III. Key Generation Process

RSA key generation is the starting point of the entire algorithm, involving steps such as prime generation and parameter calculation.

Generation Steps

1. Choose large primes：Randomly select two distinct large primes p and q with similar bit lengths but not equal
2. Compute modulus n：Calculate n = p × q. The bit length of n is the key length (e.g., 2048 bits)
3. Compute Euler's totient：Calculate φ(n) = (p-1)(q-1)
4. Choose public exponent e：Select an integer e such that 1 < e < φ(n) and e is coprime with φ(n). Typically e = 65537 (0x10001)
5. Compute private exponent d：Calculate d such that d × e ≡ 1 (mod φ(n)), i.e., d is the modular multiplicative inverse of e modulo φ(n)

Finally, the public key is (e, n) and the private key is (d, n). p and q must be destroyed or kept strictly confidential.

Simple Example

For easier understanding, let's demonstrate RSA key generation with small numbers (in practice, use primes with hundreds of digits):

// RSA 密钥生成示例（使用小数字，仅用于演示）
// 1. 选择两个素数
const p = 61;
const q = 53;

// 2. 计算 n = p * q
const n = p * q; // n = 3233

// 3. 计算 φ(n) = (p-1)(q-1)
const phi = (p - 1) * (q - 1); // phi = 60 * 52 = 3120

// 4. 选择公钥指数 e（通常为 65537，这里用小数值）
const e = 17; // 1 < 17 < 3120，且 17 与 3120 互质

// 5. 计算私钥 d = e^(-1) mod phi
// 使用扩展欧几里得算法计算
function modInverse(a, m) {
  let m0 = m;
  let y = 0, x = 1;
  if (m === 1) return 0;
  while (a > 1) {
    let q = Math.floor(a / m);
    let t = m;
    m = a % m;
    a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}

const d = modInverse(e, phi); // d = 2753

console.log('公钥 (e, n):', e, n);  // (17, 3233)
console.log('私钥 (d, n):', d, n);  // (2753, 3233)

// 加密: c = m^e mod n
// 解密: m = c^d mod n
const plaintext = 65; // 'A' 的 ASCII 码
const ciphertext = BigInt(plaintext) ** BigInt(e) % BigInt(n);
console.log('明文:', plaintext);
console.log('密文:', ciphertext.toString());

const decrypted = BigInt(ciphertext) ** BigInt(d) % BigInt(n);
console.log('解密后:', decrypted.toString());

IV. Encryption and Decryption Principles

Both RSA encryption and decryption are based on modular exponentiation, and their correctness is guaranteed by Euler's theorem.

4.1 Encryption Process

The sender encrypts the plaintext m using the recipient's public key (e, n). The plaintext m must satisfy 0 ≤ m < n. The encryption formula is: c = m^e mod n, where c is the ciphertext.

4.2 Decryption Process

The recipient decrypts the ciphertext c using their private key (d, n). The decryption formula is: m = c^d mod n. According to Euler's theorem, it can be proven that this decryption process correctly recovers the plaintext.

4.3 Correctness Proof

The core proof of RSA decryption correctness: since c = m^e mod n, then c^d = m^(ed) mod n. And since ed ≡ 1 (mod φ(n)), we have ed = kφ(n) + 1. Therefore m^(ed) = m^(kφ(n)+1) = m × (m^φ(n))^k. By Euler's theorem, m^φ(n) ≡ 1 (mod n), so (m^φ(n))^k ≡ 1^k = 1 (mod n). Thus m^(ed) ≡ m × 1 = m (mod n), meaning c^d ≡ m (mod n).

RSA Encryption/Decryption (Node.js Example)

const crypto = require('crypto');

// 生成 RSA 密钥对
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
  publicExponent: 65537,
  publicKeyEncoding: {
    type: 'spki',
    format: 'pem'
  },
  privateKeyEncoding: {
    type: 'pkcs8',
    format: 'pem'
  }
});

console.log('公钥:', publicKey);
console.log('私钥:', privateKey);

// 加密数据
const plaintext = 'Hello, RSA!';
const encrypted = crypto.publicEncrypt(
  {
    key: publicKey,
    padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
    oaepHash: 'sha256'
  },
  Buffer.from(plaintext)
);

console.log('密文:', encrypted.toString('base64'));

// 解密数据
const decrypted = crypto.privateDecrypt(
  {
    key: privateKey,
    padding: crypto.constants.RSA_PKCS1_OAEP_PADDING,
    oaepHash: 'sha256'
  },
  encrypted
);

console.log('解密后:', decrypted.toString());

V. Digital Signatures

RSA can be used not only for encryption but also for digital signatures, which is one of its most important applications.

5.1 Signature Principle

The digital signature process is the reverse of encryption: the signer signs the message digest using their private key, and the verifier verifies using the signer's public key. The signature formula is: s = m^d mod n, where m is the message digest and s is the signature. The verification formula is: m' = s^e mod n. If m' = m, the signature is valid.

5.2 Signature Flow

1. Message digest：Compute the digest of the original message using a hash algorithm (e.g., SHA-256)
2. Sign with private key：Sign the digest using the signer's private key
3. Send message：Send the original message together with the signature to the recipient
4. Verify signature：The recipient verifies the validity of the signature using the public key
5. Digest comparison：Compare the recovered digest with the computed digest to see if they match

5.3 Security Guarantees

Digital signatures provide triple security guarantees: 1) Authentication: confirming that the message indeed comes from the claimed sender; 2) Integrity: ensuring that the message has not been tampered with during transmission; 3) Non-repudiation: the sender cannot deny having sent the message.

RSA Digital Signature (Node.js Example)

const crypto = require('crypto');

// 生成 RSA 密钥对
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
  publicExponent: 65537,
  publicKeyEncoding: { type: 'spki', format: 'pem' },
  privateKeyEncoding: { type: 'pkcs8', format: 'pem' }
});

// 原始消息
const message = 'This is an important document.';

// 签名
const sign = crypto.createSign('SHA256');
sign.update(message);
const signature = sign.sign(privateKey, 'base64');

console.log('原始消息:', message);
console.log('签名:', signature);

// 验签
const verify = crypto.createVerify('SHA256');
verify.update(message);
const isValid = verify.verify(publicKey, signature, 'base64');

console.log('签名是否有效:', isValid);

// 尝试篡改消息
const tamperedMessage = 'This is a tampered document.';
const verifyTampered = crypto.createVerify('SHA256');
verifyTampered.update(tamperedMessage);
const isTamperedValid = verifyTampered.verify(publicKey, signature, 'base64');

console.log('篡改后签名是否有效:', isTamperedValid);

VI. Application Scenarios

6.1 TLS/SSL Secure Communication

In the HTTPS protocol, RSA was once the primary key exchange algorithm. The server places the public key in a digital certificate, and the client encrypts a randomly generated session key using the public key. Only the server with the private key can decrypt it, thus establishing a secure encrypted channel. Although modern TLS tends to use ECDHE for forward secrecy, RSA is still widely used for server authentication.

6.2 Email Encryption and Signing

In email security standards such as S/MIME and PGP/GPG, RSA is used for encrypting email content and digital signatures. The sender encrypts the email using the recipient's public key, ensuring that only the recipient can decrypt and read it; at the same time, they sign with their own private key, allowing the recipient to verify the source and integrity of the email.

6.3 Code Signing

Software developers use RSA private keys to digitally sign released software. Users can verify through the public key that the software indeed comes from a trusted developer and has not been tampered with. This plays an important role in preventing malware implantation and supply chain attacks.

6.4 Blockchain and Cryptocurrency

Although most modern blockchains use ECDSA (Elliptic Curve Digital Signature Algorithm), the signature principle of RSA is in the same vein as blockchain address generation and transaction signing mechanisms. RSA's public-private key system provides the theoretical foundation for decentralized identity authentication in blockchains.

6.5 Authentication and Access Control

In scenarios such as smart cards, USB Keys, and two-factor authentication, RSA is used for identity authentication. The user's device stores the private key, and the server stores the public key. User identity is verified through a challenge-response mechanism without transmitting passwords, greatly improving security.

VII. Security Analysis

RSA's security relies on the difficulty of large number factorization, but this does not mean RSA is absolutely secure.

7.1 Key Length and Security

The security of RSA is directly related to key length. As computing power increases and factorization algorithms improve, the required key length continues to grow:

7.2 Common Attack Methods

• Brute-force factorization attack：Trying all possible prime factors. For keys of 2048 bits or more, this method is computationally infeasible
• Timing attack：Inferring private key information by measuring time differences in decryption operations. Can be defended against by using constant-time operations
• Chosen-ciphertext attack：The attacker chooses specific ciphertexts for the target to decrypt, obtaining information from them. OAEP padding can effectively defend against this
• Fault injection attack：Inducing calculation errors through hardware faults, thereby leaking private key information

7.3 Importance of Padding Schemes

Using bare RSA (textbook RSA) directly is insecure; secure padding schemes must be used:

RSA-OAEP Encryption Example

// 使用 Web Crypto API 进行 RSA-OAEP 加密
async function encryptWithRSA_OAEP(publicKeyPem, plaintext) {
  // 将 PEM 格式的公钥导入
  const publicKey = await window.crypto.subtle.importKey(
    'spki',
    pemToArrayBuffer(publicKeyPem),
    {
      name: 'RSA-OAEP',
      hash: 'SHA-256'
    },
    false,
    ['encrypt']
  );

  // 加密
  const encoder = new TextEncoder();
  const data = encoder.encode(plaintext);
  const encrypted = await window.crypto.subtle.encrypt(
    { name: 'RSA-OAEP' },
    publicKey,
    data
  );

  return arrayBufferToBase64(encrypted);
}

async function decryptWithRSA_OAEP(privateKeyPem, ciphertextBase64) {
  // 将 PEM 格式的私钥导入
  const privateKey = await window.crypto.subtle.importKey(
    'pkcs8',
    pemToArrayBuffer(privateKeyPem),
    {
      name: 'RSA-OAEP',
      hash: 'SHA-256'
    },
    false,
    ['decrypt']
  );

  // 解密
  const encryptedData = base64ToArrayBuffer(ciphertextBase64);
  const decrypted = await window.crypto.subtle.decrypt(
    { name: 'RSA-OAEP' },
    privateKey,
    encryptedData
  );

  const decoder = new TextDecoder();
  return decoder.decode(decrypted);
}

VIII. Comparison with ECC/SM2

With the development of elliptic curve cryptography, ECC and SM2 are replacing RSA in more and more scenarios.

Algorithm Comparison

Comparison Summary

From the comparison we can see: 1) ECC/SM2 has shorter keys and faster computation at the same security level; 2) RSA's advantages are simple understanding, mature implementation, and good compatibility; 3) For resource-constrained devices (such as IoT devices), ECC is a better choice; 4) RSA is still widely used in legacy systems and scenarios with high compatibility requirements.

IX. Practical Recommendations

9.1 Key Length Selection

Choosing the appropriate key length is the first step to ensuring RSA security:

• Short-term security (1-2 years): 2048-bit key
• Medium-term security (3-5 years): 3072-bit key
• Long-term security (10+ years): 4096-bit key
• High security requirements: consider using ECC instead of RSA

9.2 Padding Scheme Selection

• Use OAEP padding for encryption with SHA-256 or higher hash
• Use PSS padding for signatures with SHA-256 or higher hash
• Avoid using PKCS#1 v1.5 padding scheme
• Never use bare RSA (textbook RSA)

9.3 Implementation Considerations

• Use well-tested cryptography libraries, do not implement RSA yourself
• Ensure randomness and quality of prime generation
• Use constant-time operations to defend against timing attacks
• Properly safeguard private keys, consider using Hardware Security Modules (HSM)
• Regularly rotate keys and establish a key management system

Web Crypto API RSA Implementation

// 使用 Web Crypto API 生成 RSA 密钥对并进行签名
async function generateRSAKeyPair() {
  const keyPair = await window.crypto.subtle.generateKey(
    {
      name: 'RSASSA-PKCS1-v1_5',
      modulusLength: 2048,
      publicExponent: new Uint8Array([0x01, 0x00, 0x01]), // 65537
      hash: { name: 'SHA-256' }
    },
    true,
    ['sign', 'verify']
  );

  // 导出公钥
  const publicKey = await window.crypto.subtle.exportKey(
    'spki',
    keyPair.publicKey
  );

  // 导出私钥
  const privateKey = await window.crypto.subtle.exportKey(
    'pkcs8',
    keyPair.privateKey
  );

  return {
    publicKey: arrayBufferToBase64(publicKey),
    privateKey: arrayBufferToBase64(privateKey)
  };
}

async function rsaSign(privateKeyData, message) {
  const privateKey = await window.crypto.subtle.importKey(
    'pkcs8',
    base64ToArrayBuffer(privateKeyData),
    {
      name: 'RSASSA-PKCS1-v1_5',
      hash: { name: 'SHA-256' }
    },
    false,
    ['sign']
  );

  const encoder = new TextEncoder();
  const data = encoder.encode(message);
  
  const signature = await window.crypto.subtle.sign(
    { name: 'RSASSA-PKCS1-v1_5' },
    privateKey,
    data
  );

  return arrayBufferToBase64(signature);
}

X. TudoSi Online Tool

If you want to actually experience RSA encryption/decryption and digital signatures, you can use our online tool:

XI. Summary

RSA, as the pioneering work of public-key cryptography, has a solid theoretical foundation and a wide range of application scenarios. From a mathematical perspective, RSA is based on the difficulty of large number factorization, using modular exponentiation to implement encryption/decryption and digital signatures; from an application perspective, RSA underpins the security infrastructure of the modern internet, from HTTPS to digital certificates, from email encryption to code signing, its presence can be seen everywhere.

However, with the development of computing technology and the threat of quantum computing, RSA also faces new challenges. Elliptic Curve Cryptography (ECC) has shorter keys and higher efficiency at the same security level, and is gradually becoming an alternative to RSA. But in the foreseeable future, RSA will continue to play an important role in many scenarios. Understanding the principles of RSA is crucial for deeply mastering modern cryptography.