RSA-կոդավորումը. Նկարագրությունը եւ իրականացումը RSA ալգորիթմի

RSA-կոդավորումը մեկն առաջին գործնական հանրային-առանցքային կրիպտոհամակարգերի որը լայնորեն օգտագործվում է անվտանգ տվյալների փոխանցման. Դրա հիմնական տարբերությունն այլ նմանատիպ ծառայություններ այն է, որ կոդավորումը բանալին բաց է եւ տարբերվում է decryption բանալին, որը գաղտնի է պահվում: Որ RSA տեխնոլոգիան , այս անհամաչափությունը , որը հիմնված է պրակտիկ դժվարությամբ ֆակտորինգային նվագարկումը երկու խոշոր առաջնակարգ թվերի (խնդրին ֆակտորինգի):

Պատմությունը արարման

RSA անունը բաղկացած է նախնական նամակներ ազգանունների Rivest, Շամիր եւ Adleman - գիտնականների, ովքեր առաջին անգամ հրապարակայնորեն նկարագրված այդ գաղտնագրման ալգորիթմներ է 1977 թվականին: Klifford Koks, որը Անգլերեն մաթեմատիկոս, ով աշխատել է բրիտանական հատուկ ծառայությունների, առաջին զարգացնել համարժեք համակարգ է 1973 թ., Սակայն դա չէր գաղտնազերծված մինչեւ 1997

RSA օգտվողին ստեղծում եւ հետո հրապարակում է հանրային բանալին հիման վրա երկու մեծ առաջնակարգ թվերի հետ միասին օժանդակ արժեքով: Պարզ թվեր պետք է գաղտնի պահել: Յուրաքանչյուրը կարող է օգտագործել հանրային բանալին encrypt հաղորդագրություն, բայց եթե դա բավական մեծ է, ապա միայն մեկը գիտելիքով առաջնակարգ թվերի կարող է վերծանել է հաղորդագրություն. RSA կոդավորումը բացահայտումը, որը հայտնի է որպես հիմնախնդիր, այսօր բաց քննարկում, թե ինչպես է հուսալի մեխանիզմ:

RSA ալգորիթմը համեմատաբար դանդաղ, որի համար պատճառ է ոչ թե որպես լայնորեն օգտագործվում է ուղղակիորեն Արխիվի տեսակը օգտագործողին: Շատ դեպքերում, այս մեթոդը օգտագործվում է փոխանցելու համար համօգտագործվող բանալին ծածկագրված համար սիմետրիկ կոդավորումը բանալին, որն իր հերթին կարող է կատարել գործողություններ, նավաբեռ կոդավորումը եւ decryption է շատ ավելի բարձր արագությամբ.

Երբ կար մի կրիպտոհամակարգ իր ներկա տեսքով:

Այն գաղափարը, անհամաչափ գաղտնագրման բանալի վերագրվում Դիֆֆի եւ Հելլմանում, ով հրապարակված հայեցակարգը 1976 թ., Ներկայացնելով թվային ստորագրություններ, եւ փորձում է կիրառել տեսությունը համարներով. Նրանց ձեւակերպում օգտագործում է ընդհանուր գաղտնի բանալի գեներացվել է մի որոշակի թվով exponentiation modulo վարչապետ համարը: Սակայն, նրանք թողել բացել հարցը իրականացման այս գործառույթը, քանի որ սկզբունքները ֆակտորինգի լավ չի հասկացել, այն ժամանակ.

Rivest, Ադի Շամիր, եւ Adleman MIT- ում արդեն մի քանի անգամ փորձել տարիների ընթացքում ստեղծել միակողմանի գործառույթը, որը դժվար է վերծանել: Rivest եւ Շամիր (համակարգչային գիտնականների) առաջարկել է բազմաթիվ պոտենցիալ գործառույթներ, իսկ Adleman (նման մաթեմատիկայի) է Փնտռել «խոցելի կետերի» ալգորիթմի. Նրանք օգտագործվում են շատ մոտեցումների եւ, ի վերջո, զարգացնել վերջնական համակարգ, այժմ հայտնի է որպես RSA-ի ապրիլին 1977 թ.

Էլեկտրոնային ստորագրությունը եւ հանրային բանալին

Թվային ստորագրության կամ էլեկտրոնային ստորագրությունը, անբաժանելի մասն է էլեկտրոնային փաստաթղթի տեսակի. Այն ձեւավորվում է մի որոշակի cryptographic տվյալների փոփոխությունների: Այս հատկանիշի հնարավոր է ստուգել ամբողջականությունը փաստաթղթի, նրա գաղտնիությունը, ինչպես նաեւ որոշելու, թե ով է տնօրինում է այն: Ըստ էության, այլընտրանք սովորական ստանդարտ ստորագրությամբ:

Այս կրիպտոհամակարգ (RSA կոդավորված) առաջարկում է հանրային բանալին, ի տարբերություն սիմետրիկ: Դրա սկզբունքը գործում է այն, որ երկու տարբեր բանալիների օգտագործվում են փակ (կոդավորված) եւ բացօթյա: Առաջին օգտագործվում է առաջացնում թվային ստորագրությունը, ապա կարող է decrypt տեքստը. Երկրորդը `փաստացի կոդավորումը եւ էլեկտրոնային թվային ստորագրության:

Օգտագործելով ստորագրություն ավելի լավ հասկանալ RSA կոդավորումը, որի օրինակը կարող է կրճատվել որպես նորմալ գաղտնիքը, «փակվել է հարցասեր աչքերը», փաստաթղթում:

Որն է ալգորիթմը:

RSA ալգորիթմը բաղկացած է չորս քայլերը առանցքային սերնդի, բաշխման, կոդավորման եւ վերծանման: Ինչպես արդեն նշվեց, RSA-կոդավորումը ներառում է հանրային բանալի եւ մասնավոր բանալին: Արտաքին կարող է հայտնի է բոլորին, եւ օգտագործվում է encrypt հաղորդագրությունները: Դրա էությունը կայանում է նրանում, որ ուղերձները կոդավորված հետ հանրային բանալին կարող է լինել միայն decrypted տվյալ ժամանակահատվածում, օգտագործելով գաղտնի բանալին:

Անվտանգության նկատառումներից ելնելով, նրանց integers է ընտրված պատահական եւ պետք է նույնական չափերով, սակայն տարբերվում են երկարությամբ մի քանի համարներ, որպեսզի ֆակտորինգային ավելի բարդ է. Նույնը նույն թիվը կարող է արդյունավետ գտնվել է քննության իրենց պարզությամբ, ուստի կոդավորումը տեղեկատվության պետք է անպայման բարդ:

Հանրային բանալին բաղկացած է մոդուլով եւ հանրային նմուշ. Փակ միավոր եւ բաղկացած է մասնավոր գործչի, որը պետք է գաղտնի պահել:

RSA կոդավորումը ֆայլերը եւ թույլ կողմերը,

Սակայն, կան մի շարք պարզ hacking RSA մեխանիզմների: Երբ encrypting ցածր եւ փոքր արժեքներին կոդ համարները կարող է հեշտությամբ բացվել, եթե նկարը արմատը ծածկագիրը նկատմամբ թվերի:

Քանի որ RSA-կոդավորումը է deterministic ալգորիթմ (այսինքն, չունի պատահական բաղադրիչ), հարձակվողը կարող է հաջողությամբ գործարկել ընտրված տեքստի բաց նկատմամբ հարձակում կրիպտոհամակարգ կողմից encrypting հավանական plaintexts տակ հանրային բանալին եւ հակակշիռների վրա, թե արդյոք նրանք հավասար են ծածկագիրը: Սեմանտիկորեն ապահով կրիպտոհամակարգ կոչվում է այն դեպքում, որ հարձակվող չի կարող տարբերակել երկու կոդավորումը են միմյանցից, նույնիսկ եթե նա գիտի համապատասխան տեքստեր ընդլայնված ձեւով. Ինչպես նկարագրված է վերը, ՀՀԱ այլ ծառայություններ լիցք չէ սեմանտիկորեն ապահով.

Լրացուցիչ ալգորիթմները կոդավորման եւ պաշտպանության

Է խուսափել վերը նշված խնդիրները, գործնական իրականացման RSA են սովորաբար տեղադրված մեջ ինչ - որ ձեւով համակարգված, randomized միջուկով նախքան կոդավորումը. Սա ապահովում է, որ բովանդակությունը չի ընկնում շրջանակներում շարք անապահով plaintexts, եւ որ այս ուղերձը չի կարող լուծվել `պատահական ընտրությամբ:

Անվտանգության RSA կրիպտոհամակարգ եւ կոդավորման հիման վրա երկու մաթեմատիկական խնդիրների: խնդիրը ֆակտորինգային մեծ թվեր եւ փաստացի RSA խնդիրը: Լի բացահայտումը ծածկագրի եւ ստորագրության մեջ RSA համարվում անթույլատրելի է այն ենթադրության վրա, որ այդ երկու խնդիրների չի կարող լուծվել հավաքականորեն:

Սակայն, ինչպես նաեւ հնարավորություն է վերականգնել առաջնակարգ գործոնները, հարձակվողը կարող է հաշվարկել գաղտնի մեկնաբան հանրային բանալին, իսկ հետո decrypt տեքստ, օգտագործելով ստանդարտ ընթացակարգը: Չնայած այն հանգամանքին, որ այսօր ոչ մի առկա մեթոդը ֆակտորինգային մեծ թիվ է, որը դասական համակարգչի չի կարող գտնել, դա չի ապացուցվել, որ նա գոյություն չունի:

ավտոմատ

Այդ գործիքը, որը կոչվում է Yafu, կարող է օգտագործվել օպտիմալացնել գործընթացը: Ավտոմատացում YAFU է զարգացած առանձնահատկությունն է, որ համատեղում է factorization ալգորիթմներ է մտավոր եւ հարմարվողական մեթոդաբանության, որոնք minimizes է ժամանակ գտնել գործոնները կամայական մուտքագրման համարներով. Շատ implementations multithreaded ալգորիթմ, որը թույլ կտա Yafu լիարժեք օգտագործումը բազմաբնակարան կամ բազմաթիվ բազմաբնակարան հիմնական պրոցեսորների (այդ թվում, SNFS, SIQS եւ ECM): Առաջին հերթին, դա վերահսկվում է հրամանի տող գործիք. Ժամանակը ծախսել փնտրում կոդավորումը Yafu գործոնի օգտագործելով պայմանական համակարգիչ, ապա դա կարող է կրճատվել է վայրկյանների 103.1746. Այդ գործիքը գործընթացների երկուական կարողությունները 320 bits կամ ավելի. Սա շատ բարդ ծրագրային է, որ պահանջում է որոշակի քանակությամբ տեխնիկական հմտությունների տեղադրել եւ կարգավորել: Այսպիսով, RSA-կոդավորումը կարող է խոցելի C.

Hacking փորձերը վերջին ժամանակներում

2009 թ., Bendzhamin mudi օգտագործելով RSA-512 bit բանալին աշխատում էր վերծանման kriptoteksta 73 օրով, օգտագործելով միայն հայտնի ծրագրային ապահովման (GGNFS) եւ միջին սեղանադիր (երկմիջուկանի Athlon64 ին 1900 ՄՀց): Ինչպես ցույց է փորձի, պահանջվում է մի փոքր ավելի քիչ, քան 5 ԳԲ սկավառակի եւ շուրջ 2.5 գիգաբայթ հիշողության գործընթացում »sifting:»

Ինչ վերաբերում է 2010 թ., Ամենամեծ թիվը factored RSA 768 bits երկար (232 տասնորդական նիշի, կամ RSA-768): Նրա բացահայտումը տեւեց երկու տարի մի քանի հարյուր համակարգիչների միանգամից.

Գործնականում, ՀՀԱ բանալիներ են երկար սովորաբար 1024 է 4096 bits. Որոշ փորձագետներ կարծում են, որ 1024-bit բանալիներ կարող է դառնալ անվստահելի է մոտ ապագայում, կամ նույնիսկ ավելի երկար կարող է cracked շատ լավ ֆինանսավորվող հարձակվողները. Սակայն քչերը կարող էին պնդում են, որ 4096-bit բանալիներ կարող է նաեւ բացահայտվել է մոտ ապագայում:

հեռանկարները

Հետեւաբար, որպես կանոն, ենթադրվում է, որ RSA ապահով է, եթե համարները, բավական մեծ: Եթե բազան թիվը 300 bits կամ կարճ, եւ ծածկագրի թվային ստորագրության կարող է decomposed ընթացքում մի քանի ժամվա ընթացքում մի անձնական համակարգչի օգտագործելով ծրագրային ապահովման մատչելի արդեն հանրային տիրույթում. A հիմնական երկարությունը 512 bits, ինչպես ցույց է տրված, կարող է բացվել, քանի որ դեռեւս 1999 թ., Ինչպես նաեւ օգտագործման մի քանի հարյուր համակարգիչների. Այսօր դա հնարավոր է, մի քանի շաբաթից, օգտագործելով մի հրապարակայնորեն մատչելի hardware. Այսպիսով, դա հնարավոր է, որ buduschembudet հեշտությամբ բացահայտվում RSA կոդավորված է մատները, իսկ համակարգը կդառնա անհույս հնացած:

Պաշտոնապես 2003 թ.-ին էր հարցականի տակ անվտանգությունը 1024-բիթանոց բանալիների. Այժմ, ապա խորհուրդ է տրվում ունենալ նվազագույն երկարությունը 2048 bits.