Cryptology 403The numbers in the previous example were chosen for their relevance to
RSA. Assuming the values for P and Q are 11 and 13, N would be 143. There-
fore, φ(N) = 120 = (11 − 1) · (13 − 1). Since 7253 is relatively prime to 120,
that number makes an excellent value for E.
If you recall, the goal was to find a value for D that satisfies the following
equation:
E· D= S·φ(N)+1
Some basic algebra puts it in a more familiar form:
D · E+ S·φ(N)=1
D ·7253±S·120=1
Using the values from the extended Euclidean algorithm, it’s apparent
that D = −43. The value for S doesn’t really matter, which means this math
is done modulo φ(N), or modulo 120. That, in turn, means that a positive
equivalent value for D is 77, since 120 − 43 = 77. This can be put into the
prior equation from above:
E· D= S·φ(N)+1
7253 · 77 = 4654 · 120 + 1
The values for N and E are distributed as the public key, while D is
kept secret as the private key. P and Q are discarded. The encryption and
decryption functions are fairly simple.
Encryption: C= ME(modN)
Decryption: M= CD(modN)
For example, if the message, M, is 98, encryption would be as follows:
987253 = 76(mod143)
The ciphertext would be 76. Then, only someone who knew the value for
D could decrypt the message and recover the number 98 from the number 76,
as follows:
7677 = 98(mod143)
Obviously, if the message, M, is larger than N, it must be broken down
into chunks that are smaller than N.
This process is made possible by Euler’s totient theorem. It states that
ifM and N are relatively prime, with M being the smaller number, then
when M is multiplied by itself φ(N) times and divided by N, the remainder
will always be 1:
If gcd(M, N) = 1 and M < N then Mφ(N) = 1(modN)