---

Nu er det ikke fordi at jeg vil rakke ned på Crypticore eller andre. Men nu
så jeg dem lige i TV i fjernsynet og kom til at huske tilbage igen.

Der bliver anvendt kaosmatematik i deres produkt og det skulle i praksis
være total umuligt at knække. Men hvorfor lige kaosmatematik. Jeg vil da
mene at det ville være langt bedre at bruge tilfældighed - altså en såkaldt
tilfældighedsgenerator. Fordel bygger på at least og most bits er 100% lige
tilfælde. Så hvorfor bruge en kaos ligning?.

Og hvorfor bruges en virksomheds krypteringsværktøj når der er AES - og ens
af fordele ved AES er at der ikke er nogle patenter i det (endnu?)

I AES (Advanced Encryption Standard) er der fem prøver hvor den sidste er
udvalgt af verdens bedste cryptografer i hele verden som bruger flere timer
på at teste krypteringsværktøj. Ingen virksomhed, lige meget hvor rige de så
end må være så kan de købe sådan en form for test og da AES er gratis for
alle bruger så er der ikke nogen grund til at købe andre virksomhed´s
krypteringsværktøj. Hvorfor bruge tid på at lave en ens egn standard da åben
kryptologi er bedre, men også gratis.

og så lige en ekstra lille driller, de til de folk som stadigvæk bruger
Windows (som mig), hvad med den såkaldte NSAKEY - En NSA key i Microsoft OS
som skulle være i stand til at låse en hvilken som helst IT system som
bruger Windows, da man ikke kan have at ens produkter vender i mod en selv.
Det er jo kun en ting at gøre - Linux

Ville det helt ærlig ikke være nemmere at bedre at bruge Linux og AES, da de
begge er,: som sagt bedre og gratis ?



Note.. Jeg ved ikke helt om den skulle hører hjemme her i dk.videnskab eller
de.sikkerhed, men jeg har langt en note i dk.sikkerhed så man evt. kan
follow up.

Mvh. Christian kruse

---

"Christian" <bka@sool.2.dk> writes:

> Nu er det ikke fordi at jeg vil rakke ned på Crypticore eller andre. Men nu
> så jeg dem lige i TV i fjernsynet og kom til at huske tilbage igen.
>
> Der bliver anvendt kaosmatematik i deres produkt og det skulle i praksis
> være total umuligt at knække. Men hvorfor lige kaosmatematik. Jeg vil da
> mene at det ville være langt bedre at bruge tilfældighed - altså en såkaldt
> tilfældighedsgenerator. Fordel bygger på at least og most bits er 100% lige
> tilfælde. Så hvorfor bruge en kaos ligning?.

Godt spørgsmål. For mig lyder deres salgssnak som ren snake-oil. Hvis
ikke Ivan Damgård var involveret skulle man tro det var fup. Men når
han nu *er* involveret, er der måske alligevel noget interessant ...

---

> Godt spørgsmål. For mig lyder deres salgssnak som ren snake-oil. Hvis
> ikke Ivan Damgård var involveret skulle man tro det var fup. Men når
> han nu *er* involveret, er der måske alligevel noget interessant ...

Ivan Damgård ? - Er han ikke stadigvæk hos Århus Universitet, men jeg ved at
Thomas Bohr også arbejder for Crypticore.

---

Christian wrote:
>> Godt spørgsmål. For mig lyder deres salgssnak som ren snake-oil.
>> Hvis ikke Ivan Damgård var involveret skulle man tro det var fup.
>> Men når han nu *er* involveret, er der måske alligevel noget
>> interessant ...
>
> Ivan Damgård ? - Er han ikke stadigvæk hos Århus Universitet, men jeg
> ved at Thomas Bohr også arbejder for Crypticore.

I firmaets produktoversigt:

http://www.cryptico.com/images/files/Encryption%20Technology%20DK%200208...pdf

fremgår det, at Damgård og Bohr har stået for den *eksterne* verificering
af algoritmen.

Jeg har ikke været i stand til at finde en beskrivelse af selve algoritmen.
Det lader til, at deres største salgsargument er hastigheden.

--
Jens Axel Søgaard

---

Jesper Harder wrote:

>"Christian" <bka@sool.2.dk> writes:
>
>>Nu er det ikke fordi at jeg vil rakke ned på Crypticore eller andre. Men nu
>>så jeg dem lige i TV i fjernsynet og kom til at huske tilbage igen.
>>
>>Der bliver anvendt kaosmatematik i deres produkt og det skulle i praksis
>>være total umuligt at knække. Men hvorfor lige kaosmatematik. Jeg vil da
>>mene at det ville være langt bedre at bruge tilfældighed - altså en såkaldt
>>tilfældighedsgenerator. Fordel bygger på at least og most bits er 100% lige
>>tilfælde. Så hvorfor bruge en kaos ligning?.
>>
>
>Godt spørgsmål. For mig lyder deres salgssnak som ren snake-oil. Hvis
>ikke Ivan Damgård var involveret skulle man tro det var fup. Men når
>han nu *er* involveret, er der måske alligevel noget interessant ...
>

Jeg er heller ikke sikker på præcist hvilke problemer algoritmen sigter
imod. Det pressemateriale jeg har set er uklart. Men Ivan Damgård plejer
at vide hvad han gør.

Det er næppe hastigheden alene. Konventionelle block eller stream
ciphers er både meget hurtige og mange af dem regnes for meget sikre.

En god tilfældighedsgenerator der er sværere at "bryde", altså hvor det
at fastslå frøet ud fra en dataserie er en sværere opgave, kunne tænkes
at have en vis værdi. Kan det være pointen ? Eller fabulerer jeg frit ?

--
mvh.
Morten V. Christiansen

---

On Tue, 29 Oct 2002 22:08:18 +0100
"Christian" <bka@sool.2.dk> wrote:
> Nu er det ikke fordi at jeg vil rakke ned på Crypticore eller andre.
> Men nu så jeg dem lige i TV i fjernsynet og kom til at huske tilbage
> igen.
>
> Der bliver anvendt kaosmatematik i deres produkt og det skulle i
> praksis være total umuligt at knække. Men hvorfor lige kaosmatematik.
> Jeg vil da mene at det ville være langt bedre at bruge tilfældighed -
> altså en såkaldt tilfældighedsgenerator. Fordel bygger på at least og
> most bits er 100% lige tilfælde. Så hvorfor bruge en kaos ligning?.
>
> Og hvorfor bruges en virksomheds krypteringsværktøj når der er AES -
> og ens af fordele ved AES er at der ikke er nogle patenter i det
> (endnu?)
>
> I AES (Advanced Encryption Standard) er der fem prøver hvor den sidste
> er udvalgt af verdens bedste cryptografer i hele verden som bruger
> flere timer på at teste krypteringsværktøj. Ingen virksomhed, lige
> meget hvor rige de så end må være så kan de købe sådan en form for
> test og da AES er gratis for alle bruger så er der ikke nogen grund
> til at købe andre virksomhed´s krypteringsværktøj. Hvorfor bruge tid
> på at lave en ens egn standard da åben kryptologi er bedre, men også
> gratis.
>
> og så lige en ekstra lille driller, de til de folk som stadigvæk
> bruger Windows (som mig), hvad med den såkaldte NSAKEY - En NSA key i
> Microsoft OS som skulle være i stand til at låse en hvilken som helst
> IT system som bruger Windows, da man ikke kan have at ens produkter
> vender i mod en selv. Det er jo kun en ting at gøre - Linux
>
> Ville det helt ærlig ikke være nemmere at bedre at bruge Linux og AES,
> da de begge er,: som sagt bedre og gratis ?
>

1) kaosmatematik giver et mere random output end de bedste psoudo random
generatorer som findes på markedet - tro det eller lad være!
Kaosmatematik hedder kaos netop fordi det ikke følger et mønster og
derfor er umuligt at forudsige.


2) AES er brudt (i teorien). det var fremme i flere
krypteringssammenhæng for 4-5 måneder siden. Det er derfor kun et
spørgsmål om tid før der findes hardware som er så hurtigt at det kan
bryde AES i nær polynomisk tid.



--
Kim Schulz - Freelance Development | "All God's children are not
Email : kim @ schulz.dk | beautiful. Most of God's children
Tlf : 51904262 | are, in fact, barely

---

Kim Schulz wrote:

> 2) AES er brudt (i teorien). det var fremme i flere
> krypteringssammenhæng for 4-5 måneder siden. Det er derfor kun et
> spørgsmål om tid før der findes hardware som er så hurtigt at det kan
> bryde AES i nær polynomisk tid.

Sådanne påstande bør altid underbygges med referencer. Hvis det er
XLS-metoden, du tænker på, når du skriver at AES er "brudt" - ja så
er meningerne vist delte. Jeg mener ikke, at det er rimeligt at anvende
den sprogbrug på nuværende tidspunkt.

Her er et udklip af Bruce Schneiers månedlige nyhedsbrev:



More on AES Cryptanalysis - Bruce Schneier

I can say with certainty that no one knows for certain if XLS can break
Rijndael or Serpent or anything else. Actually, I can say something
stronger: no one has produced an actual demonstration of XLS breaking
even a simplified version of Rijndael or Serpent or anything
else. This makes a lot of people skeptical.

Demonstrations are important. When differential cryptanalysis finally
broke the full 16-round DES, the authors did not demonstrate the
attack. Even though the attack was faster than brute force, it was
still too complicated to demonstrate practically. But the authors did
demonstrate the attack against reduced-round variants of DES, and
against other algorithms. The community believed that the attack
worked because the techniques had been demonstrated multiple times and
the theory behind the techniques were well understood.

The XLS techniques have not been demonstrated yet. A number of
respectable cryptographers, whose opinions I value highly, don't think
the techniques work. Don Coppersmith has published a note on the
topic. And T. Moh has a Web page about this. (To be fair, T. Moh and
Nicolas Courtois have an ongoing diagreement about another
crypto-related topic. But while that certainly affects the
motivations, it doesn't necessarily invalidate the math.)

I know that several groups are working on the techniques, and if they
work one of those groups should be able to demonstrate something, on
something, soon. I'll provide additional information when I learn of it.

Coppersmith's comment:
<http://aes.nist.gov/aes/FMPro?-token=S021&-DB=discufm.fp3&-lay=detail&-
Format=Detail.htm&SubIDMatch=S021&-op=cn&ActiveMessages=x&-Skip=1&-Max=1
&-sortfield=ThreadID&-sortorder=descending&-sortfield=MessageID&-sortord
er=ascending&-LOP=and&-Find>
Sorry about the ridiculous link. The substance of the note is in the
"Letters from Readers" column below, or here's a referral link.
<http://makeashorterlink.com/?K27C515E1>

Moh's site:
<http://www.usdsi.com/aes.html>

My essay on XLS from last month:
<http://www.counterpane.com/crypto-gram-0209.html#1>

--
Jens Axel Søgaard

---

Kim Schulz wrote:

> 1) kaosmatematik giver et mere random output end de bedste psoudo
> random generatorer som findes på markedet - tro det eller lad være!

Hvis udsagner er sandt, er det selvmodsigende.

--
Jens Axel Søgaard

---

Kim Schulz <kim@schulz.dk> writes:

> 1) kaosmatematik giver et mere random output end de bedste psoudo random
> generatorer som findes på markedet - tro det eller lad være!

Nej. Det er en ofte set fejlslutning af kaosmatematik automatisk giver
god pseudotilfældighed. Der er mere i god pseudotilfældighed end hvad
kaosmatematikken normalt arbejder med.

Man får ikke gode pseudotilfældige resultater ved bare at tage en
tilfældig kaotisk. Der er ofte tydelige mønstre i kaotiske systemer,
det må der ikke være i gode pseudotilfældige systemer.

Dermed selvfølgelig ikke sagt at man ikke kan lave gode generatorer af
pseudotilfældige tal på baggrund af kaotiske funktioner, men det
kræver mere end bare at funktionerne er kaotiske.


Og nej, kaosmatematik giver heller ikke *rigtig* tilfældighed.

--
Peter Makholm | I have no caps-lock but I must scream...
peter@makholm.net | -- Greg
http://hacking.dk |

---

Kim Schulz wrote:
> 1) kaosmatematik giver et mere random output end de bedste psoudo random
> generatorer som findes på markedet - tro det eller lad være!

Hvad betyder "random" i denne sammenhæng?

En fraktal sekvens af tal (f.eks. Feigenbaum) er umulig at forudsige,
vilkårligt langt frem i tiden, men dens tæthed er ikke nødventigvis
flad, og der kan sagtens være stærke korrelationer mellem elementerne
i sekvensen, og derved er dens entropi lavere, sammenlignet med en
sekvens, der har en flad fordeling og hvor elementer er ukorreleret.

Det sidste ville være min definition på optimalt tilfældig.

Fraktale generatorer på en computer er også deterministiske
(ellers ville dekryptering være et problem) og derfor pseudo
random.

> Kaosmatematik hedder kaos netop fordi det ikke følger et mønster og
> derfor er umuligt at forudsige.

Tilfældigetal er tilfældige, netop hvis de ikke kan beregnes.
derfor kan de specielt ikke følge et mønster.

--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk

---

Kim Schulz <kim@schulz.dk> writes:

> 1) kaosmatematik giver et mere random output end de bedste psoudo random
> generatorer som findes på markedet - tro det eller lad være!

Efter at have diskuteret det med Jacob Sparre da vi alligevel ikke
havde andet at lave er jeg kommet frem til at jeg ikke kan tro
det. I hvert fald ikke hvis vi taler om inden for diskrete mængder.

Definitionen på kaotiske funktioner er at en forskel i udgangspunktet
vil vokse ekspotentielt. Gode generatore for tilfældige tal kræver at
den gennemsnitlige forskel mellem de enkelte skridt er halvdelen af
udfaldsrummets diameter.

Der er ganske enkelt ikke plads i udfaldsrummet til at en funktion
både kan være kaotisk og en god generator for pseodutilfældige
tal. Eller også er opløsningen i vores tilfældige tal for stor til at
kunne afgøre om de er kaotiske.

> Kaosmatematik hedder kaos netop fordi det ikke følger et mønster og
> derfor er umuligt at forudsige.

Og dette er ganske enkelt forkert. Der er masser af mønstre i kaotiske
funktioner. Fraktaler er kun sjove fordi de netop indenholder mønstre.

I øvrigt så er mange kaotiske systemer kun kaotiske på bestemte
måleskalaer. Hvis ens skridt er for små eller for store så forsvinder
kaos.

--
Peter Makholm | Sit back and watch the messages. This is actually
peter@makholm.net | more important than one might think as there is a
http://hacking.dk | bug in GNU Mach whereby hitting a key during the
| boot process causes the kernel to panic
| -- GNU Hurd Installation Guide

---

Scripsit Kim Schulz <kim@schulz.dk>

> 1) kaosmatematik giver et mere random output end de bedste psoudo random
> generatorer som findes på markedet

Det er selvmodsigende. Hvis "kaosmatematik" er en algoritme som giver
bedre pseudotilfældige tal en andre pseudotilfældighedsgeneratorer på
markedet, så *er* "kaosmatematik" dén bedste
pseudotilfældighedsgenerator på markedet. Det vil sige at din påstand
er at den er bedre end sig selv, hvilket selvklart er falsk.

--
Henning Makholm "*Se*!! Nu hælder den vand ud
af ørerne *igen*!! *Et mirakel*!!!"

---

[snip]
>
> Jeg vil godt understrege, at jeg ikke betvivler Bjarkes og (måske
> specielt) hans kollegers kompetencer udi kryptografiens kunst [1], og
> jeg antager da, at der ligger nogle pragmatiske sikerhedsmæssige
> overvejelser bag udsagnet om, at hvis blot primtallene er store nok,
> så er det ligemeget om de er stærke eller ej. Jvf den nu strandede
> diskussion med hr. Schulz, så slår jeg netop et slag for, at der altid
> laves en konkret vurdering af det nødvendige sikkerhedsniveu [2].

Ja men så skal jeg da se om jeg kan forklare min holdning til sikkerhed
så også du forstår det.
Jeg ser gang på gang (bl.a. i forbindelse med de hosting servere jeg er
sysadm på) at folk vælger ringe passwords eller slet ingen. Sikkerhed
tænker de slet ikke på i den forbindelse, men så snart det er noget med
emails der skal krypteres, så er det de helt store krypteringsalgoritmer
som bliver kørt i stilling. Andre gang så er folk helt vildt paranoide
og vil helst på nettet via anonymizere, passwords er lange og kryptiske
osv. osv....og så er mailkrypteringen helt i bund.

Her sidder du (jesper) jo nok så og tænker: "ja de laver varieret
sikkerhed ud fra en vudering om hvad de mener passer".

Sådan tænker jeg bare ikke. Er der brud på sikkerheden bare ét sted, så
er sikkerheden helt spild af ressourcer - den kan bare droppes.
Det er sket indtil flere gange at jeg har været inde og få folk til at
rette deres passwords fordi de er for korte/svage (ja jeg har konstant
en maskine som står og cracker vores brugeres passwords for at finde
svage passwords). Tilsvarende anbefaler jeg altid kunder at de benytter
en stor krypteringsnøgle når de laver mailkryptering - ofte er det som
de krypterer mails indholdende passwords eller andet som kan falde
tilbage og kompromitere vores maskiner og andre kunder.


og så er vi tilbage ved det jeg startede med at sige. Der er
"næsten sikkert" (man har virkeligt gjort et forsøg på at få en optimal
sikkerhed og kun uforudsete ting kan ændre på denne sikkerhed -
algoritmens sikkerhed brydes)
"Ikke sikker" (man har sørget for en del sikkerhed men den er langt fra
i top. En fejl og så er de fleste personers sikkerhed totalt
kompromiteret - pga. menneskets simple måde at huske ting på - ikke
mange svære passwords osv).

Så er det her du(jesper) siger at mit "næsten sikkert" varierer fra
person til person, og ja det må jeg give dig ret i (på trods af at jeg
derved vil sige mig selv imod jfg. tidligere indlæg). Problemet er bare
at folk i langt størstedelen af tilfældende ikke kan klare selv at
skulle tage stilling til hvad der er "sikkert nok" for dem, og hvor
mange ting de i virkeligheden kompromiterer ved at slække på sikkerhede
bare et enkelt sted (S/Key er guds gave til os paranoide sysadms i dette
tilfælde).
Derfor er det jeg altid anbefaler at man hellere bruger en
større/stærkere kryptering alle steder end at man slækker på den uden at
være sikker på hvad man dermed kompromiterer.

Hvad der er sikkert kan jo i mange tilfælde bestemmes ud fra hvad man
har adgang til - mange krypteringsprogrammer har en masse begrænsninger
på den ene eller anden måde. Men er man i tvivl så vælg hellere det
stærkeste.
Hellere paranoid end kompromiteret.


[snip]

> [2] Jeg har altid ment, at folk med PGP-nøgler på 10000 bits nok burde
>
> læse en pixibog om kryptografi, og i det mindste overveje en
> smule, om deres password kan bære at give fuld adgang til en
> 10000bits nøgle.
>
Dem læste jeg mange af som helt lille, da jeg blev lidt ældre overtog
fagliteraturen pladsen på min bogreol.

---

"Christian" <bka@sool.2.dk> writes:

> og så lige en ekstra lille driller, de til de folk som stadigvæk bruger
> Windows (som mig), hvad med den såkaldte NSAKEY - En NSA key i Microsoft OS
> som skulle være i stand til at låse en hvilken som helst IT system som
> bruger Windows, da man ikke kan have at ens produkter vender i mod en selv.

Den teori støttes vist mest af folk med staniolhatte.
Et par folks kommentarer:
<URL:http://www.counterpane.com/crypto-gram-9909.html#NSAKeyinMicrosoftCryptoAPI>
<URL:http://ntbugtraq.ntadvice.com/default.asp?sid=1&pid=47&aid=52>

Ikke at jeg stoler på Microsoft af den grund, der er andre og bedre
grunde til at mistro deres programmer :).
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

On Tue, 29 Oct 2002 23:43:35 +0100
"Jens Axel Søgaard" <usenet@soegaard.net> wrote:
> Sådanne påstande bør altid underbygges med referencer. Hvis det er
> XLS-metoden, du tænker på, når du skriver at AES er "brudt" - ja så
> er meningerne vist delte. Jeg mener ikke, at det er rimeligt at
> anvende den sprogbrug på nuværende tidspunkt.


Der har været endnu en metode på banen ud over XLS. Da jeg er Informatik
ingeniør studerende er jeg vant til at tage til takke med et teoretisk
bevis på et stykke papir, og tager derfor også udmeldelser som disse
seriøse.
Selv om B.S. helst ville mane denne historie i jorden, så vil jeg ikke
give ham ret i at en opdagelse som denne er uvæsentlig og jeg mener
klart at dette giver et tydeligt tegn på at AES kun har kort tid igen
inden den anses som en rimeligt brydbar kryptering lige som RSA.



> Her er et udklip af Bruce Schneiers månedlige nyhedsbrev:

Ja han skriver meget sjov og ballade. Ikke alt er efter min mening helt
seriøst (og ja jeg ved godt at han er en af de "helt store" inde for
kryptering).



--
Kim Schulz - Freelance Development | Men of quality are not afraid of
Email : kim @ schulz.dk | women for equality.
Tlf : 51904262 |

---

Kim Schulz wrote :

> On Tue, 29 Oct 2002 23:43:35 +0100
> "Jens Axel Søgaard" <usenet@soegaard.net> wrote:


> Selv om B.S. helst ville mane denne historie i jorden, så vil jeg ikke
> give ham ret i at en opdagelse som denne er uvæsentlig og jeg mener
> klart at dette giver et tydeligt tegn på at AES kun har kort tid igen
> inden den anses som en rimeligt brydbar kryptering lige som RSA.

kan du uddybe lidt hvad du mener med, at "RAS er rimeligt brydbar" ?


--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

On Tue, 29 Oct 2002 23:52:12 +0100
"Jens Axel Søgaard" <usenet@soegaard.net> wrote:
> Kim Schulz wrote:
>
> > 1) kaosmatematik giver et mere random output end de bedste psoudo
> > random generatorer som findes på markedet - tro det eller lad være!
>
> Hvis udsagner er sandt, er det selvmodsigende.

hvorfor ?



--
Kim Schulz - Freelance Development | If it's Tuesday, this must be
Email : kim @ schulz.dk | someone else's fortune.
Tlf : 51904262 |

---

Kim Schulz <kim@schulz.dk> writes:

> On Tue, 29 Oct 2002 23:52:12 +0100
> "Jens Axel Søgaard" <usenet@soegaard.net> wrote:
> > Kim Schulz wrote:
> >
> > > 1) kaosmatematik giver et mere random output end de bedste psoudo
> > > random generatorer som findes på markedet - tro det eller lad være!
> >
> > Hvis udsagner er sandt, er det selvmodsigende.
>
> hvorfor ?

Fordi en kaosmatematisk baseret tilfældighedsgenerator selv er en
pseudotilfældighedsgenerator, og derfor skulle være mere tilfældig
end sig selv. :)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

[snip]
> Fordi en kaosmatematisk baseret tilfældighedsgenerator selv er en
> pseudotilfældighedsgenerator, og derfor skulle være mere tilfældig
> end sig selv. :)

ok dårlig formulering....
Ved at bruge kaos matematik kan man slippe ud over de problemer som man
har med psoudo RNGere uden at det kommer til at koste hastighed.
Når du arbejder med kaos (eller nær-kaotiske algoritmer) så får du dit
random ud af selve "kaos" delen og du behøver derfor ikke være bundet af
om ens RNG er random "nok".


--
Kim Schulz - Freelance Development | Airplanes are interesting toys but
Email : kim @ schulz.dk | of no military value. -- Marechal
Tlf : 51904262 | Ferdinand Foch, Professor of

---

Kim Schulz <kim@schulz.dk> writes:

> [snip]
> > Fordi en kaosmatematisk baseret tilfældighedsgenerator selv er en
> > pseudotilfældighedsgenerator, og derfor skulle være mere tilfældig
> > end sig selv. :)
>
> ok dårlig formulering....
> Ved at bruge kaos matematik kan man slippe ud over de problemer som man
> har med psoudo RNGere uden at det kommer til at koste hastighed.
> Når du arbejder med kaos (eller nær-kaotiske algoritmer) så får du dit
> random ud af selve "kaos" delen og du behøver derfor ikke være bundet af
> om ens RNG er random "nok".

Bliver problemet så ikke bare om funktionen er kaotisk nok, hvilket
sikkert afhænge af hvor tæt på attraktoren man er eller sådan noget.

Min idé om kaotisk opførsel falder tilbage på Lorentz' attraktor, og
jeg ved ikke hvor god den er som tilfældighedsgenerator. Hvordan
vurderes det - matematisk bevis eller statisktisk analyse?

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

[snip]
> Min idé om kaotisk opførsel falder tilbage på Lorentz' attraktor, og
> jeg ved ikke hvor god den er som tilfældighedsgenerator. Hvordan
> vurderes det - matematisk bevis eller statisktisk analyse?


Matematisk bevis først, men benyttes det i et program til kryptering så
tror jeg ikke du slipper uden om en meget omfattende statistisk analyse
desværre

--
Kim Schulz - Freelance Development | The last vestiges of the old
Email : kim @ schulz.dk | Republic have been swept away.
Tlf : 51904262 | -- Governor Tarkin

---

Christian wrote:

> Note.. Jeg ved ikke helt om den skulle hører hjemme her i dk.videnskab eller
> de.sikkerhed,

Eller i dk.politik. (hvis de ellers kunne holde en pause fra at
diskutere indvandring og terror).

Implementeringen af EU's Infosoc direktiv i Dansk lov er på vej til at
gøre hele grupper af krypteringsteknologi ulovligt.

http://www.digitalforbruger.dk/

- I opfordres til at skrive under på protesten.

Peter

---

[snip]
> kan du uddybe lidt hvad du mener med, at "RAS er rimeligt brydbar" ?

Idag er der en masse ting der skal tages højde for, for at RSA (ikke
RAS) kan kaldes for sikker. Nøglen skal selvfølgelig være tilstrækkelig
stor (4000+) og så er valg af primtal altafgørende.
Det er f.eks. enormt vigtigt at primtallene der findes er stærke primtal
og ikke bare almindelige primtal - det er ikke sjældent jeg støder på
RSA implementationer der ikke tager højde for dette.
Er de ikke stærke, så vil du kunne bryde den i polynomisk tid (hvis jeg
ikke huske helt forkert), frem for en tid som svarer til bruteforce.



--
Kim Schulz - Freelance Development | Anybody can win, unless there
Email : kim @ schulz.dk | happens to be a second entry.
Tlf : 51904262 |

---

Kim Schulz wrote :

> [snip]
>> kan du uddybe lidt hvad du mener med, at "RAS er rimeligt brydbar" ?
>
> Idag er der en masse ting der skal tages højde for, for at RSA (ikke
> RAS) kan kaldes for sikker. Nøglen skal selvfølgelig være
> tilstrækkelig stor (4000+)

Jeg antager, at du taler om bit-størelsen ... men hvor har du fra, at
den skal være på +4000bits ? Er den krævede nøglelængde ikke længere
direkte afhængig af, hvad - eller imod hvem - den skal beskytte ?

> og så er valg af primtal altafgørende.
> Det er f.eks. enormt vigtigt at primtallene der findes er stærke
> primtal og ikke bare almindelige primtal - det er ikke sjældent jeg
> støder på RSA implementationer der ikke tager højde for dette.

Men det betyder jo ikke, at RSA er usikker. Dit argument svarer til, at
jeg siger at RSA ikke er sikker, for hvis man bruger primtallene 3 og 5,
for "så tager det ikke lang tid at knække". At du så har gennemlæst nogle
implementeringer af RSA, der var lavet med hovedet under armen, betyder
jo ikke at selve systemet er usikkert.

Det underliggende problem/udfordring i RSA er faktorisering af produkter
af primtal. Dette er ikke ladsiggøreligt i polymiel tid - med mindre
primtallene ikke er udvalgt med omhu, så de fx ikke er stærke.

> Er de ikke stærke, så vil du kunne bryde den i polynomisk tid (hvis
> jeg ikke huske helt forkert), frem for en tid som svarer til
> bruteforce.

det er principielt ikke helt det samme. At en algoritme er polynomiel vil
sige, at "køretiden" ved et givet input kan beskrives ved et polynomium.
Klassen herover indeholder typisk algoritmer, der kun kan beskrives ved
en eksponentialfunktion "eller højere". Årsagen til at man skelner
imellem disse "nemme" algoritmer og de andre "svære" algoritmer er vist,
at en polynomiel algoritme med tiden vil blive "indhentet" af udviklingen
af computere, imens dette ikke (nødvendigvis) kan siges om ikke-
polynomielle algoritmer. Typisk vil det faktisk tage (meget) længere tid
at forsøge at faktorisere sig ud af et RSA-problem end ved blot at prøve
sig frem via brute_force. Derfor er ikke-polynomiel ikke altid det samme
som brute_force.



--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

Scripsit Jesper Stocholm <jespers@stocholm.invalid>

> det er principielt ikke helt det samme. At en algoritme er polynomiel vil
> sige, at "køretiden" ved et givet input kan beskrives ved et polynomium.
> Klassen herover indeholder typisk algoritmer, der kun kan beskrives ved
> en eksponentialfunktion "eller højere". Årsagen til at man skelner
> imellem disse "nemme" algoritmer og de andre "svære" algoritmer er vist,
> at en polynomiel algoritme med tiden vil blive "indhentet" af udviklingen
> af computere, imens dette ikke (nødvendigvis) kan siges om ikke-
> polynomielle algoritmer.

Tja.. en algoritme der kører O(n^10) vil vist have lige så svært ved
at blive indhentet som en ægte eksponentiel.

Grunden til at man fokuserer på polynomiel kompleksitet er at det er
en meget robust klasse af problemer - det vil sige at man har meget
vide rammer til at vælge hvordan man måler køretid uden at nogen
problemer skifter status fra polynomielle til ikke-polynomielle. Fx er
det polynomielt løsbare problemer de samme hvad enten man vælger at
definere at køretiden skal være polynomiel på en Turing-maskine med ét
bånd eller på en (hypotetisk) lambdareduktionsmaskine hvor hver
betareduktion tager konstant tid.

Den egenskab får man ikke hvis man i stedet ser på "problemer der kan
løses i tid højst O(n³)" - hvilket ellers ud fra et rent praktisk
synspunkt ville være en bedre tilnærmelse til "problemer hvor man kan
forestille sig store instanser løst på computer".

--
Henning Makholm "Nu kommer han. Kan du ikke høre knallerten?"

---

Henning Makholm wrote :

> Scripsit Jesper Stocholm <jespers@stocholm.invalid>
>
>> det er principielt ikke helt det samme. At en algoritme er polynomiel
>> vil sige, at "køretiden" ved et givet input kan beskrives ved et
>> polynomium. Klassen herover indeholder typisk algoritmer, der kun kan
>> beskrives ved en eksponentialfunktion "eller højere". Årsagen til at
>> man skelner imellem disse "nemme" algoritmer og de andre "svære"
>> algoritmer er vist, at en polynomiel algoritme med tiden vil blive
>> "indhentet" af udviklingen af computere, imens dette ikke
>> (nødvendigvis) kan siges om ikke- polynomielle algoritmer.
>
> Tja.. en algoritme der kører O(n^10) vil vist have lige så svært ved
> at blive indhentet som en ægte eksponentiel.

præcist ... den detalje fik jeg ikke med. Det er klart, at en også meget
afgørende faktor er konstanterne i udtrykkene for kompleksitet/køretid.

> Grunden til at man fokuserer på polynomiel kompleksitet er at det er
> en meget robust klasse af problemer - det vil sige at man har meget
> vide rammer til at vælge hvordan man måler køretid uden at nogen
> problemer skifter status fra polynomielle til ikke-polynomielle. Fx er
> det polynomielt løsbare problemer de samme hvad enten man vælger at
> definere at køretiden skal være polynomiel på en Turing-maskine med ét
> bånd eller på en (hypotetisk) lambdareduktionsmaskine hvor hver
> betareduktion tager konstant tid.

Det kunne jeg ikke have forklaret bedre, mange tak ... :)


--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

On Wed, 30 Oct 2002 13:34:26 +0100, Kim Schulz <kim@schulz.dk> wrote:


>Det er f.eks. enormt vigtigt at primtallene der findes er stærke primtal
>og ikke bare almindelige primtal -

<mode type="idiot" value="on">

Hvad er forskellen på alm. primtal og stærke primtal?

</mode>

--
Sune

---

sune vuorela wrote :

> On Wed, 30 Oct 2002 13:34:26 +0100, Kim Schulz <kim@schulz.dk> wrote:
>
>>Det er f.eks. enormt vigtigt at primtallene der findes er stærke primtal
>>og ikke bare almindelige primtal -
>
> <mode type="idiot" value="on">
> Hvad er forskellen på alm. primtal og stærke primtal?
> </mode>

primtal (p) kan inddeles i "klasser" alt efter om fx (p-1) kun har små
faktorer, om de kun har nogle enkelte store faktorer eller lignende. Mange
af de metoder man har fundet på til faktorisering indebærer på en eller
anden måde, at man udnytter disse ting.



--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

"Jesper Stocholm" <jespers@stocholm.invalid> wrote in message
news:Xns92B85AEF429F6spamstocholmdk@130.226.1.34...

> primtal (p) kan inddeles i "klasser" alt efter om fx (p-1) kun har små
> faktorer, om de kun har nogle enkelte store faktorer eller lignende. Mange
> af de metoder man har fundet på til faktorisering indebærer på en eller
> anden måde, at man udnytter disse ting.

Ikke at jeg har nogen kilde at referere til, men på min arbejdsplads er det
"folklore" at ved store primtal (mindst 1024 bit, eller sådan noget) giver
det *ingen* sikkerhed at vælge stærke primtal fremfor bare primtal.


Mvh. Bjarke

---

Bjarke Dahl Ebert wrote :

> "Jesper Stocholm" <jespers@stocholm.invalid> wrote in message
> news:Xns92B85AEF429F6spamstocholmdk@130.226.1.34...
>
>> primtal (p) kan inddeles i "klasser" alt efter om fx (p-1) kun har
>> små faktorer, om de kun har nogle enkelte store faktorer eller
>> lignende. Mange af de metoder man har fundet på til faktorisering
>> indebærer på en eller anden måde, at man udnytter disse ting.
>
> Ikke at jeg har nogen kilde at referere til, men på min arbejdsplads

Hvor arbejder du henne (ren interesse) ?

> er det "folklore" at ved store primtal (mindst 1024 bit, eller sådan
> noget) giver det *ingen* sikkerhed at vælge stærke primtal fremfor
> bare primtal.



Lagde du mærke til, at udsagnet som "Jeg mener, at RSA ikke er sikker
nok, men jeg har ingen kilde at referere til" var selve årsagen til, at
denne tråd blev så lang ?

Kan du kvalificere lidt, hvad du mener med, at det giver "ingen
sikkerhed" ?


Lad mig bare komme med et enkelt eksempel på, hvad jeg mener:

Hvis du vælger primtal p,q til udregning af pq til brug i RSA, hvor p-1
kun har "små" rødder, så kan jeg pudse Pollard's P-1 metode på den og
faktorisere nq i polynomiel tid [1]. Det kan godt være, at I på din
arbejdsplads er ligeglade med dette, men personligt ville jeg bruge lidt
mere tid på at finde et "godt" primtal og så sikre mig imod denne
faktorisering. Tilsvarende er der andre faktoriseringsalgortimer, der
udelukkende virker, hvis p har andre karakteristika.

[1] Kompleksiteten af algoritmen er iflg Stinson:
O(B*log(B)*(log(n))^2+(log(n))^3),
hvor B er den største faktor i p-1

--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

"Jesper Stocholm" <jespers@stocholm.invalid> wrote in message
news:Xns92B8DBCC643C1spamstocholmdk@130.226.1.34...
> > Ikke at jeg har nogen kilde at referere til, men på min arbejdsplads
> Hvor arbejder du henne (ren interesse) ?

Cryptomathic i Århus.

> > er det "folklore" at ved store primtal (mindst 1024 bit, eller sådan
> > noget) giver det *ingen* sikkerhed at vælge stærke primtal fremfor
> > bare primtal.
> Kan du kvalificere lidt, hvad du mener med, at det giver "ingen
> sikkerhed" ?

At når antal bits er "stort nok", så bidrager det ikke væsentligt til
sikkerheden i en RSA-nøgle at vælge p og q som stærke primtal.
Det at tillade svage primtal øger jo også effektivt nøglerummets størrelse,
idet der er
mange flere mulige valg af p og q.

> Lad mig bare komme med et enkelt eksempel på, hvad jeg mener:
> Hvis du vælger primtal p,q til udregning af pq til brug i RSA, hvor p-1
> kun har "små" rødder, så kan jeg pudse Pollard's P-1 metode på den og

Det er også overordentligt usandsynligt at p-1 *kun* har små faktorer.

Du kan jo også give dig til at checke om din tilfældige DES-nøgle er
0x0000000000000000, for den er altså ikke specielt god - den kan man gætte!


Men som sagt - jeg kender ikke nok til teorien selv, men jeg stoler på dem
der siger at pq er "svær nok" at faktorisere, selvom p og q ikke vælges som
stærke primtal.


> faktorisere nq i polynomiel tid [1]. Det kan godt være, at I på din
> arbejdsplads er ligeglade med dette, men personligt ville jeg bruge lidt
> mere tid på at finde et "godt" primtal og så sikre mig imod denne
> faktorisering.

Vi kan skam også levere stærke primtal i spandevis. Eller var det noget med
elliptiske kurver?
Om man skal bruge stærke primtal, eller blot primtal, afhænger selvfølgelig
af hvad de skal bruges til.


Mvh. Bjarke

---

Bjarke Dahl Ebert wrote :

> "Jesper Stocholm" <jespers@stocholm.invalid> wrote in message
> news:Xns92B8DBCC643C1spamstocholmdk@130.226.1.34...
>> > Ikke at jeg har nogen kilde at referere til, men på min
>> > arbejdsplads
>> Hvor arbejder du henne (ren interesse) ?
>
> Cryptomathic i Århus.
>
>> > er det "folklore" at ved store primtal (mindst 1024 bit, eller
>> > sådan noget) giver det *ingen* sikkerhed at vælge stærke primtal
>> > fremfor bare primtal.
>> Kan du kvalificere lidt, hvad du mener med, at det giver "ingen
>> sikkerhed" ?
>
> At når antal bits er "stort nok", så bidrager det ikke væsentligt til
> sikkerheden i en RSA-nøgle at vælge p og q som stærke primtal.
> Det at tillade svage primtal øger jo også effektivt nøglerummets
> størrelse, idet der er mange flere mulige valg af p og q.

præcist ... og så indgår det i en konkret vurdering af det nødvendige
sikkerhedsniveau - altså om man synes at det ekstra arbejde det trods alt
tager at finde "stærke" primtal eller lignede, bliver opvejet af den
ekstra sikkerhed det giver. Så er vi tilbage i eksemplet med kæresten og
Osama [1]

>> Lad mig bare komme med et enkelt eksempel på, hvad jeg mener:
> > Hvis du vælger primtal p,q til udregning af pq til brug i RSA, hvor
> > p-1
>> kun har "små" rødder, så kan jeg pudse Pollard's P-1 metode på den og
>
> Det er også overordentligt usandsynligt at p-1 *kun* har små faktorer.

ja, men det kan du jo ikke vide før du checker det :)

> Du kan jo også give dig til at checke om din tilfældige DES-nøgle er
> 0x0000000000000000, for den er altså ikke specielt god - den kan man
> gætte!

hehe

> Men som sagt - jeg kender ikke nok til teorien selv, men jeg stoler på
> dem der siger at pq er "svær nok" at faktorisere, selvom p og q ikke
> vælges som stærke primtal.

Det er klart, at det at faktorisere ikke er "nemt" ... under nogen
omstændigheder. Omend primtallene er stærke eller svage - så vil det
alligevel tage umindelige tider at faktorisere produkter imellem dem -
uanset om man har en supercomputer eller en PII 266 som jeg sidder ved
lige nu. Min oprindelige anke var, at Kim (der siden er diffunderet ?)
konsekvent påstod at RSA ikke var "sikker nok" - men uden at kunne
konkretisere, hvad "sikker nok" betød. Det skyldtes måske, at han
samtidig vedblev at sige, at sikkerhed var sort/hvidt ... og så er det jo
lidt svært at definere "sikker nok".

>> faktorisere nq i polynomiel tid [1]. Det kan godt være, at I på din
>> arbejdsplads er ligeglade med dette, men personligt ville jeg bruge
>> lidt mere tid på at finde et "godt" primtal og så sikre mig imod
>> denne faktorisering.
>
> Vi kan skam også levere stærke primtal i spandevis. Eller var det
> noget med elliptiske kurver?

Det ved jeg, jeg har faktisk for et par år siden brugt en dims på jeres
hjemmeside, der kunne lave elliptiske kurver ... eller kunne den blot
verificere en elliptisk kurve ? Jeg spurgte også engang (lidt i sjov) en
af jeres konsulenter til en konference i IDA om computersikkerhed, om
hvad et stærkt primtal på 10000 bits kostede ... hun blev faktisk
fornærmet over det.



> Om man skal bruge stærke primtal, eller blot primtal, afhænger
> selvfølgelig af hvad de skal bruges til.

nemmerlig !

[1] <Xns92B79B87D3A72spamstocholmdk@130.226.1.34>

--
Jesper Stocholm
http://stocholm.dk
Bahelorprojekt om digitale signaturer baseret på elliptiske kurver:
http://stocholm.dk/pmp

---

Bjarke Dahl Ebert skrev:

>Men som sagt - jeg kender ikke nok til teorien selv, men jeg stoler på dem
>der siger at pq er "svær nok" at faktorisere, selvom p og q ikke vælges som
>stærke primtal.

Hvorfor stoler du mere på dem end på Jesper? Han fremlægger da
argumentation (som godt nok går over min forstand).

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

---

Bertel Lund Hansen wrote :

> Bjarke Dahl Ebert skrev:
>
>>Men som sagt - jeg kender ikke nok til teorien selv, men jeg stoler på
>>dem der siger at pq er "svær nok" at faktorisere, selvom p og q ikke
>>vælges som stærke primtal.
>
> Hvorfor stoler du mere på dem end på Jesper? Han fremlægger da
> argumentation (som godt nok går over min forstand).

mange tak ... :)

Jeg vil godt understrege, at jeg ikke betvivler Bjarkes og (måske
specielt) hans kollegers kompetencer udi kryptografiens kunst [1], og jeg
antager da, at der ligger nogle pragmatiske sikerhedsmæssige overvejelser
bag udsagnet om, at hvis blot primtallene er store nok, så er det
ligemeget om de er stærke eller ej. Jvf den nu strandede diskussion med
hr. Schulz, så slår jeg netop et slag for, at der altid laves en konkret
vurdering af det nødvendige sikkerhedsniveu [2].


[1] Og lad mig i den forbindelse slå et slag for, at Cryptomathic laver
en udviklingsafdeling i det Kjøwenhaunske. Der er altså andre i .dk,
end drengene fra AAU, der arbejder med kryptografi.
:)

[2] Jeg har altid ment, at folk med PGP-nøgler på 10000 bits nok burde
læse en pixibog om kryptografi, og i det mindste overveje en smule,
om deres password kan bære at give fuld adgang til en 10000bits
nøgle.

--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

[snip]
> Jeg antager, at du taler om bit-størelsen ... men hvor har du fra, at
> den skal være på +4000bits ? Er den krævede nøglelængde ikke længere
> direkte afhængig af, hvad - eller imod hvem - den skal beskytte ?

Ja det er bitlængden af den enkelte nøgle, og nej jeg mener ikke at der
idag er noget der hedder "imod hvem man skal beskytte" for enten er man
beskyttet eller også er man ikke.......ellers kan du jo bare bruge
ROT13.



[snip]
> Men det betyder jo ikke, at RSA er usikker. Dit argument svarer til,
> at jeg siger at RSA ikke er sikker, for hvis man bruger primtallene 3
> og 5, for "så tager det ikke lang tid at knække". At du så har
> gennemlæst nogle implementeringer af RSA, der var lavet med hovedet
> under armen, betyder jo ikke at selve systemet er usikkert.

De implementeringer jeg har læst er bl.a. dem som du finder i de større
værker om algoritmer og kryptering som de benytter på DTU.
f.eks. Introduction to algorithms.
Det jeg mener med at RSA idag ikke mere er sikker, er fordi der er
fundet så utroligt mange måder at bryde den ned i dele og derved bryde
dem. Dette betyder at man skal bruge nøgler som er enormt store - en
ting som tager lang tid og derved gør det ubrugeligt i flere sammenhæng
(f.eks. internet kryptering af linje data).



> Det underliggende problem/udfordring i RSA er faktorisering af
> produkter af primtal. Dette er ikke ladsiggøreligt i polymiel tid -
> med mindre primtallene ikke er udvalgt med omhu, så de fx ikke er
> stærke.
Problemet er bare at finde stærke primtal i de størrelsesordenenr som
man bør bruge idag - altså inde for acceptabel tid.
Og så er der stadig den detalje at RSA implementationer ikke tager højde
for dette (f.eks. den gamle i win95 og i linux tidligere).


> > Er de ikke stærke, så vil du kunne bryde den i polynomisk tid (hvis
> > jeg ikke huske helt forkert), frem for en tid som svarer til
> > bruteforce.
>
> det er principielt ikke helt det samme. At en algoritme er polynomiel
> vil sige, at "køretiden" ved et givet input kan beskrives ved et
> polynomium. Klassen herover indeholder typisk algoritmer, der kun kan
> beskrives ved en eksponentialfunktion "eller højere". Årsagen til at
> man skelner imellem disse "nemme" algoritmer og de andre "svære"
> algoritmer er vist, at en polynomiel algoritme med tiden vil blive
> "indhentet" af udviklingen af computere, imens dette ikke
> (nødvendigvis) kan siges om ikke- polynomielle algoritmer. Typisk vil
> det faktisk tage (meget) længere tid at forsøge at faktorisere sig ud
> af et RSA-problem end ved blot at prøve sig frem via brute_force.
> Derfor er ikke-polynomiel ikke altid det samme som brute_force.

nej de data har jeg fra et projekt jeg lavede på DTU netop om RSA for et
halvt års tid siden.


--
Kim Schulz - Freelance Development | Indifference will certainly be the
Email : kim @ schulz.dk | downfall of mankind, but who
Tlf : 51904262 | cares?

---

Kim Schulz wrote :

> [snip]
>> Jeg antager, at du taler om bit-størelsen ... men hvor har du fra, at
>> den skal være på +4000bits ? Er den krævede nøglelængde ikke længere
>> direkte afhængig af, hvad - eller imod hvem - den skal beskytte ?
>
> Ja det er bitlængden af den enkelte nøgle, og nej jeg mener ikke at der
> idag er noget der hedder "imod hvem man skal beskytte" for enten er man
> beskyttet eller også er man ikke.......ellers kan du jo bare bruge
> ROT13.

præcist ... og derfor mener jeg også, at det er noget vrøvl, at verdenen
er sort/hvid. Hvis formålet med din RSA-implementering er, at du skal
beskytte indholdet af emails imod din kærestes øjne, mener du så ikke det
er overkill at lede efter to stærke primtal på hver 2000 bits ? Hvis du
skal sende en email til Osama om næste angreb på USA, tror du så det er
nok med +++4000 bits nøglelængde ?

> [snip]
>> Men det betyder jo ikke, at RSA er usikker. Dit argument svarer til,
>> at jeg siger at RSA ikke er sikker, for hvis man bruger primtallene 3
>> og 5, for "så tager det ikke lang tid at knække". At du så har
>> gennemlæst nogle implementeringer af RSA, der var lavet med hovedet
>> under armen, betyder jo ikke at selve systemet er usikkert.
>
> De implementeringer jeg har læst er bl.a. dem som du finder i de større
> værker om algoritmer og kryptering som de benytter på DTU.
> f.eks. Introduction to algorithms.

Formålet med bogen du omtaler er IKKE at give ubrydelige algoritmer til
brug i krypteringsalgoritmer. Formålet er at give en introduktion til
forskellige algoritmer, datastrukturer, kompleksitetsudregninger og
lignende. Den bør ikke anvendes som primær referencebog til
implementering af kryptografiske algoritmer. Specielt vigtig i
ovenstående er nok ordet "introduktion".

> Det jeg mener med at RSA idag ikke mere er sikker, er fordi der er
> fundet så utroligt mange måder at bryde den ned i dele og derved bryde
> dem.

Hvilke er disse "utroligt mange måder" ?

Allerede inden AES blev kåret, var alle algoritmer incl Serpent, Rijndahl
og Twofish blevet "brudt" indtil et vist antal runder i algoritmen (vist
nok hhv 4,8 og 6). Men det har ikke betydet, at de deraf er blevet
erklæret for usikre.

> Dette betyder at man skal bruge nøgler som er enormt store - en
> ting som tager lang tid og derved gør det ubrugeligt i flere sammenhæng
> (f.eks. internet kryptering af linje data).

Men du sammenblander tingene. Anvendelighed er ikke det samme som
ubrugelighed ... endsige usikkerhed. Det er klart, at forskellige
algoritmer anvendes bedst forskellige steder, men det er IKKE det samme
som at de er usikre - hvilket du bliver ved med at påstå.

>> Det underliggende problem/udfordring i RSA er faktorisering af
>> produkter af primtal. Dette er ikke ladsiggøreligt i polymiel tid -
>> med mindre primtallene ikke er udvalgt med omhu, så de fx ikke er
>> stærke.
> Problemet er bare at finde stærke primtal i de størrelsesordenenr som
> man bør bruge idag - altså inde for acceptabel tid.

Igen, det er ikke korrekt. Cryptomathic laver så mange, at de sælger af
dem.

>> det er principielt ikke helt det samme. At en algoritme er polynomiel
>> vil sige, at "køretiden" ved et givet input kan beskrives ved et
>> polynomium. Klassen herover indeholder typisk algoritmer, der kun kan
>> beskrives ved en eksponentialfunktion "eller højere". Årsagen til at
>> man skelner imellem disse "nemme" algoritmer og de andre "svære"
>> algoritmer er vist, at en polynomiel algoritme med tiden vil blive
>> "indhentet" af udviklingen af computere, imens dette ikke
>> (nødvendigvis) kan siges om ikke- polynomielle algoritmer. Typisk vil
>> det faktisk tage (meget) længere tid at forsøge at faktorisere sig ud
>> af et RSA-problem end ved blot at prøve sig frem via brute_force.
>> Derfor er ikke-polynomiel ikke altid det samme som brute_force.
>
> nej

hvad mener du med "nej" ? Hvad refererer du til ? Se i øvrigt Hennings
forklaring på p/np,

> de data har jeg fra et projekt jeg lavede på DTU netop om RSA for et
> halvt års tid siden.

fagpakkeprojekt ?

--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

Scripsit Jesper Stocholm <jespers@stocholm.invalid>

> hvad mener du med "nej" ? Hvad refererer du til ? Se i øvrigt Hennings
> forklaring på p/np,

Jeg har ikke forklaret NP for nylig. Det er et ganske andet bæst. Men
faktorisering er (næsten trivielt) NP.

--
Henning Makholm "De er da bare dumme. Det skal du bare sige til dem."

---

Henning Makholm wrote :

> Scripsit Jesper Stocholm <jespers@stocholm.invalid>
>
>> hvad mener du med "nej" ? Hvad refererer du til ? Se i øvrigt Hennings
>> forklaring på p/np,
>
> Jeg har ikke forklaret NP for nylig. Det er et ganske andet bæst. Men
> faktorisering er (næsten trivielt) NP.



sorry ... det var self. <yahbs5cyqm1.fsf@pc-043.diku.dk> jeg tænkte på.

--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

[snip]
> præcist ... og derfor mener jeg også, at det er noget vrøvl, at
> verdenen er sort/hvid. Hvis formålet med din RSA-implementering er, at
> du skal beskytte indholdet af emails imod din kærestes øjne, mener du
> så ikke det er overkill at lede efter to stærke primtal på hver 2000
> bits ? Hvis du skal sende en email til Osama om næste angreb på USA,
> tror du så det er nok med +++4000 bits nøglelængde ?

Nej jeg mener jeg skal bruge en stor nøgle til alt - at være sjusket med
sin sikkerhed er roden til alt ondt.

[snip]

> Formålet med bogen du omtaler er IKKE at give ubrydelige algoritmer
> til brug i krypteringsalgoritmer. Formålet er at give en introduktion
> til forskellige algoritmer, datastrukturer, kompleksitetsudregninger
> og lignende. Den bør ikke anvendes som primær referencebog til
> implementering af kryptografiske algoritmer. Specielt vigtig i
> ovenstående er nok ordet "introduktion".

Ja ok dårligt valg af bogtitel....nå men
Applied cryptography
Security Engineering
Cryptanalysis
[snip]
> Hvilke er disse "utroligt mange måder" ?

Alt efter hvor i talrækken dine primtal ligger, så er der forskellige
metoder til at faktorisere dem hurtigere. Stærke vs. svage primtal.


[snip]
> Men du sammenblander tingene. Anvendelighed er ikke det samme som
> ubrugelighed ... endsige usikkerhed.

jo hvis man som jeg ikke mener at det er ok at slække på sikkerheden.


> Det er klart, at forskellige
> algoritmer anvendes bedst forskellige steder, men det er IKKE det
> samme som at de er usikre - hvilket du bliver ved med at påstå.

Ja netop fordi jeg mener der er 2 former for sikkerhed "næsten sikkert"
og "ingen sikkerhed" - og ja det er sort/hvidt men historie viser gang
på gang at det er sådan. Selv om vi tror vi er supersmarte og det vi
bruger er sikkert, så er der intet i vejen for at en eller anden
efterretningstjeneste sidder med en genial faktoriseringsalgoritme som
de så bare ikke er kommet frem med (læs f.eks. NSA papire fra omkring
'60-'75 og du vil se at enorme mængder faktoriserings teorier er
hemmeligstemplet den dag idag - noget de kun er hvis det er "til fare
for usa" at de blever offentliggjort). Kald mig bare paranoid, men hey!
better safe than sorry.

[snip]
> Igen, det er ikke korrekt. Cryptomathic laver så mange, at de sælger
> af dem.
ja men hvorfor mon der er et marked for det? netop fordi det ikke er
rimeligt at lave på en almindelig computer.



[snip]
> Se i øvrigt Hennings forklaring på p/np,
yep den ligner lidt en oversættelse af Helen Gains beskrivelse - bare
oversat.

> > de data har jeg fra et projekt jeg lavede på DTU netop om RSA for et
> > halvt års tid siden.
>
> fagpakkeprojekt ?

Nej specialprojekt (3ugers) hos Tom.


--
Kim Schulz - Freelance Development | The gent who wakes up and finds
Email : kim @ schulz.dk | himself a success hasn't been
Tlf : 51904262 | asleep.

---

Kim Schulz wrote :

>> præcist ... og derfor mener jeg også, at det er noget vrøvl, at
>> verdenen er sort/hvid. Hvis formålet med din RSA-implementering er, at
>> du skal beskytte indholdet af emails imod din kærestes øjne, mener du
>> så ikke det er overkill at lede efter to stærke primtal på hver 2000
>> bits ? Hvis du skal sende en email til Osama om næste angreb på USA,
>> tror du så det er nok med +++4000 bits nøglelængde ?
>
> Nej jeg mener jeg skal bruge en stor nøgle til alt - at være sjusket
> med sin sikkerhed er roden til alt ondt.

Hvad er "sikkerhed" for dig ? Ude i den virkelige verden er sikkerhed en
relativ størrelse, og den hænges ikke altid på på, hvor store computere NSA
på et givet tidpunkt har. Hvis jeg bad dig om at implementere en løsning
med RSA, hvor stor ville du anbefale nøglestørrelsen ... og hvorfor ?

>> Formålet med bogen du omtaler er IKKE at give ubrydelige algoritmer
>> til brug i krypteringsalgoritmer. Formålet er at give en introduktion
>> til forskellige algoritmer, datastrukturer, kompleksitetsudregninger
>> og lignende. Den bør ikke anvendes som primær referencebog til
>> implementering af kryptografiske algoritmer. Specielt vigtig i
>> ovenstående er nok ordet "introduktion".
>
> Ja ok dårligt valg af bogtitel....nå men
> Applied cryptography
> Security Engineering
> Cryptanalysis
> [snip]
>> Hvilke er disse "utroligt mange måder" ?
>
> Alt efter hvor i talrækken dine primtal ligger, så er der forskellige
> metoder til at faktorisere dem hurtigere. Stærke vs. svage primtal.

Hurtigere end hvad ? Prøv at nævne nogle af disse metoder.

> [snip]
>> Men du sammenblander tingene. Anvendelighed er ikke det samme som
>> ubrugelighed ... endsige usikkerhed.
>
> jo hvis man som jeg ikke mener at det er ok at slække på sikkerheden.

Du misser min pointe. Det er ikke en god idé at anvende RSA med 4000bits
nøgle til at sikre en streamet videokonference, da RSA her ikke er gearet
til denne performance. Men det betyder ikke, at man så skal anvende RSA med
20bits nøgler - men at man skal anvende en anden algoritme.

>> Det er klart, at forskellige
>> algoritmer anvendes bedst forskellige steder, men det er IKKE det
>> samme som at de er usikre - hvilket du bliver ved med at påstå.
>
> Ja netop fordi jeg mener der er 2 former for sikkerhed "næsten sikkert"
> og "ingen sikkerhed" -

Det vil sige, at alle algoritmer er usikre ? Hvordan vil du kvalificere
"næsten sikkert" ?

[snip en masse vrøvl, der ikke er relevant i denne tråd, der kan i stedet
fortsættes i alt.conspiracy]

> [snip]
>> Igen, det er ikke korrekt. Cryptomathic laver så mange, at de sælger
>> af dem.
> ja men hvorfor mon der er et marked for det? netop fordi det ikke er
> rimeligt at lave på en almindelig computer.

hvad er din pointe ? Og hvorfor er det ikke rimeligt at forsøge at lave
primtal på almindelige computere ? Problemet med at lave primtal er jo ikke
processor-kraften men derimod implementeringen af algoritmerne. Det er
dette, der er det svære - og det er derfor Cryptomathic kan sælge primtal

> [snip]
>> Se i øvrigt Hennings forklaring på p/np,
> yep den ligner lidt en oversættelse af Helen Gains beskrivelse - bare
> oversat.
>
>> > de data har jeg fra et projekt jeg lavede på DTU netop om RSA for et
>> > halvt års tid siden.
>>
>> fagpakkeprojekt ?
>
> Nej specialprojekt (3ugers) hos Tom.

....

Som du nok kan fornemme, så giver jeg ikke meget for dine argumenter. Du
startede med at sige, at RSA var "rimeligt brydbar" og argumenterer for
dette med, at der er mange, der ikke kan finde ud af at implementere
systemet korrekt samt at det ikke er alle, der bruger de korrekte primtal
til det. Så fortsætter du med at fortælle, at RSA er usikkert, da det ikke
kan bruges til kryptering af liniedata.

Hvis du nu går op og snakker med Tom Høholdt igen - eller Lars R. Knudsen,
så vil de fortælle dig, at det grundliggende problem i RSA er faktorisering
af primtalsprodukter (punktum). Styrken i RSA har intet at gøre med om du
engang har set et system, hvor det var lavet dårligt. Det har heller ikke
noget at gøre med, om du synes det går langsomt, når du krypterer streaming
video med det. Dette er tilgangen, der anvendes, når man som kryptograf
undersøger en algoritme. Her anvendes altid worst-case betragtninger, og
ikke om "RSA kan brydes, hvis det ene primtal vælges som 3".

Det er klart, at anvendelsen af RSA er begrænset af, at
dekryptering/kryptering går relativt langsomt pga modularmatematikken og
opløftninger af meget store tal til andre meget store tal. Det er også
klart, at der findes andre krypteringsalgoritmer, der anvender mindre
nøgler. Alt dette er dog ligemeget, når man taler om sikkerheden af selve
systemet. Her er det nemlig den underliggende algoritme/det underliggende
problem, der undersøges. Det vil sige, at det i tilfældet RSA er
faktorisering, i tilfældet ElGamal er diskrete logaritmer og ECC-digitale
signaturer er den specielle afart af disse, der er diskrete logaritmer i
talmængder, på randen af en elliptisk kurve.

Den generelle antagelse i kryptografiske kredse er, at faktorisering er
svært. Hvis du har nogle indikationer på, at det skulle forholde sig
anderledes, så er jeg sikker på, at der findes en medalje af en eller anden
art og venter på dig.

--
Jesper Stocholm
http://stocholm.dk
Midtvejsprojekt om digitale signaturer vha Elliptisk kurve kryptografi
http://stocholm.dk/pmp

---

Kim Schulz skrev:

>Nej jeg mener jeg skal bruge en stor nøgle til alt - at være sjusket med
>sin sikkerhed er roden til alt ondt.

At tage bevidst stilling til et behov er ikke at sjuske. Min
fordør er f.eks. ikke lavet af metertykt panserstål med urstyret
lukkemekanisme. Skulle jeg så have sat min sikkerhed over styr?

>Ja netop fordi jeg mener der er 2 former for sikkerhed "næsten sikkert"
>og "ingen sikkerhed"

Der tager du fejl.

>på gang at det er sådan. Selv om vi tror vi er supersmarte og det vi
>bruger er sikkert, så er der intet i vejen for at en eller anden
>efterretningstjeneste sidder med en genial faktoriseringsalgoritme som
>de så bare ikke er kommet frem med

Hvordan skulle en 4'000-bits nøgle garantere mod den slags?

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

---

[snip]
> Hvad er "sikkerhed" for dig ? Ude i den virkelige verden er sikkerhed
> en relativ størrelse, og den hænges ikke altid på på, hvor store
> computere NSA på et givet tidpunkt har. Hvis jeg bad dig om at
> implementere en løsning med RSA, hvor stor ville du anbefale
> nøglestørrelsen ... og hvorfor ?


sikkerhed for mig er en garanti for at ingen kan læse det jeg krypterer
- i hvert fald imens jeg lever.
nøglelængde, tjaa 4000bit har jeg jo sagt tidligere. Dette fordi du
ellers vil kunne faktorisere den inde for en menneskealder med de
maskiner vi har idag (og som kommer fremover).

[snip]

> Hurtigere end hvad ? Prøv at nævne nogle af disse metoder.

Hurtigere end standard faktorisering... Har ikke lige noterne ved
hånden, så navne og beskrivelse må jeg lige skylde dig til en anden
gang.
[snip]
> Du misser min pointe. Det er ikke en god idé at anvende RSA med
> 4000bits nøgle til at sikre en streamet videokonference, da RSA her
> ikke er gearet til denne performance. Men det betyder ikke, at man så
> skal anvende RSA med 20bits nøgler - men at man skal anvende en anden
> algoritme.

Ja og så er vi tilbage til det som det hele startede med - nemlig andre
algoritmer end AES.

> >> Det er klart, at forskellige
> >> algoritmer anvendes bedst forskellige steder, men det er IKKE det
> >> samme som at de er usikre - hvilket du bliver ved med at påstå.

Nej og det har jeg vist heller aldrig sagt. Jeg siger bare at hvis du
ikke bruger en stor nøgle så vil du have problemet med at det du
krypterer ikke er sikkert nok (jfg. min beskrivelse tidligere).



> Det vil sige, at alle algoritmer er usikre ? Hvordan vil du
> kvalificere "næsten sikkert" ?

Se beskrivelse af "sikkert" tidligere

> [snip en masse vrøvl, der ikke er relevant i denne tråd, der kan i
> stedet fortsættes i alt.conspiracy]

Måske, måske ikke! Vrøvl vil jeg ikke gå med til at du kalder det.



[snip]
> hvad er din pointe ? Og hvorfor er det ikke rimeligt at forsøge at
> lave primtal på almindelige computere ?

Vi lavede en ret hurtig implementering af en algoritme til at finde
meget store stærke primtal. For at kunne garantere at man havde med et
stærkt primtal at gøre, så ville det kræve at den tyggede lang tid på
tallet (måske et døgn på f.eks. erlang). Det ville jeg ikke mene at
almindelige folk skulle gøre - derfor mener jeg at der er salg i dem.


> Problemet med at lave primtal
> er jo ikke processor-kraften men derimod implementeringen af
> algoritmerne. Det er dette, der er det svære - og det er derfor
> Cryptomathic kan sælge primtal

selv de hurtigste algoritmer har enten slækket på garantien for at den
laver stærke primtal eller også så bruger den stadig meget lang tid.


[snip]
> Som du nok kan fornemme, så giver jeg ikke meget for dine argumenter.
tjaa

> Du startede med at sige, at RSA var "rimeligt brydbar" og argumenterer
> for dette med, at der er mange, der ikke kan finde ud af at
> implementere systemet korrekt samt at det ikke er alle, der bruger de
> korrekte primtal til det.

Nej jeg pointerede at der er flere af de implementationer (og steder
hvorfra man normalt får mange algoritmer til dette) som ikke var
kritiske nok over for de fundne primtal. Folk regner ofte med at det
program som de nu engang er sikkert, men det viser sig ofte at dette er
en falsk trykhed.

> Så fortsætter du med at fortælle, at RSA er
> usikkert, da det ikke kan bruges til kryptering af liniedata.

hvilket du jo også gav mig ret i. Der findes mange algoritmer til
kryptering af linjedata, men ofte er fællesnævneren at de er noget mere
usikre end andre algoritmer fordi de skal kunne arbejde så hurtigt.


> Hvis du nu går op og snakker med Tom Høholdt igen - eller Lars R.
> Knudsen, så vil de fortælle dig, at det grundliggende problem i RSA er
> faktorisering af primtalsprodukter (punktum).

Jeg havde flere lange samtaler med Tom om dette, og generelt så var hans
holdning (som jeg forstår den) at RSA var en så gennemarbejdet algoritme
at det var tid til at finde en ny og bedre - f.eks. AES, som han dog var
noget urolig for pga. de fund de havde lavet på det der indiske
universitet.
Er lars ikke smuttet til Norge igen?

> Styrken i RSA har intet
> at gøre med om du engang har set et system, hvor det var lavet
> dårligt. Det har heller ikke noget at gøre med, om du synes det går
> langsomt, når du krypterer streaming video med det. Dette er
> tilgangen, der anvendes, når man som kryptograf undersøger en
> algoritme. Her anvendes altid worst-case betragtninger, og ikke om
> "RSA kan brydes, hvis det ene primtal vælges som 3".


> Det er klart, at anvendelsen af RSA er begrænset af, at
> dekryptering/kryptering går relativt langsomt pga modularmatematikken
> og opløftninger af meget store tal til andre meget store tal.

selfølgelig.


> Det er
> også klart, at der findes andre krypteringsalgoritmer, der anvender
> mindre nøgler. Alt dette er dog ligemeget, når man taler om
> sikkerheden af selve systemet. Her er det nemlig den underliggende
> algoritme/det underliggende problem, der undersøges.

Ja og jeg vil stadig påstå at faktorisering ikke mere er et problem som
giver nok sikkerhed.



> Det vil sige, at
> det i tilfældet RSA er faktorisering, i tilfældet ElGamal er diskrete
> logaritmer og ECC-digitale signaturer er den specielle afart af disse,
> der er diskrete logaritmer i talmængder, på randen af en elliptisk
> kurve.

yep yep


> Den generelle antagelse i kryptografiske kredse er, at faktorisering
> er svært. Hvis du har nogle indikationer på, at det skulle forholde
> sig anderledes, så er jeg sikker på, at der findes en medalje af en
> eller anden art og venter på dig.

Næppe, med mindre du virkeligt har gjort noget som klarer det nær
realtime. Der har for nogen tid siden været store diskussioner i noget
af alt.crypt grupperne (mener det var i dem) om hvor vidt faktorisering
vs. primtal i virkeligheden giver den sikkerhed som man regner med.
Noget med at man skulle faktorisere ud fra midten i stedet for fra
bunden af (den konkrete algoritme blev ikke skrevet). Dette giver en
udelukkelse af små faktorer som med stor sandsynlighed ikke bliver brugt
alligevel.



--
Kim Schulz - Freelance Development | I want to dress you up as TALLULAH
Email : kim @ schulz.dk | BANKHEAD and cover you with
Tlf : 51904262 | VASELINE and WHEAT THINS ...

---

Kim Schulz wrote :

> [snip]
>> Hvad er "sikkerhed" for dig ? Ude i den virkelige verden er sikkerhed
>> en relativ størrelse, og den hænges ikke altid på på, hvor store
>> computere NSA på et givet tidpunkt har. Hvis jeg bad dig om at
>> implementere en løsning med RSA, hvor stor ville du anbefale
>> nøglestørrelsen ... og hvorfor ?
>
>
> sikkerhed for mig er en garanti for at ingen kan læse det jeg krypterer
> - i hvert fald imens jeg lever.

Her vurderer du, at der nok ikke er nogen, der kan bryde systemet med denne
nøglelængde. I det ligger der jo også en vurdering af de tekniske
muligheder for de mennesker, der kunne have interesse i at bryde det ...
og dermed siger du også, at sikkerhed ikke er sort/hvidt - men altid beror
på en vurdering af det aktuelle "trusselsbillede". Dette er i direkte
modstrid til hvad du tidligere har sagt om at sikkerhed er s/h. Nu siger du
jo selv, at du _vurdererer_ at med 4000bits nøgler er du garanteret, at
ingen kan bryde det.

> nøglelængde, tjaa 4000bit har jeg jo sagt tidligere. Dette fordi du
> ellers vil kunne faktorisere den inde for en menneskealder med de
> maskiner vi har idag

> (og som kommer fremover).

En mand sagde vist engang, at "nu er alt, hvad der kan opfindes nogensinde,
blevet opfundet".

>> Hurtigere end hvad ? Prøv at nævne nogle af disse metoder.
>
> Hurtigere end standard faktorisering... Har ikke lige noterne ved
> hånden, så navne og beskrivelse må jeg lige skylde dig til en anden
> gang.

Jeg kan da nævne et par stykker for dig (fra Stinson):

General Number Field Sieve
Quadratic Sieve
Elliptic Curve algorithm

Fælles for alle disse algoritmer er, at der findes specielle tilfælde, hvor
de kan faktorisere i nær-polynomiel tid ... men realistisk er de ikke meget
hurtigere end trial division. Forskellen imellem disse er så vidt jeg kan
forstå den asymptotiske køretid.

>> >> Det er klart, at forskellige
>> >> algoritmer anvendes bedst forskellige steder, men det er IKKE det
>> >> samme som at de er usikre - hvilket du bliver ved med at påstå.
>
> Nej og det har jeg vist heller aldrig sagt.

Du skrev i <20021030133426.036cd6bd.kim@schulz.dk>

[...]Idag er der en masse ting der skal tages højde for, for at RSA [] kan
kaldes for sikker. Nøglen skal selvfølgelig være tilstrækkelig
stor (4000+) og så er valg af primtal altafgørende. [...]

Dette er jo fundamentalt intetsigende. Hvis dette er kriteriet, så er der
jo ingen algoritmer, der kan bruges til noget. Du vil altid kunne give en
krypto-algoritme input, der bevirker at output ikke kan bruges til noget
som helst. Derfor er der intet indhold i dit udsagn

> Jeg siger bare at hvis du
> ikke bruger en stor nøgle så vil du have problemet med at det du
> krypterer ikke er sikkert nok (jfg. min beskrivelse tidligere).
>
>> Det vil sige, at alle algoritmer er usikre ? Hvordan vil du
>> kvalificere "næsten sikkert" ?
>
> Se beskrivelse af "sikkert" tidligere

øeh ... kan du ikke skrive det igen ? Jeg er ikke sikker på, hvad du
henviser til.

>> [snip en masse vrøvl, der ikke er relevant i denne tråd, der kan i
>> stedet fortsættes i alt.conspiracy]
>
> Måske, måske ikke! Vrøvl vil jeg ikke gå med til at du kalder det.

jaja ... det er i hvert fald ikke synderligt relevant.

>> Problemet med at lave primtal
>> er jo ikke processor-kraften men derimod implementeringen af
>> algoritmerne. Det er dette, der er det svære - og det er derfor
>> Cryptomathic kan sælge primtal
>
> selv de hurtigste algoritmer har enten slækket på garantien for at den
> laver stærke primtal eller også så bruger den stadig meget lang tid.

Hvilke referencer kan du give til dette ? Jeg går ud fra, at det ikke blot
er noget du slynger ud af ærmet.

>> Du startede med at sige, at RSA var "rimeligt brydbar" og argumenterer
>> for dette med, at der er mange, der ikke kan finde ud af at
>> implementere systemet korrekt samt at det ikke er alle, der bruger de
>> korrekte primtal til det.
>
> Nej jeg pointerede at der er flere af de implementationer (og steder
> hvorfra man normalt får mange algoritmer til dette) som ikke var
> kritiske nok over for de fundne primtal. Folk regner ofte med at det
> program som de nu engang er sikkert, men det viser sig ofte at dette er
> en falsk trykhed.

Ja ... men betyder det, at RSA ikke er sikkert ?

>> Så fortsætter du med at fortælle, at RSA er
>> usikkert, da det ikke kan bruges til kryptering af liniedata.
>
> hvilket du jo også gav mig ret i.

Nej, det gav jeg dig ikke ret i. Jeg sagde:

[...]Det er ikke en god idé at anvende RSA med 4000bits
nøgle til at sikre en streamet videokonference, da RSA her ikke er gearet
til denne performance.[...]

Jeg har på intet tidspunkt sagt, at RSA dermed er usikkert. Jeg har sagt,
at RSA ikke er velegnet.

> Der findes mange algoritmer til
> kryptering af linjedata, men ofte er fællesnævneren at de er noget mere
> usikre end andre algoritmer fordi de skal kunne arbejde så hurtigt.

Igen ... hvilke algoritmer er det - og hvorfor er de mere usikre ? AES kan
så vidt jeg er orienteret kan AES eller Serpent fint bruges til kryptering
af realtime datastrømme.

>> Hvis du nu går op og snakker med Tom Høholdt igen - eller Lars R.
>> Knudsen, så vil de fortælle dig, at det grundliggende problem i RSA er
>> faktorisering af primtalsprodukter (punktum).
>
> Jeg havde flere lange samtaler med Tom om dette, og generelt så var hans
> holdning (som jeg forstår den) at RSA var en så gennemarbejdet algoritme
> at det var tid til at finde en ny og bedre - f.eks. AES, som han dog var
> noget urolig for pga. de fund de havde lavet på det der indiske
> universitet.

Jeg tror, at du har misforstået den kære Tom. Det er klart, at RSA har
flere uhensigtsmæssigheder - heriblandt at den er langsom - specielt i
hardware. Jeg tror dog, at hans anke har været, at der nu er andre
algoritmer, der giver det samme sikkerhedsniveau - men med mindre nøgler.
Jeg nægter at tro på, at Tom har sagt noget om, at RSA var usikkert fordi
"faktorisering ikke længere er svært".

> Er lars ikke smuttet til Norge igen?

det ved jeg ikke ... håber da han kommer hjem, så jeg kan skrive
afgangsprojekt ved ham til sommer.

>> Det er
>> også klart, at der findes andre krypteringsalgoritmer, der anvender
>> mindre nøgler. Alt dette er dog ligemeget, når man taler om
>> sikkerheden af selve systemet. Her er det nemlig den underliggende
>> algoritme/det underliggende problem, der undersøges.
>
> Ja og jeg vil stadig påstå at faktorisering ikke mere er et problem som
> giver nok sikkerhed.

Ja, det bliver du ved med ... uden dog at sandsynliggøre, at det forholder
sig således.

>> Den generelle antagelse i kryptografiske kredse er, at faktorisering
>> er svært. Hvis du har nogle indikationer på, at det skulle forholde
>> sig anderledes, så er jeg sikker på, at der findes en medalje af en
>> eller anden art og venter på dig.
>
> Næppe, med mindre du virkeligt har gjort noget som klarer det nær
> realtime.

Det kunne fx være, at P=NP eller lignende. Det skulle nok kunne indbringe
lidt.

> Der har for nogen tid siden været store diskussioner i noget
> af alt.crypt grupperne (mener det var i dem) om hvor vidt faktorisering
> vs. primtal i virkeligheden giver den sikkerhed som man regner med.
> Noget med at man skulle faktorisere ud fra midten i stedet for fra
> bunden af (den konkrete algoritme blev ikke skrevet). Dette giver en
> udelukkelse af små faktorer som med stor sandsynlighed ikke bliver brugt
> alligevel.

Lad mig starte med at sige, at de "rigtige" grupper at snakke kryptografi i
er sci.crypt-grupperne. Det er her folk som Don Johnson (ECC), Bob
Silvermann (RSA), David Wagner samt andre holder til. [1]

Dernæst: Jeg kan forstå, at du har arbejdet med primtalsfremstilling ...
men hvor meget har du arbejdet med faktorisering af tal ? I de algoritmer
jeg har arbejdet med er der ingen "rækkefølge-notation", hvorfor det du
refererer til med "halvdelen og frem" ikke giver umiddelbar mening. Kan du
give et link til diskussionen på fx google ?

[1]
Se i øvrigt en rigtig interessant tråd via
http://makeashorterlink.com/?R2D613942



--
Jesper Stocholm
http://stocholm.dk
Overvejer du at købe bøger ved saxo.dk ? Kig først på
http://www.firmcheck.dk/Info.asp?website=www.saxo.dk

---

On 01 Nov 2002 15:18:22 +0100
Henning Makholm <henning@makholm.net> wrote:
> Scripsit Kim Schulz <kim@schulz.dk>
>
> > 1) kaosmatematik giver et mere random output end de bedste psoudo
> > random generatorer som findes på markedet
>
> Det er selvmodsigende. Hvis "kaosmatematik" er en algoritme som giver
> bedre pseudotilfældige tal en andre pseudotilfældighedsgeneratorer på
> markedet, så *er* "kaosmatematik" dén bedste
> pseudotilfældighedsgenerator på markedet. Det vil sige at din påstand
> er at den er bedre end sig selv, hvilket selvklart er falsk.

Og her vil et normalt tænkende individ straks vide at når man sætter
kaosmatematiske algoritmer op mod psoudogenerator algoritmer, så menes
der selvfølgelig ikke kaotiske algoriter vs. de kaotiske.

---

Kim Schulz wrote :

> On 01 Nov 2002 15:18:22 +0100
> Henning Makholm <henning@makholm.net> wrote:
>> Scripsit Kim Schulz <kim@schulz.dk>
>>
>> > 1) kaosmatematik giver et mere random output end de bedste psoudo
>> > random generatorer som findes på markedet
>>
>> Det er selvmodsigende. Hvis "kaosmatematik" er en algoritme som giver
>> bedre pseudotilfældige tal en andre pseudotilfældighedsgeneratorer på
>> markedet, så *er* "kaosmatematik" dén bedste
>> pseudotilfældighedsgenerator på markedet. Det vil sige at din påstand
>> er at den er bedre end sig selv, hvilket selvklart er falsk.
>
> Og her vil et normalt tænkende individ straks vide at når man sætter
> kaosmatematiske algoritmer op mod psoudogenerator algoritmer, så menes
> der selvfølgelig ikke kaotiske algoriter vs. de kaotiske.

vil du så ikke være sød og formulere dig klart, så der ingen tvivl er om,
hvad du dog mener ?

For det første kan det ikke være rigtigt, at vi skal sidde og gætte på
"hvad mon du reelt siger", og for det andet er denne gruppe dk.videnskab
og ikke dk.folkeeventyr . Tråden er udelukkende blevet så lang fordi du
ikke har formået at forklare kort og præcist, hvad det er du gerne vil
sige. Imo er der nogle implicitte krav om præcision i de udtalelser man
måtte komme med i grupper som dk.videnskab.* ... ellers er
dk.edb.sikkerhed måske mere velvalgt, da indgangsvinklen er mere
pragmatisk dér.



--
Jesper Stocholm
http://stocholm.dk
Ny FAQ for dk.edb.internet.webdesign.serverside.asp
se http://asp-faq.dk

---

Jesper Stocholm wrote:
> Kim Schulz wrote :

>>On 01 Nov 2002 15:18:22 +0100
>>Henning Makholm <henning@makholm.net> wrote:
>>
>>>Scripsit Kim Schulz <kim@schulz.dk>
>>>
>>>>1) kaosmatematik giver et mere random output end de bedste psoudo
>>>>random generatorer som findes på markedet
>>>
>>>Det er selvmodsigende. Hvis "kaosmatematik" er en algoritme som giver
>>>bedre pseudotilfældige tal en andre pseudotilfældighedsgeneratorer på
>>>markedet, så *er* "kaosmatematik" dén bedste
>>>pseudotilfældighedsgenerator på markedet. Det vil sige at din påstand
>>>er at den er bedre end sig selv, hvilket selvklart er falsk.
>>
>>Og her vil et normalt tænkende individ straks vide at når man sætter
>>kaosmatematiske algoritmer op mod psoudogenerator algoritmer, så menes
>>der selvfølgelig ikke kaotiske algoriter vs. de kaotiske.

Så er vi ude over det første problem i påstanden.
Nu mangler vi bare et eksempel på en algoritme konstrueret udfra
"kaosmatematiske" principper. Jeg har stadig ikke gættet, hvilken
algoritme du tænker på.

> For det første kan det ikke være rigtigt, at vi skal sidde og gætte på
> "hvad mon du reelt siger", og for det andet er denne gruppe dk.videnskab
> og ikke dk.folkeeventyr.

Guld.

---

Kim Schulz wrote:
> Og her vil et normalt tænkende individ straks vide at når man sætter
> kaosmatematiske algoritmer op mod psoudogenerator algoritmer, så menes
> der selvfølgelig ikke kaotiske algoriter vs. de kaotiske.

Som et normalt tænkende individ (påstår nogle med urette) vil jeg
definere en optimal random generator som en kilde til en masse
realisationer af uendeligt lang sekvens af tal. Hvis og kun hvis
hirakiet af alle betingede sandsynelighedsfordelinger er konstanter.


Dvs.
P1(x) = konst
P2(x1|x2) = konst
P3(x1,x2|x3) = konst
:

Dvs. i P3 antages x1,x2 antages kendt, og hvad er den betingede
sandsynelighedsfordeling af det næste tal x3 i sekvensen.

Det kan også udtrykkes med at hirakiet af korrelationsfunktioner
af ovenstående sandsynelighedsfordelinger ikke har nogen struktur
udover selvkorrelation. F.eks
C2(n)=<x[i]*x[i+n]> = <x²> kronecker_delta(n) og C3,C4, ..

Fra informationsteori svarer ovenstående definition til at
at entropien af enhver Markov model af informationskilden
er maksimal.

Hvis sandsynelighedsfordelingerne ikke er flade, så kan man
forudsige at visse udfald er mere sandsynelige end andre.
Ingen struktur betyder maksimalt svært at forudsige noget,
dvs. minimal viden om udfaldet, og derfor maksimal entropi
= mest tilfældigt.

For pseudorandom generatorer vil der før eller siden være
struktur i korrelationsfunktionerne/ikke flade sandsynelighedsfordelinger,
fordi sekvensen er deterministisk. Så derfor bør man i
princippet sikre sig at det man bruger pseudorandom tal f.eks.
en Monte Carlo simulation er ufølsomt over for
højordens-korrelationsfunktioner.


For en kaotisk sekvens, vil forskellige realisationer være
ukorrelerede, fordi Lyapunov eksponenten osv., men forskellige
tal i samme sekvens vil ikke nødventigvis være ukorrelerede.

--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk