[wiskunde] rsa vercijfering/modulair rekenen

Roki

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?

Axel van de Graaf

Roki schreef: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

Via een foefelmethode is het toch gelukt, maar met zulke grote getallen zou ik het ook niet weten

edit: ik vond ook geen simulatie programma van rsa.

Roki

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

EvilBro

Om je op de goede weg te helpen:

\(x^e \mod m = (a \cdot m + b)^e \mod m = b^e \mod m\)

\(b^e \mod m = b^2 \cdot b^{e-2} \mod m = (c \cdot m + d) \cdot b^{e-2} \mod m = d \cdot b^{e-2} \mod m \)

Roki

EvilBro schreef:Om je op de goede weg te helpen:

\(x^e \mod m = (a \cdot m + b)^e \mod m = b^e \mod m\)

\(b^e \mod m = b^2 \cdot b^{e-2} \mod m = (c \cdot m + d) \cdot b^{e-2} \mod m = d \cdot b^{e-2} \mod m \)

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.

Roki

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.

EvilBro

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

\(c = m \cdot x + b\)

Er geldt dus:

\(c = b \mod m\)

Bekijk nu

\(c^2\)

:

\(c^2 = (m \cdot x + b)^2 = m^2 \cdot x^2 + 2 \cdot m \cdot x \cdot b + b^2 = m \cdot ( m \cdot x^2 + 2 \cdot x \cdot b) + b^2\)

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:

\(c^2 = b^2 \mod m\)

Roki

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

\(c = m \cdot x + b\)
Er geldt dus:

\(c = b \mod m\)
Bekijk nu
\(c^2\)
:

\(c^2 = (m \cdot x + b)^2 = m^2 \cdot x^2 + 2 \cdot m \cdot x \cdot b + b^2 = m \cdot ( m \cdot x^2 + 2 \cdot x \cdot b) + b^2\)
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:

\(c^2 = b^2 \mod m\)

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?

EvilBro

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:

\(e^r = 1 \mod m\)

Als je die r gevonden hebt dan weet je dat:

\(d = e^{r-1}\)

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[wiskunde] rsa vercijfering/modulair rekenen

[wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen

Re: [wiskunde] rsa vercijfering/modulair rekenen