tag:blogger.com,1999:blog-15084482.post7789515755632201419..comments2024-02-12T11:08:20.509+01:00Comments on Mark Klamberg: Some thoughts about cryptanalysisMark Klamberghttp://www.blogger.com/profile/11882410684961184112noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-15084482.post-7151963437426658802010-02-20T18:33:25.572+01:002010-02-20T18:33:25.572+01:00Några, mer eller mindre matematiskt pedantiska, sy...Några, mer eller mindre matematiskt pedantiska, synpunkter:<br /><br />i. Först och främst vänder jag mig mot att du framställer det (åtminstone uppfattar jag det så) som att det är utvecklingen av <i>hårdvara</i> som gör att kryptoanalys blir allt svårare. Visserligen är det korrekt att förhållandet mellan kostnaden att dekryptera och att kryptera ökar när vår förmåga till numerisk beräkning ökar; men detta är förhållandevis banalt.<br /><br />[Ditt påstående att detta förhållande är exponentiellt är i själva <i>falskt</i>; redan den naiva testa-tills-du-hittar-en-faktor-metoden terminerar på en tid exponentiell i <i>roten ur n</i> (för att faktorisera n räcker det - uppenbarligen - att leta upp till sqrt(n), men detta tillhör de matematiska petitesserna. För det av xor nämnda(*) <a href="http://en.wikipedia.org/wiki/Elliptic_curve_cryptography" rel="nofollow">ECC-systemet</a> <i>är</i> våra bästa dekrypteringsalgoritmer exponentiella i storleken av nyckeln, jag bortser därför från denna petitess i det återstående.]<br /><br />Det relevanta är i själva verket förhållandet (i fallet med RSA) mellan <a href="http://en.wikipedia.org/wiki/General_number_field_sieve" rel="nofollow">våra bästa algoritmer för faktorisering</a> (dekryptering) och för att <a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow">identifiera primtal</a> (detta är den besvärliga delen i genererandet av nycklarna, den är <i>inte</i> linjär i nyckelstorleken, som påstås i din postning). <br /><br />På grund av detta förhållande är det alltid möjligt att välja en <i>tillräckligt stor</i> nyckel - dvs så stor att även ett enormt beräkningskluster skulle ta miljontals år (säg) för att knäcka krypteringen - att <i>ytterligare</i> öka storleken på nycklarna (bara för att förbättrade processorer har gjort det möjligt) vore dock relativt meningslöst (ett krypto som inte kan knäckas på 10^12 år är inte särskilt mycket intressantare än ett som inte kan knäckas på 10^6).<br /><br />Alltså: alltsedan upptäckten av <a href="http://en.wikipedia.org/wiki/Public-key_cryptography" rel="nofollow">public key cryptography</a> i början av 70-talet har effektiv kryptoanalys av dessa protokoll varit omöjlig (förutsatt förstås att man bemödar sig om att välja lämpliga nycklar), något som alltså är synnerligen oberoende av (den enorma) utvecklingen i processorkraft.<br /><br />ii. Pga de matematiska petitesserna ovan är analogin med kodlåset missvisande (men kanske inte på något egentligen allvarligt sätt).<br /><br />iii. Den slutsats du vill dra, med avseende på de juridiska frågor som intresserar dig, är förstås korrekt: moderna framsteg inom kryptografi och datorteknik har gjort kryptoanalys praktiskt omöjlig (och det kan vi förvänta oss att den fortsätter att vara för många, många decennier; varken effektiva faktoriseringsalgoritmer eller kvantdatorer är någonting vi ens kan se vid horisonten).<br /><br />iv. Av i-iii drar jag slutsatsen att beslutet att stryka texten ovan från årsboken var korrekt: de tekniska bitarna är dels inte korrekta i detaljer (vilket de bör vara i en akademisk publikation, matematisk oder nicht), dels bidrar de inte på något väsentligt sätt till att belysa de juridiska frågorna.<br /><br /><br />(*) Det mesta xor hade att säga <i>om</i> ECC är dock uppåt väggarna fel; <br /><br />1. Det första påståendet om kryptonycklarnas storlek är falskt redan i ljuset av det lilla jag sagt ovan.<br /><br />2. Hela texten handlar ju om <i>asymmetriska</i> (public key) krypton, varför i herrans namn komma dragade med <i>symmetriska</i>?? (Dessa är knappast särskilt relevanta för de juridiska frågor du vill diskutera.)Vidkunnoreply@blogger.comtag:blogger.com,1999:blog-15084482.post-69749341471573963862010-02-14T13:30:28.987+01:002010-02-14T13:30:28.987+01:00@Mark Klamberg: Ja :) Det är ju faktiskt väldigt t...@Mark Klamberg: Ja :) Det är ju faktiskt väldigt trevligt att det är så.xorhttps://www.blogger.com/profile/12237201358478589884noreply@blogger.comtag:blogger.com,1999:blog-15084482.post-63779561557107504172010-02-14T10:40:51.313+01:002010-02-14T10:40:51.313+01:00xor: det är ju naturligvis vad The Man _vill få di...xor: det är ju naturligvis vad The Man _vill få dig_ att troAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-15084482.post-7751802233262912922010-02-14T08:13:14.169+01:002010-02-14T08:13:14.169+01:00xor,
Jag uppfattar ändå att din slutsats är den sa...xor,<br />Jag uppfattar ändå att din slutsats är den samma, det har blivit svårare att forcera kryptoskydd och det lär inte bli enklare även om den som vill forcera kryptot skulle få tag på en fungerande kvantdator (som de flesta menar inte finns).Mark Klamberghttps://www.blogger.com/profile/11882410684961184112noreply@blogger.comtag:blogger.com,1999:blog-15084482.post-77500614858508368692010-02-14T02:45:15.091+01:002010-02-14T02:45:15.091+01:00Du utgår ju från att det inte finns några fler met...Du utgår ju från att det inte finns några fler metoder att använda asymmetrisk kryptografi. Elliptisk kurv-kryptografi (ECC) har inte den egenskapen att kryptonycklarnas storlek ökar snabbare än säkerheten i kryptot. Eller, med andra ord att de två kurvorna i ditt diagram hade varit parallella med varandra, om du jämfört ECC-kryptografi med kostnaden att bryta kryptot, snarare än att bara fokusera på det gamla RSA-kryptot.<br /><br />Alltså är det inget problem.<br /><br />Faktiskt är det inte ens ett problem om kvantdatorer skulle visa sig gå att tillverka. Först och främst såras inte symmetriska krypton speciellt mycket, deras effektiva nyckellägd halveras bara, vilket inte är så farligt ur ett komplexitetsanalysperspektiv, O(n) är nästan ekvialent med O(2n). Eller på normalt språk: AES256 blir lika säkert som AES128, om det attackeras av en kvantdator. Och 128-bitars symmetriska blockkrypton går ändå inte att knäcka idag. Vid sidan av att symmetriska krypton inte skadas, så är myten om att all form av asymmetrisk kryptografi skulle gå att knäcka bara man hade tillgång till kvantdatorer bara en myt. McEliece är ett exempel på ett sådant kryptosystem.<br /><br />Så, vi är safe :)xorhttps://www.blogger.com/profile/12237201358478589884noreply@blogger.com