Introduktion

Har du set lektionen om Moderne Kryptografi? I den sidste lektion var dette det mest populære spørgsmål blandt brugerne:

I lektionen så vi hvordan primfaktorisering spillede en afgørende rolle i opbygningen af matematiske låse. En matematisk lås(eller envejsfunktion) kræver en procedure, som er let at udføre og svær at vende.

For eksempel, hvis jeg tilfældigt vælger to store primtal såsom:P1 = 709 ogP2 = 733

og ganger dem for at få: N = P1 * P2

N = 709 * 733 = 519697     (det er let at udregne)

Så ender jeg op med to ting: et stort tal (519697) og det store tals primfaktorisering (709 * 733)

Forestil dig nu at jeg skjuler primfaktoriseringen og kun giver dig det følgende:

519697 = ? * ?     (det er  svært at udregne)

Hvis jeg beder dig om at finde primfaktoriseringen,, hvor ville du så begynde? Du skal ikke bekymre dig, alle ville kæmpe meget længe med den opgave! For at finde løsningen, skal du udføre en hel masse forsøg. Multiplikation er hurtig (let) at beregne mens primtalsfaktorisering er langsom (svært). Dette simple faktum danner grundlaget for RSA kryptering.

👁️ Se denne animerede graf at se forskellen.

Men før du går videre, har vi brug for at fokusere på det første skridt og stil os selv et vigtigt spørgsmål. Når vi siger "tilfældigt vælge to store primtal ", hvordan vi gør så det hurtigt? Er det en nem opgave?

If you think about it for a while, you'll eventually agree that this step requires, at minimum, the ability to check if a randomly generated number (such as  99194853094755497) is prime or composite. Har du en knap på din lommeregner som kan fortælle dig det?

Jeg kan ikke se en….Hvorfor ikke?

For at finde ud af det, så lad os starte med en udfordring...