RSA kryptering (diskret matematik)

Algoritmen ger alltså:

72 = 14 * 5 + 2

5 = 2*2 + 1

Om du nu löser ut ettan från sista steget får du 1 = 5 - 2*2. Sen stegar du tillbaka ett steg i algoritmen, till första steget, där du kan lösa ut resten och få 2 = 72 - 14*5. Sätt in detta i uttrycket du har:

1 = 5 - 2(72 - 14*5)

Håll reda på att 72 och 5 var så att säga "ingångstalen" i hela beräkningen, vilket innebär att vi vill hålla kvar dem. Multiplicera alltså inte ihop 2*72 till 144, utan låt det stå kvar som 2*72. Förenkla på samma sätt det övriga så att det blir "nånting gånger 5". När parentesen tas bort får du 2*14, dvs. 28, stycken femmor, och med femman som är utanför blir det totalt 29 femmor:

1 = 5 - 2*72 + 2*14*5 = 5 -2*72 + 28*5 = -2*72 + 29*5

Skaft skrev:

Algoritmen ger alltså:

72 = 14 * 5 + 2

5 = 2*2 + 1

Om du nu löser ut ettan från sista steget får du 1 = 5 - 2*2. Sen stegar du tillbaka ett steg i algoritmen, till första steget, där du kan lösa ut resten och få 2 = 72 - 14*5. Sätt in detta i uttrycket du har:

1 = 5 - 2(72 - 14*5)

Håll reda på att 72 och 5 var så att säga "ingångstalen" i hela beräkningen, vilket innebär att vi vill hålla kvar dem. Multiplicera alltså inte ihop 2*72 till 144, utan låt det stå kvar som 2*72. Förenkla på samma sätt det övriga så att det blir "nånting gånger 5". När parentesen tas bort får du 2*14, dvs. 28, stycken femmor, och med femman som är utanför blir det totalt 29 femmor:

1 = 5 - 2*72 + 2*14*5 = 5 -2*72 + 28*5 = -2*72 + 29*5

okej då är jag med på hur de fick fram 29.

men hur ska man veta att man ska göra så då? eller jag menar är 29 det enda svaret på d eller finns det andra?

29 är den enda lösningen mellan 0 och 72, och det är den lösningen man letar efter. Men den generella lösningen till $5d \equiv_{72} 1$ är $x = 29 + 72n$.

Skaft skrev:

29 är den enda lösningen mellan 0 och 72, och det är den lösningen man letar efter. Men den generella lösningen till $5d \equiv_{72} 1$ är $x = 29 + 72n$.

okej men försökte göra det på ett till tal men fastnade igen för vet ej när jag ska sluta eller vilka tal jag ska lämna kvar

$7d \equiv 1 (mod 60)$

då gör jag samma sak:

60 = 8 * 7 + 4

7 = 4 * 1 + 3

4 = 3 * 1 + 1

ger

1 = 4 - 3 = 4 - (7 - 4) = 4 - (7 - (60 - 8 * 7) )

vad är det jag ska spara och förenkla här?

jag ska tydligen få fram d = 43 här

När du kommit till

1 = 4 - (7 - 4),

Utveckla parentesen och samla alla fyror "i en hög", så du kan byta ut alla på en gång:

1 = -7 + 2*4 = -7 + 2(60 - 8*7)

Skaft skrev:

När du kommit till

1 = 4 - (7 - 4),

Utveckla parentesen och samla alla fyror "i en hög", så du kan byta ut alla på en gång:

1 = -7 + 2*4 = -7 + 2(60 - 8*7)

yes jag har testat alla möjliga variationer men jag har svårt att förstå vad målet är så jag vet ej hur jag ska komma dit om jag inte vet det riktigt, vad är det jag gör efter det? jag kan göra allt möjligt men vet ej vart jag ska komma någonstans?

Du vill hitta ett tal d så att $ed \equiv_{72} 1$. Att ed är kongruent med 1 modulo 72, betyder att $ed + 72n = 1$ för något heltal n. Därför, om du kan bilda en ekvation på formen $1 = x\cdot e + 72\cdot y$ kan du läsa av d som koefficienten x.

Skaft skrev:

Du vill hitta ett tal d så att $ed \equiv_{72} 1$. Att ed är kongruent med 1 modulo 72, betyder att $ed + 72n = 1$ för något heltal n. Därför, om du kan bilda en ekvation på formen $1 = x\cdot e + 72\cdot y$ kan du läsa av d som koefficienten x.

okej men jag förstår fortfarande inte vad jag ska få ut av 1 = -7 + 2*4 = -7 + 2(60 - 8*7) men det vet ju du, hur ska jag veta det då. vilka siffror vill jag ha kvar och vilka siffror vill jag ha bort?

Ursäkta, när jag sa 72 i förra inlägget menade jag 60. Jag plockade visst tal från första uppgiften, det blev nog förvirrande.

Du vill ha kvar ingångsvärdena, som nu alltså är 60 (modulotalet) och e=7. Så du förenklar det till "nånting*60 + nånting*7".

Skaft skrev:

Ursäkta, när jag sa 72 i förra inlägget menade jag 60. Jag plockade visst tal från första uppgiften, det blev nog förvirrande.

Du vill ha kvar ingångsvärdena, som nu alltså är 60 (modulotalet) och e=7. Så du förenklar det till "nånting*60 + nånting*7".

okej så 1 = -7 + 2*4 = -7 + 2(60 - 8*7) = -7 + 2*60 - 2* 8 * 7 = -7 + 2*60 - 16 * 7 = 2*60 - 17 * 7 ?

Yes! Så nu kan du läsa av att 7:ans koefficient är -17. Men det ligger utanför intervallet 0 till 60. Vi lägger därför på en period och får -17 + 60 = 43.

Skaft skrev:

Yes! Så nu kan du läsa av att 7:ans koefficient är -17. Men det ligger utanför intervallet 0 till 60. Vi lägger därför på en period och får -17 + 60 = 43.

oj vilken magi! okej då är jag med, så man behåller alltid dom ingångna elementen sen använder koefficienten framför och ser till så den är inne i intervallet

tack!!!!