mboost-dp1
unknown
Skræmmende ved jeg nu ikke om det er. Ikke for undertegnede.
Hvis der skal 100 "computer-år" og 11 måneder til at bryde mit visakort, så er jeg overbevist om, at det vil være mere rentabelt for en forbryder at tjene de småpenge jeg har, ved at sidde et par dage ved kassen i Netto.
Hvis der skal 100 "computer-år" og 11 måneder til at bryde mit visakort, så er jeg overbevist om, at det vil være mere rentabelt for en forbryder at tjene de småpenge jeg har, ved at sidde et par dage ved kassen i Netto.
[url=#50]#50[/url] janus112
Alt dette forudsætter selvfølgelig, at man har en måde at verificere, hvornår man har fundet den rigtige nøgle. Med asymmetrisk kryptering er der altid en måde at verificere det. Med symmetrisk kryptering afhænger det af forholdet mellem størrelserne af nøgle og data. Bruges en one-time pad er nøglen mindst lige så stor som data, og så hjælper brute force ikke. Man kan selvfølgelig stadig brute force sig igennem alle mulighederne, men det er ret meningsløst, da man aldrig ved hvornår man er nået frem til den rigtige.
[url=#51]#51[/url] Hundestejle
jeg tror, uden at være sikker, at designe en algoritme der vilkårlig løser en vilkårlig kryptering er i sig selv uløseligt.Hvis ikke der stilles krav om performance, så er der en simpel løsning på det problem. Den løsning hedder brute force. Det er først når det skal gøres hurtigere en brute force, at det bliver interessant. Der findes allerede en generel kvante algoritme, der er hurtigere end brute force. Den er bare ikke så meget hurtigere, at kryptering er værdiløst. Men det betyder dog, at man skal kryptere med det dobbelte antal bits for at opnå samme sikkerhed.
Alt dette forudsætter selvfølgelig, at man har en måde at verificere, hvornår man har fundet den rigtige nøgle. Med asymmetrisk kryptering er der altid en måde at verificere det. Med symmetrisk kryptering afhænger det af forholdet mellem størrelserne af nøgle og data. Bruges en one-time pad er nøglen mindst lige så stor som data, og så hjælper brute force ikke. Man kan selvfølgelig stadig brute force sig igennem alle mulighederne, men det er ret meningsløst, da man aldrig ved hvornår man er nået frem til den rigtige.
[url=#51]#51[/url] Hundestejle
Hvis der skal 100 "computer-år" og 11 måneder til at bryde mit visakortNej, de er næppe nogen som ønsker at bruge så mange resourcer på et enkelt kreditkort. Men man må ikke glemme, at efterhånden som computere bliver hurtigere vil den nødvendige mængde resourcer falde. Desuden ville et angreb ikke nødvendigvis bliver rettet imod et enkelt kreditkort. Forestil dig, at man brugte angrebet for at fake et website hvor et stort antal brugere gennemfører transaktioner. Udfør beregningen én gang for at beregne nøglen, derefter kan man hijacke så mange sessioner som man gider.
#52
ja selfølgelig. Det jeg mener er, at en algorithme der brute force angriber ethver vilkårlig algoritme findes nok ikke. Der kræves måske en konservativ løsning til hver enkel.
Desuden kan en kvantecomputer ikke beregne mere end en almindelig computer, da det kan vises at en turing maskine kan simulere en kvantecomputer.
ja selfølgelig. Det jeg mener er, at en algorithme der brute force angriber ethver vilkårlig algoritme findes nok ikke. Der kræves måske en konservativ løsning til hver enkel.
Desuden kan en kvantecomputer ikke beregne mere end en almindelig computer, da det kan vises at en turing maskine kan simulere en kvantecomputer.
[url=#53]#53[/url] janus112
do
M=decrypt(C,K)
if correct(M) return K
done
Jeg kender til to teoretiske modeller for beregninger, en Turing maskine og en random access maskine. En Turing maskine kører frem og tilbage på et langt tape, men har i sig selv kun et begrænset antal interne tilstande. Det tager tid at køre frem og tilbage på sådan et tape, og en algoritme kan have brug for at gøre det mange gange. En random access maskine minder mere om den måde en computer faktisk fungerer på, og den vil i de fleste situationer kunne udføre en opgave hurtigere end en Turing maskine.
Det er bevist at problemer der kan løses i polynomiel tid på den ene kan også løses i polynomiel tid på den anden. Men normalt vil polynomiet have højere grad på en Turing maskine end på en random access maskine.
En kvantecomputer kan være endnu hurtigere. Spørgsmålet, som vist ikke er endegyldigt besvaret endnu er, om der er problemer som kan løses i polynomiel tid på en kvantecomputer men ikke på en Turing maskine.
Faktorisering er en kandidat, hvor den bedst kendte algoritme på en kvantecomputer kører i polynomiel tid. Det kan den bedst kendte algoritme på en Turing maskine ikke hamle op med.
Det hænger i øvrigt til dels sammen med spørgsmålet om, hvorvidt P=NP. Så vidt jeg ved vil ethveret problem, der kan løses i polynomiel tid på en kvantecomputer, også kunne løses i polynomielt tid på en nondeterministisk Turing maskine. Men det gælder ikke nødvendigvis den modsatte vej. Der er ingen som har udviklet et NP orakel som en polynomiel kvantealgoritme.
Det jeg mener er, at en algorithme der brute force angriber ethver vilkårlig algoritme findes nok ikke.for K in {0,1}^k
do
M=decrypt(C,K)
if correct(M) return K
done
Desuden kan en kvantecomputer ikke beregne mere end en almindelig computer, da det kan vises at en turing maskine kan simulere en kvantecomputer.Det skal nok passe. Det drejer sig jo ikke om, hvad der kan beregnes, men hvor hurtigt det kan gøres. En Turing maskine er langsom.
Jeg kender til to teoretiske modeller for beregninger, en Turing maskine og en random access maskine. En Turing maskine kører frem og tilbage på et langt tape, men har i sig selv kun et begrænset antal interne tilstande. Det tager tid at køre frem og tilbage på sådan et tape, og en algoritme kan have brug for at gøre det mange gange. En random access maskine minder mere om den måde en computer faktisk fungerer på, og den vil i de fleste situationer kunne udføre en opgave hurtigere end en Turing maskine.
Det er bevist at problemer der kan løses i polynomiel tid på den ene kan også løses i polynomiel tid på den anden. Men normalt vil polynomiet have højere grad på en Turing maskine end på en random access maskine.
En kvantecomputer kan være endnu hurtigere. Spørgsmålet, som vist ikke er endegyldigt besvaret endnu er, om der er problemer som kan løses i polynomiel tid på en kvantecomputer men ikke på en Turing maskine.
Faktorisering er en kandidat, hvor den bedst kendte algoritme på en kvantecomputer kører i polynomiel tid. Det kan den bedst kendte algoritme på en Turing maskine ikke hamle op med.
Det hænger i øvrigt til dels sammen med spørgsmålet om, hvorvidt P=NP. Så vidt jeg ved vil ethveret problem, der kan løses i polynomiel tid på en kvantecomputer, også kunne løses i polynomielt tid på en nondeterministisk Turing maskine. Men det gælder ikke nødvendigvis den modsatte vej. Der er ingen som har udviklet et NP orakel som en polynomiel kvantealgoritme.
#54
Din algoritme skulle virke for en vilkårlig krypteringsalgoritme, så du bliver nødt til at fortælle os, hvad kaldet af decrypt gør.
Du har måske lige samlet nogle empiriske data fra din egen Turing-maskine hjemme på kontoret eller hvad? :) (Undskyld, ved godt hvad du mener)
for K in {0,1}^k
do
M=decrypt(C,K)
if correct(M) return K
done
Din algoritme skulle virke for en vilkårlig krypteringsalgoritme, så du bliver nødt til at fortælle os, hvad kaldet af decrypt gør.
En Turing maskine er langsom.
Du har måske lige samlet nogle empiriske data fra din egen Turing-maskine hjemme på kontoret eller hvad? :) (Undskyld, ved godt hvad du mener)
#56
Så gætter jeg på, at du som programmør vil sætte stor pris på dokumentation der er så udførlig, at vi andre ikke gider læse den. :)
Jeg gætter på at den forsøger at dekryptere C ud fra nøglen K, og returnerer resultatet.
Der er 3 ting der kan forhindre algoritmen i at virke:
1 Man skal have det krypterede data (steganograpfi osv.)
2 Man skal kende krypteringsformen
3 correct(M) skal kunne implementeres, enten ved at krypteringsformen giver mulighed for det, eller med known plaintext.
Det eneste man kan gøre for at forhindre brute-force angreb helt, er 3'eren. Dvs. kryptere med one-time pad. Det er dog ret besværligt at have med at gøre. Ikke implementering (det er næsten lige så nemt som caesar), men brugen i praksis.
du bliver nødt til at fortælle os, hvad kaldet af decrypt gør.
Så gætter jeg på, at du som programmør vil sætte stor pris på dokumentation der er så udførlig, at vi andre ikke gider læse den. :)
Jeg gætter på at den forsøger at dekryptere C ud fra nøglen K, og returnerer resultatet.
Der er 3 ting der kan forhindre algoritmen i at virke:
1 Man skal have det krypterede data (steganograpfi osv.)
2 Man skal kende krypteringsformen
3 correct(M) skal kunne implementeres, enten ved at krypteringsformen giver mulighed for det, eller med known plaintext.
Det eneste man kan gøre for at forhindre brute-force angreb helt, er 3'eren. Dvs. kryptere med one-time pad. Det er dog ret besværligt at have med at gøre. Ikke implementering (det er næsten lige så nemt som caesar), men brugen i praksis.
[url=#57]#57[/url] myplacedk
Et brute force angreb kan stadig udføres, man skal bare brute force over alle nøgler og algoritmer. Det eneste tricky ved det er, at man ikke kan se på en algoritme og afgøre, om det er en kryptering. Det betyder at et brute force angreb vil være nødt til at afprøve flere algoritmer i parallel.
Man skal have det krypterede dataDet er jo åbenlyst. Hvis ikke udvekommende har adgang til de krypterede data var der jo ingen grund til at kryptere dem i første omgang.
steganograpfi osv.Er bare en del af algoritmen.
Man skal kende krypteringsformenDet er selvfølgelig en fordel, når man ønsker at bryde krypteringen. Men at basere sig på, at andre ikke kender den, er bare security through obscurity. Det opnår man ikke sikkerhed ved.
Et brute force angreb kan stadig udføres, man skal bare brute force over alle nøgler og algoritmer. Det eneste tricky ved det er, at man ikke kan se på en algoritme og afgøre, om det er en kryptering. Det betyder at et brute force angreb vil være nødt til at afprøve flere algoritmer i parallel.
correct(M) skal kunne implementeres, enten ved at krypteringsformen giver mulighed for det, eller med known plaintext.Eller ved blot at have statistisk kendskab til distributionen af plaintext. Hvis mængden af plaintext der er krypteret er væsentligt større end det antal bits, der skal brute forces, så vil sådan en statistik kunne virke.
#58
Så har du ikke forstået steganografi, for så er det bare omvendt kompression gjort besværligt. :)
Jeg er helt enig. Men hvis krypteringsmetoden ikke er kendt af dit bruteforce-værktøj, kan du ikke bruteforce den. Du må lære den at kende først, og så tilpasse dit bruteforce-værktøj.
Du kan ikke "brute force over alle algoritmer", da du ikke bare kan sætte dig ned og definere samtlige algoritmer der kan opfindes.
Som sagt, det kræver at krypteringsformen giver mulighed for det, det gør fx. one-time pads ikke.
"steganograpfi osv."
Er bare en del af algoritmen.
Så har du ikke forstået steganografi, for så er det bare omvendt kompression gjort besværligt. :)
"Man skal kende krypteringsformen"
Det er selvfølgelig en fordel, når man ønsker at bryde krypteringen. Men at basere sig på, at andre ikke kender den, er bare security through obscurity. Det opnår man ikke sikkerhed ved.
Jeg er helt enig. Men hvis krypteringsmetoden ikke er kendt af dit bruteforce-værktøj, kan du ikke bruteforce den. Du må lære den at kende først, og så tilpasse dit bruteforce-værktøj.
Du kan ikke "brute force over alle algoritmer", da du ikke bare kan sætte dig ned og definere samtlige algoritmer der kan opfindes.
"correct(M) skal kunne implementeres, enten ved at krypteringsformen giver mulighed for det, eller med known plaintext."
Eller ved blot at have statistisk kendskab til distributionen af plaintext.
Som sagt, det kræver at krypteringsformen giver mulighed for det, det gør fx. one-time pads ikke.
[url=#59]#59[/url] myplacedk
Så har du ikke forstået steganografi, for så er det bare omvendt kompression gjort besværligt.Ja, sådan kan man godt forstå steganografi. Det gør det ikke væsentligt sværere at bryde krypteringen, når man altså først lige har fundet på at prøve. Men hvis man er i gang med at brute force, så kan man jo bare prøve at brute force alle de data man kan komme i nærheden af, uanset om man tror der er nogle krypterede data gemt eller ej.
Du kan ikke "brute force over alle algoritmer", da du ikke bare kan sætte dig ned og definere samtlige algoritmer der kan opfindes.Jo, man kan. Det er jo lige netop det, der er hele essensen af Alan Turings arbejde.
Som sagt, det kræver at krypteringsformen giver mulighed for det, det gør fx. one-time pads ikke.Hvilket så også var det jeg startede med at sige. Nu er der bare mange situationer, hvor en one time pad ikke er praktisk (og meget få, hvor den er).
[url=#61]#61[/url] arne_v
Hvis du tænker på et positivt heltal kan jeg finde frem til det, hvis jeg får lov at prøve vilkårligt mange gange. Jeg gætter først på 1, hvis ikke det var det, så gætter jeg i stedet på 2, så prøver jeg 3, 4, osv.
Er der et endeligt antal krypterings algoritmer ?Nej, men de kan nummereres. Så man kan starte fra en ende af, og på et tidspunkt vil man nå frem til den rigtige. Tidsforbruget afhænger selvfølgelig af, hvor kompliceret en algoritme, der anvendes. Men for enhver given algoritme, vil man nå frem til den i endelig tid.
Hvis du tænker på et positivt heltal kan jeg finde frem til det, hvis jeg får lov at prøve vilkårligt mange gange. Jeg gætter først på 1, hvis ikke det var det, så gætter jeg i stedet på 2, så prøver jeg 3, 4, osv.
#56
Jamen, hele humlen var jo, at din algoritme skulle virke, uden at du havde noget som helst kendskab til krypteringsalgoritmen. Det var det, hele Janus' spørgsmål gik ud på. Du skal altså skrive et program, der givet en krypteret streng S, der kan være krypteret med en vilkårlig algoritme (dette inkluderer algoritmer, du ikke kender), dekrypterer S. Programmet skal virke for alle algoritmer. Det gør dit program ikke, medmindre du laver et eller andet drastisk i dekrypt-metoden.
Kalder den krypterings algoritme, du ønsker at bryde.
Jamen, hele humlen var jo, at din algoritme skulle virke, uden at du havde noget som helst kendskab til krypteringsalgoritmen. Det var det, hele Janus' spørgsmål gik ud på. Du skal altså skrive et program, der givet en krypteret streng S, der kan være krypteret med en vilkårlig algoritme (dette inkluderer algoritmer, du ikke kender), dekrypterer S. Programmet skal virke for alle algoritmer. Det gør dit program ikke, medmindre du laver et eller andet drastisk i dekrypt-metoden.
#72
Gør jeg.
r = størrelse af algoritme
f(r) = antal algoritmer af given størrelse
Det må være åbenlyst at f''(r) > 0 for alle r - oppe i
#64 antyder du at:
f(r) = a * b^r med b > 1
Lad os antage det.
g(r) = tid det tager at prøve alle algoritmer af længde r
g(r) = c * f(r) = d * b^r med b > 1
Gennemsnitlig tid for at finde den rigtige algoritme hvor
med en længde op til r:
v(r) = 0.5*sum(x=1..r,g(x))/r = 0.5*sum(x=1..r,d*b^x)/r
Jeg vil absolut mene at v(r) går mod uendelig når r går
mod uendelig.
Eller ?
Gør jeg.
r = størrelse af algoritme
f(r) = antal algoritmer af given størrelse
Det må være åbenlyst at f''(r) > 0 for alle r - oppe i
#64 antyder du at:
f(r) = a * b^r med b > 1
Lad os antage det.
g(r) = tid det tager at prøve alle algoritmer af længde r
g(r) = c * f(r) = d * b^r med b > 1
Gennemsnitlig tid for at finde den rigtige algoritme hvor
med en længde op til r:
v(r) = 0.5*sum(x=1..r,g(x))/r = 0.5*sum(x=1..r,d*b^x)/r
Jeg vil absolut mene at v(r) går mod uendelig når r går
mod uendelig.
Eller ?
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Nyheder
Gå til bund