Cryptografie

[Human]

Redcat

Mooi, maar mijn anti logica bel rinkelt.

U kent M...........maar 737.9383....niet hoor !
737.9383... kent u maar als u N kent
Maar u kent N niet, enkel M, dus ok geen 737.9383...

Redeneert u of ik verkeerd?

[RedCat]

We vergelijken het kraken van N = p * q met het kraken van M = p^a * q^b.
De bovengrens van de zoektijd om het eerste (kleinste) priemgetal te vinden wordt in beide gevallen bepaald door √(p*q).
In het geval dat we N kennen, kennen we ook deze bovengrens.
In het geval dat we M kennen, kennen we deze bovengrens niet.
Maar het punt is dat deze bovengrenzen identiek zijn: in beide gevallen hoeven we de priemgetallen tot maximaal 738 te doorzoeken.

En deze eerste stap (het vinden van p) is bepalend voor de snelheid:
- in geval N hebben we direct q = N / p
- in geval M kunnen we met een relatief zeer snel O(log(L)) algoritme q bepalen.
In beide gevallen gaat dat in een tijd die verwaarloosbaar is ten opzichte van de eerste stap.

Het kraken van M kost dus niet beduidend meer tijd dan het kraken van N.

[Human]

Rode kat,

Ik snap het wel en niet (inbreuk op de tweewaardige logica).
In het geval M kent men p en q niet .... maar ook niet a en b.

Ik snap dus niet dat de bovengrenzen voor N en M identiek zijn.
Ik zou (met mijn beperkte kennis) eerder zeggen dat in het geval van M alle priem-gettallen moeten getoetst worden
binnen ( M^)1/2 en niet binnen (N^)1/2
Breng mij tot inzicht aub.

[RedCat]

Voorbeeld:

M = 1104648809 = p^a * q^b

Stap 1: zoek priemdeler p:
p=2 ? Nee, want M is niet deelbaar door 2.
p=3 ? Nee, want M is niet deelbaar door 3.
p=5 ? Nee, want M is niet deelbaar door 5.
p=7 ? Nee, want M is niet deelbaar door 7.
p=11 ? Ja, want M / 11 = 1104648809 / 11 = 100422619 rest nul
Dit is de stap die bij grote getallen veruit het langste duurt en de snelheid van het kraken bepaalt.

Stap 2: we weten M = 1104648809 = 11^a * q^b. Bepaal nu a:
Deel alle p=11 uit M:
- de eerste keer p=11 uit M delen levert: 1104648809 / 11 = 100422619
- nog een keer door p=11 delen levert: 100422619 / 11 = 9129329
- nog een keer door p=11 delen levert: 9129329 / 11 = 829939
- nog een keer door p=11 delen levert: 829939 / 11 = 75449
- nog een keer door p=11 delen levert: 75449 / 11 = 6859
- nog een keer door p=11 delen levert: 6859 / 11 = 623 rest 6: 6859 is niet deelbaar door 11.
In totaal hebben we M dus 5 keer door 11 kunnen delen, waardoor a=5:
M = 1104648809 = 11⁵ * q^b

Stap 3: we weten M = 1104648809 = 11⁵ * q^b, bepaal q en b:
Definieer L = M / 11⁵ = 6859 = q^b
voor onbekende q en onbekende b.
Als we k oplossen uit L = p^k dan zien we
6859 = 11^k
log(6859) = log(11^k)
log(6859) = k * log(11)

\(k = \frac{\log(6859)}{\log(11)} = 3.683779...\)

Omdat q>p is b<k en kan b dus maximaal 3 zijn.
We beginnen met testen van b=3: L^1/3 = 6859^1/3 = 19.00000000...
En inderdaad: 19³ = 6859
Dus M = 1104648809 = 11⁵ * 19³
Deze stap 3 gaat snel:
Stel L is van grootte-orde 10¹⁰⁰⁰⁰ en p van grootte-orde 10¹⁰⁰,
dan is b maximaal log(10¹⁰⁰⁰⁰) / log(10¹⁰⁰) = 100.
Dat betekent slechts b's testen van b=100 t/m b=2.



N = 209 = p * q

Stap 1: zoek priemdeler p:
p=2 ? Nee, want N is niet deelbaar door 2.
p=3 ? Nee, want N is niet deelbaar door 3.
p=5 ? Nee, want N is niet deelbaar door 5.
p=7 ? Nee, want N is niet deelbaar door 7.
p=11 ? Ja, want N / 11 = 19 rest nul
Nu hebben we p=11, en we weten ook direct q = N / p = 19.
Deze stap kost dus net zoveel tijd als p zoeken in M.


Conclusie
In beide gevallen is de snelheidsbepalende stap gelimiteerd tot

\(\sqrt{p\cdot q} = \sqrt{209} = 14.45...\)

Ofwel: in beide gevallen moeten we in stap 1 maximaal doorgaan met zoeken naar priem p tot de grens van 14, en NIET alle priemgetallen tot

\(\sqrt{M} = \sqrt{p^a\cdot q^b} = \sqrt{1104648809} = 33236.25...\)

Zodra we p gevonden hebben kunnen we p^a uit M delen, en kunnen we vrij eenvoudig q en b bepalen.

[Human]

Redcat,

Heel veel werk en tijd ingestoken om het mij duidelijk te maken.
Het zit er in .... en het gaat er niet meer uit.
De machten doen er blijkbaar niet veel toe.

Bedankt hoor.

[tempelier]

Ik heb wat overleg gehad met een oud collega.
Men schijnt afgestapt zijn van de priem tweetallen.