Criptiú RSA. Cur síos agus cur i bhfeidhm algartam an RSA

Is é criptiú RSA ar cheann de na chéad chriptitheacha praiticiúla le heochair phoiblí, a úsáidtear go forleathan le haghaidh tarchur sonraí slán. Is é a phríomhshifríocht ó sheirbhísí den chineál céanna go bhfuil an t-eochair criptithe oscailte agus difriúil ón eochair díchriptithe, a choimeádtar rúnda. Tá an teicneolaíocht RSA , an neamhshiméadracht bunaithe ar an deacracht praiticiúil fachtóireacht an athsheinm de dhá uimhir phríomha mór (fadhb na fachtóireacht).

Stair na cruthú

RSA t-ainm is éard atá túslitreacha na sloinnte Rivest, Shamir agus Adleman - na heolaithe a chéad cur síos ar go poiblí na halgartaim criptithe i 1977. D'fhorbair Clifford Cox, matamaiticeoir Béarla a d'oibrigh do sheirbhísí rúnda na Breataine, córas comhionann i 1973, ach níor díghlasadh é go dtí 1997.

Cruthaíonn úsáideoir an RSA eochair phoiblí agus ansin foilsíonn sé dhá phríomhshuim chomh maith le luach cúnta. uimhreacha príomha ba chóir a choinneáil faoi rún. Is féidir le duine ar bith eochair phoiblí a úsáid chun teachtaireacht a chriptiú, ach má tá sé mór go leor, ní féidir ach duine éigin a bhfuil eolas acu ar phríomh-uimhreacha an teachtaireacht a dhíchódú. Is é an fhadhb is mó a thugtar ar nochtadh criptithe RSA: inniu tá plé oscailte ann faoi cé chomh iontaofa atá an meicníocht seo.

Is RSA algartam sách mall, a chúis nach bhfuil sé in úsáid chomh forleathan agus chun go díreach chriptiú úsáideoir. Is minic a úsáidtear an modh seo chun eochracha roinnte criptithe a sheoladh le haghaidh eochair criptithe siméadrach, a fhéadfaidh, ar a seal, oibríochtaí criptithe maisithe agus díchríofa a dhéanamh ar luas i bhfad níos airde.

Cathain a léirigh an criptheóras sa bhfoirm nua-aimseartha?

Tugtar an smaoineamh ar eochair neamhchríochnaitheach criptighchórais do Diffie agus Hellman, a d'fhoilsigh an coincheap i 1976, ag cur sínithe digiteacha i láthair agus ag iarraidh teoiric na n-uimhreacha a chur i bhfeidhm. Úsáideann a bhfoirmiú eochair rúnda coiteann, a cruthaíodh ó nochtadh uimhir mhodúl ar phríomh-uimhir. D'fhág siad, áfach, an fhadhb a bhaineann le feidhmiú an fheidhm seo a oscailt, ós rud é nach tuigtear go maith le prionsabail an fhachtóra ag an am sin.

Rinne Rivest, Adi Shamir agus Adleman ag Institiúid Teicneolaíochta Massachusetts roinnt iarrachtaí i rith na bliana chun feidhm unidirectional a chruthú atá deacair a dhíchódú. Rinne Rivest agus Shamir (mar eolaithe ríomhaireachta) go leor feidhmeanna féideartha, agus d'fhéach Adleman (mar matamaiticeoir) "laigí" an algartam. Bhain siad úsáid as go leor cur chuige agus sa deireadh i mí Aibreáin 1977 d'fhorbair an córas ar a dtugtar an RSA inniu.

EDS agus eochair phoiblí

Is cuid dhílis de dhoiciméid leictreonacha é síniú digiteach leictreonach, nó EDS. Tá sé déanta le hathrú cripteagrafach áirithe sna sonraí. Le cabhair ón tréith seo, is féidir seiceáil a dhéanamh ar ionracas an doiciméid, ar a rúndacht, agus chun a chinneadh cé leis féin é. Go deimhin, is rogha eile é seo don ghnáth-shíniú caighdeánach.

Tairgeann an criptchóras seo (criptiú RSA) eochair phoiblí, seachas difriúil ó na cinn siméadracha. Is é prionsabal a fheidhmiú ná go n-úsáidtear dhá eochracha difriúla - dúnta (criptithe), agus a oscailt freisin. Úsáidtear an chéad cheann le EDS a ghiniúint agus faigheann sé an deis an téacs a dhíchódú ina dhiaidh sin. Tá an dara ceann maidir le criptiú agus fíorú iarbhír an EDS.

Is féidir le húsáid an tsínithe criptiú RSA a thuiscint níos fearr, ar a dtugtar sampla de ghnáth mar ghnáth-aicme "dúnta ó shúile prying".

Cad é croílár an algartaim?

Tá ceithre chéim ag algartam an RSA: giniúint eochracha, a ndáileadh, a chriptiú agus a dhíchriptiú. Mar a luadh cheana, cuimsíonn criptiú RSA eochair phoiblí agus eochair phríobháideach. Is féidir le gach duine a bheith ar oscailt agus is féidir úsáid a bhaint as teachtaireachtaí a chriptiú. Is é croílár na teachtaireachtaí sin nach féidir teachtaireachtaí atá criptithe le heochair phoiblí a dhíchriptiú ach i dtréimhse áirithe ama ag baint úsáide as eochair phríobháideach.

Ar chúiseanna slándála, ba cheart slánuimhreacha a roghnú go randamach agus a bheith mar an gcéanna i méid, ach difriúil le cúpla dhigit ionas go ndéanfaí fachtóirí níos deacra. Is féidir na huimhreacha céanna a fháil go héifeachtach ag baint úsáide as tástáil as a gcuid simplíochta, agus mar sin ní mór go mbeadh gá le criptiú faisnéise níos casta.

Is éard atá sa eochair phoiblí ná modúl agus exponent poiblí. Is éard atá sa dúnta modúl agus táscaire príobháideach, agus ní mór a choinneáil rúnda.

Comhaid RSA agus pointí lag a chryptáil

Mar sin féin, tá roinnt meicníochtaí ann chun RSA simplí a dhéanamh. Nuair atá tú ag clárú le scóir íseal agus luachanna beaga uimhreacha, is féidir an sreang a oscailt go héasca má roghnaíonn tú an fhréamh ciphertext thar slánuimhreacha.

Ós rud é go bhfuil criptiú RSA ina algartam determinista (is é sin, níl comhpháirt randamach aige), is féidir le hionsaitheoir an téacs ionsaí oscailte roghnaithe a reáchtáil go rathúil i gcoinne an chreasaighchórais trí théacsanna oscailte is dócha a eisiúint faoi eochair phoiblí agus seiceáil a fháil amach an bhfuil siad comhionann le ciphertext. Deirtear go bhfuil criptheóras sách leathnach i gcás nach féidir le hionsaitheoir idirdhealú a dhéanamh ar dhá ionchódú dá chéile, fiú má tá a fhios aige na téacsanna comhfhreagracha i bhfoirm leathnaithe. De réir mar a thuairiscítear thuas, níl an RSA gan seirbhísí eile a chur ar fáil i gcónaí go sásúil.

Algartam breise le haghaidh criptithe agus cosanta

Chun na fadhbanna thuas a sheachaint, i gcur i bhfeidhm praiticiúil an RSA, tógtar cineál éigin de líonadh struchtúrtha, randamach de ghnáth roimh chriptiú. Cinntíonn sé seo nach dtagann an t-ábhar laistigh de raon na bpléiteas neamhshábháilte agus nach féidir an teachtaireacht seo a nochtadh trí roghnú randamach.

Tá slándáil criptheóras an RSA agus criptiú faisnéise bunaithe ar dhá fhadhb matamaitice: na fadhbanna a bhaineann le líon mór a dhéanamh agus fadhbanna iarbhír an RSA. Meastar go bhfuil nochtadh iomlán ciphertext agus síniú digiteach san RSA neamh-inghlactha ar an toimhde nach féidir an dá fhadhb seo a réiteach sa chomhiomlán.

Mar gheall ar an gcumas imlitheoirí simplí a chur ar ais, áfach, is féidir le hionsaitheoir eochair rúnda a ríomh ó eochair phoiblí, agus ansin an téacs a dhíchriptiú ag baint úsáide as nós imeachta caighdeánach. In ainneoin an lae inniu nach bhfuarthas aon mhodh atá ann cheana chun líon mór a dhéanamh ar ríomhaire clasaiceach, níor dearbhaíodh nach bhfuil ann.

Uathoibriú

Is féidir uirlis a dtugtar Yafu a úsáid chun an próiseas seo a uasmhéadú. Is feidhm nua-aimseartha é uathoibriú i YAFU lena n-áirítear halgartaim fachtóirithe i modheolaíocht chliste agus oiriúnaitheach, rud a laghdaíonn an t-am chun fachtóirí a fháil ar uimhreacha ionchur treallach. An chuid is mó implementations multithreaded algartam ligean úsáid Yafu iomlán de il- nó go leor próiseálaithe il-lárnach (lena n-áirítear SNFS, SIQS agus ECM). Ar an gcéad dul síos, is uirlis líne ceannais é. Is féidir an t-am a chaitear ag cuardach fachtóir criptithe ag baint úsáide as Yafu ar ríomhaire traidisiúnta a laghdú go 103.1746 soicind. Déanann an uirlis an dénártha cumas 320 giotán nó níos mó. Bogearraí an-chasta é seo a éilíonn méid áirithe scileanna teicniúla a shuiteáil agus a chumrú. Dá bhrí sin, féadfaidh criptiú RSA C bheith leochaileach.

Iarrachtaí a bhriseadh isteach san am nua-aimseartha

Sa bhliain 2009, d'oibrigh Benjamin Moody, ag baint úsáide as an eochair RSA-512 giotán, ar dhíchriptiú an cripteagrafach ar feadh 73 lá, gan úsáid a bhaint as bogearraí aitheanta aitheanta (GGNFS) agus an meánchlár deisce (Athlon64 dé-lárnach ag 1900 MHz). Mar a thaispeántar leis an taithí seo, ghlac sé beagán níos lú ná 5 gigabytes de dhiosca agus thart ar 2.5 gigabytes RAM chun an próiseas "sifting" a dhéanamh.

Ó 2010, ba é 768 giotán an fad an líon RSA fachtóirithe is mó (232 dhigit déag, nó RSA-768). Mhair a nochtadh dhá bhliain ar roinnt céad ríomhairí ag an am.

Go praiticiúil, áfach, tá eochair RSA fada - de ghnáth ó 1024 go 4096 giotán. Creideann roinnt saineolaithe gur féidir le heochracha 1024-giotán a bheith neamhiontaofa go luath amach anseo nó is féidir le hionsaitheoir dea-mhaoinithe a bheith sciobtha cheana féin. Mar sin féin, déanfaidh cúpla argóint go bhféadfar eochracha 4096-giotán a nochtadh chomh fada agus is féidir.

Ionchais

Dá bhrí sin, glactar leis go ginearálta go bhfuil an RSA sábháilte má tá na huimhreacha mór go leor. Más rud é gurb é 300 giotán nó níos giorra ná an uimhir bhunúsach, is féidir an ciphertext agus an síniú digiteach a dhiúltú laistigh de chúpla uair an chloig ar ríomhaire pearsanta ag baint úsáide as bogearraí atá ar fáil cheana féin i bhfearann an phobail. D'fhéadfaí eochracha le fad 512 giotán, de réir mar a bhí cruthaithe, a oscailt i 1999 ag baint úsáide as roinnt céad ríomhairí. Is féidir le roinnt seachtaine úsáid a bhaint as crua-earraí poiblí na laethanta seo. Dá bhrí sin, is féidir go bhféadfaí criptiú RSA ar mhéara a nochtadh go héasca sa todhchaí, agus beidh an córas le bheith gan léanta gan choinne.

Go hoifigiúil i 2003, rinneadh ceist maidir le slándáil eochracha 1024 giotán. Faoi láthair moltar go mbeadh 2048 giotán ar a laghad ann.