Pagina 1 van 2

Cryptografie

Geplaatst: wo 03 mar 2021, 19:12
door Human
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 ?

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 19:28
door Xilvo
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.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 19:38
door tempelier
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.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 20:35
door Xilvo
Een getal van 200 cijfers in twee priemfactoren ontbinden is nog steeds geen makkelijke klus en kan een computer jaren bezighouden.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 20:43
door Human
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.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 20:57
door Xilvo
Dan worden de individuele getallen zo klein dat het een fluitje van een cent is.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 21:04
door tempelier
Xilvo schreef: wo 03 mar 2021, 20:35 Een getal van 200 cijfers in twee priemfactoren ontbinden is nog steeds geen makkelijke klus en kan een computer jaren bezighouden.
Nee dat is een etje.

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 21:07
door Xilvo
tempelier schreef: wo 03 mar 2021, 21:04 Nee dat is een etje.
Bron?

Re: Cryptografie

Geplaatst: wo 03 mar 2021, 22:20
door CoenCo
https://en.m.wikipedia.org/wiki/Integer_factorization

Volgens wikipedia is het knap lastig.

Re: Cryptografie

Geplaatst: do 04 mar 2021, 08:46
door tempelier
Xilvo schreef: wo 03 mar 2021, 21:07
tempelier schreef: wo 03 mar 2021, 21:04 Nee dat is een etje.
Bron?
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.

Re: Cryptografie

Geplaatst: do 04 mar 2021, 09:33
door Xilvo
tempelier schreef: do 04 mar 2021, 08:46
Xilvo schreef: wo 03 mar 2021, 21:07
tempelier schreef: wo 03 mar 2021, 21:04 Nee dat is een etje.
Bron?
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.
Niet bepaald een eitje, blijkbaar.

Re: Cryptografie

Geplaatst: do 04 mar 2021, 11:49
door Human
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 ?

Re: Cryptografie

Geplaatst: do 04 mar 2021, 11:58
door Xilvo
Human schreef: do 04 mar 2021, 11:49 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 ?
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.
Human schreef: do 04 mar 2021, 11:49 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 ?
Natuurlijk is dat uniek. Een getal is maar op één manier te ontbinden in z'n priemfactoren.

Re: Cryptografie

Geplaatst: do 04 mar 2021, 13:43
door Human
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?

Re: Cryptografie

Geplaatst: do 04 mar 2021, 20:20
door RedCat
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:
\(\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).