Springen naar inhoud

[wiskunde] rsa vercijfering/modulair rekenen


  • Log in om te kunnen reageren

#1

Roki

    Roki


  • 0 - 25 berichten
  • 22 berichten
  • Gebruiker

Geplaatst op 02 maart 2009 - 09:50

Vercijferen: E(x) = x^e mod m

Hoe berekenen ik E(x), als x=1618090513, e=88 en m=30353?
Want ik heb al geprobeerd om dit programmaatje op mijn rekenmachine te zetten, maar hiermee kan ik verder niks.
Kan iemand mijn helpen?

Veranderd door Roki, 02 maart 2009 - 09:52


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Axel van de Graaf

    Axel van de Graaf


  • >25 berichten
  • 58 berichten
  • Ervaren gebruiker

Geplaatst op 02 maart 2009 - 20:21

Vercijferen: E(x) = x^e mod m

Hoe berekenen ik E(x), als x=1618090513, e=88 en m=30353?
Want ik heb al geprobeerd om dit programmaatje op mijn rekenmachine te zetten, maar hiermee kan ik verder niks.
Kan iemand mijn helpen?

Ik had dat probleem ook :P Via een foefelmethode is het toch gelukt, maar met zulke grote getallen zou ik het ook niet weten :D

edit: ik vond ook geen simulatie programma van rsa.

Veranderd door Axel van de Graaf, 02 maart 2009 - 20:27

Geplaatste afbeelding

#3

Roki

    Roki


  • 0 - 25 berichten
  • 22 berichten
  • Gebruiker

Geplaatst op 02 maart 2009 - 20:24

Echt vervelend, ik kom er maar niet uit. Iemand anders misschien?

#4

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 02 maart 2009 - 23:53

Om je op de goede weg te helpen:
LaTeX
LaTeX

#5

Roki

    Roki


  • 0 - 25 berichten
  • 22 berichten
  • Gebruiker

Geplaatst op 03 maart 2009 - 18:03

Om je op de goede weg te helpen:
LaTeX


LaTeX


Misschien een hele domme vraag, maar wat zou ik dan voor a, b, c en d moeten invullen?

En ik heb een voorbeeld op internet gevonden en dit is ook met grote getallen.

We illustreren dit alles nog eens met een wat kleiner getallenvoorbeeld. Als priemgetallen nemen we p = 74471 en q = 98773. De modulus m = p x q is dan 7355724083. Het getal n = (p-1)(q-1) is nu 7355550840, en voor e nemen we 619. Het algoritme van Euclides leert ons dat e inderdaad geen delers met n gemeen heeft, en bovendien dat de inverse d van e gelijk is aan 4313513659. Neem nu als boodschap PRIEM. In cijfers wordt dat x = 1618090513. Vercijferen levert:

E(x) = 1618090513^619 mod 7355724083 = 633613585

en ontcijferen geeft inderdaad:

D(633613585) = 633613585^4313513659 mod 7355724083 = 1618090513.

Bron: Kennislink


Ik snap alleen niet hoe ze 1618090513^619 mod 7355724083 uitrekenen (en dus aan 633613585 komen).

Ook heb ik een site gevonden waarbij ik een 'som' als:

C = 88^7 mod 187 (werkt alleen bij relatief kleine getallen) kan 'herleiden' tot C = 11 mod 187.
Ik zou alleen (1.) niet weten hoe je dit met een rekenmachine of uit het blote hoofd zou kunnen doen en (2.) wat dan C dan precies is. Niet uitgeschreven als 11 mod 187, maar echt als een getal, zoals staat bij het voorbeeld in de bron.

Daarnaast moet ik de boodschap weer kunnen ontcijferen met D(x) = y^d mod m, waarbij y = E(x), d is de inverse van e en m is gelijk aan de m uit de formule E(x) = x^e mod m.

Je kunt dan d uitrekenen met:

d * e = 1 mod n

En stel dat ik de volgende gegevens pak:

e = 77
n = 31552 (Mijn p = 137 en mijn q = 233, de m = 31921)

Ik zou zeggen:

d = (1 mod n)/e
d = (1 + k * n)/e
((k * n)/e) + 1 = d
(k * n)/e = d - 1
k * n = (d - 1) * e
((d - 1) * e)/n = k

Ik zou zeggen dat je dan k in de formule d = (1 + k * n)/e zou kunnen vervangen door ((d - 1) * e)/n, waardoor je de k uit de formule wegwerkt. Je krijgt dan:

d = (1 + (((d - 1) * e) * n))/e

Ik weet dan alleen niet hoe ik verder moet. Het zou goed kunnen dat ik het totaal fout doe. Wiskunde is niet mijn sterkste vak, dus het zou fijn zijn als iemand mij hiermee zou willen helpen.

Veranderd door Roki, 03 maart 2009 - 18:09


#6

Roki

    Roki


  • 0 - 25 berichten
  • 22 berichten
  • Gebruiker

Geplaatst op 03 maart 2009 - 21:29

Ik heb nu door hoe ik met zowel kleine als grote getallen E(x) kan berekenen.

Ik weet alleen nog steeds niet hoe je aan die 'd' komt. En ik heb de formule die Evilbro gepost had ook gevonden op een andere site: a^2 = b + x*m als we dit weer kwadrateren: (b + x*m)^2 = b^2 + 2bxm + x^2 * m^2 = b^2 mod m.

Ik volg alleen niet hoe ze aan: b^2 + 2bxm + x^2 * m^2 = b^2 mod gekomen zijn. Hoe krijg je in hemelsnaam uit 2bxm +x^2 * m ^2 de formule b^2 mod m. Als iemand nog zou vriendelijk zou willen zijn om mij dat uit (en dat van die 'd') uit te leggen, dan snap ik het, als het goed is, helemaal. Dank je wel, in ieder geval.

#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 03 maart 2009 - 22:08

Stel je hebt een getal c. Dit getal kun je schrijven als een geheel aantal keer het getal m plus een rest b, ofwel:
LaTeX
Er geldt dus:
LaTeX

Bekijk nu LaTeX :
LaTeX
Het kwadraat van c is dus te schrijven als een geheel aantal keer het getal m plus een rest (de b kwadraat, die eventeel ook nog groter dan m is). Voor de modules geldt dus:
LaTeX

#8

Roki

    Roki


  • 0 - 25 berichten
  • 22 berichten
  • Gebruiker

Geplaatst op 04 maart 2009 - 20:28

Stel je hebt een getal c. Dit getal kun je schrijven als een geheel aantal keer het getal m plus een rest b, ofwel:
LaTeX


Er geldt dus:
LaTeX

Bekijk nu LaTeX :
LaTeX
Het kwadraat van c is dus te schrijven als een geheel aantal keer het getal m plus een rest (de b kwadraat, die eventeel ook nog groter dan m is). Voor de modules geldt dus:
LaTeX


Dus m * x^2 + 2 * x * b is te vervangen door ťťn variabele?

En hoe kom ik dan aan de 'd' in d * e = 1 mod m?

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 04 maart 2009 - 20:47

Dus m * x^2 + 2 * x * b is te vervangen door ťťn variabele?

ik zou niet weten waarom niet. Het is echter niet relevant. Het enige dat telt is dat het een getal is dat vermenigvuldigd wordt met m. Bij 'mod m' valt het hele zaakje dan dus weg.

En hoe kom ik dan aan de 'd' in d * e = 1 mod m?

Je kan op zoek gaan naar de 'r' zodat:
LaTeX
Als je die r gevonden hebt dan weet je dat:
LaTeX





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures