Лаборатория иши мавзу: rsa алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усули

7-ЛАБОРАТОРИЯ ИШИ

 

Мавзу: RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усули

 

Ишдан мақсад: Ушбу лаборатория ишини бажариш жараёнида RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усули билан танишиш ва унинг дастурини яратишдан иборат.

 

 

Назарий қисм

 Энг қулай яширин йўлли бир томонлама функцияни танлаб асослаш 1977 йилда Массачусет технология институтининг ўша даврдаги ёш тадқиқотчилари - Р. Райвест, А. Шамир, Л. Адлеманга насиб этди. Натижада улар томонидан RSA (Rivest-Shamir-Adleman) алгоритми (криптотизими) ишлаб чиқилди ва бу алгоритм уччала тадқиқотчи номлари бош ҳарфлари билан белгиланган.

RSA алгоритми шифрлаш ва электрон рақамли имзолар учун яратилган биринчи мукаммал ошкора калитли алгоритм ҳисобланади. RSA алгоритмининг хавфсизлиги катта сонларни кўпайтувчиларга ажратиш (факторлаштириш муаммоси)нинг мураккаблигига асосланади.

RSA калитлари қуйидагича генерация қилинади:

1.                Махфий тутиладиган ҳамда етарли катта бўлган иккита ихтиёрий туб p ва q сонлар танланади (масалан, ҳар бири 1024 битли);

2.                Уларнинг кўпайтмаси n = p*q ҳисобланиб, модул сифатида қабул қилинади.

3.                Эйлер функциясининг қиймати φ(n)=(p-1)*(q-1) ҳисобланади.

4.                Бу φ(n) - функция билан ўзаро туб ва (1< e_i < φ(n)) шартни қанотлантирувчи бутун e_i сон танланади. Одатда e_i сифатида иккилик кўринишда кўп бирга эга бўлмаган туб сонлар олинади. e_i сон очиқ калит дейилади. e_i нинг жуда кичик қийматлари масалан 3, RSA схемасининг хавфсизлигини сусайтириши мумкин.

5.                Сўнгра e_i сонига φ(n) модул бўйича мультипликатив тескари бўлган d_i сони ҳисобланади, яъни d_i сон e_i*d_i ≡ 1 mod φ(n) ёки                                       e_i*d_i=1+φ(n) шартни қаноатлантирсин. Одатда бу ифода умумлашган Евклид алгоритми ёрдамида ҳисобланади. d_i - махфий калит деб эълон қилинади.

6.                Шундай қилиб (n, e_i) жуфтлик RSA криптотизими i фойдаланув-чисининг очиқ калити деб эълон қилинади.

7.                (d_i, φ(n)) жуфтлик эса RSA криптотизими i фойдаланувчисининг ёпиқ калити бўлади ва уни сир сақлайди.

RSA криптотизимида i-фойдаланувчидан j-фойдаланувчига шифрланган маълумотни жўнатиш қуйидагича амалга оширилади:

1. Шифрлаш қоидаси:  ушбу ифода M^ej mod n=C ҳисобланади, бу ерда M - очиқ маълумот, С – шифрланган маълумот;

2. Шифрни очиш қоидаси:  ушбу ифода  C^dj mod n = M^ejdj mod n _{= M}  ҳисобланиб, очиқ маълумот M ҳосил қилинади.

Қуйидаги 1-расмда RSA алгоритми асосида шифрлаш ва шифрни очиш жараёни келтирилган.

 

1-расм. RSA алгоритми асосида шифрлаш ва шифрни очиш жараёни

 

 

Шифрни очиш қоидасидаги C^dj mod n = M^ejdj mod n _{= M}   муносабат-нинг ўринлилиги қуйидаги теоремалардан келиб чиқади.

Шуни айтиб ўтиш керакки, криптографик алгоритмларнинг криптотаҳлилларга бардошлилиги криптотизимни амалиётга тадбиқ қилишда томонларнинг келишиб олинган тартиб-қоидалари мажмуи - криптотизим протоколига ҳам жуда боғлиқ бўлади. Чунончи, RSA криптотизимининг айрим протоколлари заиф чиққан. Дж. Мур RSA криптотизимида ишлатиладиган протокол агар барча фойдаланувчилар учун модул n бир хил олинса, ёки ошкора калит e тарзида кичик сон олинса ё бўлмаса шифрланаётган ахборотнинг энтропияси кичик (бу ҳол айниқса телефон сўзлашувлари учун хос) бўлса шифрни бузиб очиш осонлигини кўрсатиб ўтган. Бундан RSA криптотизими заиф экан деган хулоса келиб чиқмайди, албатта. Фақат шуни ёдда тутиш лозимки, ҳар қандай криптотизимни яратишда ишлаб чиқиладиган протокол тажовузкор қўллаши мумкин бўлган барча ҳолларни ҳисобга олиб мукаммал бўлиши лозим. RSA криптотизими ҳозирда ҳам ошкора калитли тизим сифатида энг бардошли тизимлар қаторида туради.

RSA  криптотизими протоколининг заиф  томонлари ҳам мавжуд.

 

 RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усули

Бошланғич шартлар: Бузғунчи (хакер, криптотаҳлилчи)га очиқ калит                             (e, n) ва шифрматн C маълум.

Қўйилган масала: Очиқ матн M топилсин.

Криптотаҳлилчи  тенгликни қаноатлантирувчи j сонини танлайди, яъни криптотаҳлилчи каналдан олинган шифрматнни j марта очиқ калит ёрдамида шифрлайди (бу қуйидаги кўринишга эга ). Шу тенгликни қаноатлантирувчи j ни топгандан кейин криптотаҳлилчи   ни ҳисоблайди (яъни j-1 марта шифрлаш амалини бажаради) – ушбу қиймат очиқ матн M га тенг бўлади. Бу =()^e дан келиб чиқади, яъни маълум бир e даражага оширилган  сони шифрматн C беради.

Қуйида RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усулига доир мисоллар келтирилган.

 

1-мисол:

 p=983, q=563, e=49, M=123456.

C=M⁴⁹(mod n)=1603,

(mod n)=85978,

(mod n)=123456,

(mod n)=1603.

 

 

 

 

2-мисол:

 

n	p	q	Ф(n)	e	d	m	S	С^e	j
77	11	7	60	13	37	29	57	8	1
77	11	7	60	13	37	29	57	50	2
77	11	7	60	13	37	29	57	29	3
77	11	7	60	13	37	29	57	57	4
77	11	7	60	13	37	29	57	8	5
77	11	7	60	13	37	29	57	50	6
77	11	7	60	13	37	29	57	29	7
77	11	7	60	13	37	29	57	57	8
77	11	7	60	13	37	29	57	8	9
77	11	7	60	13	37	29	57	50	10
77	11	7	60	13	37	29	57	29	11
77	11	7	60	13	37	29	57	57	12
77	11	7	60	13	37	29	57	8	13
77	11	7	60	13	37	29	57	50	14
77	11	7	60	13	37	29	57	29	15
77	11	7	60	13	37	29	57	57	16

 

Ишни бажариш учун вазифа ва топшириқлар

1.  RSA алгоритми асосида унинг дастурини тузинг.

2.  RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усулини кичик сонлар учун Excelда амалга оширинг.

3.  RSA алгоритмидан фойдаланиб шифрланган маълумотни калитсиз очиш усулининг моҳиятини таҳлил қилинг ва унинг дастурини яратинг.