RSA-The Math

Page #4355454 of Chapter:


level indicator


RSA calls for Alice to pick two equal size large primes: P, and Q, then:

  • compute n=P*Q
  • compute Z = (p-1)*(q-1)
  • pick a secret encryption key e from the range: 0,1,2.....(n-1) such that it is coprime with Z: gcd(Z,e)=1
  • find a corresponding decryption key, d to satisfy: e*d = 1 mod Z
  • define encryption over any plaintext number P, from the series 0,1,2....(n-1), as C = Pe
  • decrypt C back to P by computing: P = Cd

    So any number from 0,1,...(n-1) can be encrypted to another number from the same set, and decrypted back to the original using two different keys: e and d.

    To deduce e from d or vice versa one has to know the value of Z. To find Z one needs to find p and q, and for that one needs to factor n=pq, since n is in the open to practice both encryption and decryption.

    To properly use RSA one needs to pick p and q sufficiently large to insure that the adversarial computing power will not be able to factor n in a timely manner. .....

    Fredrick Gauss and his followers managed to estimate the frequency of primes, and accordingly, we are assured of a sufficiently large supply for RSA keys... ......

    In 1903, Professor Cole at Columbia University was met with standing ovations when he managed a feat: finding the prime ingredients for the largest number that was ever decomposed to its two large primes: 267-1:

    267-1 = 193,707,721 x 761,838,257,287

  • * Version CE-H6703 (SERVER) Crypto Academy