Cryptografie
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 387
Cryptografie
In het RSA systeem maakt men bij mijn weten gebruik van het product van twee priemgetallen......waarom niet met de macht van twee priemgetallen ?
Is het vinden van de twee priemgetallen uit een macht ervan dan niet moeilijker dan uit een product ervan ?
Is het vinden van de twee priemgetallen uit een macht ervan dan niet moeilijker dan uit een product ervan ?
- Moderator
- Berichten: 10.083
Re: Cryptografie
Een product van twee grote priemgetallen (stel als voorbeeld, ieder van 100 cijfers) is lastig te ontbinden in die priemgetallen.
Misschien is een groot priemgetal tot de macht een andere groot priemgetal (als voorbeeld elk ook weer van 100 cijfers) ook wel lastig te ontbinden in grondtal en macht, maar het resultaat is een getal van enorme proporties.
Zou je dat willen versturen met een snelheid van 1 miljard cijfers per seconde, dan doe je daar ruim 1085 jaar over.
Een beetje onpraktisch, dus.
Misschien is een groot priemgetal tot de macht een andere groot priemgetal (als voorbeeld elk ook weer van 100 cijfers) ook wel lastig te ontbinden in grondtal en macht, maar het resultaat is een getal van enorme proporties.
Zou je dat willen versturen met een snelheid van 1 miljard cijfers per seconde, dan doe je daar ruim 1085 jaar over.
Een beetje onpraktisch, dus.
- Berichten: 4.320
Re: Cryptografie
Honderd cijfers is nauwelijks een probleem tegenwoordig.
Belangrijker is dat de ontbinding in precies twee priemen is.
Zijn er meer dan twee priem factoren dan is de code gemakkelijk te kraken, ook al zijn ze net zo groot.
Belangrijker is dat de ontbinding in precies twee priemen is.
Zijn er meer dan twee priem factoren dan is de code gemakkelijk te kraken, ook al zijn ze net zo groot.
- Moderator
- Berichten: 10.083
Re: Cryptografie
Een getal van 200 cijfers in twee priemfactoren ontbinden is nog steeds geen makkelijke klus en kan een computer jaren bezighouden.
-
- Berichten: 387
Re: Cryptografie
Als men de machten gebruik van de priemen mogen ze toch kleiner zijn..dacht/denk ik zo !
Wat is gemakkelijker te ontbinden in twee priemgetallen, een product of een macht? Aannemende dat het gaat om een getal met evenveel cijfers.
Wat is gemakkelijker te ontbinden in twee priemgetallen, een product of een macht? Aannemende dat het gaat om een getal met evenveel cijfers.
- Moderator
- Berichten: 10.083
Re: Cryptografie
Dan worden de individuele getallen zo klein dat het een fluitje van een cent is.
- Berichten: 4.320
- Moderator
- Berichten: 10.083
-
- Technicus
- Berichten: 1.171
- Berichten: 4.320
Re: Cryptografie
Al heel wat jaren terug, heeft men er een paar weten te kraken.
Hoe lang men er overdeed wet ik niet, het is misschien niet eens bekend.
Men deed het onmogelijke met een wereldwijd netwerk van PC's.
- Moderator
- Berichten: 10.083
Re: Cryptografie
-
- Berichten: 387
Re: Cryptografie
Tiens, mijn reactie van op mijn iphone is blijkbaar niet doorgekomen .. dus opnieuw via de c.
Ik zet het eens op een rijtje en stel dan mijn vragen.
1. De som van de priemgetallen P1 en P2 geven geen uniek getal, ze zijn dikwils ook de som van twee andere priemgetallen,
of zelfs meerdere paren.
2. Het product van P1 en P2 heeft uiteraard en uniek getal die moeilijk te ontbinden is als P1 en P2 groot zijn.
3. De macht van een priemgetal P1 tot een ander priemgetal P2 is een enorm getal tenzij P1 en P2 relatief klein zijn ....
...... maar dan is de ontbinding ook relatief simpel.
Vragen.
Is (P1)^P2 een uniek getal die maar op 1 manier kan leiden tot P1 en P2 ....... als som, of als product, of als macht ?
Stel dat men het product !P1)^a.(P2)^b als getal neemt. Is die uniek .. enkel te ontbinden in deze vorm ?
Is die ontbinding wel mogelijk ?
Ik zet het eens op een rijtje en stel dan mijn vragen.
1. De som van de priemgetallen P1 en P2 geven geen uniek getal, ze zijn dikwils ook de som van twee andere priemgetallen,
of zelfs meerdere paren.
2. Het product van P1 en P2 heeft uiteraard en uniek getal die moeilijk te ontbinden is als P1 en P2 groot zijn.
3. De macht van een priemgetal P1 tot een ander priemgetal P2 is een enorm getal tenzij P1 en P2 relatief klein zijn ....
...... maar dan is de ontbinding ook relatief simpel.
Vragen.
Is (P1)^P2 een uniek getal die maar op 1 manier kan leiden tot P1 en P2 ....... als som, of als product, of als macht ?
Stel dat men het product !P1)^a.(P2)^b als getal neemt. Is die uniek .. enkel te ontbinden in deze vorm ?
Is die ontbinding wel mogelijk ?
- Moderator
- Berichten: 10.083
Re: Cryptografie
Dat is maar op één manier te ontbinden in P1P2
Als dat resultaat een getal van 200 cijfers is dan zijn P1 en P2 zo klein dat het vinden van die waardes heel simpel en snel te doen is.
Wat je hier met som of product bedoelt begrijp ik niet.
Natuurlijk is dat uniek. Een getal is maar op één manier te ontbinden in z'n priemfactoren.
-
- Berichten: 387
Re: Cryptografie
Dat laatste weet ik ook!
De vraag is als de priemfactoren ook te vinden zijn van ((P1)^a).((P2)^b) met a NIET gelijk aan b. Volgens welke methode in dit geval?
De vraag is als de priemfactoren ook te vinden zijn van ((P1)^a).((P2)^b) met a NIET gelijk aan b. Volgens welke methode in dit geval?
-
- Berichten: 472
Re: Cryptografie
Voorbeeld in het klein (priemgetallen van 3 cijfers):
Neem priemgetallen p = 631 en q = 863, dus N = p * q = 544553 (6 cijfers).
Nu weet je alleen N = 544553 en je weet dat dit het product is van 2 priemgetallen.
Je wil met alleen deze informatie p en q bepalen.
Dat kan je doen door alle priemgetallen ≤ √N = √544553 = 737.9383... te testen of ze N delen.
Je vindt dan p = 631 waardoor q = N / p = 863.
Neem opnieuw priemgetallen p=631 en q=863, maar werk nu verder met
M = p5 * q6 = 41324877086333376958147273127959 (32 cijfers)
Nu weet je alleen deze M en je weet dat dit het product is van machten van 2 priemgetallen.
Je wil met alleen deze informatie p en q bepalen.
Ook hier kan je p bepalen door alle priemgetallen ≤ 737.9383... te testen:
net als bij N, zal p=631 ook M delen.
Dit is evenveel werk als hierboven voor de ontbinding van N.
Deel nu alle factoren p uit M.
Je houdt dan een getal L over dat een onbekende macht van onbekend priemgetal q is: L = qk.
(in dit voorbeeld is L = 413109111924508609; een getal van 18 cijfers)
Uit L = qk volgt:
Omdat p en q van dezelfde grootte-orde zijn, is in ons geval k=6 gelijk raak.
Maar ook in het algemeen: het zoeken naar een onbekende priemmacht (zoals we zagen van O(log(L))) is veel sneller dan het zoeken naar p in de ontbinding van N (of M) (dat is van O(√N)).
Dus zowel voor het ontbinden van N als van M wordt de tijdsduur bepaald door √N (een O(√N) algoritme).
Neem priemgetallen p = 631 en q = 863, dus N = p * q = 544553 (6 cijfers).
Nu weet je alleen N = 544553 en je weet dat dit het product is van 2 priemgetallen.
Je wil met alleen deze informatie p en q bepalen.
Dat kan je doen door alle priemgetallen ≤ √N = √544553 = 737.9383... te testen of ze N delen.
Je vindt dan p = 631 waardoor q = N / p = 863.
Neem opnieuw priemgetallen p=631 en q=863, maar werk nu verder met
M = p5 * q6 = 41324877086333376958147273127959 (32 cijfers)
Nu weet je alleen deze M en je weet dat dit het product is van machten van 2 priemgetallen.
Je wil met alleen deze informatie p en q bepalen.
Ook hier kan je p bepalen door alle priemgetallen ≤ 737.9383... te testen:
net als bij N, zal p=631 ook M delen.
Dit is evenveel werk als hierboven voor de ontbinding van N.
Deel nu alle factoren p uit M.
Je houdt dan een getal L over dat een onbekende macht van onbekend priemgetal q is: L = qk.
(in dit voorbeeld is L = 413109111924508609; een getal van 18 cijfers)
Uit L = qk volgt:
\(\log(L) = \log(q^k) = k \log(q)\)
dus
\(k = \frac{\log(L)}{\log(q)}\)
omdat we de kleinste priemdeler al gevonden hadden (dus p < q is), is
\(k \le \frac{\log(L)}{\log(p)} = \frac{\log(413109111924508609)}{\log(631)} = 6.29...\)
Zoek dan voor k = 6 t/m 2 uit of
\(L^{1/k}\)
een geheel getal q is.Omdat p en q van dezelfde grootte-orde zijn, is in ons geval k=6 gelijk raak.
Maar ook in het algemeen: het zoeken naar een onbekende priemmacht (zoals we zagen van O(log(L))) is veel sneller dan het zoeken naar p in de ontbinding van N (of M) (dat is van O(√N)).
Dus zowel voor het ontbinden van N als van M wordt de tijdsduur bepaald door √N (een O(√N) algoritme).