/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
RSA - hvilke algoritme dele er hurtigst?!
Fra : Kim Schulz


Dato : 14-06-02 20:59

hejsa
Sidder og leger med RSA algoritmen men kan ikke helt finde ud af hvilke
algoritme dele der er smartest at bruge til primtals generering, modolus
og exponentialisering.
Lige nu bruger jeg Miller-Rabin til primality test (primtal)og den
udvidede Eulers til Exponentialiseringen.
Men er det nu også de hurtigste hvis jeg vil kryptere et vilkårligt
stort antal tegn uden at sikkerheden bliver forringet?
Nogen der har check på den slags?

--
Kim Schulz - Freelance Development | "I go on working for the same
www.schulz.dk - En nørds bekendelser | reason a hen goes on laying
www.linuxia.dk - hverdagens små hacks | eggs." - H. L. Mencken

 
 
Thomas Jakobsen (17-06-2002)
Kommentar
Fra : Thomas Jakobsen


Dato : 17-06-02 09:06


"Kim Schulz" <kim@schulz.dk> wrote in message
news:20020614215852.769f021f.kim@schulz.dk...

> Lige nu bruger jeg Miller-Rabin til primality test (primtal)og den
> udvidede Eulers til Exponentialiseringen.
> Men er det nu også de hurtigste hvis jeg vil kryptere et vilkårligt
> stort antal tegn uden at sikkerheden bliver forringet?

Du kunne f.eks. overveje at benytte den kinesiske restsætning (CRT) så kører
det hurtigere. I stedet for at regne modulo n, så regnes både modulo p og
modulo q og resultatet samles til sidst. (Hvis det er til smartcard eller
lign. skal du dog passe på muligheden for timing angreb-ved brug af CRT.)

Du mener formentlig, at du benytter udvidet _Euklid_ til at _finde_
eksponenten og ikke til at udføre opløftningen? Prøv at checke Barrett's
modular reduction method.

Thomas



Bjarke Dahl Ebert (19-06-2002)
Kommentar
Fra : Bjarke Dahl Ebert


Dato : 19-06-02 17:53

"Thomas Jakobsen" <tj@ioi.dk> wrote in message
news:3d0d9862$0$78797$edfadb0f@dspool01.news.tele.dk...
>
> "Kim Schulz" <kim@schulz.dk> wrote in message
> news:20020614215852.769f021f.kim@schulz.dk...
>
> > Lige nu bruger jeg Miller-Rabin til primality test (primtal)og den
> > udvidede Eulers til Exponentialiseringen.
> > Men er det nu også de hurtigste hvis jeg vil kryptere et vilkårligt
> > stort antal tegn uden at sikkerheden bliver forringet?
>
> Du kunne f.eks. overveje at benytte den kinesiske restsætning (CRT) så
kører
> det hurtigere. I stedet for at regne modulo n, så regnes både modulo p og
> modulo q og resultatet samles til sidst. (Hvis det er til smartcard eller
> lign. skal du dog passe på muligheden for timing angreb-ved brug af CRT.)

Smartcardet foretager, som du nævner, to separate beregninger som kombineres
til sidst. Er det ikke en faktor 2 eller 4, eller sådan noget, man vinder i
tid?
Der er et interessant resultat der viser at hvis man kan få den ene af de to
beregninger til at fejle (men det må ikke være dem begge!), så kan man
udlede p og q af resultatet! Jeg kan ikke lige huske matematikken i det, men
konklusionen var at man ud fra en (nu forkert) signatur og offentlig nøgle
kan beregne p og q hurtigt. Og det er ligegyldigt hvad den forkerte
mellemregning giver, bare den er forkert.

Så kan man jo fx stå og skrue lidt op for 5V-indgangen til chippen, skyde
alfapartikler eller røntgenstråler mod den, putte den i sauna eller
mikrobølgeovn, eller hvad man nu vælger af onde ting . Hvis man skruer
langsomt nok op for disse ting, kan man være heldig at chippen til sidst
bliver lige præcis så utilpas, at netop den ene delberegning fejler. Og
vupti, så har man hevet nøglen ud af kortet.

Var det mon dét, som nogle gutter kom frem med for nyligt? Der var noget med
at nogen havde vristet RSA-nøglen ud af et smartcard ved at blitze på den
gennem et mikroskop (hvordan finder de på det... har de leget med myrer og
brændglas som små?

En nem og rimeligt god beskyttelse mod det angreb er at chippen kontrollerer
det beregnede resultatet. Det er stadigvæk hurtigere end ikke at bruge CRT.


Mvh. Bjarke Ebert,
Cryptomathic A/S (vi har lidt med den slags at gøre...
http://www.cryptomathic.com/





Kim Schulz (17-06-2002)
Kommentar
Fra : Kim Schulz


Dato : 17-06-02 22:33

[snip]
> Du kunne f.eks. overveje at benytte den kinesiske restsætning (CRT) så
> kører det hurtigere. I stedet for at regne modulo n, så regnes både
> modulo p og modulo q og resultatet samles til sidst. (Hvis det er til
> smartcard eller lign. skal du dog passe på muligheden for timing
> angreb-ved brug af CRT.)

Den overvejelse sag jeg også med idag, men indtil idag var CRT ukendt
land for mig


> Du mener formentlig, at du benytter udvidet _Euklid_ til at _finde_
> eksponenten og ikke til at udføre opløftningen? Prøv at checke
> Barrett's modular reduction method.

ja klart!

--
Kim Schulz - Freelance Development | Volley Theory: It is better
www.schulz.dk - En nørds bekendelser | to have lobbed and lost than
www.linuxia.dk - hverdagens små hacks | never to have lobbed at all.

Søg
Reklame
Statistik
Spørgsmål : 177560
Tips : 31968
Nyheder : 719565
Indlæg : 6408946
Brugere : 218888

Månedens bedste
Årets bedste
Sidste års bedste