Perché RSA utilizza numeri di tipo a virgola fissa?

-1

Perché RSA usa numeri a virgola fissa invece di virgola mobile? Esistono troppe implementazioni in virgola mobile tra cui scegliere? L'aritmetica a punto fisso aumenta la difficoltà di fattorizzazione? O è qualcos'altro?

La complessità extra del floating-point non aumenterebbe la sicurezza dell'algoritmo?

    
posta muma 02.05.2013 - 14:18
fonte

2 risposte

4

Why is RSA using fixed point type numbers?

Tecnicamente parlando, RSA opera su classi di residui che sono classi di equivalenza, con la definizione "due interi sono equivalenti "essere" condividono lo stesso resto ".

Queste classi sono popolate solo da numeri interi, quindi l'operazione RSA non ha bisogno di tipi di archiviazione in virgola mobile. In quanto tale, non ha senso sprecare spazio nell'ordinare un esponente, in quanto non è necessario - anche i grandi numeri interi possono essere archiviati in memoria usando una libreria aritmetica di precisione arbitraria - se per esempio si divide il numero intero in blocchi di 32 bit, o quattro byte, sono necessari solo 128 blocchi da 4 byte per memorizzare tale numero intero o 512 byte.

Is it because only the fixed point arithmetics provide the difficulties of factorization?

La fattorizzazione diventa più complicata quando inizi a definire altri set. Ad esempio, in alcune costruzioni un numero può essere irriducibile, ma non primo.

Dato che RSA funziona molto bene con il più semplice degli insiemi che conosciamo e comprendiamo, i numeri interi, non ha molto senso introdurre ulteriori complessità a meno che non ne abbiamo bisogno.

    
risposta data 02.05.2013 - 14:23
fonte
3

I numeri in virgola mobile sono un'approssimazione di numeri reali. Sono appropriati per i calcoli continuous , in cui una piccola variazione dell'input produce una piccola variazione dell'output.

La crittografia generalmente comporta calcoli che arrivano al punto in cui arriva da continuo. Non importa quanto siano simili due messaggi non identici, non dovrebbero avere hash simili, firme simili o crittografie simili. I virgola mobile sono del tutto inappropriati per questo.

La crittografia spesso implica una sorta di scrambling dall'aspetto irreversibile, che può essere annullato solo in presenza di una chiave segreta (o non del tutto). I processi naturali tendono ad essere continui, quindi reversibili. I processi caotici , il cui passato non può essere calcolato, tendono a coinvolgere interi in qualche punto - spesso un numero di iterazioni o cicli, dove una soglia viene colpita o persa ad ogni iterazione. I numeri interi sono il modo in cui sorge l'irreversibilità.

Il risultato delle operazioni crittografiche deve essere riproducibile. Ad esempio, il processo di decrittografia deve invertire esattamente il processo di crittografia. I numeri in virgola mobile sono svantaggiati perché le operazioni su di essi tendono ad avere variazioni tra le diverse architetture del processore.

Gran parte della crittografia, inclusa la RSA, si basa su proprietà "belle" di numeri interi, spesso legate alla divisibilità (che è fondamentalmente una proprietà di numeri interi). I numeri in virgola mobile non hanno tali proprietà che fanno funzionare gli algoritmi.

La complessità non è ciò che rende sicuri gli algoritmi crittografici. È una combinazione di proprietà matematiche e nessuno ha trovato un modo per romperle. Non c'è assolutamente nulla da guadagnare con i calcoli in virgola mobile lì, e come abbiamo visto molto da perdere.

    
risposta data 03.05.2013 - 01:42
fonte

Leggi altre domande sui tag