Алгоритъм RSA | алгоритъм за криптиране и декриптиране на съобщения

RSA (Rivest-Shamir-Adleman) е алгоритъм, използван от съвременните компютри за криптиране и декриптиране на съобщения. Това е асиметричен криптографски алгоритъм. Асиметричен означава, че има два различни ключа. Нарича се още криптография с публичен ключ, тъй като единият от ключовете може да бъде даден на всеки. Другият ключ трябва да се пази в тайна. Алгоритъмът се основава на факта, че намирането на множителите на голямо съставно число е трудно: когато множителите са прости числа, проблемът се нарича просто факторизиране. Той също така е генератор на двойка ключове (публичен и частен ключ).

RSA включва публичен ключ и частен ключ. Публичният ключ може да бъде известен на всеки - той се използва за криптиране на съобщения. Съобщенията, криптирани с публичния ключ, могат да бъдат декриптирани само с частния ключ. Частният ключ трябва да се пази в тайна. Изчисляването на частния ключ от публичния ключ е много трудно.

Използвани концепции

RSA използва редица концепции от криптографията:

Еднопосочна функция, която е лесна за изчисляване; намирането на функция, която я обръща, или изчисляването на тази функция е много трудно.
RSA използва концепция, наречена дискретен логаритъм. Тя работи подобно на нормалния логаритъм: Разликата е, че се използват само цели числа и по принцип се използва операция модул. Като пример a^x =b, modulo n. Дискретният логаритъм се състои в намирането на най-малкото x, което удовлетворява уравнението, когато са дадени a b и n
Алгоритъмът на Шор може да му се противопостави.

Генериране на ключове

Ключовете за алгоритъма RSA се генерират по следния начин:

Изберете две различни големи случайни прости числа p {\displaystyle p} $p$ и q {\displaystyle q} . Това трябва да се запази в тайна.
Изчислете n = p q {\displaystyle n=pq} $n=pq$ .

n {\displaystyle n} е модулът за публичния ключ и частните ключове.

Изчислете тотиента: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} $\phi (n)=(p-1)(q-1)$ .
Изберете цяло число e {\displaystyle e} $e$ , такова че 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} $1<e<\phi (n)$ , и e {\displaystyle e} $e$ е съизмеримо с ϕ ( n ) {\displaystyle \phi (n)} $\phi (n)$ .
Т.е.: e {\displaystyle e} $e$ и ϕ ( n ) {\displaystyle \phi (n)} $\phi (n)$ нямат общи коефициенти, различни от 1 {\displaystyle 1} $1$ : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} $\gcd(e,\phi (n))=1$ ; Виж най-голям общ делител.

e {\displaystyle e} $e$ е освободен като експонента на публичния ключ.

Изчислете d {\displaystyle d} $d$ , за да удовлетворите отношението на конгруентност d e ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1\!\!\!\!{\pmod {\phi (n)}}} $de\equiv 1\!\!\!\!{\pmod {\phi (n)}}$ .
т.е.: d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} $de=1+x\cdot \phi (n)$ за някакво цяло число x {\displaystyle x} . (Просто да се каже: Изчислете d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} $d=(1+x\cdot \phi (n))/e$ да бъде цяло число)

d {\displaystyle d} $d$ се запазва като експонента на частния ключ.

Забележки към горните стъпки:

Стъпка 1: Числата могат да бъдат вероятностно проверени за първичност.
Стъпка 3: променена в PKCS#1 v2.0 на λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)} $\lambda (n)={\rm {lcm}}(p-1,q-1)$ вместо ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} $\phi (n)=(p-1)(q-1)$ .
Стъпка 4: Популярен избор за публичните експоненти е e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} $e=2^{16}+1=65537$ . Някои приложения избират по-малки стойности, като например e = 3 {\displaystyle e=3} $e=3$ , 5 {\displaystyle 5} $5$ или 35 {\displaystyle 35} $35$ . Това се прави, за да се ускори криптирането и проверката на подписите при малки устройства като смарт карти, но малките публични експоненти могат да доведат до по-големи рискове за сигурността.
Стъпки 4 и 5 могат да бъдат изпълнени с разширения алгоритъм на Евклид [en]; вж. модулна аритметика.

Публичният ключ
се състои от модула n {\displaystyle n\,} $n\,$ и публичния (или криптиращия) експонент e {\displaystyle e\,} $e\,$ . Личният ключ се състои от p,q и частния (или декриптиращ) експонент d {\displaystyle d\,} $d\,$ , който трябва да се пази в тайна.

За по-голяма ефективност може да се съхранява различна форма на частния ключ:

p {\displaystyle p} $p$ и q {\displaystyle q} : първичните числа от генерирането на ключа;
d mod ( p - 1 ) {\displaystyle d{\bmod {(}}p-1)} $d{\bmod {(}}p-1)$ и d mod ( q - 1 ) {\displaystyle d{\bmod {(}}q-1)} $d{\bmod {(}}q-1)$ : често наричани dmp1 и dmq1;
q - 1 mod p {\displaystyle q^{-1}{\bmod {p}}} $q^{-1}{\bmod {p}}$ : често се нарича iqmp.

Всички части на частния ключ трябва да се пазят в тайна в тази форма. p {\displaystyle p\,} $p\,$ и q {\displaystyle q\,} $q\,$ са чувствителни, тъй като са коефициенти на n {\displaystyle n\,} $n\,$ , и позволяват изчисляването на d {\displaystyle d\,} $d\,$ при зададено e {\displaystyle e\,} $e\,$ . Ако p {\displaystyle p\,} $p\,$ и q {\displaystyle q\,} $q\,$ не се съхраняват в тази форма на частния ключ, те се изтриват сигурно заедно с други междинни стойности от генерирането на ключа.
Въпреки че тази форма позволява по-бързо декриптиране и подписване чрез използване на китайската теорема за остатъка (CRT), тя е значително по-малко сигурна, тъй като позволява атаки по странични канали [en]. Това е особен проблем, ако се прилага върху смарт карти, които се възползват най-много от подобрената ефективност.
(Започнете с y ≡ x e ( mod n ) {\displaystyle y\equiv x^{e}\!\!\!\!{\pmod {n}}} $y\equiv x^{e}\!\!\!\!{\pmod {n}}$ и оставете картата да декриптира това. Така тя изчислява ( y d mod p ) {\displaystyle (y^{d}{\bmod {p}})} $(y^{d}{\bmod {p}})$ или ( y d mod q ) {\displaystyle (y^{d}{\bmod {q}})} $(y^{d}{\bmod {q}})$ , чиито резултати дават някаква стойност z {\displaystyle z} $z$ . Сега предизвикайте грешка в едно от изчисленията. Тогава gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} $\gcd(z-x,n)$ ще покаже p {\displaystyle p} $p$ или q {\displaystyle q} .)

Криптиране на съобщение

Алиса дава своя публичен ключ ( n , e ) {\displaystyle (n,e)} $(n,e)$ на Боб и запазва частния си ключ в тайна. Боб иска да изпрати съобщение M {\displaystyle M} $M$ на Алиса.

Първо той превръща M {\displaystyle M} $M$ в число m {\displaystyle m} , по-малко от n {\displaystyle n} , като използва договорен обратим протокол, известен като схема за подплънки. След това той изчислява шифровия текст c {\displaystyle c\,} $c\,$ , съответстващ на:

c = m e mod n {\displaystyle c=m^{e}\mod {n}} $c=m^{e}\mod {n}$

Това може да стане бързо с помощта на метода на експонентиране чрез квадратиране. След това Боб изпраща c {\displaystyle c\,} $c\,$ на Алиса.

Декриптиране на съобщението

Алиса може да възстанови m {\displaystyle m\,} $m\,$ от c {\displaystyle c\,} $c\,$ , като използва частния си ключ d {\displaystyle d\,} $d\,$ по следната процедура:

Като има предвид m {\displaystyle m\,} $m\,$ , тя може да възстанови първоначалните различни прости числа, прилагайки китайската теорема за остатъците към тези две конгруенции, тя получава

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} $m^{ed}\equiv m{\bmod {pq}}$ .

По този начин,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} $c^{d}\equiv m{\bmod {n}}$ .

Следователно:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n} $m=c^{d}\ mod\ n$

Работен пример

Ето един пример за RSA криптиране и декриптиране. Използваните тук прости числа са твърде малки, за да ни позволят да криптираме безопасно каквото и да било. Можете да използвате OpenSSL, за да генерирате и изследвате истинска двойка ключове.

1. Изберете две случайни прости числа p {\displaystyle p} $p$ и q {\displaystyle q\,} $q\,$ :

p = 61 {\displaystyle p=61} $p=61$ и q = 53 {\displaystyle q=53\,} $q=53\,$ ;

2. Изчислете n = p q {\displaystyle n=pq\,} $n=pq\,$ :

n = 61 × 53 = 3233 {\displaystyle n=61\крат 53=3233\!} $n=61\times 53=3233\!$ ;

3. Изчислете тотиентата ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} $\phi (n)=(p-1)(q-1)$ :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\!} $\phi (n)=(61-1)(53-1)=3120\!$ ;

4. Изберете e > 1 {\displaystyle e>1} $e>1$ коприма на 3120 {\displaystyle 3120\,} $3120\,$ :

e = 17 {\displaystyle e=17\,} $e=17\,$ ;

5. Изберете d {\displaystyle d\,} $d\,$ да удовлетворява e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}}} $ed\equiv 1{\bmod {\phi (n)}}$ :

d = 2753 {\displaystyle d=2753\,} $d=2753\,$ , като 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\ пъти 2753=46801=1+15\ пъти 3120} $17\times 2753=46801=1+15\times 3120$ .

Публичният ключ е ( n = 3233 {\displaystyle n=3233} $n=3233$ , e = 17 {\displaystyle e=17} $e=17$ ). За подплатено съобщение m {\displaystyle m\,} $m\,$ функцията за криптиране c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} $c=m^{e}{\bmod {n}}$ става:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,} $c=m^{17}{\bmod {3}}233\,$

Частният ключ е ( n = 3233 {\displaystyle n=3233} $n=3233$ , d = 2753 {\displaystyle d=2753} $d=2753$ ). Функцията за декриптиране m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} $m=c^{d}{\bmod {n}}$ става:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,} $m=c^{2753}{\bmod {3}}233\,$

Например, за да криптирате m = 123 {\displaystyle m=123} $m=123$ , изчисляваме

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855} $c=123^{17}{\bmod {3}}233=855$

За декриптиране на c = 855 {\displaystyle c=855} $c=855$ , изчисляваме

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123} $m=855^{2753}{\bmod {3}}233=123$

И двете изчисления могат да бъдат изчислени бързо и лесно с помощта на алгоритъма за модулно експонентиране "квадрат и умножение".

Извеждане на уравнението RSA от теоремата на Ойлер

RSA може лесно да бъде изведена с помощта на теоремата на Ойлер и функцията на Ойлер за тоталност.

Започваме с теоремата на Ойлер,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}} $m^{\phi (n)}\equiv 1{\pmod {n}}$

трябва да покажем, че декриптирането на криптирано съобщение с правилния ключ ще даде оригиналното съобщение. При дадено подплатено съобщение m, шифърът c се изчислява по следния начин

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}} $c\equiv m^{e}{\pmod {n}}$

Замествайки в алгоритъма за декриптиране, получаваме

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}} $c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}$

Искаме да покажем, че тази стойност също е конгруентна на m. Стойностите на e и d са избрани така, че да удовлетворяват,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}} $ed\equiv 1{\pmod {\phi (n)}}$

Това означава, че съществува някакво цяло число k, такова, че

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1} $ed=k\times \phi (n)+1$

Сега заместваме криптираното, а след това декриптираното съобщение,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}} ${\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}$

Прилагаме теоремата на Ойлер и получаваме резултата.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}} $m\times (1)^{k}\equiv m{\pmod {n}}$

Схеми за подплатяване

Когато се използва в практиката, RSA трябва да се комбинира с някаква схема за подплънки, така че нито една стойност на M да не води до несигурни шифрови текстове. Използването на RSA без подложка може да доведе до някои проблеми:

Стойностите m = 0 или m = 1 винаги водят до шифрограми, равни съответно на 0 или 1, поради свойствата на експоненцията.
При криптиране с малки криптографски експоненти (напр. e = 3) и малки стойности на m (немодулният) резултат m e {\displaystyle m^{e}} $m^{e}$ може да бъде строго по-малък от модула n. В този случай шифровите текстове могат лесно да бъдат декриптирани, като се вземе коренът eth от шифровия текст, без да се взема предвид модулът.
RSA криптирането е детерминистичен алгоритъм за криптиране. Той няма случаен компонент. Затова нападателят може успешно да извърши атака с избран чист текст срещу криптосистемата. Те могат да направят речник, като криптират вероятни открити текстове под публичния ключ и съхраняват получените шифротекстове. След това нападателят може да наблюдава комуникационния канал. Веднага щом видят шифротекстове, които съвпадат с тези в техния речник, нападателите могат да използват този речник, за да научат съдържанието на съобщението.

На практика първите два проблема могат да възникнат, когато се изпращат кратки ASCII съобщения. В такива съобщения m може да бъде конкатенация на един или повече ASCII-енкодирани символи. Съобщение, състоящо се от един ASCII символ NUL (чиято числова стойност е 0), би било кодирано като m = 0, което води до шифров текст от 0, независимо от това какви стойности на e и N се използват. По подобен начин един ASCII SOH (чиято числова стойност е 1) винаги би дал шифров текст от 1. За системи, които обичайно използват малки стойности на e, като например 3, всички еднозначни ASCII съобщения, кодирани по тази схема, биха били несигурни, тъй като най-голямото m би имало стойност 255, а 255³ е по-малко от всеки разумен модул. Такива открити текстове могат да бъдат възстановени, като просто се вземе коренът от куба на шифровия текст.

За да се избегнат тези проблеми, практическите реализации на RSA обикновено вграждат някаква форма на структурирана, рандомизирана подложка в стойността m, преди да я криптират. Тази подложка гарантира, че m не попада в обхвата на несигурните открити текстове и че дадено съобщение, след като бъде подплатено, ще се криптира до един от голям брой различни възможни шифрови текстове. Последното свойство може да увеличи цената на речниковата атака отвъд възможностите на разумен нападател.

Стандарти като PKCS са внимателно разработени, за да подплатяват по сигурен начин съобщенията преди криптирането с RSA. Тъй като тези схеми подплатяват открития текст m с определен брой допълнителни битове, размерът на неподплатеното съобщение M трябва да бъде малко по-малък. Схемите за подплатяване на RSA трябва да бъдат внимателно проектирани, за да се предотвратят сложни атаки. Това може да бъде улеснено чрез предвидима структура на съобщението. В ранните версии на стандарта PKCS са използвани ad-hoc конструкции, за които по-късно е установено, че са уязвими към практическа адаптивна атака с избран шифров текст. Съвременните конструкции използват сигурни техники, като например оптимална асиметрична криптираща подложка (OAEP), за да защитят съобщенията, като същевременно предотвратят тези атаки. Стандартът PKCS съдържа и схеми за обработка, предназначени да осигурят допълнителна сигурност за подписите RSA, например Вероятностната схема за подписване за RSA (RSA-PSS).

Подписване на съобщения

Да предположим, че Алиса използва публичния ключ на Боб, за да му изпрати криптирано съобщение. В съобщението тя може да твърди, че е Алиса, но Боб няма как да провери дали съобщението наистина е от Алиса, тъй като всеки може да използва публичния ключ на Боб, за да му изпраща криптирани съобщения. Така че, за да се провери произходът на дадено съобщение, RSA може да се използва и за подписване на съобщението.

Да предположим, че Алиса желае да изпрати подписано съобщение на Боб. Тя изготвя хеш стойност на съобщението, повишава я до степента на d mod n (както при декриптиране на съобщение) и я прикачва като "подпис" към съобщението. Когато Боб получи подписаното съобщение, той повишава подписа до степента на e mod n (точно както при криптиране на съобщение) и сравнява получената хеш стойност с действителната хеш стойност на съобщението. Ако двете стойности съвпадат, той знае, че авторът на съобщението е притежавал тайния ключ на Алиса и че съобщението не е било подправяно оттогава.

Обърнете внимание, че схемите за сигурна подложка, като например RSA-PSS, са също толкова важни за сигурността на подписването на съобщенията, колкото и за криптирането им, и че един и същ ключ никога не трябва да се използва както за криптиране, така и за подписване.

Въпроси и отговори

В: Какво е RSA?

О: RSA (Rivest-Shamir-Adleman) е алгоритъм, използван от съвременните компютри за криптиране и декриптиране на съобщения. Това е асиметричен криптографски алгоритъм.

В: Какво означава асиметричен?

О: Асиметричен означава, че има два различни ключа - публичен и частен ключ.

В: Каква е основата на алгоритъма RSA?

О: Алгоритъмът се основава на факта, че намирането на множителите на голямо съставно число е трудно - когато множителите са прости числа, този проблем се нарича проста факторизация.

В: Как работи RSA?

О: RSA включва публичен ключ и частен ключ. Публичният ключ може да бъде известен на всеки - той се използва за криптиране на съобщения. Съобщенията, криптирани с публичния ключ, могат да бъдат декриптирани само с частния ключ, който трябва да се пази в тайна. Изчисляването на частния ключ от публичния ключ е много трудно.

Въпрос: Има ли друго наименование за този вид криптография?

О: Този тип криптография се нарича още криптография с публичен ключ, защото единият от ключовете може да бъде даден на всеки, като другият остава частен.

Въпрос: RSA генерира ли двойка ключове?

О: Да, RSA генерира двойка ключове - публичен и частен ключ - които се използват съответно за криптиране и декриптиране.