RSA: що це, алгоритм та застосування шифрування

Що таке RSA?

RSA — криптографічний алгоритм з відкритим ключем, розроблений у 1977 році Рональдом Рівестом, Аді Шаміром та Леонардом Адлеманом. Назва утворена від перших літер прізвищ авторів. Алгоритм став першою практично застосовною асиметричною криптосистемою, де ключі шифрування та дешифрування різняться.

Історія створення

Алгоритм RSA був опублікований у 1977 році в журналі Scientific American і ґрунтується на більш ранніх роботах Вітфілда Діффі та Мартіна Геллмана з криптографії з відкритим ключем. Массачусетський технологічний інститут отримав патент на RSA у 1983 році, який діяв до 2000 року. Згідно зі звітом RSA Laboratories (2023), алгоритм залишається одним із найпоширеніших криптографічних стандартів у світі — він використовується в мільярдах пристроїв щодня.

Принцип асиметричності

На відміну від симетричних шифрів, де один і той самий ключ застосовується і для шифрування, і для дешифрування, RSA оперує математично пов'язаною парою ключів. Відкритий ключ може бути опублікований для всіх бажаючих без ризику компрометації системи. Закритий ключ відомий тільки власнику і ніколи не передається по мережі. Згідно з дослідженням IBM Security X-Force Threat Intelligence Index (2024), асиметричне шифрування використовується в 96% сучасних протоколів захищеної передачі даних.

Математичні основи

Безпека RSA базується на задачі факторизації — розкладанні добутку двох великих простих чисел на множники. Якщо вибрати прості числа p та q довжиною 1024 біти кожне, то їх добуток n міститиме 2048 біт. Обчислити p та q, знаючи тільки n, сучасними методами практично неможливо: за даними експертної оцінки CNRS (2024), для зламу RSA-2048 знадобиться понад 300 мільярдів років обчислень на класичному комп'ютері.

Як працює алгоритм RSA

Розглянемо повний цикл роботи RSA від генерації ключів до шифрування та розшифровки повідомлення. Розуміння цих етапів необхідне для коректної реалізації алгоритму в мобільних додатках.

Генерація ключів

Процес починається з вибору двох великих простих чисел p та q. Обчислюється модуль n = p x q, який визначає довжину ключа. Потім обчислюється функція Ейлера phi(n) = (p-1)(q-1). Вибирається відкрита експонента e, взаємно проста з phi(n). Закрита експонента 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 не призначений для шифрування великих об'ємів даних через низьку продуктивність — максимальний розмір повідомлення дорівнює довжині ключа мінус службові байти (приблизно 190 байт для RSA-2048 з 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);
    }
}

Цифровий підпис на RSA

RSA також використовується для створення цифрових підписів — механізму перевірки автентичності та цілісності даних. Власник підписує хеш повідомлення своїм закритим ключем, а будь-хто може перевірити підпис відкритим ключем. Згідно зі звітом Sectigo Certificate Transparency (2025), понад 85% TLS-сертифікатів в інтернеті використовують 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 біт займає приблизно в 10 разів більше часу, ніж 2048 біт. Операції шифрування та дешифрування з довгим ключем потребують більше обчислювальних ресурсів, що критично для мобільних пристроїв з обмеженим енергоспоживанням.

Квантова загроза

З розвитком квантових обчислень RSA може бути зламаний за допомогою алгоритму Шора за поліноміальний час. Цей алгоритм, запропонований Пітером Шором у 1994 році, дозволяє факторизувати великі числа за O((log n)^3) операцій. За даними IBM Quantum Roadmap (2025), практичний злам RSA-2048 очікується не раніше 2035 року, однак NIST вже рекомендує поступовий перехід на постквантові алгоритми CRYSTALS-Kyber та CRYSTALS-Dilithium.

Застосування RSA в мобільній розробці

RSA активно застосовується в мобільних додатках для забезпечення безпечної передачі даних, перевірки автентичності серверів та захисту цифрових транзакцій. Інтеграція здійснюється через стандартні криптографічні API обох основних платформ.

Android Keystore

Платформа Android надає Android Keystore — системне сховище криптографічних ключів, захищене апаратним рівнем Trusted Execution Environment. Ключі RSA, згенеровані в KeyStore, не можуть бути вилучені з пристрою навіть при компрометації додатка. Це забезпечує захист від широкого класу атак, включаючи malware з root-доступом.

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 використовується Security Framework з доступом до Secure Enclave на пристроях з чіпом A7 та новіше. Secure Enclave — виділений співпроцесор, ізольований від основного процесора, який виконує криптографічні операції та зберігає ключі в апаратному конклаві. Ключі RSA можуть бути згенеровані як всередині Secure Enclave, так і в програмному Keychain з різними рівнями доступу.

Гібридне шифрування на практиці

В реальних мобільних додатках RSA рідко використовується для шифрування великих даних безпосередньо. Стандартна практика — гібридна схема: додаток генерує сесійний ключ AES, шифрує його відкритим ключем RSA сервера та відправляє на сервер. Весь подальший трафік шифрується AES, що в 100-1000 разів швидше, ніж пряма передача даних через RSA.

Переваги та обмеження RSA

Як і будь-який криптографічний алгоритм, RSA має сильні та слабкі сторони, які необхідно враховувати при проектуванні захищених систем. Об'єктивна оцінка допомагає вибрати правильний інструмент для конкретної задачі.

Ключові переваги

Головною перевагою RSA є вирішення фундаментальної проблеми розподілу ключів — відкритий ключ можна вільно публікувати без ризику компрометації всієї системи. Універсальність алгоритму проявляється в підтримці як шифрування, так і цифрового підпису однією парою ключів. Крім того, RSA має велику екосистему підтримки: бібліотеки доступні для всіх мов та платформ.

Основні обмеження

Головний недолік RSA — низька продуктивність порівняно з симетричними алгоритмами. Дешифрування RSA-2048 на сучасному мобільному процесорі займає приблизно 5-15 мілісекунд, в той час як AES-256 обробляє гігабайти даних за той самий час. Також RSA вразливий до квантових атак через алгоритм Шора, що обмежує його застосування в системах з довгостроковим терміном захисту даних.

Рекомендації щодо використання

Для мобільних проектів експерти NIST рекомендують: використовувати RSA тільки для шифрування ключів та цифрових підписів, обирати довжину ключа не менше 3072 біт для нових проектів, комбінувати RSA з AES в гібридній схемі та відстежувати розвиток постквантових стандартів для планової міграції в довгостроковій перспективі.