7 Маъруза: Ассиметрик шифрлар

RSA алгоритми

• RSA очиқ калитли шифрлаш алгоритми муаллифлари бўлган учта олимлар, Rivest, Shamir ва Adleman, шарафига қўйилган.
• RSA алгоритми катта сонларни факторлаш муаммосига асосланади.
• RSA алгоритмида қуйидаги жараёнлар мавжуд:
• Калитни генерациялаш;
• Шифрлаш;
• Дешифрлаш.

RSA – калитларни генерациялаш

• Иккита катта узунликдаги ва сонлари танланади.
• Уларнинг кўпайтмаси ҳисобланади: .
• Эйлер функцияси ҳисобланади:
• Эйлер функцияси сонидан кичик ва у билан ўзаро туб бўлган сонлар миқдорини кўрсатади.
• билан ўзаро туб бўлган сони танланади.
• шартни қаноатлантирувчи сони ҳисобланади.
• Демак,
• ) очиқ калит жуфти
• махфий калитни ташкил этади.
• Шундан сўнг, ва сонлар ўчириб ташланади.

•  

RSA – шифрлаш ва дешифрлаш

• Шифрлаш:
• .
• Дешифрлаш:
• .

•  

Мисол

• га тенг бўлсин.
• га тенг бўлади.
• га тенг бўлади.
• У ҳолда, га тенг бўлсин.
• Эвклиднинг кенгайтирилган алгоримтига кўра
• Яъни, .
• Очиқ калити жуфти
• Шахсий калити эса

•  

Мисол

• Фараз қилайлик:
• Б томон А томонга маълумотни шифрлаш юбормоқчи:
• Бунинг учун Б томон А томоннинг очиқ калити жуфтини олади.
• Шифрматнни қуйидагича ҳисоблайди:
• Уни А томонга юборади.
• А томон шифрматнни дешифрлаш учун:
• шахсий калит дан фойдаланади

•  

RSA алгоритми

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

•