РСА алгоритам за шифровање је врста алгоритма за шифровање са јавним кључем. Да бисмо боље разумели РСА, хајде да прво разумемо шта је алгоритам шифровања са јавним кључем.
Алгоритам шифровања јавног кључа:
Алгоритам шифровања јавног кључа се такође назива асиметричним алгоритамом. Асиметрични алгоритми су они алгоритми у којима пошиљалац и прималац користе различите кључеве за шифровање и дешифровање. Сваком пошиљаоцу је додељен пар кључева:
Тхе Јавни кључ се користи за шифровање, а Приватни кључ се користи за дешифровање. Дешифровање се не може извршити коришћењем јавног кључа. Два кључа су повезана, али приватни кључ не може бити изведен из јавног кључа. Јавни кључ је добро познат, али приватни кључ је тајан и познат је само кориснику који поседује кључ. То значи да свако може да пошаље поруку кориснику користећи јавни кључ корисника. Али само корисник може да дешифрује поруку користећи свој приватни кључ.
Алгоритам јавног кључа ради на следећи начин:
- Подаци који се шаљу су шифровани од стране пошиљаоца А користећи јавни кључ предвиђеног пријемника
- Б дешифрује примљени шифровани текст користећи свој приватни кључ, који је познат само Б. Б одговара А шифрујући његову поруку користећи А јавни кључ.
- А дешифрује примљени шифровани текст користећи свој приватни кључ, који је само њему познат.
РСА алгоритам шифровања:
РСА је најчешћи алгоритам са јавним кључем, назван по својим изумитељима Ривест, Шамир и Аделман (РСА).
РСА алгоритам користи следећу процедуру за генерисање јавних и приватних кључева:
- Изаберите два велика проста броја, п и к .
- Помножите ове бројеве да бисте пронашли н = п к к, где н назива се модулом за шифровање и дешифровање.
- Изаберите број То је мање од н , тако да је н релативно једноставно (п - 1) к (к -1). То значи да То је и (п - 1) к (к - 1) немају заједнички фактор осим 1. Изаберите 'е' тако да је 1
гцд (е,д(н)) =1 - Ако н = п к к, онда је јавни кључ . Порука отвореног текста м је шифрован коришћењем јавног кључа. Да бисте пронашли шифровани текст из обичног текста, користи се следећа формула за добијање шифрованог текста Ц.
Ц = мТо јепротив н
Ево , м мора бити мање од н . Већа порука (>н) се третира као конкатенација порука, од којих је свака шифрована засебно. - Да бисмо одредили приватни кључ, користимо следећу формулу да израчунамо д тако да:
ДТо јемод {(п - 1) к (к - 1)} = 1
Ор
ДТо јемод φ (н) = 1 - Приватни кључ је . Шифрована порука ц је дешифрован коришћењем приватног кључа. За израчунавање обичног текста м из шифрованог текста ц следећа формула се користи за добијање обичног текста м.
м = цдпротив н
Узмимо неки пример РСА алгоритма шифровања:
Пример 1:
Овај пример показује како можемо да шифрујемо отворени текст 9 користећи РСА алгоритам шифровања са јавним кључем. Овај пример користи просте бројеве 7 и 11 за генерисање јавног и приватног кључа.
Објашњење:
Корак 1: Изаберите два велика проста броја, п и к .
п = 7
к = 11
Корак 2: Помножите ове бројеве да бисте пронашли н = п к к, где н назива се модулом за шифровање и дешифровање.
Прво израчунавамо
н = п к к
н = 7 к 11
н = 77
Корак 3: Изаберите број То је мање тога н , тако да је н релативно једноставно (п - 1) к (к -1). То значи да То је и (п - 1) к (к - 1) немају заједнички фактор осим 1. Изаберите 'е' тако да је 1 Друго, израчунавамо φ (н) = (п - 1) к (к-1) φ (н) = (7 - 1) к (11 - 1) φ (н) = 6 к 10 φ (н) = 60 Хајде да сада изаберемо релативни прости е од 60 као 7. Дакле, јавни кључ је = (7, 77) 4. корак: Порука отвореног текста м је шифрован коришћењем јавног кључа. Да бисте пронашли шифровани текст из обичног текста, користи се следећа формула за добијање шифрованог текста Ц. Да бисте пронашли шифровани текст из обичног текста, користи се следећа формула за добијање шифрованог текста Ц. Ц = мТо јепротив н Ц = 97против 77 Ц = 37 5. корак: Приватни кључ је . Да бисмо одредили приватни кључ, користимо следећу формулу д тако да: ДТо јемод {(п - 1) к (к - 1)} = 1 7д мод 60 = 1, што даје д = 43 Приватни кључ је = (43, 77) Корак 6: Шифрована порука ц је дешифрован коришћењем приватног кључа. За израчунавање обичног текста м из шифрованог текста ц следећа формула се користи за добијање обичног текста м. м = цдпротив н м = 3743против 77 м = 9 У овом примеру, обичан текст = 9 и шифровани текст = 37 У РСА криптосистему, одређени А користи два проста броја, 13 и 17, да генерише јавни и приватни кључ. Ако је јавни кључ А 35. Тада је приватни кључ А ……………?. Објашњење: Корак 1: у првом кораку изаберите два велика проста броја, стр и к . п = 13 к = 17 Корак 2: Помножите ове бројеве да бисте пронашли н = п к к, где н назива се модулом за шифровање и дешифровање. Прво израчунавамо н = п к к н = 13 к 17 н = 221 Корак 3: Изаберите број То је мање тога н , тако да је н релативно једноставно (п - 1) к (к -1). То значи да То је и (п - 1) к (к - 1) немају заједнички фактор осим 1. Изаберите 'е' тако да је 1 Друго, израчунавамо φ (н) = (п - 1) к (к-1) φ (н) = (13 - 1) к (17 - 1) φ (н) = 12 к 16 φ (н) = 192 г.ц.д (35, 192) = 1 Корак 3: Да бисмо одредили приватни кључ, користимо следећу формулу да израчунамо д тако да: Израчунај д = дТо јемод φ (н) = 1 д = д к 35 мод 192 = 1 д = (1 + к.φ (н))/е [нека к =0, 1, 2, 3…………………] Ставите к = 0 д = (1 + 0 к 192)/35 д = 1/35 Ставите к = 1 д = (1 + 1 к 192)/35 д = 193/35 Ставите к = 2 д = (1 + 2 к 192)/35 д = 385/35 д = 11 Приватни кључ је = (11, 221) Дакле, приватни кључ, тј. д = 11 РСА криптосистем користи два проста броја 3 и 13 да генерише јавни кључ = 3 и приватни кључ = 7. Која је вредност шифрованог текста за обичан текст? Објашњење: Корак 1: У првом кораку изаберите два велика проста броја, стр и к . п = 3 к = 13 Корак 2: Помножите ове бројеве да бисте пронашли н = п к к, где н назива се модулом за шифровање и дешифровање. Прво израчунавамо н = п к к н = 3 к 13 н = 39 Корак 3: Ако н = п к к, онда је јавни кључ . Порука отвореног текста м је шифрован коришћењем јавног кључа. Дакле, јавни кључ је = (3, 39). Да бисте пронашли шифровани текст из обичног текста, користи се следећа формула за добијање шифрованог текста Ц. Ц = мТо јепротив н Ц = 53према 39 Ц = 125 наспрам 39 Ц = 8 Дакле, шифровани текст генерисан из обичног текста, Ц = 8. РСА криптосистем користи два проста броја, 3 и 11, да генерише приватни кључ = 7. Која је вредност шифрованог текста за обичан текст 5 користећи РСА алгоритам шифровања са јавним кључем? Објашњење: Корак 1: у првом кораку изаберите два велика проста броја, стр и к . п = 3 к = 11 Корак 2: Помножите ове бројеве да бисте пронашли н = п к к, где н назива се модулом за шифровање и дешифровање. Прво израчунавамо н = п к к н = 3 к 11 н = 33 Корак 3: Изаберите број То је мање тога н , тако да је н релативно једноставно (п - 1) к (к -1). То значи да То је и (п - 1) к (к - 1) немају заједнички фактор осим 1. Изаберите 'е' тако да је 1 Друго, израчунавамо φ (н) = (п - 1) к (к-1) φ (н) = (3 - 1) к (11 - 1) φ (н) = 2 к 10 φ (н) = 20 4. корак: Да бисмо одредили јавни кључ, користимо следећу формулу да израчунамо д тако да: Израчунајте е к д = 1 мод φ (н) е к 7 = 1 против 20 е к 7 = 1 против 20 е = (1 + к. φ (н))/ д [нека к =0, 1, 2, 3…………………] Ставите к = 0 е = (1 + 0 к 20) / 7 е = 1/7 Ставите к = 1 е = (1 + 1 к 20) / 7 е = 21/7 е = 3 Јавни кључ је = (3, 33) Дакле, јавни кључ, тј. е = 3 Пример 2:
Пример 3:
Пример 4:
трећи нормални облик