RSA-576: Newbie vraag...

[Verwijderd]

Ik heb gezocht op internet en ook op het GoT forum maar ik heb het antwoord op mijn vraag niet gevonden.

Ik vond via tweakers.net onder Dutch Power Cows kopje een link naar RSA en kwam daar na wat klikken bij "The RSA Challenge numbers" terecht. Ik snap niet wat je met die getallen moet doen.

Factoren zoeken dacht ik, maar ik weet dit niet zeker. En dan als het factoren zoeken is, dan heb je een lijst met getallen die in paar, keer elkaar, het getal vormen. Hoe kom je dan ooit aan hele zinnen die eruit zouden moeten komen.

Ik wil hier erg graag een antwoord op en niet een antwoord van UTFS enzo. bij voorbaat dank

TmmK

[Stubby]

Ik zou je aanraden om eens op te zoeken hoe het RSA encryptiealgoritme in elkaar steekt. Ik zal ff voor je googlen

I'm feeling lucky ;)

[ Voor 35% gewijzigd door Stubby op 07-04-2003 22:17 ]

[Verwijderd]

Over dat encryptiealgoritme. Ik heb begrepen dat als een string in een andere string wordt omgezet (een encrypted string dus, dus van hallo naar bijvoorbeeld 3sdfd7f67df69de) dat de ontvanger die het mag weten wat er staat een sleutel heeft (algoritme) waarmee dat weer om kan worden gezet in hallo. Maar hoe komt diegene dan aan die sleutel enzo, en wat hebben die getallen en algoritmes dan met elkaar te maken...

[MadMarky]

Eh, ik zou echt niet aan RSA-576 mee gaan doen. De website is al meer als een week down en de client werkt niet meer. Kortom:
RSA-576 is dood

[Verwijderd]

Ow, maar ik hoef er ook niet aan mee te doen, ik wil alleen weten hoe encryptie werkt en nam RSA-576 als voorbeeld. doei

TmmK

PS: is nog steeds opzoek naar een beetje 'normale' uitleg hierover (veel engelse wiskundige termen ken ik niet, vandaar)

[Stubby]

Nu ook in het nederlands!
HIER!
Maar goed, encryptie bestaat grotendeels uit wiskundige operaties (in dit geval uit machtsverheffen en de modulus van een getal nemen) en ik vind dat het redelijk duidelijk uitgelegd wordt.

[Qwerty-273]

RSA-576 is een groot getal welke een 'composite' is en bestaat uit twee priem getallen met elkaar vermenigvuldigd. Zulke grote getallen worden in ecryptie algorithmes gebruikt om dat deze getallen zo groot zijn dat het terug rekenen heel lastig wordt.

ALs je eenmaal de twee priem getallen weet waarvan dit getal (RSA-576 nummer) is afgeleid heeft een significante voorsprong voor het terug rekenen met deze twee getallen.

Om de wedstrijd van RSA Labs te winnen moet je dus twee priem getallen zien te vinden die als product het challenge getal hebben.

Let er wel op dat het RSA algorithme standaard ook gebruik kan maken van meerdere priemgetallen i.p.v. twee.

Bij de wedstrijd van RSA Labs hebben ze gekozen voor 2 priems van de zelfde lengte (aantal getallen bedoel ik dus) dat maakt eht al weer een stukje makkelijker

---

Dat RSAttack niet meer actueel is tja dat betekend weinig of deze wedstrijd nog loopt. Ik bedoel dat 1 iemand het probeerd en niet succesvol is (om het project goed op te zetten) betekend niet dat de wedstrijd gelijk gecanceld is. Ik heb nu al 3 projecten gezien die proberden deze challenge op te lossen, de een op inefficiente wijze (volgens mij ook RSAttack aangezien ik daar nog steeds geen source van hun sieving heb gezien) de ander totaal slecht geprogd dus....

Pak je kans en verzin een goede aanpak

[Verwijderd]

RSAttack gebruikt(e) wat random nummertjes en waren in de veronderstelling ooit wel eens op de goede nummers uit te komen (jaartje of 20 later ). En mocht iemand je voorzijn met het verzinnen van een goede methode voor de 576 versie kan je altijd een van de andere versies nemen .

[Verwijderd]

Ik weet niet of er mensen zijn met een beetje verstand van PHP, maar ik heb een scriptje gemaakt waarbij je een getal kan invullen, waarbij hij alle mogelijke getallen (keer elkaar) het ingevulde getal vormen. Dus je vult 8 in en er komt uit 1 en 8, 2 en 4, 4 en 2, 8 en 1:

<center>
<form method="get" action="priemgetal.php">
<input type="text" name="number">
<input type="submit">
</form>
</center>
<hr>
<?
for ($i = 1; $i <= $number; $i++) {
$xnumber = $number / $i;
if(strpos($xnumber, ".",1) != ""){
}else{
echo "$i en $xnumber<br>\n";
}
}
?>

Door het omgekeerde (dus op een gegeven moment, spiegelt het gewoon, dus dan kun je net zo goed gaan stoppen) weg te laten, kun je met dit script op 1 computer al best een groot getal invullen. Nog een beetje inkorten en zelf de querystring maken en je kunt best ver komen:

<?for($i=1;$i<=$number;$i++){$xnumber=$number/$i;if(strpos($xnumber,".",1)!=""){}else{if($xnumber<$i){return;}else{echo "$i en $xnumber<br>";}}}?>

Maar ik kan dus met zo'n soortgelijk script de priemgetallen vinden van een getal, wat ik nodig heb voor encryptie? (natuurlijk niet RSA-576, want dat gaat wat te lang duren) doei

TmmK

[Verwijderd]

Verwijderd schreef op 08 April 2003 @ 16:16:
Maar ik kan dus met zo'n soortgelijk script de priemgetallen vinden van een getal, wat ik nodig heb voor encryptie? (natuurlijk niet RSA-576, want dat gaat wat te lang duren)

Inderdaad, dat heb je goed gezien. De publieke sleutel van een RSA encryptie bestaat uit twee delen, en één daarvan is het product van 2 - typisch heel grote - priemgetallen. Als je dat product in z'n priemfactoren kun splitsen (maar dat is juist de moeilijkheid met de huidige technieken en kennis) is die bepaalde encryptie in een fractie van een seconde gebroken...
De encryptie breken is dus conceptueel heel simpel - gewoon ff dat getal onbinden in z'n priemfactoren en nog een paar kleine bewerkingen en je bent er. Maar een getal ontbinden in priemfactoren is een zogenaamd 'moeilijk probleem'.
Mocht je hier een (relatief) snelle, efficiënte oplossing voor vinden, dan heb je zo een Turing award (zeg maar een nobelprijs wiskunde/computerwetenschappen) vast denk ik

[Verwijderd]

Het enige dat RSAlabs dus eigenlijk wil weten is welke twee priemgetallen (van een cijfer of 20) je nodig hebt om het door hun opgegeven getal te maken?

[Verwijderd]

Verwijderd schreef op 08 April 2003 @ 21:25:
Het enige dat RSAlabs dus eigenlijk wil weten is welke twee priemgetallen (van een cijfer of 20) je nodig hebt om het door hun opgegeven getal te maken?

Nee, niet helemaal dacht ik. Wat RSA labs wil weten is de private key die je nodig hebt om versleutelde berichten te kunnen ontcijferen. Maar dat komt bijna op hetzelfde neer, want eenmaal je die twee priemgetallen hebt is die private key zo berekend. Die twee priemgetallen vinden is dus het eigenlijke probleem, want die zogenaamde 'd-waarde' is dan maar een kwestie van een paar milliseconden langer rekenen

[edit]
Een cijfer of 20? Dat zijn kleintjes die je zo uitrekent hoor Maak daar maar meteen minstens 80 cijfers van, als het ondertussen niet meer is...

[ Voor 12% gewijzigd door Verwijderd op 08-04-2003 22:46 ]

[Qwerty-273]

RSA-576 is Decimal Digits: 174

18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

Dus twee getallen van 87 of zo getallen? of is het nou 88 ??

[Verwijderd]

RIKZ schreef op 09 April 2003 @ 11:49:
RSA-576 is Decimal Digits: 174

Dus twee getallen van 87 of zo getallen? of is het nou 88 ??

Dat weet je in principe niet. Het kan *in principe* evengoed een priemgetal van 50 cijfers zijn en een van 124 ofzo. Maar je kan er inderdaad van uitgaan dat het priemgetallen zijn van 86 a 88 cijfers.. maar dat zijn er nog steeds een flink pak om te controleren hoor Dus zelfs als je gokt dat deze beperking geldt is het niet te doen bijna, want het aantal priemgetallen wat 86, 87 of 88 cijfers telt is bij benadering ongeveer 4,87*10⁸⁶... dus zelf ook een getal met 87 cijfertjes!

[Qwerty-273]

De RSA heeft voor hun priem getallen in deze factoring challenges gekozen voor even lange getallen. Opzich kan je hiervan uitgaan. Van de vorige challenges met hun oplossingen kan je dat goed afleiden