Hoppa yfir í efnið

Stærðfræði dulritunar

Í síðasta kafla notuðum við stafróf, tilfærslur og mynstur til að skoða klassískar dulritunaraðferðir. Nú ætlum við að kynna nokkur stærðfræðileg verkfæri sem koma aftur og aftur í dulritun.

Markmiðið er ekki að gera okkur að stærðfræðingum á einum kafla. Við þurfum fyrst og fremst að læra að reikna með leifum, frumtölum, deilum og veldum. Þetta eru verkfæri sem hjálpa okkur síðar að skilja til dæmis RSA og Diffie–Hellman.

Stærðfræðin er verkfæri, ekki veggur

Það er allt í lagi að þurfa að lesa dæmi tvisvar. Við munum vinna með litlar tölur í þessum kafla og nota Python til að sannreyna útreikningana. Þegar tölurnar verða stórar lætur tölvan um útreikningana; við þurfum að skilja hugmyndina og vita hvað á að biðja hana um.

Klukkureikningur og leifar

Hugsum okkur venjulegt klukkuskífu með 12 tölum. Ef klukkan er 10 og við bætum 5 klukkustundum við, þá erum við ekki komin í „15“ á skífunni. Við erum komin í 3.

10 + 5 = 15
15 á 12-stunda klukku = 3

Við höfum í raun látið töluna „snúa hringinn“. Þetta er kjarninn í leifareikningi (e. modular arithmetic), sem oft er kallaður modulo-reikningur.

Þegar við skrifum:

17 mod 5 = 2

erum við að spyrja: „Hver er afgangurinn þegar 17 er deilt með 5?“

17 = 3 · 5 + 2

Afgangurinn er 2.

Sýnidæmi: finnum afganginn

Reiknum 29 mod 7:

  1. Stærsta margfeldi af 7 sem er ekki stærra en 29 er 4 · 7 = 28.
  2. Einn stendur eftir.
  3. Þess vegna er 29 mod 7 = 1.
29 = 4 · 7 + 1

Í Python notum við %-virkjann:

>>> 29 % 7
1
>>> 17 % 5
2

Æfing: leifin

Æfing 1

Reiknaðu:

  1. 23 mod 6
  2. 100 mod 9
  3. 48 mod 12
  4. 7 mod 10
Lausn við æfingu 1
  1. 23 mod 6 = 5, því 23 = 3 · 6 + 5.
  2. 100 mod 9 = 1, því 100 = 11 · 9 + 1.
  3. 48 mod 12 = 0, því 12 gengur upp í 48 án afgangs.
  4. 7 mod 10 = 7, því 10 gengur ekki einu sinni upp í 7. Þegar talan er minni en deilirinn er hún sjálf leifin.

Í Python má sannreyna svörin:

[23 % 6, 100 % 9, 48 % 12, 7 % 10]
# [5, 1, 0, 7]

Jafngildi modulo

Í venjulegum reikningi eru tölurnar 5 og 17 ólíkar. En á 12-stunda klukku lenda þær á sama stað:

5 mod 12 = 5
17 mod 12 = 5

Við segjum að 5 og 17 séu jafngildar modulo 12. Þetta má skrifa svona:

[ a \equiv b \pmod n ] og lesa: „a er jafngilt b modulo n“.

Dæmið okkar verður:

17 ≡ 5 (mod 12)

Ástæðan er sú að munurinn á tölunum er deilanlegur með 12:

17 - 5 = 12

Þetta jafngildi leyfir okkur að skipta stórum tölum út fyrir minni leifar án þess að breyta því sem skiptir máli í modulo-reikningnum.

Sýnidæmi: einfaldari tölur

Reiknum:

(17 + 29) mod 12

Við getum fyrst lagt saman:

17 + 29 = 46
46 mod 12 = 10

En við getum líka tekið leifarnar fyrst:

17 mod 12 = 5
29 mod 12 = 5
5 + 5 = 10

Niðurstaðan er sú sama. Þetta er mjög gagnlegt þegar tölurnar verða stórar.

Við getum gert það sama með margföldun:

(17 · 29) mod 12

Leið 1:

17 · 29 = 493
493 mod 12 = 1

Leið 2:

17 mod 12 = 5
29 mod 12 = 5
5 · 5 = 25
25 mod 12 = 1

Æfing: reiknaðu með leifum

Æfing 2

Reiknaðu án þess að þurfa að margfalda stórar tölur:

  1. (38 + 27) mod 10
  2. (38 · 27) mod 10
  3. (123 + 456) mod 7
  4. (123 · 456) mod 7
Lausn við æfingu 2

Við tökum leifina af hverri tölu fyrst.

  1. 38 mod 10 = 8 og 27 mod 10 = 7. Þá er 8 + 7 = 15, svo niðurstaðan er 5.
  2. Með sömu leifum er 8 · 7 = 56, svo 56 mod 10 = 6.
  3. 123 mod 7 = 4 og 456 mod 7 = 1. Þá er 4 + 1 = 5.
  4. Með sömu leifum er 4 · 1 = 4.

Svörin eru því:

1. 5
2. 6
3. 5
4. 4

Við hefðum getað reiknað 123 · 456 beint, en það hefði ekki kennt okkur neitt nýtt. Leifareikningur gerir okkur kleift að halda tölunum litlum.

Frumtölur og þáttun

Frumtala (e. prime number) er heiltala stærri en 1 sem hefur aðeins tvo jákvæða deila: 1 og töluna sjálfa.

Fyrstu frumtölurnar eru:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...

Talan 7 er frumtala vegna þess að einu jákvæðu tölurnar sem deila 7 eru 1 og 7. Talan 12 er ekki frumtala vegna þess að hún deilist líka með 2, 3, 4 og 6.

Öll jákvæð heiltala stærri en 1 má skrifa sem margfeldi frumtalna. Þetta kallast frumþáttun (e. prime factorization).

Sýnidæmi: frumþáttun á 84

Við byrjum á minnstu frumtölunni, 2:

84 = 2 · 42
42 = 2 · 21
21 = 3 · 7

Þess vegna er:

84 = 2 · 2 · 3 · 7
84 = 2² · 3 · 7

Æfing: er talan frumtala?

Æfing 3

  1. Hverjar af tölunum 17, 21, 23 og 27 eru frumtölur?
  2. Frumþáttaðu töluna 60.
Lausn við æfingu 3
  1. 17 er frumtala: hún deilist ekki með 2, 3 eða öðrum tölum á milli 2 og 16. 23 er líka frumtala. 21 er ekki frumtala því 21 = 3 · 7, og 27 er ekki frumtala því 27 = 3 · 9.
  2. Við skiptum 60 niður:
60 = 2 · 30
30 = 2 · 15
15 = 3 · 5

Því er:

60 = 2 · 2 · 3 · 5 = 2² · 3 · 5

Vissir þú?

Talan 2 er eina slétta frumtalan. Allar aðrar frumtölur eru oddatölur, því allar aðrar sléttar tölur deilast með 2.

Stærsti sameiginlegi deilirinn

Stundum viljum við vita hvaða stærsta tala deilir tveimur tölum án afgangs. Hún kallast stærsti sameiginlegi deilirinn (e. greatest common divisor, skammstafað gcd).

Til dæmis eru deilar 18:

1, 2, 3, 6, 9, 18

og deilar 24:

1, 2, 3, 4, 6, 8, 12, 24

Stærsti sameiginlegi deilirinn er því 6:

gcd(18, 24) = 6

Reiknirit Evklíðs

Við getum fundið gcd án þess að skrifa upp alla deila. Reiknirit Evklíðs notar leifar:

252 = 2 · 105 + 42
105 = 2 · 42 + 21
42  = 2 · 21 + 0

Síðasta leifin sem er ekki núll er 21, svo:

gcd(252, 105) = 21

Í Python getum við notað math.gcd:

from math import gcd

>>> gcd(252, 105)
21

Æfing: finndu gcd

Æfing 4

Reiknaðu:

  1. gcd(48, 18)
  2. gcd(101, 23)
  3. gcd(84, 30)
Lausn við æfingu 4
  1. Fyrir 48 og 18:
48 = 2 · 18 + 12
18 = 1 · 12 + 6
12 = 2 · 6 + 0

Síðasta leifin sem er ekki núll er 6, svo gcd(48, 18) = 6.

  1. Fyrir 101 og 23:
101 = 4 · 23 + 9
23  = 2 · 9 + 5
9   = 1 · 5 + 4
5   = 1 · 4 + 1
4   = 4 · 1 + 0

Því er gcd(101, 23) = 1.

  1. Fyrir 84 og 30:
84 = 2 · 30 + 24
30 = 1 · 24 + 6
24 = 4 · 6 + 0

Því er gcd(84, 30) = 6.

Þegar gcd(a, n) = 1 eiga tölurnar engan sameiginlegan deili annan en 1. Það þýðir ekki að báðar séu frumtölur; aðeins að stærsti sameiginlegi deilir þeirra sé 1.

Margföldunarandhverfur

Í venjulegum reikningi er andhverfa tölunnar 3 talan 1/3, því 3 · 1/3 = 1. Í leifareikningi leitum við að heiltölu sem gefur 1 eftir modulo-aðgerðina.

Margföldunarandhverfa (e. multiplicative inverse) tölunnar a modulo n er tala x sem uppfyllir:

a · x ≡ 1 (mod n)

Sýnidæmi: andhverfa 3 modulo 7

Við prófum tölurnar frá 1 upp:

3 · 1 = 3  → 3 mod 7 = 3
3 · 2 = 6  → 6 mod 7 = 6
3 · 3 = 9  → 9 mod 7 = 2
3 · 4 = 12 → 12 mod 7 = 5
3 · 5 = 15 → 15 mod 7 = 1

Þess vegna er:

3⁻¹ ≡ 5 (mod 7)

Við getum sannreynt það:

3 · 5 = 15
15 mod 7 = 1

Ekki allar tölur eiga andhverfu modulo n. Talan 6 á til dæmis enga margföldunarandhverfu modulo 12, því öll margfeldi af 6 hafa leifina 0 eða 6:

6 · 1 = 6
6 · 2 = 12 ≡ 0 (mod 12)
6 · 3 = 18 ≡ 6 (mod 12)

Það gerist nákvæmlega þegar gcd(a, n) er ekki 1.

Æfing: finndu andhverfuna

Æfing 5

  1. Finndu margföldunarandhverfu 5 modulo 12.
  2. Á talan 8 margföldunarandhverfu modulo 15?
  3. Á talan 6 margföldunarandhverfu modulo 15?
Lausn við æfingu 5
  1. Við prófum:
5 · 1 = 5
5 · 2 = 10
5 · 3 = 15 ≡ 3 (mod 12)
5 · 4 = 20 ≡ 8 (mod 12)
5 · 5 = 25 ≡ 1 (mod 12)

Því er margföldunarandhverfa 5 modulo 12 talan 5.

  1. gcd(8, 15) = 1, svo andhverfa ætti að vera til. Við prófum 2:
8 · 2 = 16 ≡ 1 (mod 15)

Andhverfan er því 2.

  1. gcd(6, 15) = 3, ekki 1. Þess vegna er engin margföldunarandhverfa fyrir 6 modulo 15.

Þetta er ástæðan fyrir því að gcd-reikningurinn er mikilvægur: hann segir okkur strax hvort við ættum að leita að andhverfu eða hætta við.

Veldareikningur með modulo

Nútímaleg dulritun notar oft mjög stór veldi. Við viljum geta reiknað:

3¹³ mod 17

án þess að skrifa niður gríðarlega stóra tölu.

Veldareikningur með modulo (e. modular exponentiation) leyfir okkur að taka leifina eftir hvert skref.

Sýnidæmi: 3⁴ mod 7

Við getum reiknað beint:

3⁴ = 81
81 mod 7 = 4

En við getum líka tekið leifina á leiðinni:

3² = 9 ≡ 2 (mod 7)
3⁴ = 3² · 3² ≡ 2 · 2 = 4 (mod 7)

Niðurstaðan er enn 4.

Í Python er innbyggða pow-fallið mjög gagnlegt:

>>> pow(3, 4, 7)
4

Þriðja viðfang pow segir Python að reikna 3⁴ mod 7 á skilvirkan hátt.

Sýnidæmi: 2¹⁰ mod 7

Við getum nýtt okkur veldi af 2:

2² = 4
2⁴ = 16 ≡ 2 (mod 7)
2⁸ ≡ 2² = 4 (mod 7)

Þar sem 10 = 8 + 2 fæst:

2¹⁰ = 2⁸ · 2² ≡ 4 · 4 = 16 ≡ 2 (mod 7)

Því er:

2¹⁰ mod 7 = 2

Python staðfestir:

>>> pow(2, 10, 7)
2

Æfing: veldi og leifar

Æfing 6

Reiknaðu:

  1. 2⁵ mod 7
  2. 5³ mod 13
  3. 7⁴ mod 10

Notaðu fyrst blað og blýant og sannreyndu svo með Python.

Lausn við æfingu 6
  1. 2⁵ = 32 og 32 mod 7 = 4, svo svarið er 4.
  2. 5³ = 125 og 125 mod 13 = 8, svo svarið er 8.
  3. 7² = 49 ≡ 9 (mod 10). Þá er 7⁴ ≡ 9² = 81 ≡ 1 (mod 10), svo svarið er 1.

Í Python:

[pow(2, 5, 7), pow(5, 3, 13), pow(7, 4, 10)]
# [4, 8, 1]

Af hverju skiptir þetta máli í dulritun?

Nú höfum við safnað saman nokkrum verkfærum:

  • leifareikningi heldur tölum innan ákveðins bils,
  • frumtölur hjálpa okkur að búa til erfið talnavandamál,
  • gcd segir okkur hvort tölur eigi sameiginlega þætti,
  • margföldunarandhverfur gera okkur kleift að „snúa við“ ákveðnum aðgerðum,
  • veldareikningur með modulo gerir stóran útreikning framkvæmanlegan.

Þetta er ekki tilviljunarkenndur listi. Í mörgum dulmálskerfum er auðvelt að framkvæma útreikninginn í eina átt, en erfitt að finna leyndu upplýsingarnar sem þarf til að fara til baka.

Sýnidæmi: pínulítið dulmálskerfi

Við skulum nota mjög lítið og algjörlega óöruggt dæmi:

Dulrita:  x → (x + 3) mod 10
Dulráða: x → (x - 3) mod 10

Ef x = 8:

(8 + 3) mod 10 = 1

Til baka:

(1 - 3) mod 10 = 8

Þetta er bara töluleg útgáfa af Caesar-dulritun. Næst getum við notað margföldun, andhverfur og stærri modulo-tölur til að búa til flóknari kennsludæmi.

Ekki rugla stærðfræðilegri erfiðleika saman við öryggi

Það að útreikningur sé leiðinlegur fyrir okkur þýðir ekki endilega að hann sé öruggur. Öryggi dulritunar byggist á nákvæmri greiningu, góðum slembitölum, réttum lyklastærðum og vandlega prófuðum aðferðum — ekki bara á því að tölurnar séu stórar.

Lokaverkefni: allt saman

Æfing 7

Við höfum tölurnar a = 7 og n = 20.

  1. Finndu gcd(7, 20).
  2. Finndu margföldunarandhverfu 7 modulo 20.
  3. Reiknaðu 7 · 3 mod 20.
  4. Reiknaðu 7⁴ mod 20.
Lausn við æfingu 7
  1. Reiknirit Evklíðs gefur:
20 = 2 · 7 + 6
7  = 1 · 6 + 1
6  = 6 · 1 + 0

Því er gcd(7, 20) = 1.

  1. Þar sem gcd er 1 ætti andhverfa að vera til. Við prófum 3:
7 · 3 = 21 ≡ 1 (mod 20)

Andhverfan er 3.

  1. 7 · 3 = 21, og 21 mod 20 = 1. Þetta er líka staðfesting á því að 3 sé andhverfan.

  2. Við getum reiknað:

7² = 49 ≡ 9 (mod 20)
7⁴ ≡ 9² = 81 ≡ 1 (mod 20)

Svarið er 1.

Samantekt

Í þessum kafla lærðum við að:

  • leifareikningur vinnur með afganginn eftir deilingu,
  • tölur geta verið jafngildar modulo ákveðna tölu,
  • frumtölur hafa aðeins tvo jákvæða deila,
  • frumþáttun skrifar tölu sem margfeldi frumtalna,
  • stærsti sameiginlegi deilirinn fæst meðal annars með reikniriti Evklíðs,
  • margföldunarandhverfa a modulo n uppfyllir a · x ≡ 1 (mod n),
  • andhverfa er til aðeins þegar gcd(a, n) = 1,
  • pow(a, b, n) í Python reiknar aᵇ mod n á skilvirkan hátt,
  • þessi verkfæri eru undirstaða margra nútímalegra dulritunaraðferða.

Næst notum við stærðfræðina til að skoða einfaldari nútímalegri hugmyndir, þar á meðal XOR, einnota lykla og hvernig endurnotkun lykla getur lekið leyndarmálum.