On erilaisia koodaustekniikoita, joilla voidaan esimerkiksi tallentaa salasanoja kryptatussa muodossa. Tällöin alkuperäisen sanan saaminen kryptatusta versiosta on käytännössä mahdotonta.
Eri metodeja kryptauksen tekemiseen on luonnollisesti useampia ja mieleen tuli, että jos kryptaan salasanan s metodilla A, jolloin kryptattu salasana on vaikka A(s), niin onko olemassa keinoa saada tuosta kryptatusta versiosta toisella mekanismilla B kryptatty versio? Eli onko edes teoriassa jotain kevyttä keinoa luoda muunnoskuvaus A(s) -> B(s) tietämättä alkuperäistä salasanaa s jos A ja B ovat sinällään järkeviä toteutuksia, eli palautus A(s) tai B(s) -> s on hyvin vaikea?
Eri metodeja kryptauksen tekemiseen on luonnollisesti useampia ja mieleen tuli, että jos kryptaan salasanan s metodilla A, jolloin kryptattu salasana on vaikka A(s), niin onko olemassa keinoa saada tuosta kryptatusta versiosta toisella mekanismilla B kryptatty versio? Eli onko edes teoriassa jotain kevyttä keinoa luoda muunnoskuvaus A(s) -> B(s) tietämättä alkuperäistä salasanaa s jos A ja B ovat sinällään järkeviä toteutuksia, eli palautus A(s) tai B(s) -> s on hyvin vaikea?
Vastaukset 7
Vanhimmat
Sillä oletuksella, että algoritmit A ja B ovat OLEELLISESTI eri algoritmit (Esim. A ei ole B:n osa) niin löytyykö tehokasta algoritmia C, joka syötteelle A(s) antaa B(s):n on yhtä vaikea (ellei vaikeampia) kuin kysymys löytyykö tehokasta algoritmia D joka kääntää algoritmin A eli D(A(s))=s.
Yleisesti oletetaan että on olemassa algoritmeja, jotka on hankala kääntää tehokkaasti. Ns. P=/=NP? on pieni, mutta tärkeä osa tätä ongelmaa.
Laskennan teoriassa on huomattu kuinka vaikea on muuttaa yksi ongelma toiseksi kuten tässäkin siis on kyse. Esim. Voidaanko lukujen tekijöihin jako ongelma, muuttaa diskreetin logaritmin ongelmaksi tai päin vastoin.
Tällaista vähän oletinkin. Mihin tulos perustuu? En saanut pienellä pohdinnalla esiin mitään syytä miksei kyseistä algoritmia voisi olla. Polynomiaikaisia palautusalgoritmeja kuitenkin on kehitetty erilaisten ongelmien välille hyvinkin paljon (esim. juuri palautukset luokkaan NP), eli ainakaan niin yleisellä tasolla ei voida puhua "yleisesti vaikeasta" ongelmasta.
Ei ole menetelmää, jolla voitaisiin ongelmia muuttaa toisikseen vaan ne ovat vähintäänkin haastavia. Nyt on kyse siitä, että sanoin oleellisesti eri algoritmit, eihän niillä välttämättä ole yhtään mitään matemaattista yhteyttä. Katsotaan vaikka diskreetti logaritmi ja tekijöihin jako.
Jos meillä on g^x=a mod P, missä g,a ja P (alkuluku) tunnetaan, pitäisi selvittää x. Jos meillä on tehokas algoritmi tekijöihin jakoon eli voitaisiin jakaa tekijöihin g ja a, niin auttaisiko se mitenkään x:n selvittämiseen?
Vai ovatko ongelmat toisistaan "riippumattomat"?
Joo, toki yleisellä tasolla ongelma on yleisesti ottaen vaikea :) Menin ajatuksissa vähän sekaisin.
Asia vain tuli mieleeni kun meillä on kaksi erilaista salasanojen kryptausta käyttävää autentikaatiota ja hashit on eri kannoissa. Jos nuo autentikaatiomoduulit joskus integroidaan, niin olisi näppärää jos toisen kannan hash-koodit voisi muuttaa toisen kannan kanssa samanlaiseksi.
" Jos meillä on g^x=a mod P, missä g,a ja P (alkuluku) tunnetaan, pitäisi selvittää x. Jos meillä on tehokas algoritmi tekijöihin jakoon eli voitaisiin jakaa tekijöihin g ja a, niin auttaisiko se mitenkään x:n selvittämiseen? "
Jos kyetään a jakamaan nopeasti tekijöihinsä, niin laskemalla g:n potensseja satunnaisesti modulo P väliltä [1,P-1]. Jos esim. luvulla (g^e modP) on yhteisiä tekijöitä luvun a kanssa, niin sehän on erinomaisen käyttökelpoinen probleeman ratkaisussa! Hakemalla vielä muutama vastaava potenssi voidaan muodostaa lineaariset yhtälöryhmät indeksin ratkaisemiseksi.
Valaiseva esimerkki:
2^x = 10 mod131
10= 2*5
2^8= 5^3 mod131
2^12= 5*7 mod131
2^14= 3^2 mod131
2^34= 3*5^2 mod131
sitten vain kirjoitetaan:
(2^8a)(2^12b)(2^14c)(2^34d) = (2^a)(3^(2d e))(5^(3b c 2e))(7^c)
ehdoilla (huomaa Eulerin lauseen kriteerit)
a=1 mod130
2d e=0 mod130
3b c 2e=1 mod130
c=0 mod130
Suotuisa ratkaisu: a=1, b=129, c=0, d=64, e=2
siis x= 8a 12b 14c 24d= 1997= 47 mod130
Tehtävä on muuttunut erittäin helposti ratkaistavaksi, mutta siis vain siinä tapauksessa JOS on käytössä überhyvä tekijöihinjako algoritmi...
Itse asiassa tämä visainen tehtävä on tiede.fi-foorumillakin, mutta sinne en ratkaisua postaa koska boikotoin ko. keskustelupalstaa.
http://www.tiede.fi/keskustelut/viewtopic.php?f=3&t=27770
Jos vain jokainen kryptausfunktio on injektiivinen, niin mikään ei estä ketjuttamasta:
A(s)->B->C->...->N(s)esim. AES. MUTTA! huomaa että näin syntyy vain yksi funktio, joka on käännettävissä.
Klassinen esimerkki on ketjuttaa Hillin kryptosysteemiä uusilla avainmatriiseilla, mutta näin syntynyt salaus ei poikkea vaativuudeltaa yhtään ensimmäisen kierroksen salauksesta.
Minkään NP-täydellisen probleeman luonti ei siis onnistu näin helposti, vaan vaatii kokonaan uutta innovaatiota matematiikan saralla. ;)