RSA è un algoritmo lento, specialmente per la decrittazione. Devi calcolare m = c^d mod N
dove d è approssimativamente la dimensione del modulo. Per RSA-1024/2048/4096 (dove 1024/2048/4096 è il numero di byte del modulo N), anche con l'esponenziazione modulare rapida mediante squadratura ripetuta richiede circa 1,5 lg N (~ 1500 / ~ 3000 / ~ 6000) moltiplicazioni di numeri interi a N bit. La moltiplicazione di un intero N-bit non è un'operazione primitiva ma scala come O (N ^ 1.6) per un numero intero di n bit (quindi ogni moltiplicazione è approssimativamente 84/256/776 volte più lenta di una primitiva di moltiplicazione a 64 bit).
Nota: la crittografia RSA è significativamente più veloce della decrittografia poiché con il padding corretto non c'è debolezza nella scelta di un esponente di chiave pubblica piccola come e = 65537 dove il tuo step di esponenziazione richiede solo ~ 17 moltiplicazioni; infatti e = 3 richiedendo solo due moltiplicazioni funzionerebbe perfettamente bene con un'adeguata imbottitura.
Inoltre, un'applicazione di b-bit RSA che significa che dovevi generare due numeri primi di una lunghezza approssimativa ciascuno) può decrittografare un messaggio fino a circa b-128 bit (usando un pad casuale di 128 bit) o circa 112 / 240/496 byte poiché decodifichi univocamente un numero compreso tra 0 e N. Questa risposta con codifica ASCII a 8 bit richiede 7449 byte.
Pertanto, ciò che accade di solito è crittografare una chiave simmetrica poiché la chiave simmetrica sarà molto più veloce e l'utilizzo di una modalità di crittografia (ad es. CBC, CTR) può crittografare messaggi di dimensioni arbitrarie.
Informazioni sul tempo per giustificare l'analisi precedente
Ho creato casualmente una coppia di chiavi RSA a 4096 bit (N, e) e (N, d) (usando import rsa; rsa.newkeys(nbits=4096)
) e poi ho eseguito il tempo per confrontare "libro di testo" (debole - senza byte casuali imbottiti) crittografia / decifratura RSA alla crittografia AES.
L'impostazione per la temporizzazione RSA è fornita sotto crittografia / decrittografia:
>>> encryption = "pow(m,e,N)"
>>> decryption = "pow(c,d,N)"
>>> setup = """N = 650022002033202164791638561174816123258916492020045683486079596172818033518252144860009135975860423604411399274822133841546708494765449009472683563317182198759309684914356008659922538583279515419473227210977474088638850782595732910857797571156318425669817244314450827318145758475770172116229990603884173470104902799641093008914867436680133631971559712828465243806241512864086546090728020169682901285441149037545107765998640217114788723715575098893307499744794060936075307573516246976128444578474543743151813381476261995022381469996299316134038828450334308951123635607639233510908350391842701316709834010335732144351192249236953330927673972067894385163240378028762678952835544528074929660347162229394149982403274141710996800529609644247153732931740566379474447028470447165473543764460712691302632667942726305345440613110797535733482536487121364569032950159436896042439632454394173272272373593467791776848612054118558722637286863035388661691125609333937871344046274188817824229897604542696165894703693345718292207375417809743565484488696015562272970275127353631067240331072960179800283770558952793368549384848991363395614092594834723746484679602433778811932755737361396956451757817273043140309312219744371338360280947729616063853738641
e = 65537
d = 163256819101675505935126275492278764497028632049833711493978518287449606050176698725845711249563797130302144316394896364372168726426893063398086141449880510117616574052677112204439095245140620165777031598832556014144612720776443287192263118867708337069520909431555619232749121633751575949969416441703671137188560661642925231956585104715733090960096935672315454064890600755952584778878850298197667808388563912873529057301030226798746088352508752731797937742028323588321094384242144517250929974849184277771012531228150089843422784017258750683831715157735366668225506845014904307329056055723208632277201486994123654288753880392020556964543443597828229493325467616467308118864809565200248599428162198788308364968380312577988297310500286974136209331121821893719017982045957945241683426015912952303440579610553088057331105677592306795472995839704525934407019706992740653789223747419222232691256397983243926154436341276701812083801394467756814989897357722664273229362826815661611670740504736110949984419908621950792127278167263015929591331285519955311164883226113070661776218890597216617564529563317568347817244502395174702566462626236588608296425638109493962233171124725237010153412040065506840529586822535766472003407847003802265141256193
m= int("This is a secret message provided as a test for RSA-4096 and AES encryption. To be fair it is 496 bytes long. Keyboard mashing follows: asdbklajsdgl;sdjgl;kasjdgiowepgj opijg aslekgjase;lgk jasel; elask;gj lask;lgjl;ske gjasle;k asel;k gjl;asekgj asljsel;k jseal; gkjasel; kjsael;kjg aal;se asegkl;j asel;kjasegl;k jasegl;k jasel;gk jasegl;k jasel gkjsael;gkjasel;gkj sea;lekgjseal;kjasegl;asekgjasel;kgjsael;jkasel;gjkgasel;asfasfl;kjasf;lkjsadfkljdl;kfaskl;jfasldk;fkfkjl;akasdfasdfasdfkjkjga".encode('hex'),16)
c = pow(m, e, N)
"""
>>> import timeit
>>> timeit.repeat(encryption, setup=setup, repeat=3, number=1)
[0.0044488906860351562, 0.0045480728149414062, 0.0044538974761962891]
>>> timeit.timeit(decryption, setup=setup, repeat=3, number=1)
[1.9231810569763184, 1.9048171043395996, 1.9280149936676025]
La crittografia RSA a 4096 bit impiega ~ 4,5 ms per esecuzione e la decifrazione dura 1,9 secondi (~ 500 volte più lenta della crittografia poiché d è molto più grande di e). La crittografia di questo messaggio con RSA richiede 16 blocchi e richiede circa 30 secondi per decrittografare. Ripetendo per altre dimensioni RSA, ho trovato 1024 bit RSA richiede ~ 0,5 ms per la crittografia e 40 ms per la decrittografia. RSA a 2048 bit prende ~ 1,6 ms per la crittografia e ~ 270 ms per la decrittografia.
Ora diamo un'occhiata ad AES-128, usando la libreria pycrypto.
setup = """
from Crypto.Cipher import AES
from Crypto import Random
from hashlib import sha256
def aes_encrypt(plaintext, key):
block_size = AES.block_size
iv = Random.new().read(block_size)
cipher = AES.new(key, AES.MODE_CBC, iv)
pad_len = block_size - (len(plaintext) % block_size)
padding = ''.join([chr(pad_len)]*pad_len)
encrypted_msg = iv + cipher.encrypt(plaintext + padding)
return encrypted_msg
def aes_decrypt(encrypted_msg, key):
block_size = AES.block_size
iv = encrypted_msg[:block_size]
cipher = AES.new(key, AES.MODE_CBC, iv)
padded_msg = cipher.decrypt(encrypted_msg[block_size:])
pad_len = ord(padded_msg[-1])
msg = padded_msg[:len(padded_msg)-pad_len]
return msg
key = sha256("secret passphrase").digest()[0:16]
message = "This is a secret message provided as a test for RSA-4096 and AES encryption. To be fair it is 496 bytes long. Keyboard mashing follows: asdbklajsdgl;sdjgl;kasjdgiowepgj opijg aslekgjase;lgk jasel; elask;gj lask;lgjl;ske gjasle;k asel;k gjl;asekgj asljsel;k jseal; gkjasel; kjsael;kjg aal;se asegkl;j asel;kjasegl;k jasegl;k jasel;gk jasegl;k jasel gkjsael;gkjasel;gkj sea;lekgjseal;kjasegl;asekgjasel;kgjsael;jkasel;gjkgasel;asfasfl;kjasf;lkjsadfkljdl;kfaskl;jfasldk;fkfkjl;akasdfasdfasdfkjkjga"
cipher = aes_encrypt(message,key)
"""
>>> timeit.repeat("aes_encrypt(message,key)", setup=setup, repeat=3, number=1)
[6.198883056640625e-05, 6.198883056640625e-05, 6.008148193359375e-05]
>>> timeit.repeat("aes_decrypt(cipher,key)", setup=setup, repeat=3, number=1)
[1.0967254638671875e-05, 9.059906005859375e-06, 9.059906005859375e-06]
Bottomline , la crittografia AES è approssimativamente 8/25/500 volte più veloce di RSA e la decrittografia AES riguarda circa 4000/25000/200000 volte più veloce di RSA (con crittografia 1024/2048/4096 bit rispettivamente). Quindi, la crittografia ibrida ha sempre senso ogni volta che è necessario più di un blocco.