To encrypt a message, convert your message into a large integer *m*.
Then calculate *c = m ^{e} (*modulo

- Set
*x[0] = (p-1)*(q-1)* - Set
*y[0] = 0* - Set
*x[1] = e* - Set
*y[1] = 1* - Then while
*x[i] > 0*calulate:*x[i] = x[i-2]*modulo*x[i-1]**y[i] = y[i-2] -*floor*( x[i-2] / x[i-1] ) * y[i-1]*

- You can show by induction that
*x[i] ≡ e * y[i] (*modulo*(p-1)*(q-1) )*, so if*x[i] = 1*we know both that*e*is relatively prime to*(p-1)*(q-1)*, and that*y[i] (*modulo*(p-1)*(q-1) )*is the corresponding value for*d*

When we calculate the keys, we calculate four additional values:

*d1 = d (*modulo*p-1)**d2 = d (*modulo*q-1)**p*modulo^{-1}(*q)*- Use the same algorithm we used to calculate the decryption exponent*d*above*q*modulo^{-1}(*p)*

*M*modulo_{p}= m^{d1}(*p)**M*modulo_{q}= m^{d2}(*q)*

Return to my home page

Go to the EKU CS Department page