Հեշ ֆունկցիա

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

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

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

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

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

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

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

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

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

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

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