RSA algorithme Priemgetallen

[Verwijderd]

Hallo, we zijn aan het leren voor een cryptolgie tentamen.
We komen er even niet uit,

Vraag:
Bij de methode van Diffie helman word de K aan beide zijden door de andere publieke sluetel te verheffen tot de macht de eigen sleutel modulo q.
Deze berekening werkt voor alle waarden van q!
Ook de berekening van de publieke sleutel uit de geheime sleutel vmet alfa werkt
voor alle waarden van alpha.

Waarom stelt men als eis dat alpha een primitieve wortel van q moet zijn?
(hint denk aan de aanvaller).

Nou, we snappen er niks van , Kan iemand ons op weg helpen?
Dus waarom gebruikt je twee priemgetallen om N te berekenen (n=p*q)
en niet gewoon te normale getallen?

HELP

[bankrupcy]

Stel dat p en q geen priemgetallen zijn: dan geldt: N=p1*p2*q1*q2 (p=p1*p2; q=q1*q2)
dat zijn dus al 4 getallen waarmee N te vinden is, en wat belangrijker is: de getallen bevinden zich in de orde sqrt(sqrt(N)) wat belangrijk lager is dan p (orde sqrt(N) ). Daarmee zijn p1 e.d. dus veel makkelijker te vinden dan p en q.

Waarschijnlijk kan dit makkelijker gezegd worden....

[TheLunatic]

Niet om het een of ander, maar volgens mij is dit een ordinaire huiswerkvraag

[Verwijderd]

huiswerk ? nee!
We hebben morgen een tentamen en we snappen er niks van

[DroogKloot]

Omdat alleen als p en q priem zijn geldt

x^(p-1) = 1 (mod p) (evenzo voor q)

ofwel de relatie tussen exponent en modulus waar RSA op gebaseerd is, want de reeks A (1, 2,..., (p-1)) bestaat enkel uit copriemen en dus ook alle getallen in (mod p). Stel namelijk de reeks B (x (mod p)*1, x (mod p)*2, x (mod p)*...(p-1)), dan zijn zowel x en elk element van A copriem met p en dus ook elk element van B. Nog belangrijker: B is distinct, want xBi = xBj (mod p) met i != j --> Bi = Bj (mod p)
als x != 0, maar B is distinct, dus contradictie. En omdat B alle getallen in (mod p) gebruikt die copriem zijn met p, is -ie een permutatie van A. Ga maar na:
B(1)*B(2)*...B(p-1) = A(1)*A(2)*...A(p-1) (mod p) -->
xA(1)*xA(2)*...xA(p-1) = A(1)*A(2)*... A(p-1) (mod p) --> wegdelen -->

x^(p-1) = 1 (mod p)

Er zijn trouwens meer redenen, maar de wiskundige achtergrond van RSA is redelijk tricky.

[Christiaan]

Zoals gezegd; het betreft een typische huiswerkvraag en dat hoort niet in W&L.

Je kunt hier terecht voor informatie:
http://www.ifs.univie.ac.at/~os/encrypti.htm (met dank aan OpifexMaximus).