Forfatter: Shadowmaker

Man kunne godt tro at man er anonym når man bevæger sig rundt på nettet. Men det er helt forkert.

Cookies

Cookien er små bidder af information som ens browser gemmer på en egen computer. Indholdet bestemmes af de internetsider man besøger. Ved brug af cookies kan man spore computeren, dvs. google kan f.eks. se at du har været inde på dr.dk, jp.dk, og en masse andre sider. Søg selv efter ‘tredie-parts-cookies’. EU har prøvet at lave regler der siger at brugeren skal godkende brug af cookies; det er, efter min mening, noget håbløst sludder, for fingerprinting sporer sikkert ens computere mindst lige så godt som cookies.

IP-adresse og VPN

Først og fremmest kan alle de sider du besøger normalt se din IP-adresse. Din IP-adresse er et langt nummer som fortæller hvorfra du går på nettet. En IP-adresse ser ud som 185.239.415.241.

Søg på nettet efter ‘IP-adresse’, og du finder straks et link til en side der kan oplyse dig din IP-adresse.

Hvis du ikke vil have at nogen skal kunne finde dig via din IP-adresse, så kan du gå på ud på nettet gennem en VPN. Informationerne du sender ud på nettet, fra din computer, sendes kodet til en anden computer, som så sender dine informationer ud på nettet. På de måde ser det ud som om du går på nettet gennem den anden computer. Brug af VPN koster typisk penge.

Fingerprinting

Når du går på nettet, så kan de sider du besøger spørge din browser om en masse informationer. Prøv f.eks. at gå ind på siden: https://www.amiunique.org/ og se hvilke informationer der kan læses.

Ens browser afsætter altså et specielt fingeraftryk hver gang man besøger en side på nettet. Besøger man to forskellige sider, der begge har installeret f.eks. google-analytics, så kan google se at siderne er besøgt med samme browser.

Nogle skifter mellem forskellige browsere (Firefox, Chrome, Safari, Brave, …) men det skulle, så vidt jeg har læst mig til, ikke nytte ret meget.

Bedre er det at forhindre internetsider i at hente for meget information om ens browser.

Jeg har prøvet at sætte indstillinger i Firefox så fingerprinting besværliggøres, men det virker, så vidt jeg kan se, ikke ret godt, selv om Mozilla påstår andet.

Bedre er vist browseren Brave. Her får man bedre mulighed for at blokere for fingerprinting. Man slipper nok ikke for at slå ‘Bloker scripts’ til hvis man vil have en hvis effekt. Men så er der nogle internetsider som ikke virker helt som de burde, men det blokerer effektivt for at ens browser afslører en masse information der bruges til fingerprinting.

Man kan også bruge Tor Browseren. Det er en browser som på en måde både bruger VPN (så ens IP-adresse er skjult), og så forhindrer den fingerprinting hvis man under ‘Security’ vælger ‘Safest’: “Only allows website features required for static sites and basic services. These changes affect images, media, and scripts”

Nogle er bange for at bruge Tor Browseren; de tror at den har noget at gøre med kriminelle personer. Det er noget sludder, alle kan bruge den, det er der intet ulovligt i. Den krypterer bare informationerne til og fra ens browser, og så skjuler den ens IP-adresse. Men man skal naturligvis ikke logge ind på facebook, google m.v. og så tro at man stadig er anonym.

Hvis man læser på nettet om kryptering opdager man, at der er mange der anbefaler at man ikke skriver sit eget computer-program til RSA kryptering.

Man bør, ifølge anbefalingerne, bruge færdige ‘biblioteker’, hvor færdige program-dele importeres og anvendes. Det er sikkert rigtig nok.

En meget stor fordel ved selv at skrive koden til RSA, er dog, at man har 99% styr på hvad der foregår. Det har men ikke ved brug af færdige biblioteker.

Det er dog lidt mere vanskeligt at lave et sikkert RSA kryptosystem, der er en del man skal tage hensyn til. Jeg er ikke krypteringsekspert, men herunder er nogle råd.

Et RSA-system kræver, som nævnt, to meget store primtal p og q.

De to primtal ganges så sammen til \(n = p \cdot q\).

Så skal man finde e og d. Og det er sådan set det!

For at systemet skal være rimelig sikkert, så skal man, for det første, bruge store primtal p og q, samt værdier for e og d med mange cifre.

Ifølge artiklen herunder, så er det ikke nok bare at finde to meget store primtal. De to primtal bør desuden være stærke primtal; se artiklen. Et problem er, som artiklen beskriver, at der ikke er ret mange stærke primtal. Som jeg har læst mig til, så vælger man derfor ikke stærke primtal, men primtal som opfylder krav der gør at de næsten er ‘stærke primtal’.

Man kan yderligere søge råd i

Jeg kommer måske til at skrive mere om det med sikkerhed. Jeg tror ikke det er helt så vanskeligt som nogen gør det til, og jeg vil gerne afslutte med mit eget RSA kryptosystem som opfører sig præcis som jeg vil have det til.

Det anbefales også at man bruger ‘padding’ og ‘salting’.

Padding betyder nok(?) ikke andet end at man skal særge for at de filer man krypterer har fuld information. Er de for korte skal de udfyldes med anden date.

Salting betyder nok(?) at man, inden kryptering med RSA, skal tilføje tilfældig data, således at strukturen i de oprindelige date fjernes.

Det skal jeg nok læse lidt lidt op på, men det er nærppe ret vanskeligt.

Pointen er, at man, for at alt lave RSA rimelig sikker, skal sørge for at det grundlæggende er i orden. Da princippet i RSA matematisk set er i orden, så er udfordringen at det grundlæggende er i orden, således at an angriber ikke kan angribe pga. svagheder i den grundliggende.

Jeg vender frygtelig tilbage med et RSA krypto-system som prøver at fjerne kendte svagheder, som kan tweekes efter behov, som bliver ubrydeligt for alle ‘fjender’. Jeg skal undgå kendte fælder, jeg skal lade nøglelængden være bestemt af brugeren, og jeg skal fjerne al information om selve kryptosystemet – hvorfor hjælpe en modstander med information om metoden, det er direkte åndsvagt.

Kryptering handler om at kode en meddelselse, så ikke andre end afsenderen og modtageren kan læse meddelelesen.

Jeg har, indtil videre, skrevet en del om RSA kryptering.

Jeg kommer også til at skrive om elliptisk kurve kryptering og sikket Elgamal-krypteringssystemet.

Nu skal vi se på hvordan man kan undersøge om et stort tal m er et primtal.

Den hårde og langsomme metode

Hvis tallet m ikke er et primtal, så findes der et helt tal, større end 1 og mindre end m, som går op i m. Det med at finde de tal som går op i et andet tal kaldes for faktorisering. Det kan være meget svært at faktorisere store tal. Det er i bund og grund den kendsgerning der giver sikkerheden i RSA kryptering.

Som eksempel kan vi tage tallet 987654321. Er det et primtal? Ikke let at svare på. Vi kan prøve at undersøge om 2 går op i tallet. Nej, det gør det ikke, for tallet er ikke et lige tal. Går 3 op i tallet? Vi kan jo dividere tallet 987654321 med 3. Det giver 329218107. Dermed er tallet 987654321 ikke et primtal, for 3 går jo op i det

\(987654321/2 = 493827160.5\)
\(987654321/3 = 329218107\)

Men hvad med tallet 9876543211. Det er ikke det samme tal som før. Er det et primtal? Hverken 2 eller 3 går op i det:

\(9876543211/2 = 4938271605.5\)
\(9876543211/3 = 3292181070.3333333\)

Faktisk er tallet et primtal. Så havde vi prøvet at dividere det store tal 9876543211 med de første mange hele tal; 2, 3, 4, 5, 6, 7, 8, .., så ville ingen af divisionerne gå op.

Skal man derfor undersøge om et stort tal er et primtal, så er det ikke fornuftigt at begynde fra bunden af, og så se om 2 går op i tallet, om 3 går op i tallet, ….

Vi skal se på Fermats primtalstest, og senere Miller-Rabins primtalstest.

Vi vil nu se på selve Miller-Rabin testen.

Vi har tallet n. Vi skal undersøge om dette tal n er et primtal.

Vi skriver tallet n på formen \(2^s \cdot d + 1\).

Vi tager så et tilfældigt test-tal a, positivt, og mindre end n. Dvs. \(0<a<n\).

Vi tester så tallet n ved brug af tallet a. Hvis n passerer testen, dvs. hvis n godkendes for denne værdi af a, så prøver vi med en ny tilfældig værdi for a. Sådan fortsættes f.eks. 10 gange.

Hvis n godkendes for alle de 10 værdier af a, så kan vi med stor sandsynlighed antage, at n er et primtal.

Hvis der bare er en værdi af a hvor n ikke godkendes, så ved vi at n er et sammensat tal.

Nu til testen, der består af to dele:

Hvis \(a^d \equiv_n 1\) så godkendes n for denne værdi af a, og vi tester for en ny værdi af a.

Hvis der ikke gælder at \(a^d \equiv_n 1\) , så skal vi undersøge om \(a^{2 ^ r \cdot d} \equiv_n n-1\) for en eller anden værdi af r, mindre end s.

Det gør vi helt konkret ved at prøve med r = 0, så med r = 1, så med r = 2, o.s.v. helt frem til r = s – 1. Hvis der bare for en værdi af r‘erne gælder at \(a^{2 ^ r \cdot d} \equiv_n n-1\), så passerer n testen. Hvis der ikke er nogle værdier af r, så \(a^{2 ^ r \cdot d} \equiv_n n-1\), så ved vi at n er et sammensat tal.

Python-programmet

Jeg har lavet et Python-program som tester om et helt tal n er et sammensat tal, eller, med stor sandsynlighed er et primtal.

Jeg genbruger Python-programmet som skriver n som \(2^s \cdot d + 1\). Dette er den første del i Python-programmet.

Herefter kører jeg testen som forklaret herover:

import random

n = 1001                            # Tallet der skal testes

# Skriv tallet n på den specielle form, dvs. bestem s og d
s = 0
d =  n-1
while True:
    if d % 2 == 0:
        d = d // 2
        s=s+1
    else:
        break


i_max = 10                          # Antal a'værdier der testes med
sammensat = False

for i in range(1,i_max):
    
    a=random.randint(1,n-1)         # Tilfældig værdi af a
    
    if pow(a,d,n)==1:
        continue                    # Næste i og nyt a
    
    r=0                             # Undersøger for r=0 til r=s-1
    while(True):
        if pow(a,pow(2,r)*d,n)==n-1:
            break                   # Afbryd while-løkken
        else:
            r = r+1
            if r == s+1:            # Ingen værdi af r kan bruges
                sammensat=True      # Tallet er sammensat?
                break               # Hvis 'ja', afbryd while-løkken
                
    if sammensat==True:             # Er tallet sammensat?
        break                       # Hvis 'ja', afbryd i-løkken

if sammensat==True:
    print('Tallet',n,'er sammensat')
else:
    print('Tallet',n,'er et primtal')           

Eksempler på output:

Kontrol med Maple:

En pointe er, at selv om det lyder avanceret med en Miller-Rabin test, så er selve testen ret simpel at gå igennem, Python-programmet er ikke ret langt, det er ikke så kompliceret, dog skal der udføres en række tests undervejs, og resultaterne af disse tests skal der tages hånd om.

Miller-Rabin test som funktion i Python

Det kan være smart at have Miller-Rabins primtalstest som en funktion i Python. Så kan programmet let kaldes, igen og igen. Her er det uden kommentarer:

import random

def ErSammensat(n):

    s = 0
    d =  n-1
    while True:
        if d % 2 == 0:
            d = d // 2
            s=s+1
        else:
            break

    i_max = 10
    sammensat = False

    for i in range(1,i_max):
        a=random.randint(1,n-1)
    
        if pow(a,d,n)==1:
            continue
        
        r=0
        while(True):
            if pow(a,pow(2,r)*d,n)==n-1:
                break
            else:
                r = r+1
                if r == s+1:
                    sammensat=True
                    break
                
        if sammensat==True:
            break

    return sammensat

for k in range(2,100):
    if ErSammensat(k)==True:
        print(k,'er et sammensat tal')
    else:
        print(k,'er et primtal')

De sidste fem linier undersøger om tallene 2, 3, 4, …, 100 er primtal. En del af outputtet er:

Miller-Rabins test afslører, som nævnt, om et tal er et sammesat tal, eller om et tal, med stor sandsynlighed, er et primtal.

Man kunne så, for faste værdier af n, teste n for alle værdier af a fra a = 1 til a = n – 1. Resultatet ville sige noget om hvor sikker Miller-Rabin’s test er.

Man kunne også, for faste værdier af n, finde de værdier af a hvor testen giver et forkert resultat; der må være nogle værdier af a hvor testen siger ‘primtal’ selv om tallet n er et sammesat tal.

For at teste om et givet tal n er et primtal, så tester vi med forskellige værdier for a. Værdierne for a skal vælges tilfældigt blandt tallene 1, 2, …, n -1. Det med at vælge tilfældige tal er en kunst i sig selv. Mange indbyggede tilfældige-tals-generatorer, vælger ikke tilfældigt nok, så man bør bruge lidt tid på at find og anvende gode tilfældige-tals-generatorer. Der er sikkert en i et Python bibliotek der kan anvendes.

Vi har set på Fermats primtalstest. Den er anvendelig, men en bedre test er Miller-Rabins primtalstest. Miller-Rabins primtalstest skulle være meget anvendt, så lad os se på den her.

Vi har et stort tal n. Vi skal undersøge om tallet n er et primtal.

Inden vi udfører testen, så skal tallet n, der antages at være ulige, skrives på formen

\(n = 2^s \cdot d + 1\)

Det med at tallet n antages at være ulige er helt ok, det eneste primtal der er et lige tal er jo tallet 2.

Lad os se på tallet n = 201. Vi trækker 1 fra, og får tallet 200.

\(201 = 200 + 1\)

Nu dividerer vi tallet 200 med 2, og se hvad der sker:

\(200/2 = 100\)

Divisionen gik op. Vi ved nu at 2 går op i n – 1, og vi har

\(201 = 2 \cdot 100 + 1\)

Vi dividerer så de 100 med 2, og ser hvad der sker:

\(100/2 = 50\)

Divisionen gik op. Vi har nu at

\(201 = 2^2 \cdot 50 + 1\)

Vi dividerer så de 50 med 2, og ser hvad der sker:

\(50/2 = 25\)

Divisionen gik igen op. Vi har nu at

\(201 = 2^3 \cdot 25 + 1\)

Da 25 er et ulige tal, kan 25 ikke divideres med 2.

Sammenligner vi de to udtryk

\(n = 2^s \cdot d + 1\)
\(201 = 2^3 \cdot 25 + 1\)

så ser vi at s = 3 og d = 25.

Vi har nu fået skrevet tallet n på formen \(2^s \cdot d + 1\)

Python-program

Jeg har lavet et lille Python-program der udfører beregningerne for os.

Vi har tallet n, og skal undersøge om det er et primtal.

Vi trækker 1 fra tallet n. Resultatet kalder vi for d:

\(d = n-1 \)

Vi sætter s til 0. Variablen s tæller hvor mange gange 2 gå op i tallet d.

I hvert trin, så undersøges om 2 gå op i d. Hvis 2 går op i d, så forøges s med 1, og d divideres med 2. Præcis samme fremgangsmåde som i eksemplet herover.

Programmet er her:

n=201
d=n-1
s=0

while True:
    if d % 2 == 0:           # Går 2 op i d ?
        d = d // 2           # Hvis 'ja', så divideres d med 2
        s=s+1                # og s forøges med 1
    else:
        break                # Hvis 2 ikke gik op i d, så er vi færdige
 
print('n =',n)
print('2^s*d+1 = 2^',s,'',d,'+1 = ',pow(2,s)*d+1,sep='')

Output når n = 201

n = 201
2^s*d+1 = 2^3*25+1 = 201

Output når n = 987654321

n = 987654321
2^s*d+1 = 2^4*61728395+1 = 987654321

Vi er ikke helt færdige med Fermats primtalstest.

I afsnittet om Fermats primtalstest diskuterer jeg hvordan man kan teste om et stort tal m er et primtal.

Mere præcist; vi så på hvor mange af tallene a = 1,2,3, …, m – 1 som opfylder at

\(a^{m-1} \equiv 1 \textrm{ mod } m \)

Hvis m er et primtal, så skal \(a^{m-1} \equiv 1 \textrm{ mod } m \) for alle værdier af a, fra a = 1, til a = m – 1.

Hvis vi bare har en værdi af a, så \(a^{m-1}\) ikke er lig 1, modulo m, så kan m ikke være et primtal.

Vi så også, at for langt de fleste tal m, som ikke er primtal, så vil de a‘er, hvor \(a^{m-1} \equiv 1 \textrm{ mod } m \), typisk kun udgøre få procent af samtlige a‘er fra a = 1 til a = m -1.

I dette afsnit vil vi ikke se på alle værdier af a, fra a = 1 til a = m – 1. Vi vil kun se på de værdier af a som er primiske med m.

Python-program

Ved at ændre minimalt i python-programmet fra forrige afsnit, så kan jeg, for hver værdi af m, optælle hvor mange af a‘erne der både er primiske med m, og som giver 1, når a opløftes i potensen m – 1. Vi regner naturligvis modulo m.

import math
mmax=1000
for m in range(1,mmax+1):
    antal=0
    antal_primiske=0
    for a in range(1,m):
        if math.gcd(a,m)==1:
            antal_primiske+=1
            if pow(a,m-1,m)==1:
                antal+=1
    print(m,antal_primiske,antal)

I pakken math, som vi importerer, ligger funktionen gcd, som beregner den største fælles divisor for to tal.

Jeg har brugt antal_primiske til at tælle de a‘er som er primiske med m.

Jeg har brugt antal til at tælle de a‘er som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \). Bemærk at antal kun forøges hvis a både er primiske med m og \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Eksempel på output af første resultater:

1 0 0
2 1 1
3 2 2
4 2 1
5 4 4
6 2 1
7 6 6
8 4 1
9 6 2
10 4 1

I hver række står der tre tal;

• Første tal er værdien af m.
• Andet tal er antallet af a‘er, fra a = 1, til a = m -1, der er primiske med m.
• Tredie tal er antallet af de tal, der er primiske med m, som også opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Række 2: Når m = 2, så er der ét tal der er primisk med m; det er tallet 1. Og tallet 1 opfylder, at \(1^{2-1} \equiv 1 \textrm{ mod } 2 \). Derfor står der i række 2; “2 1 1”

\(1^{4-1} = 1^3 = 1 \equiv 1 \textrm{ mod } 4\)
\(3^{4-1} = 3^3 = 27 \equiv 3 \textrm{ mod } 4\)

Række 3: Når m = 3, så er der to tal som er primiske med m, og for begge de to tal gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \):

\(1^{3-1} = 1^2 = 1 \equiv 1 \textrm{ mod } 3\)
\(2^{3-1} = 2^2 = 4 \equiv 1 \textrm{ mod } 3\)

Række 4. Når m = 4, så er der to tal som er primisk med m. Det er tallene 1 og 3. Opfylder de at \(a^{m-1} \equiv 1 \textrm{ mod } m \) ?

\(1^{4-1} = 1^3 = 1 \equiv 1 \textrm{ mod } 4\)
\(3^{4-1} = 3^3 = 27 \equiv 3 \textrm{ mod } 4\)

Så det er kun tallet a = 1 der både er primisk med 4 og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Figur

Jeg har, for alle værdier af m fra m = 1 til m = 105, optalt antal a‘er der er primiske med m, og antal a‘er som både er primiske med m og som opfylder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Jag har så divideret antal med antal_primiske, og omregnet til procent.

Figuren viser resultaterne:

De værdier af m hvor procenten er 100 er primtallene. Når m er et primtal, så vil alle værdier af a, fra a = 1 til a = m – 1, både være primiske med m og opfylde at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Man kan så omvendt spørge; findes der værdier af m, som ikke er primtal, hvor der for alle a‘er, som er primiske med m, også gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \) ?

Svaret er ‘ja’, der findes sammensatte tal m som opfylder, at der for alle a‘er primiske med m, gælder at \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Disse tal kaldes Carmichael-tal. Det mindste af disse tal er 561. Der er 320 tal fra a = 1 til a = 560 som er primiske med 561. For alle disse 320 værdier af a gælder der at \(a^{560} \equiv 1 \textrm{ mod } 561 \).

Tallet 561 er ikke et primtal; \(561 = 3 \cdot 11 \cdot 17\).

Hvis vi derfor vil teste om et tal m er et primtal, og kun kontrollerer for a‘er der er primiske med m, så kan vi komme ud for værdier af m hvor alle a‘er opfylder ligningen \(a^{m-1} \equiv 1 \textrm{ mod } m \).

Figuren viser situationen.

Hvad er talteori?

For at forstå matematikken bag RSA kryptering, for at forstå matematikken bag Bitcoins, så er det nødvendigt med lidt tal-teori.

I folkeskolen har du mødt de hele tal, de lige tal, de ulige tal, primtallene.

Du ved måske, at lægger man to lige tal sammen, så får man igen et lige tal. Lægger man to ulige tal sammen, så får man et ulige tal.

Måske har du også hørt at ethvert helt positivt helt tal kan skrives som nogle primtal ganget sammen.

Det er alt sammen talteori.

Om talteorien og hjemmesiden

Jeg har været meget i tvivl om hvordan jeg skal forklare om den tal-teori der bruges på denne hjemmeside.

Der er ikke noget lettere end at opskrive en masse definitioner, opskrive nogle sætninger, og mere eller mindre skrive nogle beviser af. Og så snakke lidt om anvendelse. Problemet med den fremgangsmåde er, at læseren ingen fornemmelse har og ingen fornemmelse får for emnet.

Jeg har forsøgt at fortælle om tal-teori på en sådan måde, at læseren får et billede af teorien, hvad det er det handler om, sammenhænge, resultater.

Jeg vil arbejde med de hele tal; læseren er nemlig fortrolig med de hele tal, læseren kan let forstå beregningerne, læseren kan se mønstre i resultaterne.

I begyndelsen ville jeg, for ikke at skræmme læsere væk, helt undgå begreber som ‘grupper’ og ‘restklasser’. Men jo mere jeg får skrevet, jo sværere bliver det at undgå de præcise faglige begrever. Uden de faglige begreber er det svært at forklare kort og præcist.