Алгоритам RSA - за оне који желе да знају више¶

Генерисање криптографских кључева за RSA алгоритам¶

Први корак при генерисању кључева је избор два велика проста броја, \(p\) и \(q\). Нека је \(n=p*q\). Да бисмо формирали кључ за енкрипцију, потребан нам је још број \(e\), такав да је \(1 < e < (p-1)(q-1)\) и да је \(e\) узајамно прост са \((p-1)(q-1)\).

Јавни кључ представља пар бројева \((n, e)\) и он може да буде доступан свима.

Може се доказати да за дате \(p, q, e\) који испуњавају наведене услове, постоји јединствен број \(d\), такав да је \(1 < d < (p-1)(q-1)\) и да \(d \cdot e\) при дељењу са \((p-1)(q-1)\) даје остатак \(1\), што записујемо

Кажемо и да је \(d \cdot e\) једнако јединици по модулу \((p-1)(q-1)\), односно да је број \(d\) мултипликативни инверз од \(e\) по модулу \((p-1)(q-1)\).

Приватни кључ представља пар бројева \((n, d)\) и он треба да буде познат само примаоцу порука.

Пример генерисања јавног и приватног RSA кључа¶

Нека је \(p=11, q=13\). Према томе, \(n = p \cdot q = 11 \cdot 13 = 143\). Изаберимо нпр. \(e=7\). Ово је један исправан избор, јер број \(7\) нема заједничких фактора (осим јединице) са \((p − 1)(q − 1) = 10 \cdot 12 = 120\), тј. јер је \(nzd(7, 120) = 1\).

Пар бројева \((n, e) = (143, 7)\) представља јавни кључ, који можемо да објавимо и учинимо доступним свима од којих намеравамо да примамо криптоване поруке.

Помоћу проширеног Еуклидовог алгоритма, за \(p = 11, q = 13, e = 7\) добијамо \(d = 103\). Проверимо да је \(d\) исправно израчунато, тако што потврдимо да је \(d \cdot e \equiv_{(p-1)(q-1)} 1\):

У нашем случају, \(d \cdot e = 103 \cdot 7 = 721 \equiv_{120} 1\).

Следећи програм за изабране \(p, q, e\) израчунава \(d\). Можете да га испробате на вредностима из примера, или на вредностима које изаберете (промените прва два реда програма).

Криптовање и декриптовање¶

Једном када је пар кључева генерисан, процес шифровања и дешифровања је релативно једноставан и није рачунски захтеван.

Претпоставимо да пошиљалац жели да пошаље текстуалну поруку користећи јавни кључ \((n, e)\). Пошиљалац прво треба да представи текст као низ бројева мањих од \(n\). Поступак кодирања текста помоћу бројева може такође да буде јавно познат (ово још увек није шифровање, односно енкрипција). Након добијања поменутог низа бројева који представља полазни текст, сваки од тих бројева криптујемо помоћу кључа \((n, e)\) и декриптујемо помоћу кључа \((n, d)\), на следећи начин.

Криптовање: Нека је \(M\) један од бројева из низа који представља полазни текст. Криптована вредност \(C = F(M)\) добија се као \(C = M^e \mod n\). У нашем примеру, ако је \(M=46\), добијамо криптовану вредност \(C = 46^7 \mod 143 = 84\)

Декриптовање: Процес декриптовања је једнако једноставан као и криптовање. Претпоставимо да смо примили криптовани број \(C\). Полазни број \(M = F^{-1}(C)\) добијамо као \(C^d \mod n\). У нашем примеру, \(C^d \mod n = 84^{103} \mod 143 = 46\).

Следећи програм илуструје рад алгоритма RSA.

Напади на RSA криптосистем¶

Нападач би могао да покуша да на основу јавног кључа открије, тј. израчуна тајни кључ и тако разбије шифру. Пошто је број \(n\) део јавног кључа, он је нападачу познат. Растављањем броја \(n\) на просте чиниоце, нападач може да дође до простих бројева \(p\) и \(q\), а затим да одреди кључ \(d\) на исти начин као што то ради и власник приватног кључа.

Ево како би тај постуапак изгледао:

Видимо да полазећи само од јавног кључа \((n, e)\), нападач у принципу може да израчуна приватни кључ \((n, d)\). Након откривања приватног кључа, нападач веома једноставно може да декриптује сваки пресретнути шифрат \(C\) и открије поруку \(M\).

Сва безбедност криптосистема RSA је у томе што се у пракси користе много већи бројеви од ових у нашем примеру. Мали бројеви попут ових из примера би учинили криптосистем са таквим параметрима врло небезбедним. Ми смо користили мале бројеве само ради лакшег праћења рада алгоритма и његовог разумевања.

Функције prosireni_euklidov_algoritam, inverz, kriptovano и dekriptovano се извршавају прилично брзо чак и за огромне бројеве, у њима је број потребних операција сразмеран броју цифара броја на који се примењују. Једина спорија функција је faktorizacija, јер је број операција које су њој потребне сразмеран са вредношћу \(\sqrt{n}\). Када би нападач користио поступак факторизације као у претходном програму, за број \(n\) од 100 цифара би му на обичном рачунару требале милијарде година да нађе његове просте чиниоце.

Безбедност алгоритма RSA се не заснива на пажљивом чувању неког тајног податка или поступка. Напротив, видели смо да је познато како може да се израчуна приватни кључ. Дакле, изазов који се поставља пред нападача је „само“ проблем огромне количине рачунања.

Током ових неколико деценија колико се алгоритам RSA користи, пронађени су разни начини да се алгоритам факторизације убрза. Због тога, чак ни бројеви са 100 цифара нису више довољно велики да би се криптовање базирано на њима сматрало безбедним. То не компромитује саму идеју алгоритма, али захтева од организатора криптосистема да користе све веће и веће бројеве. Да би се по данашњим стандардима поступак криптовања сматрао безбедним, потребно је да се бројеви \(p\) и \(q\) записују са по бар 1024 бита, што значи да имају преко 300 декадних цифара. При томе, ово чак није једини услов који треба да испуне \(p\) и \(q\), да би нападачу било тешко (у пракси немогуће) да разбије шифру. Неки од додатних услова су да бројеви \(p\) и \(q\) не смеју да буду сувише близу један другом (треба да се по дужини записа разликују за више десетина цифара), а важно је и да се ниједан од бројева \(p\) и \(q\) не користи у другим криптосистемима заснованим на алгоритму RSA.

Последњи услов може лако да се образложи. Претпоставимо да смо изабрали неке огромне просте бројеве \(p_1\) и \(q_1\), а неко други бројеве \(p_2\) и \(q_2\). Ако би било \(p_1 = p_2\), тада би нападач, знајући бројеве \(n_1\) и \(n_2\), могао брзо да нађе \(nzd(n_1, n_2) = p_1 = p_2\), а то би му било довољно да факторише и \(n_1\) и \(n_2\) и да разбије обе шифре.

Видимо да је избор простих бројева који се користе у алгоритму RSA прилично сложен проблем. Исто важи и за избор јавног кључа, па и за начин представљања оригиналних података бројевима, који ће даље бити криптовани алгоритмом RSA. На ову тему постоји велики број научних радова, што није ни чудо због изузетног практичног значаја који овај алгоритам и даље има. Из свега што је познато о алгоритму RSA, може се закључити да је овај поступак криптовања у основи поуздан, али да је у многим случајевима имплементиран на несигуран начин, тј. са недовољно поузданим вредностима параметара.

Мада је алгоритам RSA у међувремену инспирисао откриће других, сличних али напреднијих алгоритама, он је још увек најпопуларнији криптосистем са јавним кључем.