SRP: RSA-kryptering

Du kan sætte de pågældende udtryk for n og  φ(n) og vise at det giver andengradsligningen x2 -(p+q)x +p*q=0

Iøvrigt er det en mærkelig måde at skulle vise at så er koden brudt. Det kan gøres nemmere. Man skal blot finde d så e*d ≡1 mod φ(n).

Hej Peter, tak for svaret :)

Kan du lynhurtigt fortælle mig hvor andengradsligningen x2 -(p+q)x +p*q=0 kommer fra?

Mange hilsner.

Hvis en andengrads ligning x²+ax+c = 0 har  løsninger gælder der at summen af rødderne er koefficienten til x med modsat fortegn og produktet af rødderne er konstantleddet. Det kan vises ved at gange parenteserne i (x-r)(x-r2) ud

Så for lige at få det helt på det rene, så skal jeg gøre noget a la

x² - (p*q - ((p-1)(q-1) + 1)x + pq = x² -(p+q)x + p*q

Okay jeg har lavet nu vist, at p og q er løsninger til ligningen, dog ikke på ovenstående måde.

Jeg satte bare x = p og viste at venstresiden gav 0 når det var reduceret. Det samme gjorde jeg for q.

Men nu mangler jeg bare at finde ud af, hvordan dette kan bruges til at bryde RSA-systemet, hvis man kender φ(n).

Beklager at jeg bliver ved med at spørge, men er der nogen der kan hjælpe mig med ovenstående? :)

Opgavestilleren har vist klokket i det. Normalt siges det, at man kan bryde koden ved at finde de 2 primtal. Måden man bryder den på er ved at finde φ(n). Derefter kan man bruge Euklids udvidede algoritme til at finde d så e*d ≡ 1 mod φ(n). Det er faktisk den metode som dem, der konstruerer koden, bruger. Det man har brug for til at bryde koden er φ(n) ikke p og q men kendskab til p og q gør at man kan finde φ(n)