Հեշ ֆունկցիա

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Հեշ ֆունկցիա
Դաս Ֆունկցիա

Հեշ ֆունկցիան դա գերազանց որոշված ընթացակարգ կամ մաթեմատիկական ֆունկցիա է, որը հիշողությունը՝ ենթադրելի փոփոխականի չափով տվյալը փոխակերպում է փոքր թվի, սովորաբար մի ամբողջ թվի, որը կարող է ծառայել որպես զանգվածի ինդեքս, հեշտացնել և արագացնել մեծ տրամաբանական աղյուսակներում փնտրման աշխատանքը։ Այն արժեքները, որոնք վերադարձնում է հեշ ֆունկցիան կոչվում են հեշ արժեքներ, հեշ կոդեր կամ պարզապես հեշեր։ Հեշ ֆունկցիաները լայնորեն կիրառվում են աղյուսակների որոնումը կամ համեմատության գործողությունները արագեցնելու նպատակով, օրինակ "տվյալների բազա"-ից մասեր գտնելը, ԴՆԹ կառուցվածքների մեջ նույնատիպ հետքերի փնտրման, ուղղագրության ստուգման, բառարանների և այլ ծրագրերում հասցնելով բառարանային գործողությունների արագությունը Օ(1) կոնստանտ ժամանակի։

Հեշ ֆունկցիան կարող է քարտեզագրել երկու կամ ավելի բանալիներ մեկ հեշ արժեքի, ցանկալի է մինիմիզացնել այդպիսի բախումների առաջացումը, դա նշանակում է որ հեշ ֆունկցիան պետք է հնարավորինս պարզորեն քարտեզագրի հեշ արժեքները։ Ծրագրից կախված այլ պայմաններել կարող են նույնքան պահանջված լինել։ Չնայած այդ գաղափարը մտածել են 1950 թ., որակյալ հեշ ֆունկցիաների նախագծումը դեռևս հանդիսանում է ակտիվ հետազոտության թեմա։

Հեշ ֆունկցիաները առնչվում են (և հաճախ շփոթում են) մատնահետքերի, պատահական թվերի գեներացման, սխալների ուղղման կոդերի, թվանշանների ստուգման, և կրիպտոգռաֆիկ հեշ ֆունկցիաների հետ։ Չնայած նրան, որ այս հասկացությունները ինչ-որ իմաստով համընկնում են, յուրաքանչյուրը ունի իր կիրառությունը ու պահանջները, և նախագծված ու օպտիմիզացված են տարբեր եղանակներով։

Հեշ աղյուսակներ

Հեշ ֆունկցիաները պարզորեն օգտագործվում են հեշ աղյուսակներում, տվյալի գրառման հասցեն արագ որոշելու համար (օրինակ բառարանի սահմանումը) տրված է գտնել բանալի հանդիսացող բառը։ Սովորաբար հեշ ֆունկցիայով քարտեզագրում են որոնման բանալին հեշին՝ ստեղծելով ինդեքսը, որը ցույց կտա թե որտեղ է տվյալ գրառումը պահված։ Իսկ հեշ աղյուսակները իրենց հերթին օգտագործվում են դինամիկ բազմությունների և ասոցիացված զանգվածներ իրականացնելու համարի։ Ընդհանուր առմամբ հեշ ֆունկցիան կարող է քարտեզագրել մի քանի տարբեր բանալիներ նույն ինդեքսին, հետևաբար յուրաքանչյուր հեշ աղյուսակի դիրք ասոցացվում է (ուղղակիորեն կամ անուղղակիորեն) գրառումների ինչ-որ բազմության հետ, այլ ոչ թե մի գրառման հետ։ Սա է պատճառը, որ յուրաքանչյուր դիրքի հաճախ անվանում են փունջ և հեշ արժեքները նաև անվանում են փնջի ցուցանիշներ։ Այսպիսով հեշ ֆունկցիան միայն հուշում է ռեկորդի հասցեն՝ թե որտեղ պետք է փնտրել այն։

Գաղտնագրական հեշ ֆունկցիա դա ձևափոխություն է, որը վերցնում է հաղորդագրություն և վերադարձնում ֆիքսած երկարության տող, որը անվանում են հեշ արժեք, կամ հաղորդագրությունների հավաքածու կամ թվային մատնահետք։ Իդեալ հեշ ֆունկցիան ունի 3 հատկություն

  • Շատ հեշտ է ստանալ ցանկացած տեքստի հեշ արժեքը
  • Սարսափելի բարդ, կամ ընդհանրապես անհնար է հեշ արժեքից վերականգնել սկզբնական տեքստը
  • Շատ անհավանական է, որ 2 տարբեր սկզբնական տեքստեր կտան նույն հեշը

Հեշ ֆունկցիաները օգտագործվում են բազմազան նպատակներով գաղտնագրման ասպարեզում և նրա սահմաններից դուրս։ Վերջիններս լայն կիրառում են գտել հաղորդագրությունների ամբողջականության ստուգման, թվային ստորագրությունների, անձորոշման և ինֆորմացիայի ապահովագրման գործում։ Հեշ ֆունկցիաների հատկություններից ելնելով կարելի է նրանց օգտագործել միանման կամ տարբերվող ֆայլերի հայտնաբերման և ինդեքսավորման գործում։ Ամենատարածված հեշ ֆունկցիաներն են MD5-ը և SHA-1-ը։ 2005-ին 2-ում էլ հանտնաբերվել են խոցելիություններ, որոնք կապված են օգտագործվող մաթեմատիկական համակարգի հետ, սա նշանակում է որ այժմ կա հզոր հեշ ֆունկցիայի պահանջ։ 2007-ին Ամերիկայի Ստանդարտների և Տեխնոլեգիայի ինստիտուտը հայտարարել է նոր ալգորիթմի մշակման մրցույթ, որը կկոչվի SHA-3 և կհանդիսանա FIPS ստանդարտի հիմքը։

Հեշ ֆունկցիան ընդունում է ցանկացած երկարության տող և վեր է ածում այն ֆիքսած երկարության տողի, որը կարելի է ընդունել որպես նախնական տողի ստորագրություն։ Այսպիսով, մեկը, ով գիտի հեշ կոդը՝ ի վիճակի չէ ստանալ նախնական տեքստը, սակայն, մեկը, ով գիտի սկզբնական տեքստը՝ կարող է ապացուցել որ հեշը ստացվել է այդ և միայն այդ տողից։ Այսպիսով հեշ ֆունկցիան պետք է վարի իրեն ինչպես պատահական ֆունկցիա, մինչդեռ պահպանելով իր միանշանակությունը և հեշտ հաշելիությունը։ Հեշ ֆունկցիան համարվում է անապահով, եթե հնարավոր է հետևյալ պայմաններից հաշվարկով ստացումը։

  1. Գտնել անհայտ հաղորդագրությունը, որը համապատասխանում է հեշ կոդին
  2. Գտնել ընդհարումներ, երբ 2 տարբեր սկզբնական տողեր տալիս են նույն հեշը

Հարձակվողը, որը կարող է անել թվարկվածներից որևէ մեկը, կարող է ներկայացնել չգրանցված տողը ինչպես գրանցված։ Իդեալական դեպքում պետք է ընդհանրապես հնարավոր չլինի գտնել 2 տողեր որ ունենան նույն հեշը, ինչը չի թույլ տա հարձակվողին որևէ ինֆորմացիա քաղել կոդի մասին։ Սակայն ցանկացած դեպքում հարձակվողը ստանում է մինիմալ ինֆորմացիա տեքստի մասին՝ հեշ կոդը, ինչը թույլ կտա հետագայում ճանաչել նույն կոդը հանդիպելու դեպքում։