💻 computer science

New Ideas on a New Old Type of Cipher:The Mixed-Radix One-Time Pad

Questo articolo formalizza e generalizza il one-time pad a basi non uniformi come Mixed-Radix One-Time Pad (MR-OTP), dimostrando che raggiunge la perfetta segretezza di Shannon, recuperando le varianti classiche come casi particolari, e dimostrando che le basi segrete non possono ridurre l'entropia della chiave richiesta, proponendo al contempo un protocollo di sessione sicuro.

Autori originali: Fabio F. G. Buono

Pubblicato 2026-06-16

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Fabio F. G. Buono

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

L'Idea Centrale: Un Modo Migliore per Preparare una Valigia

Immagina di avere una valigia (un messaggio) che vuoi inviare a un amico, ma vuoi assicurarti che nessun altro possa aprirla. Il punto di riferimento per questo è il One-Time Pad (OTP). Pensa all'OTP come a una serratura magica dove serve una chiave che sia esattamente della stessa dimensione della tua valigia. Se la chiave è veramente casuale e usata una sola volta, la serratura è inattaccabile.

Tuttavia, l'OTP tradizionale di solito ti costringe a imballare tutto in una valigia "binaria" standard (usando solo 0 e 1). Se stai inviando una lettera, devi convertire ogni lettera in una lunga stringa di 0 e 1, il che può essere inefficiente.

Questo articolo introduce una nuova versione chiamata Mixed-Radix One-Time Pad (MR-OTP). Invece di forzare tutto in una valigia binaria, ti permette di costruire una valigia personalizzata dove ogni scomparto può avere una dimensione diversa.

Come Funziona: La Valigia Personalizzata

Immagina di preparare una valigia con tre articoli diversi:

Una lettera (26 possibilità: A–Z).
Il colore di un semaforo (3 possibilità: Rosso, Giallo, Verde).
Un lancio di moneta (2 possibilità: Testa o Croce).

Nel vecchio sistema binario, dovresti convertire tutti questi elementi in una lunga e disordinata stringa di 0 e 1.
Nell'MR-OTP, crei un sistema a "base mista" (mixed-radix). Hai tre slot nella tua valigia:

Slot 1: Contiene 26 opzioni.
Slot 2: Contiene 3 opzioni.
Slot 3: Contiene 2 opzioni.

Per chiuderla a chiave, non usi solo una singola chiave. Usi una chiave per ogni slot:

Un numero casuale tra 0 e 25 per la lettera.
Un numero casuale tra 0 e 2 per la luce.
Un numero casuale tra 0 e 1 per la moneta.

Aggiungi il tuo messaggio segreto a questi numeri casuali (come mescolare ingredienti in una ciotola) per creare il "ciphertext" (la valigia chiusa a chiave). Per sbloccarla, il tuo amico sottrae gli stessi numeri casuali. Poiché l'operazione matematica viene fatta nella specifica "base" di ogni slot (mod 26, mod 3, mod 2), il messaggio emerge perfettamente.

La Grande Scoperta: Questo Rende la Chiave Più Corta?

L'autore pone una domanda molto invitante: "Se manteniamo segrete le dimensioni degli slot (le basi), possiamo usare una chiave più corta?"

Immagina di dire al tuo amico: "Sto usando una valigia con uno slot da 26, uno da 3 e uno da 2", ma non dici loro quale slot è quale. Magari li scambi tra loro? La speranza era che questa disposizione segreta potesse permetterti di usare una chiave più piccola.

Il documento dimostra che questo è impossibile.
L'autore mostra che, affinché la serratura sia matematicamente inattaccabile (segretezza perfetta), i numeri casuali (la chiave) devono comunque coprire ogni singola possibilità in ogni slot.

L'Analogia: Immagina di cercare di nascondere una carta specifica in un mazzo. Se mescoli il mazzo (il messaggio) e poi distribuisci una carta casuale (la chiave) per coprirla, la carta che distribuisci deve poter essere qualsiasi carta del mazzo. Se provi a usare un mazzo di chiavi più piccolo, la matematica si rompe e il segreto trapela.
Il Risultato: Anche se nascondi le "regole" della valigia (le basi), la chiave deve comunque essere lunga e casuale quanto il messaggio stesso. Non puoi imbrogliare le leggi della teoria dell'informazione per ottenere una chiave più corta.

Il Vero Vantaggio: L'Efficienza, Non la Magia

Quindi, se la chiave non è più corta, perché usare questo nuovo sistema? L'articolo sostiene che si tratti di efficienza e adattabilità, non di magia.

Imballaggio Naturale: Se stai inviando dati del DNA (4 lettere: A, C, T, G), non hai bisogno di forzarli nel binario (0 e 1). Puoi semplicemente usare uno slot "base-4". Si adatta ai dati naturalmente, come inserire un incastro tondo in un buco tondo invece che in uno quadrato.
Rotolo di Chiavi (Key Rolling): L'articolo suggerisce un protocollo in cui Alice e Bob condividono un enorme "rotolo" di chiavi. Per il primo messaggio, usano un set specifico di basi (ad esempio, per il testo). Per il messaggio successivo, srotolano una nuova sezione della chiave che definisce un set di basi diverso (ad esempio, per i numeri).
- Regola Cruciale: Non riutilizzano mai la stessa parte del rotolo di chiavi. Questo mantiene la sicurezza perfetta pur permettendo loro di cambiare formato al volo.

Cosa Significa (e Cosa Non Significa)

Cosa È: È un modo formale e matematicamente provato per usare il One-Time Pad su dati che non sono solo binari. Conferma che il vecchio OTP binario è solo un caso speciale di questo nuovo sistema più flessibile.
Cosa NON È: Non è un modo per infrangere la regola che "La lunghezza della chiave deve essere almeno la lunghezza del messaggio". Non offre un "pasto gratis" dove puoi usare una chiave minuscola per bloccare un messaggio enorme.
La Domanda Aperta: L'articolo ammette che, sebbene la matematica sia perfetta, rimane una questione pratica non ancora risposta: se un attaccante non conosce le "basi" (le dimensioni degli slot), è abbastanza difficile per lui indovinare la combinazione giusta per violare il codice? L'articolo lascia questo come un mistero per ricerche future.

Riassunto

Il Mixed-Radix One-Time Pad è come passare da un rigido contenitore di spedizione di dimensione unica a un set di casse modulari di dimensioni personalizzate. Ti permette di imballare diversi tipi di dati in modo più naturale e di cambiare formato facilmente. Tuttavia, l'articolo afferma fermamente che la sicurezza costa lo stesso: hai comunque bisogno di una chiave lunga e casuale quanto il messaggio stesso. Guadagni flessibilità, ma non ottieni una scorciatoia verso la segretezza perfetta.

Sintesi Tecnica: Il One-Time Pad a Base Mista (MR-OTP)

Enunciato del Problema
Il documento affronta la rappresentazione e la cifratura dei dati utilizzando basi non uniformi (sistemi numerici a base mista). Mentre un preprint del 2012 aveva introdotto un cifrario basato sulla decomposizione degli interi tramite divisori decrescenti, esso rimaneva uno schizzo non sviluppato con vincoli analitici goffi. Il problema centrale è quello di formalizzare questo concetto in un primitivo crittografico rigoroso che generalizzi il classico One-Time Pad (OTP) a basi miste, determinando al contempo se l'uso di basi segrete possa ridurre i requisiti informativi della chiave per la segretezza perfetta.

Metodologia
L'autore formalizza la rappresentazione a base mista sottostante e definisce il One-Time Pad a Base Mista (MR-OTP).

Rappresentazione: Un messaggio $M$ è trattato come una tupla di cifre $(m_1, \dots, m_L)$ all'interno di uno spazio di cifre definito da una sequenza di basi $B = (b_1, \dots, b_L)$ , dove ogni $b_i \ge 2$ . Il messaggio corrisponde a un intero tramite pesi posizionali derivati dal prodotto delle basi successive.
Cifratura: Il cifrario opera cifra per cifra. Data una chiave $K = (k_1, \dots, k_L)$ estratta uniformemente a caso dallo spazio delle chiavi, la cifratura viene eseguita come $c_i = (m_i + k_i) \mod b_i$ .
Decifratura: L'operazione inversa è $m_i = (c_i - k_i) \mod b_i$ .
Analisi: Il documento impiega la definizione di Shannon di segretezza perfetta, utilizzando la regola di Bayes per analizzare la probabilità condizionata dei messaggi dati i testi cifrati. Esamina inoltre l'entropia dello spazio delle chiavi quando le basi sono trattate come segrete rispetto a quando le basi sono fisse.

Contributi Chiave

Formalizzazione di MR-OTP: Il documento definisce l'MR-OTP come l'estensione naturale dell'OTP ai sistemi a base mista, sostituendo l'XOR bit a bit con l'addizione modulo $b_i$ cifra per cifra.
Dimostrazione di Segretezza Perfetta e Correttezza:
- Correttezza: Dimostrata mostrando che la mappa di cifratura è una biiezione sul gruppo ciclico finito $\mathbb{Z}_{b_i}$ per ogni posizione.
- Segretezza Perfetta: Dimostrata dimostrando che, per una chiave uniformemente casuale, la probabilità di un testo cifrato $c$ dato un messaggio $m$ è indipendente da $m$ . Di conseguenza, la probabilità a posteriori del messaggio dato il testo cifrato è uguale alla probabilità a priori.
Generalizzazione degli OTP Classici: Il documento stabilisce che il classico OTP binario è il caso specifico in cui tutti $b_i = 2$ , e le varianti a base fissa recuperano gli OTP su alfabeti arbitrari (ad esempio, base 26 per il testo latino).
Risoluzione della Congettura della "Chiave Breve": Il documento indaga l'ipotesi che trattare le basi $B$ $B$ come parte della chiave segreta potrebbe permettere al pad additivo $k$ $k$ di essere più breve del messaggio pur mantenendo la segretezza perfetta. Dimostra che ciò è falso.
- Ragionamento: La segretezza perfetta richiede che il pad additivo $k$ sia distribuito uniformemente su l'intero insieme $\{0, \dots, b_i-1\}$ per ogni posizione. Se il pad viene accorciato (ovvero non copre l'intera entropia dello spazio dei messaggi), la probabilità condizionata $P[C|M]$ diventa dipendente da $M$ , rompendo la segretezza perfetta. L'entropia delle basi segrete $H(B)$ si aggiunge all'entropia totale della chiave ma non può sostituire l'entropia richiesta per il pad additivo.
Protocollo di Sessione con Rotazione della Chiave: Viene proposto un protocollo pratico in cui una chiave iniziale condivisa viene partizionata in segmenti disgiunti. Ogni sessione utilizza un nuovo segmento per il pad additivo e un nuovo segmento per definire le basi per la sessione successiva. Ciò preserva la segretezza perfetta consentendo alle basi di adattarsi alla struttura dei dati (ad esempio, corrispondendo alla base 26 per il testo) per l'efficienza della codifica, senza ridurre il materiale di chiave totale consumato.

Risultati

Limiti Teorici: L'MR-OTP soddisfa il limite di Shannon $|K| \ge |M|$ . Lo spazio delle chiavi e lo spazio dei messaggi coincidono ( $K = D_B = M$ ), garantendo che non venga sprecato alcun materiale di chiave.
Contabilità dell'Entropia: L'entropia totale della chiave richiesta è $H(K) = H(B) + H(k|B)$ . Poiché è richiesto che $H(k|B) \ge H(M)$ per la segretezza perfetta, l'inclusione di basi segrete aumenta strettamente il requisito di entropia della chiave totale piuttosto che ridurlo.
Overhead: Nel protocollo di sessione proposto, l'overhead della trasmissione delle basi è trascurabile quando la dimensione media della base è grande rispetto ai bit necessari per rappresentare la base stessa. Nel caso degenero delle basi binarie ( $b_i=2$ ), l'overhead è uguale alla lunghezza del pad, offrendo nessun guadagno di rappresentazione rispetto allo standard OTP binario.

Significatività e Rivendicazioni
Il documento sostiene di fornire una "generalizzazione pulita" dell'OTP che collega la teoria dei gruppi algebrici (OTP su gruppi abeliani finiti) con i sistemi numerici. La sua importanza primaria risiede nella:

Chiarificazione: Formalizza rigorosamente un concetto precedentemente vago, rimuovendo i "vincoli laterali" dello schizzo originale del 2012.
Confutazione di un Equivoco: Smentisce esplicitamente l'idea che le basi segrete possano abbassare il requisito di chiave informatico-teorica per la segretezza perfetta, chiarendo che tale riduzione violerebbe l'ipotesi di uniformità essenziale per la prova di Shannon.
Utilità Pratica: Posiziona la struttura a base mista non come un metodo di compressione della chiave, ma come uno strumento di efficienza e adattività della codifica. Adattando le basi all'alfabeto della sorgente (ad esempio, DNA o testo), il sistema evita conversioni binarie artificiali e padding, rendendo l'OTP più efficiente nella rappresentazione pur mantenendo una rigorosa sicurezza informatico-teorica.

Il documento conclude identificando problemi aperti riguardanti la durezza del caso medio nel recupero delle basi segrete e la selezione ottimale delle basi per sorgenti strutturate, osservando che la sicurezza della selezione delle basi rimane una questione computazionale piuttosto che informatico-teorica.