Asymetrická kryptografie

Aneb jak poslat tajnou zprávu v krabici nesené otrokem

Jak tedy poslat tajnou zprávu v krabici nesené otrokem?

Aristokles chce nečekaně poslat tajnou zprávu své přítelkyni Xantife. 

Jak to provede? 

K dipozici má:
	 otroka, 
	 krabici
	 a zámek. 
Xantife má také zámek.

Asymetrická kryptografie

Kryptografický systém umožňující výměnu šifrovaných zpráv bez nezávislé výměny klíčového materiálu.
Používá dva různé klíče:

Veřejný klíč - veřejně dostupný,

Soukromý klíč  - známý pouze vám.

Dva hlavní způsoby použití:

Šifrování komunikace,

Digitální podpisy.

Asymetrická kryptografie - Šifrování komunikace

Veřejný klíč - známý autorům zprávy, použije se k zašifrování zprávy,

Soukromý klíč  - známý pouze příjemci, použit k dešifrování zprávy.

Asymetrická kryptografie je typicky náročná na výpočetní zdroje, a tak obsahem šifrovaných zpráv zpravidla bývají klíče pro například proudové šifry.

Asymetrická kryptografie - Digitální podpisy

Protokol ověření autorství zprávy.

Veřejný klíč - známý příjemcům, umožňuje příjemci ověřit, že autor zprávy měl přístup k soukromému klíči.

Soukromý klíč  - známý autorovi, slouží k podpisu zprávy.

Příklad ze života- Secure SHell (SSH)

Rozšírený protokol v síťové komunikaci. Typický postup:

Při vašem prvním připojení k serveru dojde ke stažení veřejného klíče serveru na váš počítač (host).

Je navázáno zabezpečené spojení pomocí symetrické šifry:

host vygeneruje náhodný “session” klíč pro symetrickou šifru,

host zašifruje náhodný klíč pomocí veřejného klíče serveru a odešle ho serveru,

server dešifruje “session” klíč pomocí svého soukromého klíče,

server naváže zabezpečené spojení s hostem pomocí symetrické šifry.

Po navázání zabezpečeného spojení server ověří identitu hosta:

server zašle hostovi “výzvu” zašifrovanou pomocí veřejného klíče hosta,

host výzvu dešifuje pomocí svého soukromého klíče a odešle ji zpět serveru

Je navázáno zabezpečené spojení a ověřena identita hosta, na vašem terminálu se objeví prompt umožňující provádět příkazy na serveru.

RSA - nejslavnější algoritmus pro asymetrické šifrování

RSA stojí na faktu, že pro nás je faktorizace čísel časově náročnější než násobení:

https://ww.khanacademy.org/labs/explorations/time-complexity

Základ

Pár řádek o modulární aritmetice

a,b,c,r,n, .... ∈ Ζ

a je “coprime” k b ⟺ gcd(a,b) = 1

mod  jako binární operace: r = a mod n ⟺ existuje b takové, že a = bn + r, 0≤ r <n (zbytek po dělení n)

mod  jako relace kongruence: a≡b   (mod n) ⟺ n | a - b, platí, že a≡b   (mod n) ⟺ a mod n = b mod n

ab | n ⟹ a | n ∧ b | n, neboť pro nějaké c musí platit že n=abc

=> pro m,n “coprime”, a≡b  (mod mn) ⟺ a≡b  (mod n) ∧ a≡b   (mod m)

Eulerova funkce ϕ

ϕ(n) = #{a ∈ Ν | gcd(a,n) = 1}

Pro každé prvočíslo p, ϕ(p) = p - 1, neboť každé číslo 1, 2, ... p-1 je “coprime” s p

pro m “coprime” n, ϕ(mn) = ϕ(m)ϕ(n)

Malá Fermatova věta

p ∈ P, a ∈ Ζ ⟹ (a^p)≡ a     (mod p)

Příklad:

a= 2; p= 5;
a^p

32 - 2 == 5*6

Důkaz:

Na tabuli nebo vůbec

Euklidův rozšířený algoritmus (hledání inverzních čísel na okruzích s aritmetikou modulo n)

Euklidův algoritmus:

vstup: a,b ∈ Ζ, a≥b
výstup: gcd(a,b)

while b>0 do
	r:= a mod b
	a:= b
	b:= r
return a

Příklad:
gcd(93, 219)

Diofantické rovnice a Bezoutova věta:

T:Pro lib. a, b ∈ Ζ  nenulové exitují x,y ∈ Z takové, že gcd(a,b) = xa + yb

Příklad: gcd(219,93) = x*219 + y*93  (Použij Euklidův algoritmus k nalezení x a y)

Postup hledání inverze d=(e^(-1))mod m

Nalezni x a y taková, že gcd(m,e) = ex+my=1 pomocí Euklidova algoritmu a Bezoutovy věty

tedy ex+my ≡ 1 (mod m)

a neboť  my ≡ 0 (mod m) ⟹ ex ≡ 1 (mod m)

tzn x=d≡(e^(-1))

Příklad: najdi inverzi pro m=20 a e=3

RSA - algoritmus

Tvorba klíčů

Zvol dvě rozdílná prvočísla p a q. Označ jejich produkt n=pq.

Spočítej ϕ(n) = (p-1)(q-1).

Zvol veřejný exponent e takový, že 1<e<ϕ(n) a gcd(e,ϕ(n))=1.

Vypočítej d, modulo ϕ(n) inverzní prvek k e: ed ≡ 1	 mod(ϕ(n))

Lze, neboť gcd(e,ϕ(n)) = 1.

Uspořádaná dvojice (n,e) nyní tvoří veřejný klíč, uspořádaná čvteřice (d,p,q,ϕ(n)) tvoří soukromý klíč.

Šifrování s RSA

Pravidlo pro šifrování: cyphertext c = (Subscript[RSA, Public])(m) = (m^e) mod n, 1 < m < n-1

Pravidlo pro dešifrování: plaintext m = (Subscript[RSA, Private])(m) = (c^d) mod n

Identita: m = (Subscript[RSA, Private])((Subscript[RSA, Public])(m))

Podepisování s RSA

Podepsání: podpis s = (Subscript[RSA, Private])(h) = (h^d) mod n, 1 < m < n-1

Ověření podpisu: h = (Subscript[RSA, public])(s) = (s^e) mod n, 1 < m < n-1

Identita: h = (Subscript[RSA, Public])((Subscript[RSA, Private])(h))

Funguje to?

Všimněte si:

(Subscript[RSA, Private])((Subscript[RSA, Public])(m)) = ((m^e) mod ((n))^d) mod n = (m^ed) mod n

(Subscript[RSA, Public])((Subscript[RSA, Private])(o)) = ((m^d) mod ((n))^e) mod n = (m^ed) mod n

To znamená, že stačí ukázat že šifrovací pravidlo funguje, tzn. dokázat následující tvrzení:

Tvrzení(RSA): Pro výše definovanou dvojici (n,e) a čtveřici (d,p,q,ϕ(n)), kde  ed≡1   (mod ϕ(n)), platí: 
 c= (m^e) mod n, 1<m<n    ⟹    m= (c^d) mod n

Důkaz (pomocí Fermatovy malé věty ):

Chceme ukázat, že m≡(m^ed)  mod pq.

Přepišme ed≡1  (mod ϕ(n)) ⟺ ed-1 = h ϕ(n)=h(p-1)(q-1).

Platí, že m≡(m^ed)  mod pq  ⟺  pq | m-(m^ed)⟺  p|m-(m^ed) ∧ q|m-(m^ed), tzn. musíme ukázat, že m≡(m^ed)  mod p  a m≡(m^ed)  mod q:

buď m ≡ 0 mod p, pak m=kp pro nějaké celé k, a tedy m≡ m mod.

nebo m ≢ 0 mod p, a potom  (m^ed)= (m^(ed-1))m=(m^(h(p-1)(q-1)))m=((((m^(p-1))))^(h(q-1)))m ≡ (1^(h(q-1)))m ≡ m     (mod p)

Fermatovu malou větu jsme zde využili ve tvaru (m^(p-1))≡ 1 mod p, což je možné, neboť p nedělí m.

Obdobným postup zopakujeme pro q. Ve výsledku pak dostáváme m≡(m^ed)  mod pq, což jsme chtěli dokázat.

Šifrování s RSA - Příklady

Příklad na RSA spočitatelný v ruce

Tvorba klíčů:

Zvol p=11, q=3

n = pq = 3*11 = 33, ϕ(33) = 10*2 = 20

Zvol e=3, proveď kontrolu:

gcd(p-1, 3) = gcd(10,3) = 1

gcd(q-1,3) = gcd(2,3) = 1

tzn gcd(10*2, 3) = 1

Tedy mohu hledat inverzi mod 20 k e = 3, tzn d takové, že ed ≡ 1 (mod ϕ(n)):

tzn. hledáme hodnotu d takovou, že ϕ=20 dělí 3*d - 1

zkoušením zjišťujeme, že první hodnota splňující tento vztah je d=7:   3*7 - 1 = 20, nebo použijeme výsledek z rozšířeného euklidova algoritmu.

Máme tedy: Veřejný klíč (n, e) = (33, 3), a soukromý klíč (n, d) = (33, 7)

Šifrování zprávy m=7

c = (m^e) mod n = (7^3) mod 33 = 343 mod 33 = 13

Dešifrování šifrované zprávy c=13

m = (c^d)mod n = (13^7) mod 33 = 62 748 517 mod 33 = 7 mod 33

13^7

Poznámky:

Pro takto malou hodnotu n je m ∈ {1,..,32}. V tomto případě lze náš kryptosystém použít pouze jako načančanou variaci na Cézarovo šifru:

m  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 
c  0  1  8 27 31 26 18 13 17  3 10 11 12 19  5  9  4 29 24 28 

m 20 21 22 23 24 25 26 27 28 29 30 31 32
c 14 21 22 23 30 16 20 15  7  2  6 25 32

Prolomení šifry = vypočtení (c^(-e))mod n = (m^(e-e ))mod n = m mod n tzn. nalezení m = (13^(-3)) mod 33, což je pro velké hodnoty n velmi náročná úloha.

Výpočet (c^d) mod n lze zjednodušit skládánám čtverců: (c^d) mod n = (c^((Subscript[(∑^k), i=0])(2^i)))mod n (operaci modulo provedem na každém čvtverci zvlášť, neboť platí, bc mod n = (b mod n).(c mod n) mod n)

Poznámky k implementaci

Hledání prvočísel p a q

vygeneruj náhodné číslo r o bitové délce b/2, kde b je potřebná délka n,

nastav první dva a poslední bit r na 1,

(zajistí lichost, a správnou délku n)

r= 2^^100100
rr = 2^^110101
   s=2^^101100
ss=2^^111101
BaseForm[r*s,2]
BaseForm[rr*ss,2]

Je-li r prvočíslo, polož p=r. Zopakuj pro q (délky b-b/2).

Volba e

vhodnou volbou e je možné výrazně zrychlit operaci (m^e)mod n

požívaným algoritmem je “right-to-left binary method” pro výpočet s=(m^e)mod n:

e =(Subscript[(∑^(b-1)), i=0]) (Subscript[a, i])(2^i) ⟹ (m^e)= (m^(((Subscript[(∑^(b-1)), i=0]) (Subscript[a, i])(2^i))))=((∏_(i=0))^(b-1))((((b^(2^i))))^(Subscript[a, i]))

(Subscript[e=((Subscript[a, b-1]),(Subscript[a, b-2]), ... (Subscript[a, 0])), 2])
s = 1
for i=1 .. b
	if (Subscript[a, i])==1 then s = s*(2^i) mod n
end for

za e se proto obvykle volí 3, 17 a 65537 (Fermatova prvočísla, (Subscript[F, i])= (2^(2^i)) + 1):

BaseForm[3,2]
BaseForm[17,2]
BaseForm[65537,2]

V implementacích se typicky používá “padding”, mechanismus doplnění bytového zápisu zprávy náhodnými bity.

Přestože v algoritmu není rozdíl mezi podepisovacím a šifrovacím shématem, v implementaci se tyto rozdíly projeví:

Operace “podepsání” je prováděna na hashi zprávy, nikoliv na zprávě samotné

Při šifrování je vhodné použít náhodný “padding”, naopak při podepisování je třeba použít “padding” pokaždé stejný.

Příklad ze života (PKCS #1v1.5):

n=16^^A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170FBDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A93324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1CFB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
e=16^^010001
d=16^^67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D149E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319

Náhodný klíč pro AES-128:

AES= 16^^4E636AF98E40F3ADCFCCB698F4E80B9F

Pro dodání paddingu tvaru  00 || 02 || RandomBytes || 00 || AES

m=16^^0002257F48FD1F1793B7E5E02306F2D3228F5C95ADF5F31566729F132AA12009E3FC9B2B475CD6944EF191E3F59545E671E474B555799FE3756099F044964038B16B2148E9A2F9C6F44BB5C52E3C6C8061CF694145FAFDB24402AD1819EACEDF4A36C6E4D2CD8FC1D62E5A1268F496004E636AF98E40F3ADCFCCB698F4E80B9F
c= Mod[m^e , n]
m2=PowerMod[c,d, n]

BaseForm[c,16]
BaseForm[m2,16]
BaseForm[m,16]

m-m2

Srovnání s jinými algoritmy

Sym. šifra	Srovnatelná délka n v RSA	Srovnatelná Hash fce	Bezp. bitů
2TDEA*		1024			SHA-1				80
3TDEA		2048			SHA-224			112
AES-128		3072			SHA-256			128
AES-192		7680			SHA-384			192
AES-256		15360			SHA-512			256

Algoritmus ElGamal

Grupa

Grupa = dvojice (G, ++×), G ... množina, × ... operace

Cyklická grupa = grupa (G, ×) taková, že ∃ g ∈ G, G = {(g^n)| n ∈ Ζ}

Například multiplikativní grupa celých čísel modulo 5 = (SuperStar[(Subscript[Z, 5])]) s generátorem 2.

Tvorba klíčů - Příjemce zprávy A:

Zvol náhodné velké prvočíslo p a generátor g grupy (SuperStar[(Subscript[Ζ, p])]).

Zvol náhodné celé číslo x, 1≤  x ≤ p-2, a spočítej y=(g^x)mod p

Uspořádaná trojice (p, g, y) nyní tvoří veřejný klíč, číslo (x) tvoří soukromý klíč.

Šifrování - Odesílatel zprávy B:

Získej autentický veřejný klíč A:  (p, g, y)

Převeď zprávu na celé číslo m ∈ {0,1,..., p-1}

Zvol náhodné celé číslo k, 1 ≤ k ≤ p-2

Spočítej a= (g^k)mod p a b= (my^k)mod p

Odešli příjemci A šifrovanou zprávu c=(a,b)

Dešifrování - Příjemce zprávy A

Použij soukromý klíč k výpočtu t:=(a^(p-1-x))mod p    { ≡ (a^(-x)) ≡ (g^(-xk))  (mod p) }

Vypočítej m jako m=t*b mod p      {= ((a^(-x)))*b mod p }

Funguje to?

Tento systém funguje, neboť ((a^(-x)))×b ≡ (g^(-xk))×m ×(g^xk)≡m    (mod p).

Bezpečnost schématu

Bezpečnost tohoto systému je založena na předpokládané náročnosti řešení Diffie-Hellmanova problému pro některé cyklcké grupy s generátorem g:

Pro dané g, a hodnoty (g^x) a (g^y), jaká je hodnota (g^xy)?

Nejefektivnější známá metoda pro řešení této úlohu vede na problém tzv. diskrétního logaritmu (logaritmus na cyklické grupě):

Pro dané g a h, jaké je řešení h=(g^x)?

Stejně jako pro faktorizaci celých čísel, ani pro hledání diskrétního logaritmu neznáme žádný efektivní (nekvantový) algoritmus.

Šifrování s ElGamal - Příklad

Tvorba klíčů - Příjemce zprávy A:

Zvol prvočíslo p=2357 a generátor g=2 grupy  (SuperStar[(Subscript[Ζ, 2357])])

Zvol soukromý klíč x=1751, 1≤  x ≤ p-2,  a spočítej spočítej (g^x)mod p:

p:=2357; g:=2; x:= 1751;
y:=Mod[(g^x),p]
y

Máme tedy: Veřejný klíč (p, g, y) = (2357,2,1185), a soukromý klíč (x) = (1751)

Šifrování zprávy m=2035

Odesílatel zprávy B zvolí náhodné k = 1520 a spočítá  a = (2^1520) a b=2035 * (1185^1520)mod 2357 = 697.

k:=1520; m:= 2035;
a:= Mod[g^k,p]
b:= Mod[m*y^k,p]
a
b

Odesílatel B posílá A zprávu (a,b)=(1430, 697)

Dešifrování šifrované zprávy (a,b)=(1430, 697)

A nejdříve spočítá (a^(p-1-x))mod p a získá m jako m=((a^(-x)))*b mod p

t:= Mod[a^(p-x-1),p]
		Mod[t*b, p]

Biblio

http://www.linuxforums.org/forum/networking/160660-solved-how-does-ssh-encrypt-connections-2.html
http://docstore.mik.ua/orelly/networking_2ndEd/ssh/ch03_03.htm
http://www.di-mgt.com.au/rsa_theory.html
http://www.ietf.org/rfc/rfc4252.txt