03. november 2005 - 20:50Der er
8 kommentarer og 1 løsning
BigInteger.modPow underligt resultat
Jeg er ved at lege lidt med noget primitivt RSA kryptering. Jeg benytter RSA til at kryptere et lille tal med den offentlige nøgle og kører så brute force for at finde den private nøgle. For at se et resultat i min levetid, benytter jeg meget små tal. Min kode er som følger:
BigInteger message = new BigInteger("5");//besked BigInteger e = new BigInteger("17");//offentlig nøgle BigInteger d = new BigInteger("0");//privat nøgle, værdi er 2753 BigInteger n = new BigInteger("3233");//modolus BigInteger cipher;
for(int i=0; i<3000; i++){//forsøg fra 0 til 3000 /*Forsøg at dekryptere cipher*/ BigInteger mess=cipher.modPow(new BigInteger(String.valueOf(i)),n);
/*stemmer dekryptered besked overens med oprindelig besked?*/ if(message.equals(mess)){ System.out.println("d is: "+i + " message was "+mess); } }
Som resultat får jeg følgende nøgler:
413 1193 1973 2753
Hvilket ikke stemmer overens med at der så vidt jeg ved (correct me, if im wrong!) kun findes én unik inverse (privat nøgle) til ens offentlige nøgle. Det mærkelige er at hvis jeg kører samme regnestykke med nøglen 413 på min KCalc (lommeregner til KDE) så får jeg resultatet 424 (ifølge java giver det 5), og regnet på Windows lommeregner giver det også 5. Jeg har dog svært ved at tro på at der skulle være 4 nøgler mellem 0 og 3000 der kan bruges til at dekryptere mod én offentlig nøgle. Desuden passer eks. 413 ikke ind i de matematisk krav for at finde den private nøgle, så det kan simpelthen ikke passe, så hvad er fejlen ? Er det BigInteger's modpow der regner forkert ? Er RSA ikke så sikker som jeg tror ? Eller har jeg lavet en dum fejl ? Jeg tror mest på det sidste, men jeg kan ikke se fejlen, og metoden finder også den korrekte nøgle 2753 til sidst.
Det kan jo godt være at der er flere mulige privat-nøgler, som dekoder en given tekst. Men der burde kun være een privat-nøgle, som dekoder alle beskeder som er kodet med en given offenlig-nøjle.
Har lige prøvet at cryptere 45, 666, 66, 2560 og 3000....der kommer ganske rigtig mange forskellige nøgler ud over den korrekte, men det skræmmende er at de 4 nøgler fra eksemplet går igen på alle sammen foruden en variende ekstra mængde.
Der kan sagtens være flere dekrypteringsnøgler. Især hvis du har svage primtal. Hvis phi(n), som her er (p-1)(q-1) er det samme som lcm(p-1,q-1) (lcm er least common multiplum), vil der kun være 2. Det er ikke et sikkerhedsproblem.
I dit tilfælde er lcm(p-1,q-1)=780, som netop er forskellen mellem dine nøgler. De to valgte primtal er ikke (super)stærke. Men de bliver tit brugt som eksempel alligevel ;)
Men 4 dekrypteringsnøgler er nu heller ikke et sikkerhedsproblem, generelt.
Hovsa, mener: hvis (p-1)(q-1) er det samme som 2*lcm(p-1,q-1)
Da p og q er ulige, vil der altid være en faktor 2 til fælles i p-1 og q-1. Så bedre kan det ikke blive. Så vil d+lcm(p-1,q-1) mod n også kunne bruges.
jo jo...så blev jeg lidt klogere idag...det kunne heller ikke gå modsat.
Jeg siger tak for svaret, erik. Jeg hører, at du ikke samler point, så jeg beholder dem bare, hvis du ikke har nogen indvendinger. Du har ellers gjort dig fortjent til dem :)
Helt i orden. Jeg ville egentlig have givet dig et link til en diskussion om dette, men det er tilsyneladende svært at finde. For det er ikke noget jeg har fundet på - jeg har bare læst det en gang.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.