Matematik

RSA-kryptering

19. juni 2007 af Lektie boy (Slettet)

Hej folkens

Sagen er den at jeg snart skal til mundtlig eksamen i matematik 1-årig forløb til A-niveau. I mit pensum indgår RSA-kryptering, som jeg ikke rigtigt har styr på.
Så jeg ville høre om der var nogen der kunne fortælle om principperne i RSA-kryptering på en meget letforståelig måde? Samt evt. fortælle lidt om Public Key kryptering på en rigtig letforståelig måde?

De bøger jeg har, er ikke så gode til at forklare. Jeg synes det er meget svært at forstå. Jeg ville blive rigtig glad hvis der var nogen der kunne hjælpe mig med dette.

På forhånd 1000 tak

Brugbart svar (0)

Svar #1
19. juni 2007 af peter lind

Det er altså et ret kompliceret emne, som kun kan berøres meget overfladisk på en portal som denne.

Kort fortalt:

Man kan vise at der gælder a^[k*(p-1)*(q-1) ] mod n = a. Her er p og q to forskellige primtal, k er et vilkårligt naturligt tal og n = p*q

Kan man finde e og d så e*d = k*(p-1)*(q-1) har man

a^(e*d) mod n = a.

Hvis du har et tal x du skal kode bliver koden y = x^e mod n. Her kan du ikke bare ud fra y regne tilbage og finde x. Man kan få x tilbage nemlig af y^d mod n = (x^e)^d mod n = x, men det forudsætter at man kender d.

Alle offentlig kryperings metoder er baseret på at det er svært at regne tilbage undtagen hvis man har specielle oplysninger som i ovennævnte tilfælde er d.

Langt de fleste er også baseret på regninger med restklasser.

Jeg er stødt på en enkelt der er baseret på polynomier af meget høj grad.

Svar #2
19. juni 2007 af Lektie boy (Slettet)

Er det muligt at du kan forklare det med modulo på en lidt nemmere måd. Fordi det er netop det at jeg ikke helt forstår.

Hvis jeg evt. trækker dette emne til eksamen, hvor store tror du så kravene vil være til mig? Vi har haft et projekt/forløb i kryptologi og har kun lidt berørt dette punkt.

Brugbart svar (0)

Svar #3
19. juni 2007 af peter lind

Desværre overstiger det min evner at give en ordentlig redegørelser på så lille en plads. Mundtlig vil en overfladisk indførelse af restklasser tage mindst 2 timer. Dertil kommer så inførelsen af RSA i større detaljer. Hvis din bog ikke er uddybende nok kan du prøve at søge på internettet.

Hvis du er gået i stå et specifikt sted er det noget andet. Der kan jeg måske hjælpe, hvis du kan angive problemet præcist.

Svar #4
19. juni 2007 af Lektie boy (Slettet)

Jeg er mest gået i stå omkring beregning af kongruenser. Fx a = b mod n.... hvor lighedstegnet selvfølgelig er modulus tegnet eller hvad det kaldes. Jeg har meget svært ved at forstå beregninger af denne type.
Jeg har søgt på internettet og fundet ud af, at hvis forskellen mellem to tal (a og b) er deleligt med et andet tal m, kan man finde n således:
n = (a-b)/m

Dvs. a = nm + b

så tror jeg b er en slags rest. men så er det så rest-begrebet jeg heller ikke helt forstår. Altså n = qm+ r. Er det muligt du kan fortælle lidt om disse to:
n = qm+ r
a = b mod n

Og hvordan man særligt regner med modulo

Brugbart svar (0)

Svar #5
20. juni 2007 af peter lind

Det du kalder modulus tegnet skal læses "ævivalent med". Jeg har set andre på portalen skrive dette tegn som et dobbelt lighedstegn altså == og det vil jeg også gøre:
Ellers har du helt ret i at det har noget med resten ved division at gøre.

Den første ligning drejer sig om heltalsdivision.

hvis n= 12 og m=6 har man q=n/6 =2.6 går op i 12 og så er resten r=0. Sat ind ovenfor med q=2 står der 12 = 2*6+0.

Hvis du i stedet sætter n=14 får du får du q = heltal(14/6) = 2. Kvotienten er stadig 2; men nu er resten ikke 0 længere. Den er 2. Sat ind får man:

14 = 2*6 + 2

Relation a==b mod n betyder at a og b har samme rest ved division med n.

Hvis du sætter a = 14, b=20, n=6 vil resten ved division af a med n være 2. Hvis du dividerer b med n får d q=3 og resten 2. a og b har altså samme rest ved division med n og man kan derfor skrive

12==20 mod 6

Håber det hjælper.

Svar #6
20. juni 2007 af Lektie boy (Slettet)

Jo, tak. Nu giver det klart mere mening for mig. Meget flot forklaring du kom med dér, vil jeg lige sige :)

Men til sidst, hvor du skriver: 12 == 20 mod 6

Mener du så ikke: 14 == 20 mod 6

Fordi som jeg ser det, går 6 op i 12 og giver dermed en rest 0, mens 6 går 3 gange op i 20 med en rest på 2. Dermed er de to rester forskellig fra hinanden. Det er vel sådan det skal forstås?

Brugbart svar (0)

Svar #7
20. juni 2007 af peter lind

Du har ret.Undskyld

Svar #8
20. juni 2007 af Lektie boy (Slettet)

Nej nej, du skal da ikke undskylde. Kom bare lidt i tvivl. Din forklaring med eksemplerne har virkelig hjulpet mig meget ang. forståelsen :) tusind tak skal du have

Skriv et svar til: RSA-kryptering

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.