C'è uno pseudo messaggio che verrà crittografato e decrittografato correttamente se uno dei numeri primi è uno pseudo primo in RSA
Per la generazione di numeri primi, si può usare un algoritmo probabilistico di generazione di numeri primi come il test di primalità di Miller-Rabin che produrrà un composto come un primo probabile con probabilità$\frac{1}{4^r}$ per $r$turni. Se usiamo$r=50$, questo ha probabilità $2^{-100}$. Questo è sufficiente per credere che sia primo a causa dell'elevata probabilità, se il potere collettivo dei minatori di Bitcoin non sta cercando un candidato, non ne vedremo uno in giro.
E se volessimo assicurarci che sia al 100%? Possiamo usare il test deterministico di primalità AKS e le sue varianti più veloci per vedere che è primo o era uno pseudoprime per Miller-Rabin. Il test di primalità AKS, tuttavia, è molto lento ed è per questo che utilizziamo metodi probabilistici.
Ora, invece di AKS, vogliamo un approccio più veloce e utilizzarlo nel sistema crittografico RSA per crittografare e decrittografare un messaggio. Se tutto funziona, supporremo che sia primo (dovremmo?) !
Prendi un numero primo noto come lo chiamano i numeri primi di Fermat o Mersenne$p$ e lo pseudo primo (uno vero può essere trovato se usiamo meno round ma supponiamo di averne trovato uno con 50 round) e lo chiamiamo $\bar{p}$. Costruisci l'RSA come al solito con l'eccezione che invece di scegliere in primo luogo$e$ quindi trovare i numeri primi, scegli uno adatto $e$.
- $n = p \cdot\bar{p}$
- $\varphi{(n)} = (p-1)(\bar{p}-1)$, (in realtà possiamo usare $\lambda{(n)}$)
- trova $e$ tale che $\gcd(e, \varphi(n)) = 1$
- trova $d \equiv e^{-1} \pmod{\varphi(n)}$
e il resto è crittografia e decrittografia RSA da manuale.
Domande):
- Ci aspettiamo che la crittografia fallisca poiché il file $\varphi(n)$. Esiste uno pseudomessaggio che crittografa e decrittografa correttamente con questo pseudoprime$\bar{p}$?
- Se sì, come possiamo trovarne uno?
- In tal caso, qual è la probabilità degli pseudo messaggi?
Risposte
- Ci aspettiamo che la crittografia fallisca poiché il file $\varphi(n)$.
Non sempre; per esempio, considera il caso$p=31$ (un primo di Mersenne) e $\bar{p} = 561 = 3 \times 11 \times 17$. Ci metteremo$e = 13$ e $d = e^{-1} \bmod 30 \times 560 = 3877$.
Quindi, se scegliamo un messaggio casuale $m=2$, poi $2^e \bmod n = 8192$, e $8192^{3877} \bmod n = 2$; la crittografia e la decrittografia funzionano perfettamente. In realtà, si scopre che qualsiasi valore$m$ crittograferà e decifrerà correttamente con questo particolare $n, e, d$ impostato.
Riproviamo con un altro esempio casuale; questa volta sceglieremo un numero primo di Fermat$p=17$ e un arbitrario $\bar{p} = 91 = 7 \times 13$, e così $n= 1547$. Questa volta useremo$\lambda(n) = (p-1)(\bar{p}-1) / \gcd( p-1, \bar{p}-1 )= 720$; sceglieremo$e=7$ e così $d=e^{-1} \bmod \lambda(n) = 103$. Di nuovo, se scegliamo un messaggio casuale (proveremo$m=3$ questa volta, abbiamo $3^e \bmod n = 640$ e $640^d \bmod n = 3$. E, ancora, qualsiasi$m$ crittograferà e decifrerà correttamente con questo particolare $n, e, d$ impostato.
Allora, come ha funzionato? Ho scelto questi esempi a caso? È sempre vero per i numeri primi di Fermat e Mersenne? Beh, no, per questo trucco, ho selezionato il mio$\hat{p}$ valuta attentamente e quasi tutto il resto era arbitrario.
Nel primo caso, ho selezionato $\hat{p}$ essere un numero di Carmichael, cioè un numero composto tale che $\lambda(\hat{p})$ è un fattore di $\hat{p}-1$. Si scopre che un numero di Carmichael si comporta proprio come un numero primo per quanto riguarda RSA; qualunque$p$ (relativamente primo a $\hat{p}$ lo farebbe funzionare).
Nel secondo caso, ho selezionato un file $\hat{p}$quello non era un numero Carmichael (561 sembra essere il più piccolo), ma invece è qualcosa che potremmo chiamare un "numero semicarmichael" (terminologia che ho appena inventato, quindi non preoccuparti di cercarlo su Google); ha la proprietà che$\lambda(\hat{p})$ è un fattore di $2(\hat{p}-1)$. Ora, questi numeri non funzioneranno sempre all'interno di RSA, tuttavia funzionano anche se entrambi$p \equiv 1 \bmod 2^{k+1}$ (dove $2^k$ è la più grande potenza di 2 che è un divisore di $\hat{p}-1$), o in alternativa usi il file $\phi(n)$ relazione di $e, d$ (piuttosto che il $\lambda(n)$ relazione - per numeri primi e numeri di Carmichael, non importa - per numeri semicarmici, sì).
Quindi, che cosa si riferisce questo trucco magico alla tua domanda:
In tal caso, qual è la probabilità degli pseudo messaggi?
Più alto di quanto ti aspetteresti, se avessi fatto un numero di round di Fermat o Miller-Rabin in anticipo. Si scopre che i numeri di Carmichael ingannano sempre Fermat (a meno che non ti capiti di scegliere un generatore che non è relativamente primo rispetto al numero di Carmichael), e i numeri semicarmichael ingannano Fermat per metà del tempo. Ed entrambi questi numeri hanno buone probabilità di ingannare Miller-Rabin (ovviamente$< 1/4$, tuttavia a volte non molto di meno). Quindi, mentre i numeri di Carmichael e Semicarmichael sono rari, se si dispone di un numero composto che inganna diversi round di Fermat o MR, la probabilità di iniziare con un tale numero è piuttosto buona.
Presumo $\gcd(p,\bar p)=1$ (che è probabilmente casuale $p$e facilmente verificabile). Pertanto, per CRT , un messaggio$m$ con $0\le m<n$ crittografa / decrittografa correttamente se e solo se $m^{e\,d}\equiv m\pmod p\tag{1}\label{fgr1}$ e $m^{e\,d}\equiv m \pmod{\bar p}\tag{2}\label{fgr2}$.
Dalla costruzione di $e$ e $d$, Tiene $e\,d=i\,(p-1)+1$ e $e\,d=j\,(\bar p-1)+1$ per un numero intero $i$ e $j$. Per FLT , proprio come in RSA, il primo lo implica$\eqref{fgr1}$ vale per tutti i numeri interi $m$.
Definisci il set $\mathcal V$ essere il sottoinsieme di $[0,\bar p)$ quali elementi $m$ soddisfare $\eqref{fgr2}$. Questo set$\mathcal V$ dipende da $\bar p$, e in una certa misura può dipendere da $e\,d$, così via $e$ e su come $d$ è selezionato.
Secondo la solita formula CRT in RSA, il set $\mathcal M$ di messaggio $m$ con $0\le m<n$ che crittografare / decrittografare correttamente è precisamente l'insieme di $m=((\bar p^{-1}\bmod p)(u-v)\bmod p)\,\bar p+v\tag{3}\label{fgr3}$ per tutti $(u,v)\in[0,p)\times\mathcal V$. Invece di$\eqref{fgr3}$ potremmo anche usare $m=((p^{-1}\bmod \bar p)(v-u)\bmod\bar p)\,p+u\tag{4}\label{fgr4}$.
Questo dice $|\mathcal M|$ è un multiplo di $p$. E la probabilità di prenderne uno a caso$m$ è precisamente $\mu=|\mathcal V|/\bar p\tag{5}\label{fgr5}$.
Da $\{0,1,\bar p-1\}\subset\mathcal V$, Tiene $|\mathcal M|\ge3\,p$, e $\mu\ge2/\bar p$.
Quindi possiamo rispondere alla domanda 1 e 1.1: sì, ci sono messaggi che crittografano e decrittano correttamente, e ne abbiamo mostrati alcuni. Finora, irrimediabilmente pochi. Ma questo è prima che lo invocassimo$\bar p$ è uno pseudoprime!
Definisci il set $\mathcal W$ essere il sottoinsieme di $[0,\bar p)$ quali elementi $w$ soddisfare $w^{p-1}\equiv1\pmod n$; cioè basi$w$ fabbricazione $\bar p$uno pseudoprime di Fermat . Tiene$(\mathcal W\cup\{0\})\subset\mathcal V$, e $\{1,\bar p-1\}\subset\mathcal W$.
Gli pseudoprimi più forti sono i numeri di Carmichael A002997 . quando$\bar p$ è uno di questi, $\mathcal W=\mathbb Z_\bar p^*$, e quindi è la maggior parte di $[1,\bar p)$, così $\mu$ è vicino a $1$.
Senza prove, osservo $\mu=1$ quando $\bar p$è un numero di Carmichael (che sono estremamente rari, anche tra gli pseudoprimi), e poi alcuni altri pseudoprimi, inclusi alcuni pseudoprimi Fermat in base 2 A001567 (ad es.$\bar p=997633$); e quello$\mu$ è considerevole per più classi di pseudoprimi.
Quindi possiamo rispondere alla domanda 1.2 con: esistono pseudoprime $\bar p$ fabbricazione $\mu=1$, e altro ancora rendendolo un valore non estraneo.