Avatar billede catch22 Nybegynder
03. november 2005 - 20:50 Der 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;

cipher = message.modPow(e,n);//krypter beskeden "5"

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.
Avatar billede nielle Nybegynder
03. november 2005 - 20:56 #1
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.
Avatar billede catch22 Nybegynder
03. november 2005 - 21:04 #2
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.
Avatar billede erikjacobsen Ekspert
03. november 2005 - 23:02 #3
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.
Avatar billede erikjacobsen Ekspert
03. november 2005 - 23:06 #4
Et eksempel på stærkere primtal, man sommetider ser som eksempel

p = 107; q = 167; n = pq = 17869
phi(n) = (p-1)(q-1) = 17596
e = 43
d  7775

men også d=16573 kan bruges. Bedre bliver det ikke.
Avatar billede erikjacobsen Ekspert
03. november 2005 - 23:08 #5
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.
Avatar billede erikjacobsen Ekspert
03. november 2005 - 23:13 #6
Og for egentlig at svare på spørgsmålet: modpow i java regner det korrekt ud. Du kan kontrollere med programmet bc på din linux box.
Avatar billede catch22 Nybegynder
04. november 2005 - 00:42 #7
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 :)
Avatar billede catch22 Nybegynder
04. november 2005 - 00:44 #8
hov..glemte det skulle være et svar....
Avatar billede erikjacobsen Ekspert
04. november 2005 - 09:33 #9
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.
Avatar billede Ny bruger Nybegynder

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.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester