La funzione di crittografia nel cifrario RSA è una funzione esponenziale modulo n e la funzione di decifratura è una funzione esponenziale con un esponente diverso?

/ / Pubblicato in Cybersecurity, Fondamenti di crittografia classica EITC/IS/CCF, Introduzione alla crittografia a chiave pubblica, Il crittosistema RSA e l'elevamento a potenza efficiente

Il crittosistema RSA è uno schema crittografico fondamentale a chiave pubblica basato su principi di teoria dei numeri, in particolare sulla difficoltà matematica della fattorizzazione di numeri composti di grandi dimensioni. Nell'esaminare le funzioni di crittografia e decifratura in RSA, è sia accurato che istruttivo caratterizzare queste operazioni come esponenziali modulari, ciascuna delle quali utilizza un esponente distinto.

Generazione di chiavi in ​​RSA

L'algoritmo RSA inizia con la generazione di due grandi numeri primi, indicati come p e q, che sono tenuti segreti. Il loro prodotto n = pq forma il modulo sia per la chiave pubblica che per quella privata. Il totale (funzione phi di Eulero) di n è calcolato come \varphi(n) = (p-1)(q-1)L'esponente pubblico e è scelto in modo tale che 1 < e < \varphi(n) e \mcd(e, \varphi(n)) = 1, assicurando che e è invertibile modulo \varphi(n). L'esponente privato d viene quindi calcolato come l'inverso moltiplicativo modulare di e modulo \varphi(n), soddisfacente ed \equiv 1 \pmod{\varphi(n)}.

- Chiave pubblica: (n, e)
- Chiave privata: (n, d)

Funzione di crittografia

Dato un messaggio in chiaro mDurante la serata, 0 \leq m < n, l'operazione di crittografia trasforma m in testo cifrato c utilizzando la chiave pubblica del destinatario:

    \[ c = E(m) = m^e \bmod n \]

Questa è inequivocabilmente una funzione esponenziale, dove la base è il messaggio m e l'esponente è l'esponente della chiave pubblica e, tutto calcolato modulo nL'operazione viene eseguita nel gruppo matematico degli interi modulo n, indicato come \mathbb{Z}_n.

Funzione di decrittazione

Per recuperare il messaggio originale m dal testo cifrato c, il destinatario utilizza l'esponente della chiave privata d:

    \[ m = D(c) = c^d \bmod n \]

Ancora una volta, la funzione di decrittazione è una funzione esponenziale modulo n, questa volta con il testo cifrato c come base e come esponente privato d come esponente. L'operazione sfrutta le proprietà aritmetiche modulari e la relazione matematica tra e e d.

Perché l'esponenziazione modulare?

L'uso dell'esponenziale modulare non è casuale. Il fulcro della sicurezza e della correttezza di RSA è radicato nel teorema di Eulero, che afferma che per qualsiasi numero intero a coprimo a n:

    \[ a^{\varphi(n)} \equiv 1 \pmod{n} \]

Dal ed \equiv 1 \pmod{\varphi(n)}, esiste un numero intero k così ed = 1 + k\varphi(n)Pertanto, la decrittazione annulla la crittografia, come mostrato di seguito:

    \[ D(E(m)) = (m^e)^d \bmod n = m^{ed} \bmod n = m^{1 + k\varphi(n)} \bmod n = m \cdot (m^{\varphi(n)})^k \bmod n \]

Dal m^{\varphi(n)} \equiv 1 \pmod{n}, questo si semplifica in m.

Esempio didattico

Consideriamo un esempio concreto utilizzando numeri primi piccoli per chiarezza (nota: in pratica, per motivi di sicurezza, i numeri primi devono essere composti da centinaia di cifre):

1. Scegli i numeri primi: p = 61, q = 53.
2. Calcola n = pq = 3233.
3. Calcola \varphi(n) = (p-1)(q-1) = 60 \times 52 = 3120.
4. Scegliere e = 17 (comunemente usato, coprimo con 3120).
5. Calcola d così ed \equiv 1 \pmod{3120}. Qui, d = 2753.

Supponiamo che Alice voglia crittografare m = 65 per Bob:

- crittografia:

    \[ c = 65^{17} \bmod 3233 = 2790 \]

- Decrittografia:

    \[ m = 2790^{2753} \bmod 3233 = 65 \]

Entrambe le operazioni sono esponenziali modulari: la crittografia utilizza l'esponente 17, la decrittazione l'esponente 2753, entrambe modulo 3233.

Esponenziazione efficiente

Nelle implementazioni pratiche, il calcolo m^e \bmod n or c^d \bmod n direttamente eseguendo l'esponenziale e quindi riducendo il modulo n sarebbe computazionalmente irrealizzabile per esponenti grandi. Invece, vengono utilizzati algoritmi come "quadrato e moltiplicazione" (noto anche come elevazione a potenza binaria). Questi algoritmi scompongono l'elevazione a potenza in una sequenza di quadrati e moltiplicazioni, ciascuna seguita da una riduzione modulare, che consente un calcolo efficiente anche per esponenti e moduli molto grandi.

Proprietà matematiche che garantiscono la correttezza

La correttezza dell'RSA dipende dalle seguenti proprietà:

– La mappatura m \mapsto m^e \bmod n è iniettivo (uno a uno) sull'insieme dei messaggi validi, a condizione m è coprimo a n.
– La mappatura inversa c \mapsto c^d \bmod n recupera il messaggio originale m, a causa della relazione ed \equiv 1 \pmod{\varphi(n)}.
– La sicurezza dell’RSA si basa sulla difficoltà di dedurre d da e e n, o equivalentemente, la fattorizzazione n per trovare p e q, che consente quindi il calcolo di \varphi(n).

Fondamenti teorici

La struttura algebrica alla base di RSA è il gruppo moltiplicativo degli interi modulo n, indicato come \mathbb{Z}_n^*Per i messaggi che non sono sovrapponibili a n, vengono apportate alcune modifiche tecniche, ma in circostanze tipiche i messaggi sono obbligatori o rinforzati per garantire la coprimalità.

Dalla teoria dei gruppi, la funzione di esponenziale modulare è un automorfismo di gruppo quando è limitata a \mathbb{Z}_n^*Questo automorfismo è invertibile, con la mappa inversa data dall'esponenziale alla potenza d.

Riepilogo delle funzioni

- Funzione di crittografia: Funzione esponenziale modulo n con esponente e: E(m) = m^e \bmod n.
- Funzione di decrittazione: Funzione esponenziale modulo n con esponente d: D(c) = c^d \bmod n.

Entrambi i processi sono matematicamente equivalenti all'elevamento dell'input a una potenza (o e or d) e riducendo il risultato modulo n.

Potenziali insidie ​​e considerazioni sulla sicurezza

È importante notare che l'RSA testuale (come descritto sopra) è deterministico e malleabile; ovvero, crittografare lo stesso messaggio due volte produce testi cifrati identici e alcune manipolazioni algebriche sui testi cifrati si traducono in modifiche prevedibili nel testo in chiaro. Per questi motivi, le implementazioni pratiche utilizzano schemi di padding (come PKCS#1 v1.5 o OAEP), che randomizzano il testo in chiaro prima della crittografia, migliorando notevolmente la sicurezza.

Inoltre, se vengono scelti valori impropri per e o se i numeri primi p e q Se sono troppo piccoli o generati male, il sistema RSA può essere compromesso. Gli esponenti devono essere sufficientemente grandi da prevenire determinati attacchi, ma sufficientemente piccoli da consentire un calcolo efficiente.

Le funzioni di crittografia e decrittografia in RSA sono entrambe operazioni di esponenzializzazione modulari, che differiscono solo per l'esponente utilizzato: esponente pubblico e per la crittografia, esponente privato d per la decrittazione. La simmetria matematica e l'invertibilità di queste funzioni sono fondamentali per il funzionamento e la sicurezza del sistema crittografico RSA.

Altre domande e risposte recenti riguardanti Fondamenti di crittografia classica EITC/IS/CCF:

Visualizza altre domande e risposte in EITC/IS/CCF Classical Cryptography Fundamentals

Altre domande e risposte:

Etichettato sotto: , , , , ,