Hallo,
Momenteel bezig met mijn profielwerstuk over RSA.
Ik zit echter met een probleem, aangezien de vercijferings en ontcijferings methodes bij mij niet helemaal goed uitkomen. Niet altijd, overigens.
De formules zijn als volgt:
- Men neme een woord, wat je omzet in cijfers. A = 01 B = 02 etc, of volgens de ASCII tabel. dit woord is 'x'
- Je kiest 2 priemgetallen, die vermenigvuldig je met elkaar, dat is je modulus. Ik heb 13 en 23 gekozen. M = 13 x 23 = 299
- je berekent N = (p-1)(q-1), oftewel 12 x 22 = 264
- je kiest de E doormiddel van ggd(e,264) = 1. Hiervoor heb ik 7 gekozen.
- Vercijfer het dmv de formule: E(x) = x^e (mod m.)
- bereken de 'd'. via een calculator op internet is hier 151 uitgekomen.
- ontcijfer het dmv de formule: D(y) = y^d (mod m)
Mijn probleem is dat het soms wel en soms niet werkt. Als ik volgens de ASCII tabel de letter 'X' ga vercijferen (88), dan komt alles mooi uit en krijg ik als ik het ontcijfer ook weer de 88 terug.
Ook een random klein getal, 10 bijv. blijkt ook te werken.
Maar ga ik bijvoorbeeld het getal 162319 vercijferen, dan krijg ik een totaal ander getal. Het lijkt wel alsof het bij grotere getallen niet meer werkt?
Iemand ideeen waaraan het zou kunnen liggen ?
Alvast bedankt,
Maarten.
RSA probleem
Re: RSA probleem
Je vercijfert met E(x) = x^e (mod m)
Dit getal kan nooit groter of gelijk aan m zijn, je kan dus ook nooit meer dan m verschillende woorden x vercijferen.
Kies daarom grotere priemgetallen (groot genoeg om je grootste woord te coderen).
Dit getal kan nooit groter of gelijk aan m zijn, je kan dus ook nooit meer dan m verschillende woorden x vercijferen.
Kies daarom grotere priemgetallen (groot genoeg om je grootste woord te coderen).
Laatst gewijzigd door arie op 04 jan 2009, 07:55, 1 keer totaal gewijzigd.
Re: RSA probleem
Aaah dat is het ^^
Dankjewel
Dankjewel
Re: RSA probleem
Hoewel nu de vercijferingen en ontcijferingen goed werken, toch nog even een vraagje:
Of, je ziet de formule verkeerd (wat heel goed denkbaar is), aangezien de 'officiele' formule voor modulus:
a = c (mod m)
waar A het gekozen getal is, M de gekozen modulus en C het antwoord (De 'rest').
E(x) = x^e (mod m), wil niet zeggen dat er een E(x) is, met als rest x^e, maar dat je simpelweg van links naar rechts moet rekenen.
Oftewel eerst x^e uitrekenen, en dan zo vaak mogelijk M eraf trekken. Het antwoord wat je dan krijgt (de 'rest') is de vercijferde boodschap.
Misschien is daarom je uitleg niet 100% kloppend.
Of ik snap het principe gewoon niet.
Je doet x^e, en een dikke kans dat die uitkomst groter is dan de M
Waarom zou dan de M groter moeten zijn dan x?
persoonlijk denk ik dat ik het principe niet snap overigens ^^
Of, je ziet de formule verkeerd (wat heel goed denkbaar is), aangezien de 'officiele' formule voor modulus:
a = c (mod m)
waar A het gekozen getal is, M de gekozen modulus en C het antwoord (De 'rest').
E(x) = x^e (mod m), wil niet zeggen dat er een E(x) is, met als rest x^e, maar dat je simpelweg van links naar rechts moet rekenen.
Oftewel eerst x^e uitrekenen, en dan zo vaak mogelijk M eraf trekken. Het antwoord wat je dan krijgt (de 'rest') is de vercijferde boodschap.
Misschien is daarom je uitleg niet 100% kloppend.
Of ik snap het principe gewoon niet.
Je doet x^e, en een dikke kans dat die uitkomst groter is dan de M
Waarom zou dan de M groter moeten zijn dan x?
persoonlijk denk ik dat ik het principe niet snap overigens ^^
Re: RSA probleem
Bij modulo m rekenen gebruiken we m getallen, vaak van 0 t/m (m-1).
Alle getallen die bij deling door m dezelfde rest geven zijn dan gelijkwaardig, bijvoorbeeld:
2009 (mod 10) = 169 (mod 10) = 9 (mod 10)
modulo 10 hebben we 10 verschilldende restklassen, die we hier aangeven met 0 t/m 9.
De functie E(x) geeft de vercijfering (E van encryptie) van woord x.
E(x) = x^e (mod m).
Je mag ook stellen:
E(x) = x^e (mod m) = (x (mod m))^e (mod m)
Als 0 <= x <= m-1, dan heeft dit laatste geen invloed, maar als x>=m heeft dit wel effect.
In je eerste voorbeeld:
E(162319) = 162319^7 (mod 299) = (162319 (mod 299))^7 (mod 299) = 261^7 (mod 299) = 196
dus E(162319) = E(261) = E(261 + k*299) = 196 (mod 299) [waarbij k een geheel getal]
met andere woorden:
als al deze getallen hetzelfde vercijferingsresultaat geven, kunnen we ze na het terug ontcijferen ook niet van elkaar onderscheiden,
ofwel:
door het (mod m) rekenen beeldt E elk getal x af op een getal E(x) van 0 t/m (m-1), we hebben dus maximaal m gecodeerde woorden E(x), dus kunnen we ook maximaal m woorden x vercijferen.
(overigens: RSA zorgt ervoor (door de keuze van e) dat ook alle m verschillende woorden E(x) bereikt worden en dat we dus precies m woorden kunnen vercijferen).
De ontcijfering D(y) (met D van decryptie) levert hier:
D(196) = 196^151 (mod 299) = 261
een getal van 0 t/m 298.
In feite is D(196) = 261 (mod 299) = 261 + k*299 [met k een geheel getal].
De waarde van k kunnen we niet uit de ontcijfering afleiden, daarom nemen we doorgaans de oncijferingswaarden tussen 0 en (m-1), hier van 0 t/m 298.
Hierdoor heeft x ook deze grenzen.
Alle getallen die bij deling door m dezelfde rest geven zijn dan gelijkwaardig, bijvoorbeeld:
2009 (mod 10) = 169 (mod 10) = 9 (mod 10)
modulo 10 hebben we 10 verschilldende restklassen, die we hier aangeven met 0 t/m 9.
De functie E(x) geeft de vercijfering (E van encryptie) van woord x.
E(x) = x^e (mod m).
Je mag ook stellen:
E(x) = x^e (mod m) = (x (mod m))^e (mod m)
Als 0 <= x <= m-1, dan heeft dit laatste geen invloed, maar als x>=m heeft dit wel effect.
In je eerste voorbeeld:
E(162319) = 162319^7 (mod 299) = (162319 (mod 299))^7 (mod 299) = 261^7 (mod 299) = 196
dus E(162319) = E(261) = E(261 + k*299) = 196 (mod 299) [waarbij k een geheel getal]
met andere woorden:
als al deze getallen hetzelfde vercijferingsresultaat geven, kunnen we ze na het terug ontcijferen ook niet van elkaar onderscheiden,
ofwel:
door het (mod m) rekenen beeldt E elk getal x af op een getal E(x) van 0 t/m (m-1), we hebben dus maximaal m gecodeerde woorden E(x), dus kunnen we ook maximaal m woorden x vercijferen.
(overigens: RSA zorgt ervoor (door de keuze van e) dat ook alle m verschillende woorden E(x) bereikt worden en dat we dus precies m woorden kunnen vercijferen).
De ontcijfering D(y) (met D van decryptie) levert hier:
D(196) = 196^151 (mod 299) = 261
een getal van 0 t/m 298.
In feite is D(196) = 261 (mod 299) = 261 + k*299 [met k een geheel getal].
De waarde van k kunnen we niet uit de ontcijfering afleiden, daarom nemen we doorgaans de oncijferingswaarden tussen 0 en (m-1), hier van 0 t/m 298.
Hierdoor heeft x ook deze grenzen.
Re: RSA probleem
Ok, nu is het duidelijk
Dankjewel.
Dankjewel.