Sólin Sólin Rís 09:06 • sest 17:16 í Reykjavík
Tunglið Tunglið Rís 06:24 • Sest 16:46 í Reykjavík
Flóð Flóð Árdegis: 05:17 • Síðdegis: 17:24 í Reykjavík
Fjaran Fjara Árdegis: 11:24 • Síðdegis: 23:36 í Reykjavík
Sólin Sólin Rís 09:06 • sest 17:16 í Reykjavík
Tunglið Tunglið Rís 06:24 • Sest 16:46 í Reykjavík
Flóð Flóð Árdegis: 05:17 • Síðdegis: 17:24 í Reykjavík
Fjaran Fjara Árdegis: 11:24 • Síðdegis: 23:36 í Reykjavík
LeiðbeiningarTil baka

Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=
Forsíða Náttúruvísindi og verkfræði Tölvunarfræði Hvaða gagn er að prímtölum?

Flokkun:

9.10.2020
Náttúruvísindi og verkfræði Tölvunarfræði
Náttúruvísindi og verkfræði Stærðfræði

Hvaða gagn er að prímtölum?

Kristín Bjarnadóttir

Prímtölur eru tölur sem er ekki hægt að leysa upp í eiginlega þætti. Engin tala gengur upp í prímtölu nema hún sjálf og 1, sem er hlutleysa og hefur engin áhrif í margföldun.

Oft getur verið þægilegt að fást við tölur sem margar aðrar tölur ganga upp í. Það á til dæmis við töluna 60. Tölurnar 2, 3, 4, 5, 6, 10, 12, 15, 20 og 30 ganga upp í hana auk 1 og 60. Líklegt þykir að þessi eiginleiki tölunnar 60 hafi valdið því að klukkustundinni er skipt í 60 mínútur og mínútunni í 60 sekúndur.

Fjórðungur talna á bilinu 1-100 eru prímtölur.

Mikilvægi prímtalna felst í því að sérhverja náttúrlega tölu stærri en 1 má rita sem margfeldi prímtalna. Ef tala er ekki sjálf prímtala má leysa hana upp í þætti þangað til allir þættir hennar eru prímtölur. Til dæmis er 180 = 3·60 = 3·5·12 = 3·5·3·4 = 3·5·3·2·2 = $2^2·3^2·5$. Þáttun sem þessi er nefnd prímþáttun eða að leysa upp í prímþætti. Náttúrleg tala, stærri en 1, sem er ekki prímtala, er kölluð samsett tala.

Það getur líka haft sína kosti að nota tölur sem engar aðrar tölur ganga upp í, eins og prímtölurnar. Prímtölur eru eins konar frumstærðir heilla talna, hvort sem er í daglegum reikningi eða notkun þeirra í tækni, til dæmis í dulkóðun. Það er einmitt í dulkóðun sem gagnið af prímtölum er einna skýrast.

RSA-dulmálskerfið er kennt við vísindamennina Rivest, Shamir og Adleman. Það styðst við fremur einfalda hugmynd. Gagnsemi kerfisins er fólgin í að unnið er með margfeldi af mjög stórum prímtölum sem erfitt er að þátta.

Í dulkóðunarferli með RSA-kerfi eru valdar tvær prímtölur, sem við nefnum $p$ og $q$, og margfeldi þeirra fundið $n$:$$ n = p · q$$

Ef $p$ og $q$ eru báðar 300 tölustafa tölur er talan $n$ um 600 tölustafa tala. Þáttun $n$ í $p·q$ er þá mjög tímafrek.

Dulkóðunin fer þannig fram: Fundnar eru tvær að minnsta kosti 300 tölustafa prímtölur, $p$ og $q$. Það tekur aðeins nokkrar mínútur. Næst þarf að velja tölu, $e$, þannig að $e$ og $n$ hafi enga sameiginlega þætti. Ein leið er að velja $e$ sem prímtölu sem er stærri en bæði $p$ og $q$. Talnaparið ($e, n$) nefnist opinber lykill. Allir geta fengið að vita hvaða tölur $e$ og $n$ eru.

Texti, sem dulkóða skal, er fyrst þýddur yfir í einfaldan talnastreng, til dæmis þannig að hver bókstafur sé táknaður með tveggja stafa tölu. Textann þarf að þýða í skömmtum á stærð við n. Það er ekki mjög stór texti, ef til vill um tvo, þrjú hundruð bókstafir.

Látum talnastrenginn heita $T$. Textinn er dulkóðaður yfir í annan talnastreng sem við látum heita $C$, þannig að $T-$talnastrengurinn er hafinn upp í veldi með veldisvísinum $e$. Síðan er fundin leifin þegar deilt er í þá stærð með $n$. Leifin er $C$.[1]

Þá er dulkóðunartextinn tilbúinn. Þetta er ritað þannig:

$$T^e \equiv C \ mod \ n$$

Sá sem á að ráða dulmálið fær í hendur talnaparið ($d, n$) sem kallast einkalykill. Talan $d$ er margföldunarandhverfa $e$ miðað við töluna $\varphi = (p - 1)·(q - 1)$. Þá er:

$$e·d \equiv 1 \ mod \ \varphi $$

Veldishafningin og leitin að andhverfu taka einnig aðeins fáar sekúndur. Afkóðunin er þá:

$$C^d \equiv T \ mod \ n $$

af því að $C^d \equiv (T^e)^d \equiv T^{ed} \equiv T ^{k·\varphi+1} \equiv (T^\varphi)^k·T \equiv 1^k·T \ mod \ n \equiv T \ mod \ n.$[2]

Dæmi með lágum tölum:

Látum $p = 43$ og $q = 59$. Þá er $n = 43·59 =2537$. Veljum $e = 13$. Þá er opinberi lykillinn ($13, 2537$).

$\varphi = (43-1)·(59-1) = 42·58 = 2436$.

Þá er $d$ fundið þannig að $d·13 = 1 + k·2436$ fyrir eitthvert gildi á k.

Gildið $k = 5$ gefur $d = 937$.

Einkalykillinn er þá $(d, n) = (937, 2537)$.

Prófum að dulkóða orðið AF. Látum $A = 10$, $F = 17$. Þá er $T = 1017$.

Dulkóðun: $C \equiv T^e \ mod \ n \equiv 1017^{13} mod \ 2537 \equiv 2442$

Afkóðun: $T \equiv C^d \ mod \ n \equiv 2442^{937} mod \ 2537 \equiv 1017$

Þetta gildir (ef T og 2537 eru ósamþátta sem er mjög líklegt) af því að

$$C^{937} \equiv (T^{13})^{937} \equiv T^{13·937} \equiv T ^{5·2436 +1} \equiv (T^{2436})^5·T \equiv (T^{42·58})^5·T \equiv 1^5·T \ (mod \ 2537) = T \ (mod \ 2537).$$

Tilvísanir:
  1. ^ Til að finna leifina þegar deilt er með $n$ er hægt að nota aðgerðina mod sem er á mörgum vísindalegum reiknivélum, til dæmis á tölvum.
  2. ^ Hér þarf að trúa því að $T^\varphi \equiv T ^{(p-1)(q- 1)} \equiv 1 \ mod \ n$. Það byggist á Euler-reglu sem er of langt mál að skýra hér.

Höfundur

Kristín Bjarnadóttir

Kristín Bjarnadóttir

prófessor emerita

Útgáfudagur

9.10.2020

Spyrjandi

Unnur Þóra Jökulsdóttir

Efnisorð

Tilvísun

Kristín Bjarnadóttir. „Hvaða gagn er að prímtölum?“ Vísindavefurinn, 9. október 2020, sótt 30. október 2024, https://visindavefur.is/svar.php?id=75039.

Kristín Bjarnadóttir. (2020, 9. október). Hvaða gagn er að prímtölum? Vísindavefurinn. https://visindavefur.is/svar.php?id=75039

Kristín Bjarnadóttir. „Hvaða gagn er að prímtölum?“ Vísindavefurinn. 9. okt. 2020. Vefsíða. 30. okt. 2024. <https://visindavefur.is/svar.php?id=75039>.

Chicago | APA | MLA

Tengd svör

Skoða öll nýjustu svörin

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki

Senda grein til vinar

=

Hvaða gagn er að prímtölum?
Prímtölur eru tölur sem er ekki hægt að leysa upp í eiginlega þætti. Engin tala gengur upp í prímtölu nema hún sjálf og 1, sem er hlutleysa og hefur engin áhrif í margföldun.

Oft getur verið þægilegt að fást við tölur sem margar aðrar tölur ganga upp í. Það á til dæmis við töluna 60. Tölurnar 2, 3, 4, 5, 6, 10, 12, 15, 20 og 30 ganga upp í hana auk 1 og 60. Líklegt þykir að þessi eiginleiki tölunnar 60 hafi valdið því að klukkustundinni er skipt í 60 mínútur og mínútunni í 60 sekúndur.

Fjórðungur talna á bilinu 1-100 eru prímtölur.

Mikilvægi prímtalna felst í því að sérhverja náttúrlega tölu stærri en 1 má rita sem margfeldi prímtalna. Ef tala er ekki sjálf prímtala má leysa hana upp í þætti þangað til allir þættir hennar eru prímtölur. Til dæmis er 180 = 3·60 = 3·5·12 = 3·5·3·4 = 3·5·3·2·2 = $2^2·3^2·5$. Þáttun sem þessi er nefnd prímþáttun eða að leysa upp í prímþætti. Náttúrleg tala, stærri en 1, sem er ekki prímtala, er kölluð samsett tala.

Það getur líka haft sína kosti að nota tölur sem engar aðrar tölur ganga upp í, eins og prímtölurnar. Prímtölur eru eins konar frumstærðir heilla talna, hvort sem er í daglegum reikningi eða notkun þeirra í tækni, til dæmis í dulkóðun. Það er einmitt í dulkóðun sem gagnið af prímtölum er einna skýrast.

RSA-dulmálskerfið er kennt við vísindamennina Rivest, Shamir og Adleman. Það styðst við fremur einfalda hugmynd. Gagnsemi kerfisins er fólgin í að unnið er með margfeldi af mjög stórum prímtölum sem erfitt er að þátta.

Í dulkóðunarferli með RSA-kerfi eru valdar tvær prímtölur, sem við nefnum $p$ og $q$, og margfeldi þeirra fundið $n$:$$ n = p · q$$

Ef $p$ og $q$ eru báðar 300 tölustafa tölur er talan $n$ um 600 tölustafa tala. Þáttun $n$ í $p·q$ er þá mjög tímafrek.

Dulkóðunin fer þannig fram: Fundnar eru tvær að minnsta kosti 300 tölustafa prímtölur, $p$ og $q$. Það tekur aðeins nokkrar mínútur. Næst þarf að velja tölu, $e$, þannig að $e$ og $n$ hafi enga sameiginlega þætti. Ein leið er að velja $e$ sem prímtölu sem er stærri en bæði $p$ og $q$. Talnaparið ($e, n$) nefnist opinber lykill. Allir geta fengið að vita hvaða tölur $e$ og $n$ eru.

Texti, sem dulkóða skal, er fyrst þýddur yfir í einfaldan talnastreng, til dæmis þannig að hver bókstafur sé táknaður með tveggja stafa tölu. Textann þarf að þýða í skömmtum á stærð við n. Það er ekki mjög stór texti, ef til vill um tvo, þrjú hundruð bókstafir.

Látum talnastrenginn heita $T$. Textinn er dulkóðaður yfir í annan talnastreng sem við látum heita $C$, þannig að $T-$talnastrengurinn er hafinn upp í veldi með veldisvísinum $e$. Síðan er fundin leifin þegar deilt er í þá stærð með $n$. Leifin er $C$.[1]

Þá er dulkóðunartextinn tilbúinn. Þetta er ritað þannig:

$$T^e \equiv C \ mod \ n$$

Sá sem á að ráða dulmálið fær í hendur talnaparið ($d, n$) sem kallast einkalykill. Talan $d$ er margföldunarandhverfa $e$ miðað við töluna $\varphi = (p - 1)·(q - 1)$. Þá er:

$$e·d \equiv 1 \ mod \ \varphi $$

Veldishafningin og leitin að andhverfu taka einnig aðeins fáar sekúndur. Afkóðunin er þá:

$$C^d \equiv T \ mod \ n $$

af því að $C^d \equiv (T^e)^d \equiv T^{ed} \equiv T ^{k·\varphi+1} \equiv (T^\varphi)^k·T \equiv 1^k·T \ mod \ n \equiv T \ mod \ n.$[2]

Dæmi með lágum tölum:

Látum $p = 43$ og $q = 59$. Þá er $n = 43·59 =2537$. Veljum $e = 13$. Þá er opinberi lykillinn ($13, 2537$).

$\varphi = (43-1)·(59-1) = 42·58 = 2436$.

Þá er $d$ fundið þannig að $d·13 = 1 + k·2436$ fyrir eitthvert gildi á k.

Gildið $k = 5$ gefur $d = 937$.

Einkalykillinn er þá $(d, n) = (937, 2537)$.

Prófum að dulkóða orðið AF. Látum $A = 10$, $F = 17$. Þá er $T = 1017$.

Dulkóðun: $C \equiv T^e \ mod \ n \equiv 1017^{13} mod \ 2537 \equiv 2442$

Afkóðun: $T \equiv C^d \ mod \ n \equiv 2442^{937} mod \ 2537 \equiv 1017$

Þetta gildir (ef T og 2537 eru ósamþátta sem er mjög líklegt) af því að

$$C^{937} \equiv (T^{13})^{937} \equiv T^{13·937} \equiv T ^{5·2436 +1} \equiv (T^{2436})^5·T \equiv (T^{42·58})^5·T \equiv 1^5·T \ (mod \ 2537) = T \ (mod \ 2537).$$

Tilvísanir:
  1. ^ Til að finna leifina þegar deilt er með $n$ er hægt að nota aðgerðina mod sem er á mörgum vísindalegum reiknivélum, til dæmis á tölvum.
  2. ^ Hér þarf að trúa því að $T^\varphi \equiv T ^{(p-1)(q- 1)} \equiv 1 \ mod \ n$. Það byggist á Euler-reglu sem er of langt mál að skýra hér.

...