Essee - Tiedon salaaminen RSA-menetelmällä
1.11.1999
Markus Vartiovaara, 45397H
Petteri Kaski, 46572D
Tik
Teknillinen korkeakoulu
Tiivistelmä
Tiedonsalauksen merkitys tulee kasvamaan ja käyttökelpoisten salausmenetelmien merkitys kasvaa jatkuvasti. Tässä dokumentissa on esitelty RSA-salausmenetelmään perustuvia periaatteita ja toimintoja. Esittelemme menetelmän yleisellä tasolla (puuttumatta algoritmin takana olevaan matematiikkaan sen tarkemmin). Dokumentin lopussa olevista viittauksista löytyy tarkempaa tietoa niin itse algoritmista, sen toteutuksesta sekä sovelluksista.
Kahdesta avainparista koostuva RSA-menetelmä on ainut laajaa luottamusta ja suosiota nauttiva asymmetrinen salausmenetelmä [4]. Tämän dokumentin luvuissa 1-3 on johdantoa tarkoituksena antaa lukijalle sopiva peruskäsitys tiedonsalauksesta ja RSA:n merkitys osana tätä aluetta. Tärkeää on myös tiedostaa, että RSA (tai asymmetriset menetelmät ylipäätään) ei ole suinkaan perinteisiä salaisen avaimen menetelmiä luotettavampi.
Dokumentissa käydään lyhyesti läpi esimerkki RSA:n soveltamisesta tiedonsalaukseen. Hash-funktioista mainitaan lyhyesti kappalessa 6, koska ne ovat oleellinen osa digitaalista allekirjoitusta, joissa RSA:ta voidaan mainiosti soveltaa. Katsaus nykypäivään on RSA:n osalta ajankohtainen, koska sovellusten määrä on räjähdysmäisesti kasvamassa ja kysyntä ja tarve tietoturvamekanismeille on huutava.
1 Johdanto
2 Yleistä tiedon salaamisesta
3 Yleistä salausjärjestelmistä
3.1 Salausjärjestelmät
3.2 Allekirjoitusjärjestelmät
4 RSA:n lyhyt kuvaus
4.1 RSA julkinen avain
4.2 RSA salainen avain
4.3 Kryptograafiset primitiivit
5 Salaaminen RSA:lla
6 Muuta
6.1 Hash-funktiot
7 Katsaus nykyhetkeen
8 Lisätietoja
9 Lähteet
Tiedon salaaminen tulee olemaan yksi merkittävimmistä tekniikoista tulevaisuuden tietoliikenteessä. Kasvava Internet-liikenne tarvitsee tehokkaita, toimivia, luotettavia ja riittävän yksinkertaisia ratkaisuja turvalliseen tiedon siirtoon. Esimerkiksi kaupankäynti ja rahojen siirtäminen verkossa tulee nostamaan luotettavan salauksen avainasemaan. Tällä hetkellä ollaan myös tilanteessa, jossa tietotekniikkaan huonosti perehtyneet käyttäjät opettelevat vasta luottamaan tietoverkkojen turvallisuuteen ja käytettävien salausmenetelmien luotettavuuteen.
Julkisen avaimen kryptausmenetelmä RSA (Rivest-Shamir-Adleman) on nykymittapuun mukaan yksi turvallisimmista algoritmeista, minkä vuoksi se on hyvin yleisesti käytössä. Se perustuu suuriin alkulukuihin, joista luotua purkuavainta ei voida nykyisen tiedon rajoissa laskea yleisestä salausavaimesta.
Selväkielisen sanoman muuttamista sellaiseen muotoon, että sen sisältö on ulkopuolisilta "piilossa" kutsutaan salaamiseksi eli kryptaamiseksi. Purkamista sanotaan vastaavasti dekryptaamiseksi. Kryptografia on salaamisen tiede, kryptoanalyysi keskittyy salausten murtamiseen ilman asianmukaisten avainten tuntemista ja kryptografia on eräs matematiikan haara, joka pyrkii soveltamaan ja kehittämään matematiikkaa tiedon salauksen näkökulmasta.
On olemassa kaksi erilaista avaimiin pohjautuvaa menetelmää: symmetrinen (salattu avain) ja epäsymmetrinen (julkinen avain). Erona on se, että symmetrinen menetelmä käyttää samaa avainta sekä salaamiseen että purkamiseen (tai purkuavain on helposti johdettavissa salausavaimesta), kun taas epäsymmetrinen menetelmä käyttää eri avainta salaamiseen ja purkamiseen, eikä purkuavain ole johdettavissa alkuperäisestä salausavaimesta.
Symmetriset menetelmät voidaan jakaa edelleen kahteen tyyppiin: koodivirtoihin ja koodilohkoihin. Koodivirtoihin perustuvat menetelmät salaavat selväkielistä sanomaa bitti kerrallaan, kun taas koodilohkoihin perustuvat menetelmät salaavat useamman bitin jaksoissa (64 bittiä yleinen nykymenetelmissä).
Epäsymmetriset menetelmät (myös kutsutaan julkisen avaimen menetelmiksi) sallivat salausavaimen olevan julkinen tarjoten kenelle tahansa mahdollisuuden salaamiseen, mutta vain oikea vastaanottaja (joka tietää purkamisavaimen) voi purkaa viestin. Salausavainta kutsutaan julkiseksi avaimeksi ja purkuavain on salainen avain.
Symmetriset menetelmät ovat huomattavasti nopeampia ajaa tietokoneilla kuin epäsymmetriset. Käytännössä niitä käytetään yhdessä salaamalla satunnanisesti luotuja avaimia julkisen avaimen menetelmiä käyttäen ja varsinainen sanoma salataan symmetrisiä menetelmiä käyttäen. Tunnettuja symmetrisiä menetelmiä ovat mm. DES ja IDEA. RSA on ehkä tunnetuin epäsymmetrinen menetelmä. [3]
OSI (Open Systems Interconnections) eli avoimien systeemien välinen tiedonsiirto luonnollisesti vaatii yhteisiä sopimuksia, joihin sisältyy myös tiedonsalaus siirron aikana. [5]
Järjestelmällä tarkoitetaan primitiivien ja muiden tekniikoiden avulla muodostettua kokonaisuutta, jotta saavutetaan haluttu päämäärä tietoturvatasolla. Järjestelmät voidaan karkeasti jakaa kahteen tyyppiin: salausjärjestelmiin ja allekirjoitusjärjestelmiin.
Salausjärjestelmä koostuu salausoperaatiosta ja purkuoperaatiosta. Salausoperaatio tuottaa salatun sanoman (ciphertext) alkuperäisestä viestistä vastaanottajan julkisella avaimella. Tämä sanoma vastaavasti puretaan vastaanottajan salaisella avaimella.
Allekirjoitusjärjestelmät koostuvat allekirjoituksen muodostamisesta sekä allekirjoituksen tarkistamisesta. Allekirjoitus muodostetaan sanomasta allekirjoittajan salaisella avaimella, ja se voidaan tarkistaa allekirjoittajan julkisella avaimella.
RSA:n avainpari muodostetaan kahden suuren alkuluvun tulosta. Salausmenetelmän luotettavuus perustuukin olettamukseen, että tämän tulon pilkkominen takaisin kahdeksi alkuluvuksi on riittävän työläs eikä tehokkaita algoritmejä ole mahdollista kehittää. Toisaalta ei ole myöskään osoitettu, etteikö sellaista menetelmää olisi olemassa.
RSA julkinen avain koostuu kahdesta komponentista: n (jakojäännös-parametri, ei-negatiivinen kokonaisluku) ja e (julkinen eksponentti, ei-negatiivinen kokonaisluku). [2]
RSA julkisessa avaimessa n on kahden alkuluvun p ja q tulo, ja eksponentti e on välillä 3 ja n-1. Lisäksi suurimman yhteisen jakajan ehdon tulee täyttyä. [2]
RSA salaiselle avaimelle esitetään kaksi esitystapaa.
1. tapa on samankaltainen kuin julkisen avaimen esitys: n (jakojäännös, ei-negatiivinen kokonaisluku) ja d (salainen eksponentti, ei-negatiivinen kokonaisluku). [1]
2. tapa koostuu viidestä kokonaisluvusta p, q, dP, dQ ja qInv. p ja q ovat ei-negatiivisia tekijöitä, dP ja dQ niiden vastaavat eksponentit ja qInv on ns. CRT kerroin. [2]
Em. komponenttien tulee vastaavasti täyttää tietyt ehdot, jotta RSA salainen avain täyttää sille määritellyt ehdot.
Kryptograafiset primitiivit ovat matemaattisia perusoperaatioita, joiden päälle salausmallit ja -järjestelmät voidaan rakentaa. Ne voidaan toteuttaa joko ohjelmallisesti tai rautatasolla, ja ovat vahvasti sidottu osaksi kokonaisuutta (eivät takaa yksinään tietoturvaa). [2]
Primitiivit voidaan jakaa neljään primitiivityyppiin, jotka ovat pareittain: salaus- ja purkuprimitiivit (encryption, decryption) ja allekirjoitus- ja tarkistusprimitiivit (signature, verifcation). [2]
Seuraavassa kuvataan esimerkin avulla RSA-algoritmin pääpiirteet [4]. Esityksessä käytetty merkintä Fii(n) viittaa funktioon (Euler), jonka arvona on lukua n pienemmät ja sille suhteellisten alkulukujen määrä. Gcd-funktio viittaa kahden parametrinsä suurimpaan yhteiseen tekijään (greatest common divisor).
| Valitaan alkuluvut p ja q.
| Esim. p=7 ja q=17.
|
| Lasketaan n = p x q
| 7 x 17 = 119
|
| Lasketaan Fii(n) = (p-1) x (q-1)
| Fii(n) = 96
|
| Valitaan kokonaisluku e, siten että gcd(Fii(n), e)=1; 1 < e < Fii(n)
| Valitaan e = 5, koska 5 on suhteellinen alkuluku 96:lle.
|
| Lasketaan d = e^(-1) mod Fii(n)
| de = 1 mod 96 ja d < 96. Tässä tapauksessa d 0 77, koska 77 x 5 = 385 = 4 x 96 +1.
|
| Nyt julkinen avain KU = [e,n] ja salainen avain KR =[d,n].
| Julkinen avain = [5, 119] ja salainen [77, 119].
|
Salaaminen (M < n, M = plaintext viesti):
C = M^e (mod n)
| Esim. M = 19, jolloin 19^5 = 2476099. Lasketaan jakojäännös = 66, joka on salattu viesti.
|
Purkaminen (C = salattu viesti):
M = C^d (mod n)
| Esim. C = 66 eli 66^77 = 1.27 x 10^140, josta jakojäännös jaettaessa 119 saadaan 19 = M.
|
Hash-funktioit ovat deterministisiä (lopputulos riippuu täysin syötteestä). Hash-funktio ottaa syötteenä ei-vakiopituisen oktettijonon ja muodostaa siitä vakiopituisia oktettijonoja. Hash-funktion tulo on tiiviste syötteestä eli eri syötteistä muodostuu eri palautusarvot.
Tarve tietoturvalle on tänä päivänä suuri ja tulevaisuudessa valtava. Informaation siirtyessä sähköiseen esitysmuotoon ja verkoitse tapahtuvan kommunikaation räjähdysmäinen kasvu tarvitsevat uudenlaista tietoturvaa. Tiedon salaus ja sähköinen allekirjoitus ovat tulevaisuuden vastineita esim. henkilöllisyystodistuksille ja kirjatuille kirjeille.
Tässä lyhyesti esitelty RSA-menetelmä on merkittävässä asemassa
tulevaisuuden tietoturvajärjestelmissä ja -sovelluksissa sen tarjoamien kehittyneiden ominaisuuksiensa ansiosta. Jo tällä hetkellä olemassa olevista sovelluksista esim. Pretty Good Privacy (PGP) käyttää RSA-avaimia tietoliikenteen salaamiseen ja koekäytössä jo olevalla HST-kortilla (Henkilön Sähköinen Tunnistaminen) suositellaan vahvasti vähintään 1024-bittisten RSA-avaimien käyttämistä kansalaisten luotettavassa tunnistamisessa.
Tietoturvallisuus on häilyvä käsite, joka muuttuu ajan myötä. Spekulointi esim. riittävän pitkästä avaimesta on tänä päivänä kaukana siitä mitä vain muutama vuosi sitten. Tänä päivänä on mahdollista rakentaa erittäin tehokkaita vain murtamiseen tarkoitettuja sulautettuja järjestelmiä, joiden avulla voidaan ratkaista (esim. rinnakkaisprosessoinnilla) pitkiäkin salausavaimia. Ratkaisu voi löytyä myös fysiikasta, jossa ns. elektronilukoilla voidaan äärettömän nopeasti löytää ratkaisuja periaatteessa ratkeamattomiin ongelmiin. Tällöin kaikki salausjärjestelmät muuttuvat hetkessä turvattomiksi.
Salausalgoritmit RSA-menetelmä etunenässä tulevat meidän jokaisen arkipäivään kovalla vauhdilla. Kaukana ei ole esimerkiksi hetki, kun ensimmäisen kerran allekirjoitat kauppalaskusi omalla RSA-avaimellasi tai toteat yrityksen julkisella avaimella, että sen kotisivuillaan esittämä kauppasopimus on aidosti pätevä ja juridisesti sitova. Muutokset tulevat olemaan suuria ...
[1] Amoroso, Edward, Fundamentals of Computer Security Technology
Prentice Hall 1994
[2] Comer, Douglas, Internetworking with TCP/IP
3rd edition
[3] Cormen, T. & Leiserson, E. & Rivest, R, Introduction to Algorithms
The MIT Press & McGraw-Hill Book co. 1990
[4] Gollmann, Dieter, Computer Security
Wiley 1999
[5] Guttman, E., Sun Microsystems, RFC #2504, Users' Security Handbook, 2/99 (viitattu 29.09.1999)
http://www.es.net/pub/rfcs/rfc2504.txt
[6] IAB, IASG, RFC #1984, IAB and IESG Statement on Cryptographic Technology and the Internet, 8/96 (viitattu 29.09.1999)
http://www.es.net/pub/rfcs/rfc1984.txt
[7] Penttinen, Heikki, HST-järjestelmän tekninen määrittely: yhteiset vaatimukset pilot-projekteille , 1997-11-24
http://www.vn.fi/vm/suomi/muuta/vahti/hst_ma1.htm
[8] RSA Security homepages (viitattu 29.09.1999)
http://www.rsa.com/
[9] Salomaa, A, Public-Key Cryptograph
New York: Springer-Verlag, 1996
[10] SSH Communications Security Ltd., SSH / Cryptographic algorithms / RSA, 1998-1999 (viitattu 29.09.1999)
http://www.ssh.fi/tech/crypto/algorithms.html#asymmetric
[1] Kaliski, B., RFC #2437, PKCS #1: RSA Cryptography Specifications Version 2.0, 10/98 (viitattu 29.09.1999)
http://www.es.net/pub/rfcs/rfc2437.txt
[2] Kaliski, B., RFC #2313, PKCS #1: RSA Encryption Version 1.5, 3/98 (viitattu 29.09.1999)
http://www.es.net/pub/rfcs/rfc2313.txt
[3] Schneider, B., Applied Cryptography
New York: Wiley, 1996
[4] Stallings, William, Cryptography and network security
2nd edition
[5] Tanenbaum, Andrew S, Computer Networks
Third Edition, Prentice-Hall International, Inc., 1996
|