Kryptering?

Kryptering virker ved at du har en algorithme der kan tage en text og en key også kryptere teksten udfra det, modtageren har så også keyen og kan dekryptere teksten med keyen.

Krypteringer.
Skubbe alfabetets bogstaver til den ene eller anden side, keyen er så længden af skubbets.

Skifte bogstaver ud med tal, skal brugeren have en key der fortæller hvilke tal der er hvilke bogstaver.

det er de simple som jeg kan forklare, ellers findes yahoo,google,etc.. søg på encryption burde du nok kunne finde nogle mere ud specukuleret.
-----------------------------------------------------------------------------

Min side ->www.the-hive.dk/~donp/

Hej Johan

Gode(nyere effektive) kryptosstemer kræver et stort kendskab til talteori for at forstå detaljerne - og det er uanset hvad andre kunne finde på at sige herinde.

Nu ved jeg ikke hvor stor dit kendskab er til talteori, men som altid vil jeg synes, at man skal starte i det små. Til sidst nævner jeg lidt om det såkaldte knapsack problem som også kan bruges til at kryptere med en rimelig god sikkerhed... (med mindre altså man besidder ægte NINJA-MONSTER-computere)...RSA kryptering er nok en tand for vanskeligt, hvis man vil forstå detaljerne.
-----------------------------------------------------------------------
Simple kryptosystemer
Et monoalfabetisk kryptosystem fungerer på den måde at man f.eks. skriver alfabetet:
Klaralfabet: A B C D E F ... Æ Ø Å
Krypto: H I O Q D A ... W T A

man substituerer - vælger at ethver bogstav i det oprindelige alfabet skiftes ud med et andet bogstav i alfabetet.
I det her tilfælde valgte jeg at A -> H; B->I .. osv.
Med ovenstående kan man altså skrive vil ordet "abe" i krypteret form som "hid".
Der findes mere 8.8*10^30 "måder"(nøgler) at gøre dette på så hvis man skulle få en computer til at tjekke samtlige nøgler i et forsøg på at bryde kryptosystemet vil det praktisk talt være umuligt. Tag dog ikke fejl for det vil med et statistisk angreb ikke være svært at bryde.

Et additivt kryptosystem var det som Cæsar gjorde brug af. Man tager f.eks.
Klaralfabet: A B C D E F ... Æ Ø Å
Krypto: D E F G H I A B C

Man tager altså og "skubber" det oprindelige alfabet x-antal pladser til venstre - sagt på en anden måde - man skifter et bogstav ud med bogstavet der står x pladser længere fremme. Ovenstående kryptoalfabet er "skubbet" 3 pladser til venstre.
Da det danske alfabet har 29 bogstaver vil der være 28 muligheder ... den 29. vil bare være det opindelige alfabet... for at kryptere. Det er en meget ringe sikkerhed, hvis en computer og en mand vælger at angribe systemet.

Ovenstående kryptosystemer lider under svagheden af at det er muligt at lave statistiske angreb og i kombination med en computer vil det være meget sårbart.
-----------------------------------------------------------------------
Middelsvært kryptosytem
En mand ved navn (mener jeg) Vigenére lavede et kryptosystem der brugte ikke bare ét men flere monoalfabetiske kryptosystemer til at kryptere.
Vi skriver:

*  A |  B |  C |  D |   E |  F | G |  H  | I  | J |  K | L |  M |  N ... osv 
A| A    B    C    D     E    F    G    H    I    J    K    L     M    N ... osv
B| B    C    D    E     F    G    H    I     J    K   L    M    N    O
C| C   D     E    F     G   H     I     J    K    L   M    N    O    P
D| D   E     F    G     H    I     J    K    L    M   N    O    P    Q
E| E    F     G    H     I    J     K    L    M    N   O    P    Q    R
F| F    G     H    I      J    K    L    M    N    O   P    Q    R    S
G|G   H      I     J     K    L    M    N    O    P   Q    R    S    T
H| H   I      J     K     L    M   N    O    P     Q   R    S    T    U
osv.

Idéen er så at du vælger en "nøgle" et ord(du bestemmer selv længden) ... for at gøre det simpelt her vælger jeg "ABE" som nøgleord. Jeg vil så nu prøve at kryptere ordet/sætningen "GODNAT":
nøgle: A B E A B E
krypto: G O D N A T

Nøglen repeteres hvis klarteksten er længere end nøglen.
Tænk på skemaet som et "koordinatsystem" du skal så finde "punktet" der svarer til koordinatsættet (A,G) ell. (G,A)... hvilket ses at være bogstavet "G".
Det samme gøres med (B,O), (E,D), osv... vi får altså:
GODNAT -> GPHNBX

I det her tilfælde oplevede vi dog at der ikke var nogen egentlig "kryptering" ved bogstaverne A og N... Men hvis man nu lige lagde et ekstra T på GODNAT ... GODNATT og lagde det oveni GPHNBX vil man se at T før blev til X... det ekstra T bliver dog ikke til X men derimod T selv. Pointen er her at det samme bogstav krypteres forskelligt.
Dog i dette tilfælde ikke særligt godt...

Denne metode gør det noget langsommere med et statisktisk angreb, hvis man angriber det. En computer er nærmest en nødvendighed hvis man vil bryde dette kryptosystem hurtigt.
-----------------------------------------------------------------------
Public key kryptosystemer(svære)
En ting der er essentielt ved de ovennævnte kryptosystemer er hemmeligholdelsen af nøglen ... den blev brugt til både kryptering og dekryptering.

Det var nærmest sensationelt da man fandt ud af at lave kryptosystemer hvor det var muligt at offentliggøre én nøgle mens en anden blev hemmeligholdt.

Du kan prøve at forestille dig at du har en lille boks med plads til en besked til mig.
Jeg har en "postkasse" som alle kan åbne og lægge bokse i.
Derudover kan du ligesåvel som andre gå hen og bestille en "MF-hængelås" til at låse din boks.

Du får pludselig lyst til at sende mig en besked som andre ikke må se... du "krypterer" din meddelelse (putter den i boksen og låser den med min hængelås) og putter den i min postkasse... Jeg er så den eneste der har en nøgle som passer til hængelåsen og derfor kan jeg åbne boksen og læse beskeden.

Med et rimeligt kendskab til talteori kan man lave algoritmer der er baseret på knapsackproblemet som er beregningsmæssigt svært. Jeg springer her over en del, men vil afslutte med at sige at en let knapsack I_s{2,4,9,25,47} kan blive til I_p{1798,351,1601,3005,68}...
s = secret og p= public ... man offentliggør altså den svære udgave af knapsack'en og krypterer ved hjælp af denne, mens den lette knapsack hemmeligholdes.
Hele idéen med disse systemer er at frembringe et beregningsmæssigt meget svært problem som selv de bedste supercomputere indenfor overskuelig tid ikke kan klare.
Ovenstående tyndt beskrevet public key-kryptosystem er blevet brudt, men det er de færreste der har mulighed for dette.
-----------------------------------------------------------------------

Jeg kan godt fortælle dig mere om dette, men jeg synes du skal starte med at se på det ovenstående, se om du kan bruge det til noget. Du kan også prøve at låne noget på biblioteket eller søge på internettet om kryptologi(cryptology)... Det er spændende, men kan også være forbløffende avanceret.

God fornøjelse
MF

PS.: klokken er mange og der kan godt være stavefejl eller andre småfejl hist og her... . Hovedmeningen er dog bevaret. Tilføjelse længere nede.

[Redigeret d. 01/09-05 16:30:00 af MF]

Hej Johan

Gode(og så mener jeg gode) krypteringsalgoritmer kræver et stort kendskab til talteori for at forstå detaljerne - og det er uanset hvad andre kunne finde på at sige herinde.

Ikke nødvendigvis. Ved symmetrisk kryptering (samme nøgle til kryptering og dekryptering) bruges sjælden sværere matematik end modulær addition og multiplikation. Derudover bit operationer som shift, rotation, and, or og xor.

Og til Johans formål vil symmetrisk kryptering sikkert være bedst. Asymmetrisk kryptering bruges ikke til kryptering af data. Det er algoritmerne simpelt hen for langsomme til og dataene kommer til at fylde mere. I stedet bruger man en hybrid, hvor dataene krypteres med en tilfældigt valgt nøgle og en symmetrisk algoritme. Derefter krypteres nøglen med en asymmetrisk algoritme og den krypterede nøgle og dataene kan sendes til modtageren.

Og desuden er Vigenere koden absolut ikke svær at bryde uden computer. Charles Babbage var (vist nok) den første som brød koden...og det var uden computer. Jeg har selv leget med den og brudt den en del gange med succes (jeg gider ikke at løse kryds og tværser...dette er sjovere). En computer gør det rigtig nok nemmere da der skal samles en del statistik ud fra den krypterede tekst og det går noget hurtigere med en computer, men det er ikke en nødvendighed.

[Redigeret d. 01/09-05 13:33:38 af Robert Larsen]

Hej Robert...
Jeg har ændret lidt i den oprindelige tekst. Men...

Ikke nødvendigvis. Ved symmetrisk kryptering (samme nøgle til kryptering og dekryptering) bruges sjælden sværere matematik end modulær addition og multiplikation. Derudover bit operationer som shift, rotation, and, or og xor.

Jeg tænker nok mest på Knapsack og RSA kryptosystemerne der kræver et større kendskab til matematik(talteori) for at forstå de overvejelser der ligger bag systemerne. Ved RSA f.eks. faktoriseringsteori... Knapsack.. Polynomieltidsløsning...

Og desuden er Vigenere koden absolut ikke svær at bryde uden computer. Charles Babbage var (vist nok) den første som brød koden...og det var uden computer. Jeg har selv leget med den og brudt den en del gange med succes (jeg gider ikke at løse kryds og tværser...dette er sjovere). En computer gør det rigtig nok nemmere da der skal samles en del statistik ud fra den krypterede tekst og det går noget hurtigere med en computer, men det er ikke en nødvendighed.

Jeg tager mine ord i mig igen og vælger at omformulere. Det er rigtigt nok at det ikke svært, men nærmere en langsommelig affære uden en computer. Håber du er enig med det Erfaring er selvfølgelig også godt.

Hvad Johan har brug for er vel i starten at konstruere et simpelt krypteringsalgoritme i starten og så lade de andre overvejelser vente.

Venlig hilsen
MF

Okay jeg har læst alt det i har skrevet og tænkte hvorfor dog egenligt gøre det så matematisk? gør det det ikke bare nemere at bryde når der er en måde at udregne det på? Kunne det ikke være nemmere og svære at bryde at lave sådan et system hvor du vælger forskellige koder for hvert tegn fx:

a = sdsdf341sdf (fuldstændig tælfædige bogstaver og tal)
b = lafdalpasd21
c = alsdlasdf422

og så videre og så lave et program som så ser om det første bogstav er a,b,c... og så oversætter det hvis det f.eks var et 'a' til a koden = "sdsdf341sdf" og så tager den næste tegn og det er f.eks c det bliver så oversat til c = "alsdlasdf422" og så videre med de to bogstaver a og c kommer koden så til at se sådan ud samlet "sdsdf341sdfalsdlasdf422" så kunne man så f.eks også lave en kode der indikere mellemrum og så videre? så laver man bare et program der virker omvendt og så oversætter det til a og c igen? burde det ikke være en extrem svær kode at knække hvis man f.eks laver hver tegns kode på 20 tegn eller sådan noget?

Okay jeg har læst alt det i har skrevet og tænkte hvorfor dog egenligt gøre det så matematisk? gør det det ikke bare nemere at bryde når der er en måde at udregne det på? K...

Dit data kommer da til at fylde en hel del på den måde, og jeg tror heller ikke det bliver helt vildt sikkert.

Jeg har tidligere med ret stor success brugt en ganske simpel metode med XOR, som Robert også foreslår.

Princippet er simpelt:
Data = "Her skal bare være noget data, det behøver ikke være en string, men bare for at skrive noget"
Nøgle = etellerandettilfældigt1234

Krypterings rutinen kommer til at se ud som (skrevet i lidt pseudo/c agtigt kode):
for(unsigned int i=0; i<Længde af data; i++)
{
output = Data ^ Nøgle[i%længde af nøgle]; //^ er bitvis XOR, % er modulus, altså heltals resten efter en division
}

For at dekryptere dit output igen, gør du nødagtigt det samme igen, bare "pudser" nøglen på output;

Hvis du vil gøre det lidt mere avanceret, kan du lave et "offset" i hvor fra i nøglen du vil starte, så evt det første ciffer i dit output vil være dit offset i nøglen, eller lave det som en kode brugeren skal indtaste for at decryptere dit data igen... det blev en ret rodet forklaring, der skal vidst lidt mere pseudo kode til.

output[0] = offset;
for(unsigned int i=0; i<Længde af data; i++)
{
output[i+1] = Data ^ Nøgle[(i+offset)%længde af nøgle]; //^ er bitvis XOR, % er modulus, altså heltals resten efter en division
}

Jeg har lavet et lille exempel efter denne type. Det er skrevet i Borland C++ builder, du kan hente det på:
http://b2vn.dk/div/crypt.zip

Held og lykke med det

Okay jeg har læst alt det i har skrevet og tænkte hvorfor dog egenligt gøre det så matematisk? gør det det ikke bare nemere at bryde når der er en måde at udregne det på? Kunne det ikke være nemmere og svære at bryde at lave sådan et system hvor du vælger forskellige koder for hvert tegn fx:

a = sdsdf341sdf (fuldstændig tælfædige bogstaver og tal)
b = lafdalpasd21
c = alsdlasdf422

og så videre og så lave et program som så ser om det første bogstav er a,b,c... og så oversætter det hvis det f.eks var et 'a' til a koden = "sdsdf341sdf" og så tager den næste tegn og det er f.eks c det bliver så oversat til c = "alsdlasdf422" og så videre med de to bogstaver a og c kommer koden så til at se sådan ud samlet "sdsdf341sdfalsdlasdf422" så kunne man så f.eks også lave en kode der indikere mellemrum og så videre? så laver man bare et program der virker omvendt og så oversætter det til a og c igen? burde det ikke være en extrem svær kode at knække hvis man f.eks laver hver tegns kode på 20 tegn eller sådan noget?

Hej Johan... (også hej til jer andre)

Interessant tråd forresten.
(ser lige bort fra det de to andre siger med "pladsproblemet")

Hvis du forestiller dig du havde "sdsdf341sdfalsdlasdf422...." vil det ikke tage lang tid for et (evt. trænet) menneske(én ting som computeren ikke har er "overblik", men mennesket er tilgengæld god på dette område) at finde ud af at f.eks. "sdsdf341sdf" gik igen flere gange.. altså må det representere et bogstav ell. tal ell. noget andet. Og det er uanset hvor lang din "c= flfsaæjfaklfalknfanm104194187lknlasnla10n.... ".

Så er vi tilbage ved det problem man har kæmpet med i århundreder - et kryptosystem der er sårbart overfor et statistisk angreb...

Angående det med at det der virker mærkeligt at gøre tingene matematisk - man kan jo "bare" regne sig frem til løsningen.
Det er særligt nemt for folk med lidt viden inden for krypotlogi at bryde("regne sig frem til") de nævnte kryptosystemer på nær public key systemerne.
---------------------------------------------------------------------
Simpelt sagt er sikkerheden i RSA systemet at det er umådeligt svært at faktorisere f.eks. et tal n=p*q > 2^600 ... , hvor p og q er primtal...
Primtal er f.eks tallet 11,13,19,...,101,... kan du finde to tal eller flere der ganget med hinanden giver 11,13,19,...,101,...(du må ikke bruge kommatal eller brøker) - der findes iøvrigt uendeligt mange primtal.

Faktorisering af et tal vil sige man finder dets primfaktorer f.eks. 15 = 3*5, eller 100 = 2²*5²
Aritmetikkens fundamentalsætning siger at dette kan gøres på entydig vis(pånær lige rækkefølgen af primfaktorerne).

Når tallet der skal faktoriseres når størrelsesordnen 2^600 er det umådeligt svært.
Det må da selvfølgelig være en langsommelig affære når det er sådanne store tal vi har med at gøre??... tjaaa.. men rigtig programmering kan gøre det til en forbavsende hurtig affære.

Selv med de bedste faktoriseringsalgoritmer f.eks. Lenstra Elliptic Curve Factorization(en smart og hurtig måde med brug af elliptiske kurver) eller "den nyere som jeg ikke kan huske hvad hedder" kan det få sveden frem på de største supercomputere hvis tal over 150 cifre skal faktoriseres.

RSA-(tal) betyder hvilken bits nøgler vi har brugt.

De har fat i 576 bits nøglerne(RSA-576), altså faktorisering af et tal med 576*log(2) = cirka 173 cifre.
Så må man jo bare vælge at kryptere med endnu større nøgler f.eks. 640(RSA-640) bits nøgler(mangler stadig at blive faktoriseret). Sådan bliver man så ved med at gøre nøglerne større efterhånden som computerkraft og effektiviteten af faktoriseringsalgoritmerne vokser.
---------------------------------------------------------------------
Nu har de jeg givet dig "lidt teori", mens de to andre har givet dig forslag til hvad du kan bruge... Selv synes jeg også det er en fin nok start det de har forslået - så længe sikkerheden ikke er livsnødvendig.

Venlig hilsen
MF

NB.:
Dette er kun en lille del af et meget stort og omfattende emne. Der er en grund til at nogle af de største matematikhjerner arbejder med dette.
Lenstra Elliptic Curve Factorization har jeg kun indtil videre delvist fat i teorien kan altså ikke forklare denne fuldtud.
Det med småfejlene holder stadig stik .. klokken er mange

Når tallet der skal faktoriseres når størrelsesordnen 2^600 er det umådeligt svært.
Det må da selvfølgelig være en langsommelig affære når det er sådanne store tal vi har med at gøre??... tjaaa.. men rigtig programmering kan gøre det til en forbavsende hurtig affære.

Tja....god programmering kan selvfølgelig løse problemer hurtigere end langsomme algoritmer. Men de operationer, som er nødvendige i RSA (og andre public key kryptosystemer) er tunge og vil altid være langsommere end de som symmetriske systemer bruger.
Problemet med symmetriske systemer er, at to parter, som vil kommunikere privat, skal blive enige om en nøgle. Alice finder på en nøgle, og skal formidle den videre til Bob...uden at Mallory får kendskab til den. Og det er svært.
Men asymmetriske systemer løser problemet ved at have én nøgle til at kryptere og en anden til at dekryptere. Krypterings nøglen (den offentlige nøgle) KAN bruges til at finde dekrypterings nøglen (den private nøgle), men i et godt system er det "svært". Og med svært siger man gerne at det skal tage tage så lang tid og så mange resourcer, at det ikke kan betale sig. Med store nok RSA nøgler vil det tage alle jordens computere længere end jordens forventede levealder at beregne den private nøgle.
Problemet med asymmetriske systemer er bare at de tager lang tid. Derfor den tidligere nævnte hybrid.
Hos www.komogvind.dk (et spilsite hvor jeg arbejder) bruger vi den symmetriske krypteringsalgoritme Blowfish til at kryptere spildataene mens RSA bruges til at blive enige om, hvilken nøgle, der skal bruges til at kryptere med Blowfish. Vi bruger en 768 bit RSA nøgle, som bør være ubrydelig de næste par milliarder år. Men det tager ca. et halvt sekund at dekryptere Blowfish nøglen med RSA (kodet i Java). Derimod bliver flere megabyte data krypteret og dekrypteret med Blowfish hvert sekund, og jeg tror ikke at det er Blowfish, som er flaskehalsen. Der er bare ikke brug for at sende flere data. Jeg har ikke lavet benchmarks men mener at have læst, at AES (symmetrisk algoritme) er ca. 1000 gange hurtigere end RSA.

Nu har de jeg givet dig "lidt teori", mens de to andre har givet dig forslag til hvad du kan bruge... Selv synes jeg også det er en fin nok start det de har forslået - så længe sikkerheden ikke er livsnødvendig.

Ja...kryptografi er et enormt emne og også meget spændende. Start bare med en substitutions algoritme ('A' byttes ud med 'F', 'B' byttes ud med 'Y', osv.). Så kan du jo skifte algoritmen ud, når du er klar til at gå videre.
Kig evt. på dette: http://www.eskimo.com/~weidai/cryptlib.html
Det er et lib til kryptering. Rimelig nemt at bruge, taget i betragtning hvor kompliceret et emne det er.

Hvis du forestiller dig du havde "sdsdf341sdfalsdlasdf422...." vil det ikke tage lang tid for et (evt. trænet) menneske(én ting som computeren ikke har er "overblik", men mennesket er tilgengæld god på dette område) at finde ud af at f.eks. "sdsdf341sdf" gik igen flere gange.. altså må det representere et bogstav ell. tal ell. noget andet. Og det er uanset hvor lang din "c= flfsaæjfaklfalknfanm104194187lknlasnla10n.... ".

Faktisk så er computere også ekstremt gode til at finde gentagelser. Det findes der maaange algoritmer til, og en kodebryders værkøjskasse er fyldt til randen med dem :-)
Substitution ER usikkert, men en god start.

[Redigeret d. 02/09-05 11:34:37 af Robert Larsen]

Hvis du forestiller dig du havde "sdsdf341sdfalsdlasdf422...." vil det ikke tage lang tid for et (evt. trænet) menneske(én ting som computeren ikke har er "overblik", men mennesket er tilgengæld god på dette område) at finde ud af at f.eks. "sdsdf341sdf" gik igen flere gange.. altså må det representere et bogstav ell. tal ell. noget andet. Og det er uanset hvor lang din "c= flfsaæjfaklfalknfanm104194187lknlasnla10n.... ".

Faktisk så er computere også ekstremt gode til at finde gentagelser. Det findes der maaange algoritmer til, og en kodebryders værkøjskasse er fyldt til randen med dem :-)
Substitution ER usikkert, men en god start.

Hej...

Ville bare sige at koden der blev genereret ikke ville være svært for et menneske at se på og finde perioder. At computeren så kan programmeres til at udføre operationer der fører til samme resultat er noget andet

Vi bruger en 768 bit RSA nøgle, som bør være ubrydelig de næste par milliarder år.

Mon ikke de med Number Field Sieve(af J.Pollard) samt yderligere udvikling formår at klare den indenfor de næste 5 år...???

Venlig hilsen
MF

[Redigeret d. 02/09-05 16:58:55 af MF]