Симметрик криптогрфик алгоритмлар. Оқимли шифрлаш алгоритмлари. Режа

Муаммо
Баёни
Факторлаш	Бутун факторлаш муаммоси: бутун мусбат n берилган,

	у нинг Tуб факторларини топиш керак: яъни, n p1^e^1p2^e^2....pk^e^k кўринишда ѐзиш керак, бу ерда p^i - турли туб сонлар ва ҳар бири ei 1.
RSA муаммоси (RSAP)	R SA муаммоси (RSA инверсия каби маълум): иккита турли p ва q тоқ сонларнинг кўпайтмаси бўлган бутун мусбат n сони, EKUB (e, (p-1)(q-1))=1 га тенг бўлган бутун мусбат e сони ва бутун с берилган, шундай бутун m ни топиш керакки, унда m^ec(modn) бўлсин.
Квадратик чегирма муаммоси (QRP)	Квадратик чегирма муаммоси: тоқ мураккаб бутун n ва Якоби белгисига эга бўлган бутун a сони берилган, a сони n модуль бўйича квадратик чегирма эканлиги ѐки чегирма эмаслиги аниқланcин.
n модули бўйича квадрат илдиз (SQROOT)	n модули бўйича квадрат илдиз: мураккаб бутун n сони ва a Q^n (n модули бўйича квадратик чегирма тўплами) берилган, n модули бўйича a дан шундай бутун квадратик илдиз x топилсинки, унда x^2=a(mod n) бўлсин.
Дискрет логарифм муаммоси (DLP)	Д искрет логарифм муаммоси: Туб cон p учун, чекли майдон Zp* да ҳосил қилувчи (генератор) элемент ҳамда Zp* берилган бўлса, шундай 0 p-2 бўлган бутун x сон топилсинки, унда (mod p) бўлсин, бу ерда x – даража кўрсаткичи.
Умумлашган дискрет логарифм муаммоси (GDLP)	У мумлашган дискрет логарифм муаммоси: n тартибли чекли циклик группа G, G нинг ҳосил қилувчиси ва G элемент берилган, шундай 0 n-1 бўлган бутун x сони топилсинки, унда бўлсин.
Диффи- Хеллман муаммоси (DHP)	Д иффи-Хеллман муаммоси: туб сон p, Zp* ҳосил қилувчиси - ва ^a(mod p) ва (mod p) элементлари берилган, ^ab(mod p) топилсин.
Умумлашган Диффи- Хеллман муаммоси (GDHP)	У мумлашган Диффи-Хеллман муаммоси: чекли циклик группа G, G ҳосил қилувчиси - ва группа элементлари ^b лар берилган, топилсин.
Қисм тўплам йиғиндиси (SUBSET- SUM)	Қ исм тўплам-йиғиндиси муаммоси: бутун мусбат сонлар тўплами a1,a2,...,an ва бутун мусбат сон S берилган, йиғиндиси S га тенг бўлган ^aj қисм тўплам мавжудми ѐки йўқми аниқлансин.
Эллиптик эгри	Эллиптик эгри чизиқли дискрет логарифм муаммоси:
чизиқда дискрет логарифм муаммоси (ECDLP)	K чекли майдон ва G нуқтада тартиби n бўлган G нуқта, Q E(K) нуқтада E ЭЭЧ берилган. Q=[d]G шартни қаноатлантирувчи d, 0 d n-1 бутун сонни топиш талаб этилади, агарда у мавжуд бўлса.
Даража параметри муаммоси	1 -таъриф. Агар параметрли группа (Fn; ) да ташувчи Fn нинг элементи y берилган бўлса, унда параметр R, даража кўрсаткичи е ва элемент a топилсин. 2 -таъриф. Агар параметрли группа (Fn; ) да ташувчи Fn нинг элементлари y ва a берилган бўлса, унда параметр R ва даража кўрсаткичи е топилсин. Б у ерда Fn – n та бутун сонлардан тузилган чекли тўплам, y a^\e(mod n), ^\e – a ни параметр R билан e-даражаси рамзи, φ(n)>R>1, элемент a a^\ (mod n) 0 шартини фақат = q бўлгандагина қаноатлантиради, q – φ(n) нинг бутун сонли бўлувчиси, φ(n) – Эйлер пи-функцияси, n {p, p1*p2}, p, p1, p2 – туб сонлар.

Катта сонни туб кўпайтувчиларга ажратиш ва дискрет логарифмлаш муаммосига асосланган шифрлаш усуллари

Маълумки, энг кўп фойдаланиб келинган носимметрик тизимларга бардошлилиги учта муаммонинг, яъни факторлаш, дискрет логарифмлаш ва ЭЭЧ группасида дискрет логарифмлаш мураккаблиги муаммоларидан бири билан белгиланадиган криптотизимлар киради. Булар билан бир қаторда қўшимча махфийликка эга бўлган носимметрик криптотизимлар ҳам юзага келмоқда.
RSA шифрлаш алгоритми. Диффи ва Хелман критография соҳасида янгича ѐндашишни тарғиб қилиб, очиқ калитли криптотизимларнинг барча талабларига жавоб берадиган криптографик алгоритм яратиш таклифибилан чиқди. Биринчилардан бўлиб бунга жавобан 1997 йил Рон Райветс (Ron Rivest), Ади Шамир (Adi Shamir) ва Лен Адлмен (Len Adlmen)лар шу вақтгача тан олинган ва амалий кенг қўлланиб келинган очиқ калитли шифрлаш алгоритм схемасини таклиф қилди ва бу алгоритм уларнинг номи шарафига RSA алгоритми деб аталди. RSA алгоритми факторлаш мураккаблигига асосланган шифрлаш алгоритми ҳисобланади.

Райвест, Шамир ва Адлмен томонидан яратилган схема даража кўрсаткичига асосланган. Очиқ матн блокларга ажратилиб шифрланади, ҳар бир блок баъзи берилган n сонидан кичик бўлган иккилик қийматга эга бўлади. Бундан келиб чиқадики блок узунлиги дан кичик ѐки тенг бўлиши керак. Умуман олганда амалиѐтда блок узунлиги га тенг деб олинади, бу ерда . Очиқ матн M блоки ва шифрланган матн Cблоки учун шифрлаш ва дешифрлаш қуйидаги формула билан ҳисоблаш мумкин.
,
Жўнатувчи ҳам, қабул қилувқи ҳам n ни қийматини билиши керак.
Жўнатувчи e ни қийматини, қабул қилувчи эса фақат d ни қийматини билишади. Ушбу схема очиқ калитли шифрлаш алгоритми ҳисобланади, KU={e,n}- очиқ калит ва KR={d,n}-махфий калит ҳисобланади. Бу алгоритм очиқ калит ѐрдамида шифрланиши учун, қуйидаги талаблар бажарилиши керак.

1. Шундай e, d ва n қийматлар мавжуд бўлиш керакки, барча учун тенглик ўринли бўлиши керак.
учун ва ни ҳисоблаш осон бўлиши керак.
3. Амалий жиҳатдан e ва n ни билмасдан туриб d ни қийматини билиш мумкин бўлмаслиги керак.
Биринчи шартга биноан қуйидаги муносабатни топиш керак

Эйлер функциясига асосан: ҳар қандай иккита p ва q туб сонва ҳар қандай n ва m бутун сонлар учун, n=pq ва , ва ихтиѐрий k бутун сон учун қуйидаги муносабат бажарилади.

Бу ерда Эйлер функцияси бўлиб, n дан кичик ва n билан ўзаро туб бўлган мусбат бутун сон. Эйлер функцияси билан ўзаро туб бўлган e сон танлаб олинади ва талаб қилинаѐтган муносабат қуйидаги шарт асосида бажарилади. Бу қуйидаги муносабат билан эквивалент:

e ва d, модул бўйичаўзаро тескари сон, яъни gcd(.
Юқорида келтирилган параметрлар асосида RSA схемасини қуйидаги таьснифлаш мумкин:
p ва q - туб сонлар (махфий, танлаб олинади),
n=pq (очиқ, ҳисобланади),
шундай e, gcd( (очиқ, танлаб олинади),
(махфий, ҳисобланади).
Махфий калит {d,n} дан, очиқ калит эса {e,n} дан иборат бўлади. Фараз қилайлик A фойдаланувчи очиқ калитини элон қилди ва B фойдаланувчи унга
M хабарни жўнатмоқчи. Bфойдаланувчи ҳисоблаб Cни
жўнатади. Шифрланган матнни қабул қилган A фойдаланувчи ѐрдамида дешифрлаб дастлабки очиқ матнга эга бўлади.
Қуйида келтирилган мисолда RSA алгоритми амалий қўллаш кўрсатилган.

1. 
   Иккита туб сон танлаб олинади, p=7 ва q=17.
   
2. 
   n=p*q=7*17 ҳисобланади.
   
3. 
   Эйлер функцияси ҳисобланади
   
4. 
   Эйлер функцияси билан ўзаро туб бўлган ва ундан кичкина бўлнаг e танлаб олинади; бизни, мисолимизда e=5.
   
5. 
   de=1mod 96 ваd<96шартни қаноатлантирувчи dсони топилади. d=77, 77*5=385=4*96+1.
   

Натижада очиқ калит KU={5,119} ва ѐпиқ калит KR={77,119}ҳосил бўлади. Юқоридаги мисолда очиқ матн қиймати M=19 олинган. Шифрлаш формуласига кўра очиқ матн қиймати очиқ калит қиймати ѐрдамида даражага кўтарилиб, n модул бўйича қиймати олинади, яъни 19 сони 5 даражага кўтарилади, натижада 2476099 ҳосил бўлади. Натижани 119 га бўлинса, қолдиқ 66 га тенг бўлади. ва шунинг учун ҳам шифрланган матн 66 га тенг бўлади. Дешифрлаш учун эса шифрланган матн қиймати махфий калит қиймати ѐрдамида даражага кўтарилиб, n модул бўйича қиймати олинади, яъни амални ҳисобланади ва дастлабки очиқ матн қийматига эга бўлинади, яъни 19 га.