RSA on julkisen avaimen salausalgoritmi. RSA nimi tulee algoritmin keksijöiden nimistä. Algoritmin kehittivät vuonna 1977 Ron Rivest, Adi Shamir ja Leonard (Len) Adleman. RSA ei ollut täysin uusi keksintö. Vuonna 1976 Whitfield Diffie ja Martin Hellman julkaisivat avaimenvaihtoalgoritmin. Diffie-Hellman algoritmi ja RSA ovat pohjimmiltaan saman matematiikan eri implementaatiota. Englantilainen matemaatikko Clifford Cocks kehitti RSA:ta vastaavan menetelmän 1973, mutta kyseistä menetelmää ei julkaistu kuin vasta 1997. Historia osoittaa, että usein samat asiat keksitään useassa paikassa toisistaan riippumatta suurinpiirtein samaan aikaan. Auringon alla ei siis ole mitään uutta.
Mutta mikä on RSA salausalgoritmi? Useimmissa salausalgoritmeissa on tarve vaihtaa salausavainta lähettäjän ja vastaanottajan välillä. Tämä on usein salauksen heikoin lenkki. Useimpien salausalgoritmien turvallisuus heikkenee jos samaa salausavainta käytetään useaan kertaan. Tämä vain korostaa salausavaimen vaihdosta syntyvää ongelmaa. Avaimen välitys pitää pystyä tekemään turvallisesti kerta toisensa jälkeen. RSA ratkaisee tämän ongelma. RSA-menetelmässä salausavain on julkinen, sen voi vaikka julkaista päivälehdessä.
RSA salauksessa lähettäjällä ja vastaanottajalla on molemmilla kaksi salausavainta, julkinen- ja salainen avain. Viestin salaus tapahtuu käyttämällä lähettäjän salaista avainta ja vastaanottajan julkista avainta. Salauksen purku tapahtuu käyttämällä vastaanottajan salaista avainta ja lähettäjän julkista avainta. Järjestelyn lopputulos on se, että salaista avainta ei koskaan tarvitse vaihtaa lähettäjän ja vastaanottajan kesken. Sanomaa ei voi avata käyttämällä pelkästää julkista avainta. RSA:n matematiikka mahdollistaa myös vahvan digitaalisen allekirjoituksen (tunnistamisen) jos avaimia käytetään hieman eri järjestyksessä.
RSA menetelmä turvallisuus perustuu siihen, että suurien lukujen tekijöihin jako on vaikeaa. Kertomalla keskenään kaksi suurta lukua saa vielä suuremman luvun. Mutta sama toisin päin, tekijöihin jako, on vaikeaa. RSA-menetelmässä mainitut kaksi suurta lukua ovat alkulukuja, siis lukuja joilla ei ole tekijöitä. Kahden alkuluvun tulolla on tasan kaksi tekijää, kyseiset alkuluvut. Tekijöihin jaossa on siis löydettävä kyseiset kaksi suurta alkulukua. Suurten lukujen tekijöihin jakoon kuluu paljon aikaa. Vahvalla avaimella (suuri luku) salatun viestin murtamiseen kuluu supertietokoneellakin enemmän aikaa kuin maailmankaikkeuden tämän hetkinen ikä.
RSA salauksen matematiikka ei itsessään ole vielä riittävä vahvaan salaukseen. Salauksen lopputulos on oikeastaan yksinkertainen korvaussalakirjoitus, joka on periaatteessa helppo murtaa. Todelliseen RSA menetelmään on lisätty erilaisia manipulaatioita, joilla salattavaa viestiä käsitellään ennen varsinaista RSA salausta. RSA salaus on laskennallisesti raskas menetelmä. Sen vuoksi useissa julkisen avaimen menetelmissä avaimen vaihto tapahtuu RSA menetelmän turvin mutta varsinaisen viestin salaaminen jollakin laskennallisesti tehokkaalla menetelmällä (esim. DES).
Olkoon RSA kätkö herrojen Rivest, Shamir ja Adleman kunniaksi. Sinun tehtäväsi on avata kuvauksessa oleva RSA matematiikalla salattu viesti. Kätkön koordinaatit ja muuta tarpeelliset ohjeet kätkön löytymiseen on kätkökuvauksen salatussa osassa. Koska kätkö on tarkoitettu löydettäväksi, salauksessa ei ole käytetty vahvaa avainta. Avainavaruus on alle 10 bittiä. Kuvauksen salatussa osassa ei ole käytetty mitään datan sekoitusta vaan pelkästään RSA salauksen perusmatematiikkaa. Viestin saattaa siis avata myös kyryptoanalyysin keinoin. Varmimmin lopputulokseen pääsee kuitenkin käyttämällä raakaa voimaa eli kokeilemalla kaikki mahdolliset avaimet.
Onnea matkaan!
|
RSA is a cryptosystem that uses the public key. Name RSA comes after its inventors, Ron Rivest, Adi Shamir and Leonard (Len) Adleman. The algorithm was published the first time on 1977. RSA was not the novel idea really. A few years earlier, 1976, Whitfield Diffien and Martin Hellman published a key exchange algorithm that was also based to same idea of public key. The Diffie-Hellman and RSA algorithms are different utilizations of the same math. Englishman Clifford Cock developed an algorithm similar to RSA on 1973 but it was published as late as 1997. As we can see, there is very little new under the sun.
So, what is RSA cipher anyway? Most of the cryptosystems requires exchange of the cipher key between the sender and receiver. Often this is the weakest link in the system. Many cryptosystems rely on that the key is not used too many times or it is used once only therefore there will be need to preform the safe key exchange time after time. This is where RSA comes in. RSA is a public key cryptosystem. The key can be really published even in a newspaper.
RSA cryptosystem uses two separate key. The sender and receiver both have a public key and a private key. The message is encrypted by using the receiver’s public key and sender’s private key. Then the message is decrypted by using the receiver private key and sender’s public key. The message can’t be decrypted by using the public key only. Use of this arrangement doesn’t require exchange of the private key. By using the keys in separate order RSA enables digital signature too.
The strength of RSA cryptosystem lays on the fact that bignum factorization is hard task. It is very easy to generate big numbers. Just multiply two big integers and your will have even bigger integer. Opposite of this, factorization, is very difficult task for big numbers. RSA uses two big primes that are multiplied. The product can be factorized only by finding the mentioned two big primes. There is no any know shortcut to find mentioned two primes than doing proper factorization. Computational time of factorization of big numbers can be very long, resulting tremendous time consumption in breaking RSA cipher. This is where security of RSA comes from.
The math part of the RSA cipher is not enough for strong cryptosystem. In theory, the math of RSA only leads to substitution cipher which is, in theory, easy to break. The realization of RSA includes various manipulations of the data prior to RSA cipher. The purpose of manipulations is to hinder or scramble anything in the data that can be used to break the code. RSA is a task that is computationally hard to perform therefor many realizations of the public key crypto system utilize public key cryptosystem only in key exchange and then the real data is to be encoded by using computationally effient methods (like DES for example).
Let this RSA cache be honor to Rivest, Shamir and Adleman. Your task is the break the code below. Coordinates for the cache can be found from the message below. As the cache is meant to be found, RSA utilization used here is not strong. The key space is less than ten bits. There is no additional padding or scrambling in use but only the basic RSA encoding is used. In theory one may try cryptanalysis but brute force will work well here.
Good luck!
|