RSA med store eksponenter

Er der tilfældigvis nogen her som ved om der findes en effektiv algoritme til at beregne RSA med meget store eksponenter? Der er en feature jeg godt kunne tænke mig at tilføje til et lille hobbyprojekt. For at implementere den feature har jeg brug for at kunne beregne RSA med en eksponent på ca. 20GB. Modulus vil være af en ganske normal størelse på nogle få kbit.

I teorien er det nemt nok, jeg skal blot udføre en kvadrering og evt. en multiplikation for hver bit i eksponenten. Men i praksis tror jeg den fremgangsmåde vil blive lidt langsom når man har 20GB i sin eksponent.

Er her nogen som ved om der findes en hurtigere algoritme?

Du kan vist nok tage modulus af eksponenten inden du udfører beregningen. Det burde gøre square-and-multiply algoritmen hurtig nok.

Edit: Men jeg kan ikke se hvad det har med RSA at gøre, da begge eksponenter allerede burde være mindre end n (modulus) hvis de er fundet korrekt.

Emil Melgaard (2) skrev:

Du kan vist nok tage modulus af eksponenten inden du udfører beregningen. Det burde gøre square-and-multiply algoritmen hurtig nok.

Jeg glemte at nævne, at den part der skal udføre beregningen ikke må kende faktoriseringen af n, og derfor ikke kan reducere eksponenten.

Edit: Men jeg kan ikke se hvad det har med RSA at gøre, da begge eksponenter allerede burde være mindre end n (modulus) hvis de er fundet korrekt.

Du har ret i at det jeg har tænkt mig at gøre ikke er helt præcist RSA. Lad mig forklare i lidt flere detaljer, hvad det er jeg har tænkt mig.

Jeg har et system hvor en klient maskine laver backupkopier, som den placerer på en server. Klienten stoler ikke på serveren, så alle data bliver krypteret før de lægges på serveren.

Jeg ville gerne implementere en måde hvorpå klienten kan checke integriteten af det arkiv, der ligger på serveren. Det kunne gøres ved at downloade det hele og dekryptere det på klienten. Men den metode bruger for meget båndbredde.

I stedet har jeg så overvejet at klienten kan spørge serveren efter en checksum af arkivet. Men fordi krypteringen er probabilistisk, så kan klienten ikke selv beregne den samme checksum. Hvis klienten krypterer data igen, så vil resultatet ikke blive identisk med det, der ligger på serveren.

Klienten kunne selv gemme en kopi af samme krypterede data, som ligger på serveren. Men det synes jeg er spild af diskplads på klienten.

Men idé var så at i stedet husker klienten altid på indholdet af arkivet modulus (p-1)(q-1). Når indholdet opdateres kan klienten opdatere denne værdi uden at skulle kende resten af indholdet på serveren.

Når klienten vil checke integriteten så sender den n=pq og et tilfældigt tal r til serveren, og serveren vil så udregne r^data mod n og sende det tilbage til klienten. Hvis serveren kendte faktoriseringen kunne serveren snyde og unlade at gemme alle data og i stedet kun gemme værdien reduceret modulus (p-1)(q-1).

Hvor kræves det at du bruger symmetriske nøgler?

Det er sent og jeg burde ligge i min seng; men umiddelbart så vil jeg mene at din beskrivelse vil virke ligeså godt med en symmetrisk krypteret backup, hvor serveren selvfølgelig ikke får nøglen, samt (ramdom key'ed) hashes for at checke ændringer og at serveren vitterlig har gemt data. Eller er der noget jeg overser?

Prøv at kigge på Exponentiation by squaring.

Under Further applications står der noget du måske kan bruge, men uanset hvordan du gør vil det nok tage noget tid at regne på 2 GB data.

Edit til #4:
Hvor kræves det at du bruger asymmetriske nøgler?

Pally (4) skrev:

Hvor kræves det at du bruger symmetriske nøgler?

Det er sent og jeg burde ligge i min seng; men umiddelbart så vil jeg mene at din beskrivelse vil virke ligeså godt med en symmetrisk krypteret backup, hvor serveren selvfølgelig ikke får nøglen,

Krypteringen er allerede implementeret med en symmetrisk nøgle. Det jeg mangler er en måde at checke integriteten uden at overføre samtlige data.

samt (ramdom key'ed) hashes for at checke ændringer og at serveren vitterlig har gemt data. Eller er der noget jeg overser?

For at serveren kan udregne hash værdien er man nødt til at give den nøglen. Det virker fint til at checke data én gang. Men når jeg gerne vil have mulighed for at checke alle data flere gange, så nytter det ikke noget at bruge samme nøgle hver gang. For efter første check kender serveren nøglen. Og da man ikke selv opbevarer de krypterede data, så kan man ikke beregne hash under en ny nøgle.

kasperd (7) skrev:

Pally (4) skrev:

Hvor kræves det at du bruger symmetriske nøgler?

Og da man ikke selv opbevarer de krypterede data, så kan man ikke beregne hash under en ny nøgle.

Ah. Det giver bedre mening. Interessant problemstilling.