Archief - Cryptologie en priemgetallen
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.
Fraggie
Legacy Member
In mijn ogen is het verantwoord om met priemgetallen beveiligingen te maken daar priemgetallen enkel bestaan per definitie. Het is niet dat men ooit gezegd heeft "Voila ik ga eens getallen uitvinden, een paar die aan die eigenschap voldoen en nog een paar die aan een andere eigenschap voldoen etc..". Bijgevolg is er ook geen manier om achter priemgetallen te komen over het volledig bereik van het getallen stelsel. Dat bestaat niet en zal dus ook niet uitgevonden worden.
Pas ook op, het is niet omdat er een super pc super veel combo's probeert dat het systeem gekraakt is he.
Pas ook op, het is niet omdat er een super pc super veel combo's probeert dat het systeem gekraakt is he.
Europa
Legacy Member
NotoriousP zei:Iemand heeft de aflevering van Numb3rs gezien zeker?
Ja als iemand het probleem van de Riemann hypothese kan oplossen zal hij zichzelf toegang kunnen geven tot belangrijke gegevens. De wereld platleggen is veel gezegd maar hij zal er serieus van kunnen profiteren.
Nee ik haalde het niet van Numbers alhoewel ik toegeef dat die serie me meer dan één keer gefascineerd heeft
.Ik nam vlug een kijkje naar het Riemann hypothese maar zag daar niet direct het verband tussen, is er een verband tussen priemgetallen en het Riemann hypothese? Nog bedankt voor je constructieve reactie.
[BAT] Hydra
Legacy Member
taLa. zei:Met efficiënte algoritmes wordt overigens bedoeld: een algoritme dat het probleem oplost in een polynomiaal aantal stappen in functie van de inputgrootte. Heel informeel wordt hiermee bedoeld dat als men de uitvoeringstijd van het algoritme in functie van de grootte van het probleem n uitzet, dat er dan een zekere waarde p bestaat zodat de uitvoeringstijdscurve onder de curve van n^p blijft naarmate de probleemgrootte nadert tot oneindig (over de hele as van probleemgroottes).
Met andere woorden, er bestaat een polynomiale functie (i.e. iets van de vorm n tot een zekere macht) die een bovengrens vormt voor de uitvoeringstijd voor grote probleemgroottes.
Een voorbeeld van een probleemgrootte is bijvoorbeeld het aantal bits in het getal waarvan men de factoren wilt kennen. Voor de complexiteitsanalyse van algoritmes is men enkel geinteresseerd in het gedrag van de uitvoeringstijd naarmate de inputgrootte tot oneindig nadert.
Er bestaan ook functies die sneller stijgen dan polynomiaal. Voor een algoritme waarvan de uitvoeringstijd bijvoorbeeld exponentiëel stijgt in functie van de probleemgrootte tijd vraagt bestaat er geen curve van de vorm n^p, omdat er altijd een punt zal zijn waarop uw exponentiële uitvoeringstijdscurve boven de n^p zal uittorenen en naarboven schieten. Het punt op de x-as waarop dat gebeurt zal wel verschuiven naar rechts naarmate ge p groter neemt, maar de exponentiële zal er vroeg of laat toch bovenuitschieten ongeacht hoe groot ge p ook kiest.
Daarom zegt men dat de exponentiële functie "sneller stijgt" dan de polynomiale functie, omdat exponentiële functies vroeg of laat altijd boven een polynomiale zullen uitschieten. Algoritmes die exponentiële tijd vragen zijn dus minder efficiënt dan diegene die polynomiale tijd vragen.
Problemen worden opgedeeld in verschillende klassen volgens hun eigenschappen. Zo is de klasse "P" de verzameling van alle problemen die in polynomiale tijd opgelost kunnen worden, maw. waarvoor een algoritme bestaat met uitvoeringstijd O(n^p) voor zekere waarde van p.
De klasse van "NP"-problemen zijn dan weer die problemen waarvoor, als men een kandidaat-oplossing heeft, men in polynomiale tijd kan verifiëren of die kandidaat ook effectief een oplossing is van het probleem of niet. Het klassiek voorbeeld hierbij is het subset-sum probleem:
Gegeven een lijst getallen, bestaat er een subset die samen sommeren tot 0?
bv. input: { −7, −3, −2, 5, 8}.
Het is uiteraard eenvoudig om, gegeven een mogelijke oplossing (bv. { −3, −2, 5}), te controleren of die getallen sommeren tot 0. Als ge k getallen hebt in uw kandidaat-oplossing (hier dus 3) is dat dus gewoon k-1 optellingen; duidelijk polynomiale tijd want dat ligt overal onder k^1. Subset-sum ligt dus in NP.
Veel minder eenvoudig is om die subset van getallen ook te vinden (althans in polynomiale tijd). Tot nog toe is niemand erin geslaagd om hier een algoritme voor te vinden dat in polynomiale tijd werkt.
In de loop der jaren heeft men een hele hoop van dergelijke problemen gevonden; dus die in NP zitten maar waarvoor nog niemand polynomiale algoritmen heeft kunnen vinden. Men heeft kunnen aantonen dat bepaalde van die problemen karakteristiek zijn voor de klasse NP. Deze problemen zijn karakteristiek in die zin dat men ontdekt heeft dat alle andere problemen in NP er naar kunnen omgevormd worden. Deze problemen noemt men NP-compleet.
Zowat hét belangrijkste onopgeloste probleem in de complexiteitstheorie is nu de vraagstelling of P = NP. Dit is met andere woorden de vraag: kan elk probleem dat in polynomiale tijd geverifieerd kan worden ook opgelost worden in polynomiale tijd?
Men weet triviaal dat P een deelverzameling is van NP; dit is logisch, want elke oplossing van een P-probleem kan men uiteraard in polynomiale tijd verifiëren want men kan hem gewoon berekenen in polynomiale tijd. Om aan te tonen dat P = NP volstaat het dus om aan te tonen dat een NP-compleet probleem in polynomiale tijd opgelost kan worden.
Dit is overigens ook een van de Millenniumprijsproblemen, zowat de lijst met de moeilijkste openstaande wiskundige problemen. Los dit probleem op en u wint $1M en wereldwijde academische faam
Hele reden van dit verhaal: integer-factorisatie is een (F)NP-probleem waarvan niet geweten is of het in (F)P ligt. Het is NP want gegeven een kandidaatoplossing (ie. een verzameling priemgetallen) kunnen we makkelijk kijken of het een oplossing is: gewoon vermenigvuldigen. Het effectief ook vinden van die priemgetallen is echter heel wat moeilijker.
Om moderne cryptografie onderuit te halen, volstaat dus een bewijs dat P = NP. Algemeen wordt aangenomen dat P != NP omdat niemand er vooralsnog in geslaagd is om polynomiale algoritmes te vinden voor NP-complete problemen.
Wees dus enigszins gerust: cryptografie steunt op een van de moeilijkste wiskundige problemen die er zijn en waar men al meer dan 40 jaar tevergeefs op zoekt. Als men kan bewijzen dat P != NP dan is cryptografie aantoonbaar inherent veilig (voor voldoende grootte inputgroottes).
Anderzijds, als men kan aantonen dat P = NP, dan is cryptografie ook nog altijd niet compleet verloren. Moderne cryptografie steunt voor een groot deel op het groot genoeg maken van de priemgetallen om brute-forcing tegen te gaan. Zelfs al geldt P = NP, dan nog is het perfect mogelijk dat een algoritme om priemfactoren te bepalen een complexiteit van O(n^(10^10^10^...^10)) heeft. Theoretisch polynomiaal, maar praktisch nog altijd even nutteloos wegens veel te lange uitvoeringstijd.
DesorteD zei:Rep++
Ik kijk enorm graag terug naar de vakken waar dit in terugkwam. Zo super interessant...
Inderdaad zeer leuke en interessante post! Leuk om alles even te verfrissen
.MilM
Legacy Member
Europa zei:
Zo eenvoudig is het allemaal niet.
Die begrippen zijn niet onopgelost. Men kan ze wel degelijk oplossen, alleen duurt het enorm lang om de oplossing te vinden. Wanneer de rekenkracht van de computers toenemen, gaat men ook de lengte van de sleutel gaan vergroten.
Het klopt trouwens niet dat dit de enige security is voor ebanking. Certificaten worden bij de ebanking systemen vaak enkel gebruikt voor de encryptie van de gegevens die naar de bank verstuurd worden en vice versa (https ipv http in de URL). Het is ook een vorm van server authenticatie.
Dit op zich wordt de dag van vandaag al gemakkelijk omzeild door hackers. Https is dus allesbehalve nog veilig te noemen. Het is gewoon een extra layer. Nog een extra layer kan bijvoorbeeld een hardened browser zijn die draait op een USB stick in combinatie met een certificaat. De user is dan verplicht om de browser op zijn USB stick te gebruiken die op read only memery draait.
De hoofdbeveiliging zit hem echter nog altijd in de client authenticatie. Meestal wordt daar geen gebruik gemaakt van PKI, maar van symmetrische systemen zoals DES, 3DES en AES. Een voorbeeld hiervan zijn de DIGIPASS devices die door de meeste banken gebruikt worden.
Authenticatie op zich kan altijd gehacked worden en kan men nooit volledig beveiligen (man in the middle attack).
Daarom ook dat je bij verschillende banken aan transaction signing moet doen.
In dat geval, beveilig je de transactie zelf. (een voorbeeld is indien je 400 euro wil overschrijven en dit bedrag ook effectief in uw digipass moet ingeven)
PKI kan hier ook voor gebruikt worden (in Noorwegen en Zweden is dit populair) met een connected lezer en dan moet je een onderscheid maken tussen een transparante lezer (zoals een smart card lezer in uw laptop zonder pinpad en scherm) of een SWYS lezen. Het eerste is minder veilig omdat een hacker nog altijd de gegevens kan aanpassen wanneer die van de web site naar de lezer gestuurd worden;. In het tweede geval heeft de lezer een keypad (voor safe PIN entry) en een scherm. De gegevens worden naar de lezer gestuurd en worden niet automatisch gesigned, maar eerst op het scherm getoond voor approval van de user.
Daarnaast kunnen banken ook risk management gaan invoeren. Men kan bijvoorbeeld gaan controleren van welk IP adres het request komt, of de gebruiker al geld overgeschreven heeft naar die persoon of is die nog onbekend, om hoeveel geld gaat het, ...
Vergeet niet dat het om een continu process gaat. We komen van username password wat nog altijd veel minder veilig is. Dit is dus een grote stap voorwaarts.
Vergeet ook niet dat wanneer PKI bijvoorbeeld gebruikt wordt om transaction signing te doen bij een bank, normaal gezien niet enkel de private key, maar ook de public key niet gekend is.
Dit in tegenstelling bij normaal gebruik van PKI waar je het publieke certificaat nodig hebt om de verificatie te doen en je dus 1 sleutel kent.
NotoriousP
Legacy Member
Europa zei:Nee ik haalde het niet van Numbers alhoewel ik toegeef dat die serie me meer dan één keer gefascineerd heeft
Ik nam vlug een kijkje naar het Riemann hypothese maar zag daar niet direct het verband tussen, is er een verband tussen priemgetallen en het Riemann hypothese? Nog bedankt voor je constructieve reactie.
Wikipedia:
"The Riemann hypothesis implies results about the distribution of prime numbers that are in some ways as good as possible. Along with suitable generalizations, it is considered by some mathematicians to be the most important unresolved problem in pure mathematics (Bombieri 2000)."
Maar vraag mij niet om er dieper op in te gaan, deze wiskunde gaat mijn petje te boven.
Het archief is een bevroren moment uit een vorige versie van dit forum, met andere regels en andere bazen. Deze posts weerspiegelen op geen enkele manier onze huidige ideeën, waarden of wereldbeelden en zijn op sommige plaatsen gecensureerd wegens ontoelaatbaar. Veel zijn in een andere tijdsgeest gemaakt, al dan niet ironisch - zoals in het ironische subforum Off-Topic - en zouden op dit moment niet meer gepost (mogen) worden. Toch bieden we dit archief nog graag aan als informatiedatabank en naslagwerk. Lees er hier meer over of start een gesprek met anderen.