RSA kryptering

Kan du forklare hvorfor det ikke går godt?

Jeg har først givet alle bogstaverne tal efter deres plads i alfabetet altså C = 03 osv. Derefter opløfter jeg det i 17 og dividere med 77, sådan har jeg i hvert fald forstået jeg skulle gøre..

Resultatet jeg ender ud med er 1677144,974 og det resultat ved jeg ikke hvad jeg skal gøre ved? 

Det går galt for dig, da k og tallet (p-1)·(q-1) skal være indbyrdes primiske.
Hvis du vælger k=60 og (7-1)(11-1)=60 vil det betyde, at de ikke er indbyrdes primiske.
Du bliver nødt til at vælge en anden værdi for k (fx 29), - jeg har checket 60 og 29 er indbyrdes primiske,
da gcd(60,13) = 1 (gcd "greatest common divisor", altså største fælles divisor (sfd))

primtallene:   p = 7 og q = 11 bruges til at beregne: N = p·q = 77

derudover vælges endnu et tal k, - i dette tilfælde k = 13

bemærk, at k og tallet (p-1)·(q-1) skal være indbyrdes primiske...... checket :-)

kryptering af Christina, hvor a=1, b=2, c=3 osv.....

KRYPTERINGSALGORITME

C = M^k (mod N)    

C er kodeteksten (ciphertext)
M er klarteksten (messagetext)

kryptering af klartekstbogstavet C (talværdi 03)

C(iphertext) = M^k (mod N)

C_C = 3²⁹ (mod 77) = 26

mod(ulo) beregner resten ved heltalsdivision, - fx 7 = 1 (mod 3) da 7:3 = 2 rest 1 

Når man skal regne den anden vej (dekryptere), hedder algoritmen:

M = C^d (mod N)
M = 26²⁹ (mod 77)
M = 3

som er lig med C (03) på samme måde kan de øvrige bogstaver i CHRISTINA krypteres og dekrypteres)

hvor d beregnes som (en lidt langhåret beregning): 

k·d = 1 (mod (p-1)(q-1))
29·d = 1 (mod 6·10)
29·d = 1 (mod 60)

d = 29 

(d bestemmes med Euklids algoritme)

 glemte at sige, at det ikke er nemt at bestemme værdien for d
du skal bruge Euklids algoritme.

har lavet et regneark til EXCEL, der kan klare det...

Indtast k og tallet (p-1)(q-1) i de to gule felter, så klarer arket resten...
(test om de er indbyrdes primiske og beregning af d, hvis der er én)
 

 Du har lavet en fejl. Måske kan du selv finde den..

Nu har vi jo godt nok bevæget os ind i verdenen af hemmeligholdelse, - er det derfor, du ikke bare fortæller, hvor du mener, jeg har lavet en fejl ? :-)

Kan det være den her:

i #3 skrev jeg

"....Du bliver nødt til at vælge en anden værdi for k (fx 29), - jeg har checket 60 og 29 er indbyrdes primiske, da gcd(60,13) = 1 (gcd "greatest common divisor", altså største fælles divisor (sfd))....."

der skal stå gcd(60,29)  det er udelukkende en tastefejl, beregningerne "holder"

 Tak for hjælpen, jeg tænkte på om det betyder noget at den offentlige nøgle (k,m) =(17,77)?

du mener vist (k,N) altså (17, 77)

N er produktet af de to (meget) hemmelige primtal p og q, - i dit oprindelige indlæg havde du valgt 7 og 11

k er et selvvalgt (prim)tal

Tilsammen er det den offentlige nøgle, der bruges til at kryptere den klartekst, man gerne vil sende til nøglens ejer.

C = M^k (mod N)      (hvor C er kodeteksten og M er klarteksten)

Med hensyn til dit spørgsmål i #8

hvordan er du kommet frem til N = 77 ?

N er jo beregnet ud fra dine to valge primtal p og q:    N = p·q

 77 er kommet frem til ved at bruge mine primtal p*q = 7*11=77

 Men så må N være 60?

Ved du, hvad der er værre end at lave fejl? - At man ikke kan finde dem.

Ved du hvad der er endnu værre? - At man benægter det.  

 #12 jeg har altså opdaget fejlen, det vil jeg da gerne indrømme, - det der fik mig op i "det røde felt", var den lidt for oversmarte selvfede måde, hvorpå du hoverede i aftes i stedet for at bidrage positivt til indlægget, - det handler jo ikke om overherredømmet mellem nørderne i forhold til at vide mest, men tværtimod om at hjælpe dem, der bruger tid på at oprette indlæg på dette forum i forventning om, at de får de rigtige svar, ikke sandt ?

skulle vi så ikke i fællesskab prøve at hjælpe 3082 til det rigtige svar ?

Peter Valberg

 #11 som du sikkert kan se af den parallelle diskussion her i dit indlæg, så har jeg regnet lidt forkert,- hvilket jeg har opdaget og er ved at rette op på... 

Det var ment lidt sjovt Peter. No hard feelings.

Dit citat af Sokrates.. Er det korrekt eller misbrug af ham ? 

 #15 okay H2OH2O godt ord igen, - fedt citat forøvrigt, som du sikkert hurtigt kan udlede, så kendte jeg det ikke:-) 

 #16 Jamen Sokrates sagde: "Jeg ved, at jeg ved, at jeg intet ved." - På din profil står der noget helt anderledes .. 

 Er du forvirret ? :-)

 #18 ja, det må være derfor :-)

Til 3082

Nu skulle der endelig være styr på krypteringen :-)

Der vælges to primtal p = 7 og q = 11 (som skal holdes hemmelige)

N beregnes som N = p·q = 77

Derudover vælges et tal k, i dette tilfælde k = 29
k og tallet (p-1)(q-1) = 60 skal være indbyrdes primiske:  gcd(77,60) = 1 OKAY

N og k er den offentlige nøgle.

Til dekryptering skal du bruge et hemmeligt tal d som bestemmes således:

k·d = 1 (mod (p-1)(q-1))

Dette bestemmes lettest med Euklids algoritme
det EXCEL ark som jeg uploader med dette svar kan klare det
det er en forbedrede version af den første :-)

Kryptering af fx B=02

C = M^k (mod N) = 2²⁹ (mod 77) = 39

Dekryptering af 39

M = C^d (mod N) = 39²⁹ (mod 77) = 2  

Så skulle det vist være i orden, hvad siger du H2OH2O ?

 Tusind tak Peter:), men den offentlige nøgle jeg har fået opgivet stå der (k,m)=(17,77) skal jeg ikke anvende 17 til noget?