Matematik
RSA-kryptering - Hjælp til at finde de hele tal, u og v, når k og ø(m) er indbyrdes primiske?
Hej folkens
Jeg er ved at skrive SRP om RSA-kryptering.
Jeg sidder med noget teori der lyder:
Hvis a og b er indbyrdes primiske, eksisterer der hele tal u og v, så:
a*u+b*v=1
Da k og -ø(m) er indbyrdes primiske, eksisterer der altså hele tal u og v, så:
k*u-ø(m)*v=1
Det jeg så ikke helt forstår, er hvordan det minus der, ligepludselig kommer ind?
Jeg skal vælge to primtal, p og q, og gange dem sammen så jeg finder m. Fx m=331*149=49319
Herefter finder jeg ø(m) ved formlen: ø(m)=ø(49319)=(331-1)*(149-1)=48840.
Herefter vælger jeg et kal, k, som er indbyrdes primisk med ø(m), fx k=7.
Og så er det jeg vil finde de hele tal u og v. Og jeg tror egentlig godt jeg forstår metoden. Men jeg forstår ikke hvorfor der er det minus i formlen. Nogen der kan hjælpe? :)
Svar #1
30. november 2014 af peter lind
Der er ikke noget mystisk ved det. Hvis du ser på formele a*u+b:v = 1, a og b >> 1 må en af tallene u eller v være negativ. Du kan ikke på forhånd vælge hvilken af de tal som er negativ. Hvis den du skal bruge er negativ, adderer du blot den restklasse du regner med til tallet
Svar #2
01. december 2014 af Myariea (Slettet)
Ej det giver jo god mening så, når a og b er >1.
Resten er jeg dog ikke helt med på? Begge mine tal er jo positive? :-)
Hvordan ved jeg så hvilket af tallene jeg skal sætte minus foran?
Svar #3
01. december 2014 af peter lind
Bestemmelsen af u og b sker normalt ved at bruge euklids udvidede algoritme. Den giver u og v med fortegn. Hvis du får begge positive må du have gjort noget andet. Desuden holder u*a+v*b = 1 så ikke. Du skal bruge den del der svarer til dit valg af k. I dit eksempel k=7 Hvis a= 7 er det så u, du skal bruge
Svar #4
01. december 2014 af Myariea (Slettet)
yes. Tror det hele er ved at hænge sammen nu!
Tak for hjælpen :-)
Skriv et svar til: RSA-kryptering - Hjælp til at finde de hele tal, u og v, når k og ø(m) er indbyrdes primiske?
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.