ŠIFROVACÍ ALGORITMUS RSA

Šifrovací algoritmus RSA je typ šifrovacieho algoritmu s verejným kľúčom. Aby sme lepšie porozumeli RSA, najprv pochopme, čo je šifrovací algoritmus verejného kľúča.

Algoritmus šifrovania verejného kľúča:

Šifrovací algoritmus verejného kľúča sa tiež nazýva asymetrický algoritmus. Asymetrické algoritmy sú tie algoritmy, v ktorých odosielateľ a príjemca používajú rôzne kľúče na šifrovanie a dešifrovanie. Každému odosielateľovi je priradený pár kľúčov:

Verejný kľúč Súkromný kľúč

The Verejný kľúč sa používa na šifrovanie a Súkromný kľúč sa používa na dešifrovanie. Dešifrovanie nie je možné vykonať pomocou verejného kľúča. Tieto dva kľúče sú prepojené, ale súkromný kľúč nemožno odvodiť z verejného kľúča. Verejný kľúč je dobre známy, ale súkromný kľúč je tajný a pozná ho iba používateľ, ktorý kľúč vlastní. To znamená, že každý môže poslať správu používateľovi pomocou verejného kľúča používateľa. Ale iba používateľ môže dešifrovať správu pomocou svojho súkromného kľúča.

Algoritmus verejného kľúča funguje nasledujúcim spôsobom:

Údaje, ktoré sa majú odoslať, odosielateľ šifruje A pomocou verejného kľúča zamýšľaného prijímača
B dešifruje prijatý šifrový text pomocou svojho súkromného kľúča, ktorý pozná iba B. B odpovedá A zašifrovaním svojej správy pomocou verejného kľúča A.
A dešifruje prijatý šifrový text pomocou svojho súkromného kľúča, ktorý pozná iba on.

Šifrovací algoritmus RSA:

RSA je najbežnejší algoritmus verejného kľúča, pomenovaný po jeho vynálezcoch Rivest, Shamir a Adelman (RSA).

Algoritmus RSA používa na generovanie verejných a súkromných kľúčov nasledujúci postup:

Vyberte dve veľké prvočísla, p a q .
Nájdi tieto čísla vynásobením n = p x q, kde n sa nazýva modul pre šifrovanie a dešifrovanie.
Vyberte číslo to je menej ako n , takže n je relatívne prvočíslo k (p - 1) x (q - 1). Znamená to, že to je a (p - 1) x (q - 1) nemajú žiadny spoločný faktor okrem 1. Vyberte „e“ tak, že 1 gcd (e,d(n)) =1
Ak n = p x q, potom je verejný kľúč . Jednoduchá textová správa m je šifrovaný pomocou verejného kľúča. Na nájdenie šifrovaného textu z obyčajného textu sa na získanie šifrového textu C používa nasledujúci vzorec.
C = m^{to je}proti n
Tu , m musí byť menšia ako n . Väčšia správa (>n) sa považuje za zreťazenie správ, pričom každá z nich je šifrovaná samostatne.
Na určenie súkromného kľúča používame nasledujúci vzorec na výpočet d tak, že:
D_{to je}mod {(p - 1) x (q - 1)} = 1
Alebo
D_{to je}mod φ (n) = 1
Súkromný kľúč je . Šifrovaná textová správa c sa dešifruje pomocou súkromného kľúča. Na výpočet obyčajného textu m zo šifrového textu c sa na získanie čistého textu používa nasledujúci vzorec m.
m = c^dproti n

Zoberme si nejaký príklad šifrovacieho algoritmu RSA:

Príklad 1:

Tento príklad ukazuje, ako môžeme šifrovať čistý text 9 pomocou šifrovacieho algoritmu s verejným kľúčom RSA. Tento príklad používa prvočísla 7 a 11 na generovanie verejného a súkromného kľúča.

Vysvetlenie:

Krok 1: Vyberte dve veľké prvočísla, p a q .

p = 7

q = 11

Krok 2: Nájdi tieto čísla vynásobením n = p x q, kde n sa nazýva modul pre šifrovanie a dešifrovanie.

Najprv vypočítame

n = p x q

n = 7 x 11

n = 77

Krok 3: Vyberte číslo to je menej n , takže n je relatívne prvočíslo k (p - 1) x (q - 1). Znamená to, že to je a (p - 1) x (q - 1) nemajú žiadny spoločný faktor okrem 1. Vyberte „e“ tak, že 1

Po druhé, počítame

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

Vyberme teraz relatívne prvočíslo e 60 ako 7.

Verejný kľúč je teda = (7, 77)

Krok 4: Jednoduchá textová správa m je šifrovaný pomocou verejného kľúča. Na nájdenie šifrovaného textu z obyčajného textu sa na získanie šifrového textu C používa nasledujúci vzorec.

Na nájdenie šifrovaného textu z obyčajného textu sa na získanie šifrového textu C používa nasledujúci vzorec.

C = m^{to je}proti n

C = 9⁷proti 77

C = 37

Krok 5: Súkromný kľúč je . Na určenie súkromného kľúča používame nasledujúci vzorec d taký, že:

D_{to je}mod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1, čo dáva d = 43

Súkromný kľúč je = (43, 77)

Krok 6: Šifrovaná textová správa c sa dešifruje pomocou súkromného kľúča. Na výpočet obyčajného textu m zo šifrového textu c sa na získanie čistého textu používa nasledujúci vzorec m.

m = c^dproti n

m = 37⁴³proti 77

m = 9

V tomto príklade je obyčajný text = 9 a šifrovaný text = 37

Príklad 2:

V kryptosystéme RSA používa konkrétny A dve prvočísla, 13 a 17, na generovanie verejného a súkromného kľúča. Ak je verejný kľúč A 35. Potom súkromný kľúč A je ……………?.

Vysvetlenie:

Krok 1: v prvom kroku vyberte dve veľké prvočísla, p a q .

p = 13

q = 17

Krok 2: Nájdi tieto čísla vynásobením n = p x q, kde n sa nazýva modul pre šifrovanie a dešifrovanie.

Najprv vypočítame

n = p x q

n = 13 x 17

n = 221

Po druhé, počítame

φ (n) = (p - 1) x (q-1)

φ (n) = (13 - 1) x (17 - 1)

φ (n) = 12 x 16

φ (n) = 192

algoritmus mergesort

g.c.d (35, 192) = 1

Krok 3: Na určenie súkromného kľúča používame nasledujúci vzorec na výpočet d tak, že:

Vypočítajte d = d_{to je}mod φ (n) = 1

d = d x 35 mod 192 = 1

d = (1 + k.φ (n))/e [nech k = 0, 1, 2, 3………………]

Dajte k = 0

d = (1 + 0 x 192)/35

d = 1/35

Dajte k = 1

d = (1 + 1 x 192)/35

d = 193/35

Dajte k = 2

d = (1 + 2 x 192)/35

d = 385/35

d = 11

Súkromný kľúč je = (11, 221)

Súkromný kľúč teda d = 11

Príklad 3:

Šifrovací systém RSA používa dve prvočísla 3 a 13 na generovanie verejného kľúča = 3 a súkromného kľúča = 7. Akú hodnotu má šifrovaný text pre obyčajný text?

Vysvetlenie:

Krok 1: V prvom kroku vyberte dve veľké prvočísla, p a q .

p = 3

q = 13

Krok 2: Nájdi tieto čísla vynásobením n = p x q, kde n sa nazýva modul pre šifrovanie a dešifrovanie.

Najprv vypočítame

n = p x q

n = 3 x 13

n = 39

Krok 3: Ak n = p x q, potom je verejný kľúč . Jednoduchá textová správa m je šifrovaný pomocou verejného kľúča. Verejný kľúč je teda = (3, 39).

Na nájdenie šifrovaného textu z obyčajného textu sa na získanie šifrového textu C používa nasledujúci vzorec.

C = m^{to je}proti n

C = 5³proti 39

C = 125 vs. 39

C = 8

Šifrový text vygenerovaný z čistého textu je teda C = 8.

Príklad 4:

Šifrovací systém RSA používa dve prvočísla, 3 a 11, na generovanie súkromného kľúča = 7. Akú hodnotu má šifrovaný text pre obyčajný text 5 pomocou šifrovacieho algoritmu RSA s verejným kľúčom?

Vysvetlenie:

Krok 1: v prvom kroku vyberte dve veľké prvočísla, p a q .

p = 3

q = 11

Krok 2: Nájdi tieto čísla vynásobením n = p x q, kde n sa nazýva modul pre šifrovanie a dešifrovanie.

Najprv vypočítame

n = p x q

n = 3 x 11

n = 33

Po druhé, počítame

bash polia

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

φ (n) = 2 x 10

φ (n) = 20

Krok 4: Na určenie verejného kľúča použijeme nasledujúci vzorec na výpočet d tak, že:

Vypočítajte e x d = 1 mod φ (n)

e x 7 = 1 proti 20

e = (1 + k. φ (n))/d [nech k = 0, 1, 2, 3………………]

Dajte k = 0

e = (1 + 0 x 20) / 7

e = 1/7

Dajte k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e = 3

Verejný kľúč je = (3, 33)

Verejný kľúč teda e = 3