---

Hej alle!

Jeg så netop at OE 5.0 kan dekryptere en krypteret fil med ROT13....
(der var en tråd om det i en anden NG)


Hvad mener I om denne kryptering?


mvh.

Brian K. Larsen
(DCE)

---

"Brian K. Larsen (DCE)" <brian@brianbrianbrian.dk> writes:

> Jeg så netop at OE 5.0 kan dekryptere en krypteret fil med ROT13....
> (der var en tråd om det i en anden NG)
>
> Hvad mener I om denne kryptering?

Tjah.. Det, den gør er at "rotere" alfabetet 13 tegn.. Sådan a bliver
til n und so.. Deraf navnet! ROT13 kan vel betegnes som meget svag
kryptering! :)

> Brian K. Larsen

--
Ole Hansen

---

Brian K. Larsen (DCE) skrev:

>Jeg så netop at OE 5.0 kan dekryptere en krypteret fil med ROT13....
>Hvad mener I om denne kryptering?

Den er fortræffelig - til det den er beregnet til, nemlig at
camouflere engelsksprogede svar på gåder og vittigheder så der
kræves et par tastetryk før de kan læses i klar tekst. Ceøi fryi.

Jeg har produceret en ROT15 der kan håndtere danske tekster.

Men ingen af koderne har en snus med sikkerhed at gøre.

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote in
news:7hee1u4ccc5nh59sbsgvnqipq6f77lh8du@sunsite.auc.dk:

> Brian K. Larsen (DCE) skrev:
>
>>Jeg så netop at OE 5.0 kan dekryptere en krypteret fil med ROT13....
>>Hvad mener I om denne kryptering?
>
> Den er fortræffelig - til det den er beregnet til, nemlig at
> camouflere engelsksprogede svar på gåder og vittigheder så der
> kræves et par tastetryk før de kan læses i klar tekst. Pr›v selv.
>
> Jeg har produceret en ROT15 der kan håndtere danske tekster.
>
> Men ingen af koderne har en snus med sikkerhed at gøre.
>

Hvorfor ikke det ? Der tales da ofte om kryptering herinde, og det er da en
ganske valid shift-cipher. Den kendes også under navnet "The Caesar Cipher".

--
Jesper Stocholm - http://stocholm.dk

Gad vide hvor lang tid der går, inden danskerne
finder ud af, at de har købt katten i sækken til valget ...

---

In article <Xns9175873761spamstocholmdk@192.38.208.81>, "Jesper Stocholm"
<spam200112@stocholm.dk> wrote:

> Hvorfor ikke det ? Der tales da ofte om kryptering herinde, og det er da
> en ganske valid shift-cipher. Den kendes også under navnet "The Caesar
> Cipher".
>
Det er muligt det kan kaldes kryptering, men det er ikke sikkerhed, da
der jo ikke er nogen nøgle ( lidt søgt kan man måske sige at der er een
nøgle)
For det skal være sikkerhed skal der være et antal nøgler, hvis man havde
sagt ROTxx så havde der været et antal nøgler.
Det svarer til at du låser din bildør men at det er den samme nøgle der
anvendes i alle biler - der ville nok være problemer med få forsikringen
til at acceptere at bilen er låst
/ch

---

> Det er muligt det kan kaldes kryptering, men det er ikke sikkerhed, da
> der jo ikke er nogen nøgle ( lidt søgt kan man måske sige at der er een
> nøgle)
> For det skal være sikkerhed skal der være et antal nøgler, hvis man havde
> sagt ROTxx så havde der været et antal nøgler.

Jeg ser ikke rigtig hvad 10 nøgler gør bedre end 1 nøgle? Fx. DES bruger da kun 1.
Og hvad hjælper det at bruge flere "nøgler" til substitution? Det kommer selvfølgelig
an på hvordan de bruges. Flytter man først 13 pladser i alfabetet og derefter 5,
svarer det jo til en gang at flytte 18 pladser? Bruger man derimod forskellige
"nøgler" til tegn 1,2,3,4 og 5 og så forfra, så giver det bedre mening?

/Aggeboe
--
Remove XXX when replying

---

On Wed, 12 Dec 2001 23:07:40 +0100, Aggeboe <XXXaggeboe@bigfoot.com> wrote:

ROT13 _er_ kryptering i gængs forstand. Det er derimod ikke en særligt
effektiv kryptering idet at antallet af mulige nøgler er 1. Tages
cæsarkryptering (som ROT13 er en udspringer af) findes der nøjagtigt det
samme antal nøgler, som alfabetet har i størrelse.

--
Jesper

---

On Wed, 12 Dec 2001 23:07:40 +0100,
Aggeboe <XXXaggeboe@bigfoot.com> wrote:
>> Det er muligt det kan kaldes kryptering, men det er ikke sikkerhed, da
>> der jo ikke er nogen nøgle ( lidt søgt kan man måske sige at der er een
>> nøgle)
>> For det skal være sikkerhed skal der være et antal nøgler, hvis man havde
>> sagt ROTxx så havde der været et antal nøgler.
>
> Jeg ser ikke rigtig hvad 10 nøgler gør bedre end 1 nøgle? Fx. DES bruger da kun 1.

Hvad er den ene nøgle du altid bruger til at DES kryptere med ?
Er det "password" ?

> Og hvad hjælper det at bruge flere "nøgler" til substitution? Det kommer selvfølgelig
> an på hvordan de bruges. Flytter man først 13 pladser i alfabetet og derefter 5,
> svarer det jo til en gang at flytte 18 pladser? Bruger man derimod forskellige
> "nøgler" til tegn 1,2,3,4 og 5 og så forfra, så giver det bedre mening?

Det der siges er, at hvis algoritmen er ROTxx, så er der xx nøgler
der skal prøves, og dermed er den sværere at bryde. xx er max 26 i
engelsk alfabet, så der skal i snit testes 13 "nøgler" hvilket
er langt mere besværligt end at teste 1. Begge dele er dog
lade-sig-gørlige indenfor menneskets levetid :)

---

> Hvad er den ene nøgle du altid bruger til at DES kryptere med ?
> Er det "password" ?

Det fatter jeg ikke en meter af? Men ok, jeg havde fuldstændig misforstået "nøgle"
begrebet i den her forbindelse :) Men DES bruger da kun en 56 bit nøgle.

> Det der siges er, at hvis algoritmen er ROTxx, så er der xx nøgler
> der skal prøves, og dermed er den sværere at bryde. xx er max 26 i
> engelsk alfabet, så der skal i snit testes 13 "nøgler" hvilket
> er langt mere besværligt end at teste 1. Begge dele er dog
> lade-sig-gørlige indenfor menneskets levetid :)

Ahh, det var sådan ROTxx skulle forståes og ikke som jeg antydede. Enig. Og den endnu
bedre metode er så den jeg nævnte med fx. ROT13 til de første 2 tegn og ROT18 til de
næste 2 tegn, osv.

/Aggeboe
--
Remove XXX when replying

---

Aggeboe wrote:

>>Hvad er den ene nøgle du altid bruger til at DES kryptere med ?
>>Er det "password" ?
>>
>
> Det fatter jeg ikke en meter af? Men ok, jeg havde fuldstændig misforstået "nøgle"
> begrebet i den her forbindelse :) Men DES bruger da kun en 56 bit nøgle.


DES har 72057594037927936 forskellige kombinationer.

ROTxx har 26 forskellige kombinationer.

---

> DES har 72057594037927936 forskellige kombinationer.
>
> ROTxx har 26 forskellige kombinationer.

Ja, og ?

Fint nok, vi snakker totalt forbi hinanden (som jeg allerede skrev i mit forrige
indlæg). Jeg troede, som jeg også allerede har skrevet, at ROTxx betød substitution
først 3 pladser, så 10, så 50, osv, altså brugen af flere "nøgler". Og i den
forbindelse er det ligemeget om man bruger 1 "nøgle" eller 1 milliardmillion "nøgler"
(substitutioner).

DES var bare et eksempel, men et dårligt ser jeg nu.

Go' Jul.

/Aggeboe
--
Remove XXX when replying

---

Aggeboe wrote:

>>DES har 72057594037927936 forskellige kombinationer.
>>ROTxx har 26 forskellige kombinationer.

> Ja, og ?


Ville blot sætte tal på det :)

---

nospam@home.terminal.dk (Povl H. Pedersen) wrote:

[snip]

>Det der siges er, at hvis algoritmen er ROTxx, så er der xx nøgler
>der skal prøves, og dermed er den sværere at bryde. xx er max 26 i
>engelsk alfabet, så der skal i snit testes 13 "nøgler" hvilket
>er langt mere besværligt end at teste 1. Begge dele er dog
>lade-sig-gørlige indenfor menneskets levetid :)

Jeg ved godt, at det så er noget helt andet vi snakker om, men
man _kan_ jo "kryptere" tekst med nøglen

ROT(2,4,5,12,7,23,5,8,19)

- altså "krypter" første tegn med ROT2, andet tegn med ROT4,
niende tegn med ROT19 og start forfra så tiende tegn "krypteres"
med ROT2, ellevte tegn med ROT4 osv. Reelt er der vel (?) tale om
en nøgle der indeholder 9 nøgler.

- nu har du 26^9 kombinationer ialt (eller er det 9^26? Min
sandsynlighedsregning er lidt rusten...)

Man kan også, i stedet for tal der repræsenterer bogstaver i et
alfabet, bruge ascii-værdier, og så har du teoretisk 256^9 (eller
er det 9^256?) kombinationer, selvom det i praksis er lidt
mindre, da nogle tegn jo ikke kan bruges i nøglen (linieskift
osv.).

Det er stadig "lade-sig-gørlige indenfor menneskets levetid" at
bryde "krypteringen", men vi er rykket et skridt videre end "The
Caesar Cipher"

---

Og egentlig, nu jeg er ved emnet, hvor trivielt er det at bryde
en tekst krypteret med ovenstående princip?

Jeg lavede engang et program der "krypterer" efter det princip -
er der nogen der har et bud på hvilken børnesang jeg har
krypteret et vers af her? Eller hvad nøglen (password) er?

http://hjem.get2net.dk/lindblad/krypt.zip

(jeg har zippet tekstfilen for at undgå at den bliver ødelagt
under turen op og ned til og fra serveren)

Programmet er skrevet i en BASIC variant

---------

FOR infileoffset = 1 TO infile.size
   IF keyoffset > Len(key) THEN
      keyoffset = 0
   END IF
   keyoffset = keyoffset + 1
   keychar = Asc(Mid(key, keyoffset, 1))
   
   inchar = infile.peek()

   IF inchar + keychar > 255 THEN
      outchar = inchar + keychar - 255
   ELSE
      outchar = inchar + keychar
   END IF

   outfile.poke(outchar)

NEXT infileoffset

--------

key er en tekststreng (password)
keychar, inchar og outchar indeholder ascii-værdier (tal)
infile er klar tekst, outfile er krypteret tekst

Dekryptering foregår naturligvis med

   IF inchar - keychar < 0 THEN
      outchar = inchar - keychar + 255
   ELSE
      outchar = inchar - keychar
   END IF



Jeg ved det - i hvert fald i teorien - er trivielt at bryde sådan
en "kryptering", men er det også så trivielt i praksis? Hehe, kom
så drenge, vis hvad i duer til...



--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

On Fri, 14 Dec 2001 23:37:59 +0100,
Thomas L. Christensen <tlc@get2net.dk> wrote:
> ROT(2,4,5,12,7,23,5,8,19)
>
> - altså "krypter" første tegn med ROT2, andet tegn med ROT4,
> niende tegn med ROT19 og start forfra så tiende tegn "krypteres"
> med ROT2, ellevte tegn med ROT4 osv. Reelt er der vel (?) tale om
> en nøgle der indeholder 9 nøgler.
>
> - nu har du 26^9 kombinationer ialt (eller er det 9^26? Min
> sandsynlighedsregning er lidt rusten...)
>
> Man kan også, i stedet for tal der repræsenterer bogstaver i et
> alfabet, bruge ascii-værdier, og så har du teoretisk 256^9 (eller
> er det 9^256?) kombinationer, selvom det i praksis er lidt
> mindre, da nogle tegn jo ikke kan bruges i nøglen (linieskift
> osv.).
> ---
>
> Og egentlig, nu jeg er ved emnet, hvor trivielt er det at bryde
> en tekst krypteret med ovenstående princip?
>
> Jeg lavede engang et program der "krypterer" efter det princip -
> er der nogen der har et bud på hvilken børnesang jeg har
> krypteret et vers af her? Eller hvad nøglen (password) er?
>
> Jeg ved det - i hvert fald i teorien - er trivielt at bryde sådan
> en "kryptering", men er det også så trivielt i praksis? Hehe, kom
> så drenge, vis hvad i duer til...
>

Det er meget trivielt. Der er stadig kun kardinaliteten af alfabetets
størrelse, så 256 nøgler er alt der skal prøves.

Alternativt kan du antage at du foretager deciderede ombytninger, men så
udnytter jeg bare at frekvensen hvormed e forekommer i dansk tekst er
urimeligt stor, og derfor kan jeg med en simpel frekvensanalyse finde e.
Samme gælder for en del andre tegn, hvorfor at jeg hurtigt kan bryde en
kryptering efter _det_ skema.

Det bliver først svært når der er flere krypteringer i gang på samme
tid. Her kan ``index of coincidence'' eventuelt komme på tale for at
bryde disse principper.

Du bliver nødt til at læse noget mere krytoanalyse, hvis vi ikke skal
bryde al din tekst :)

--
Jesper

---

jlouis@ivalde.diku.dk (Jesper Louis Andersen) wrote:

Jeg spurgte:
>> Og egentlig, nu jeg er ved emnet, hvor trivielt er det at bryde
>> en tekst krypteret med ovenstående princip?
>>
>> Jeg lavede engang et program der "krypterer" efter det princip -
>> er der nogen der har et bud på hvilken børnesang jeg har
>> krypteret et vers af her? Eller hvad nøglen (password) er?
>>
>> Jeg ved det - i hvert fald i teorien - er trivielt at bryde sådan
>> en "kryptering", men er det også så trivielt i praksis? Hehe, kom
>> så drenge, vis hvad i duer til...
>>

>
>Det er meget trivielt. Der er stadig kun kardinaliteten af alfabetets
>størrelse, så 256 nøgler er alt der skal prøves.

Øh, jeg forstår ikke hvad du mener med det. Hvad betyder
"kardinaliteten af alfabetets størrelse"?

Anyway, hvis jeg krypterer en tekst med en "nøgle der indeholder
9 nøgler", altså fx. ROT(2,4,5,12,7,23,5,8,19), så er det da 9
nøgler, der hver kan antage en af 256 værdier, du skal finde - og
som jeg siger, i teorien er det sikkert trivielt, men er det også
det i praksis? Fx. vil længden af klarteksten og længden af
password (antallet af "nøgler i nøglen") har en indflydelse på
hvor trivielt det nu også er.

>
>Alternativt kan du antage at du foretager deciderede ombytninger, men så
>udnytter jeg bare at frekvensen hvormed e forekommer i dansk tekst er
>urimeligt stor, og derfor kan jeg med en simpel frekvensanalyse finde e.
>Samme gælder for en del andre tegn, hvorfor at jeg hurtigt kan bryde en
>kryptering efter _det_ skema.

Du snakker om ROTx, hvor x kan være en værdi mellem 0 og 255,
ikk? For så har du jo helt ret.

>Det bliver først svært når der er flere krypteringer i gang på samme
>tid. Her kan ``index of coincidence'' eventuelt komme på tale for at
>bryde disse principper.

Jeg tror at vi snakker forbi hinanden. Hvad mener du med "flere
krypteringer på samme tid"? Jeg har hele tiden snakket om noget
man kunne kalde "flere krypteringer på samme tid", altså "en
nøgle der indeholder 9 nøgler".

>Du bliver nødt til at læse noget mere krytoanalyse, hvis vi ikke skal
>bryde al din tekst :)

Jamen, jeg *opfordrer* jer jo til at bryde "min" kryptering.
Og jeg _har_ læst lidt om kryptoanalyse. Ikke meget, men nok til
at lære, at det kryptosystem some *jeg* havde opfundet, allerede
var opfundet, af en fyr der hed Blaise de Vignére, for 400 år
siden... Man skal stå tidligt op, hvis man vil have en plads i
verdenshistorien...



--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

On Sat, 15 Dec 2001 11:05:13 +0100,
Thomas L. Christensen <tlc@get2net.dk> wrote:
> Øh, jeg forstår ikke hvad du mener med det. Hvad betyder
> "kardinaliteten af alfabetets størrelse"?

Kardinaliteten af en mængde er antallet af elementer i denne mængde.
Opfatter vi vores alfabet (der ikke nødvendigvis har noget med vores
normale alfabet at gøre, det er bare en betegnelse) som en mængde kan en
normal ROTx opfattes som at rotere dette alfabet. Derfor er der i det
tilfælde med en enkelt ROTx kun kardinaliteten af alfabetet antal
nøgler. (skrives normalt (i TeX) |\sigma|)

> var opfundet, af en fyr der hed Blaise de Vignére, for 400 år
> siden... Man skal stå tidligt op, hvis man vil have en plads i
> verdenshistorien...

Det er netop sådan et system jeg omtaler. Hvis du virkeligt benytter
sådan et system er det ikke nok at rotere i alle muligheder. Der gælder
det om en hel del andet. Desværre røber du, at der er 9 nøgler. Det
betyder at din længde er 9. Derefter er det et spørgsmål om at rotere
hvert 9. tegn passende. Den passende rotation kan findes ved
frekvensanalyse af hvert 9. tegn (efter ideen om, at e forekommer
temmeligt ofte i en dansk tekst).

Kendes længden ikke bliver det lidt vanskeligere.

--
Jesper

---

jlouis@fafner.diku.dk (Jesper Louis Andersen) wrote:

>On Sat, 15 Dec 2001 11:05:13 +0100,
>Thomas L. Christensen <tlc@get2net.dk> wrote:

>> Øh, jeg forstår ikke hvad du mener med det. Hvad betyder
>> "kardinaliteten af alfabetets størrelse"?
>
>Kardinaliteten af en mængde er antallet af elementer i denne mængde.

Okay, Jesper. Så lad os lige prøve at få tingene sat på plads.

Du citerer mig for følgende.:
> Og egentlig, nu jeg er ved emnet, hvor trivielt er det at bryde
> en tekst krypteret med ovenstående princip?
>
> Jeg lavede engang et program der "krypterer" efter det princip -
> er der nogen der har et bud på hvilken børnesang jeg har
> krypteret et vers af her? Eller hvad nøglen (password) er?
>
> Jeg ved det - i hvert fald i teorien - er trivielt at bryde sådan
> en "kryptering", men er det også så trivielt i praksis? Hehe, kom
> så drenge, vis hvad i duer til...
>

Hvortil du svarede:
"Det er meget trivielt. Der er stadig kun kardinaliteten af
alfabetets størrelse, så 256 nøgler er alt der skal prøves."

Det jeg kan konstatere er, at du taler om et monoalfabetisk
kryptosystem - du forstod tilsyneladende ikke, at "ovenstående
princip" og "efter det princip" refererer til det jeg også skrev,
men som du klippede bort:

<< [...] man _kan_ jo "kryptere" tekst med nøglen

ROT(2,4,5,12,7,23,5,8,19) >>

...som er en anden måde at sige "polyalfabetisk kryptosystem" på.

Men nu hvor den misforståelse er ryddet af vejen, så kan du jo
lige fortælle om du mener at et polyalfabetisk system er trivielt
at bryde.

Jeg gætter på, at der sikkert er noger her der vil mene at det er
det, men så er det jo at jeg har lagt en lille tekst på min
hjemmeside de kan bevise deres påstand med...

Og lad mig lige sige, at jeg ikke er i tvivl om at det er muligt
at bryde krypteringen - men jeg vil meget gerne have demonstreret
at det er trivielt.

Som jeg skriver - i teorien er det trivielt, men er det nu også
det i praksis?

En ting er at man lave nogle beregninger på hvor ofte tegn
forekommer, hvorefter man manuelt kan lave nogle kvalificerede
gæt og så SE/LÆSE om det giver tekst der giver mening - men
derfra, og så til at lave et computerprogram, hvor man kan smide
noget kryptotekst ind og få klartekst ud, der er langt - vil jeg
mene... og det kan jeg ikke se skulle være trivielt. Men vis mig
at jeg tager fejl, hvis det er sådan det forholder sig.


>> var opfundet, af en fyr der hed Blaise de Vignére, for 400 år
>> siden... Man skal stå tidligt op, hvis man vil have en plads i
>> verdenshistorien...
>
>Det er netop sådan et system jeg omtaler.

Ja, sådan et du _også_ omtaler...


>Desværre røber du, at der er 9 nøgler.

Hvor? Hvornår? Nej, jeg har snakket om et eksempel;

<< Anyway, hvis jeg krypterer en tekst med en "nøgle der
indeholder 9 nøgler", altså fx. ROT(2,4,5,12,7,23,5,8,19), >>

>Det
>betyder at din længde er 9. Derefter er det et spørgsmål om at rotere
>hvert 9. tegn passende. Den passende rotation kan findes ved
>frekvensanalyse af hvert 9. tegn (efter ideen om, at e forekommer
>temmeligt ofte i en dansk tekst).

Hehe... Du får det til at lyde som om det er simpelt.

En frekvensanalyse kræver at du har en stor mængde kryptotekst.
Helst skal du også kunne teste for naboskab-frekvens
(sandsynligheden for at to tegn optræder ved siden af hinanden),
hvilket er rimeligt nemt på en tekst krypteret med et
monoalfabetisk kryptosystem.

Men hvis der er brugt et polyalfabetisk kryptosystem, med fx 9
nøgler, så skal du bruge 9 gange så meget kryptotekst for at få
den samme sikkerhed i din frekvensanalysen (hvis jeg ellers har
forstået det her frekvensanalyse ret). Og jeg kan ikke lige på
stående fod se at det skulle være muligt at teste for
naboskab-frekvens på en tekst krypteret med et polyalfabetisk
kryptosystem.

Så, selv om man kender længden af nøgleordet...

>Kendes længden ikke bliver det lidt vanskeligere.

Lidt? Du skal da være direkte heldig hvis du kan gætte (!)
længden af mit nøgleord i det eksempel jeg har lagt på min
hjemmeside, pga. den begrænsede mængde kryptotekst. Og uden
længden er der ikke meget at bygge en frekvensanalyse på. Eller
hva'?




--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

On Sat, 15 Dec 2001 21:06:06 +0100,
Thomas L. Christensen <tlc@get2net.dk> wrote:
> ROT(2,4,5,12,7,23,5,8,19) >>
>
> ..som er en anden måde at sige "polyalfabetisk kryptosystem" på.

Ja, det gik også først op for mig efter et stykke tid.

Holder du nøglens længde hemmelig kan ``index of coincidence'' anvendes
til at gætte på nøglens længde. Så tager det nok længere tid, men det er
ikke umuligt at gøre med et stykke papir...

Igen er størrelsen af kryptoteksten selvfølgeligt afgørende, men givet
tilstrækkeligt mange små dele skal det nok lykkedes :) Alternativt kan
man jo bare prøve sig frem (ikke at jeg har tid til det).

--
Jesper

---

Thomas L. Christensen skrev

> Men nu hvor den misforståelse er ryddet af vejen, så kan du jo
> lige fortælle om du mener at et polyalfabetisk system er trivielt
> at bryde.
>
> Som jeg skriver - i teorien er det trivielt, men er det nu også
> det i praksis?

Må jeg her have lov til at indskyde en bemærkning om, at man i praksis
vurderer styrken af et kryptosystem ved at kigge på hvor mange resourcer det
"i snit" vil kræver at bryde systemet i den givne situation.

Hvis den givne situation er at man kun skal holde et lille stykke klartektst
hemmeligt, så kan vurderingen meget vel være, at selv ret simple
kryptosystemer vil være "sikre nok". Hvis kompleksiteten af kryptosystemet
også betyder noget, fx. fordi kodning/dekodning skal forgå uden brug af
maskiner, så kan der være god grund til at acceptere selv ret simple
systemer.

På den anden side, hvis kompleksiteten af kryptosystemet er underordnet, så
vil jeg gætte på, at der generelt gælder, at moderne systemer er mere sikre
end historiske systemer, og man i en given situation derfor lige så godt kan
benytte et moderne system.

Sådanne forhold mener jeg er vigtige når man begynder at snakke "praksis", i
modsætning til de lidt mere steril og højtflyvende forhold der normalt gør
sig gældende ved "teoretiske" overvejelser. Din udfordring er, efter min
mening, stadig rimelig "teoretisk" fordi situationen er teoretisk opstillet
og jeg mener, at polyalfabetiske systemer i praksis er trivielle at bryde
fordi det er de i næsten alle nutidige praktiske situationer hvor et moderne
kryptosystem også ville kunne anvendes.


Mvh,
--
Filip Larsen <filip.larsen@mail.dk>

---

Thomas L. Christensen wrote:
>
> Men nu hvor den misforståelse er ryddet af vejen, så kan du jo
> lige fortælle om du mener at et polyalfabetisk system er trivielt
> at bryde.

Ja, polyalfabetisk kryptering er triviel at bryde hvis mængden
er krypteret tekst er væsentlig større end nøglen. Jeg har f.eks.
på et tidspunkt fået stillet opgaven: "Lav et program der som
input tager 30KB tekst krypteret med XOR kryptering og et
nøgleord på højst 30 tegn, og som output giver den dekrypterede
tekst." Det tog tre datalogi studerende et par timer at løse
opgaven. Derefter sad vi med 1691 bytes C kode, der lavede en
frekvensanalyse for hver mulig længde af nøgleordet, og fandt
den mest sandsynlige længde. Programmet anvender derefter samme
statistik til at gætte hvert tegn i nøgleordet.

Programmet har altid fundet den rigtige længde, eller et
multiplum af længden, hvilket er næsten lige så godt. Programmet
gætter normalt de fleste tegn i nøgleordet rigtigt, med en lille
smule efterfølgende menskelig ínspektion er det nemt at finde ud
af resten.

Din kryptering er ikke identisk med XOR kryptering, men de er så
tæt på hinanden at vores program kan finde ud af noget om din
tekst. F.eks. er det meget tydligt, at længden af dit nøgleord
er 13. For at finde tegnene i nøgleordet er det nødvendigt, at
ændre lidt på programmet.

Her er den statistik som programmet udregnede for at finde talet
13, jo større tal jo mere sandsynlig længde. Læg mærke til hvor
meget 13 skiller sig ud.

1: 0.0178629275
2: 0.0168448332
3: 0.0172150493
4: 0.0174001573
5: 0.0180480355
6: 0.0133277801
7: 0.0161969550
8: 0.0170299412
9: 0.0116618076
10: 0.0231385071
11: 0.0111990374
12: 0.0111064834
13: 0.0721921422
14: 0.0168448332
15: 0.0111064834
16: 0.0133277801
17: 0.0094405109
18: 0.0116618076
19: 0.0087926327
20: 0.0203618863
21: 0.0155490768
22: 0.0122171318
23: 0.0149011986
24: 0.0177703735
25: 0.0069415521
26: 0.0577537137
27: 0.0074968763
28: 0.0129575640
29: 0.0107362673
30: 0.0111064834

--
Kasper Dupont

---

Kasper Dupont wrote:
>
> Thomas L. Christensen wrote:
> >
> > Men nu hvor den misforståelse er ryddet af vejen, så kan du jo
> > lige fortælle om du mener at et polyalfabetisk system er trivielt
> > at bryde.
[...]
>
> Din kryptering er ikke identisk med XOR kryptering, men de er så
> tæt på hinanden at vores program kan finde ud af noget om din
> tekst. F.eks. er det meget tydligt, at længden af dit nøgleord
> er 13. For at finde tegnene i nøgleordet er det nødvendigt, at
> ændre lidt på programmet.

Jeg udskiftede et par xor operationer i programmet med +'er
og -'er, og programmet gættede nu på dette nøgleord:
"Bookworld.dX\0". Det kræver ikke meget inteligens at se,
at 'X' er et forkert gæt, og der skulle have stået 'k'.
Desuden opdager jeg her, at du anvender nul karrakteren i
slutningen af nøgleordet som en del af nøgleordet. Det
betyder at hvert 13'ende tegn ikke bliver krypteret. Det
har ikke ret meget at gøre med kryptosystemet, der er blot
tale om en fejl i din implementation. Teksten er:

Se min kjole, den er hvid som sneen
alt hvad jeg ejer, det er hvidt som den
det er fordi jeg elsker alt det hvide
og fordi en snemand er min ven

Og den tekst kunne programmet finde næsten fuldstændig
automatisk.

--
Kasper Dupont

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:


>Jeg udskiftede et par xor operationer i programmet med +'er
>og -'er, og programmet gættede nu på dette nøgleord:
>"Bookworld.dX\0". Det kræver ikke meget inteligens at se,
>at 'X' er et forkert gæt, og der skulle have stået 'k'.

Som jeg allerede har sagt, så er jeg meget forundret over at du
har kunne udelede noget som helst ud fra så lidt kryptotekst. Jeg
*har* faktisk gjort en lidt længere tekst klar, fordi jeg regnede
med at der ville være en der brokkede sig over det urimelige i at
skulle udelede noget fra en så kort kryptotekst...

>Desuden opdager jeg her, at du anvender nul karrakteren i
>slutningen af nøgleordet som en del af nøgleordet. Det
>betyder at hvert 13'ende tegn ikke bliver krypteret.

Av, av, av. Den er godt nok pinlig. Det burde jeg da have set.

>Det
>har ikke ret meget at gøre med kryptosystemet, der er blot
>tale om en fejl i din implementation.

Hov, vent nu lige lidt. Kan den fejl ikke være årsagen til at 13
skillede sig så markant ud? Umiddelbart synes jeg tendensen er
ret voldsom i den statistik du viste i dit forrige indlæg -
ville den være lige så tydelig, hvis programmet ikke havde haft
den fejl?

>Teksten er:
>
>Se min kjole, den er hvid som sneen
>alt hvad jeg ejer, det er hvidt som den
>det er fordi jeg elsker alt det hvide
>og fordi en snemand er min ven
>
>Og den tekst kunne programmet finde næsten fuldstændig
>automatisk.

Ja, jeg er imponeret. Hehe..


--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

Thomas L. Christensen wrote:
>
> >Det
> >har ikke ret meget at gøre med kryptosystemet, der er blot
> >tale om en fejl i din implementation.
>
> Hov, vent nu lige lidt. Kan den fejl ikke være årsagen til at 13
> skillede sig så markant ud? Umiddelbart synes jeg tendensen er
> ret voldsom i den statistik du viste i dit forrige indlæg -
> ville den være lige så tydelig, hvis programmet ikke havde haft
> den fejl?

Jeg tror ikke at din fejl ændrer ret meget på hvad vores
program kunne finde ud af. For vores program er et null
tegn i nøglen nøjagtig lige så godt som et vilkårligt
andet tegn. Men hvis man havde kendt fejlen på forhånd
kunne man have udnyttet den.

Jeg tror derimod at det kan have haft en betydning, at
længden af nøglen er et primtal. Hvis du kun havde brugt
de 12 tegn, ville divisorer i 12 sikkert også have skillet
sig lidt ud. I så fald kunne programmet muligvis have
troet at længden havde været 2, 3, 4 eller 6.

På den anden side ville man nok ikke vinde særlig meget
ved at holde sig fra primtal. Med den viden ville man på
forhånd kunne udelukke nogle muligheder, og dermed
nemmere kunne bryde systemet.

--
Kasper Dupont

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:


>Ja, polyalfabetisk kryptering er triviel at bryde hvis mængden
>er krypteret tekst er væsentlig større end nøglen.

Jeg ville egentlig have sagt, at der skal *en hel del* tekst til
- men jeg kan se at du jo lige har bevist det modsatte... :-/

Og lad mig sige; det overrasker mig. Oprindeligt var mit
spørgsmål; "hvor svært er det at bryde sådan en kryptering?", men
jeg havde samtidig den opfattelse, at det er nemmere at sige "det
er trivielt" end faktisk at gøre det. Nu ved jeg ikke rigtig hvad
jeg skal tro...

>Jeg har f.eks.
>på et tidspunkt fået stillet opgaven: "Lav et program der som
>input tager 30KB tekst krypteret med XOR kryptering og et
>nøgleord på højst 30 tegn, og som output giver den dekrypterede
>tekst." Det tog tre datalogi studerende et par timer at løse
>opgaven.

Nu ved jeg ikke hvilken løsning i er kommet frem til, men det jeg
har set af forsøg på at finde længden af nøgleordet [1], har ikke
set trivielt ud.

Men okay, jeg må jo bøje mig og erkende, at det må siges at
være trivielt, hvis et par halvstuderede dataloger kan gøre det
på et par timer...

Jeg bliver sådan set lidt nysgerrig efter at se hvordan du finder
nøglen, men jeg er bange for at jeg alligevel ikke ville fatte en
brik af det, så ... glem det...

>Her er den statistik som programmet udregnede for at finde talet
>13, jo større tal jo mere sandsynlig længde. Læg mærke til hvor
>meget 13 skiller sig ud.

Jeg er forundret over at man har kunne udlede en så klar tendens
ud fra så lidt tekst.



[1]
Kryptologi, Peter Landrock og Knud Nissen, 1990 Forlaget ABACUS


--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

Thomas L. Christensen wrote:
>
> Nu ved jeg ikke hvilken løsning i er kommet frem til, men det jeg
> har set af forsøg på at finde længden af nøgleordet [1], har ikke
> set trivielt ud.

Jeg har læst den bog da jeg i gynmasiet for fem år siden skrev
3. årsopgave om kryptologi i almindelighed og RSA i særdeleshed.
Det var også den gang jeg læste hvordan man kan angribe en
polyalfabetisk substitution. Om det var i samme bog kan jeg
ikke huske.

>
> Men okay, jeg må jo bøje mig og erkende, at det må siges at
> være trivielt, hvis et par halvstuderede dataloger kan gøre det
> på et par timer...

Det tager jo lidt tid at komme i tanke om, præcis hvordan en
algoritme, man har læst om fem år tidligere, virker.

>
> Jeg bliver sådan set lidt nysgerrig efter at se hvordan du finder
> nøglen, men jeg er bange for at jeg alligevel ikke ville fatte en
> brik af det, så ... glem det...

Det er nu ikke så vanskeligt. Ikke alle tegn forekommer lige
hyppigt i en dansk tekst. Denne skævhed vil blive glattet ud
ved kryptering et polyalfabetisk system, og vil blive glattet
endnu mere ud ved et forsøg på dekryptering med en forkert
nøgle længde.

Hvis man gætter på en nøglelængde, kan man udtage par af tegn
fra cifferteksten der er krypteret med samme tegn fra nøgleordet.
Man kan nemt beregne hvor stor en procentdel af disse mulige par,
der er samme tegn. Så vælger man blot den nøgle, hvor
procentdelen bliver størst.

I dit tilfælde er der 147 tegn krypteret med en 13 tegns nøgle.
Det betyder at 4 af tegnene fra nøglen er brugt 12 gange, og de
resterende 9 er brugt 11 gange. Dermed er der i alt
4*(12*11)/2+9*(11*10)/2 = 759 par at lave statistik på.

>
> >Her er den statistik som programmet udregnede for at finde talet
> >13, jo større tal jo mere sandsynlig længde. Læg mærke til hvor
> >meget 13 skiller sig ud.
>
> Jeg er forundret over at man har kunne udlede en så klar tendens
> ud fra så lidt tekst.

Det er jeg egentlig også, jeg troede ikke det var *så* nemt.
Jeg prøvede bare vores program for at se hvor meget man kunne
sige ud fra en så lille tekst, og for at se om nøglelængden
kunne være 9 som tidligere nævnt.

>
> [1]
> Kryptologi, Peter Landrock og Knud Nissen, 1990 Forlaget ABACUS

Koden til at finde nøglelængden er faktisk meget simpel:

void compstat(int step,int start)
{
int i;
memset(stat,0,sizeof(stat));
for (i=start;i<N;i+=step)
stat[buf[i]]++;
}

int enspar()
{
int i,n=0;
for (i=0;i<256;++i) {
n+=stat[i]*(stat[i]-1);
}
return n;
}

void guesslen()
{
double bestavg,avg;
int enspartotal=0;
int trylen,i;
bestavg=0.0;
for (trylen=1;trylen<31;trylen++) {
enspartotal=0;
for (i=0;i<trylen;++i) {
compstat(trylen,i);
enspartotal+=enspar();
}
avg=(enspartotal*trylen)/(double)(N*N);
printf("%d: %.10f\n",trylen,avg);
if (avg>bestavg) {
bestavg=avg;
keylen=trylen;
}
}
}

--
Kasper Dupont

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:

>Det tager jo lidt tid at komme i tanke om, præcis hvordan en
>algoritme, man har læst om fem år tidligere, virker.
>
Så hvis du havde haft det i frisk erindring, så ville det ikke
have tage hele 3 timer? *LOL* Jeg giver op! Jeg overgiver mig!


>>Koden til at finde nøglelængden er faktisk meget simpel:
>
[snip - kode]

Ja, det ser jo umiddelbart overkommeligt ud. Jeg har desværre
ikke rigtig tid til at fordybe mig det for tiden - og der kommer
jo nok til gå er par uger før jeg får det - men jeg vil helt
sikkert kigge på det. Måske skriver jeg til dig med et par
spørgsmål.



--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

Thomas L. Christensen <tlc@get2net.dk> writes:

> Så hvis du havde haft det i frisk erindring, så ville det ikke
> have tage hele 3 timer? *LOL* Jeg giver op! Jeg overgiver mig!

Kloge hoveder (ikke mig ;)) gør altid meget ud af at forklare, at
kryptering og programmer til dette kræver en meget stor indsigt i
deres udførsel.

Altså, det kan godt være, at du har super-algoritme foo, men hvis du
laver fejl i implementationen, så kan den være så godt som
nytteløs. Kryptering baserer sig på matematiske principper på
universitetsniveau. Og mit gæt er, at man nok skal være deroppe af før
man rigtig kan begynde at udtale sig om sikkerheden af en given
kryptering på egen hånd (læs, at man ikke bare referer hvad andre
siger). Det er i alt fald min opfattelse, efter at have læst lidt om
stoffet hist og her... men jeg kunne jo også tage fejl?

Med venlig hilsen
- Jacob Atzen

---

Jacob Atzen <jacob_a@spamos.dk> writes:

> Thomas L. Christensen <tlc@get2net.dk> writes:
>
> > Så hvis du havde haft det i frisk erindring, så ville det ikke
> > have tage hele 3 timer? *LOL* Jeg giver op! Jeg overgiver mig!
>
> Kloge hoveder (ikke mig ;)) gør altid meget ud af at forklare, at
> kryptering og programmer til dette kræver en meget stor indsigt i
> deres udførsel.
>
> Altså, det kan godt være, at du har super-algoritme foo, men hvis du
> laver fejl i implementationen, så kan den være så godt som
> nytteløs.

Selvfølgelig vil en direkte fejl give forkerte resultater, men det
rigtigt farlige er ikke fejl. De bliver såmænd hurtigt nok opdaget når
det ikke kan pakkes ud igen :) Problemet er mere med alt det uden om
selve algoritmen. Hvis du er dårlig til at generere tilfældige nøgler,
så hjælper det ikke at algoritmen er god. Hvis du lækker information
på andre måder, f.eks. hvis du bruiger krypteringen som del af en
protokol, og noget af den krypterede information også findes i
en header, så er det også skidt. Og hvis det er i hardware, så pas
på med folk der kan måle tids- og strømforbrug :)

> Kryptering baserer sig på matematiske principper på
> universitetsniveau. Og mit gæt er, at man nok skal være deroppe af før
> man rigtig kan begynde at udtale sig om sikkerheden af en given
> kryptering på egen hånd (læs, at man ikke bare referer hvad andre
> siger). Det er i alt fald min opfattelse, efter at have læst lidt om
> stoffet hist og her... men jeg kunne jo også tage fejl?

Det er ikke nok at kunne matematikken på universitetsniveau. Faktisk
tror jeg ikke der er ret mange andre end specialister i kryptologi der
har en chance, og blandt dem er der også klart nogle krypto-analytikere
der er bedre end andre.

/L
--
Lasse Reichstein Nielsen - lrn@daimi.au.dk
This message may be reproduced freely for non-commercial purposes.
"... but where do you want to go tomorrow?"

---

Thomas L. Christensen wrote in
<news:oo4m1uo3e9debfs8f31sqjh7ec7bd628ra@news.get2net.dk>:

> Jamen, jeg *opfordrer* jer jo til at bryde "min" kryptering.

Så vidt jeg umiddelbart kan se, er din løsning sårbar overfor "known
plain text" angreb. Kunne jeg for eksempel lokke dig til at kryptere
et andet stykke tekst (underordnet hvilket, blot jeg kender det) med
den samme nøgle, så "burde" det være en smal sag at fortælle dig
hvilken børnesang du har hygget dig med.

--
Niels Callesøe - nørd light @work
"Jeg repræsenterer med denne udtalelse mig selv og ikke TDC Internet"
Disclaimer: http://www.spacefish.net/nica/index.php3?step=disclaim

---

"Niels Callesøe" <niels2000@spamcop.net> wrote:

>Thomas L. Christensen wrote in
><news:oo4m1uo3e9debfs8f31sqjh7ec7bd628ra@news.get2net.dk>:
>
>> Jamen, jeg *opfordrer* jer jo til at bryde "min" kryptering.
>
>Så vidt jeg umiddelbart kan se, er din løsning sårbar overfor "known
>plain text" angreb.

Altså at man lokker "fjenden" til at kryptere og sende en tekst
man selv kender, opsnapper derefter kryptoteksten og regner sig
frem til kodeordet? Jo, det er den sårbar overfor... :-/



--
Med venlig hilsen
Thomas L. Christensen, Svendborg

---

Men hvorfor har man overhoved implementeret den i OE... er det en form for
selvironi fra MS's side?? Nej vel!
Hvad er begrundelsen for at man overhovedet har valgt den ?


--
mvh.

Brian K. Larsen
(DCE)

---

On Wed, 12 Dec 2001 22:33:50 +0100,
Brian K. Larsen (DCE) <brian@brianbrianbrian.dk> wrote:
> Men hvorfor har man overhoved implementeret den i OE... er det en form for
> selvironi fra MS's side?? Nej vel!
> Hvad er begrundelsen for at man overhovedet har valgt den ?

Fordi den bruges på usenet til svar på gåder etc.
Fbeqv qra oehtrf cå hfrarg gvl fine cå tåqre rgp.

---

Povl H. Pedersen skrev:

>Fordi den bruges på usenet til svar på gåder etc.
>Sordi den bruges på usenet tiy svar på gåder etc.

Er det et eksempel på OE's implementation?

--
Bertel
http://lundhansen.dk/bertel/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>
> Povl H. Pedersen skrev:
>
> >Fordi den bruges på usenet til svar på gåder etc.
> >Sordi den bruges på usenet tiy svar på gåder etc.
>
> Er det et eksempel på OE's implementation?

Er det et eksempel på det sædvanlige brok, når Microsoft forbedrer
standarderne?

Mvh. Kim Ludvigsen

---

On Thu, 13 Dec 2001 11:07:41 +0100,
Bertel Lund Hansen <nospam@lundhansen.dk> wrote:
> Povl H. Pedersen skrev:
>
>>Fordi den bruges på usenet til svar på gåder etc.
>>Sordi den bruges på usenet tiy svar på gåder etc.
>
> Er det et eksempel på OE's implementation?

Desværre. En hurtig fundet rot13 vim makro som ikke holder.
Jeg var klar over problemet med uppercase. Kunne se det på
første bogstav.