[RSA] p en q te kraken?

[Verwijderd]

Hallo,

Ik gebruik momenteel een p en q waarde van elk 100 cijfers, zodat n een getal is van ongeveer 200 cijfers. Dat is veilig genoeg zover. Nu vraag ik me af hoe groot p,q en n moeten zijn willen ze te kraken zijn door een huis-tuin-keuken gebruiker. Welke waarden zijn groot genoeg zodat ze niet te kraken zijn door 1 pc?

Want immers, hoe kleiner p,q en n...hoe sneller het gaat en dat is wel zo prettig, maar de waarden moeten dus niet te klein worden zodat ze gevonden kunnen worden door buitenstaanders.

Ik was eigenlijk op zoek naar een tabel ofzo waar de waarde van n uitgezet werd tegen de factioneringstijd, maar kan deze niet vinden.
Iemand een suggestie/opmerking?

[Verwijderd]

Waar zijn de n, p en q voor?

[Verwijderd]

Ik vermoed een standaard-encryptiemethode waarbij n het product van de priemgetallen p en q is. De vraag wordt daarmee, hoe groot moet n zijn om te voorkomen dat een standaard PC het antwoord (de getallen p en q) binnen bijvoorbeeeld een jaar vindt. Lijkt me niet zo lastig experimenteel te bepalen, we hebben alleen iemand nodig die meedoet aan RC5 om aan te geven hoeveel berekeningen zijn computer per uur doet, dat extrapoleren naar een jaar, en vervolgens uit te rekenen hoe groot n moet zijn om meer mogelijkheden voor p en q te hebben die brute-force nagerekend moeten worden.

[ Voor 3% gewijzigd door Verwijderd op 07-04-2003 11:55 ]

[Verwijderd]

Uhm hier kun je een pagina vinden met informatie over RSA encryptie
http://www.win.tue.nl/~jessers/aansluiting/RSAsysteem.html

[Verwijderd]

Uhm als het in een week niet te kraken is vind ik het al best hoor, maar ik heb dus geen idee wat voor n daarbij hoort

[Erkens]

Verwijderd schreef op 07 april 2003 @ 11:57:
Uhm hier kun je een pagina vinden met informatie over RSA encryptie
http://www.win.tue.nl/~jessers/aansluiting/RSAsysteem.html

Not Found
The requested URL /~jessers/aansluiting/RSAsysteem.html was not found on this server.

Apache/1.3.26 Server at www.win.tue.nl Port 80

ik denk dat je http://www.win.tue.nl/~jessers/aansluiting/RSAsysteem.htm bedoeld voor deze huiswerk opdracht

[Verwijderd]

Huiswerkopdracht? LoL
Nee ik gebruik RSA om te voorkomen dat mensen met een packet sniffer plaintext kunnen onderschappen op een server/client applicatie

Zie ook: [rml][ Java] (Simpele) Encryptie/decryptie van Strings[/rml]

[ Voor 19% gewijzigd door Verwijderd op 07-04-2003 12:04 ]

[Gnoom]

Als ik ga zoeken waar je het nou eigenlijk over hebt, dan kom ik al gauw veel tabellen tegen met mips-years enzo. Deze geven misschien niet gelijk het juiste antwoord wat je zoekt, maar waarschijnlijk wel als je even doorrekent, of de waarden in een grafiekkie zet. Moet toch niet zo'n probleem zijn dacht ik.

[Verwijderd]

Verwijderd schreef op 07 April 2003 @ 11:57:
Uhm hier kun je een pagina vinden met informatie over RSA encryptie
http://www.win.tue.nl/~jessers/aansluiting/RSAsysteem.html

D00D

---

Is het niet 1-bit/tik van je CPU? Dus bij een 2.0Ghz 2.000.000.000 bits = 250.000.000 Bytes / sec

[ Voor 19% gewijzigd door Verwijderd op 07-04-2003 12:34 ]

[Rey Nemaattori]

Verwijderd schreef op 07 April 2003 @ 11:55:
Ik vermoed een standaard-encryptiemethode waarbij n het product van de priemgetallen p en q is. De vraag wordt daarmee, hoe groot moet n zijn om te voorkomen dat een standaard PC het antwoord (de getallen p en q) binnen bijvoorbeeeld een jaar vindt. Lijkt me niet zo lastig experimenteel te bepalen, we hebben alleen iemand nodig die meedoet aan RC5 om aan te geven hoeveel berekeningen zijn computer per uur doet, dat extrapoleren naar een jaar, en vervolgens uit te rekenen hoe groot n moet zijn om meer mogelijkheden voor p en q te hebben die brute-force nagerekend moeten worden.

Brute force hackers gebruiken vaak niet een enkele huis-, tuin- en keuken pc, maar parrallel geschakelde superbakken(naja, hackers met geld that is ) Daarmee gaan ze tientallen keren zo snel

[Verwijderd]

Tja, ik ben niet degene die dat wil bepalen voor een enkele huisPC

[toraq]

Rey_Nema schreef op 07 April 2003 @ 14:57:
[...]


Brute force hackers gebruiken vaak niet een enkele huis-, tuin- en keuken pc, maar parrallel geschakelde superbakken(naja, hackers met geld that is ) Daarmee gaan ze tientallen keren zo snel

Ja, maar helaas is dat nog steeds niet snel genoeg. Het meest efficiente algoritme dat er is voor het ontbinden van een priemgetal in die orde kost nog steeds maanden aan preprocessing en vervolgens nog wat tijd op een supercomputer. En dan hebben we het over een 512 bits priemgetal (~155 cijfers). Dus tenzij die hackers genoeg geld hebben om een betere supercomputer te kopen dan Teras (zie www.sara.nl). En dan hebben we het nog niet eens over het schrijven van een implementatie. Oftewel, 512 bits is ruim voldoende.

[CaptBiele]

ik heb pas RSA gehad op school, en kan je wel verzekeren dat zo`n getal echt niet in één dag met een huisPc-tje is gekraakt.
Als ik het me goed herinner, dan hadden een aantal gelinkte supercomputers een paar weken nodig, om dit te kraken (ben niet helemaal zeker).....

[Verwijderd]

Met een dik cluster van dual procs kan je het wel kraken.... alleen misschien niet binnen een week.
Ik weet niet hoe het precies met RSA zit, maar kan het niet zonder Brute Force te kraken zijn? Ik ben nog niet echt bezig met grote encrypties als RSA, dus daar weet ik nog niet zoveel van , ben nog bezig met de eerste paar studieboeken van de NSA

[Verwijderd]

Verwijderd schreef op 09 april 2003 @ 08:29:Ik weet niet hoe het precies met RSA zit, maar kan het niet zonder Brute Force te kraken zijn?

Het algoritme dat de sleutel moet genereren selekteert eerst twee grote priemgetallen p en q. Van deze twee priemgetallen wordt het produkt n bepaald. Dus:
n=p*q
Vervolgens wordt een getal e bepaald zodanig dat:

3 < e < (p-1)(q-1)

en de grootste gemene deler van e en (p-1)(q-1) is 1, ofwel e is relatief priem tov (p-1)(q-1).
Mbv dit getal e wordt getal d berekend zodanig dat:


d*e=1 mod (p-1)(q-1)
waarmee d de inverse is van e. De openbare sleutel bestaat nu uit het getallenpaar (e,n). De grootheden p, q en d zijn geheim. Het maken van de versleutelde code gaat als volgt. De originele boodschap wordt opgedeeld in blokken B en:


Code=B^e mod n

De werking van het systeem berust op het feit dat e weliswaar gemakkelijk uit d berekend kan worden, maar niet andersom. Het is bijna ondoenlijk om d op basis van alleen de openbare sleutel (e,n) te berekenen. Voor de berekening van d moeten ook p en q bekend zijn.

Als je dus twee grote waarden voor p en q kiest dan zit je vrij safe voor de huis-tuin-en-keuken kraker Computers zijn heel goed in staat om snel priemgetallen te berekenen, maar het factoriseren van n in (p,q) gaat erg langzaam en dat is de kracht van RSA...maar goed...deze thread ging niet over het uitleggen van RSA...maar nu weet je ff hoe het ongeveer zit

[RickN]

uitgebreide link

samenvatting

The resources required to factor a large number using GNFS consist of both processing power (machines) and data storage (memory).

The table below provides an estimate of the resources required to factor numbers of various bit lengths in a time period of one year. The Machines column is the number of 500 MHz Pentium (or comparable) machines needed.The Memory column is the amount of RAM required in each machine.

code:

Number Length (bits)     Machines   Memory  
                 430            1  trivial  
                 760      215,000     4 Gb  
                1020  342,000,000   170 Gb  
                1620  1.6 x 10^15   120 Tb

As shown, to factor a 760-bit number in one year would require 215,000 Pentium-class machines, each with 4 Gigabytes of physical RAM. These are estimates based on today's best factoring technology. It is possible that new techniques will be developed that may reduce both the number of machines and the storage per machine.

[ Voor 3% gewijzigd door RickN op 09-04-2003 12:34 ]