Back rsa2.shtml Next

RSA - The Algorithm

  • Given:
    • primes p, q randomly generated
    • n = pq
    • a, b s.t. ab ::: 1 (mod phi(n)) ::: = is congruent
      • phi(n) = number of n's relative primes
    • x, y are in the set of n's relative primes

  • Private key is made of [p, q, a]
  • Public key is made of [n, b]

  • Encryption and Decryption equations
    • E(x) = y = x^a mod n
    • D(y) = x = y^b mod n
  • Why does this work?
    • Take the plain text value, x = y^b mod n
    • Substitute y = x^a mod n into equation
    • x = (x^a mod n)^b mod n
    • x = x^ab mod n

    • ab ::: 1 (mod phi(n))
    • ab mod phi(n) = 1 mod phi(n)
    • ab mod phi(n) = 1, given n > 1
    • ab = t * phi(n) + 1

    • x = x^(t * phi(n) + 1) (mod n)
    • x = (x^(phi(n)))^t * x (mod n)

    • if x is an element of n's relative's primes, x^phi(n) (mod n) = 1

    • x = 1^t * x (mod n)
    • x = x (mod n)

Copyright 1997 by Slackers Union. Comments should go to any of the group members. Opinions reflected on this page are by no means opinions of UCSD. Go sue somebody else.

Last Modified: June 1st, 1997