kryptering ?

Det var et dejligt naivt spørgsmål! Dit spørgsmål fylder 2 linjer, og et uddybende svar vil fylde mange sider, hvis det skal have bare lidt substans. Alligevel vil jeg besvare det med det kortest mulige eksempel:

Alt foregår med de hele tal! Vi har primtallene p=5 og q=7, som giver produktet n=35. Til disse knyttes tallet φ(n)=4·6=24. Nu finder vi et tal e, der skal være indbyrdes primisk med φ(n) - dvs. de må ikke have fælles divisorer på nær tallet 1. Lad os vælge e=11. Så skal vi finde et tal d, således at ed=k·φ(n)+1 for et eller andet tal k. Det viser sig, at 11·11=121=5·24+1, så vi sætter også d=11.

Vi kan nu kryptere og dekryptere alle tal fra 1-35 vha. tallene n=35 og e=d=11. Lad os se, hvordan dette foregår. Vi tager f.eks. tallet 17 og vil nu forsøge at kryptere det. Først udregnes 17¹¹'s rest efter division med 35. Det lyder svært, men det er ikke så slemt, hvis man bruger gentagen kvadrering:

17² = 289 = 8·35+9 giver rest 9. Vi skriver kort [17²] = [9]

9² = 81 = 2·35+11 giver altså rest 11. Dvs. [17⁴] = [9²] = [11]

11² = 121 = 3·35+16, så [17⁸] = [11²] = [16]

og selvfølgelig er [17]=[17].

Nu skal vi udregne [17¹¹], dvs. 17¹¹'s rest efter division med 35. Da 17¹¹=17¹·17²·17⁸, kan vi vha. ovenstående skrive, at [17¹¹] = [17][17²][17⁸] = [17][9][16]. Lad os først udregne 17·9 = 143 = 4·35+3, så [17][9] = [3] og 3·16 = 48 = 35+13, så [17¹¹] = [13].

Sikke en masse dejlige udregninger!!! Nu har vi krypteret et tal, nemlig 17, af tallene mellem 1 og 35 til et andet tal, nemlig 13, så 17 krypteret med det givne system giver 13. Formelt set har vi udregnet 17^e's rest efter division med n.

Dekrypteringen foregår ved at udregne 17^ed's rest efter division med n. Dette svarer til at udregne [17^e]^d = [13]^d, så vi skal have udregnet 13^d's rest efter division med n=35 for at genskabe det oprindelige tal. Dette foregår på en lignende facon:

13² = 169 = 4·140+29, så [13²] = [29] eller man kan skrive [29] = [-6] da 29+6=35.

(-6)² = 36 = 35+1, så [13⁴] = [1]

1² = 1, så [13⁸] = 1

Derfor er [13¹¹] = [13][-6][1], og da 13·(-6) = -78 = -2·35-8, får vi [-8], som svarer til [17], da 17+8=35. Altså har vi genskabt tallet 17 igen.

Da denne metode fungerer med alle tal fra 1 til 35, så kan den også anvendes til at kryptere de 28 bogstaver i alfabetet efter tur, men der er flere årsager til, at mit eksempel kun er et pædagogisk (hvis det da er det) eksempel. Bl.a. er det meget let at bryde krypteringen, når tallet n er så let at faktorisere. Tallet 35 er simpelthen for lille - så lille at stort set alle ved, at det er 5·7. Derfor kan alle, der kender n=35 og e=11 forholdsvist let finde frem til at φ(n)=24 og derfra, at d=11, så de kender dekrypteringsnøglen, nemlig d. Desuden kan man ligeså godt samle datamængden i større klumper, så man f.eks. kan kryptere hele ordet "kryptogram" af én omgang og ikke med hvert bogstav enkeltvis. Ordet kan oversættes med tabellen:

a = 01

b = 02

c = 03

etc.

Til talkoden 11182416201507180113 idet k=11, r=18 etc. Dette er et forholdsvist stort tal, og n skal være endnu større end - eller mindst ligeså stort som - dette tal, for at metoden virker. Og denne talkode skal så opløftes i nogle forholdvist meget større potenser end e=d=11 som ovenfor!!!

Men ellers et meget hyggeligt lille "overskueligt" spørgsmål. Jeg formoder ikke, at ovenstående eksempel giver ret meget mening, hvis man ikke kender en smule til regning med restklasser i forvejen, og forklaringen på, hvorfor det virker, er slet ikke forsøgt gengivet!!!

Hej igen

Tusind tak for hjælpen :)

Du krypterede med primtallene p=4 og q=7. Nu har jeg så prøvet at siddet og regne på det med mine egne primtal, som jeg skal bruge. Altså p= 11 og q=19, men når jeg når lidt længere ind i regnestykket, kan jeg ikke rigtig få det til at passe.

Så ville høre om du evt kunne hjælpe mig igen ?

Det kan jeg garanteret. Har du fundet n, φ(n), e og d, eller skal du have hjælp til denne del? Hvis du har, så skriv dem herinde.

Jeg har fundet ud af dette.

p= 11 og q= 19   pq = 209
φ(n) = (p – 1)(q – 1) = (11 – 1)(19 – 1) = 180
Jeg vælger e = 7, da det opfylder 0 < e < φ(n) og (e, φ(n)) = 1

Men jeg har ikke fundet d. vil jeg meget gerne have hjælp til?
 
 

For at bestemme d, kan du anvende en metode kaldet Euklids udvidede algoritme. Vi har tallene a=180 og b=7 med (a,b)=1 og ønsker at bestemme λ og μ således at λ·a+μ·b=1 (Bezouts identitet kaldes denne ligning). Lad os bruge notationen (x,y) for tallet x·a+y·b, således at (1,0)=180 og (0,1)=7.

Nu udfører vi Euklids algoritme, som dybest set handler om division med rest:

180-25·7=5=(1,0)-25·(0,1)=(1,-25)

7-5=2=(0,1)-(1,-25)=(-1,26)

5-2·2=1=(1,-25)-2(-1,26)=(3,-77)

Så vi har, at 1=(3,-77), hvilket betyder at 3·180-77·7=1. Bemærk, at (-7,180)=0, så:

1=(3,-77)+(-7,180)=(-4,103)

og dermed -4·180+103·7=1, hvilket giver, at 103·7=4·180+1. Vi har dermed bestemt d til at være d=103. Det er et højt tal :) Det skal nok blive morsomt, når beskeden skal dekrypteres...

Okay, tak.. det hjalp godt nok lidt på forståelsen.. nu skal der så krypteres og dekrypteres alle tal fra 1 - 103, ikke. så vidt jeg har forstået ? :)

Ved godt jeg spørger meget. Men det er en meget vigtig opgave, som skal i min SRP opgave(som skal aflevers på torsdag :S ) så vil meget gerne have det rigtitgt. og er meget usikker på udregningerne.  

N=pq=209, så du kan kryptere tallene fra 1 til 209 - eller egentlig fra 0 til 208, da restklassen [209]₂₀₉ plejer at blive identificeret som [0]₂₀₉. For at enkryptere skal du opløfte beskeden [x], hvor 0≤x≤208 i 7. potens, fordi e=7. Lad os kalde resultatet/den krypterede meddelelse for [y]. For at dekryptere skal du opløfte restklassen [y] i 103. potens fordi d=103. Så får du [x] igen.

Disse to potensopløftninger af restklasser definerer faktisk en bijektion fra tallene 0-208 til sig selv. Sagt på dansk, sender potensopløfningen med e=7 tallene fra 0 til 208 over i en anden rækkefølge af tal fra 0 til 208, mens potensopløftningen med d=103 sender denne rækkefølgeændring tilbage igen. Bemærk at restklassen [1] ikke rigtig kan krypteres, da [1]^e=[1] og derpå [1]^d=[1], så ganske vidst kan meddelelsen genskabes, men den har aldrig været rigtig krypteret.

nu har jeg enkrypteret Kryptogram til

k:  11     11
r:   18     94
y:   24     73
p:  16     36
t:   20     191
o: 15      203
g:  7       83
r:  18      94
a:  1       1
m: 13     29
 

men dekrypteringen. hvordan vil du gøre det? det syns jeg godt nok er svært, da 103 er så stort

så skal man sige 11^103/209, men det bliver et ret vildt tal

Det er her gentagen kvadrering kommer ind i billedet! Du kan skrive 103=1100111_II forstået som tallet 1100111 i totalssystemet. Det betyder altså 103=1·2⁶+1·2⁵+0·2⁴+0·2³+1·2²+1·2¹+1·2⁰, eller 103=64+32+4+2+1. Med eksemplet x=18 og dermed y=94 kan du så skrive 94¹⁰³=94⁶⁴·94³²·94⁴·94²·94¹. Dermed kan du udregne følgen af restklasser, hvor du hele tiden tager dit resultat og opløfter i 2. potens igen:

[94]² = [58]

[94]⁴ = [58]² = [20]

[94]⁸ = [20]² = [191]

[94]¹⁶ = [191]² = [115]

[94]³² = [115]² = [58]

[94]⁶⁴ = [20] (se tidligere udregning)

Derfor er [94]¹⁰³ = [94]⁶⁴[94]³²[94]⁴[94]²[94]¹ = [20][58][191][20][58] = [18]

Og så er [x]=[18] genskabt!

okay

Hvis jeg skal gøre det med tallet 11, så siger jeg

[11]² = [121]

[11]⁴ = [11] kan det passe?

Ja, det ser rigtigt ud!

[1]² = [1]

af en eller anden grund kan jeg ikke få de andre til at passe