Ինչ է Hashing- ի գործառույթը: Գաղտնագրային հեշ գործառույթներ

Մեր դիտարկած որոնման ալգորիթմները սովորաբար հիմնված են վերացական համեմատության գործողության վրա: Այս շարքից «խորհրդանիշի սեղաններ եւ երկուական որոնման ծառեր» նկարագրված բաշխման մեթոդը, որը պահվում է սեղանի I-րդ դիրքում, ինչը թույլ է տալիս ուղղակիորեն վկայակոչել դրան: Բաշխելով որոնումը, ստեղները օգտագործվում են որպես զանգվածի ինդեքս, եւ ոչ թե համեմատության գործողության օպերաներ. Մեթոդն ինքնին հիմնված է այն փաստի վրա, որ ստեղները տարբեր ամբողջական թվեր են նույն տեւողությամբ, ինչպես աղյուսակի ցուցիչները: Այս գլխում մենք կանդրադառնանք Hashing (Hashing) - բաշխման որոնման ընդլայնված տարբերակ, որն օգտագործվում է որոնման ավելի բնորոշ ծրագրերում, որտեղ ստեղները չունեն այդքան հարմար հատկություններ: Դիմումի վերջնական արդյունքը Այս մոտեցումը Համեմատության վրա հիմնված մեթոդների նման չէ. Փոխանակ տվյալների տվյալների կառուցվածքների միջոցով տեղափոխվելու փոխարեն `համեմատելով տարրերի հիմնական որոնման ստեղները, մենք սեղանի վրա ներկայացրելու համար նախատեսված իրերը:

HASHING- ով օգտագործող որոնման ալգորիթմները բաղկացած են երկու առանձին մասից: Առաջին քայլը HASH- ի գործառույթը (HASH գործառույթ) հաշվարկելն է, որը վերափոխում է սեղանի որոնման ստեղնը: Իդեալում, տարբեր ստեղներ պետք է ցուցադրվեն տարբեր հասցեներով, բայց հաճախ երկու կամ ավելի տարբեր ստեղներ կարող են աղյուսակում նույն հասցեն տալ: Հետեւաբար, խուզարկության երկրորդ մասը `Hashing մեթոդով, բախումների լուծման գործընթացն է (բախման բանաձեւ), որը գործընթաց է մշակում նման բանալիներ: Հակամարտության լուծման մեթոդներից մեկում, որոնք մենք կքննարկենք այս գլխում, միացված ցուցակները օգտագործվում են, ուստի այն ուղղակի օգտագործում է դինամիկ իրավիճակներում, երբ դժվար է կանխատեսել որոնման ստեղների քանակը: Բախումների լուծման այլ երկու մեթոդներով, խիստ ձեռք բերված կատարում Որոնել, քանի որ տարրերը պահվում են ֆիքսված զանգվածով: Մենք կքննարկենք այս մեթոդների կատարելագործման եղանակը, ինչը թույլ կտա ձեզ օգտագործել եւ այն դեպքերում, երբ նախապես հնարավոր չէ կանխատեսել սեղանի չափը:

Hashing- ը ժամանակի եւ հիշողության միջեւ հավասարակշռության լավ օրինակ է: Եթե \u200b\u200bօգտագործված հիշողության քանակի սահմանափակումներ չկային, ցանկացած որոնում կարող էր իրականացվել, օգտագործելով ընդամենը մեկ հիշողության հասանելիություն, պարզապես օգտագործելով ստեղնը որպես հիշողության հասցե: Այնուամենայնիվ, այս իդեալական դեպքը սովորաբար անհասանելի է, քանի որ երկար ստեղները կարող են պահանջել հսկայական հիշողություն: Մյուս կողմից, եթե սահմանափակումներ չլինեին կատարման ժամանակ, Հնարավոր կլինի անել նվազագույն հիշողությամբ, օգտագործելով հաջորդական որոնման եղանակը: Հովինգն է `ինչպես հիշողության, այնպես էլ ժամանակի ընդունելի ծավալը օգտագործելու եւ այս երկու ծայրահեղ պահանջների միջեւ հավասարակշռության հասնելու համար: Մասնավորապես, դուք կարող եք աջակցել ցանկացած հավասարակշռության, պարզապես փոխելով աղյուսակի չափը եւ չվերածնել կոդը եւ առանց այլ ալգորիթմների ընտրության:

Hashing- ը համակարգչային գիտությունների դասական առաջադրանքներից մեկն է. Դրա տարբեր ալգորիթմները մանրամասն ուսումնասիրվում են եւ լայնորեն օգտագործվում են: Մենք կտեսնենք, որ ոչ բոլոր ծանր ենթադրություններով, կարող եք հույս ունենալ, որ աջակցություն է ցուցաբերել խորհրդանշական աղյուսակներով գտնել եւ կպցնել խորհրդանիշի սեղանները `մշտական \u200b\u200bկատարման ժամանակ, անկախ սեղանի չափից:

Այս ակնկալվող արժեքը տեսական ներկայացումն է, որը օպտիմալ է խորհրդանշական սեղանի ցանկացած իրականացման համար, բայց Hash- ը դեռեւս չլինի Panacea երկու հիմնական պատճառով: Նախ, կատարման ժամանակ Կախված է հիմնական երկարությունից, որը իրական ծրագրերում երկար ստեղներ օգտագործող իրական ծրագրերում կարող է նշանակալի լինել: Երկրորդ, Hashing- ը չի ապահովում խորհրդանշական սեղաններով այլ գործողությունների արդյունավետ իրականացում, ինչպիսիք են ընտրելը կամ տեսակավորումը: Այս գլխում մենք մանրամասն կքննարկենք այս եւ այլ հարցեր:

Hash գործառույթ

Առաջին հերթին անհրաժեշտ է լուծել Hash գործառույթը հաշվարկելու խնդիրը, որը վերածում է սեղանի հասցեի բանալիները: Սովորաբար, այս թվաբանական հաշվարկի իրականացումը չի ներկայացնում բարդություն, բայց դեռ անհրաժեշտ է պահպանել խնամքը, որպեսզի չլինի ցածր մակարդակի ցածր մակարդակի թերություններ: Եթե \u200b\u200bկա սեղան, որը կարող է պարունակել M տարրեր, ձեզ հարկավոր է գործառույթ, որը բաշխում է միջակայքում գտնվող ամբողջ թվերի ստեղները: Իդեալական հեշ գործառույթը պետք է հեշտ լինի հաշվարկել եւ նման լինել պատահական գործառույթի. Any անկացած փաստարկների համար անհրաժեշտ է համարժեք լինել:

Հաշի գործառույթը կախված է բանալու տեսակից: Խստորեն ասած, առանձին HASH գործառույթը պահանջում է առանձին հիմնական տիպ: Արդյունավետությունը բարձրացնելու համար, սովորաբար ցանկալի է խուսափել տեսակների հստակ փոխակերպումից, դիմելով մեքենայի բառի բանալիների երկուական ներկայացմանը դիտարկելու գաղափարի հետ, որը կարող է օգտագործվել թվաբանության հաշվարկներում: Հոլրինգը հայտնվեց մինչեւ բարձր մակարդակի լեզուները `վաղ համակարգիչների վրա սովորական հարց էր` հաշվի առնելով ցանկացած արժեք որպես լարային բանալին: Որոշ բարձր մակարդակի լեզուներով դժվար է ստեղծել ծրագրեր, որոնք կախված են որոշակի համակարգչում ստեղների ներկայացումից, քանի որ նման ծրագրերը, ըստ էության, դժվար է տեղափոխել մեկ այլ համակարգիչ: Սովորաբար, Hash- ի գործառույթները կախված են փոխակերպման հիմնական գործընթացից, հետեւաբար դժվար է միաժամանակ ապահովել մեքենայի անկախությունը եւ արդյունավետությունը `հեշինգի իրականացման մեջ: Որպես կանոն, ամբողջական ամբողջական թիվ ստեղները կամ լողացող կետի ստեղները կարող են վերածվել ընդամենը մեկ մեքենայի շահագործման, բայց լարային ստեղները եւ բարդ ստեղների այլ տեսակները պահանջում են բարձր ծախսեր եւ ավելի մեծ ուշադրություն դարձնել արդյունավետության վրա:

Հավանաբար, ամենապարզ իրավիճակը այն է, երբ ստեղները ֆիքսված տեսականիով լողացող կետով թվեր են: Օրինակ, եթե ստեղները թվեր են, մեծ 0 եւ փոքր 1, այն պարզապես բազմապատկվում է M- ով, կլորացրեք արդյունքը ավելի փոքր ամբողջ թվով եւ հասցեն ստացեք 0-ից մ - 1-ի սահմաններում: Այս օրինակը ներկայացված է Նկ. 14.1. Եթե \u200b\u200bստեղները ավելի մեծ են, քան s եւ պակաս t, դրանք կարող են մասշտաբվել, հանելով S եւ բաժանելով TS- ում, որի արդյունքում նրանք ընկնում են արժեքների սահմաններում, իսկ հետո բազմապատկվում են Սեղանի հասցեն:

ՆկՂ 14.1.

Թողող կետը լողացող կետով 0-ից 1-ի սահմաններում սեղանի ինդեքսների միջակայքում փոխարկելու համար, որի չափը 97 է, բազմապատկելով այդ թվերը 97-ով: Այս օրինակում տեղի ունեցան երեք հակամարտություններ, 17, 53 եւ 76: Հաշի արժեքները որոշվում են երեցների հիմնական արտանետումների միջոցով, երիտասարդ արտանետումները որեւէ դեր չեն խաղում: Հաշի գործառույթի զարգացման նպատակներից մեկը նման անհավասարակշռությունն է վերացնել, որպեսզի հաշվարկի ընթացքում հաշվի առնվի յուրաքանչյուր արտահոսք:

Եթե \u200b\u200bստեղները W-Bit ամբողջ թվեր են, դրանք կարող են վերածվել լողացող կետի համարների եւ բաժանվել են 2 W- ի `0-ից 1-ի սահմաններում լողացող կետի համարներ ստանալու համար, իսկ հետո բազմապատկվում է M- ի, ինչպես նախորդ պարբերության մեջ: Եթե \u200b\u200bլողացող կետերը շատ ժամանակ են գրավում, եւ թվերն այնքան էլ բարձր չեն արտահոսքի հասնելու համար, նույն արդյունքը կարելի է ձեռք բերել `օգտագործելով թիվ թեւեր, ապա դրա հիմնականը տեղափոխվում է Right իշտ է `2 Վ-ն բաժանելու համար (կամ, եթե բազմապատկումը հանգեցնում է արտահոսքի, տեղափոխման, այնուհետեւ բազմապատկման): Նման մեթոդներն անօգուտ են հեշինգի համար, քանի դեռ ստեղները միատեսակ չեն բաշխվում միջակայքում, քանի որ հաշի արժեքը որոշվում է միայն բանալու առաջատար թվանշաններով:

Ավելի պարզ I. Արդյունավետ մեթոդ W-Bit ամբողջական թվերի համար `հեշինգի թերեւս ամենատարածված մեթոդներից մեկը` ընտրություն, որպես պարզ համարի չափի չափի աղյուսակ եւ հաշվարկելով մնացորդը մ.թ.ա. H (k) \u003d k mod m ցանկացած ամբողջական ամբողջական ստեղնաշարի համար: Այս գործառույթը կոչվում է մոդուլային հեշ գործառույթ: Դա շատ հեշտ է հաշվարկել (K% m- ն C ++), եւ արդյունավետ է փոքր արժեքների միջեւ առկա հիմնական արժեքների միատեսակ բաշխումը `փոքր օրինակ, որը ցույց է տրված Նկ. 14.2.

ՆկՂ 14.2.

Երեք աջ սյունակում ձախ կողմում ցուցադրված 7-բիթանոց ստեղների արդյունքը ցույց է տրված հետեւյալ գործառույթները.

v% 97 (ձախ)

v% 100 (կենտրոն) եւ

(int) (A * V)% 100 (աջ),

որտեղ a \u003d .618033: Այս գործառույթների աղյուսակի չափերը համապատասխանաբար 97, 100 եւ 100 տարեկան են: Արժեքները պատահական են թվում (քանի որ ստեղները պատահական են): Երկրորդ գործառույթը (V% 100) օգտագործում է ստեղների միայն երկու ծայրահեղ աջ թվանշան, ուստի ոչ պատահական ստեղների համար կարող են ցածր ներկայացում ցույց տալ:

Մոդուլային հեշինգը վերաբերում է լողացող կետի ստեղներին: Եթե \u200b\u200bստեղները պատկանում են փոքր տիրույթին, դրանք կարող են մասշտաբի թվերի մեջ թվեր `0-ից 1-ը, որպեսզի ստանան W-BIT ամբողջական թվով արժեքներ, ապա օգտագործեք մոդուլային հեշ գործառույթը: Մեկ այլ տարբերակ `պարզապես օգտագործելը մոդուլային հեշ-գործառույթի երկուական հիմնական ներկայացում (եթե առկա է):

Մոդուլային հեշինգը կիրառվում է բոլոր դեպքերում, երբ բիտերը մուտք են գործում, որից ստեղները բաղկացած են, անկախ նրանից, թե մեքենայական բառով ներկայացված են մի ամբողջություն, կամ ներկայացված են որեւէ այլ կերպ Հնարավոր տարբերակ, Պատահական խորհրդանիշների հաջորդականությունը, որը փաթեթավորված է մեքենայի բառի մեջ, ճիշտ նույնը չէ, որքան պատահական ամբողջական ստեղները, քանի որ բոլոր արտանետումները օգտագործվում են կոդավորման համար: Բայց այս երկու տեսակներն էլ (եւ ցանկացած այլ տեսակի բանալին կոդավորված են մեքենայի բառի մեջ տեղավորվելու համար) կարող են արվել փոքր սեղանի վրա պատահական ցուցանիշների նման:

Ընտրության հիմնական պատճառը, որպես չափի M մոդուլային հեշինգի համար պարզ համարի պարզ համարի աղյուսակը ցուցադրվում է FIG- ում: 14.3. Այս օրինակում 7-բիթ կոդավորմամբ խորհրդանշական տվյալները մեկնաբանվում են որպես բազայի 128-ով մի շարք `բանալին յուրաքանչյուր բնույթի մեկ թվանշանով: Այժմ բառը համապատասխանում է 1816567 համարին, որը նույնպես կարող է գրվել որպես

Քանի որ ASCII կոդային խորհրդանիշները n, o եւ w համապատասխանում են 1568 \u003d 110, 1578 \u003d 111 եւ 1678 \u003d 119 համարներին: Սեղանի M \u003d 64 Այս տեսակի ստեղնաշարի չափը անհաջող է, քանի որ X արժեքների ավելացում, բազմակի 64 (կամ 128), չի փոխում XID 64 արժեքը, ցանկացած բանալին է այս բանալու վերջին 6 թվանշանների արժեքը: Իհարկե, լավ հեշ գործառույթը պետք է հաշվի առնի բոլոր հիմնական արտանետումները, հատկապես խորհրդանշական ստեղների համար: Նման իրավիճակներ կարող են առաջանալ, երբ M- ն պարունակում է բազմապատկիչ, որը 2-րդ աստիճան է: Ամենապարզ ձեւը Խուսափեք սա - Ընտրեք որպես M պարզ համար:

ՆկՂ 14.3.

Այս աղյուսակի յուրաքանչյուր շարքում դուք եք, 3-տառ բառ, այս բառի շնորհանդեսը ASCII կոդով, որպես օկտանե եւ տասնորդական ձեւի եւ ստանդարտ մոդուլային հեշի գործառույթներ 64 եւ 31-րդ աղյուսակների չափերի համար (երկուսը) ծայրահեղ սյուն աջ կողմում): Աղյուսակ 64-ի չափը հանգեցնում է անցանկալի արդյունքների, քանի որ ընդամենը միանգամայն հիմնական լիցքավորվում է բշտիկավոր արժեքը ստանալու համար, իսկ սովորական լեզվով բառերով տառերը անհավասարաչափ բաշխվում են: Օրինակ, Y տառով օժտված բոլոր բառերը համապատասխանում են HASH արժեքին 57. Եվ, ընդհակառակը, 31-ի պարզ արժեքը աղյուսակում ավելի քիչ է առաջացնում ավելի քան երկու անգամ ավելի քիչ:

Մոդուլային հեշինգը շատ հեշտ է իրականացնել, բացի այն, որ աղյուսակի չափը պետք է լինի պարզ համար: Որոշ ծրագրերի համար կարող եք գոհ լինել մի փոքր հայտնի պարզ թվով կամ որոնելով հայտնի վարչապետի ցուցակում, որը մոտ է սեղանի ցանկալի չափին: Օրինակ, համարները 2 t - 1 են, պարզ են t \u003d 2, 3, 5, 7, 13, 17, 19 եւ 31 (եւ ոչ մի այլ արժեքների< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не Միակ պատճառըորի վրա աղյուսակի չափը արժե պարզ թվով դարձնել. 14.4 բաժնում դիտարկվում է եւս մեկ պատճառ:

ՆկՂ 14.4.

Այս աղյուսակը 2-ից փոքրագույն ամենամեծ պարզ համարներն են Կարող է օգտագործվել դինամիկ հեշի սեղանի բաշխման համար, երբ անհրաժեշտ է, որ աղյուսակի չափը պարզ համար է: Shared անկացած տվյալ դրական արժեքի համար այս աղյուսակը կարող է օգտագործվել պարզ թվով պարզելու համար, որը տարբերվում է դրանից ավելի քիչ, քան 2 անգամ:

Թեմթերի ստեղների մեկ այլ մարմնավորում է բազմապատկիչ եւ մոդուլային մեթոդների համադրություն. Դուք պետք է բազմապատկեք մշտական \u200b\u200bկետի համար `0-ից 1-ի սահմաններում, այնուհետեւ Module Man- ի միջոցով բաժանումը, դուք պետք է օգտագործեք գործառույթը: Հիմնական համարների համակարգի արժեքների եւ արդյունավետ բազայի միջեւ կա մի հարաբերություն, որ տեսականորեն կարող է հանգեցնել անոմալ պահվածքի, բայց եթե կամայական արժեք եք օգտագործում A- ն Իրական հավելված Խնդիր չունի որեւէ խնդիր ունենալ: Հաճախ, որպես A, 0.618033 արժեքը ... (Ոսկե հատված) ընտրվում է:

Այս թեմայի վերաբերյալ շատ այլ տատանումներ են ուսումնասիրվել, մասնավորապես, Hash գործառույթները, որոնք կարող են իրականացվել `օգտագործելով այնպիսի արդյունավետ մեքենայի հրահանգներ, ինչպիսիք են հերթափոխը եւ դիմակի ընտրությունը (տես հղումներ):

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

7-բիթանոց ASCII կոդում այս բառը համապատասխանում է 84-բիթանոց համարին \\ Սկիզբը (հավասարեցնել *) 97 \\ CDot 128 ^ (11) & + 118 \\ CDot 128 ^ (10) + 114 \\ CDot 128 ^ (8) + 121 \\ CDot 128 ^ (7) \\\\ & + 108 \\ CDot 128 ^ (6) + 111 \\ CDot 128 ^ (5) + 103 (4) + 103 \\ CDot 128 ^ (3) \\\\ & + 107 \\ CDot 128 ^ (2) + 101 \\ CDot 128 ^ (1) + 121 \\ CDot 128 ^ (0), \\ վերջ (հավասարեցում *),

Որը չափազանց մեծ է, որպեսզի սովորական թվաբանական գործառույթները կարողանան դրա հետ միասին իրականացվել համակարգիչների մեծ մասում: Եվ հաճախ պահանջվում է կարգավորել եւ շատ ավելի երկար ստեղներ:

Երկար ստեղների համար մոդուլային հեշ գործառույթը հաշվարկելու համար դրանք փոխարկվում են բեկորների համար: Կարող եք օգտագործել մոդուլի ֆունկցիայի թվաբանական հատկությունները եւ օգտագործել Gorner Algorithm- ը (տես Բաժին 4.9 "վերացական տվյալների տեսակները): Այս մեթոդը հիմնված է ստեղներին համապատասխան թվերի ձայնագրման մեկ այլ մեթոդի վրա: Քննարկվող օրինակի համար մենք գրում ենք հետեւյալ արտահայտությունը. \\ CDot 128 ^ (9) + 114) \\ CDot 128 ^ (8) + 121) \\ CDot 128 ^ (7) \\\\ & + 108) \\ CDOT 128 ^ (6) + 110) \\ CDot 128 ^ (4) + 103) \\ CDot 128 ^ (3) \\\\ & + 107) \\ CDot 128 ^ (2) + 101) \\ CDOT 128 ^ (1) + 121. \\ վերջ (հավասարեցում) *)

Այսինքն, տողի նիշերի կոդավորմանը համապատասխան տասնորդական թիվ կարող է հաշվարկվել այն ժամանակ, երբ այն դիտում է ձախից աջ, կուտակված արժեքը մինչեւ 128, իսկ հետո ավելացնելով հաջորդ խորհրդանիշի կոդը: Երկար տողի դեպքում հաշվարկման այս մեթոդը, ի վերջո, կհանգեցնի մեծի, որը կարող է բոլորովին ներկայացվել համակարգչում: Այնուամենայնիվ, այս թիվը անհրաժեշտ չէ, քանի որ Մ.-ի իր դիվիզիոնից պահանջվում է միայն (փոքր) մնացորդը: Արդյունքը կարելի է ձեռք բերել, առանց նույնիսկ կուտակված արժեքը պահելու, քանի որ Any անկացած պահի հաշվարկը կարող է հանվել բազմակի M - ամեն անգամ, երբ դուք կատարում եք բազմապատկում եւ լրացում, անհրաժեշտ է պահել միայն Մոդուլից միայն մնացորդը, եթե մենք հաշվարկենք Երկար թվով եւ հետո կատարեք բաժինը (տես Զորավարժություն 14.10): Այս դիտարկումը հանգեցնում է երկարատեւ տողերի համար մոդուլային հեշ գործառույթների հաշվարկման ուղղակի թվաբանական մեթոդի. Տես ծրագիրը 14.1. Այս ծրագիրը օգտագործում է եւս մեկ, վերջին հյուսելը. 128 բազայի փոխարեն այն օգտագործում է պարզ թիվ 127: Այս փոփոխության պատճառը դիտարկվում է հաջորդ պարբերությունում:

Հեշհը հաշվարկելու շատ եղանակներ կան մոտավորապես նույն ծախսերով, ինչպես մխիթարական հեշինգը, օգտագործելով Gorner մեթոդը (մեկ կամ երկու) Թվաբանական գործողություններ Բանալին յուրաքանչյուր խորհրդանիշի համար): Պատահական ստեղների համար այս մեթոդները գործնականում տարբերվում են միմյանցից, բայց իրական ստեղները հազվադեպ են պատահական: Իրական ստեղների պատահական տեսակը ցածր ծախսերի արժեքի հնարավորությունը հանգեցնում է պատահական վարակման ալգորիթմների դիտարկմանը, քանի որ մենք ունենք Hash գործառույթներ, որոնք ստեղծում են սեղանի պատահական ինդեքսներ, անկախ հիմնական բաշխումից: Պատահականություն կազմակերպելը դժվար չէ, քանի որ անհրաժեշտ չէ բառացիորեն հավատարիմ մնալ մոդուլային հեշինգի սահմանմանը. Այն անհրաժեշտ է միայն ավելի փոքր մ-ի ամբողջ քանակը հաշվարկել: Բոլոր հիմնական արտանետումները օգտագործվել են:

M \u003d 96 եւ A \u003d 128 (վերեւում)

M \u003d 97 եւ A \u003d 128 (կենտրոն) եւ

M \u003d 96 եւ A \u003d 127 (ստորեւ)

Առաջին դեպքում անհավասար բաշխումը տառերի անհավասար օգտագործման եւ անհավասարության պահպանման արդյունքն է այն պատճառով, որ սեղանի չափը եւ բազմապատկիչ բազմապատկիչը 32: Երկու այլ օրինակներ պատահական են թվում, քանի որ սեղանի չափը եւ բազմապատկիչը փոխշահավետ են համարներ:

Ծրագիրը 14.1-ը ցույց է տալիս դա կատարելու եղանակներից մեկը. 2-րդ աստիճանի փոխարեն պարզ հիմք օգտագործելը եւ տողի ASCI ներկայացուցչությանը համապատասխանող ամբողջ թիվ: Նկ. 14.5 Նկ. 14.5 Ուցադրվում է, թե ինչպես է այս փոփոխությունը բարելավում բաշխումը բնորոշ լարային ստեղների համար: Ծրագրով 14.1 ծրագրով ստեղծված տեսականորեն կարող են վատ արդյունքներ տալ սեղանի չափերի համար, որոնք բազմակի 127-ն են (չնայած գործնականում, հավանաբար, դա գրեթե աննկատելի է). Պատահական ալգորիթմ ստեղծելու համար հնարավոր կլինի պատահականորեն ընտրել բազմապատկիչի արժեքը: Նույնիսկ ավելի արդյունավետ մոտեցում է `գործակիցների պատահական արժեքները հաշվարկման մեջ եւ յուրաքանչյուր հիմնական համարի համար տարբեր պատահական արժեքներ օգտագործել: Այս մոտեցումը տալիս է պատահական ալգորիթմ, որը կոչվում է ունիվերսալ հեշինգ (ունիվերսալ հեշինգ):

Տեսականորեն, իդեալական ունիվերսալ հեշ գործառույթը գործառույթ է, որի համար նախատեսված է չափի երկու տարբեր ստեղների միջեւ բախման հավանականությունը `չափով հավասար է 1 / մ: Դա կարող է ապացուցվել, որ որպես գործակիցը, որպես գործակից, 14.1-ը ֆիքսված կամայական արժեք չունի, եւ պատահական տարբեր արժեքների հաջորդականությունները վերածում են համընդհանուր հեշի գործառույթի: Այնուամենայնիվ, բանալին յուրաքանչյուր խորհրդանիշի համար նոր պատահական համար ստեղծելու արժեքը սովորաբար անընդունելի է: Գործնականում հնարավոր է հասնել ծրագրում ներկայացված փոխզիջման, առանց յուրաքանչյուր հիմնական խորհրդանիշի համար տարբեր պատահական համարների զանգվածը պահելու եւ տարբեր կեղծ պատահական հաջորդականության սերնդի օգտագործող գործակիցներին:

Մենք ամփոփենք. Վերացական նիշերի սեղանն իրականացնելու համար, դուք պետք է ընդլայնել վերացական տիպի ինտերֆեյսը, այն վերածելով Hash- ի շահագործման, որը ցուցադրում է ոչ բացասական թվերի ստեղները:

Որպես այս հոդվածի մաս, ես ձեզ կասեմ Ինչ է hashԻնչու է անհրաժեշտ, որտեղ եւ ինչպես է այն օգտագործվում, ինչպես նաեւ առավել հայտնի օրինակներ:

Տեղեկատվական տեխնոլոգիաների ոլորտում շատ մարտահրավերներ շատ կարեւոր են տվյալների ծավալների համար: Օրինակ, եթե Ձեզ անհրաժեշտ է համեմատել երկու ֆայլեր 1 KB եւ 10 GB- ի երկու ֆայլերով, ապա այն բոլորովին այլ ժամանակ է: Հետեւաբար, ալգորիթմները, որոնք թույլ են տալիս գործել ավելի կարճ եւ ընդարձակ արժեքներով, համարվում են շատ տարածված:

Նման տեխնոլոգիաներից մեկը հեշինգ է, որն իր օգտագործումը գտել է առաջադրանքների զանգվածը լուծելիս: Բայց ես կարծում եմ, որ դուք, որպես սովորական օգտվող, դեռեւս անհասկանալի է, ինչպիսի գազան է այն անհրաժեշտի համար: Հետեւաբար, ես կփորձեմ բացատրել բոլոր ամենահեշտ բառերը:

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

Ինչ է Hash- ը կամ Hashing- ը:

Ես կսկսեմ պայմաններով:

Hash գործառույթ, Concoolution գործառույթ - Սա հատուկ առանձնահատկություն է, որը թույլ է տալիս վերափոխել կամայական երկարության տեքստերը ֆիքսված երկարության կոդով (սովորաբար կարճ թվային գրառում):

Խիճ - Սա աղբյուրի տեքստերի վերափոխման գործընթացն է:

HASH, HASH ծածկագիր, արժեք HASH, HASH-SUM - Սա HASH գործառույթի ելքային արժեքն է, այսինքն, արդյունքում ստացված բլոկը ֆիքսված երկարություն է:

Ինչպես տեսնում եք, տերմիններն ունեն մի քանի ձեւավորված նկարագրություն, որից դժվար է հասկանալ, թե ինչու է դա անհրաժեշտ: Հետեւաբար, ես անմիջապես կտամ փոքր օրինակ (այլ դիմումների մասին մի փոքր ավելի ուշ կպատմի): Ենթադրենք, որ ունեք 10 ԳԲ 2 ֆայլ: Ինչպես կարող եք արագ պարզել, թե որ մեկը պետք է: Կարող եք օգտագործել ֆայլի անունը, բայց դա հեշտ է վերանվանել: Կարող եք դիտել ամսաթվերը, բայց ֆայլի ֆայլերը պատճենելուց հետո կարող է լինել նույնը կամ այլ հաջորդականություններ: Չափը, թե ինչպես եք հասկանում, քիչ բան կարող է օգնել (հատկապես, եթե չափերը համընկնում են, կամ դուք չեք նայում բայթերի ճշգրիտ արժեքներին):

Այստեղ է, որ ձեզ հարկավոր է հենց այս hash- ը, որը կարճ բլոկ է, որը ստեղծվում է ֆայլի աղբյուրի տեքստից: Այս երկու ֆայլերը 10 ԳԲ կունենան երկու տարբեր, բայց կարճ հեշ ծածկագիր (նման բան «ACCAC43535» եւ «BBB3232A42»): Օգտագործելով դրանք, կարող եք արագ պարզել Ցանկալի ֆայլ:Նույնիսկ անունները պատճենելուց եւ փոփոխությունից հետո:

ՆշումԲացի այդ, աշխարհի եւ ինտերնետի համակարգչում հեշը շատ հայտնի հայեցակարգ է, ապա հաճախ այն ամենը, ինչ կապված է Hash- ի հետ, այս բառով կրճատվում է: Օրինակ, թարգմանության մեջ «Ես օգտագործում եմ HASH MD5» արտահայտությունը, որ կայքում կամ ինչ-որ այլ տեղ օգտագործվում է MD5 ստանդարտի Hashing Algorithm- ի կողմից:

Հեշի հատկություններ

Այժմ ես ձեզ կասեմ Hash գործառույթների հատկությունների մասին, որպեսզի ձեզ համար ավելի հեշտ է հասկանալ, թե որտեղ է այն օգտագործվում եւ ինչի համար անհրաժեշտ է: Բայց նախ մեկ այլ բնորոշում:

Բախում - Սա է իրավիճակը, երբ մեկ եւ նույն հեշի գումարը ձեռք է բերվում երկու տարբեր տեքստերի համար: Ինչպես գիտեք, ֆիքսված երկարության բլոկը, այն ունի սահմանափակ քանակությամբ հնարավոր արժեքներ, եւ, հետեւաբար, կրկնում են կրկնողությունները:

Եվ հիմա HASH գործառույթների հատկություններին.

1. Տեքստը կարող է մատակարարվել ցանկացած չափի տեքստին, իսկ ելքը ֆիքսված տվյալների շտեմարան է: Սա հետեւում է սահմանումից:

2. Նույն տեքստերի հեշ-գումարը պետք է լինի նույնը: Հակառակ դեպքում, նման գործառույթները պարզապես անօգուտ են. Սա նման է պատահական համարին:

3. Լավ բաշխման գործառույթը պետք է ունենա լավ բաշխում: Համաձայնեք, որ եթե ելքային հեշի չափը, օրինակ, 16 բայթ է, ապա եթե գործառույթը վերադառնում է միայն 3 տարբեր արժեքներ ցանկացած տեքստի համար, ապա այդպիսի գործառույթի եւ 16 բայթը 2 ^ 128 է Ընտրանքներ, որոնք մոտավորապես 3, 4 * 10 ^ 38 աստիճան են):

4. Որքանով է գործառույթը պատասխանում աղբյուրի տեքստի աննշան փոփոխություններին: Պարզ օրինակ: 10 ԳԲ ֆայլի մեջ փոխված 1 տառը փոխեց, գործառույթի արժեքը պետք է տարբեր լինի: Եթե \u200b\u200bայդպես չէ, ապա շատ խնդրահարույց է այդպիսի գործառույթ կիրառելը:

5. Բախման առաջացման հավանականությունը: Որոշակի պայմաններում հաշվարկված շատ բարդ պարամետր: Բայց նրա էությունն այն է, որ որն է HASH գործառույթի կետը, եթե արդյունքում ստացված HASH գումարը հաճախ համընկնի:

6. HASHA հաշվարկման տոկոսադրույքը: Որն է շատ բանը, եթե դա երկար ժամանակ հաշվարկի համար է: Ոչ, քանի որ այդ դեպքում ֆայլերը ավելի հեշտ են համեմատել կամ օգտագործել մեկ այլ մոտեցում:

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

8. Նման գործառույթի համար բացված կամ փակ կոդով: Եթե \u200b\u200bօրենսգիրքը բաց չէ, տվյալների վերականգնման բարդությունը, մասնավորապես, գաղտնոտությունը, մնում է հարցական: Մասամբ, սա գաղտնագրման խնդիր է:

Այժմ դուք կարող եք գնալ «եւ ինչու է այդ ամենը»:

Ինչու է պետք խոչ:

Hash- ի գործառույթների հիմնական նպատակները միայն երեքն են (ավելի ճիշտ, դրանց նպատակը):

1. Ստուգեք տվյալների ամբողջականությունը: Մեջ Այս դեպքը Ամեն ինչ պարզ է, նման գործառույթը պետք է արագ հաշվարկվի եւ թույլ տա արագ ստուգել, \u200b\u200bօրինակ, ինտերնետից ներբեռնված ֆայլը չի \u200b\u200bվնասվել:

2. Տվյալների որոնման արագությունը մեծացնելը: Հաստատուն բլոկի չափը թույլ է տալիս ստանալ շատ առավելություններ որոնման առաջադրանքների լուծման գործում: Այս դեպքում մենք խոսում ենք այն մասին, թե ինչն է զուտ տեխնիկապես, Hash գործառույթների օգտագործումը կարող է դրական ազդեցություն ունենալ կատարման վրա: Նման գործառույթների համար շատ կարեւոր է բախումների հավանականությունը եւ լավ բաշխումը:

3. Գաղտնագրային կարիքների համար: Այս տեսակ Հայկացիայի գործառույթներն օգտագործվում են անվտանգության ոլորտներում, որտեղ կարեւոր է, որ արդյունքները դժվար է փոխարինել կամ որտեղ անհրաժեշտ է բարդացնել հնարավորինս ձեռք բերելու խնդիրը: Օգտակար տեղեկատվություն Hash- ից:

Որտեղ եւ ինչպես է կիրառվում հեշը:

Ինչպես երեւի դուք արդեն կռահել եք, Խելը կիրառվում է շատ առաջադրանքներ լուծելիս: Ահա դրանցից մի քանիսը.

1. Գաղտնաբառերը սովորաբար պահվում են ոչ թե բաց ձեւով, այլ HASH SM- ի տեսքով, ինչը թույլ է տալիս ապահովել անվտանգության ավելի բարձր աստիճան: Ի վերջո, նույնիսկ եթե հարձակվողը մուտք գործի նման տվյալների բազա, նա դեռ պետք է շատ ժամանակ ծախսեր այս Hash կոդերի համապատասխան տեքստերը վերցնելու համար: Ահա «Հեշի արժեքներից նախնական տվյալների վերականգնման բարդությունը» բնորոշ է:

ՆշումԵս խորհուրդ եմ տալիս ծանոթանալ հոդվածի մի քանի խորհուրդների, գաղտնաբառերի անվտանգությունն բարելավելու համար:

2. Ծրագրավորման մեջ, ներառյալ տվյալների բազաները: Իհարկե, ամենից հաճախ մենք խոսում ենք տվյալների կառուցվածքների մասին, որոնք թույլ են տալիս Արագ որոնում, Մաքուր տեխնիկական տեսանկյունից:

3. Երբ տվյալների փոխանցման տվյալները (ներառյալ ինտերնետը): Շատ արձանագրություններ, ինչպիսիք են TCP / IP- ն, ներառում են հատուկ ստուգման դաշտեր, որոնք պարունակում են աղբյուրի հաղորդագրության հեշ գումար, որպեսզի եթե ինչ-որ տեղ ձախողվի, այն չի ազդել տվյալների փոխանցման վրա:

4. Անվտանգության հետ կապված տարբեր ալգորիթմների համար: Օրինակ, Hash- ն օգտագործվում է էլեկտրոնային թվային ստորագրություններում:

5. Հաստատել ֆայլերի ամբողջականությունը: Եթե \u200b\u200bուշադրություն դարձնեք, հաճախ հնարավոր է հանդիպել ֆայլերը ինտերնետում (օրինակ, արխիվ) Լրացուցիչ նկարագրություններ Հեշի կոդով: Այս միջոցը կիրառվում է ոչ միայն այնպես, որ դուք պատահական չեք գործարկեք այն ֆայլը, որը վնասվել է ինտերնետից ներբեռնելիս, այլեւ հյուրընկալման պարզություն կան: Նման դեպքերում դուք կարող եք արագ ստուգել Hash- ը եւ անհրաժեշտության դեպքում, ապա ավելի չափազանցեք ֆայլը:

6. Երբեմն Hash գործառույթներն օգտագործվում են եզակի նույնականացուցիչներ ստեղծելու համար (որպես մաս): Օրինակ, նկարները կամ պարզապես ֆայլերը խնայելու ժամանակ, սովորաբար անուններով օգտագործում եք hash- ը `ամսաթվի եւ ժամի հետ միասին: Սա թույլ է տալիս նույն անունով չգրավել ֆայլերը:

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

Հայտնի հեշ գործառույթներ

Առավել հայտնի են հետեւյալ երեք Hash- ի գործառույթները:

Ծանոթագրություն. Այս դասախոսության մեջ ձեւակերպվում է HASH գործառույթի հայեցակարգը, ինչպես նաեւ Կարճ ակնարկ Ալգորիթմներ `հեշ գործառույթների ձեւավորման համար: Բացի այդ, այն համարվում է բլոկային ալգորիթմներ օգտագործելու համար կոդավորման համար կոդավորման համար `հեշ գործառույթ ձեւավորելու համար:

Դասախոսության նպատակը. Ծանոթանալ «Հաշի գործառույթի» հայեցակարգին, ինչպես նաեւ նման գործառույթների սկզբունքներով:

Հեշի գործառույթի հայեցակարգ

Hash գործառույթ (Hash գործառույթ) Զանգահարվում է մաթեմատիկական կամ այլ գործառույթ, որը կամայական երկարության տողերի համար հաշվարկում է որոշակի ամբողջ թիվ կամ ֆիքսված երկարության մի այլ շարք: Մաթեմատիկորեն, դա կարող է գրվել այսպես.

որտեղ M- ն երբեմն կոչվում է բնօրինակ հաղորդագրություն Նվեր, իսկ H - Արդյունքը, որը կոչվում է հեշ գործառույթ (ինչպես նաեւ Հեշի ծածկագիր կամ digest հաղորդագրություն (անգլերենից: Հաղորդագրություն Digest.)).

Հաշմանդամի իմաստը նմուշի բնորոշ առանձնահատկությունն է `հեշ գործառույթի իմաստը: Այս արժեքը սովորաբար ունի որոշակի ֆիքսված չափ, օրինակ, 64 կամ 128 բիթ: HASH ծածկագիրը կարող է հետագայում վերլուծվել ցանկացած առաջադրանքի լուծման համար: Օրինակ, հեշինգը կարող է օգտագործվել տվյալների համեմատության համար. Եթե երկու հեշ կոդավորվում են, զանգվածները երաշխավորված են. Եթե \u200b\u200bնույն - զանգվածները, ամենայն հավանականությամբ, նույնն են: Ընդհանրապես, աղբյուրի տվյալների եւ HASH ծածկագրի միջեւ միանշանակ նամակագրությունը պայմանավորված չէ այն փաստով, որ Hash- ի գործառույթների քանակը միշտ էլ պակաս է, քան մուտքային ընտրանքները: Հետեւաբար, կան բազմաթիվ մուտքային հաղորդագրություններ, որոնք տալիս են նույն հեշ ծածկագրերը (նման իրավիճակները կոչվում են Կոլիզիա): Բախումների առաջացման հավանականությունը կարեւոր դեր է խաղում Հաշի գործառույթների որակը գնահատելու գործում:

Հեշի գործառույթները լայնորեն օգտագործվում են ժամանակակից գաղտնագրման մեջ:

Ամենապարզ Hash- ի գործառույթը կարելի է պատրաստել `օգտագործելով« Մոդուլի գումարը 2 »գործողության հետեւյալը. Մենք ստանում ենք մուտքային տող, բոլոր բայթերը մետաղի միջոցով ենք ծալում 2-ով, իսկ բայթը, բացի բոյդը: Հեշի գործառույթի երկարությունը կլինի այս դեպքում 8 բիթ, անկախ մուտքային հաղորդագրության չափից:

Օրինակ, թող թվային դիտում թարգմանված բնօրինակ հաղորդագրությունը, հետեւյալը (hexadecimal ձեւաչափով).

Հաղորդագրությունը կփոխանցենք երկուական տեսքին, գրելու բայթերը միմյանց եւ կդառնան բիտերը յուրաքանչյուր սյունակում `մոդուլի 2-ով.

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Արդյունքը (0110 0101 (2) կամ 65 (16)) եւ կլինի HASH գործառույթի արժեքը:

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

Հետեւաբար, համարվող HASH գործառույթը հարմար չէ գաղտնագրական ծրագրերի համար: Գաղտնագրման մեջ HASH գործառույթը լավ է համարվում, եթե դժվար է ստեղծել երկու տեսակի նույն հեշ գործառույթով, ինչպես նաեւ գործառույթի արդյունքը բացահայտորեն կախված չէ մուտքից:

Մենք ձեւակերպում ենք Cryptograpic Hash գործառույթների հիմնական պահանջները.

hash գործառույթը պետք է կիրառելի լինի ցանկացած չափի հաղորդագրության համար.
Գործառույթի արժեքի հաշվարկը պետք է իրականացվի բավականաչափ արագ.
Հայտնի Hash- ի գործառույթով պետք է լինի դժվար (գրեթե անհնար) համապատասխան նախատիպը գտնելու համար.
Հայտնի հաղորդագրությամբ M- ն պետք է դժվար լինի գտնել մեկ այլ հաղորդագրություն M 'Հեշի գործառույթի նույն արժեքով, ինչպես աղբյուրի հաղորդագրությունը.
Պետք է դժվար լինի գտնել ցանկացած զույգ պատահական տարբեր հաղորդագրություններ նույն հեշ գործառույթով:

Ստեղծեք HASH գործառույթ, որը բավարարում է նշված բոլոր պահանջները հեշտ գործ չէ: Անհրաժեշտ է նաեւ հիշել, որ գործառույթի գործառույթը ստացվում է կամայական չափի գործառույթի վրա, եւ հեշ արդյունքը չպետք է հավասար լինի այս տարբեր չափերի համար:

Ներկայումս գործնականում, մուտքային հաղորդագրության մշակման գործառույթները օգտագործվում են որպես հեշ գործառույթներ, եւ հաշվում է հաշիվը `տիպի կախվածության վրա մուտքային հաղորդագրության յուրաքանչյուր մ-ի համար

h i \u003d H (m i, h i-1)

որտեղ H I-1- ը ստացված արդյունքն է, երբ ստացվում է հեշ գործառույթը հաշվարկելիս Նախորդ բլոկը Մուտքային տվյալներ:

Արդյունքում, Hash Function Contem H N N- ը բոլոր N մուտքային բլոկներից գործառույթ է:

Օգտագործեք բլոկային ալգորիթմների կոդավորումը `HASH գործառույթ ձեւավորելու համար

Կարող եք օգտագործել բլոկ, որպես հեշ գործառույթ: Եթե \u200b\u200bբլոկային ալգորիթմի կողմից օգտագործվող բլոկները, ապա դրա հիման վրա HASH գործառույթը հուսալի կլինի:

Բլոկի ալգորիթմ օգտագործելու ամենապարզ միջոցը `Hash ծածկագիրը ստանալու համար հաղորդագրության կոդավորումը CBC ռեժիմում: Այս դեպքում հաղորդագրությունը ներկայացված է որպես բլոկների հաջորդականություն, որի երկարությունը հավասար է կոդավորման ալգորիթմի միավորի երկարությանը: Անհրաժեշտության դեպքում վերջին միավորը լրացվում է աջ զրո, որպեսզի ցանկալի երկարության միավորը լինի: Hash- ը կլինի վերջին կոդավորված տեքստային բլոկը: Առանձնացված բլոկային կոդավորման հուսալի ալգորիթմի օգտագործումը, արդյունքում ստացված հեշ արժեքը կունենա հետեւյալ հատկությունները.

Գրեթե անհնար է, առանց իմանալու տեղեկատվության բացման համար Հաշմանդգության հիմնական հաշվարկը
Դա գործնականում անհնար է առանց իմանալու կոդավորման հիմնական ընտրությունը նշված հեշ արժեքի տակ:

Այս եղանակով ձեւավորված տանիքի արժեքը սովորաբար կոչվում է imitovka կամ վավերական եւ օգտագործվում էր հաղորդագրության ամբողջականությունը ստուգելու համար: Այսպիսով, սիմուլյատորը վերահսկման համադրություն է, որը կախված է բաց տվյալների եւ գաղտնի բանալիների մասին: Իմիտովկա օգտագործելու նպատակը տեղեկատվության զանգվածում բոլոր պատահական կամ դիտավորյալ փոփոխությունները հայտնաբերելն է: Հաշմանդամի կողմից մուտքագրման հաղորդագրության մշակման ժամանակ ստացված արժեքը կցվում է հաղորդագրությանը այն պահին, երբ հայտնի է, որ հաղորդագրությունը ճիշտ է: Ստացողը ստուգում է հաղորդագրության ամբողջականությունը `հաշվարկելով ստացված հաղորդագրության իմիտանությունը եւ այն համեմատելով արդյունքում ստացված Հեշի օրենսգրքի հետ, որը պետք է փոխանցվի անվտանգ ձեւով: Դրանցից մեկը Ապահով եղանակներ Միգուցե Imitovka- ի կոդավորումը Փակ բանալին Ուղարկող, այսինքն. Ստորագրություն ստեղծելը: Հնարավոր է նաեւ կոդավորել ստացված HASH կոդային ալգորիթմը սիմետրիկ կոդավորման համար, եթե ուղարկողը եւ ստացողը ունեն սիմետրիկ կոդավորման ընդհանուր բանալին:

Imitovka- ն ձեռք բերելու եւ օգտագործելու նշված գործընթացը նկարագրված է ներքին ստանդարտ ԳՕՍՏ 28147-89: Ստանդարտ առաջարկներ `օգտագործելու համար նախատեսված բլոկի ավելի երիտասարդ 32 բիթը, որը ձեռք է բերվել CIPER բլոկի ճարմանդային ռեժիմում գտնվող ամբողջ հաղորդագրության կոդավորման արդյունքում` փոխանցվող հաղորդագրության ամբողջականությունը դիտարկելու համար: Նույն կերպ ցանկացած բլոկ կարող է օգտագործվել Imitavka առաջացնելու համար Սիմետրիկ կոդավորման ալգորիթմ.

Բլոկային ծածկագիր օգտագործելու եւս մեկ հնարավոր միջոց հետեւյալն է. Աղբյուրի հաղորդագրությունը վերամշակվում է շարքի բլոկներում: Վերջին բլոկը, անհրաժեշտության դեպքում, լրացնում է Զերոսը, երբեմն վերջին թաղամասում դուք վերագրում եք հաղորդագրության երկարությունը ձեւով Երկուական համարներ, Յուրաքանչյուր փուլում կոդավորեք նախորդ փուլում ձեռք բերված հեշի արժեքը, ներկայացնելով ներկայիս հաղորդագրության բլոկը որպես բանալին: Վերջին մուտքագրված գաղտնագրված արժեքը կլինի վերջնական հեշը:

Փաստորեն, բլոկային ծածկագիր օգտագործելու համար մի քանի այլ սխեմաներ `Hash- ի գործառույթը ձեւավորելու համար: Թող M- ն լինի աղբյուրի բլոկի միավոր, HI - I- մակարդակի փուլում հեշ գործառույթի արժեքը, F- ի կոդավորման ալգորիթմի բլոկը, որն օգտագործվում է պարզ փոխարինման ռեժիմով. Օրինակ, հետեւյալ HASH գործառույթի ձեւավորման սխեմաները.

Այս բոլոր դիագրամներում ստեղծված հեշ արժեքի երկարությունը ծածկագրման ընթացքում հավասար է բլոկի երկարությանը: Այս ամենը, ինչպես նաեւ մի քանի այլ սխեմաներ `բլոկային ալգորիթմ օգտագործելու համար ծածկագրման համար հաշմանդամ արժեքները հաշվարկելու համար կարող են օգտագործվել գործնականում:

Բլոկի ալգորիթմների հիման վրա նախագծված Hash- ի գործառույթների հիմնական թերությունը համեմատաբար ցածր արագություն Աշխատել: Պահանջվող ծպտյալը կարող է ապահովվել նաեւ մուտքային տվյալների վրա ավելի փոքր թվով գործողությունների համար: Գոյություն ունեն Scrathently- ի համար, որոնք նախագծվել են ինքնուրույն, որոնք հիմնված են ծիլից, հիմնվելով ծպտյալ դիմադրության պահանջներից (դրանցից ամենատարածվածը `MD5, SHA-1, SHA-2 եւ GOST R 34.11-94):

Ինչ է hash?Հաշի գործառույթը կոչվում է կարճ ժամանակահատվածում տեղեկատվության մաթեմատիկական վերափոխում:

Ինչու է ձեզ հարկավոր:Հաշմանդամների գործառույթների միջոցով վերլուծություն հաճախ օգտագործվում է կարեւոր ֆայլերի ամբողջականությունը դիտարկելու համար: օպերացիոն համակարգ, կարեւոր ծրագրեր, կարեւոր տվյալներ: Վերահսկողությունը կարող է իրականացվել ինչպես անհրաժեշտ եւ կանոնավոր կերպով:

Ինչպես է դա արվել:Սկզբում որոշեք, թե որ ամբողջականությունը պետք է վերահսկվի ֆայլերը: Յուրաքանչյուր ֆայլի համար հաշվարկվում է հաշվարկել իր հեշի արժեքը հատուկ ալգորիթմի վրա `արդյունքը պահպանելիս: Պահանջվող ժամանակից հետո նման հաշվարկ է արվում, եւ արդյունքները համեմատվում են: Եթե \u200b\u200bարժեքները տարբերվում են, նշանակում է, որ ֆայլում պարունակվող տեղեկատվությունը փոխվել է:

Ինչ հատկանիշներ պետք է ունենան HASH գործառույթ:

Պետք է կարողանա կատարել ամրագրված կամայական երկարության տվյալների վերափոխումները.
պետք է ունենա բաց ալգորիթմ, որպեսզի իր ծպտյալոսկոպը ուսումնասիրվի.
Պետք է միակողմանի լինի, այսինքն, չպետք է լինեն մաթեմատիկական հնարավորություններ `որոշելով աղբյուրի տվյալները.
Պետք է «դիմադրեն» հակամարտություններին, այսինքն, այն չպետք է նույն արժեքները տա տարբեր մուտքային տվյալներով.
չպետք է մեծ հաշվարկային ռեսուրսներ պահանջի.
Մուտքագրման տվյալների փոքր փոփոխությամբ, արդյունքը պետք է զգալիորեն փոխվի:

Որոնք են հանրաճանաչ հեշինգ ալգորիթմները:Ներկայումս օգտագործվում են հետեւյալ HASH գործառույթները.

CRC - ցիկլային ավելորդ կոդ կամ ստուգում: Ալգորիթմը շատ պարզ է, ունի մեծ թվով Տատանումներ, կախված պահանջվող ելքային երկարությունից: Ոչ թե cryptographic!
MD 5-ը շատ տարածված ալգորիթմ է: Նրա նման Նախորդ տարբերակը MD 4- ը գաղտնագրային գործառույթ է: Hesha Size 128 Bits.
SHA -1- ը նույնպես շատ տարածված գաղտնագրական խոստովան է: Hesha Size 160 Bits.
ԳՕՍՏ Ռ 34.11-94 - Ռուսական գաղտնագրային ստանդարտ `հաշմանդամների գործառույթները հաշվարկելու համար: Hesha Size 256 բիթ:

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

Ինչն է ավելի հարմար հաշվել Hash- ին:Այժմ կան մեծ թվով նմանատիպ կոմունալ ծառայություններ ինչպես վճարովի, այնպես էլ անվճար օգտագործման համար: Ես անձամբ սիրում էի Հեշթաբը: Նախ, տեղադրման ընթացքում կոմունալը ներկառուցված է ներդիրի տեսքով, ֆայլերի հատկություններին, երկրորդը, թույլ է տալիս ընտրել մեծ քանակությամբ հսահող ալգորիթմներ, իսկ երրորդը անվճար է մասնավոր ոչ առեւտրային օգտագործման համար:

Ինչ է ռուսերենը:Ինչպես վերը նշվեց Ռուսաստանում, կա Hashing Gost R 34.11-94 ստանդարտ, որն օգտագործվում է ամենուրեք տեղեկատվական անվտանգության գործիքների շատ արտադրողների: Այս միջոցներից մեկը բնօրինակ վիճակի ամրագրման եւ վերահսկման ծրագիրն է: Ծրագրային փաթեթ "Ուղղել". Այս ծրագիրը SZI- ի կիրառման արդյունավետությունը վերահսկելու միջոց է:

Fix (2.0.1 տարբերակ 2.0.1) 9x / NT / 2000 / XP

Հաշվարկեք նշված ֆայլերի ստուգումները `իրականացված 5 ալգորիթմներից մեկի կողմից:
Ծրագրային փաթեթի բնօրինակ վիճակի ամրագրում եւ հետագա վերահսկողություն:
Ծրագրային փաթեթի վարկածների համեմատություն:
Կատալոգների ամրագրում եւ վերահսկում:
Նշված ֆայլերի (դիրեկտորիաների) փոփոխությունների մոնիտորինգ:
Զեկույցների ձեւավորում TXT, HTML, SV ձեւաչափերով:
Ապրանքը FSTEC- ի վկայագիր ունի NDV 3-ի թիվ 913-ը մինչեւ 2013 թվականի հունիսի 1-ը:

Եվ ինչպես eds- ին:Օգտագործողի գաղտնի բանալու հետ միասին գործառույթի հաշվարկման արդյունքը մտնում է գաղտնագրային ալգորիթմի մուտքագրում, որտեղ հաշվարկվում է էլեկտրոնային թվային ստորագրությունը: Խստորեն ասած, Hash- ի գործառույթը EDS ալգորիթմի մաս չէ, բայց հաճախ դա կատարվում է հատուկ, որպեսզի հարձակումը բացառվի հանրային բանալին:

Ներկայումս էլեկտրոնային առեւտրի շատ դիմումներ թույլ են տալիս պահպանել օգտագործողի գաղտնի բանալին փակ նշանների տարածքում (Rutoken, Etroken) առանց այն այնտեղից հանելու տեխնիկական ունակության: Նշանն ինքնին ունի շատ սահմանափակ հիշողություն, որը չափվում է կիլոբայթներով: Փաստաթուղթը ստորագրելու համար հնարավոր չէ փաստաթուղթը փոխանցել նշանին, այլ փաստաթղթի հաշմանդամը փոխանցել նշանին եւ ED- ներին `ED- ները շատ պարզ է:

Հարցեր.

1. Հեշի գործառույթի հայեցակարգը:

2. Օգտագործեք բլոկային ալգորիթմներ կոդավորման համար `հեշ գործառույթ ձեւավորելու համար:

3. Ալգորիթմների վերանայում `հեշ գործառույթների ձեւավորման համար:

1. Հեշի գործառույթի հայեցակարգ

Hash գործառույթ(Hash գործառույթ) կոչվում է մաթեմատիկական կամ այլ գործառույթ, որը կամայական երկարության տողերի համար հաշվարկում է որոշակի ամբողջ թիվ կամ ֆիքսված երկարության մի շարք այլ շարք: Մաթեմատիկորեն, դա կարող է գրվել այսպես.

Հ. \u003d H (մ) ,

Որտեղ Տղամարդ - Աղբյուրի հաղորդագրությունը, որը կոչվում է երբեմն Նվեր , բայց Հ. - Արդյունքը, որը կոչվում է Հաշի գործառույթի արժեքը (ինչպես նաեւ Հեշի ծածկագիր կամ digest հաղորդագրություն (անգլերենից: Հաղորդագրություն Digest.)).

Հաշմանդամի իմաստը նմուշի բնորոշ առանձնահատկությունն է `հեշ գործառույթի իմաստը: Այս արժեքը սովորաբար ունի որոշակի ֆիքսված չափ, օրինակ, 64 կամ 128 բիթ: HASH ծածկագիրը կարող է հետագայում վերլուծվել ցանկացած առաջադրանքի լուծման համար: Օրինակ, հեշինգը կարող է օգտագործվել տվյալների համեմատության համար. Եթե երկու հեշ կոդավորվում են, զանգվածները երաշխավորված են. Եթե \u200b\u200bնույն - զանգվածները, ամենայն հավանականությամբ, նույնն են: Ընդհանրապես, աղբյուրի տվյալների եւ HASH ծածկագրի միջեւ միանշանակ նամակագրությունը պայմանավորված չէ այն փաստով, որ Hash- ի գործառույթների քանակը միշտ էլ պակաս է, քան մուտքային ընտրանքները: Հետեւաբար, կան բազմաթիվ մուտքային հաղորդագրություններ, որոնք տալիս են նույն հեշ ծածկագրերը (նման իրավիճակները կոչվում են Կոլիզիա ): Բախումների առաջացման հավանականությունը կարեւոր դեր է խաղում Հաշի գործառույթների որակը գնահատելու գործում:

Հեշի գործառույթները լայնորեն օգտագործվում են ժամանակակից գաղտնագրման մեջ:

Հախի ամենապարզ գործառույթը կարող է կազմվել «Մոդուլի 2» գործողության միջոցով հետեւյալ կերպ. Մենք ստանում ենք մուտքային տող, մենք բոլոր բայթերը ծալում ենք մոդուլի 2-ով, եւ բայթը բացի այդ արժեքն է: Հեշի գործառույթի երկարությունը կլինի այս դեպքում 8 բիթ, անկախ մուտքային հաղորդագրության չափից:

Օրինակ, թող թվային դիտում թարգմանված բնօրինակ հաղորդագրությունը, հետեւյալը (hexadecimal ձեւաչափով).

2 Բ1 4 A9 5 Զ.Ե.4

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Արդյունք. 0010 1101 կամ 2 Գցել Եվ դա կլինի HASH գործառույթի արժեքը:

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

Հետեւաբար, Test Hash գործառույթը հարմար չէ գաղտնագրական ծրագրերի համար: Գաղտնագրման մեջ HASH գործառույթը լավ է համարվում, եթե դժվար է ստեղծել երկու տեսակի նույն հեշ գործառույթով, ինչպես նաեւ, եթե գործառույթի արտադրանքի բացումը չունի:

Մենք ձեւակերպում ենք Cryptograpic Hash գործառույթների հիմնական պահանջները.

· HASH գործառույթը պետք է կիրառելի լինի ցանկացած չափի հաղորդագրության համար.

· Գործառույթի արժեքի հաշվարկը պետք է արագ կատարվի.

· Հաշի գործառույթի հայտնի իմաստով, այն պետք է լինի դժվար (գրեթե անհնար) `համապատասխան նախատիպ գտնելու համար Տղամարդ ;

· Հայտնի հաղորդագրությամբ Տղամարդ Պետք է դժվար լինի գտնել մեկ այլ հաղորդագրություն: Մ ' Հաշմանդամի նույն արժեքով, ինչպես աղբյուրի հաղորդագրությունը.

· Պետք է դժվար լինի գտնել ցանկացած զույգ պատահական տարբեր հաղորդագրություններ նույն HASH գործառույթով:

Ներկայումս գործնականում գործառույթները օգտագործվում են որպես հեշ գործառույթներ, վերամշակում են միավորի մուտքի հաղորդագրության բլոկը եւ հաշվարկելով Hash- ՈՂՋՈՒ՜ՅՆ. Յուրաքանչյուր բլոկի համար Մ Մուտքագրեք հաղորդագրությունը կախվածության վրա

h i \u003d H (m i, h i-1)

Որտեղ Հ I-1 - ներմուծման տվյալների նախորդ բլոկի համար հաշմանդամ գործառույթը հաշվարկելիս ստացված արդյունքը:

Արդյունքում, HASH գործառույթի եկամտաբերությունը Հ Ն. բոլորից գործառույթ է Ն. Մուտքային բլոկներ:

2. Օգտագործեք բլոկային ալգորիթմների կոդավորումը `Hash գործառույթը կազմելու համար:

Որպես HASH գործառույթ, սիմետրիկ կոդավորման համար կարող եք օգտագործել բլոկային ալգորիթմ: Եթե \u200b\u200bօգտագործված բլոկային ալգորիթմը կրիպտոգրաֆիկ փորվածք է, ապա դրա հիման վրա հեշագործ գործառույթը հուսալի կլինի:

Հասկլե ծածկագիր ստանալու համար բլոկային ալգորիթմ օգտագործելու ամենապարզ միջոցը CBC ռեժիմում հաղորդագրության կոդավորումը է ( CIPER բլոկի շղթաներ - Ciphertex ճարմանդային ռեժիմ): Այս դեպքում հաղորդագրությունը ներկայացված է որպես բլոկների հաջորդականություն, որի երկարությունը հավասար է կոդավորման ալգորիթմի միավորի երկարությանը: Անհրաժեշտության դեպքում վերջին միավորը լրացվում է աջ զրո, որպեսզի ցանկալի երկարության միավորը լինի: Hash- ը կլինի վերջին կոդավորված տեքստային բլոկը: Հուսալի բլոկի կոդավորման ալգորիթմի օգտագործման ենթակա, ձեռք բերված Hash- ը կունենա հետեւյալ հատկությունները.

· Գործնականորեն անհնար է առանց իմանալու տեղեկության բաց զանգվածի համար Հաշի արժեքի կոդավորման հիմնական հաշվարկը.

Այն գործնականում անհնար է առանց իմանալու կոդավորման հիմնական ընտրությունը `բացման արժեքի համար:

Այս եղանակով ձեւավորված խոնարհությունը սովորաբար կոչվում է imitovka կամ վավերական եւ օգտագործվում էր հաղորդագրության ամբողջականությունը ստուգելու համար: Այսպիսով, սիմուլյատորը վերահսկման համադրություն է, որը կախված է բաց տվյալների եւ գաղտնի բանալիների մասին: Իմիտովկա օգտագործելու նպատակը տեղեկատվության զանգվածում բոլոր պատահական կամ դիտավորյալ փոփոխությունները հայտնաբերելն է: Հաշմանդամի կողմից մուտքագրման հաղորդագրության մշակման ժամանակ ստացված արժեքը կցվում է հաղորդագրությանը այն պահին, երբ հայտնի է, որ հաղորդագրությունը ճիշտ է: Ստացողը ստուգում է հաղորդագրության ամբողջականությունը `հաշվարկելով ստացված հաղորդագրության իմիտանությունը եւ այն համեմատելով արդյունքում ստացված Հեշի օրենսգրքի հետ, որը պետք է փոխանցվի անվտանգ ձեւով: Այս անվտանգ եղանակներից մեկը կարող է կոդավորիչի իմիտարկությունը գաղտնագրել փակ ստեղնով, այսինքն: Ստորագրություն ստեղծելը: Հնարավոր է նաեւ կոդավորել ստացված HASH կոդային ալգորիթմը սիմետրիկ կոդավորման համար, եթե ուղարկողը եւ ստացողը ունեն սիմետրիկ կոդավորման ընդհանուր բանալին:

Imitovka- ն ձեռք բերելու եւ օգտագործելու նշված գործընթացը նկարագրված է ներքին ստանդարտ ԳՕՍՏ 28147-89: Ստանդարտ առաջարկներ `օգտագործելու համար նախատեսված բլոկի ավելի երիտասարդ 32 բիթը, որը ձեռք է բերվել CIPER բլոկի ճարմանդային ռեժիմում գտնվող ամբողջ հաղորդագրության կոդավորման արդյունքում` փոխանցվող հաղորդագրության ամբողջականությունը դիտարկելու համար: Նույն կերպ, սիմետրիկ կոդավորման ցանկացած բլոկային ալգորիթմ կարող է օգտագործվել Imitavka ձեւավորելու համար:

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

Այսպիսով, եթե սովորական հաղորդագրությունների գաղտնագրման սխեման Տղամարդ Օգտագործելով Block CIPER Զ. Հիմնականում Դեպի Մենք ձայնագրեցինք որպես E \u003d F (M, K) Այնուհետեւ Hash Code սխեման Հ. Համաձայն վերը նկարագրված ալգորիթմի, կարող եք պատկերացնել, թե ինչպես

ՈՂՋՈՒ՜ՅՆ. = Զ. ( ՈՂՋՈՒ՜ՅՆ. -1 , Տղամարդ )

Որպես նախնական HASH կոդ Հ 0: Վերցրեք որոշակի հաստատուն: Գաղտնագրումը կատարվում է պարզ փոխարինման ռեժիմով: Թեթլ նշված մեթոդը Բլոկի չափը համընկնում է բանալու երկարության հետ, եւ հեշի արժեքի չափը կլինի միավորի երկարությունը:

Հնարավոր է նաեւ բլոկային ծածկագրեր օգտագործելու եւս մեկ եղանակ, հնարավոր է նաեւ. Հաղորդագրության տարրերը կոդավորված են նախորդ փուլում ձեռք բերված հեշ արժեքներով.

ՈՂՋՈՒ՜ՅՆ. = Զ. ( Տղամարդ , ՈՂՋՈՒ՜ՅՆ. -1 ,)

Փաստորեն, բլոկային ծածկագիր օգտագործելու համար մի քանի այլ սխեմաներ `Hash- ի գործառույթը ձեւավորելու համար: Թե Մ - աղբյուրի հաղորդագրության բլոկ, ՈՂՋՈՒ՜ՅՆ. - Հեշի գործառույթի արժեքը Ես - բեմ, Զ. - Բլոկի ալգորիթմը, որը օգտագործվում է պարզ փոխարինման ռեժիմում օգտագործվող կոդավորման համար. Մոդուլի հավելյալ շահագործում 2. Այն ժամանակ, հնարավոր է, օրինակ, սխեմաներ

Բլոկի ալգորիթմների հիման վրա նախագծված Hash- ի գործառույթների հիմնական թերությունը համեմատաբար ցածր արագություն է: Պահանջվող ծպտյալը կարող է ապահովվել նաեւ մուտքային տվյալների վրա ավելի փոքր թվով գործողությունների համար: Կան ավելի արագ հալվող ալգորիթմներ (ամենատարածվածները `MD5, SHA-1, SHA-2 եւ GOST R 34.11-94):

3. Ալգորիթմների վերանայում `հեշ գործառույթների ձեւավորման համար:

Ներկայումս տարբեր հատուկ ալգորիթմներ են առաջարկվում եւ գործնականում օգտագործվում է Հաշի գործառույթը հաշվարկելու համար: Առավել հայտնի ալգորիթմներն են MD5, SHA-1, SHA-2 եւ SHA- ի այլ վարկածներ, ինչպես նաեւ տեղական ալգորիթմը, որը նկարագրված է ԳՕՍՏ Ռ 34.11-94-ում:

Ալգորիթմ MD5 Հայտնվեց քսաներորդ դարի սկզբին 90-ականների սկզբին, MD4 Hash- ի ձեւավորման ալգորիթմի բարելավման արդյունքում: Նշանները «MD» անունով «MEN MESS» Digest - հաղորդագրության ամփոփում: Ալգորիթմների MD4 եւ MD5 - R. RIVEST (R.RIVEST) հեղինակ: MD5 օգտագործման արդյունքում կամայական հաղորդագրության համար ձեւավորվում է 128 բիթանոց հեշ: Մուտքագրման տվյալները մշակվում են 512 բիթ բլոկներով: Ալգորիթմը տարրական օգտագործում է Տրամաբանական գործողություններ (Inversion, Concition, մոդուլի 2, ցիկլային տեղաշարժեր եւ այլն), ինչպես նաեւ սովորական թվաբանական հավելում: Ալգորիթմի այս տարրական գործառույթների համապարփակ կրկնությունը ապահովում է, որ արդյունքը մշակվելուց հետո լավ խառնված է: Հետեւաբար, քիչ հավանական է, որ պատահականորեն ընտրված երկու հաղորդագրություն ունեն նույն Հեշի ծածկագիրը: MD5 ալգորիթմը ունի հետեւյալ գույքը. Արդյունքում HASH արժեքի յուրաքանչյուր բիթը յուրաքանչյուր մուտքի բիթերից գործառույթ է: Համարվում է, որ MD5- ը ամենաուժեղ հեշ գործառույթն է `128-բիթանոց հեշ արժեքի համար:

Ալգորիթմ Սա Ապահով HASH ալգորիթմ - անվտանգ հեշ-ալգորիթմ) մշակվել է Միացյալ Նահանգների ստանդարտների եւ տեխնոլոգիաների ազգային ինստիտուտի (Nist) եւ հրապարակվել է որպես 1993 թվականին որպես ամերիկյան դաշնային տեղեկատվության ստանդարտ: SHA-1, ինչպես նաեւ MD5, հիմք ընդունելով MD4 ալգորիթմի վրա: SHA-1- ը կազմում է 160 բիթանոց հեշ, հիմնվելով 512 բիթ բլոկների աղբյուրի վերամշակման վրա: SHA-1 ալգորիթմը օգտագործում է նաեւ պարզ տրամաբանական եւ թվաբանական գործողություններ: SHA-1- ի MD5- ի միջեւ ամենակարեւոր տարբերությունն այն է, որ Hash Code Sha-1- ը 32 բիթ է ավելի երկար, քան Hash Code MD5- ը: Եթե \u200b\u200bենթադրենք, որ երկու ալգորիթմները նույնն են ծպտյալության համար դժվարության մեջ, ապա SHA-1- ը ավելի դիմացկուն ալգորիթմ է: Օգտագործելով հարձակումը կոպիտ ուժի միջոցով (ճակատային հարձակումը), ավելի դժվար է ստեղծել կամայական հաղորդագրություն, որն ունի տվյալ HASH ծածկագիր, եւ նույն Հեշի ծածկագիրը ունեցող երկու հաղորդագրություն է ստեղծելը:

2001-ին Միացյալ Նահանգների ստանդարտների եւ տեխնոլոգիաների ազգային ինստիտուտը որդեգրել է երեք հեշ գործառույթ, որպես Հաշվիչի ավելի մեծ երկարությամբ ստանդարտ, քան SHA-1- ում: Հաճախ, այս Hash- ի գործառույթները կոչվում են SHA-2 կամ SHA-256, SHA-384 եւ SHA-512 (վերնագրում նշվում է ալգորիթմների կողմից ստեղծված հեշի կոդի): Այս ալգորիթմները տարբերվում են ոչ միայն ստեղծված HASH ծածկագրի երկարությամբ, այլեւ օգտագործվում են ներքին գործառույթներ եւ վերամշակված բլոկի երկարություն (SHA-256-ում `512 եւ SHA-384 եւ SHA-512 բլոկի երկարությամբ) 1024 բիթ է): Sha Algorithm- ի աստիճանական բարելավումները հանգեցնում են նրա ծպտյալ դիմադրության աճի: Չնայած միմյանցից քննարկվող ալգորիթմների տարբերություններին, բոլորն էլ SHA-1 եւ MD4- ի հետագա զարգացումն են եւ ունեն նման կառույց:

Ռուսաստանում ընդունվում է ԳՕՍՏ P34.11-94, որը ներքին ստանդարտ է Hash- ի գործառույթների համար: Դրա կառուցվածքը բավականին տարբերվում է SHA-1.2 կամ MD5 ալգորիթմների կառուցվածքից, որոնք հիմնված են MD4 ալգորիթմի վրա: Ալգորիթմ ԳՕՍՏ Ռ 34.11-94- ի կողմից ստեղծված Hash ծածկագրի երկարությունը 256 բիթ է: Ալգորիթմը հաջորդաբար վերամշակվում է աղբյուրի հաղորդագրությամբ, 256 բիթի բլոկներով աջ ձախ: Ալգորիթմի պարամետրը Hash- ի մեկնարկային վեկտորն է. Կամայական ֆիքսված արժեքը նույնպես 256 բիթ է: Ալգորիթմում, ԳՕՍՏ Ռ 34.11-94, permutation- ի, shear- ի, թվաբանական հավելման գործառնություններ, մոդուլի հավելում 2. Ինչպես Օժանդակ գործառույթ ԳՕՍՏ 34.11-94-ը օգտագործում է ալգորիթմ, ըստ ԳՕՍՏ 28147-89-ի `պարզ փոխարինման ռեժիմով:

4. Հաշմանդների գործառույթների պահանջները

HASH գործառույթը կոչվում է միակողմանի գործառույթ, որը նախատեսված է մարսողական կամ «մատնահետք» ֆայլը, հաղորդագրությունները կամ տվյալների որոշ բլոկ ստանալու համար:

Հեշի ծածկագիրը ստեղծվում է գործառույթի կողմից Ն. :

h \u003d H (մ)

Որտեղ Տղամարդ կամայական երկարության հաղորդագրություն է եւ Հ. Դա ֆիքսված երկարության Hash կոդ է:

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

Hash գործառույթ Ն. Սա օգտագործվում է հաղորդագրությունները հաստատելու համար պետք է ունենան հետեւյալ հատկությունները.

1. HASH գործառույթ Ն. Այն պետք է կիրառվի ցանկացած երկարության տվյալների բլոկի վրա:

2. HASH գործառույթ Ն. Ստեղծում է ֆիքսված երկարության ելք:

3. N (մ) համեմատաբար հեշտությամբ (բազմամյա ժամանակ) հաշվարկվում է ցանկացած արժեքի համար Տղամարդ .

4. ցանկացած տրված HASH կոդի համար Հ. Պարզապես անհնար է գտնել Տղամարդ այնպիսին է, որ Ժ (մ) \u003d ժ .

5. ցանկացած տրված Հ. Դա հաշվարկիչորեն անհնար է գտնել դա

Հ. (y) \u003d H (x):

6. Հաշվարկայինորեն հնարավոր չէ գտնել կամայական զույգ ( Հ. , յ. ) այնպիսին է, որ H (y) \u003d H (x) .

Առաջին երեք հատկությունները պահանջում են HASH գործառույթ `ցանկացած հաղորդագրության համար Hash կոդ ստեղծելու համար:

Չորրորդ գույքը որոշում է HASH գործառույթների միակողմանիության պահանջը. Հեշտ է ստեղծել այս հաղորդագրության համար Hash կոդ, բայց այս Հեշի կոդի վերաբերյալ հաղորդագրությունը վերականգնելը անհնար է: Այս գույքը կարեւոր է, եթե հեշ գործառույթը օգտագործելը ստուգում է գաղտնի արժեք: Այնուամենայնիվ, գաղտնի արժեքը չի կարող ուղարկվել, սակայն, եթե Hash գործառույթը միակողմանի չէ, թշնամին կարող է հեշտությամբ բացահայտել հետեւյալ արժեքը: Փոխանցումը փոխելիս հարձակվողը հաղորդագրություն է ստանում Տղամարդ եւ Hash ծածկագիրը C \u003d H (sab || մ) , Եթե \u200b\u200bհարձակվողը կարող է շրջվել հեշ գործառույթը, ապա, հետեւաբար, այն կարող է ստանալ Սաբ || M \u003d H - 1 (C) , Քանի որ հարձակվողը այժմ գիտի եւ Տղամարդ մի քանազոր Սաբ || Տղամարդ , ստացեք Սաբ. բավականին պարզ:

Հինգերորդ գույքն ապահովում է, որ անհնար է գտնել մեկ այլ հաղորդագրություն, որի հաշմանդամ գործառույթի արժեքը համընկավ HASH գործառույթի արժեքի հետ Այս հաղորդագրությունը, Սա խանգարում է վավերականին կեղծել կոդավորված Hash ծածկագիրը օգտագործելիս: Այս դեպքում հակառակորդը կարող է կարդալ հաղորդագրությունը եւ, հետեւաբար, ստեղծեք դրա HASH ծածկագիրը: Բայց քանի որ թշնամին գաղտնի բանալին չունի, այն չունի հաղորդագրությունը փոխելու հնարավորություն, որպեսզի ստացողը չգտնի: Եթե \u200b\u200bայս գույքը չկատարվի, հարձակվողը հնարավորություն ունի իրականացնել գործողությունների հետեւյալ հաջորդականությունը. Հաղորդագրությունը եւ դրա գաղտնագրված Hash ծածկագիրը հաշիվը հաշվարկեք նույն Հեշի կոդով, փոխարինեք այլընտրանքային հաղորդագրությունը դեպի կեղծ: Քանի որ այս հաղորդագրությունների Hash ծածկագրերը համընկնում են, ստացողը չի հայտնաբերելու փոխարինում:

Hash- ի գործառույթը, որը բավարարում է առաջին հինգ հատկությունները, կոչվում է պարզ կամ թույլ հեշ գործառույթ: Եթե \u200b\u200bվեցերորդ գույքը կատարվի, ապա այս գործառույթը կոչվում է ուժեղ հեշ գործառույթ: Վեցերորդ գույքը պաշտպանում է դասի գրոհներից, որոնք հայտնի են որպես հարձակման «ծննդյան օր»:

5. Պարզ հեշ գործառույթներ

Ամբողջ Հաշի գործառույթները կատարվում են հետեւյալ կերպ. Մուտքային արժեքը (հաղորդագրությունը, ֆայլը եւ այլն) համարվում են հաջորդականություն Ն. - Blocks. Մուտքի արժեքը վերամշակվում է հաջորդականորեն արգելափակում միավորի հետեւում եւ ստեղծվում է: Տղամարդ -Բեդ Հեշի ծածկագրի արժեքը:

HASH գործառույթի ամենապարզ օրինակներից մեկը յուրաքանչյուր բլոկի XOR- ի կողմից է.

I- ի հետ: - Ես BIT HASH ծածկագիր, 1 <= i <= n .

Կ. - Թիվ Ն. - Blocks- ի մուտքը:

Բ IJ. – Ես Bit B. Ամբ. Բլոկ:

Այնուհետեւ ամբողջ հաղորդագրությունը կոդավորված է, ներառյալ HASH ծածկագիրը, CCS ռեժիմում `կոդավորված բլոկներ ստեղծելու համար Y1, Y2, ..., YN + 1: Ըստ սահմանման, ես ունեմ.

Բայց XN + 1- ը HASH ծածկագիր է.

Քանի որ նախորդ հավասարության բաղադրիչները կարող են հաշվարկվել ցանկացած կարգով, հետեւաբար, Hash ծածկագիրը չի փոխվի, եթե վերադասավորվեն կոդավորված բլոկները:

NIST- ի կողմից առաջարկվող նախնական ստանդարտը օգտագործեց պարզ XOR, որն օգտագործվել է 64-բիթանոց հաղորդագրության բլոկների համար, ապա ամբողջ հաղորդագրությունը կոդավորված է CCS ռեժիմով:

«Ծննդյան պարադոքս»

Նախքան ավելի բարդ բաճկոնների գործառույթները հաշվի առնելը անհրաժեշտ է վերլուծել մի հատուկ հարձակումը պարզ հեշ գործառույթների վրա:

Այսպես կոչված «ծննդյան պարադոքսը» հետեւյալն է. Ենթադրենք, HASH գործառույթի ելքային արժեքների քանակը Ն. հավասարապես Ն. , Ինչ պետք է լինի համարը Կ. Հատուկ արժեքին X. եւ արժեքներ Y1 YK Առնվազն մեկ yi կատարվել է հավասարության հավասարություն

H (x) \u003d H (y)

Կլիներ ավելի քան 0,5:

Մեկի համար Յ. հավանականությունը, որ H (x) \u003d H (y) , հավասար 1 / Ն. .

Համապատասխանաբար, հավանականությունը, որ , հավասար 1 - 1 / n .

Եթե \u200b\u200bստեղծում եք Կ. Արժեքներ, հավանականությունը, որ ոչ մի զուգահեռ չի լինի հավասար նշանակության արտադրանքին, որը համապատասխանում է մեկ արժեքին, այսինքն. (1 - 1 / N) k .

Հետեւաբար, առնվազն մեկ զուգադիպության հավանականությունը հավասար է

1 - (1 - 1 / N) k

Այսպիսով, մենք պարզեցինք, որ դրա համար Տղամարդ -Bed Hash ծածկագիրը բավարար է ընտրելու համար 2M-1 Հաղորդագրություններ այնպես, որ Հեշի կոդերի համընկնումի հավանականությունը 0,5-ից մեծ էր:

Այժմ հաշվի առեք հետեւյալ առաջադրանքը. Նշեք P (n, k) հավանականությունը, որ մի շարք Կ. տարրեր, որոնցից յուրաքանչյուրը կարող է տեւել Ն. Արժեքներ, նույն արժեքներով առնվազն երկուսը կան: Ինչ պետք է լինի հավասար Կ. դեպի P (n, k) Ավելի շատ կլիներ 0,5 ?

Տարբեր եղանակների քանակը `տարրեր ընտրելու համար այնպես, որ այն չունի կրկնակի, հավասար

n (n - 1) ... (n - k + 1) \u003d n! / (n-k):

Տարրեր ընտրելու բոլոր հնարավոր եղանակները հավասար են n k.

Հավանականությունը, որ ոչ մի զույգ հավասար չէ n! / (N - k)! N k

Համապատասխանաբար կրկնօրինակ, համապատասխանաբար

1 - n! / (N-k)! Լ.Հ. P (n, k) \u003d 1 - n! / ((n - k)! x nk) \u003d 1 - (n x (n - 1) x ... x (n - k-1)) / nk \u003d 1 - [(n - 1) / n x (n-2) / n x ... x (n - k + 1) / n] \u003d n] \u003d 1 - [(1 - 1 / n) x (1 - 2 / n) x ... x (1 - (k-1) / n)]

Եթե \u200b\u200bHash ծածկագիրը ունի երկարություն Տղամարդ Քիչ, ես: Ընդունել 2 մ. Արժեքներ, T.

Նմանատիպ արդյունքը կոչվում է «Ծննդյան օրվա պարադոքս», քանի որ վերը նշված փաստարկների համաձայն, երկու անձի ծննդյան տարեդարձի հավանականության հավանականությունը `ավելի քան 0,5-ը, պետք է լինի խմբում ընդամենը 23 մարդ: Այս արդյունքը, կարծես, հիանալի է, քանի որ խմբում յուրաքանչյուր առանձին մարդու համար հավանականությունը, որ խմբում մեկ ուրիշի ծննդյան տարեդարձը համընկնում է իր ծննդյան օրվա հետ, բավականին փոքր է:

Եկեք վերադառնանք Հաշմանդամների գործառույթների հատկությունների քննարկմանը: Ենթադրենք, որ օգտագործվում է 64-բիթանոց հեշ ծածկագիր: Կարելի է համարվել, որ այն բավականին բավարար է եւ, հետեւաբար, ապահով երկարություն HASH ծածկագրի համար: Օրինակ, եթե կոդավորված Hash ծածկագիրը Դեպի Փոխանցվում է համապատասխան չկիրառված հաղորդագրությամբ Տղամարդ , ապա թշնամին պետք է գտնել Մ ' այնպիսին է, որ

N (մ) \u003d n (մ) ,

Հաղորդագրությունը փոխարինելու եւ ստացողին խաբելու համար: Միջին հաշվով, թշնամին պետք է ներխուժի 263 հաղորդագրություն, որպեսզի պարզվի, որ Hash ծածկագիրը հավասար է ընդհատվող հաղորդագրությանը:

Այնուամենայնիվ, հնարավոր են տարբեր տեսակի գրոհներ «Ծննդյան օրվա պարադոքս» -ում: Հնարավոր է հետեւյալ ռազմավարությունը.

1. Թշնամին ստեղծում է 2 մ / 2 Հաղորդագրությունների ընտրանքներ, որոնցից յուրաքանչյուրն ունի որոշակի որոշակի իմաստ: Թշնամին պատրաստում է նույն թվով հաղորդագրություններ, որոնցից յուրաքանչյուրը կեղծ է եւ նախատեսված է փոխարինել այս հաղորդագրությունը:

2. Հաղորդագրությունների երկու հավաքածուն համեմատում է նույն HASH ծածկագիրը ունեցող զույգ հաղորդագրությունների որոնման մեջ: «Ծննդյան օրվա պարադոքսին համապատասխան» հաջողության հավանականությունը ավելի մեծ է, քան 0.5: Եթե \u200b\u200bհամապատասխան զույգը չի գտնվել, ստեղծվում են լրացուցիչ աղբյուր եւ կեղծ հաղորդագրություններ, մինչեւ գոլորշին գտնվի:

3. Հարձակվողը ուղարկողին առաջարկում է հաղորդագրության նախնական տարբերակը ստորագրության համար: Այս ստորագրությունը այնուհետեւ կարող է կցվել ստացողին փոխանցելու կեղծ տարբերակին: Քանի որ երկու տարբերակները ունեն նույն հեշ ծածկագիրը, նույն ստորագրությունը կստեղծվի: Թշնամին վստահ կլինի հաջողության մեջ, նույնիսկ չգիտակցելով կոդավորման բանալին:

Այսպիսով, եթե օգտագործվում է 64-բիթանոց հեշ ծածկագիր, հաշվարկների անհրաժեշտ բարդությունը կազմում է 232:

Եզրափակելով, մենք նշում ենք, որ Հեշի օրենսգրքի երկարությունը պետք է լինի բավականին մեծ: 64 բիթի հավասար երկարությունը ներկայումս անվտանգ չի համարվում: Նախընտրելի է, որ երկարությունը կազմում է 100 բիթի կարգը:

Օգտագործելով կոդավորված բլոկների շղթա

Կան տարբեր հեշ գործառույթներ, որոնք հիմնված են կոդավորված բլոկների շղթա ստեղծելու վրա, բայց առանց գաղտնի բանալին օգտագործելու: Այս Hash- ի գործառույթներից մեկը առաջարկվել է Rabin- ի կողմից: Հաղորդագրություն Տղամարդ բաժանվել ֆիքսված երկարության բլոկների վրա M1, M2,. , , , MN. եւ օգտագործելով սիմետրիկ կոդավորման ալգորիթմ, ինչպիսիք են DES, հաշիվը հաշիվը հաշվարկելու համար Գամասեղ Հաջորդ ձեւով.

Հ 0 - Նախնական իմաստ N i. = E mi. Գամասեղ = Հ Ն.

Սա նման է CSA ռեժիմում կոդավորման օգտագործման օգտագործման, բայց այս դեպքում գաղտնի բանալին չկա: Ինչպես ցանկացած պարզ հեշի գործառույթի դեպքում, այս ալգորիթմը ենթակա է «ծննդյան հարձակման», եւ եթե կոդագրման ալգորիթմը ստեղծվի, համակարգը համարվում է բավականին խոցելի:

Կարող են լինել «Ծննդյան օրվա» նման այլ հարձակումներ, որոնք հնարավոր են նույնիսկ եթե թշնամին ունի միայն մեկ հաղորդագրություն եւ համապատասխան կոդավորված հեշ ծածկագիր եւ չի կարող ստանալ մի քանի զույգ հաղորդագրություն եւ կոդավորված Hash ծածկագրեր: Հետեւյալ սցենարը հնարավոր է. Ենթադրենք, որ թշնամին վավերացուցիչով հաղորդագրություն է տարածել կոդավորված հեշ ծածկագրի տեսքով, եւ հայտնի է, որ չկարգավորված Hash ծածկագիրը ունի երկարություն Տղամարդ բիթեր: Հաջորդը, թշնամին պետք է կատարի հետեւյալ գործողությունները.

· Վերոնշյալ նկարագրված ալգորիթմի օգտագործումը, հաշվարկեք Unencrypted Hash ծածկագիրը Գամասեղ .

· Ստեղծեք կեղծ հաղորդագրություն ձեւով Q1, Q2,. , , , QN-2 .

· Հաշվարկել N i \u003d e qi համար 1 <= i <= N-2 .

· Ստեղծել 2 մ / 2 Պատահական բլոկներ Հ. Եւ յուրաքանչյուր նման բլոկի համար Հ. հաշվել Ե , Ստեղծեք լրացուցիչ 2 մ / 2 Բավարար բլոկ Յ. եւ յուրաքանչյուր բլոկի համար Յ. հաշվել Դ y [g] որտեղ Գցել - Համապատասխան ձեւավորում Ե. , Հիմնվելով «Ծննդյան օրվա պարադոքսից», մենք կարող ենք ասել, որ հավանականության բարձր աստիճանի, այս հաջորդականությունը պարունակում է բլոկներ Հ. մի քանազոր Յ. այնպիսին է, որ E x \u003d D Y [y] .

· Ստեղծեք հաղորդագրություն Q1, Q2,. , , , QN-2, X, Y , Այս հաղորդագրությունն ունի HASH ծածկագիր Գամասեղ Եվ, հետեւաբար, այն կարող է օգտագործվել կոդավորված վավերացուցիչով:

Հարձակման այս ձեւը հայտնի է որպես հարձակման «հանդիպում մեջտեղում»: Տարբեր ուսումնասիրություններում առաջարկվում է ավելի նուրբ մեթոդներ `բլոկի շղթայի հիման վրա մոտեցումը բարելավելու համար: Օրինակ, Devis- ը եւ գինը նկարագրեցին հետեւյալ տարբերակը.

Հնարավոր է եւս մեկ տարբերակ.

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

Հետագա հետազոտությունները նպատակ ունեին գտնել այլ մոտեցումներ, որոնք ստեղծում են հեշինգ գործառույթներ ստեղծելու համար:

MD5 HASH գործառույթ

Դիտարկենք MD5 հաղորդագրության մարսողական ալգորիթմը (RFC 1321), որը մշակվել է Ron Rivesom- ի կողմից MIT- ից:

MD5 կատարման տրամաբանություն

Ալգորիթմը կամայական երկարություն է ստանում մուտքագրում եւ ստեղծում է 128 խմբաքանակի հաղորդագրություն, որպես ելք: Ալգորիթմը բաղկացած է հետեւյալ քայլերից.

ՆկՂ 8.1.MD5 կատարման տրամաբանություն

Քայլ 1. Բացակայող բիթերի ավելացում

Հաղորդագրությունը լրացվում է այնպես, որ դրա երկարությունը հավասար լինի 448 մոդուլոյի 512 (): Սա նշանակում է, որ 64 բիթով ավելացված հաղորդագրության երկարությունը պակաս է, քան թիվը, բազմակի 512: Լրացում միշտ էլ կատարվում է ցանկալի երկարություն: Օրինակ, եթե հաղորդագրության երկարությունը 448 է, այն լրացվում է 512 բիթով մինչեւ 960 բիթ: Այսպիսով, ավելացված բիթերի քանակը 1-ից 512 սահմաններում է:

Հավելվածը բաղկացած է մի միավորից, որի համար հետեւում է զերը:

Քայլ 2. Երկարացում ավելացնելը

Աղբյուրի երկարության 64-բիթանոց ներկայացուցչությունը (նախքան ավելացնելով) հաղորդագրությունները բիտերում միանում է առաջին քայլի արդյունքին: Եթե \u200b\u200bնախնական երկարությունը ավելի մեծ է, քան 2,64, օգտագործվում են միայն վերջին 64 բիթը: Այսպիսով, դաշտը պարունակում է աղբյուրի հաղորդագրության երկարությունը ըստ մոդուլի 2 64:

Առաջին երկու քայլերի արդյունքում ստեղծվում է հաղորդագրություն, որի երկարությունը բազմակի 512 բիթ է: Այս ընդլայնված հաղորդագրությունը ներկայացված է որպես 512 բիթանոց բլոկների հաջորդականություն y 0, y 1,: , ., Y L-1, մինչդեռ ընդլայնված հաղորդագրության ընդհանուր երկարությունը հավասար է L * 512 բիթին: Այսպիսով, ստացված առաջադեմ հաղորդագրության երկարությունը ավելի քան տասնվեց 32-բիթանոց բառ է:

ՆկՂ 8.2.Ընդլայնված հաղորդագրության կառուցվածքը

Քայլ 3: MD- բուֆերային նախաստորագրում

Օգտագործվում է 128-բիթանոց բուֆեր `խանգարված գործառույթի միջանկյալ եւ վերջնական արդյունքներ պահելու համար: Բուֆերը կարող է ներկայացվել որպես չորս 32-բիթանոց գրանցամատյաններ (A, B, C, D): Այս գրանցամատյանները նախաստորագրվում են հետեւյալ վեցանկյունների համարներով.

A \u003d 01234567 B \u003d 89ABCDEF C \u003d FEDCBA98 D \u003d 76543210

Քայլ 4. 512-բիթանոց (16-քնարերգական) բլոկների հաջորդականության վերամշակում

Ալգորիթմի հիմքը մոդուլ է, որը բաղկացած է չորս ցիկլային բուժումներից, որոնք նշվում են որպես HMD5: Չորս ցիկլ ունեն նման կառույց, բայց յուրաքանչյուր ցիկլը օգտագործում է իր տարրական տրամաբանական գործառույթը, որը նշվում է համապատասխանաբար F F, F G, F H եւ F I I- ով:

ՆկՂ 8.3.Հաջորդ 512-բիթանոց բլոկի վերամշակում

Յուրաքանչյուր ցիկլը վերցնում է որպես մուտք գործում ընթացիկ 512-բիթանոց բլոկ Y Q, ներկայումս վերամշակված, եւ ABCD բուֆերի 128-բիթանոց արժեքը, որը միջանկյալ մարսողական արժեք է եւ փոխում է այս բուֆերի բուֆենտը: Յուրաքանչյուր ցիկլը օգտագործում է նաեւ 64-տարրի աղյուսակի չորրորդ մասը, հիմնվելով մեղքի գործառույթի վրա: T- ի կողմից նշվող I- րդ տարրը հավասար է 2 32 * ABS- ի ամբողջ մասի (SIN (I) (SIN (I)), ես դրված եմ ռադիաների մեջ: Քանի որ ABS- ը (SIN (I)) 0-ից 1-ի միջեւ թիվ է, յուրաքանչյուր տարրը մի ամբողջություն է, որը կարող է ներկայացվել 32 բիթով: Աղյուսակն ապահովում է 32-բիթանոց արժեքների «պատահական» հավաքածու, որը պետք է վերացնի ցանկացած օրինաչափություն մուտքային տվյալների մեջ:

MD Q + 1 ստանալու համար չորս ցիկլերի բերքատվությունը ձեւավորվում է MD Q- ի հետ 2 32 մոդուլով: Բացի այդ, լրացումն իրականացվում է բուֆերի չորս բառերից յուրաքանչյուրի համար:

CLS S- ը ցիկլային հերթափոխում է 32-բիթանոց փաստարկների բիթերի ձախ կողմում:

X [k] - M - K-O 32-Bit Word in Q-Ohm 512 հաղորդագրության բլոկում:

T [i] - I-O, 32-bit Word- ը Matrix T.

- 2 32 մոդուլի հավելում:

Ալգորիթմի չորս ցիկլերից յուրաքանչյուրում օգտագործվում է տարրական տրամաբանական չորս գործառույթներից մեկը: Յուրաքանչյուր տարրական հատկություն մուտքագրում է երեք 32-բիթանոց բառեր, եւ արդյունքը ստեղծում է մեկ 32-բիթանոց բառ: Յուրաքանչյուր գործառույթ խմբաքանակի տրամաբանական գործողություններ է, այսինքն: NTH Արդյունքի բիտը գործառույթ է `N-B- ի երեք մուտքի բիտով: Տարրական գործառույթները հետեւյալն են.

32-բիթանոց բառերի շարքը պարունակում է ներկայումս մշակված ընթացիկ 512 բիթանոց մուտքային բլոկի արժեքը: Յուրաքանչյուր ցիկլը անցնում է 16 անգամ, եւ քանի որ մուտքային հաղորդագրության յուրաքանչյուր բլոկ է մշակվում չորս ցիկլով, ապա յուրաքանչյուր մուտքային միավոր վերամշակվում է ըստ Նկ. 4, 64 անգամ: Եթե \u200b\u200bմուտքագրեք 512 բիթանոց բլոկը տասնվեց 32-բիթանոց բառերի տեսքով, յուրաքանչյուր մուտք 32-բիթանոց բառը օգտագործվում է չորս անգամ, յուրաքանչյուր փուլում մեկ անգամ, եւ սեղանի տանի յուրաքանչյուր տարրը, որը բաղկացած է 64 32-բիթից Բառեր, օգտագործվում է միայն մեկ անգամ: Տեղի յուրաքանչյուր քայլից հետո տեղի է ունենում ցիկլային հերթափոխ դեպի չորս բառի A, B, C եւ D- ն: Յուրաքանչյուր քայլի, ABCD բուֆերային փոփոխությունների չորս բառերից միայն մեկը: Հետեւաբար, յուրաքանչյուր բուֆերային բառ 16 անգամ տատանվում է, իսկ վերջում 17-րդ անգամ `այս միավորի վերջնական արդյունքը ստանալու համար:

մարսել:

2. Արագություն. Ալգորիթմի ծրագրի իրականացումը պետք է իրականացվի բավականին արագ: Մասնավորապես, ալգորիթմը պետք է բավականաչափ արագ լինի 32-բիթանոց ճարտարապետության վրա: Հետեւաբար, ալգորիթմը հիմնված է տարրական գործողությունների պարզ փաթեթի վրա 32-բիթանոց բառերի վրա:

3. Պարզություն եւ կոմպակտություն. Ալգորիթմը պետք է լինի պարզ նկարագրության մեջ եւ հեշտ է ծրագրի համար, առանց մեծ ծրագրերի կամ վայրի բնապատկերների: Այս բնութագրերը ոչ միայն ունեն ակնհայտ ծրագրի նպաստ, այլեւ ցանկալի անվտանգության առումով, քանի որ հնարավոր թույլ կետերը վերլուծելը ավելի լավ է ունենալ պարզ ալգորիթմ:

4. Desired անկալի է փոքր-endian ճարտարապետությամբ. Որոշ պրոցեսորի ճարտարապետություն (օրինակ, Intel 80XXX գիծը) պահում են Byte- ի ստորին բայթերի հասցեները (փոքրիկ-էնդիան) մնացած բառերը: Ուրիշները (օրինակ, արեւի սպարան) Խոսքի ճիշտ բայթերը պահում են կրտսեր բայթ հասցեների դիրքում (առաջին ցիկլի մեծ MD4 լրացուցիչ կայունությունը չի կիրառվում: Երկրորդ փուլում յուրաքանչյուր լրացուցիչ լրացուցիչ Երրորդ ցիկլի յուրաքանչյուր քայլի համար անընդհատ օգտագործվում է: Այսինքն, քիչ հավանական է, որ պատահականորեն ընտրված երկու հաղորդագրություն, նույնիսկ եթե նրանք ունենան ակնհայտ նմանատիպ օրինակներ, ունեն նույն մարսումը, որը ստեղծում է նույն ելքային արժեքը: Սա կհանգեցնի 512 բիթի մեկ բլոկի վրա Նույն ելքը ABCD բուֆերում երկու տարբեր մուտքային արժեքների համար: Մինչդեռ հաջող հարձակման համար այս մոտեցումը ընդլայնելու մեթոդը գոյություն չունի: