Kehittelin joutessani oikein rutiköyhän miehen kryptausalgoritmia ja siinä sivussa törmäilin tällaiseen ongelmaan, onko olemassa valmista ratkaisukaavaa.
On kolme tuntematonta kokonaislukua, joiden summa ja tulo tunnetaan. Pitäisi löytää nämä luvut. Löysin yhden jokseenkin kankean tavan, joka toimii kun yksi luvuista on alkuluku. Löytyykö ratkaisua, jos kaikki luvut ovat jaollisia? Entä neljälle luvulle?
On kolme tuntematonta kokonaislukua, joiden summa ja tulo tunnetaan. Pitäisi löytää nämä luvut. Löysin yhden jokseenkin kankean tavan, joka toimii kun yksi luvuista on alkuluku. Löytyykö ratkaisua, jos kaikki luvut ovat jaollisia? Entä neljälle luvulle?
Vastaukset 7
Vanhimmat
Ei vastauksia. Eikä tarvikkaan vastata. Pahoitteluni että heitin tänne keskeneräisen pähkinän. Ensinnäkään tekijöihin jakaminen ei olekaan ihan triviaali juttu. Jos alkulukutekijä on suurin kysytyistä luvuista, ehkä sitten saa yksikäsitteisen tuloksen, muuten tulee vaihtoehtoisia ratkaisuja. Vai lähestynkö ongelmaa ihan väärin päin. Ei se mitään. Pähkäily on joka tapauksessa hauskempaa kuin sudokujen ratkonta.
Neuvosta huolimatta yritin tähän jonkinlaisen metodin keksiä. Sulla varmaan samanlainen olikin, ja lähtee toisen asteen yhtälöstä:
http://aijaa.com/Sf1q1f
Jollain pienillä luvuilla ratkaisut ehkä löytyy, jos tuon Diskriminantin rajoitukset osaa laskea...
Aivan justiinsa samanlainen. Jos sen yhden luvun saa esiin alkutekijöihin jakamalla niin päädytään yhtälöparin kautta toisen asteen yhtälöön, jonka juuret ovat haetut luvut. Jos tosiaan on useita lukuehdokkaita niin ne on testattava.
Voi tällä ainakin periaatteessa pakata kolme lukua kahdeksi. Ei taatusti maailman tehokkain konsti ole kuiteskaan.
Ja vielä voi vaikka piirtää kuvan. Saadaan ylöspäin aukeava paraabeli, joka leikkaa x-akselin lukujen kohdalla. Ja derivaatan nollakohta / lukujen keskiarvo on paraabelin huipun x-arvo. Voisikohan tästä jatkokehitellä jotain ... :)
Vinkkinä vielä että RSA-algoritmi on mielenkiintoinen oikea kryptaussysteemi. Haulla löytyy kuvauksia. Perusjuttu ei ole edes mahdottoman laaja ja "kryptinen" ja sitä voi kokeilla pienilläkin alkuluvuilla.
RSA-algoritmi on vaikeaselkoinen !
JOS kuvauksen lukee tarkkaan, siellä on kohtia : "valitaan luku siten, että..."
Eli ei riitä vain kahden suuren alkuluvun kertominen keskenään, vaan siellä on muita lisäkriteerejä.
Se, miten nuo lisäkriteerit tulevat täytetyiksi, se jätetään yleensä selittämättä.
Onko kukaan löytänyt oikeasti hyvää ja täydellistä kuvausta RSA -algoritmin salausavainten luonnista?
esim. wikipedia:
https://fi.wikipedia.org/wiki/RSA
1. Valitse kaksi suurta alkulukua p ≠ q satunnaisesti ja toisistaan riippumatta. Laske N = p q.
2. Valitse kokonaisluku 1 < e < N jolle (p-1)(q-1) on suhteellinen alkuluku.
3. Valitse d siten, että d e ≡ 1 (mod (p-1)(q-1)).
4. Tuhoa kaikki p:tä ja q:ta koskevat tiedot.
---
Kohdat 1 ja 4 ovat selkeitä, mutta se, MITEN toteutetaan kohdat 2 ja 3, jätetään selittämättä.
Onko jokin keino laskea d ja e ?
2. Sattumanvaraisesti valitaan joku ja kokeillaan onko syt(e, (p-1)(q-1)) = 1. Jos ei valitaan uudestaan. Tämä on järkevää, sillä niitä suhteellisia alkulukuja on kuitenkin suhteellisen paljon (ks. esim. https://en.wikipedia.org/wiki/Euler's_totient_function#Growth_rate)
3. Tämä d on e:n käänteisalkio ryhmässä Z*_{(p-1)(q-1)}. Sen voi määrätä Eukleideen algoritmilla määrittämällä syt(e, (p-1)(q-1)) (joka siis on 1) ja kertoimet d ja b (Bezout'n yhtälössä)
de b(p-1)(q-1) = 1.
Tässä siis saadaan d e:n kertoimena. (Ratkaisu on modulo(p-1)(q-1), sillä termistä de voi "erottaa" toiseen termiin osan e(p-1)(q-1), jos d>=(p-1)(q-1), ks. lineaarinen Diofantoksen yhtälö. Siis voidaan valita d väliltä [1, (p-1)(q-1)].)
On olemassa laajennettu Eukleideen algoritmi, jossa saa nuo kertoimet (s_i, t_i) saa samalla kun syttiä määrittää, ks. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Englanninkielisessä artikkelissa (https://en.wikipedia.org/wiki/RSA_(cryptosystem)) on tuo paremmin sanottu. Mm. että e valitaan 1
Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
Determine d as d ≡ e^{−1} (mod φ(n)); i.e., d is the modular multiplicative inverse of e (modulo φ(n))
This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))
e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 216 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.[13]
e is released as the public key exponent.
d is kept as the private key exponent.