Bryde kryptering

Beregningen er ret simpel.

En 128 bit key har 2^128 mulig eværdier. Altså skal der laves 2^128 forsøg
inden man med sikkerhed har brudt den.

Så hvis det tager X micro sekunder at teste en key, så tager det X * 2^128
at forsøge alle (brute force).

2^128 er et meget stort tal !

Du kan godt lave beregninger over hvor lang tid det tager, men det er ikke altid en lige simpel opgave. Det letteste er at lave en beregning over, hvor lang tid det tager i worst-case udfra en mængde betingelser (såsom længden af input etc). Det udmynter sig nok i at se hvor antallet af mulige kombinationer og så sammenkæde det med den fremgangsmåde du vil bryde noget krypteret på. Hvis du derfor benytter brute-force metoden er det antallet af inputs du prøver i worstcase (hvilket er antallet er gyldige tegn opløftet i maxlængden af strengen plus noget mere :)) multipliceret med den tid det tager at kryptere input og sammenligne det.

Det bliver mere komplekst, hvis du skal lave statistisk analyse af, hvilken gennemsnitstid man kan forvente.

Jeg ser at jeg havde overset key-længden. Så kan jeg forsimple det jeg skrev til hvad arne_v skrev :)

Hvad med de X antal micro sekunder..

Hvad ville et realistisk bud være for en almindelig P4 3 GHz og hvad måske med en halv-stor super-computer? (Ved ikke hvor store sådan nogle er ;)

X afhænger af:
  - algoritmen
  - koden
  - compileren
  - hardwaren

Læs:
  http://www.interhack.net/pubs/des-key-crack/

Hvis vi nu antager at algoritmen, koden og compileren er optimale. Og siger at hardwaren er en almindelig P4 3 GHz.. Har du så et bud?

acid-head: Det er meget normalt at man ikke taler om tid i form af sekunder når man snakker om køretid for algoritmer. Man snakker istedet om processer-operationer i forhold til længden af det input algoritmen arbejder med.

For eksempel kan man vise at hvis man sorterer n tal med insertion sort vil køre i værste fald tage n^2 operationer.

acid-head: Det er jo svært at give et bud på. For vi kan jo forvente at du kører i et trådet miljø så den tid du rent faktisk observerer til være højere end den tid vi kan beregne os frem til. Dertil er det umiddelbart lidt svært at skulle beregne på tiden det tager at få fat i informationerne og gemme i lageret samt den tid det nu tager for lager-systemet at skrive tilbage til disken, hvis det bliver nødvendigt.

Dertil kommer at jeg ikke lige kender en god måde at undersøge hvorvidt en compiler er optimal.

Bromer: Okay.. Grunden til at jeg gerne vil have et tidseksempel er bare, at det er meget pædagogisk og nemt at relatere til.

Læs den artikel og gange op med forskellen 1998-2005

acid-head: Det forstår jeg udemærket godt, jeg prøver bare at forklare hvorfor tid ikke altid er et super let begreb at regne med.

Ja, det kan jeg også godt se og forstå, jeg kunne bare godt tænke mig, at få fingerpeg om, hvilke antagelser jeg skal lave..

Det er jo bare et fiktivt eksempel, så præcisionen betyder ikke alting.

Jeg synes også du skal læse den artikel som arne_v postede tidligere.

Med hensyn til hvilke antagelser du skal tage så har arne_v allerede nævnt nogle af de ting som køretiden afhænger af nemlig "algoritmen, koden, compileren, hardwaren". En anden vigtig faktisk er også hvilken input du giver til algoritmen. Der er tilfælde hvor man kan begrænse dette domæne. Hvis man for eksempel vil bryge personlige passwords er det måske en fair antagelse at typiske passwords består af alphanumeriske tegn, samt længden af passwordet max er 16. Det er stadig man kombinationer men dog væsentligt mindre end hvis man skulle udtømme alle muligheder inden for et tegnsæt.

Okay. Læser artiklen grundigere lidt senere..
Ellers tak for hjælpen!

Smid et svar begge to, så skal i få nogle point :)

danke

ok

husk at ved brute force angreb vil man i gennemsnit skulle lave (2^128)/2 forsøg for at bryde nøglen.