Cryptografie

[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 ?

[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 10⁸⁵ jaar over.
Een beetje onpraktisch, dus.

[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.

[Xilvo]

Een getal van 200 cijfers in twee priemfactoren ontbinden is nog steeds geen makkelijke klus en kan een computer jaren bezighouden.

[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.

[Xilvo]

Dan worden de individuele getallen zo klein dat het een fluitje van een cent is.

[tempelier]

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.

[Xilvo]

Nee dat is een etje.

Bron?

[CoenCo]

https://en.m.wikipedia.org/wiki/Integer_factorization

Volgens wikipedia is het knap lastig.

[tempelier]

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.

[Xilvo]

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.

[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 ?

[Xilvo]

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 P₁^P₂
Als dat resultaat een getal van 200 cijfers is dan zijn P₁ en P₂ 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.

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.

[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?

[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 = p⁵ * q⁶ = 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 = q^k.
(in dit voorbeeld is L = 413109111924508609; een getal van 18 cijfers)
Uit L = q^k 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).