Велики проблем симетричних криптографских система представља размена кључева међу странама које комуницирају. Да ли је онда могуће применити криптографију без размене кључева? Размислите о решењу следећег проблема:
Алиса се налази на острву А, Боб се налази на острву Б. Алиса поседује катанце и кључеве за своје катанце и Боб поседује катанце и кључеве за своје катанце. Алиса нема кључеве који отварају Бобове катанце, нити Боб има кључеве који отварају Алисине катанце. Алиса треба да пошаље писмо Бобу у транспортном ковчегу који може да се закључа катанцем. Труди је пират чији брод пресреће све бродове који путују између острва А и Б. Ако наиђе на транспортни ковчег без катанца отвориће га и прочитати писма. Како може Алиса да пошаље писмо Бобу, а да га Труди не прочита?
Решење: Алиса ставља писмо у ковчег, ставља свој катанац А на ковчег и шаље га Бобу. Труди пресреће брод, али не може да отвори ковчег јер је закључан катанцем А. Боб ставља свој катанац Б на ковчег и враћа га Алиси. Труди пресреће брод, али не може да отвори ковчег јер је закључан катанцима А и Б. Алиса скида свој катанац А са ковчега и враћа га Бобу. Труди пресреће брод, али не може да отвори ковчег јер је закључан катанцем Б. Боб скида свој катанац Б са ковчега, чиме је откључао ковчег и примио писмо од Алисе.
Седамдесетих година прошлог века развила се нова грана криптографије која је у великој мери решила проблем размене кључева у симетричној криптографија – асиметрична криптографија или криптографија са јавним кључем (Public Key Cryptography). Каже се да системи који користе криптографију са јавним кључем користе инфраструктуру јавних кључева (Public Key Infrastructure – PKI).
PKI представља скуп правила, процедура, софтвера и хадрвера неопходних за креирање, дистрибуцију, употребу, складиштење и опозив дигиталних сертификата, као и за управљање шифровањем јавним кључем.
У PKI системима отворени текст, односно поруку обележаваћемо са M, а шифрат са C. У комуникацији ће опет учествовати Алиса и Боб, док ће Труди бити нападач. Свако може да шифрује поруку M за Боба, тако што ће користити његов јавни кључ. Само Боб може да дешифрује поруку са својим приватним кључем. Поред тога Боб може да дигитално потпише поруку тако што ће је шифровати са својим приватним кључем. Свако ко има Бобов јавни кључ може да верификује тај потпис његовим дешифровањем.
PKI системи се заснивају на математичким једносмерним функцијама са замком (Trapdoor One-way Function). Оне се лако израчунавају у једном смеру, а практично немогуће у другом. Замка омогућује да нападач не може лако да израчуна приватни кључ из јавног кључа. Једноставан пример била би факторизација – ако су p и q два проста броја, онда лако можемо изврачунати N, где је N = p * q, али тешко можемо из N израчунати p и q, нарочито ако је N довољно велик број. Други пример била би функција експонента чија је инверзна функција логаритам.
RSA
На идеји асиметричних криптографских система радили су Whitfield Diffie и Martin Helman (творци DH алгоритма за размену симетричних кључева). Међутим, конкретан алгоритам креирали су Рон Ривест, Шамир Ади и Леонард Адлеман 1977. године. Алгоритам је назван RSA по почетним словима њихових имена (Rivest, Shamir, Adleman). Заснива се на математички сложеном поступку растављања (факторизације) производа два велика проста броја на његове чиниоце (факторе).
C = E ( M, Ke ), где је Ke јавни кључ
М ≠ D ( C, Ke ), јер је Е једносмерна функција
М = D ( C, Kd ), где је Kd приватни кључ
из овог можемо да закључимо да је:
М = D ( E ( M, Ke ), Kd )
Једносмерна математичка функција са замком која задовољава ове услове је:
f(x) = xe mod N
Да би се генерисао RSA пар кључева, одабирају се два велика проста броја p и q, где је N = p * q и број е уз одређене услове.
Јавни кључ формира се од N и е, а приватни од d, где се d одређује на основу одређене математичке функције помоћу N и e.
Шифровање: C = Me mod N,
Дешифровање: M = Cd mod N