Algoritem za šifriranje Rsa. Vzorec algoritma za šifriranje rsa

Razmislite o delu asimetričnega RSA ... Predlagali so ga trije matematiki Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) in Leonard Adlman ( L. Adleman) leta 1978.

Spodaj praštevilo razumeli bomo število, ki je deljivo samo z 1 in samo s seboj. Euclid je v svojih "Načelih" pokazal, da je za vsako praštevilo večje praštevilo, to je, da je število praštevil neskončno.

Dokazi.Recimo, da je največje praštevilo str, določite zmnožek vseh osnovnih števil P=2∙3∙5∙7∙…∙str.

Razmislite o številki P+1. Sama številka je veliko število str ali zmnožek praštevil, večjih od P... Prišli smo do protislovja, zato je število osnovnih števil neskončno.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Vzajemno praštevila poklicali bomo takšne številke, ki nimajo skupnega delitelja, razen 1 .

Končno, pod rezultatom operacije i mod j upoštevali bomo preostanek celoštevilčne delitve jazna j. Če želite uporabiti algoritem RSA, morate najprej ustvariti javni in zasebni ključ, tako da sledite spodnjim korakom.

1. Izberite dva zelo velika prime r in q.

2. Določite n kot rezultat množenja r na q (n \u003d p q).

3. Izberite veliko naključno številko, ki jo bomo poklicali d... To število mora biti sorazmerno z rezultatom množenja (p - 1) (q - 1).

4. Določite tako številko eza katero velja naslednja relacija (e d) mod ((p - 1) (q - 1)) \u003d 1.

5. Pokličimo številke e in n, skrivni ključ pa so številke din n.

Zdaj za šifriranje podatkov z znanim ključem ( e, n), morate narediti naslednje:

- razdeli šifrirano besedilo na bloke, od katerih je vsak lahko predstavljen kot številka M (i);

- šifriranje besedila, ki se šteje za zaporedje številk M (i) po formuli С (i) \u003d (M (i) e) mod n... Za dešifriranje teh podatkov s skrivnim ključem (d, n), opraviti je treba naslednje izračune: M (i) \u003d (C (i) d) mod n... Rezultat bo niz številk M (i), ki so izvirno besedilo.

Algoritem RSA temelji na enem od dokazanih Eulerjevih izrekov, katerega poseben primer navaja, da če je število n predstavljiv kot dva praštevila str in q, potem za katero koli x velja enakost

x (p-1) (q-1) mod n = 1.

To formulo bomo uporabili za dešifriranje sporočil RSA. Če želite to narediti, dvignite oba dela na moč (- y):

(x (- y) (p-1) (q-1)) mod n \u003d 1 (- y) \u003d 1.

Zdaj pomnožimo obe strani z x:

(x (-y) (p-1) (q-1) +1) mod n = 1· x \u003d x.

Spomnimo se zdaj, kako so bili ustvarjeni javni in zasebni ključi. Izbrali smo d tako da

e d + (p-1) (q-1) y \u003d 1,

e d \u003d (-y) (p-1) (q-1) +1.

Zato lahko v zadnjem izrazu prejšnjega odstavka eksponent nadomestimo s številom (e d).Dobimo (x e d) mod n \u003d x... Če želite prebrati sporočilo c i \u003d ((m i) e) mod n samo dvignite ga na moč dmodulo m:

((c i) d) mod n \u003d ((m i) e d) mod n \u003d m i.

Tu je preprost primer uporabe metode RSA za šifriranje sporočila CAB. Za poenostavitev bomo uporabili zelo majhne številke (v praksi se uporabljajo velike številke).

1. Izberimo p \u003d3 in q \u003d11.

2. Določite n \u003d3· 11=33.

3. Najdi (p - 1) (q - 1) \u003d20. Kot d izberite katero koli številko, ki je primerna z 20, na primer d \u003d3.

4. Izberite številko e... Kot takšno število lahko vzamemo katero koli številko, za katero je razmerje (npr3) mod20 = 1,
na primer 7.

5. Predstavljajmo šifrirano sporočilo kot zaporedje celih števil v obsegu 0 ... 32. Naj pismo IN predstavlja številka 1, črka IN - številka 2 in črka OD - številka 3. Potem lahko sporočilo predstavimo kot zaporedje številk 312. Šifrirajmo sporočilo s tipko (7, 33):

С (1) \u003d (З 7) mod 33 \u003d 2187 mod 33 \u003d 9,

С (2) \u003d (1 7) mod 33 \u003d 1 mod 33 \u003d 1,

С (З) \u003d (2 7) mod 33 \u003d 128 mod 33 \u003d 29.

6. Poskusimo dešifrirati sporočilo (9, 1, 29), pridobljeno kot rezultat šifriranja z znanim ključem, na podlagi tajnega ključa (3, 33):

M (1) \u003d (9 3) mod 33 \u003d 729 mod 33 \u003d 3,

М (2) \u003d (1 3) mod 33 \u003d 1 mod 33 \u003d 1,

M (Z) \u003d (29 3) mod 33 \u003d 24389 mod 33 \u003d 2.

Tako je kot posledica dešifriranja sporočila prejeto izvirno sporočilo CAB.

Kriptografska trdnost algoritma RSA temelji na predpostavki, da je izjemno težko določiti tajni ključ iz znanega javnega, saj to zahteva rešitev problema obstoja celoštevilčnih deliteljev. Ta težava trenutno ne omogoča učinkovite (polinomske) rešitve. V zvezi s tem tradicionalne metode iskanja delilnikov za ključe, sestavljene iz 200 binarnih številk (in prav te številke je priporočljivo uporabiti), zahtevajo veliko število operacij (približno 10 23).

Kripto sistem RSA se uporablja na najrazličnejših platformah in v številnih panogah. Vdelana je v vse več komercialnih izdelkov. Uporabljajo ga operacijski sistemi Microsoft, Apple, Sun in Novell. V strojni opremi se algoritem RSA uporablja v varnih telefonih, na omrežnih karticah Ethernet, na pametnih karticah in se pogosto uporablja v kriptografski opremi podjetja Zaxus (Rasal). Poleg tega je algoritem vključen v vse glavne protokole za varne internetne komunikacije, vključno s S / MIME, SSL in S / WAN, uporablja pa se tudi v mnogih institucijah, na primer v državnih službah, v večini korporacij, v vladnih laboratorijih in na univerzah. ...

Tehnologijo šifriranja RSA BSAFE uporablja več kot 500 milijonov uporabnikov po vsem svetu. Ker se v večini primerov uporablja algoritem RSA, ga lahko štejemo za najpogostejši kriptosistem z javnimi ključi na svetu in se to število očitno nagiba k povečanju z rastjo uporabnikov interneta.

RSA uporablja dve vrsti tipk - e in d, kjer je e javno, d pa tajno. Denimo, da je P izvirno besedilo, C pa šifrirano besedilo. Alice uporablja C \u003d P e mod n za ustvarjanje šifranta C iz izvirnega besedila P; Bob s P \u003d C d mod n izvleče izvirno besedilo (datoteko), ki jo je poslala Alice. Z uporabo postopka generiranja ključev je ustvarjenih zelo veliko število n modulov, o katerih bomo razpravljali kasneje.

Za šifriranje in dešifriranje se uporablja stopnjevanje po modulu. Kot smo razpravljali v predavanjih 12-13, je pri uporabi hitrega algoritma možno stopnjevanje v polinomskem času. Vendar je iskanje modularnega logaritma tako težko kot razširitev števila v modulu. Zanj ni polinomskega časovnega algoritma. To pomeni, da lahko Alice sporočilo šifrira z javnim ključem (e) ob polinomskem času. Bob ga lahko tudi dešifrira v polinomskem času (ker pozna d). Toda Eve tega sporočila ne more razvozlati, ker bi morala z modularno aritmetiko izračunati e-ti koren C. Slika 14.5 prikazuje idejo RSA.

Slika: 14.5.

Z drugimi besedami, Alice uporablja enosmerna funkcija (stopnjevanje po modulu) z vrzeljo, ki jo pozna samo Bob. Eve ne pozna vrzeli, zato sporočila ne more razvozlati. Če nekega dne najdemo polinomski algoritem za modul izračuna e-te korenine n, potem stopnjevanje po modulu n ne bo več enosmerna funkcija.

Postopek

Slika 14.6 prikazuje splošno predstavo o postopku, ki se uporablja v RSA.

RSA uporablja stopnjevanje za šifriranje / dešifriranje. Za napad na zaprto besedilo mora Eve izračunati

Dve algebrski strukturi

RSA uporablja dve algebrski strukturi: obroč in skupino.

Obroči za šifriranje / dešifriranje... Šifriranje in dešifriranje se izvede s pomočjo komutativnega obroča z dvema aritmetičnima operacijama: seštevanje in množenje. V RSA je ta obroč javno dostopen, ker je modul n javno dostopen. Vsakdo lahko s tem šifrirnim obročkom pošlje sporočilo Bobu.

Skupine ključnih generacij... RSA uporablja multiplikativno skupino za generiranje ključev. Skupina podpira samo množenje in deljenje (multiplikativno inverzno), ki sta potrebna za ustvarjanje javnih in zasebnih ključev. Ta skupina mora biti skrita, ker je njen modul skriven. Videli bomo, da če Eve najde ta modul, lahko zlahka napade kriptografski sistem.

RSA uporablja dve algebrski strukturi: odprti obroč R \u003d< Z n , +, x\u003e in skrivna skupina G \u003d< Z (n) * , x\u003e.

Ustvarjanje ključev

Bob uporablja korake, prikazane v algoritmu 14.2, za ustvarjanje svojih javnih in zasebnih ključev. Po generiranju ključev Bob izjavi nabor (e, n) kot svoj javni ključ za dostop: Bob shrani d kot svoj zasebni ključ. Bob lahko pusti p, q in; zasebnega ključa ne morejo spremeniti, ne da bi spremenili modul. Zaradi varnosti je priporočena velikost vsakega osnovnega p ali q 512 bitov (skoraj 154 decimalnih mest). To določa velikost enote, n 1024 bitov (309 števk).

V RSA je nabor (e, n) javni dostopni ključ; celo število d - skrivni ključ.

Šifriranje

Vsakdo lahko s svojim javnim ključem za dostop pošlje sporočilo Bobu. Šifriranje v RSA lahko izvedemo s pomočjo algoritma polinomne časovne kompleksnosti, kot je prikazano v algoritmu 14.3. O algoritmu hitre eksponentizacije smo govorili na predavanjih 12-13. Velikost izvornega besedila mora biti manjša od n; če je velikost izvornega besedila večja, ga je treba razdeliti na bloke.

Kriptosistem RSA v vsakem šifrirnem ciklu pretvori binarni blok navadnega besedila m dolžine velikosti (n), ki se šteje kot celo število, v skladu s formulo: c \u003d m e (mod n).

Poleg tega je n \u003d pq , kjer sta p in q naključna primera velike širine, ki sta uničena po generiranju modula in ključev. Javni ključ je sestavljen iz para številk e in n . Podključ e je izbran kot dovolj veliko število iz obsega 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Nadalje, pri reševanju enačbe xe + yφ (n) \u003d 1 v celih številih x, y, nastavimo d \u003d x, tj. ed \u003d 1 (j (n)). Poleg tega je za vse m razmerje m ed \u003d m (n) , zato znanje d omogoča dešifriranje kriptogramov.

Za zagotovitev zanesljive informacijske varnosti obstajata dve zahtevi za sisteme javnih ključev.

1. Preoblikovanje izvirnega besedila ne sme izključevati njegove obnove na podlagi javnega ključa.

2. Določanje zasebnega ključa na podlagi javnega ključa mora biti tudi računsko neuresničljivo. V tem primeru je zaželena natančna spodnja meja zapletenosti (števila operacij) lomljenja šifre.

Algoritmi šifriranja z javnimi ključi se pogosto uporabljajo v sodobnih informacijskih sistemih.

Razmislimo o konstrukciji kriptosistema RSA na preprostem primeru.

1. Izberite p \u003d 3 in q \u003d 11.

2. Določite n \u003d 3 ∙ 11 \u003d 33.

3. Poiščite j (n) \u003d (p - 1) (q - 1) \u003d 20.

5. Izberimo število d, ki ustreza 7d \u003d 1 (mod 20).

Lahko je videti, da je d \u003d 3 (mod 20).

Predstavljajmo šifrirano sporočilo kot zaporedje celih števil z uporabo korespondence: A \u003d 1, B \u003d 2, C \u003d 3, ..., Z \u003d 26. Ker je velikost (n) \u003d 6 , potem lahko naš kriptosistem šifrira črke latinske abecede, ki se štejejo za bloke. Objavimo javni ključ (e, n) \u003d (7, 33) in povabimo druge udeležence tajnega komunikacijskega sistema, naj šifrirajo sporočila, poslana na naš naslov, z uporabo njega. , ki ima v kodiranju, ki smo ga izbrali, obliko (3, 1, 2). Pošiljatelj mora šifrirati vsak blok in poslati šifrirano sporočilo na naš naslov:

RSA (C) \u003d RSA (3) \u003d 3 7 \u003d 2187 \u003d 9 (mod 33);
RSA (A) \u003d RSA (1) \u003d 1 7 \u003d 1 (mod 33);
RSA (B) \u003d RSA (1) \u003d 2 7 \u003d 128 \u003d 29 (mod 33).

Po prejemu šifriranega sporočila (9, 1, 29) ga lahko dešifriramo na podlagi skrivnega ključa (d, n) \u003d (3, 33), pri čemer vsak blok dvignemo na d \u003d 3:

9 3 \u003d 729 \u003d 3 (mod 33);
1 3 \u003d 1 (mod 33);
29 3 \u003d 24389 \u003d 2 (mod 33).

V našem primeru je enostavno prisilno prisiliti tajni ključ. V praksi je to nemogoče, saj za praktično uporabo so trenutno priporočene velikosti (n) :

· 512-768 bitov - za posameznike;

· 1024 bitov - za komercialne informacije;

2048 bitov - za tajne podatke.

Primer izvedbe algoritma RSA je prikazan v seznamih 18.1 in 18.2 (prevajalniki - Delphi, FreePascal).

Seznam 18.1. Primer izvedbe algoritma RSA v Pascalu

program Rsa;
($ APPTYPE CONSOLE)
($ IFDEF FPC)
($ MODE DELPHI)
($ ENDIF)

uporablja SysUtils, uBigNumber;

// Generator naključnih števil

var t: matrika bajtov;
var pos: Celo število;
var cbox: niz bajtov \u003d
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

postopek InicMyRandom;
var i: Celo število;
var s: niz;
začeti
WriteLn ("Vnesite nekaj besedila za inicializacijo generatorja
naključne številke (do 256 znakov): ");
ReadLn (s);
i: \u003d 1;
medtem ko jaz<=255) and (i<=Length(s)) do

Uvod 3

Glavni del 5

1 Zgodovina ustvarjanja 5

2 Opis algoritma 5

2.1 Ustvarjanje tipk 6

2.2 Šifriranje in dešifriranje

2.3 Primer 7

Zaključek 9

Seznam uporabljenih virov 10

Uvod

Kriptografija je poseben sistem za spreminjanje običajnega pisanja, ki se uporablja za razumevanje besedila le omejenega števila ljudi, ki poznajo ta sistem.

Kriptografija je znanost o zaščiti informacij z matematičnimi metodami.

Sodobna kriptografija vključuje:

simetrični kriptosistemi;

asimetrični kriptosistemi;

sistemi za elektronski digitalni podpis (EDS);

hash funkcije;

upravljanje ključev;

pridobivanje skritih informacij;

kvantna kriptografija.

Simetrično šifriranje - Simetrični algoritmi so tisti, ki za šifriranje in dešifriranje uporabljajo isti (le pošiljatelju in prejemniku znan tajni ključ).

Pogosti simetrični algoritmi šifriranja:

AES (Advanced Encryption Standard) - ameriški standard šifriranja;

GOST 28147-89 - domači standard za šifriranje podatkov;

DES (Data Encryption Standard) je standard za šifriranje podatkov v ZDA do AES;

3DES (Triple-DES, trojni DES);

IDEA (mednarodni algoritem za šifriranje podatkov);

SEED je korejski standard za šifriranje podatkov;

Camellia je šifra, certificirana za uporabo na Japonskem;

XTEA je najpreprostejši algoritem za izvedbo.

Asimetrični kriptoalgoritmi so namenjeni predvsem odpravi glavne pomanjkljivosti simetričnih kriptosistemov - zapletenosti upravljanja in distribucije ključev.

Osnova vseh asimetričnih kriptoalgoritmov je velika računska zapletenost obnovitve navadnega besedila brez poznavanja zasebnega ključa.

Primeri asimetričnih kriptoalgoritmov:

Diffie-Hellmann;

RSA - Rivest, Shamir, Adelman - temelji na zapletenosti problema upoštevanja velikih števil v kratkem času;

DSA - algoritem digitalnega podpisa, ameriški standard;

GOST R 34.10 - 94, 2001, RF standardi.

V tem povzetku bomo podrobno preučili asimetrični kriptoalgoritem šifriranja - algoritem RSA.

Glavni del

RSA (dobesedna okrajšava za Rivest, Shamir in Adleman) je kriptografski algoritem z javnim ključem, ki temelji na računski zapletenosti problema faktorjenja velikih celih števil. Kripto sistem RSA je bil prvi sistem, primeren tako za šifriranje kot digitalni podpis.

Zgodovina ustvarjanja

Whitfield Diffie in Martin Hellman, ki sta jo novembra 1976 objavila New Directions in Cryptography, sta revolucionirala razumevanje kriptografskih sistemov s postavitvijo temeljev za kriptografijo z javnimi ključi. Pozneje razvit Diffie-Hellmanov algoritem je dvema osebama omogočil, da sta z nezaščitenim komunikacijskim kanalom pridobili skupni tajni ključ. Vendar ta algoritem ni rešil težave z preverjanjem pristnosti. Brez dodatnih sredstev uporabniki niso mogli biti prepričani, s kom so ustvarili skupno skrivnost.

Po pregledu tega članka so se trije znanstveniki Ronald Linn Rivest, Adi Shamir in Leonard Adleman z Massachusetts Institute of Technology (MIT) lotili iskanja matematične funkcije, ki bi uvedla model kriptografskega sistema javnega ključa, ki sta ga oblikovala Whitfield Diffie in Martin Hellman. Potem ko so delali na več kot 40 možnih možnostih, jim je uspelo najti algoritem, ki temelji na razliki v tem, kako enostavno je najti velike praštevilke in kako težko je razdeliti produkt dveh velikih praštevilk, ki sta kasneje postala znana kot RSA. Sistem je dobil ime po prvih črkah imen njegovih ustvarjalcev.

Opis algoritma

Prvi korak v katerem koli asimetričnem algoritmu je ustvariti par javnih / zasebnih ključev in javni ključ distribuirati "po vsem svetu".

Ustvarjanje ključev

Za algoritem RSA je stopnja generiranja ključa sestavljena iz naslednjih operacij:

Številka se imenuje odprti eksponent

Šifriranje in dešifriranje

Recimo, da želi pošiljatelj prejemniku poslati sporočilo.

Sporočila so cela števila od 0 do, tj. ... Slika 1 prikazuje diagram algoritma RSA.

Slika 1 - Diagram algoritma RSA

Algoritem pošiljatelja:

Algoritem sprejemnika:

Enačbi (1) in (2), na katerih temelji shema RSA, opredeljujejo medsebojno inverzne transformacije množice.

Primer uporabe

Tabela 1 prikazuje primer uporabe algoritma RSA. Pošiljatelj je poslal šifrirano sporočilo "111111", prejemnik pa ga je šifriral s svojim zasebnim ključem.

Tabela 1 - Fazno izvajanje algoritma RSA

Zaključek

V tem eseju je bil podrobno obravnavan algoritem RSA za asimetrično šifriranje. Opisana je bila zgodovina njegovega ustvarjanja, opisani so algoritmi za ustvarjanje ključev, šifriranje in dešifriranje. Predstavljen je tudi primer praktične uporabe algoritma RSA.

Seznam uporabljenih virov

Semenov Yu.A. Internetni protokoli // M.: Prospect, 2011. - 114 str.

Belyaev A.V. Metode in sredstva za zaščito informacij // ChF SPbSTU, 2010. - 142s.

Venbo M. Sodobna kriptografija. Teorija in praksa // M.: Williams, 2005. - 768 str.

Schneier B. Uporabna kriptografija. Protokoli, algoritmi, izvorna besedila // M.: Triumph, 2002. - 816 str.

Algoritem RSA // Internetni vir: http://ru.wikipedia.org/wiki/Rsa

Shema Rivest-Shamir-Adleman (RSA) je trenutno edina splošno sprejeta in praktično uporabljena shema šifriranja z javnimi ključi.

Shema RSA je blokovna šifra, pri kateri sta tako navadno besedilo kot šifra besedila cela števila od 0 do p - 1 za nekatere p.

Navadno besedilo je šifrirano v blokih, od katerih vsak vsebuje binarno vrednost, manjšo od neke dane številke p. To pomeni, da dolžina bloka ne sme presegati log2 ("). V praksi je izbrana dolžina bloka 2 do bitov kje 2 к Shema, ki so jo razvili Rivest, Shamir in Adleman, temelji na izrazih s pooblastili. Šifriranje in dešifriranje za blok navadnega besedila M in blok šifreksta C lahko predstavimo kot naslednji formuli:

Pošiljatelj in prejemnik morata vedeti pomen p. Pošiljatelj pozna pomen e, in samo prejemnik ve vrednost d. Ta shema je torej algoritem za šifriranje z javnim ključem KU \u003d (e, n), in zasebni ključ KR \u003d (d, n).

Da se ta algoritem uporablja za šifriranje z javnim ključem, morajo biti izpolnjene naslednje zahteve:

Takšne vrednote morajo obstajati e, d in p, kaj M ed \u003d M (mod p) za vse M str.

IVT mora biti razmeroma enostavno izračunati in C c1 za vse vrednosti M p.

Skoraj nemogoče je določiti d glede na razpoložljivo njen str.

Najprej analiziramo prvo zahtevo, ostale pa pozneje. Najti je treba odnos oblike

Tu je najbolj primeren Eulerjev izrek: za kateri koli dve praštevili r in q in poljubna dva taka cela števila pete, kaj n \u003d pqn0 in poljubno celo število do veljajo naslednji odnosi:

kjer je φ (π) Eulerjeva funkcija, katere vrednost je enaka številu pozitivnih celih števil, manjšim od p in vzajemno preprosto s p.

V primeru preprostega r in q imamo f (pq) - (str - 1 ) (q - 1). Zato dobimo zahtevano razmerje pod pogojem

To je enakovredno naslednjim razmerjem:

tiste. ona d so medsebojno inverzni modulo φ (i). Upoštevajte, da zaradi aritmetičnih pravil v razredih ostankov to lahko velja le, kadar d (in zato e) je coprime z φ (u). V enakovrednem zapisu (f (/ 7), d) \u003d.

Zdaj imamo vse, kar predstavlja shemo RSA. Sestavni deli vezja so:

r in q - dva prime (tajna, izbrana);

n - pq (odprto, izračunano);

taka eda (f (i), e) \u003d 1,1 e

d = e l (mod f (/?)) (skrivnost, izračunano).

Zasebni ključ je sestavljen iz (d, n), in odprto od (f, n).Recimo, da je uporabnik A objavil svoj javni ključ, zdaj pa bo uporabnik B kmalu posredoval M-ovo sporočilo njemu.

Nato uporabnik B izračuna šifrirano sporočilo

Ko je prejel to šifrirano besedilo, jo uporabnik A dešifrira z izračunom

Tu je smiselno navesti utemeljitev tega algoritma. So bili izbrani ona d tako da

Torej oblika kts\u003e (n) +. Toda na podlagi Eulerjevega izreka za katera koli dva praštevila r in qu cela števila n \u003d pqn М, da О odnosi

torej

Zdaj smo že

Tabela 10.1 povzema algoritem RSA in sl. 10.1 prikazuje primer njegove uporabe. V tem primeru se ključi izračunajo na naslednji način:

• 1. Izbrana sta dva primerka: p- 7 wq- 17.
• 2. Izračunano n \u003d pq \u003d 7 x 17 \u003d 119.
• 3. Izračunaj φ (n) - (p -) (q - 1) = 96.
• 4. Izbirno ecoprime s f (P) \u003d 96 in manj kot f (i); v tem primeru \u003d 5.
• 5. To je določeno d, kaj de \u003d 1 (mod 96) in d 96. Ustrezna vrednost je d \u003d 77, saj je 77 x 5 \u003d 385 \u003d 4 x 96 + 1.
• 6. Rezultat je javni ključ KU \u003d (5, 119) in zasebni ključ KR \u003d (77, 119).

Ta primer prikazuje uporabo teh tipk z vhodnim navadnim besedilom M \u003d 19. Šifriranje poviša 19 na peto stopnjo, kar ima za posledico 2.476.099. Kot rezultat deljenja z 119 je preostanek 66. Zato je 19 5 \u003d 66 (mod 119), zato bo šifrirano besedilo 66. Po dešifriranju se izkaže, da

Slika: 10.1.

Preglednica 10.1