Asümmeetriline krüptograafia

1.

ASÜMMEETRILINE KRÜPTOGRAAFIA

2.

3.

AVALIKU VÕTMEGA KRÜPTOGRAAFIA
Lahendab kaht olulist ülesannet:
Võtmejaotus
Digitaalallkiri (võimatu on üht osalejat välja vahetada)

4.

NÕUDED ALGORITMILE
Algoritm kasutab krüpteerimiseks üht võtit ja dekrüpteerimiseks teist võtit ning
ainult krüpteerimisalgoritmi ja krüpteerimisvõtit teades on dekrüpteerimisvõtit
arvutuslikult võimatu määrata.
Mõningate algoritmide puhul, näiteks RSA, saab kumbagi kahest võtmest kasutada nii
krüpteerimiseks kui ka dekrüpteerimiseks.

5.

AVALIK VÕTI JA PRIVAATVÕTI
Diffie ja Hellman kirjeldavad nõudeid, millele peab avaliku võtmega krüpteerimise algoritm vastama:
1. Arvutuslikult on lihtne luua paari (avalik võti KU, privaatvõti KR ).
2. Arvutuslikult on avalikku võtit ja krüpteerimata teadet M omades lihtne luua vastavat krüpteeritud teadet:
С = ЕKU[М]
3. Sõnumi dekrüpteerimine privaatvõtme abil on arvutuslikult lihtne:
М = DKR[C] = DKR[EKU[M]]
4. Arvutuslikult on avalikku võtit KU, teades võimatu kindlaks teha privaatvõtit KR.
5. Teades avalikku võtit KU ja krüpteeritud sõnumit С, on arvutuslikult võimatu taastada algset sõnumit М.

6.

ÜHEPOOLNE FUNKTSIOON
funktsioon, milles igal argumendil on üks pöördväärtus, samas kui funktsiooni enda arvutamine on lihtne, kuid
pöördfunktsiooni arvutamine on keeruline.
Y = f(X) - lihtne
X = f-1(Y) - keeruline

7.

ALGORITMI KEERUKUS
kui sisendi pikkuses on n bitti, siis on funktsiooni arvutusaeg proportsionaalne na, kus а on fikseeritud konstant.
Keerukus suureneb kiiremini kui võti.

8.

ALGORITMIDE VÕRDUS
Algoritm
Krüpteerimine / dekrüpteerimine Digiallkiri
RSA
Jah; ei sobi suurtele plokkidele
Jah
DSS
Ei
Jah
Diffie-Hellman
Ei
Ei

9.

ÜLESANNE
Mõelge välja ühesuunaline funktsioon

10.

RSA

11.

RSA
Algoritm Rivest-Shamir-Adleman (RSA)
selle töötasid välja 1977. aastal Ron Rivest, Adi Shamir ja Len Adleman
Faktoriseerimise probleem (arvu algtegurite leidmine)
Krüpteerimise plokkalgoritm
Krüptitud ja krüptimata andmed on täisarvud vahemikus 0 kuni n-1 mõne n jaoks

12.

ALGORITMI TOIMIMISE NÄIDE
Выбрать два простых числа: р = 7, q = 17.
Вычислить n = p x q = 7 x 17 = 119.
Вычислить
Выбрать е так, чтобы е было взаимно простым с
и меньше, чем
Определить d так, чтобы
d = 77, так как 77 x 5 = 385 = 4 x 96 + 1.
Результирующие ключи открытый KU = {5, 119} и закрытый KR = {77, 119}.
Например, требуется зашифровать сообщение М = 19.
195 = 66 (mod 119); С = 66.
Для дешифрования вычисляется 6677 (mod 119) = 19.

13.

VÕTMETE LOOMINE
Teha kindlaks
kaks algarvu
p ja q
Valida e ja
arvutada d

14.

JUHUSLIKE ARVUDE OTSING
Praegusel ajal ei ole teada algoritme, mis looks jususlikult suuri algarve. Selleks
kasutatav protseduur valib nõutavast vahemikust juhusliku paaritu arvu ja kontrollib,
kas see on algarv. Kui arv ei ole algarv, valitakse taas juhuslik arv, kuni leitakse algarv.
kui otsitakse algarvu vahemikus 2200, , siis tuleb teha umbes ln (2200) / 2 =
70 kontrolli.

15.

VÕIMALIKUD RÜNDED
Frontaalrünnak: katsetada kõiki võimalikke privaatvõtmeid.
Jagage n kaheks algteguriks. See annab võimaluse välja arvutada
.
Leida
otse, esialgu ilma p ja q kindlaks määramiseta. See annab ka võimaluse
leida
Määrata kindlaks otse d, teadmata
.
väärtust.

16.

ALGORITMI STABIILSUS
1. Võtme pikkuse suurendamine
2. Kaasaegses etapis arvatakse, et 100 arvust koosnevat arvu saab teguriteks jaotada
umbes kahe nädala jooksul. 150 arvust koosnevat arvu saab jaotada umbes aasta
jooksul. Arv, mis koosneb 200 arvust, on suurem kui arvutusvõimekus.
3. Praegu tuntud algoritmide puhul on
määramise ülesanne antud e ja n põhjal
vähemalt ajaliselt võrreldav arvu faktoriseerimise ülesandega.

17.

RSA NÄITED
https://www.youtube.com/watch?v=vooHjWxmcIE
https://www.youtube.com/watch?v=4zahvcJ9glg
https://www.youtube.com/watch?v=oOcTVTpUsPQ

18.

RSA SECURITY
In 2009, Benjamin Moody factored an RSA-512 bit key in 73 days using only public software (GGNFS) and his
desktop computer (a dual-core Athlon64 with a 1,900 MHz cpu.). Just less than five gigabytes of disk storage was
required and about 2.5 gigabytes of RAM for the sieving process. The first RSA-512 factorization in 1999 required
the equivalent of 8,400 MIPS years, over an elapsed time of about seven months.
As of 2019, the largest factored RSA number was 795 bits long (240 decimal digits, RSA-240). Its factorization
took around 900 CPU years. No larger RSA key is known publicly to have been factored. In practice, RSA keys are
typically 1024 to 4096 bits long.

19.

DIFFIE-HELLMANI ALGORITM

20.

DIFFIE-HELLMANI VÕTME OMAVAHELISE VAHETAMISE
ALGORITM
Krüptograafiline protokoll, mis võimaldab kahel või enamal osapoolel saada kaitsmata sidekanali kaudu ühise
salajase võtme. Saadud võtit kasutatakse edasise vahetamise sümmeetriliste krüpteerimisalgoritmide abil
krüptimiseks.
Puhtal kujul on Diffie-Hellmani algoritm vastuvõtlik sidekanalis andmete muutmise, sealhulgas man-in-themiddle-rünnaku suhtes, seega kasutavad seda rakendavad skeemid täiendavaid ühe- või kahesuunalisi
autentimismeetodeid.

21.

THE DIFFIE-HELLMAN KEY EXCHANGE
n and g are two agreed large numbers
x and y are large (say, 512-bit) private
numbers generated by both sides
The trouble is, given only g mod n, it is
hard to find x.All currently-known
algorithms simply take too long, even on
massively parallel supercomputers.
x

22.

THE DIFFIE-HELLMAN KEY EXCHANGE (2)
https://www.youtube.com/watch?v=YEBfamv-_do

23.

ALGORITMI TURVALISUS
Diffie-Hellmani võtmevahetuse turvalisus tuleneb asjaolust, et kuigi algarvu mooduli järgi on eksponente
suhteliselt lihtne arvutada, on diskreetsete logaritmide arvutamine väga keeruline. Ülesannet peetakse
võimatuks suurte algarvude jaoks.
Antud algoritm on man-in-the-middle-tüüpi rünnakutele vastuvõtlik. Kui ründaja suudab sooritada aktiivse
rünnaku, s.t on võimeline mitte ainult sõnumeid pealt kuulama, vaid ka asendama need muudega, suudab ta
kinni püüda osalejate Yi ja Yj, avalikke võtmeid, luua oma avaliku ja privaatvõtme paari (Xоп, Yоп) ja saata
igale osalejale oma avalik võti. Pärast seda arvutab iga osaleja võtme, mis on ühine ründajaga, mitte teise
osalejaga. Kui terviklikkuse kontrolli pole, ei suuda osalejad sellist asendust tuvastada

24.

KAHEPOOLSE AUTENTIMISE PROTOKOLL
A, B are the identities of Alice and Bob.
Ri - the challenge, where the subscript identifies the
challenger.
Ki - are keys, where i indicates the owner.

25.

KAHEPOOLSE AUTENTIMISE PROTOKOLL: RÜNDELE VASTU SEISNUD
Second session is opened (message 3), supplying the
RB taken
from message 2.
Bob encrypts it and sends back KAB (RB) in message 4.

26.

KAHEPOOLSE AUTENTIMISE PROTOKOLL: LAHENDUS
HMAC – hashed message authentication code
Data structured is hashed into the HMAC, for
example using SHA-1.
Based on received information, Alice can compute the
HMAC herself.
Алгоритм обмена ключа Диффи-Хеллмана

27.

DIFFIE-HELLMANI PROTOKOLL: MAN-IN-THE-MIDDLE-RÜNNAK
Alice thinks she is talking to Bob so she
establishes a session key (with Trudy). So
does Bob.
Every message that Alice sends on the
encrypted session is captured by Trudy,
stored, modified if desired, and then
(optionally) passed on to Bob. Similarly, in
the other direction.

28.

VÕTMEJAOTUSKESKUSE ABIL AUTENTIMINE: TAASESITUSRÜNNE
KDC - Key distribution center
Ks - generated session key
By snooping on the network, Trudy copies
message 2 and the money-transfer request
that follows it. Later, she replays both of them
to Bob.

29.

NEEDHAM–SCHROEDER PROTOCOL.
NEEDHAM–SCHROEDERI PROTOKOLL
sümmeetrilise ja asümmeetrilise autentimise ja võtmevahetuse protokollide üldnimetus.
Mõlemat protokolli pakkusid välja Michael Schroeder ja Roger Needham.
Sümmeetrilisel krüptimisel põhinev variant kasutab vahepealset usaldusväärset osapoolt.
See protokoll sai aluseks tervele klassile sellistele protokollidele. Näiteks on Kerberos üks sümmeetrilise
Needham-Schroederi protokolli variantidest.
Asümmeetrilisel krüptimisel põhinev variant on mõeldud poolte vastastikuseks autentimiseks. Originaalses
olekus on mõlemad protokolli variandid rünnakutele vastuvõtlikud.

30.

NEEDHAM–SCHROEDER PROTOCOL.
NEEDHAM–SCHROEDERI PROTOKOLL(2)

31.

OTWAY–REES PROTOCOL. OTWAY-REESI PROTOKOLL
sümmeetriline autentimis- ja
võtmevahetusprotokoll, mis
kasutab usaldusväärset osapoolt.

32.

KERBEROS

33.

KERBEROS (2)
Võrgu autentimisprotokoll, mis pakub mehhanismi kliendi ja serveri vastastikuseks
autentimiseks enne nendevahelise ühenduse loomist, kusjuures esmane teabevahetus
kliendi ja serveri vahel toimub ebaturvalises keskkonnas ning edastatavaid pakette saab
vahelt kinni püüda ja muuta.

34.

ÜLESANNE
Kirjeldage Kerberose protokolli kasutusvaldkondi

35.

KERBEROS
TGS — ticket granting server

36.

KERBEROS
Kerberos on võrgu autentimisprotokoll, mis pakub mehhanismi kliendi ja serveri vastastikuseks autentimiseks
enne nendevahelise ühenduse loomist, kusjuures esmane teabevahetus kliendi ja serveri vahel toimub
ebaturvalises keskkonnas ning edastatavaid pakette saab vahelt kinni püüda ja muuta.
loodud 1983. aastal Massachusettsi Tehnoloogiainstituudis (MIT)
Põhineb sümmeetrilise võtmega krüptograafial ja nõuab usaldusväärset kolmandat osapoolt ning saab vajadusel
kasutada autentimisprotsessis asümmeetrilist krüptograafiat.
Vaikimisi kasutab 88 UDP porti.

37.

ÜHEKORDSE SISSELOGIMISE TEHNOLOOGIA
Ühekordse sisselogimise tehnoloogia (Single Sign-On)
Kasutusel domeeni autentimiseks Windowsis.

38.

KERBEROS 5

39.

KERBEROS 4 VS KERBEROS 5
Kerberos 4 põhineb DES-il
Sõnumiväljade vormingut ei ole võimalik muuta