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

Модул арифметикаси

• Тенгликни икки томонини модулга ( олинади:

Ёки

• Ушбу тенгликни га таққослаш орқали

га тенглигини ёки лигини топиш мумкин.

• Яъни, тенглик ўринли.

•  

RSA алгоритми

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

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

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

•  

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

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

•  

Мисол

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

•  

Мисол

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

•