Rivest-Shamir-Adleman-algoritmus

Magyar

Kiejtés

IPA: [ ˈrivɛʃtʃhɒmirɒdlɛmɒnɒlɡoritmuʃ]

Főnév

(matematika, algoritmusok, kriptográfia)

RSA (Rivest–Shamir–Adleman) algoritmus

Az RSA algoritmus egy aszimmetrikus titkosítási algoritmus, amelyet széles körben használnak adatvédelemre és digitális aláírásokra. A biztonsága azon alapul, hogy nagy számok prímtényezős felbontása számítási szempontból nehéz feladat.

Elmélet

Kulcsgenerálás

Két nagy prímszám kiválasztása: (p) és (q).
Modulus kiszámítása: (n = p q).
Euler-féle totient függvény: ((n) = (p-1) (q-1)).
Nyilvános kulcs exponens: Válasszunk egy (e)-t, amely relatív prím ((n))-hez ((1 < e < (n))).
Privát kulcs exponens: Számítsuk ki (d)-t, amelyre ((e d) (n) = 1).

Titkosítás

Egy (m) (üzenet) titkosítása: [ c = m^e n ] ahol (c) a titkosított üzenet.

Visszafejtés

A titkosított (c) üzenet visszafejtése: [ m = c^d n ] ahol (d) a privát kulcs.

1. 1. 1. **Kulcsgenerálás** 1. **Két nagy prímszám kiválasztása**: ${\textstyle p}$ és ${\textstyle q}$ . 2. **Modulus kiszámítása**: ${\textstyle n=p\cdot q}$ . 3. **Euler-féle totient függvény**: ${\textstyle \phi (n)=(p-1)\cdot (q-1)}$ . 4. **Nyilvános kulcs exponens**: Válasszunk egy ${\textstyle e}$ -t, amely relatív prím ${\textstyle \phi (n)}$ -hez ( ${\textstyle 1<e<\phi (n)}$ ). 5. **Privát kulcs exponens**: Számítsuk ki ${\textstyle d}$ -t, amelyre ${\textstyle (e\cdot d)\mod \phi (n)=1}$ .

1. 1. 1. **Titkosítás** Egy ${\textstyle m}$ (üzenet) titkosítása: $c=m^{e}\mod n$ ahol ${\textstyle c}$ a titkosított üzenet.

1. 1. 1. **Visszafejtés** A titkosított ${\textstyle c}$ üzenet visszafejtése: $m=c^{d}\mod n$ ahol ${\textstyle d}$ a privát kulcs.

Pszeudokód

Kulcsgenerálás

GenerateKeys():
    válassz két nagy prímszámot: p, q
    n = p * q
    φ = (p - 1) * (q - 1)
    válassz egy e-t, amely 1 < e < φ és gcd(e, φ) = 1
    számítsd ki d-t, amelyre (e * d) mod φ = 1
    visszatér (e, n), (d, n)  // nyilvános és privát kulcsok

Titkosítás

Encrypt(m, e, n):
    c = (m^e) mod n
    visszatér c

Visszafejtés

Decrypt(c, d, n):
    m = (c^d) mod n
    visszatér m

Python implementáció

RSA Algoritmus

import random
from math import gcd

def generate_keys():
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

    def mod_inverse(a, m):
        m0, x0, x1 = m, 0, 1
        while a > 1:
            q = a // m
            m, a = a % m, m
            x0, x1 = x1 - q * x0, x0
        return x1 + m0 if x1 < 0 else x1

    # Véletlenszerű prímszámok generálása
    primes = [i for i in range(100, 200) if is_prime(i)]
    p, q = random.sample(primes, 2)

    n = p * q
    phi = (p - 1) * (q - 1)

    # Nyilvános kulcs komponensek
    e = random.choice([i for i in range(2, phi) if gcd(i, phi) == 1])

    # Privát kulcs komponens
    d = mod_inverse(e, phi)

    return (e, n), (d, n)  # Nyilvános és privát kulcsok

def encrypt(message, public_key):
    e, n = public_key
    return [(ord(char) ** e) % n for char in message]

def decrypt(ciphertext, private_key):
    d, n = private_key
    return ''.join([chr((char ** d) % n) for char in ciphertext])

# Kulcsgenerálás
public_key, private_key = generate_keys()
print("Nyilvános kulcs:", public_key)
print("Privát kulcs:", private_key)

# Üzenet titkosítása és visszafejtése
message = "HELLO"
cipher = encrypt(message, public_key)
print("Titkosított üzenet:", cipher)

decrypted_message = decrypt(cipher, private_key)
print("Visszafejtett üzenet:", decrypted_message)

C++ implementáció

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// Euklideszi algoritmus a legnagyobb közös osztóhoz
int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// Moduláris inverz kiszámítása
int mod_inverse(int a, int m) {
    int m0 = m, x0 = 0, x1 = 1;
    while (a > 1) {
        int q = a / m;
        int t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }
    return (x1 + m0) % m0;
}

// Ellenőrzi, hogy egy szám prímszám-e
bool is_prime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

void generate_keys(int& e, int& d, int& n) {
    vector<int> primes;
    for (int i = 100; i < 200; ++i) {
        if (is_prime(i)) primes.push_back(i);
    }

    srand(time(0));
    int p = primes[rand() % primes.size()];
    int q = primes[rand() % primes.size()];
    while (q == p) {
        q = primes[rand() % primes.size()];
    }

    n = p * q;
    int phi = (p - 1) * (q - 1);

    do {
        e = rand() % phi;
    } while (gcd(e, phi) != 1);

    d = mod_inverse(e, phi);
}

vector<int> encrypt(const string& message, int e, int n) {
    vector<int> cipher;
    for (char c : message) {
        cipher.push_back(static_cast<int>(pow(c, e)) % n);
    }
    return cipher;
}

string decrypt(const vector<int>& cipher, int d, int n) {
    string message;
    for (int c : cipher) {
        message += static_cast<char>(static_cast<int>(pow(c, d)) % n);
    }
    return message;
}

int main() {
    int e, d, n;
    generate_keys(e, d, n);

    cout << "Nyilvános kulcs: (" << e << ", " << n << ")\n";
    cout << "Privát kulcs: (" << d << ", " << n << ")\n";

    string message = "HELLO";
    vector<int> cipher = encrypt(message, e, n);

    cout << "Titkosított üzenet: ";
    for (int c : cipher) {
        cout << c << " ";
    }
    cout << endl;

    string decrypted_message = decrypt(cipher, d, n);
    cout << "Visszafejtett üzenet: " << decrypted_message << endl;

    return 0;
}

Összegzés

Előnyök:
- Az RSA biztonságos és széles körben használt.
- Könnyen érthető matematikai alapelvek.
Hátrányok:
- Lassabb, mint a szimmetrikus algoritmusok.
- Nagy számítási erőforrásokat igényel.

Az RSA algoritmus a biztonságos kommunikáció alapvető eszköze, és Pythonban és C++-ban is könnyen implementálható kis léptékű alkalmazásokhoz.

További információk

Rivest-Shamir-Adleman-algoritmus - Értelmező szótár (MEK)
Rivest-Shamir-Adleman-algoritmus - Etimológiai szótár (UMIL)
Rivest-Shamir-Adleman-algoritmus - Szótár.net (hu-hu)
Rivest-Shamir-Adleman-algoritmus - DeepL (hu-de)
Rivest-Shamir-Adleman-algoritmus - Яндекс (hu-ru)
Rivest-Shamir-Adleman-algoritmus - Google (hu-en)
Rivest-Shamir-Adleman-algoritmus - Helyesírási szótár (MTA)
Rivest-Shamir-Adleman-algoritmus - Wikidata
Rivest-Shamir-Adleman-algoritmus - Wikipédia (magyar)