Лабораториялық жұмыс №4

RSА криптожүйесі

RSА криптожүйесінде Кв ашық кілті, kв құпия кілті, М хабары және С криптограммасы ZN = {0, 1,2,..., N-1} бүтін сандар жиынына жатады. Мұнда N-модуль: N=Р*Q, ал Р және Q - кездейсоқ, үлкен қарапайым сандар. Максималды қауіпсіздікті қамтамасыз ету үшін Р және Q сандарының ұзындығын бірдей қылып таңдап алып, оны құпияда ұстайды.

Кв ашық кілтін келесі шарттар орындалатындай етіліп кездейсоқ түрде таңдап алады:

1< Кв ≤ φ(N), НОД(КВ, φ (N))=1, φ(N)=(Р-1)(Q-1),

мұнда φ(N) - Эйлер функциясы. Эйлер функциясы 1-ден N-ге дейінгі аралықтағы N санымен өзара қарапайым оң бүтін сандардың санын көрсетеді.

Жоғарыда көрсетілген екінші шарт Кв ашық кілті мен φ(N) Эйлер функциясы өзара қарапайым болу керек екенің көрсетеді.

Әрі қарай, кеңейтілген Евклид алгоритмін пайдаланып kв құпия кілтін есептейді:

kв * Кв =1 (mod φ(N)) немесе kB=КB-1(mod (Р - 1)(Q - 1)). (1.1)

Бұны іске асыруға болады, өйткені хабар алушы (Р,Q) қарапайым сандар жұбын біледі және φ(N) функциясын оңай таба алады. kв және N өзара қарапайым болуы керек. Кв ашық кілті деректерді шифрлауға, ал kв кұпия кілті кері шифрлау үшін пайдаланылады.

С криптограммасын (Кв ашық кілт, М хабар жұбы арқылы) келесі формулаға сәйкес табуға болады:

С = ЕKB (М) = Ев(М) = МKB(mod N). (1.2)

С= МKB (mod N) функциясын кері түрлендіру, яғни М мәнін белгілі С, Кв және N мәндері бойынша N≈2512 рет есептеу арқылы анықтау мүмкін емес. Дегенмен, кері есепті яғни С криптограммасын кері шифрлау есебін (kв құпия кілт, С криптограммасы жұбын пайдалана отырып) келесі формуламен шығаруға болады:

M = DKB (C) = Dв(М) = CKB(mod N). (1.3)

Кері шифрлау үрдісін былайша жазуға болады:

DB ( Ев(М)) = М (1.4)

(1.4)-ке (1.2) және (1.3) мәндерін қойсақ:

(МKB) KB = M(mod N) немесе МKB kB = М(mod N) (1.5)

φ(N) шамасы Эйлер теоремасында өте маңызды рөл атқарады. Эйлер теоремасы бойынша: егер НОД(х, N)=1, онда

хφ(N)≡1(mod)N немесе хп*(N) ≡ 1 (mod φ(N)) (1.6)

(1.5) және (1.6) өрнектерін салыстыра отырып, мынаны аламыз:

КB*kB = n* φ(N)+1 немесе КB*kB≡ 1 (mod φ(N)).

Сондықтан kB құпия кілтін есептеу үшін (1.1) өрнегін пайдаланады. Осылайша, егер С=МКB(mod N) криптограммасын kв дәрежесіне шығарсақ, онда оның нәтижесінде ашық М мәтіні алғашқы қалпына келеді, өйткені:

(МKB) KB = МKB kB = Mn*((N)+1)≡М(mod N).

Сөйтіп, хабар алушы екі параметрді қорғайды: kв кұпия кілтті және көбейтіндісі N модулін беретін (Р, Q) сандар жұбын. Екінші жағынан, хабар алушы N модуль мәнін және kв ашық кілтті ашады.

Қарсы жаққа Кв және N мәндері белгілі. Егер ол N санын Р және Q көбейткіштеріне жіктей алса, онда "құпия жолды", яғни {Р, Q, Кв} үш санын білер еді. Әрі қарай ((Н)((Р-1)(<3-1) Эйлер функциясының мәнін есептеп табар еді және ол арқылы құпия кілтінің мәнін анықтар еді. Бірақ мәні өте үлкен N санын көбейткіштерге жіктеу мүмкін емес (егер Р және Q сандарының ұзындығы 100 ондық таңбадан кем болмаса).

Техникалық тапсырма

1. Текстік файлды RSА криптожүйесі қолданып шифрлеуді ұйымдастыру

2. Текстік файлды RSА криптожүйесі қолданып дешифрлеуді ұйымдастыру